User:AkaDonlon/wip/维特比解码器

维特比解码器使是一种使用维特比算法的解码器，可以对卷积码或网格码编码的比特流进行解码。

除了维特比算法外，还有其他算法可对卷积码进行解码（如Fano 算法）。 相比之下，维特比算法最消耗资源，但它可以进行最大似然解码。它最常用于解码约束长度 k ≤ 3 的卷积码，但实际使用的值高达 k=15。

维特比解码由 Andrew J. Viterbi 开发并发表在论文 Viterbi, A. Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm. IEEE Transactions on Information Theory. April 1967, 13 (2): 260–269. doi:10.1109/tit.1967.1054010.  “卷积码的误差界限和渐近最优解码算法”。 IEEE 信息论汇刊。 13 (2): 260–269。 doi ： 10.1109/tit.1967.1054010 。

Viterbi 解码器有硬件（如应用在调制解调器中）和软件实现。

维特比解码用于迭代维特比解码算法。

硬件实现

硬件维特比解码器的常见实现途径

用于基本（未穿孔）代码的硬件维特比解码器通常由以下主要模块组成：

• 分支度量单元 (Branch metric unit, BMU)
• 路径度量单位（Path metric unit, PMU）
• 回溯单元 (Traceback unit, TBU)

分支度量单元 (BMU)

分支度量单元的一种实现方式

分支度量单元的功能是计算分支度量，它是代码字母表中每个可能符号与接收符号之间的归一化距离。

维特比解码器的判决方式被分为硬判决和软判决。硬判决维特比解码器将简单的比特流作为输入，并用汉明距离作为每个符号的度量。而软判决维特比解码器接收的比特流还包含关于每个接收符号的可靠性的信息。例如，如果使用 3 位编码，可靠性信息可以编码如下：

值	含义
000	最强	0
001	比较强	0
010	比较弱	0
011	最弱的	0
100	最弱的	1
101	比较弱	1
110	比较强	1
111	最强	1

当然，这不是唯一对可靠性数据进行编码的方法。

在软判决解码器中，欧几里得距离的平方值常用作度量值。

路径度量单元（PMU）

特定 K=4 解码器的路径度量单元的示例实现

路径度量单元总结了分支度量以获取度量$2^{K-1}$路径，其中 K 是代码的约束长度，最终可以选择其中之一作为优化。它制造的每一个时钟$2^{K-1}$决策，故意抛弃非最佳路径。这些决定的结果被写入回溯单元的内存中。

PMU 的核心元素是ACS（相加-比较-选择）单元。它们之间的连接方式由特定代码的网格图定义。

由于分支指标总是$\geq 0$ ，必须有一个额外的电路（图中未显示）防止公制计数器溢出。无需监视路径度量增长的另一种方法是允许路径度量“滚动”；要使用此方法，必须确保路径度量累加器包含足够的位以防止“最佳”和“最差”值彼此^{相差 2 (n-1) 以内。}比较电路基本上没有变化。

ACS 单元的一种实现方式

通过监控“最佳”路径度量的增长率，可以监控传入比特流上的噪声水平。一种更简单的方法是监视单个位置或“状态”并观察它“向上”通过累加器范围内的四个离散级别。当它向上通过这些阈值中的每一个时，计数器会递增，以反映传入信号中存在的“噪声”。

回溯单元 (TBU)

回溯单元的一种实现方式

回溯单元从路径度量单元的输出中恢复（几乎）最大似然路径。由于它是在相反的方向上进行的，因此维特比解码器包括一个 FILO（先进后出）缓冲器来重建正确的顺序。

请注意，图像上显示的实现需要双倍频率。有一些技巧可以消除这种要求。

实现问题

软判决解码的量化

为了充分利用软判决解码的优势，需要对输入信号进行适当的量化。最佳量化区宽度由以下公式定义：

$\,\!T={\sqrt {\frac {N_{0}}{2^{k}}}},$

在哪里$N_{0}$是噪声功率谱密度， k是软判决的位数。

欧几里得度量的计算

平方范数（ $\ell _{2}$ ) 码字母表中接收到的符号和实际符号之间的距离可以进一步简化为线性和/差形式，从而降低计算强度。

考虑一个1/2卷积编码器，其产生对每个输入位（1或0）的2位'（00，01，10'或11）。这些归零信号被转换为旁边显示的非归零形式。

代码字母表	矢量映射
00	+1, +1
01	+1，-1
10	−1, +1
11	-1, -1

每个接收符号可以向量形式表示为v _r = {r ₀, r ₁ }，其中r ₀和r ₁是软判决值，其大小表示接收向量v _r的联合可靠性。

欧几里得距离度量的实际计算是：

$\,\!D=({\overrightarrow {v_{r}}}-{\overrightarrow {v_{i}}})^{2}={\overrightarrow {v_{r}}}^{2}-2{\overrightarrow {v_{r}}}{\overrightarrow {v_{i}}}+{\overrightarrow {v_{i}}}^{2}$

每个平方项是一个赋范距离，描述了符号的能量。例如，符号v _i = {±1, ±1}的能量可以计算为

$\,\!{\overrightarrow {v_{i}}}^{2}=(\pm 1)^{2}+(\pm 1)^{2}=2$

因此，代码字母表中所有符号的能量项是常数（在（归一化）值 2 处）。

Add-Compare-Select ( ACS ) 操作比较接收到的符号||v _r || 之间的度量距离以及代码字母表中的任何 2 个符号，其路径在相应格子中的节点处合并， ||v _i ⁽⁰⁾ ||和||v _i ⁽¹⁾ || .这相当于比较

$\,\!D_{0}={\overrightarrow {v_{r}}}^{2}-2{\overrightarrow {v_{r}}}{\overrightarrow {v_{i}^{0}}}+{\overrightarrow {v_{i}^{0}}}^{2}$

和

$\,\!D_{1}={\overrightarrow {v_{r}}}^{2}-2{\overrightarrow {v_{r}}}{\overrightarrow {v_{i}^{1}}}+{\overrightarrow {v_{i}^{1}}}^{2}$

但是，从上面我们知道v _i的能量是常数（等于（归一化）值 2），并且v _r的能量在两种情况下是相同的。这减少了与 2 个（中间）点积项之间的最小值函数的比较，

$\,\!\min(-2{\overrightarrow {v_{r}}}{\overrightarrow {v_{i}^{0}}},-2{\overrightarrow {v_{r}}}{\overrightarrow {v_{i}^{1}}})=\max({\overrightarrow {v_{r}}}{\overrightarrow {v_{i}^{0}}},{\overrightarrow {v_{r}}}{\overrightarrow {v_{i}^{1}}})$

因为min操作可能被解释为对正数max

每个点积项可以扩展为

$\,\!\max(\pm r_{0}\pm r_{1},\pm r_{0}\pm r_{1})$

其中，每一项的符号取决于要比较的符号v _i ⁽⁰⁾和v _i ⁽¹⁾ 。因此，可以用简单的加/减操作来执行平方欧几里德度量距离计算以计算分支度量。

回溯

回溯的一般方法是累积最多五倍约束长度（5（ K -1））的路径度量，找到累积成本最大的节点，并从该节点开始回溯。

卷积码的存储器（约束长度 K -1）的五倍截断深度的常用经验法则仅对速率 1/2 码是准确的。对于任意速率，准确的经验法则是 2.5( K - 1)/(1− r )，其中r是码率。

然而，计算累积最大成本（最大或最小的积分路径度量）的节点涉及找到几个（通常为 2 ^{K -1} ）数的最大值或最小值，这在嵌入式硬件系统上实现时可能很耗时。

大多数通信系统采用维特比解码，涉及固定大小的数据包，在数据包的开头或/和结尾具有固定的位/字节模式。通过使用已知的位/字节模式作为参考，可以将起始节点设置为固定值，从而在回溯期间获得完美的最大似然路径。

限制

由于输入信号的量化、分支和路径度量以及有限的回溯长度，维特比解码器的物理实现不会产生精确的最大似然流。实际实现确实接近理想值的 1dB 以内。

维特比解码器的输出，在解码被加性高斯信道损坏的消息时，错误分组为错误突发。 单单纠错码无法纠正此类突发，因此卷积码和维特比解码器必须设计得足够强大以将错误降低到可接受的速率，或者必须使用突发纠错码。

打孔代码

打孔码的硬件维特比解码器通常以这样的方式实现：

• 一个 depuncturer，它将输入流转换为看起来像原始（未打孔）流的流，在位被擦除的位置带有 ERASE 标记。
• 理解这些 ERASE 标记的基本维特比解码器（即，不将它们用于分支度量计算）。

软件实现

在软件实现中，最耗时的操作之一是 ACS 的蝶形运算过程，通常使用汇编语言和适当的指令集扩展（例如SSE2 ）来实现，以加快解码时间。

应用

维特比解码算法广泛应用于以下领域：

• 无线电通信：数字电视（ ATSC 、 QAM 、 DVB-T等）、无线电中继、卫星通信、业余无线电的PSK31数字模式。
• 解码网格编码调制（TCM，电话线调制解调器中使用的一种技术），可从 3 kHz的带宽 个中挤出高频谱效率 kHz 带宽模拟电话线。
• 计算机存储设备，如硬盘驱动器。
• 自动语音识别

 

外部链接

• Forney. The Viterbi Algorithm: A Personal History. arXiv:cs/0504020 . 
• Details on Viterbi decoding, as well as a bibliography.
• Viterbi algorithm explanation with the focus on hardware implementation issues.
• r=1/6 k=15 coding for the Cassini mission to Saturn.
• Online Generator of optimized software Viterbi decoders (GPL).
• GPL Viterbi decoder software for four standard codes.
• Description of a k=24 Viterbi decoder, believed to be the largest ever in practical use.
• Generic Viterbi decoder hardware (GPL).

[[Category:错误检测与校正]] [[Category:資料傳輸]]