《计算机组成与体系结构（原书第4版）》 —3.6.6　时序逻辑的应用：卷积编码和维特比检测

3.6.6　时序逻辑的应用：卷积编码和维特比检测

在数据存储和通信中采用几种编码方法。其中之一是部分响应最大似然（PRML）编码方法。以前的讨论（这不是理解本节的前提）主要关注PRML的“部分响应”部分。“最大似然”分量来自对位进行编码和解码的方式。解码过程的显著特征是只有某些位模式有效。这里使用卷积码产生这种模式。维特比译码器读取通过卷积解码器产生的位，并且将读取的符号流与一组“可能”符号流进行比较，选择错误最少的一个输出。提出下面讨论的原因是它汇集了一系列本章以及第2章中给出的概念。下面从编码过程开始讨论。

在第2章中引入的汉明码是一种使用数据块（或块编码）来计算必要冗余位的前向纠错类型。一些应用需要适合连续数据流的编码技术，例如来自卫星电视发射机的数据流。卷积编码是对输入串行位流进行操作的方法，并生成编码的串行输出流（包括冗余位），使其能够连续校正错误。卷积码是一种编码过程，输出是输入和先前接收的一些位数的函数。因此，输入在自身上重叠或卷积以形成输出符号流。在某种意义上，卷积码构建用于输出精确解码的上下文。卷积编码与维特比解码结合成为在编码和解码存储数据或在不完全（噪声）介质上传输的公认的工业标准。

图3-33显示了在PRML中使用的卷积编码机制。仔细观察这个电路，它揭示了两个输出位写入到了每个输入位中。第一个输出位是输入位和第二个先前输入位的函数：A XOR C。第二位是输入位和两个先前位的函数：A XOR C XOR B。在图的右侧有两个与门，当时钟脉冲到来时交替选择这些函数中的每一个。每一个时钟脉冲的输入通过D触发器移位。注意，最左边的触发器仅用作缓冲器输入，但并不是绝对必需的。

乍一看，可能不容易看到编码器如何为每个输入位产生两个输出位。诀窍是位于时钟和电路其他组件之间的触发器。当该触发器的互补输出反馈到输入时，触发器交替地存储0和1。因此，每隔一个时钟周期，输出变为高电平，每个周期应使能和禁止正确的与门。

图3-33　PRML卷积编码器

我们逐步完成图3-34所示的一系列时钟周期。假定编码器初始状态是标记为A、B和C的触发器中包含所有0。将第一个输入移入A触发器（缓冲器）和编码器输出两个0需要两个时钟周期。图3-34a显示了编码器传递到触发器A输出后的第一个输入（1）。看到触发器A、B和C上的时钟被使能，上面的与门也被使能。因此，函数A XOR C被路由到输出。在下一个时钟周期（见图3-34b），下面的与门被使能，函数A XOR C XOR B路由到输出。然而，因为触发器A、B和C的时钟被禁止，所以输入位不能从触发器A传播到触发器B，以防止在第二个输出写入时下一个输入位被消耗。在时钟周期3（见图3-34c），输入通过触发器A传播，并且触发器A中的位已经传播到触发器B。输出上面的与门被使能，并且函数A XOR C被路由到输出。

图3-34　通过卷积编码器的4个时钟周期

图3-34　（续）

该电路的特性表如表3-13所示。举个例子，考虑输入位流11010010。编码器最初包含所有0，所以B=0且C=0。此时编码器处于状态0（002）。当输入流的第一个1离开缓冲器时A、B=0且C=0，给出（A XOR C XOR B）=1和（A XOR C）=1。输出为11，编码器转换到状态2（102）。下一个输入位为1，有B=1和C=0（处于状态2），得到（A XOR C XOR B）=0和（A XOR C）=1，输出为01，编码器转换到状态1（012）。在保留剩余的六个位之后，完成的函数是：F（1101 0010）=11 01 01 00 10 11 11 10

表3-13　图3-33所示的卷积编码器的特性表

使用米莉机会使编码过程更清楚一些（见图3-35）。这个图一目了然地显示了哪些转换是可能的，哪些是不可能的。在图3-35中你可以看到特性表与机器之间的对应关系，这个表是通过读取表和跟踪弧获得的。事实上，对代码错误校正属性和维特比译码器操作至关重要的是具有有限的转换，译码器负责正确地解码位流。如图3-36所示，通过过渡弧上的输出反转输入，围绕该组可能的解码输入放置边界。

图3-35　图3-33所示的卷积编码器的米莉机　　　图3-36　卷积解码器的米莉机

例如，假设解码器处于状态1并且模式是00 01。返回的解码位值为11，并且解码器在状态3中结束。（路径遍历是1→2→3。）另一方面，如果解码器处于状态2并且模式是00 11，由于在状态2上没有用于00的出口转换，因此发生错误。状态2上的出口转换是01和10，它们两个都有一个从00开始的汉明距离1。如果跟随两个（同样相等的）路径离开状态2，解码器最终处于状态1或状态3。可以看到对于下一个位对11，在状态3上没有出口转换。来自状态3的每个出口转换都具有从11开始的汉明距离1。对于两个路径2→3→1和2→3→2，它们的累积汉明距离为2。然而，状态1在11上具有有效转变。通过采用路径2→1→0，累积误差只有1，所以这是最有可能的序列。因此，输入的最大似然解码为00。

表示这个思路的一种等价（也许更清楚）方式是网格图，如图3-37所示。4个状态在图的左边显示。从左到右读取转换（或时间）组件。卷积码中的每个码字都与网格图中的唯一路径相关联。维特比译码器使用与此图等效的逻辑路径确定最可能的位模式。在图3-37中，译码器在状态1开始遇到输入序列00 10 11 11时，状态转换发生。读者可以比较网格图中的转换与图3-36所示的米莉图中的转换。

假设在输入的第一个位对中引入一个错误，给出错误的串是10 10 11 11。如前所述，译码器在状态1中开始，图3-38通过网格跟踪可能的路径。累积的汉明距离显示在每个过渡圆弧上。正确的路径应是具有最小路径累积误差的字符串，假设这个字符串是00 10 11 11，因此它被接受为正确的序列。

图3-37　描述序列00 10 11 11状态转换的网格图　图3-38　描述序列10 10 11 11汉明误差的网格图

在应用维特比译码器的大多数情况下，译码器仅提供一个电平误差校正。在维特比算法产生一个干净的符号流之后，会应用附加的纠错机制，例如循环冗余校验和里德-所罗门编码（在第2章中讨论）。使用本章中描述的数字构建块，所有这些算法通常能以最快的速度在硬件中实现。

希望本节的讨论能帮助读者了解数字化逻辑和纠错算法是如何配合在一起使用的。当然，任何算法都可以做到，只要其可以使用有限状态机来表示。实际上，刚才描述的卷积码也被称为（2，1）卷积码，因为对于每一个符号输入会输出两个符号。其他卷积码提供了更复杂的误差校正，但它们很难通过经济实惠的硬件来实现。