跳转至

第11章 差错控制编码

11.1 概述

数字信号在传输过程中，由于受到干扰的影响，码元波形将变坏。接收端收到后可能发生错误判决。由乘性干扰引起的码间串扰，可以采用均衡的办法纠正。而加性干扰的影响则需要用其他办法解决。在设计数字通信系统时，应该首先从合理选择调制制度、解调方法以及发送功率等方面考虑，使加性干扰不足以影响达到误码率要求。在仍不能满足要求时，就要考虑采用本章所述的差错控制措施了。一些通用的系统，其误码率要求因用途而异，也可以把差错控制作为附加手段，在需要时加用。

从差错控制角度看，按照加性干扰引起的错码分布规律的不同，信道可以分为三类，即随机信道 (random channel)、突发信道 (burst channel) 和混合信道 (mixed channel)。在随机信道中，错码的出现是随机的，而且错码之间是统计独立的。例如，由正态分布白噪声引起的错码就具有这种性质。在突发信道中，错码是成串集中出现的，即在一些短促的时间段内会出现大量错码，而在这些短促的时间段之间存在较长的无错码区间。这种成串出现的错码称为突发错码。产生突发错码的主要原因之一是脉冲干扰，例如电火花产生的干扰。信道中的衰落现象也是产生突发错码的另一个主要原因。我们把既存在随机错码又存在突发错码，且哪一种都不能忽略不计的信道称为混合信道。对于不同类型的信道，应该采用不同的差错控制技术。差错控制技术主要有以下 4 种。

（1）检错 (error detection) 重发 (retransmission): 在发送码元序列中加入差错控制码元，接收端利用这些码元检测到有错码时，利用反向信道通知发送端，要求发送端重发，直到正确接收为止。所谓检测到有错码，是指在一组接收码元中知道有一个或一些错码，但是不知道该错码应该如何纠正。在二进制系统中，这种情况发生在不知道一组接收码元中哪个码元错了。因为若知道哪个码元错了，将该码元取补即能纠正，即将错码 “0” 改为 “1” 或将错码 “1” 改为 “0” 就可以了，不需要重发。在多进制系统中，即使知道了错码的位置，也无法确定其正确取值。

采用检错重发技术时，通信系统需要有双向信道传送重发指令。

(2) 前向纠错：前向纠错一般简称 FEC。这时接收端利用发送端在发送码元序列中加入的差错控制码元，不但能够发现错码，还能将错码恢复其正确取值。在二进制码元的情况下，能够确定错码的位置，就相当于能够纠正错码。

采用 FEC 时，不需要反向信道传送重发指令，也没有因反复重发而产生的时延，故实时性好。但是为了能够纠正错码，而不是仅仅检测到有错码，和检错重发相比，需要加入更多的差错控制码元。故设备要比检测重发设备复杂。

以上几种技术可以结合使用。例如，检错和纠错技术结合使用。当接收端出现少量错码并有能力纠正时，采用前向纠错技术；当接收端出现较多错码没有能力纠正时，采用检错重发技术。

在上述四种技术中，除第 (3) 种外，其共同点是都在接收端识别有无错码。由于信息码元序列是一种随机序列，接收端无法预知码元的取值，也无法识别其中有无错码。所以在发送端需要在信息码元序列中增加一些差错控制码元，它们称为监督 (check) 码元。这些监督码元和信息码元之间有确定的关系，譬如某种函数关系，使接收端有可能利用这种关系发现或纠正可能存在的错码。

差错控制编码常称为纠错编码 (error-correcting coding)。不同的编码方法，有不同的检错或纠错能力。有的编码方法只能检错，不能纠错。一般说来，付出的代价越大，检 (纠) 错的能力越强。这里所说的代价，就是指增加的监督码元多少，它通常用多余度来衡量。例如，若编码序列中平均每两个信息码元就添加一个监督码元，则这种编码的多余度为 1/3。或者说，这种码的编码效率 (code rate, 简称码率) 为 2/3。设编码序列中信息码元数量为 k, 总码元数量为 n, 则比值 k/n 就是码率；而监督码元数 (n-k) 和信息码元数 k 之比 (n-k)/k 称为冗余度 (redundancy)。

从理论上讲，差错控制是以降低信息传输速率为代价换取提高传输可靠性。本章的主要内容就是讨论各种常见的编码和解码方法。在此之前，下面先简单介绍一下用检错重发方法实现差错控制的原理。采用检错重发法的通信系统通常称为自动要求重发 (ARQ) 系统。最早的 ARQ 系统称作停止等待 (stop-and-wait) ARQ 系统，其工作原理示于图 11-1 (a) 中。在这种系统中，数据按分组发送。每发送一组数据后发送端等待接收端的确认 (ACK) 答复，然后再发送下一组数据。图 11-1 (a) 中的第 3 组接收数据有误，接收端发回一个否认 (NAK) 答复。这时，发送端将重发第 3 组数据。所以，系统是工作在半双工 (half-duplex) 状态，时间没有得到充分利用，传输效率较低。在图 11-1 (b) 中示出一种改进的 ARQ 系统，它称为拉后 (pullback) ARQ 系统。在这种系统中发送端连续发送数据组，接收端对于每个接收到的数据组都发回确认 (ACK) 或否认 (NAK) 答复 (为了能够看清楚，图中的虚线没有全画出)。例如，图中第 5 组接收数据有误，则在发送端收到第 5 组接收的否认答复后，从第 5 组开始重发数据组。在这种系统中需要对发送的数据组和答复进行编号，以便识别。显然，这种系统需要双工信道。为了进一步提高传输效率，可以采用图 11-1 (c) 所示方案。这种方案称为选择重发 (selective repeat) ARQ 系统，它只重发出错的数据组，因此进一步提高了传输效率。

第 11 章 差错控制编码

ARQ 和前向纠错方法相比的主要优点: ①监督码元较少即能使误码率降到很低，即码率较高；②检错的计算复杂度较低；③检错用的编码方法和加性干扰的统计特性基本无关，能适应不同特性的信道。

ce23410feea601ba8bacf6218f8f7be70ac4303e76efb8bd2d0cde4bc97ede02.jpg

7f4b5ede83dc579d3b2eb09120e603ba24a0486f996bd23fe651724abc5c9ccd.jpg

d57c87c1a8915c1be9dcb01e16de148ec9d7952925b328452440c3c6885f1f29.jpg

但是 ARQ 系统需要双向信道来重发，并且因为重发而使 ARQ 系统的传输效率降低。在信道干扰严重时，可能发生因不断反复重发而造成事实上的通信中断。所以在要求实时通信的场合，例如，电话通信，往往不允许使用 ARQ 法。此外，ARQ 法不能用于单向信道，例如广播网，也不能用于一点到多点的通信系统，因为重发控制难以实现。

图 11-2 示出 ARQ 系统原理方框图。在发送端，输入的信息码元在编码器中被分组编码（加入监督码元）后，除了立即发送外，还暂存于缓冲存储器 (buffer) 中。若接收端解码器检出错码，则由解码器控制产生一个重发指令。此指令经过反向信道送到发送端。这时，由发送端重发控制器控制缓冲存储器重发一次。接收端仅当解码器认为接收信息码元正确时，才将信息码元送给收信者，否则在输出缓冲存储器中删除接收码元。当解码器未发现错码时，经过反向信道发出不需重发指令。发送端收到此指令后，即继续发送后一码组，发送端的缓冲存储器中的内容也随之更新。

11.1 概述

d739e9bef23e0b7939b753cf1db513dac192dbcd9da5632209f71d6390259c9b.jpg

11.2 纠错编码的基本原理

现在先用一个例子说明纠错编码的基本原理。设有一种由 3 位二进制数字构成的码组，它共有 8 种不同的可能组合。若将其全部用来表示天气，则可以表示 8 种不同天气，例如：“000”（晴），“001”（云），“010”（阴），“011”（雨），“100”（雪），“101”（霜），“110”（雾），“111”（雹）。其中任一码组在传输中若发生一个或多个错码，则将变成另一个信息码组。这时，接收端将无法发现错误。

若在上述 8 种码组中只准许使用 4 种来传送天气，例如:

\[ \left\{ \begin{array}{l l} 0 0 0 = \text { 晴 } \\ 0 1 1 = \text { 云 } \\ 1 0 1 = \text { 阴 } \\ 1 1 0 = \text { 雨 } \end{array} \right. \tag {11.2-1} \]

这时，虽然只能传送 4 种不同的天气，但是接收端却有可能发现码组中的一个错码。例如，若 “000”(晴) 中错了一位，则接收码组将变成 “100” 或 “010” 或 “001”。这 3 种码组都是不准使用的，称为禁用码组。故接收端在收到禁用码组时，就认为发现了错码。当发生 3 个错码时，“000” 变成了 “111”, 它也是禁用码组，故这种编码也能检测 3 个错码。但是这种码不能发现一个码组中的两个错码，因为发生两个错码后产生的是许用码组。

上面这种编码只能检测错码，不能纠正错码。例如，当接收码组为禁用码组 “100” 时，接收端将无法判断是哪一位码出错，因为晴、阴、雨三者错了一位都可以变成 “100”。

要想能够纠正错误，还要增加多余度。例如，若规定许用码组只有两个:“000”(晴),“111”(雨), 其他都是禁用码组，则能够检测两个以下错码，或能够纠正一个错码。例如，当收到禁用码组 “100” 时，若当作仅有一个错码，则可以判断此错码发生在 “1” 位，从而纠正为 “000”(晴)。因为 “111”(雨) 发生任何一位错码时都不会变成 “100” 这种形式。但是，这时若假定错码数不超过两个，则存在两种可能性:“000” 错一位和 “111” 错两位都可能变成 “100”, 因而只能检测出存在错码而无法纠正错码。

第 11 章 差错控制编码

从上面的例子中，我们可以得到关于 “分组码” 的一般概念。如果不要求检 (纠) 错，为了传输 4 种不同的消息，用两位的码组就够了，即可以用:“00”、“01”、“10”、“11”。这些两位码称为信息位。在式 (11.2-1) 中使用了 3 位码，增加的那位称为监督位。在表 11-1 中示出此信息位和监督位的关系。这种将信息码分组，为每组信码附加若干监督码的编码称为分组码 (block code)。在分组码中，监督码元仅监督本码组中的信息码元。

表11-1信息位和监督位关系
信息位监督位
晴000
云011
阴101
雨110

分组码一般用符号 \((n,k)\) 表示，其中 n 是码组的总位数，又称为码组的长度（码长），k 是码组中信息码元的数目，n-k=r 为码组中的监督码元数目，或称监督位数目。今后，将分组码的结构规定为具有如图 11-3 所示的形式。图中前 k 位 \((a_{n-1}\cdots a_{r})\) 为信息位，后面附加 r 个监督位 \((a_{r-1}\cdots a_{0})\) 。在式 (11.2-1) 的分组码中 n=3,k=2,r=1，并且可以用符号 (3,2) 表示。

在分组码中，把码组中 “1” 的个数目称为码组的重量，简称码重（code weight）。把两个码组中对应位上数字不同的位数称为码组的距离，简称码距。码距又称汉明（Hamming）距离。例如，式 (11.2-1) 中的 4 个码组之间，任意两个的距离均为 2。我们把某种编码中各个码组之间距离的最小值称为最小码距 \((d_0)\) 。例如，式 (11.2-1) 中编码的最小码距 \(d_0 = 2\) 。

594f34ed4f6ec24ac5361cd13ec3416403cc16560e3b12741022ccd4c0611c21.jpg

对于 3 位的编码组，可以在三维空间中说明码距的几何意义。如前所述，3 位的二进制编码，共有 8 种不同的可能码组。在三维空间中它们分别位于一个单位立方体的各顶点上，如图 11-4 所示。每个码组的 3 个码元的值 \((a_{1}, a_{2}, a_{3})\) 就是此立方体各顶点的坐标。而上述码距概念在此图中就对应于各顶点之间沿立方体各边行走的几何距离。由此图可以直观看出，式 (11.2-1) 中 4 个准用码组之间的距离均为 2。

一种编码的最小码距 \(d_{0}\) 的大小直接关系着这种编码的检错和纠错能力：

(1) 为检测 e 个错码，要求最小码距:

\[ d _ {0} \geqslant e + 1 \tag {11.2-2} \]

这可以用图 11-5 (a) 简单证明如下：设一个码组 \(A\) 位于 \(O\) 点。若码组 \(A\) 中发生一个错码，则可以认为 \(A\) 的位置将移动至以 \(O\) 点为圆心，以 1 为半径的圆上某点，但其位置不会超出此圆。若码组 \(A\) 中发生两位错码，则其位置不会超出以 0 点为圆心，以 2 为半径的圆。因此，只要最小码距不小于 3（例如图中 B 点），在此半径为 2 的圆上及圆内就不会有其他码组。这就是说，码组 A 发生两位以下错码时，不可能变成另一个准用码组，因而能检测错码的位数等于 2。同理，若一种编码的最小码距为 \(d_{0}\) ，则将能检测 \((d_{0}-1)\) 个错码。反之，若要求检测 e 个错码，则最小码距 \(d_{0}\) 至少应不小于 \((e+1)\) 。

e2a502851e8dc95f39560c596d5ef173718651461ed7ffdd247b13b0c4a19636.jpg

59531c4fa523135ddac8dd3c9237fb942cfffdb95aaa81d93545e05efd190e06.jpg

11.2

纠错编码的基本原理

(2) 为了纠正 t 个错码，要求最小码距:

\[ d _ {0} \geqslant 2 t + 1 \tag {11.2-3} \]

此式可用图 11-5 (b) 加以阐明。图中画出码组 \(A\) 和 \(B\) 的距离为 5。码组 \(A\) 或 \(B\) 若发生不多于两位错码，则其位置均不会超出半径为 2 以原位置为圆心的圆。这两个圆是不重叠的。因此，我们可以这样判决：若接收码组落于以 \(A\) 为圆心的圆上就判决收到的是码组 \(A\) ，若落于以 \(B\) 为圆心的圆上就判决为码组 \(B\) 。这样，就能够纠正两位错码。若这种编码中除码组 \(A\) 和 \(B\) 外，还有许多种不同码组，但任两码组之间的码距均不小于 5，则以各码组的位置为中心以 2 为半径画出之圆都不会互相重叠。这样，每种码组如果发生不超过两位错码都将能被纠正。因此，当最小码距 \(d_0 = 5\) 时，能够纠正两个错码，且最多能纠正两个。若错码达到三个，就将落入另一圆上，从而发生错判。故一般说来，为纠正 \(t\) 个错码，最小码距应不小于 \((2t + 1)\) 。

81fccae2dd483a4b8f7c9d5660a0de4b5d507c07280823dabd7b5e53315f493f.jpg

d771cb1892b4e659d7ad74edb4085962fcf0dbf19abc678a5c0cca0e1cfb7270.jpg

df78e26f3b7c0a64327e9715d6b6b1ab05fbdad4bbd793cf4639acb2e0d4ea8a.jpg

(3) 为纠正 t 个错码，同时检测 e 个错码，要求最小码距:

\[ d _ {0} \geqslant e + t + 1 \quad e > t \tag {11.2-4} \]

在解释此式之前，我们先来继续分析一下图 11-5 (b) 所示的例子。图中码组 A 和 B 之间距离为 5。按照式 (11.2-2) 检错时，最多能检测 4 个错码，即 \(e=d_{0}-1=5-1=4\) , 按照式 (11.2-3) 纠错时，能纠正两个错码。但是，不能同时做到两者，因为当错码位数超过纠错能力时，该码组立即进入另一码组的圆内而被错误地 “纠正” 了。例如，码组 A 若错了 3 位，就会被误认为码组 B 错了 2 位造成的结果，从而被错 “纠” 为 B。这就是说，式 (11.2-2) 和式 (11.2-3) 不能同时成立或同时运用。所以，为了在可以纠正 t 个错码的同时，能够检测 e 个错码，就需要像图 11-5 (c) 所示那样，使某一码组 (如码组 A) 发生 e 个错误之后所处的位置，与其他码组 (如码组 B) 的纠错圆圈至少距离等于 1, 不然将落在该纠错圆上从而发生错误地 “纠正”。由此图可以直观看出，要求最小码

第 11 章 差错控制编码

距满足式 \((11.2-4)\) 。

这种纠错和检错结合的工作方式简称纠检结合。这种工作方式是自动在纠错和检错之间转换的。当错码数量少时，系统按前向纠错方式工作，以节省重发时间，提高传输效率；当错码数量多时，系统按反馈重发方式纠错，以降低系统的总误码率。所以，它适用于大多数时间中错码数量很少，少数时间中错码数量多的情况。

11.3 纠错编码的性能

由 11.2 节所述的纠错编码原理可知，为了减少接收错误码元数量，需要在发送信息码元序列中加入监督码元。这样做的结果使发送序列增长，冗余度增大。若仍须保持发送信息码元速率不变，则传输速率必须增大，因而增大了系统带宽。系统带宽的增大将引起系统中噪声功率增大，使信噪比下降。信噪比的下降反而又使系统接收码元序列中的错码增多。一般说来，采用纠错编码后，误码率总是能够得到很大改善的，改善的程度和所用的编码有关。

作为例子，在图 11-6 中示出一种编码的性能。由此图可以看到，在未采用纠错编码时，若接收信噪比保持 7dB，在编码前误码率约 \(8\times10^{-4}\) （图中 A 点），在采用纠错编码后，误码率降至约 \(4\times10^{-5}\) （图中 B 点）。这样，不用增大发送功率就能降低误码率约一个半数量级。由图 11-6 还可以看出，若保持误码率为 \(10^{-5}\) （图中 C 点）不变，未采用编码时，约需要信噪比 \(E_{b}/n_{0}=9.5dB\) 。在采用这种编码时，约需要信噪比 7.5dB（图中 D 点）。可以节省功率 2dB。通常称这 2dB 为编码增益。

上面两种情况付出的代价是带宽增大。

对于给定的传输系统，其传输速率和 \(E_{b}/n_{0}\) 的关系为

\[ \frac {E _ {\mathrm{b}}}{n _ {0}} = \frac {P _ {\mathrm{s}} T}{n _ {0}} = \frac {P _ {\mathrm{s}}}{n _ {0} (1 / T)} = \frac {P _ {\mathrm{s}}}{n _ {0} R _ {\mathrm{B}}} \tag {11.3-1} \]

式中： \(R_{B}\) 为码元速率。

若希望提高传输速率 \(R_{B}\) ，由式 (11.3-1) 可以看出势必使信噪比下降，误码率增大。假设系统原来工作在图中 C 点，提高速率后由 C 点升到 E 点。但是，加用纠错编码后，仍可以将误码率降到原来的水平（图中 D 点）。这时付出的代价仍是带宽增大。

11.4 简单的实用编码

11.4.1 奇偶监督码

奇偶监督 (parity check) 码分为奇数监督码和偶数监督码两种，两者的原理相同。在偶数监督码中，无论信息位多少，监督位只有 1 位，它使码组中 “1” 的数目为偶数，即满足下式条件:

11.4 简单的实用编码

\[ a _ {n - 1} \oplus a _ {n - 2} \oplus \dots \oplus a _ {0} = 0 \tag {11.4-1} \]

式中： \(a_{0}\) 为监督位，其他位为信息位。

表 11-1 中的编码，就是按照这种规则加入监督位的。这种编码能够检测奇数个错码。在接收端，按照式 (11.4-1) 求 “模 2 和”, 若计算结果为 “1” 就说明存在错码，结果为 “0” 就认为无错码。

奇数监督码与偶数监督码相似，只不过其码组中 “1” 的数目为奇数，即满足条件:

\[ a _ {n - 1} \oplus a _ {n - 2} \oplus \dots \oplus a _ {0} = 1 \tag {11.4-2} \]

且其检错能力与偶数监督码的一样。

11.4.2 二维码偶监督码

二维 (two dimensional) 奇偶监督码又称方阵码。它是先把上述奇偶监督码的若干码组，每个写成一行，然后再按列的方向增加第二维监督位，如图 11-7 所示。图中 \(a_{0}^{1}\) \(a_{0}^{2}\) \(\cdots\) \(a_{0}^{m}\) 为 m 行奇偶监督码中的 m 个监督位。 \(c_{n-1}\) \(c_{n-2}\) \(\cdots\) \(c_{0}\) 为按列进行第二次编码所增加的监督位，它们构成了一监督位行。

\[ \begin{array}{c c c c c} a _ {n - 1} ^ {1} & a _ {n - 2} ^ {1} & \dots & a _ {1} ^ {1} & a _ {0} ^ {1} \\ a _ {n - 1} ^ {2} & a _ {n - 2} ^ {2} & \dots & a _ {1} ^ {2} & a _ {0} ^ {2} \\ \vdots & \vdots & \dots & \vdots & \vdots \\ a _ {n - 1} ^ {m} & a _ {n - 2} ^ {m} & \dots & a _ {1} ^ {m} & a _ {0} ^ {m} \\ c _ {n - 1} & c _ {n - 2} & \dots & c _ {1} & c _ {0} \end{array} \]

图 11-7 二维码奇偶监督码

这种编码有可能检测偶数个错码。因为每行的监督位 \(a_{0}^{1}\) \(a_{0}^{2}\) \(\cdots\) \(a_{0}^{m}\) 虽然不能用于检测本行中的偶数个错码，但按列的方向有可能由 \(c_{n-1}\) \(c_{n-2}\) \(\cdots\) \(c_{0}\) 等监督位检测出来。有一些偶数错码不可能检测出来。例如，构成矩形的 4 个错码，譬如图 11-7 中 \(a_{n-2}^{2}\) ， \(a_{1}^{2}\) ， \(a_{n-2}^{m}\) ， \(a_{1}^{m}\) 错了，就检测不出。

这种二维奇偶监督码适于检测突发错码。因为突发错码常常成串出现，随后有较长一段无错区间，所以在某一行中出现多个奇数或偶数错码的机会较多，而这种方阵码正适于检测这类错码。前述的一维奇偶监督码一般只适于检测随机错码。

由于方阵码只对构成矩形四角的错码无法检测，故其检错能力较强。一些试验测量表明，这种码可使误码率降至原误码率的 1/100\~1/10 000。

二维奇偶监督码不仅可用来检错，还可以用来纠正一些错码。例如，当码组中仅在一行中有奇数个错码时，能够确定错码位置，从而纠正之。

11.4.3 恒比码

在恒比码中，每个码组均含有相同数目的 “1”(和 “0”)。由于 “1” 的数目与 “0” 的数目之比保持恒定，故得此名。这种码在检测时，只要计算接收码组中 “1” 的数目是否对，就知道有无错码。

恒比码的主要优点是简单，适于用来传输电传机或其他键盘设备产生的字母和符号。对于信源来的二进制随机数字序列，这种码就不适合使用了。

第 11 章 差错控制编码

11.4.4 正反码

正反码是一种简单的能够纠正错码的编码，其中的监督位数目与信息位数目相同，监督码元与信息码元相同或者相反则由信息码中 “1” 的个数而定。例如，若码长 \(n = 10\) ，其中信息位 \(k = 5\) ，监督位 \(r = 5\) ，其编码规则为：①当信息位中有奇数个 “1” 时，监督位是信息位的简单重复；②当信息位有偶数个 “1” 时，监督位是信息位的反码。例如，若信息位为 11001，则码组为 1100111001；若信息位为 10001，则码组为 1000101110。

接收端解码方法：先将接收码组中信息位和监督位按 “模 2” 相加，得到一个 5 位的合成码组。然后，由此合成码组产生一个校验码组。若接收码组的信息位中有奇数个 “1”, 则合成码组就是校验码组；若接收码组的信息位中有偶数个 “1”, 则取合成码组的反码作为校验码组。最后，观察校验码组中 “1” 的个数，按表 11-2 进行判决及纠正可能发现的错码。

表11-2校验码组和错码的关系
序号校验码组的组成错码情况
1全为“0”无错码
2有4个“1”和1个“0”信息码中有1位错码,其位置对应校验码组中“0”的位置
3有4个“0”和1个“1”监督码中有1位错码,其位置对应校验码组中“1”的位置
4其他组成错码多于1个

例如，发送码组为 1100111001，接收码组中无错码，则合成码组应为 \(11001\oplus11001=00000\) 。由于接收码组信息位中有奇数个 “1”，所以校验码组就是 00000。按表 11-2 判决，结论是无错码。若传输中产生了差错，使接收码组变成 1000111001，则合成码组为 \(10001\oplus11001=01000\) 。由于接收码组中信息位有偶数个 “1”，所以校验码组应取合成码组的反码，即 10111。由于其中有 4 个 “1” 和一个 “0”，按表 11-2 判断信息位中左边第 2 位为错码。若接收码组错成 1100101001，则合成码组变成 \(11001\oplus01001=10000\) 。由于接收码组中信息位有奇数个 “1”，故校验码组就是 10000，按表 11-2 判断，监督位中第一位为错码。最后，若接收码组为 1001111001，则合成码组为 \(10011\oplus11001=01010\) ，校验码组与其相同，按表 11-2 判断，这时错码多于一个。

上述长度为 10 的正反码具有纠正一位错码的能力，并能检测全部二位以下的错码和大部分二位以上的错码。

11.5 线性分组码

从 11.4 节介绍的一些简单编码可以看出，每种编码所依据的原理各不相同，而且是大不相同，其中奇偶监督码的编码原理是利用代数关系式产生监督位。我们把这类建立在代数学基础上的编码称为代数码。在代数码中，常见的是线性码。在线性码中信息位和监督位是由一些线性代数方程联系着的，或者说，线性码是按照一组线性方程构成的。本节将以汉明 (Hamming) 码为例引入线性分组码的一般原理。

上述正反码中，为了能够纠正 1 位错码，使用的监督位数和信息位一样多，即编码效率只有 50%。那么，为了纠正 1 位错码，在分组码中最少要增加多少监督位才行呢？编码效率能否提高呢？从这种思想出发进行研究，便导致汉明码的诞生。汉明码是一种能够纠正 1 位错码且编码效率较高的线性分组码。下面就将介绍汉明码的构造原理。

e51625699a652b35babfe11b7b0bd72a15e61d86a3df9de84fa6f3a208fb4da9.jpg

11.5 线性分组码

我们先来回顾一下按照式 \((11.4-1)\) 条件构成的偶数监督码。由于使用了一位监督位 \(a_{0}\) ，它和信息位 \(a_{n-1}\cdots a_{1}\) 一起构成一个代数式，如式 \((11.4-1)\) 所示。在接收端解码时，实际上就是在计算

\[ S = a _ {n - 1} \oplus a _ {n - 2} \oplus \dots \oplus a _ {0} \tag {11.5-1} \]

若 S=0，就认为无错码；若 S=1，就认为有错码。现将式 (11.5-1) 称为监督关系式，S 称为校正子（syndrome，又称校验子、伴随式）。由于校正子 S 只有两种取值，故它只能代表有错和无错这两种信息，而不能指出错码的位置。不难推想，若监督位增加一位，即变成两位，则能增加一个类似于式 (11.5-1) 的监督关系式。由于两个校正子的可能值有 4 种组合：00,01,10,11，故能表示 4 种不同的信息。若用其中一种组合表示无错，则其余 3 种组合就有可能用来指示一个错码的 3 种不同位置。同理，r 个监督关系式能指示一位错码的 \((2'-1)\) 个可能位置。

一般来说，若码长为 n, 信息位数为 k, 则监督位数 r=n-k。如果希望用 r 个监督位构造出 r 个监督关系式来指示一位错码的 n 种可能位置，则要求

\[ 2 ^ {r} - 1 \geqslant n \quad \text {或} \quad 2 ^ {r} \geqslant k + r + 1 \tag {11.5-2} \]

下面通过一个例子来说明如何具体构造这些监督关系式。

设分组码 \((n,k)\) 中 k=4，为了纠正一位错码，由式 (11.5-2) 可知，要求监督位数 \(r\geqslant3\) 。若取 r=3，则 \(n=k+r=7\) 。我们用 \(a_{6}a_{5}\cdots a_{0}\) 表示这 7 个码元，用 \(S_{1},S_{2}\) 和 \(S_{3}\) 表示 3 个监督关系式中的校正子，则 \(S_{1},S_{2}\) 和 \(S_{3}\) 的值与错码位置的对应关系可以规定如表 11-3 所列。自然，我们也可以规定成另一种对应关系，这不影响讨论的一般性。由表中规定可见，仅当一位错码的位置在 \(a_{2},a_{4},a_{5}\) 或 \(a_{6}\) 时，校正子 \(S_{1}\) 为 1；否则 \(S_{1}\) 为零。这就意味着 \(a_{2},a_{4},a_{5}\) 和 \(a_{6}4\) 个码元构成偶数监督关系：

\[ S _ {1} = a _ {6} \oplus a _ {5} \oplus a _ {4} \oplus a _ {2} \tag {11.5-3} \]

同理， \(a_{1}\) 、 \(a_{3}\) 、 \(a_{5}\) 和 \(a_{6}\) 构成偶数监督关系：

\[ S _ {2} = a _ {6} \oplus a _ {5} \oplus a _ {3} \oplus a _ {1} \tag {11.5-4} \]

以及 \(a_{0}\) 、 \(a_{3}\) 、 \(a_{4}\) 和 \(a_{6}\) 构成偶数监督关系：

$S_1S_2S_3$ 错码位置 $S_1S_2S_3$ 错码位置
001 $a_0$ 101 $a_4$
010 $a_1$ 110 $a_5$
100 $a_2$ 111 $a_6$
011 $a_3$ 000无错码
\[ S _ {3} = a _ {6} \oplus a _ {4} \oplus a _ {3} \oplus a _ {0} \tag {11.5-5} \]

在发送端编码时，信息位 \(a_6, a_5, a_4\) 和 \(a_3\) 的值决定于输入信号，因此它们是随机的。监督位 \(a_2, a_1\) 和 \(a_0\) 应根据信息位的取值按监督关系来确定，即监督位应使式 (11.5-3)\~ 式 (11.5-5) 中 \(S_1, S_2\) 和 \(S_3\) 的值均为 0（表示编成的码组中应无错码）：

\[ \left\{ \begin{array}{l} a _ {6} \oplus a _ {5} \oplus a _ {4} \oplus a _ {2} = 0 \\ a _ {6} \oplus a _ {5} \oplus a _ {3} \oplus a _ {1} = 0 \\ a _ {6} \oplus a _ {4} \oplus a _ {3} \oplus a _ {0} = 0 \end{array} \right. \tag {11.5-6} \]

第 11 章 差错控制编码

式 \((11.5-6)\) 经过移项运算，解出监督位为

\[ \left\{ \begin{array}{l} a _ {2} = a _ {6} \oplus a _ {5} \oplus a _ {4} \\ a _ {1} = a _ {6} \oplus a _ {5} \oplus a _ {3} \\ a _ {0} = a _ {6} \oplus a _ {4} \oplus a _ {3} \end{array} \right. \tag {11.5-7} \]

给定信息位后，可以直接按式 (11.5-7) 算出监督位，其结果如表 11-4 所列。

接收端收到每个码组后，先按照式 (11.5-3)\~ 式 (11.5-5) 计算出 \(S_{1}\) 、 \(S_{2}\) 和 \(S_{3}\) ，再按照表 11-3 判断错码情况。例如，若接收码组为 0000011，按式 (11.5-3)\~ 式 (11.5-5) 计算可得： \(S_{1}=0,S_{2}=1,S_{3}=1\) 。由于 \(S_{1}S_{2}S_{3}=011\) ，故根据表 11-3 可知，在 \(a_{3}\) 位有一个错码。

按照上述方法构造的码称为汉明码。表 11-4 中所列的 (7,4) 汉明码的最小码距 \(d_{0}=3\) 。因此，根据式 (11.2-2) 和式 (11.2-3) 可知，这种码能够纠正一个错码或检测两个错码。由于码率 \(k/n=(n-r)/n=1-r/n\) ，故当 n 很大和 r 很小时，码率接近 1。可见，汉明码是一种高效码。

现在我们介绍线性分组码的一般原理。上面已经提到，线性码是指信息位和监督位满足一组线性代数方程式的码。式 (11.5-6) 就是这样一组线性方程式的例子。现在将它改写成

信息位 $a_6a_5a_4a_3$ 监督位 $a_2a_1a_0$ 信息位 $a_6a_5a_4a_3$ 监督位 $a_2a_1a_0$
00000001000111
00010111001100
00101011010010
00111101011001
01001101100001
01011011101010
01100111110100
01110001111111
\[ \left\{ \begin{array}{l} 1 \cdot a _ {6} + 1 \cdot a _ {5} + 1 \cdot a _ {4} + 0 \cdot a _ {3} + 1 \cdot a _ {2} + 0 \cdot a _ {1} + 0 \cdot a _ {0} = 0 \\ 1 \cdot a _ {6} + 1 \cdot a _ {5} + 0 \cdot a _ {4} + 1 \cdot a _ {3} + 0 \cdot a _ {2} + 1 \cdot a _ {1} + 0 \cdot a _ {0} = 0 \\ 1 \cdot a _ {6} + 0 \cdot a _ {5} + 1 \cdot a _ {4} + 1 \cdot a _ {3} + 0 \cdot a _ {2} + 0 \cdot a _ {1} + 1 \cdot a _ {0} = 0 \end{array} \right. \tag {11.5-8} \]

式 (11.5-8) 中已经将 “⊕” 简写成 “+”。在本章后面，除非另加说明，这类式中的 “+” 都指模 2 加法。式 (11.5-8) 可以表示成如下矩阵形式：

\[ \left[ \begin{array}{l l l l} 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 \end{array} \right] = \left[ \begin{array}{l} a _ {6} ^ {\frac {3}{2}} \\ a _ {5} \\ a _ {4} \\ a _ {3} \\ a _ {2} \\ a _ {1} \\ a _ {0} \end{array} \right] \quad (\text {模2}) \tag {11.5-9} \]

式 \((11.5-9)\) 还可以简记为

\[ \pmb {H} \cdot \pmb {A} ^ {\mathrm{T}} = \pmb {0} ^ {\mathrm{T}} \quad \text {或} \quad \pmb {A} \cdot \pmb {H} ^ {\mathrm{T}} = \pmb {0} \tag {11.5-10} \]

其中， \(H=\begin{bmatrix}1110100\\1101010\\1011001\end{bmatrix};A=\left[a_{6}a_{5}a_{4}a_{3}a_{2}a_{1}a_{0}\right];0=\left[000\right]\) 。

687f5f444860e72c4b3467c86d1e216c5b1ae6b63d67624a55d0b7c13a29e04a.jpg

11.5

线性分组码

上角 “T” 表示将矩阵转置。例如， \(H^{T}\) 是 H 的转置，即 \(H^{T}\) 的第一行为 H 的第一列， \(H^{T}\) 的第二行为 H 的第二列，等等。

我们将 H 称为监督矩阵 (parity-check matrix)。只要监督矩阵 H 给定，编码时监督位和信息位的关系就完全确定了。由式 (11.5-9) 和式 (11.5-10) 都可以看出，H 的行数就是监督关系式的数目，它等于监督位的数目 r。H 的每行中 “1” 的位置表示相应码元之间存在的监督关系。例如，H 的第一行 1110100 表示监督位 \(a_{2}\) 是由 \(a_{6}a_{5}a_{4}\) 之和决定的。式 (11.5-9) 中的 H 矩阵可以分成两部分，即

\[ \boldsymbol {H} = \left[ \begin{array}{l l} 1 1 1 0 & 1 0 0 \\ 1 1 0 1 & 0 1 0 \\ 1 0 1 1 & 0 0 1 \end{array} \right] = [ \boldsymbol {P I _ {r}} ] \tag {11.5-11} \]

式中：P 为 \(r \times k\) 阶矩阵； \(I_{r}\) 为 \(r \times r\) 阶单位方阵。

我们将具有 \([PI_{r}]\) 形式的 H 矩阵称为典型阵。

由代数理论可知，H 矩阵的各行应该是线性无关（linearly independent）的，否则将得不到 r 个线性无关的监督关系式，从而也得不到 r 个独立的监督位。若一矩阵能写成典型阵形式 \([P I_{r}]\) ，则其各行一定是线性无关的。因为容易验证 \([I_{r}]\) 的各行是线性无关的，故 \([P I_{r}]\) 的各行也是线性无关的。

类似于式 (11.5-6) 改变成式 (11.5-9) 那样，式 (11.5-7) 也可以改写成

\[ \left[ \begin{array}{l} a _ {2} \\ a _ {1} \\ a _ {0} \end{array} \right] = \left[ \begin{array}{l} 1 1 1 0 \\ 1 1 0 1 \\ 1 0 1 1 \end{array} \right] \left[ \begin{array}{l} a _ {6} \\ a _ {5} \\ a _ {4} \\ a _ {3} \end{array} \right] \tag {11.5-12} \]

或者

\[ \left[ a _ {2} a _ {1} a _ {0} \right] = \left[ a _ {6} a _ {5} a _ {4} a _ {3} \right] \left[ \begin{array}{l} 1 1 1 \\ 1 1 0 \\ 1 0 1 \\ 0 1 1 \end{array} \right] = \left[ a _ {6} a _ {5} a _ {4} a _ {3} \right] Q \tag {11.5-13} \]

其中， \(Q\) 为一个 \(k\times r\) 阶矩阵，它为 \(\pmb{P}\) 的转置 (transpose)，即

\[ Q = P ^ {\mathrm{T}} \tag {11.5-14} \]

式 \((11.5-13)\) 表示，在信息位给定后，用信息位的行矩阵乘矩阵 Q 就产生出监督位。

我们将 Q 的左边加上一个 \(k \times k\) 阶单位方阵，就构成一个矩阵 G

第 11 章 差错控制编码

\[ \boldsymbol {G} = \left[ \boldsymbol {I} _ {k} \boldsymbol {Q} \right] = \left[ \begin{array}{l l} 1 0 0 0 & 1 1 1 \\ 0 1 0 0 & 1 1 0 \\ 0 0 1 0 & 1 0 1 \\ 0 0 0 1 & 0 1 1 \end{array} \right] \tag {11.5-15} \]

G 称为生成矩阵 (generator matrix)，因为由它可以产生整个码组，即有

\[ \left[ a _ {6} a _ {5} a _ {4} a _ {3} a _ {2} a _ {1} a _ {0} \right] = \left[ a _ {6} a _ {5} a _ {4} a _ {3} \right] \cdot G \tag {11.5-16} \]

或者

\[ \boldsymbol {A} = \left[ a _ {6} a _ {5} a _ {4} a _ {3} \right] \cdot \boldsymbol {G} \tag {11.5-17} \]

因此，如果找到了码的生成矩阵 G, 则编码的方法就完全确定了。具有 \([I_{k}Q]\) 形式的生成矩阵称为典型生成矩阵。由典型生成矩阵得出的码组 A 中，信息位的位置不变，监督位附加于其后。这种形式的码称为系统码 (systematic code)。

比较式 (11.5-11) 和式 (11.5-15) 可见，典型监督矩阵 H 和典型生成矩阵 G 之间由式 (11.5-14) 相联系。

与 H 矩阵相似，我们也要求 G 矩阵的各行是线性无关的。因为由式 (11.5-17) 可以看出，任一码组 A 都是 G 的各行的线性组合。G 共有 k 行，若它们线性无关，则可以组合出 \(2^{k}\) 种不同的码组 A, 它恰是有 k 位信息位的全部码组。若 G 的各行有线性相关的，则不可能由 G 生成 \(2^{k}\) 种不同的码组了。实际上，G 的各行本身就是一个码组。因此，如果已有 k 个线性无关的码组，则可以用其作为生成矩阵 G, 并由它生成其余码组。

一般说来，式 (11.5-17) 中 A 为一个 n 列的行矩阵。此矩阵的 n 个元素就是码组中的 n 个码元，所以发送的码组就是 A。此码组在传输中可能由于干扰引入差错，故接收码组一般说来与 A 不一定相同。若设接收码组为一 n 列的行矩阵 B, 即

\[ \boldsymbol {B} = \left[ b _ {n - 1} b _ {n - 2} \dots b _ {1} b _ {0} \right] \tag {11.5-18} \]

则发送码组和接收码组之差为

\[ \pmb {B} - \pmb {A} = \pmb {E} \quad (\text {模} 2) \tag {11.5-19} \]

它就是传输中产生的错码行矩阵，即

\[ \boldsymbol {E} = \left[ e _ {n - 1} e _ {n - 2} \dots e _ {1} e _ {0} \right] \tag {11.5-20} \]

其中 \(e_{i}=\left\{\begin{aligned}&0&b_{i}=a_{i}\\ &1&b_{i}\neq a_{i}\end{aligned}\right.\) \(i=0,1,\cdots,n-1\)

因此，若 \(e_{i}=0\) ，表示该接收码元无错；若 \(e_{i}=1\) ，则表示该接收码元有错。式 (11.5-19) 可以改写成

\[ \boldsymbol {B} = \boldsymbol {A} + \boldsymbol {E} \tag {11.5-21} \]

例如，若发送码组 \(A = [1000111]\) ，错码矩阵 \(E = [0000100]\) ，则接收码组 \(B = [1000011]\) 。

34a843439d9474f4a7994d82287562ac83ace7e270f357c294668cb243b066ae.jpg

11.5 线性分组码

错码矩阵有时也称为错误图样 (error pattern)。

接收端解码时，可将接收码组 B 代入式 (11.5-10) 中计算。若接收码组中无错码，即 E=0, 则 \(B=A+E=A\) 。把它代入式 (11.5-10) 后，该式仍成立，即有

\[ \boldsymbol {B} \cdot \boldsymbol {H} ^ {\mathrm{T}} = \mathbf {0} \tag {11.5-22} \]

当接收码组有错时， \(E \neq 0\) ，将 B 代入式 (11.5-10) 后，该式不一定成立。在错码较多，已超过这种编码的检错能力时，B 变为另一许用码组，则式 (11.5-22) 仍能成立。这样的错码是不可检测的。在未超过检错能力时，式 (11.5-22) 不成立，即其右端不等于 0。假设这时式 (11.5-22) 的右端为 S，即

\[ \boldsymbol {B} \cdot \boldsymbol {H} ^ {\mathrm{T}} = \boldsymbol {S} \tag {11.5-23} \]

将 \(B = A + E\) 代入式 (11.5 - 23)，可得

\[ \boldsymbol {S} = (\boldsymbol {A} + \boldsymbol {E}) \boldsymbol {H} ^ {\mathrm{T}} = \boldsymbol {A} \cdot \boldsymbol {H} ^ {\mathrm{T}} + \boldsymbol {E} \cdot \boldsymbol {H} ^ {\mathrm{T}} \]

由式 (11.5-10) 可知，\(A\cdot H^{T}=0\) , 所以

\[ \boldsymbol {S} = \boldsymbol {E} \cdot \boldsymbol {H} ^ {\mathrm{T}} \tag {11.5-24} \]

式中：S 称为校正子。它与式 (11.5-1) 中的 S 相似，有可能利用它来指示错码的位置。

这一点可以直接从式 (11.5-24) 中看出，式中 S 只与 E 有关，而与 A 无关，这就意味着 S 和错码 E 之间有确定的线性变换关系。若 S 和 E 之间一一对应，则 S 将能代表错码的位置。

线性码有一个重要性质，就是它具有封闭性。所谓封闭性，是指一种线性码中的任意两个码组之和仍为这种码中的一个码组。这就是说，若 \(A_{1}\) 和 \(A_{2}\) 是一种线性码中的两个许用码组，则 \((A_{1}+A_{2})\) 仍为其中的一个码组。这一性质的证明很简单。若 \(A_{1}\) 和 \(A_{2}\) 是两个码组，则按式 (11.5-10), 有

\[ \boldsymbol {A} _ {1} \cdot \boldsymbol {H} ^ {\mathrm{T}} = \boldsymbol {0}, \boldsymbol {A} _ {2} \cdot \boldsymbol {H} ^ {\mathrm{T}} = \boldsymbol {0} \]

将以上两式相加，得

\[ \boldsymbol {A} _ {1} \cdot \boldsymbol {H} ^ {\mathrm{T}} + \boldsymbol {A} _ {2} \cdot \boldsymbol {H} ^ {\mathrm{T}} = (\boldsymbol {A} _ {1} + \boldsymbol {A} _ {2}) \boldsymbol {H} ^ {\mathrm{T}} = \mathbf {0} \tag {11.5-25} \]

所以 \((A_{1}+A_{2})\) 也是一个码组。由于线性码具有封闭性，所以两个码组 \((A_{1}\) 和 \(A_{2})\) 之间的距离（即对应位不同的数目）必定是另一个码组 \((A_{1}+A_{2})\) 的重量（即 “1” 的数目）。因此，码的最小距离就是码的最小重量（除全 “0” 码组外）。

11.6 循环码

11.6.1 循环码原理

在线性分组码中，有一种重要的码称为循环码 (cyclic code)。它是在严密的代数学理论基础上建立起来的。这种码的编码和解码设备都不太复杂，而且检 (纠) 错的能力较强。循环码除了具有线性码的一般性质外，还具有循环性。循环性是指任一码组循环一位 (即将最右端的一个码元移至左端，或反之) 以后，仍为该码中的一个码组。在表 11-5 中给出一种 (7,3) 循环码的全部码组。由此表可以直观看出这种码的循环性。例如，表中的第 2 码组向右移一位即得到第 5 码组；第 6 码组向右移一位即得到第 7 码组。一般说来，若 \((a_{n-1}a_{n-2}\cdots a_{0})\) 是循环码的一个码组，则循环移位后的码组

第 11 章 差错控制编码

\[ \begin{array}{l} \left(a _ {n - 2} a _ {n - 3} \dots a _ {0} a _ {n - 1}\right) \\ \left(a _ {n - 3} a _ {n - 4} \dots a _ {n - 1} a _ {n - 2}\right) \\ \left(a _ {0} a _ {n - 1} \dots a _ {2} a _ {1}\right) \\ \end{array} \]

:

也是该编码中的码组。

表11-5一种(7,3)循环码的全部码组
码组编号信息位监督位码组编号信息位监督位
$a_6a_5a_4$ $a_3a_2a_1a_0$ $a_6a_5a_4$ $a_3a_2a_1a_0$
1000000051001011
2001011161011100
3010111071100101
4011100181110010

在代数编码理论中，为了便于计算，把这样的码组中各码元当作是一个多项式 (polynomial) 的系数，即把一个长度为 n 的码组表示成

\[ A (x) = a _ {n - 1} x ^ {n - 1} + a _ {n - 2} x ^ {n - 2} + \dots + a _ {1} x + a _ {0} \tag {11.6-1} \]

例如，表 11-5 中的任意一个码组可以表示为

\[ A (x) = a _ {6} x ^ {6} + a _ {5} x ^ {5} + a _ {4} x ^ {4} + a _ {3} x ^ {3} + a _ {2} x ^ {2} + a _ {1} x + a _ {0} \tag {11.6-2} \]

其中第 7 个码组可以表示为

\[ A (x) = 1 \cdot x ^ {6} + 1 \cdot x ^ {5} + 0 \cdot x ^ {4} + 0 \cdot x ^ {3} + 1 \cdot x ^ {2} + 0 \cdot x + 1 = x ^ {6} + x ^ {5} + x ^ {2} + 1 \tag {11.6-3} \]

这种多项式中，x 仅是码元位置的标记，例如上式表示第 7 码组中 \(a_{6}\) 、 \(a_{5}\) 、 \(a_{2}\) 和 \(a_{0}\) 为 “1”，其他均为 0。因此我们并不关心 x 的取值。这种多项式也称为码多项式。

下面我们将介绍循环码的运算方法。

1. 码多项式的按模运算

在整数运算中，有模 \(n(\text{modulo}-n)\) 运算。例如，在模 2 运算中，有

\[ \begin{array}{l} 1 + 1 = 2 \equiv 0 \quad (\text { 模 } 2) \\ 1 + 2 = 3 \equiv 1 \quad (\text { 模 } 2) \\ 2 \times 3 = 6 \equiv 0 (\text { 模 } 2) \\ \end{array} \]

6f59184fabd829a583517991fadae31a3a2670422a7b55bdd830f9c6562aa6c2.jpg

11.6 循环码

一般说来，若一个整数 (integer) m 可以表示为

\[ \frac {m}{n} = Q + \frac {p}{n} p < n \tag {11.6-4} \]

式中： \(Q\) 为整数，

则在模 n 运算下，有

\[ m \equiv p \quad (\text {模} n) \tag {11.6-5} \]

这就是说，在模 n 运算下，一个整数 m 等于它被 n 除得的余数 (remainder)。

在码多项式运算中也有类似的按模运算。若一任意多项式 \(F(x)\) 被一 n 次多项式 \(N(x)\) 除，得到商式 (quotient) \(Q(x)\) 和一个次数小于 n 的余式 (residue) \(R(x)\) ，即

\[ F (x) = N (x) Q (x) + R (x) \tag {11.6-6} \]

则

\[ F (x) \equiv R (x) \quad (\text {模} N (x)) \tag {11.6-7} \]

这时，码多项式系数仍按模 2 运算，即系数只取 0 和 1。例如，\(x^{3}\) 被 \((x^{3}+1)\) 除，得到余项 1。所以有

\[ x ^ {3} \equiv 1 \quad (\text {模} (x ^ {3} + 1)) \tag {11.6-8} \]

同理

\[ x ^ {4} + x ^ {2} + 1 \equiv x ^ {2} + x + 1 \quad (\text {模} (x ^ {3} + 1)) \tag {11.6-9} \]

因为

\[ x ^ {3} + 1 \quad \sqrt {\frac {x ^ {4} + x ^ {2} + 1}{\frac {x ^ {4} + x}{x ^ {2} + x + 1}}} \]

应当注意，由于在模 2 运算中，用加法代替了减法，故余项不是 \(x^{2}-x+1\) , 而是 \(x^{2}+x+1\) 。

在循环码中，若 \(A(x)\) 是一个长为 n 的许用码组，则 \(x^{i} \cdot A(x)\) 在按模 \(x^{n} + 1\) 运算下，也是该编码中的一个许用码组，即若

\[ x ^ {i} \cdot A (x) \equiv A ^ {\prime} (x) \quad (\text {模} \left(x ^ {n} + 1\right)) \tag {11.6-10} \]

则 \(A'(x)\) 也是该编码中的一个许用码组。其证明很简单，因为若

\[ A (x) = a _ {n - 1} x ^ {n - 1} + a _ {n - 2} x ^ {n - 2} + \dots + a _ {1} x + a _ {0} \tag {11.6-11} \]

则

\[ \begin{array}{l} x ^ {i} \cdot A (x) = a _ {n - 1} x ^ {n - 1 + i} + a _ {n - 2} x ^ {n - 2 + i} + \dots + a _ {n - 1 - i} x ^ {n - 1} + \dots + a _ {1} x ^ {1 + i} + a _ {0} x ^ {i} \\ \equiv a _ {n - 1 - i} x ^ {n - 1} + a _ {n - 2 - i} x ^ {n - 2} + \dots + a _ {0} x ^ {i} + a _ {n - 1} x ^ {i - 1} + \dots + a _ {n - i} \\ \end{array} \]

第 11 章 差错控制编码

\[ (\text { 模 } (x ^ {n} + 1)) \tag {11.6-12} \]

所以，这时有

\[ A ^ {\prime} (x) = a _ {n - 1 - i} x ^ {n - 1} + a _ {n - 2 - i} x ^ {n - 2} + \dots + a _ {0} x ^ {i} + a _ {n - 1} x ^ {i - 1} + \dots + a _ {n - i} \tag {11.6-13} \]

式 (11.6-13) 中 \(A'(x)\) 正是式 (11.6-11) 中 \(T(x)\) 代表的码组向左循环移位 i 次的结果。因为原已假定 \(A(x)\) 是循环码的一个码组，所以 \(A'(x)\) 也必为该码中一个码组。例如，式 (9.6-3) 中的循环码组为

\[ A (x) = x ^ {6} + x ^ {5} + x ^ {2} + 1 \]

其码长 \(n = 7\) 。现给定 \(i = 3\) ，则

\[ \begin{array}{l} x ^ {3} \cdot A (x) = x ^ {3} \left(x ^ {6} + x ^ {5} + x ^ {2} + 1\right) = x ^ {9} + x ^ {8} + x ^ {5} + x ^ {3} \tag {11.6-14} \\ = x ^ {5} + x ^ {3} + x ^ {2} + x \quad (\text {模} (x ^ {7} + 1)) \\ \end{array} \]

其对应的码组为 0101110，它正是表 11-5 中第 3 码组。

由上述分析可见，一个长为 n 的循环码必定为按模 \((x^{n}+1)\) 运算的一个余式。

2. 循环码的生成矩阵 G

由式 (11.5-17) 可知，有了生成矩阵 G, 就可以由 k 个信息位得出整个码组，而且生成矩阵 G 的每一行都是一个码组。例如，在式 (11.5-17) 中，若 \(a_{6}a_{5}a_{4}a_{3}=1000\) , 则码组 A 就等于 G 的第一行；若 \(a_{6}a_{5}a_{4}a_{3}=0100\) , 则码组 A 就等于 G 的第二行；等等。由于 G 是 k 行 n 列的矩阵，因此若能找到 k 个已知码组，就能构成矩阵 G。如前所述，这 k 个已知码组必须是线性不相关的，否则给定的信息位与编出的码组就不是一一对应的。

在循环码中，一个 \((n,k)\) 码有 \(2^{k}\) 个不同的码组。若用 \(g(x)\) 表示其中前 \((k-1)\) 位皆为 “0” 的码组，则 \(g(x),xg(x),x^{2}g(x),\cdots,x^{k-1}g(x)\) 都是码组，而且这 k 个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵 G。

在循环码中除全 “0” 码组外，再没有连续 \(k\) 位均为 “0” 的码组，即连 “0” 的长度最多只能有 \((k - 1)\) 位。否则，在经过若干次循环移位后将得到一个 \(k\) 位信息位全为 “0”，但监督位不全为 “0” 的一个码组。这在线性码中显然是不可能的。因此， \(g(x)\) 必须是一个常数项不为 “0” 的 \((n - k)\) 次多项式，而且这个 \(g(x)\) 还是这种 \((n, k)\) 码中次数为 \((n - k)\) 的唯一一个多项式。因为如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码组多项式的次数将小于 \((n - k)\) ，即连续 “0” 的个数多于 \((k - 1)\) 。显然，这是与前面的结论矛盾的，故是不可能的。我们称这唯一的 \((n - k)\) 次多项式 \(g(x)\) 为码的生成多项式。一旦确定了 \(g(x)\) ，则整个 \((n, k)\) 循环码就被确定了。

因此，循环码的生成矩阵 G 可以写成

\[ \boldsymbol {G} (x) = \left[ \begin{array}{c} x ^ {k - 1} g (x) \\ x ^ {k - 2} g (x) \\ \vdots \\ x g (x) \\ g (x) \end{array} \right] \tag {11.6-15} \]

74c26a4b8d5946575e9654310e6b163953706712a030bd62e02594e5f78d0286.jpg

11.6 循环码

例如，在表 11-5 所给出的循环码中， \(n = 7,k = 3,n - k = 4\) 。由此表可见，唯一的一个 \((n - k) = 4\) 次码多项式代表的码组是第二码组 0010111，与它相对应的码多项式（即生成多项式） \(g(x) = x^{4} + x^{2} + x + 1\) 。将此 \(g(x)\) 代入式 (11.6-15)，得

\[ \mathbf {G} (x) = \left[ \begin{array}{l} x ^ {2} g (x) \\ x g (x) \\ g (x) \end{array} \right] \tag {11.6-16} \]

或

\[ \boldsymbol {G} (x) = \left[ \begin{array}{l} 1 0 1 1 1 0 0 \\ 0 1 0 1 1 1 0 \\ 0 0 1 0 1 1 1 \end{array} \right] \tag {11.6-17} \]

由于式 (11.6-17) 不符合式 (11.5-15) 所示的 \(G=[I_{k}Q]\) 形式，所以它不是典型阵。不过，将它作线性变换，不难化成典型阵。

类似式 \((11.5-17)\) ，我们可以写出此循环码组，即

\[ \begin{array}{l} A (x) = [ a _ {6} a _ {5} a _ {4} ] \mathbf {G} (x) = [ a _ {6} a _ {5} a _ {4} ] \left[ \begin{array}{l} x ^ {2} g (x) \\ x g (x) \\ g (x) \end{array} \right] \\ = a _ {6} x ^ {2} g (x) + a _ {5} x g (x) + a _ {4} g (x) \\ = \left(a _ {6} x ^ {2} + a _ {5} x + a _ {4}\right) g (x) \tag {11.6-18} \\ \end{array} \]

式 (11.6-18) 表明，所有码多项式 \(A(x)\) 都可被 \(g(x)\) 整除，而且任意一个次数不大于 \((k-1)\) 的多项式乘 \(g(x)\) 都是码多项式。需要说明一点，两个矩阵相乘的结果应该仍是一个矩阵。式 (11.6-18) 中两个矩阵相乘的乘积是只有一个元素的一阶矩阵，这个元素就是 \(A(x)\) 。为了简洁，式中直接将乘积写为此元素。

3. 如何寻找任一 \((n, k)\) 循环码的生成多项式

由式 (11.6-18) 可知，任一循环码多项式 \(A(x)\) 都是 \(g(x)\) 的倍式，故它可以写成

\[ A (x) = h (x) \cdot g (x) \tag {11.6-19} \]

而生成多项式 \(g(x)\) 本身也是一个码组，即有

\[ A ^ {\prime} (x) = g (x) \tag {11.6-20} \]

由于码组 \(A'(x)\) 是一个 \((n-k)\) 次多项式，故 \(x^{k}A'(x)\) 是一个 n 次多项式。由式 (11.6-10)

第 11 章 差错控制编码

可知， \(x^{k}A^{\prime}(x)\) 在模 \((x^n +1)\) 运算下也是一个码组，故可以写成

\[ \frac {x ^ {k} A ^ {\prime} (x)}{x ^ {n} + 1} = Q (x) + \frac {A (x)}{x ^ {n} + 1} \tag {11.6-21} \]

式 (11.6-21) 左端分子和分母都是 \(n\) 次多项式，故商式 \(Q(x) = 1\) 。因此，式 (11.6-21) 可以化成

\[ x ^ {k} A ^ {\prime} (x) = \left(x ^ {n} + 1\right) + A (x) \tag {11.6-22} \]

将式 \((11.6-19)\) 和式 \((11.6-20)\) 代入式 \((11.6-22)\) ，经过化简后得到

\[ x ^ {n} + 1 = g (x) \left[ x ^ {k} + h (x) \right] \tag {11.6-23} \]

式 (11.6-23) 表明，生成多项式 \(g(x)\) 应该是 \((x^{n}+1)\) 的一个因子。这一结论为我们寻找循环码的生成多项式指出了一条道路，即循环码的生成多项式应该是 \((x^{n}+1)\) 的一个 \((n-k)\) 次因式。例如，\((x^{7}+1)\) 可以分解为

\[ x ^ {7} + 1 = (x + 1) \left(x ^ {3} + x ^ {2} + 1\right) \left(x ^ {3} + x + 1\right). \tag {11.6-24} \]

为了求 (7,3) 循环码的生成多项式 \(g(x)\) ，需要从式 (11.6-24) 中找到一个 \((n-k)=4\) 次的因子。不难看出，这样的因子有两个，即

\[ (x + 1) (x ^ {3} + x ^ {2} + 1) = x ^ {4} + x ^ {2} + x + 1 \tag {11.6-25} \]
\[ (x + 1) (x ^ {3} + x + 1) = x ^ {4} + x ^ {3} + x ^ {2} + 1 \tag {11.6-26} \]

式 (11.6-25) 和式 (11.6-26) 都可作为生成多项式。不过，选用的生成多项式不同，产生出的循环码码组也不同。用式 (11.6-25) 作为生成多项式产生的循环码即为表 11-5 中所列。

11.6.2 循环码的编解码方法

1. 循环码的编码方法

在编码时，首先要根据给定的 \((n,k)\) 值选定生成多项式 \(g(x)\) , 即从 \((x^{n}+1)\) 的因子中选一个 \((n-k)\) 次多项式作为 \(g(x)\) 。

由式 (11.6-18) 可知，所有码多项式 \(A(x)\) 都可以被 \(g(x)\) 整除。根据这条原则，就可以对给定的信息位进行编码：设 \(m(x)\) 为信息码多项式，其次数小于 k。用 \(x^{n-k}\) 乘 \(m(x)\) , 得到的 \(x^{n-k}m(x)\) 的次数必定小于 n。用 \(g(x)\) 除 \(x^{n-k}m(x)\) , 得到余式 \(r(x),r(x)\) 的次数必定小于 \(g(x)\) 的次数，即小于 \((n-k)\) 。将此余式 \(r(x)\) 加于信息位之后作为监督位，即将 \(r(x)\) 和 \(x^{n-k}m(x)\) 相加，得到的多项式必定是一个码多项式。因为它必定能被 \(g(x)\) 整除，且商的次数不大于 \((k-1)\) 。

根据上述原理，仍以 \((7,3)\) 码为例，编码步骤可以归纳如下:

（1）用 \(x^{n-k}\) 乘 \(m(x)\) 。这一运算实际上是在信息码后附加上 \((n-k)\) 个 “0”。例如，信息码为 110，它相当于 \(m(x)=x^{2}+x\) 。当 n-k=7-3=4 时， \(x^{n-k}m(x)=x^{4}(x^{2}+x)=x^{6}+x^{5}\) ，它相当于 1100000。

(2) 用 \(g(x)\) 除 \(x^{n-k}m(x)\) ，得到商 \(Q(x)\) 和余式 \(r(x)\) ，即

\[ \frac {x ^ {n - k} m (x)}{g (x)} = Q (x) + \frac {r (x)}{g (x)} \tag {11.6-27} \]

11.6 循环码

例如，若选定 \(g(x)=x^{4}+x^{2}+x+1\) ，则

\[ \frac {x ^ {n - k} m (x)}{g (x)} = \frac {x ^ {6} + x ^ {5}}{x ^ {4} + x ^ {2} + x + 1} = (x ^ {2} + x + 1) + \frac {x ^ {2} + 1}{x ^ {4} + x ^ {2} + x + 1} \tag {11.6-28} \]

式 \((11.6-28)\) 相当于

\[ \frac {1 1 0 0 0 0 0}{1 0 1 1 1} = 1 1 1 + \frac {1 0 1}{1 0 1 1 1} \tag {11.6-29} \]

(3) 编出的码组为

\[ A (x) = x ^ {n - k} m (x) + r (x) \tag {11.6-30} \]

在上例中， \(A(x)=1100000+101=1100101\) ，它就是表 11-5 中的第 7 码组。

上述三步运算在用硬件实现时，可以用除法电路实现。除法电路主要由若干移位寄存器和模 2 加法器组成。上述 (7,3) 循环码编码器的组成示于图 11-8 中。图中有 4 级移位寄存器，它们分别用 \(a, b, c, d\) 表示。此外，还有一个双刀双掷开关 \(S\) 。当信息位输入时，开关 \(S\) 倒向下，输入信息位一方面送入除法器进行运算，另一方面直接输出。在信息位全部进入除法器后，开关倒向上，这时输出端接到移位寄存器，将其中存储的除法运算余项依次取出，同时断开反馈线。此编码器的工作过程示于表 11-6 中。用这种方法编出的码组中，前面是原来的 \(k\) 个（现在是 3 个）信息位，后面是 \((n - k)\) 个（现在是 4 个）监督位。因此它是系统分组码。

f549dddd763a1dece11c2c335ebcdd45971c428129c34065d9d6aa81f37fb998.jpg

表11-6(7,3)循环码编码器工作过程
输入m移位寄存器a b c d反馈e输出f
0000000
111101 $\left.\begin{matrix}1 \\ 1 \\ 0\end{matrix}\right\} f=m$
110011
010101
001010 $\left.\begin{matrix}0 \\ 1 \\ 0 \\ 1\end{matrix}\right\} f=e$
000101
000010
000001

由于微处理器和数字信号处理器的应用日益广泛，目前已多采用这些先进的器件和相应的软件代替硬件逻辑电路来实现上述编码。

第 11 章 差错控制编码

2. 循环码的解码方法

接收端解码的要求有两个：检错和纠错。达到检错目的的解码原理十分简单。由于任意一个码组多项式 \(A(x)\) 都应该能被生成多项式 \(g(x)\) 整除，所以在接收端可以将接收码组 \(B(x)\) 用原生成多项式 \(g(x)\) 去除。当传输中未发生错误时，接收码组与发送码组相同，即 \(B(x)=A(x)\) , 故接收码组 \(B(x)\) 必定能被 \(g(x)\) 整除；若码组在传输中发生错误，则 \(B(x)\neq A(x)\) , \(B(x)\) 被 \(g(x)\) 除时可能除不尽而有余项，即有

\[ B (x) / g (x) = Q (x) + r (x) / g (x) \tag {11.6-31} \]

因此，我们就以余项是否为零来判别接收码组中有无错码。

根据这一原理构成的检错解码器示于图 11-9 中。由图可见，解码器的核心是一个除法电路和缓冲移位寄存器，而且这里的除法电路与发送端编码器中的除法电路相同。若在此除法器中进行 \(B(x)/g(x)\) 运算的结果，余项为零，则认为码组 \(B(x)\) 无错。这时就将暂存于缓冲器中的接收码组送到解码器的输出端。若运算结果余项不等于零，则认为 \(B(x)\) 中有错，但错在何位不知。这时就可以将缓冲器中的接收码组删除，并向发送端发出一个重发指令，要求重发一次该码组。

96e8925613beaa09df411b7801845e49898f7f4f600b94150fbf76e8d6b6748d.jpg

需要指出，有错码的接收码组也有可能被 \(g(x)\) 整除。这时的错码就不能检出了。这种错误称为不可检错误。不可检错误中的误码数必定超过了这种编码的检错能力。

在接收端为纠错而采用的解码方法自然比检错时复杂。容易理解，为了能够纠错，要求每个可纠正的错误图样必须与一个特定余式有一一对应关系。这里，错误图样是指式 (11.5-20) 中错码矩阵 E 的各种具体取值的图样，余式是指接收码组 \(B(x)\) 被生成多项式 \(g(x)\) 除所得的余式。因为只有存在上述一一对应的关系时，才可能从上述余式唯一地决定错误图样，从而纠正错码。因此，原则上纠错可按下述步骤进行:

这种解码方法称为捕错解码法。通常，一种编码可以有不同的几种纠错解码方法。对于循环码来说，除了用捕错解码法外，还有大数逻辑（majority logic）解码等算法。作判决的方法也有不同，有硬判决和软判决等方法。

上述解码运算，都可以用硬件电路实现。由于数字信号处理器的应用日益广泛，目前已多采用软件运算实现上述解码。

11.6 循环码

11.6.3 截短循环码

在设计纠错编码方案时，常常信息位数 k、码长 n 和纠错能力都是预先给定的。但是，并不一定有恰好满足这些条件的循环码存在。这时，可以采用将码长截短的方法，得出满足要求的编码。

设给定一个 \((n,k)\) 循环码，它共有 \(2^{k}\) 种码组，现使其前 \(i(0<i<k)\) 个信息位全为 “0”，于是它变成仅有 \(2^{k-i}\) 种码组。然后从中删去这 i 位全 “0” 的信息位，最终得到一个 \((n-i,k-i)\) 的线性码。将这种码称为截短循环码（truncated cyclic code）。截短循环码与截短前的循环码至少具有相同的纠错能力，并且截短循环码的编解码方法仍和截短前的方法一样。例如，要求构造一个能够纠正 1 位错码的 (13,9) 码。这时可以由 (15,11) 循环码的码组中选出前两信息位均为 “0” 的码组，构成一个新的码组集合。然后在发送时不发送这两位 “0”。于是发送码组成为 (13,9) 截短循环码。因为截短前后监督位数相同，所以截短前后的编码具有相同的纠错能力。原 (15,9) 循环码能够纠正 1 位错码，所以 (13,9) 码也能够纠正 1 位错码。

11.6.4 BCH 码

BCH 码是一种获得广泛应用的能够纠正多个错码的循环码，它是以 3 位发明这种码的人名 (Bose, Chaudhuri, Hocguenghem) 命名的。BCH 码的重要性在于它解决了生成多项式与纠错能力的关系问题，可以在给定纠错能力要求的条件下寻找到码的生成多项式。有了生成多项式，编码的基本问题就随之解决了。

BCH 码可以分为两类，即本原 BCH 码和非本原 BCH 码。它们的主要区别在于，本原 BCH 码的生成多项式 \(g(x)\) 中含有最高次数为 \(m\) 的本原多项式 (primitive polynomial), 且码长为 \(n = 2^{m} - 1 (m \geqslant 3\) , 为正整数); 而非本原 BCH 码的生成多项式中不含这种本原多项式，且码长 \(n\) 是 \((2^{m} - 1)\) 的一个因子，即码长 \(n\) 一定除得尽 \(2^{m} - 1\) 。本原多项式的概念将在下一章介绍。

BCH 码的码长 n 与监督位、纠错个数 t 之间的关系如下：对于正整数 \(m(m \geqslant 3)\) 和正整数 t < m/2，必定存在一个码长为 \(n = 2^{m} - 1\) ，监督位为 \(n - k \leqslant mt\) ，能纠正所有不多于 t 个随机错误的 BCH 码。若码长 \(n = (2^{m} - 1)/i (i > 1\) ，且除得尽 \((2^{m} - 1)\) ，则为非本原 BCH 码。

前面已经介绍过的汉明码是能够纠正单个随机错误的码。可以证明，具有循环性质的汉明码就是能纠正单个随机错误的本原 BCH 码。例如，(7,4) 汉明码就是以 \(g_{1}(x) = x^{3} + x + 1\) 或 \(g_{2}(x) = x^{3} + x^{2} + 1\) 生成的 BCH 码，而用 \(g_{3}(x) = x^{4} + x + 1\) 或 \(g_{4}(x) = x^{4} + x^{3} + 1\) 都能生成 (15,11) 汉明码。

在工程设计中，一般不需要用计算方法去寻找生成多项式 \(g(x)\) 。因为前人早已将寻找到的 \(g(x)\) 列成表，故可以用查表法找到所需的生成多项式。表 11-7 给出了码长 \(n \leqslant 127\) 的二进制本原 BCH 码生成多项式系数， \(n = 255\) 的参数在其他文献中有记载 [2]。表 11-8 则列出了部分二进制非本原 BCH 码生成多项式系数。表中给出的生成多项式系数是用八进制数字列出的。例如， \(g(x) = (13)_8\) 是指 \(g(x) = x^3 + x + 1\) ，因为 \((13)_8 = (1011)_2\) ，后者就是此 3 次方程 \(g(x)\) 的各项系数。

第 11 章 差错控制编码

n=3n=63
ktg(x)ktg(x)
117571103
n=751212471
ktg(x)4531701317
4113394166623567
13773651033500423
n=15306157464165347
ktg(x)24717323260404441
1112318101363026512351725
7272116116331141367235453
5324671013472622305527250155
17777777155231045543503271737
131全部为1
n=31n=127
ktg(x)ktg(x)
261451201211
2123551113241567
163107657106311554743
11554233259943447023271
67313365047925624730022327
11517777777777856130704476322273
78726230002166130115
7196255010713253127753
64101206534025570773100045
5711235265252505705053517721
501354446512523314012421501421
431517721772213651227521220574343
36≥153146074666522075044764574721735
29≥22403114461367670603667530141176155
22≥23123376070404722522435445626637647043
15≥2722057042445604554770523013762217604353
8≥317047264052751030651476224271567733130217
163全部为1

在表 11-8 中的 (23,12) 码称为戈莱 (Golay) 码。它能纠正 3 个随机错码，并且容易解码，实际应用较多。此外，BCH 码的长度都为奇数。在应用中，为了得到偶数长度的码，并增大检错能力，可以在 BCH 码生成多项式中乘上一个因式 \((x + 1)\) ，从而得到扩展 BCH 码 \((n + 1,k)\) 。扩展 BCH 码相当于在原 BCH 码上增加了一个校验位，因此码距比原 BCH 码增加 1。扩展 BCH 码已经不再具有循环性。例如，广泛实用的扩展戈莱码 (24,12)，其最小码距为 8，码率为 \(1 / 2\) ，能够纠正 3 个错码和检测 4 个错码。它比汉明码的纠错能力强很多，付出的代价是解码更复杂，码率也比汉明码低。此外，它不再是循环码了。

25fb6a2f7230ca50216a136057d5be19277232e961ed4dbd0cba8ad7a61a9655.jpg

11.6 循环码

表11-8部分二进制非本原BCH码生成多项式系数
nktg(x)nktg(x)
17927274724543073357
2112216636553210761
231235343654043543Q0067
332225145734641717773537
412146647133

11.6.5 RS 码

RS 码是用其发明人的名字 Reed 和 Solomon 命名的。它是一类具有很强纠错能力的多进制 BCH 码。

若仍用 n 表示 RS 码的码长，则对于 m 进制的 RS 码，其码长需要满足下式:

\[ n = m - 1 = 2 ^ {q} - 1 \tag {11.6-32} \]

式中： \(q \geqslant 2\) ，为整数。

对于能够纠正 t 个错误的 RS 码，其监督码元数目为

\[ r = 2 t \tag {11.6-33} \]

这时的最小码距 \(d_{0}=2t+1\) 。

RS 码的生成多项式为

\[ g (x) = (x + \alpha) (x + \alpha^ {2}) \dots (x + \alpha^ {2 t}) \tag {11.6-34} \]

式中： \(\alpha\) 为伽罗华域 \(GF(2^{q})\) 中的本原元（伽罗华域的概念见附录 I）。

若将每个 m 进制码元表示成相应的 q 位二进制码元，则得到的二进制码的参数为

码长 \(n=q(2^{q}-1)\) （二进制码元）

监督码 r = 2qt （二进制码元）

由于 RS 码能够纠正 t 个 m 进制错码，或者说，能够纠正码组中 t 个不超过 q 位连续的二进制错码，所以 RS 码特别适用于存在突发错误的信道，例如移动通信网等衰落信道中。此外，因为它是多进制纠错编码，所以特别适合用于多进制调制的场合。

11.7 卷积码

卷积码 (convolutional code) 是由伊利亚斯 (P. Elias) 发明的一种非分组码。它与前面几节讨论的分组码不同，是一种非分组码。通常它更适用于前向纠错，因为对于许多实际情况它的性能优于分组码，而且运算较简单。

在分组码中，编码器产生的 n 个码元的一个码组，完全决定于这段时间中 k 比特输入信息。这个码组中的监督位仅监督本码组中 k 个信息位。卷积码则不同。卷积码在编码时虽然也是把 k 比特的信息段编成 n 个比特的码组，但是监督码元不仅和当前的 k 比特信息段有关，而且还同前面 \(m=(N-1)\) 个信息段有关。所以一个码组中的监督码元监督着 N 个信息段。通常将 N 称为编码约束 (constraint) 度，并将 nN 称为编码约束长度。一般说来，对于卷积码，k 和 n 的值是比较小的整数。我们将卷积码记作 \((n,k,N)\) 。码率则仍定义为 k/n。

第 11 章 差错控制编码

11.7.1 卷积码的基本原理

图 11-10 示出卷积码编码器一般原理方框图。编码器由三种主要元件构成，包括 \(Nk\) 级移存器、 \(n\) 个模 2 加法器和一个旋转开关。每个模 2 加法器的输入端数目可以不同，它连接到一些移存器的输出端。模 2 加法器的输出端接到旋转开关上。将时间分成等间隔的时隙，在每个时隙中有 \(k\) 比特从左端进入移存器，并且移存器各级暂存的信息向右移 \(k\) 位。旋转开关每时隙旋转一周，输出 \(n\) 比特 \((n > k)\) 。

2eb0b24331013c0451f2a862320a9158f79c110d57890511c9d942c624c59e73.jpg

下面我们将仅讨论最常用的卷积码，其 \(k = 1\) 。这时，移存器共有 \(N\) 级。每个时隙中，只有 1b 输入信息进入移存器，并且移存器各级暂存的内容向右移 1 位，开关旋转一周输出 \(n\) 比特。所以，码率为 \(1 / n\) 。在图 11-11 中给出一个实例。它是一个 \((n,k,N) = (3,1,3)\) 卷积码的编码器，其码率等于 \(1 / 3\) 。我们将以它为例，作较详细的讨论。

cc4f3387b7acfe5788c4a44f7b92e87a0831249200363bb1936fe214bdb4bbb0.jpg

设输入信息比特序列是 \(\cdots b_{i-2}b_{i-1}b_{i}b_{i+1}\cdots\) ，则当输入 \(b_{i}\) 时，此编码器输出 3b, \(c_{i}d_{i}e_{i}\) ，输入和输出的关系如下：

\[ \left\{ \begin{array}{l} c _ {i} = b _ {i} \\ d _ {i} = b _ {i} \oplus b _ {i - 2} \\ e _ {i} = b _ {i} \oplus b _ {i - 1} \oplus b _ {i - 2} \end{array} \right. \tag {11.7-1} \]

式中： \(b_{i}\) 为当前输入信息位； \(b_{i-1}\) 和 \(b_{i-2}\) 为移存器存储的前两信息位。

在输出中信息位在前，监督位在后，如图 11-12 所示；故这种码是 11.5 节中定义过的系统码。在此图中还用虚线示出了信息位 \(b_{i}\) 的监督位和各信息位之间的约束关系。这里的编码约束长度 nN=9。

11.7 卷积码

5c0a52e15ed3e48db903457ec8cacf42574a201520326005079e3fe1d1486720.jpg

11.7.2 卷积码的代数表述

式 (11.7-1) 表示卷积码也是一种线性码。由 11.5 节中讨论可知，一个线性码完全由一个监督矩阵 H 或生成矩阵 G 所确定。下面就来寻找这两个矩阵。

1. 监督矩阵 \(H\)

现在仍从图 11-11 给出的实例开始分析。假设图 11-11 中在第一个信息位 \(b_{1}\) 进入编码器之前，各级移存器都处于 “0” 状态，则监督位 \(d_{i}, e_{i}\) 和信息位 \(b_{i}\) 之间的关系可以写为

\[ \left\{ \begin{array}{l} d _ {1} = b _ {1} \\ e _ {1} = b _ {1} \\ d _ {2} = b _ {2} \\ e _ {2} = b _ {2} + b _ {1} \\ d _ {3} = b _ {3} + b _ {1} \\ e _ {3} = b _ {3} + b _ {2} + b _ {1} \\ d _ {4} = b _ {4} + b _ {2} \\ e _ {4} = b _ {4} + b _ {3} + b _ {2} \\ \dots \end{array} \right. \tag {11.7-2} \]

式 \((11.7-2)\) 可以改写为

\[ \left\{ \begin{array}{l} b _ {1} + d _ {1} = 0 \\ b _ {1} + e _ {1} = 0 \\ b _ {2} + d _ {2} = 0 \\ b _ {1} + b _ {2} + e _ {2} = 0 \\ b _ {1} + b _ {3} + d _ {3} = 0 \\ b _ {1} + b _ {2} + b _ {3} + e _ {3} = 0 \\ b _ {2} + b _ {4} + d _ {4} = 0 \\ b _ {2} + b _ {3} + b _ {4} + e _ {4} = 0 \\ \dots \end{array} \right. \tag {11.7-3} \]

式 \((11.7-2)\) 和式 \((11.7-3)\) 及后面的式子中，为简便计，用 “+” 代替 “⊕”。

第 11 章 差错控制编码

将式 \((11.7-3)\) 用矩阵表示时，可以写成

\[ \left[ \begin{array}{l} 1 1 \\ 1 0 1 \\ 0 0 0 1 1 \\ 1 0 0 1 0 1 \\ 1 0 0 0 0 0 1 1 \\ 1 0 0 1 0 0 1 0 1 \\ 0 0 0 1 0 0 0 0 0 1 1 \\ 0 0 0 1 0 0 1 0 0 1 0 1 \\ \dots \end{array} \right] \left[ \begin{array}{l} b _ {1} \\ d _ {1} \\ e _ {1} \\ b _ {2} \\ d _ {2} \\ e _ {2} \\ b _ {3} \\ d _ {3} \\ e _ {3} \\ b _ {4} \\ d _ {4} \\ e _ {4} \end{array} \right] = [ O ] \tag {11.7-4} \]

与式 \((11.5-10)\) 对比，可以看出监督矩阵为

\[ \boldsymbol {H} = \left[ \begin{array}{c c c c} 1 1 & & & \\ 1 0 1 & & & \\ 0 0 0 & 1 1 & & \\ 1 0 0 & 1 0 1 & & \\ 1 0 0 & 0 0 0 & 1 1 & \\ 1 0 0 & 1 0 0 & 1 0 1 & \\ 0 0 0 & 1 0 0 & 0 0 0 & 1 1 \\ 0 0 0 & 1 0 0 & 1 0 0 & 1 0 1 \\ & & \dots \end{array} \right] \tag {11.7-5} \]

由此例可见，在卷积码中，监督矩阵 H 是一个有头无尾的半无穷矩阵。观察式 (11.7-5), 可以看出，这个矩阵的每 3 列的结构是相同的，只是后 3 列比前 3 列向下移了两行。例如，第 4 列 \~ 第 6 列比第 1 列 \~ 第 3 列低 2 行。此外，自第 7 行起，每两行的左端比上两行多了 3 个 “0”。因此，虽然这样的半无穷矩阵不便于研究，但是只要研究产生前 9 个码元 (9 为约束长度) 的监督矩阵就足够了。不难看出，这种截短监督矩阵的结构形式如图 11-13 所示。由此图可见， \(H_{1}\) 的最左边是 n 列、 \((n-k)N\) 行的一个子矩阵，且向右的每 n 列均相对于前 n 列降低 \((n-k)\) 行。

3abc70c56f1b05b5630c47e20cf9272651e7e26c59b34287844cc5e9cb280e98.jpg

11.7 卷积码

此例中码的截短监督矩阵可以写为

\[ \boldsymbol {H} _ {1} = \left[ \begin{array}{l} 1 1 \\ 1 0 1 \\ 0 0 0 1 1 \\ 1 0 0 1 0 1 \\ 1 0 0 0 0 0 1 1 \\ 1 0 0 1 0 0 1 0 1 \end{array} \right] = \left[ \begin{array}{c c c c c c} \boldsymbol {P} _ {1} & \boldsymbol {I} _ {2} & & & & \\ \boldsymbol {P} _ {2} & \boldsymbol {O} _ {2} & \boldsymbol {P} _ {1} & \boldsymbol {I} _ {2} & & \\ \boldsymbol {P} _ {3} & \boldsymbol {O} _ {2} & \boldsymbol {P} _ {2} & \boldsymbol {O} _ {2} & \boldsymbol {P} _ {1} & \boldsymbol {I} _ {2} \end{array} \right] \tag {11.7-6} \]

式中： \(I_{2}=\begin{bmatrix}10\\ 01\end{bmatrix}\) ，为 2 阶单位方阵； \(P_{i}\) 为 \(2\times1\) 阶矩阵，i=1,2,3； \(O_{2}\) 为 2 阶全零方阵。

将式 \((11.7-6)\) 和式 \((11.5-11)\) 对比，可以发现它们的相似之处。一般说来，卷积码的截短监督矩阵具有如下形式:

\[ \boldsymbol {H} _ {1} = \left[ \begin{array}{c c c c c c c c} \boldsymbol {P} _ {1} & \boldsymbol {I} _ {n - k} & & & & & \\ \boldsymbol {P} _ {2} & \boldsymbol {O} _ {n - k} & \boldsymbol {P} _ {1} & \boldsymbol {I} _ {n - k} & & & \\ \boldsymbol {P} _ {3} & \boldsymbol {O} _ {n - k} & \boldsymbol {P} _ {2} & \boldsymbol {O} _ {n - k} & \boldsymbol {P} _ {1} & \boldsymbol {I} _ {n - k} & & \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & & \\ \boldsymbol {P} _ {N} & \boldsymbol {O} _ {n - k} & \boldsymbol {P} _ {N - 1} & \boldsymbol {O} _ {n - k} & \boldsymbol {P} _ {N - 2} & \boldsymbol {O} _ {n - k} & \dots & \boldsymbol {P} _ {1} & \boldsymbol {I} _ {n - k} \end{array} \right] \tag {11.7-7} \]

式中： \(I_{n-k}\) 为 \((n-k)\) 阶单位方阵； \(P_{i}\) 为 \((n-k)\times k\) 阶矩阵； \(O_{n-k}\) 为 \((n-k)\) 阶全零方阵。有时还将 \(H_{1}\) 的末行称为基本监督矩阵，即

\[ \boldsymbol {h} = \left[ \boldsymbol {P} _ {N} \boldsymbol {O} _ {n - k} \boldsymbol {P} _ {N - 1} \boldsymbol {O} _ {n - k} \boldsymbol {P} _ {N - 2} \boldsymbol {O} _ {n - k} \dots \boldsymbol {P} _ {1} \boldsymbol {I} _ {n - k} \right] \tag {11.7-8} \]

它是卷积码的一个最重要的矩阵，因为只要给定了 h, 则 \(H_{1}\) 也就随之决定了。或者说，我们从给定的 h 不难构造出 \(H_{1}\) 。

2. 生成矩阵 G

由式 \((11.7-2)\) 可知，此例中的输出码元序列可以写成

\[ \begin{array}{l} \left[ b _ {1} d _ {1} e _ {1} b _ {2} d _ {2} e _ {2} b _ {3} d _ {3} e _ {3} b _ {4} d _ {4} e _ {4} \dots \right] \\ = \left[ b _ {1} b _ {1} b _ {1} b _ {2} b _ {2} \left(b _ {2} + b _ {1}\right) b _ {3} \left(b _ {3} + b _ {1}\right) \left(b _ {3} + b _ {2} + b _ {1}\right) b _ {4} \left(b _ {4} + b _ {2}\right) \left(b _ {4} + b _ {3} + b _ {2}\right) \dots \right] \\ = \left[ b _ {1} b _ {2} b _ {3} b _ {4} \dots \right] \left[ \begin{array}{l l l l l} 1 1 1 & 0 0 1 & 0 1 1 & 0 0 0 & 0 \dots \\ 0 0 0 & 1 1 1 & 0 0 1 & 0 1 1 & 0 \dots \\ 0 0 0 & 0 0 0 & 1 1 1 & 0 0 1 & 0 \dots \\ 0 0 0 & 0 0 0 & 0 0 0 & 1 1 1 & 0 \dots \\ 0 0 0 & 0 0 0 & 0 0 0 & 0 0 0 & 1 \dots \\ 0 0 0 & 0 0 0 & 0 0 0 & 0 0 0 & 0 \dots \\ 0 0 0 & 0 0 0 & 0 0 0 & 0 0 0 & 0 \dots \\ & & \dots \end{array} \right] \tag {11.7-9} \\ \end{array} \]

与式 \((11.5-16)\) 对比可知，此码的生成矩阵 G 即为式 \((11.7-9)\) 最右矩阵，即

第 11 章 差错控制编码

\[ \boldsymbol {G} = \left[ \begin{array}{l l l l l} 1 1 1 & 0 0 1 & 0 1 1 & 0 0 0 & 0 \dots \\ 0 0 0 & 1 1 1 & 0 0 1 & 0 1 1 & 0 \dots \\ 0 0 0 & 0 0 0 & 1 1 1 & 0 0 1 & 0 \dots \\ 0 0 0 & 0 0 0 & 0 0 0 & 1 1 1 & 0 \dots \\ 0 0 0 & 0 0 0 & 0 0 0 & 0 0 0 & 1 \dots \\ 0 0 0 & 0 0 0 & 0 0 0 & 0 0 0 & 0 \dots \\ 0 0 0 & 0 0 0 & 0 0 0 & 0 0 0 & 0 \dots \\ & & \dots \end{array} \right] \tag {11.7-10} \]

它也是一个半无穷矩阵，其特点是每一行的结构相同，只是比上一行向右退后 3 列 (因现在 n=3)。

类似式 \((11.7-6)\) ，也有截短生成矩阵：

\[ \boldsymbol {G} _ {1} = \left[ \begin{array}{l l l} 1 1 1 & 0 0 1 & 0 1 1 \\ 0 0 0 & 1 1 1 & 0 0 1 \\ 0 0 0 & 0 0 0 & 1 1 1 \end{array} \right] = \left[ \begin{array}{c c c c c c} \boldsymbol {I} _ {1} & \boldsymbol {Q} _ {1} & \boldsymbol {O} & \boldsymbol {Q} _ {2} & \boldsymbol {O} & \boldsymbol {Q} _ {3} \\ & & \boldsymbol {I} _ {1} & \boldsymbol {Q} _ {1} & \boldsymbol {O} & \boldsymbol {Q} _ {2} \\ & & & & \boldsymbol {I} _ {1} & \boldsymbol {Q} _ {1} \end{array} \right] \tag {11.7-11} \]

式中： \(I_{1}\) 为一阶单位方阵； \(Q_{i}\) 为 \(1 \times 2\) 阶矩阵。

与式 (11.7-6) 比较可见，\(Q_{i}\) 是矩阵 \(P_{i}^{T}\) 的转置:

\[ \boldsymbol {Q} _ {i} = \boldsymbol {P} _ {i} ^ {\mathrm{T}} \quad i = 1, 2, \dots \tag {11.7-12} \]

一般说来，截短生成矩阵具有如下形式:

\[ \boldsymbol {G} _ {1} = \left[ \begin{array}{c c c c c c c c} \boldsymbol {I} _ {k} & \boldsymbol {Q} _ {1} & \boldsymbol {O} _ {k} & \boldsymbol {Q} _ {2} & \boldsymbol {O} _ {k} & \boldsymbol {Q} _ {3} & \dots & \boldsymbol {O} _ {k} & \boldsymbol {Q} _ {N} \\ & & \boldsymbol {I} _ {k} & \boldsymbol {Q} _ {1} & \boldsymbol {O} _ {k} & \boldsymbol {Q} _ {2} & \dots & \boldsymbol {O} _ {k} & \boldsymbol {Q} _ {N - 1} \\ & & & & \boldsymbol {I} _ {k} & \boldsymbol {Q} _ {1} & \dots & \boldsymbol {O} _ {k} & \boldsymbol {Q} _ {N - 2} \\ & & & & & & & \vdots & \vdots \\ & & & & & & & \boldsymbol {I} _ {k} & \boldsymbol {Q} _ {1} \end{array} \right] \tag {11.7-13} \]

式中： \(I_{k}\) 为 k 阶单位方阵； \(Q_{i}\) 为 \(k \times (n - k)\) 阶矩阵； \(O_{k}\) 为 k 阶全零方阵。

并将式 \((11.7-13)\) 中矩阵第一行称为基本生成矩阵：

\[ \boldsymbol {g} = \left[ \boldsymbol {I} _ {k} \boldsymbol {Q} _ {1} \boldsymbol {O} _ {k} \boldsymbol {Q} _ {2} \boldsymbol {O} _ {k} \boldsymbol {Q} _ {3} \dots \boldsymbol {O} _ {k} \boldsymbol {Q} _ {N} \right] \tag {11.7-14} \]

同样，如果基本生成矩阵 g 已经给定，则可以从已知的信息位得到整个编码序列。

以上就是卷积码的代数表述。目前卷积码的代数理论尚不像循环码那样完整严密。

11.7 卷积码

11.7.3 卷积码的解码

卷积码的解码方法可以分为两类：代数解码和概率解码。代数解码是利用编码本身的代数结构进行解码，不考虑信道的统计特性。大数逻辑解码，又称门限 (threshold) 解码，是卷积码代数解码的最主要一种方法，它也可以应用于循环码的解码。大数逻辑解码对于约束长度较短的卷积码最为有效，而且设备较简单。概率解码 (又称最大似然解码) 则是基于信道的统计特性和卷积码的特点进行计算。首先由沃曾克拉夫特 (Wozencraft) 针对无记忆信道提出的序贯解码就是概率解码方法之一；另一种概率解码方法是维特比 (Viterbi) 算法 \(^{[3]}\) 。当码的约束长度较短时，它比序贯解码算法的效率更高、速度更快，目前得到广泛的应用。下面将仅介绍大数逻辑解码和维特比解码算法。

1. 大数逻辑解码

卷积码的大数逻辑解码是基于卷积码的代数表述运算的，其一般工作原理示于图 11-14 中。上面已经提到，卷积码是一种线性码。在 11.5 节中指出，线性码有可能用校正子指明接收码组中的错码位置，从而纠正错码。图 11-14 中即利用此原理纠正错码。图中首先将接收信息位暂存于移存器中，并从接收码元的信息位和监督位计算校正子。然后，将计算得出的校正子暂存，并用它来检测错码的位置。在信息位移存器输出端，接有一个模 2 加电路；当检测到输出的信息位有错时，在输出的信息位上加 “1”, 从而纠正之。

e6fc0ff2d11b08e94a0a6bafab71565c7c923acac5cc35e5d0acafe57c50f322.jpg

这里的错码检测是采用二进制码的大数逻辑解码算法。它利用一组正交校验方程进行计算。这里的 “正交” 是有特殊定义的。其定义是，若被校验的那个信息位出现在校验方程组的每一个方程中，而其他的信息位至多在一个方程中出现，则称这组方程为正交校验方程。这样就可以根据被错码影响了的方程数目在方程组中是否占多数来判断该信息位是否错了。下面将用一个实例来具体讲述这一过程。

在图 11-15 中画出一个 (2,1,6) 卷积码编码器。其监督位和信息位的关系如下：

c3f05d7123ff9ccb03cee8cba6ed60994610b8e03efb27ddd8e0a8b909a8ca55.jpg

第 11 章 差错控制编码

当输入序列为 \(b_{1}b_{2}b_{3}b_{4}\cdots\) 时，监督位为

\[ \left\{ \begin{array}{l} c _ {1} = b _ {1} \\ c _ {2} = b _ {2} \\ c _ {3} = b _ {3} \\ c _ {4} = b _ {1} + b _ {4} \\ c _ {5} = b _ {1} + b _ {2} + b _ {5} \\ c _ {6} = b _ {1} + b _ {2} + b _ {3} + b _ {6} \\ \dots \end{array} \right. \tag {11.7-15} \]

参照式 \((11.5-1)\) ，由式 \((11.7-15)\) 容易写出监督关系式如下：

\[ \left\{ \begin{array}{l} S _ {1} = c _ {1} + b _ {1} \\ S _ {2} = c _ {2} + b _ {2} \\ S _ {3} = c _ {3} + b _ {3} \\ S _ {4} = c _ {4} + b _ {1} + b _ {4} \\ S _ {5} = c _ {5} + b _ {1} + b _ {2} + b _ {5} \\ S _ {6} = c _ {6} + b _ {1} + b _ {2} + b _ {3} + b _ {6} \end{array} \right. \tag {11.7-16} \]

式 (11.7-16) 中的 \(S_{i}(i=1\sim6)\) 称为校正子，经过简单线性变换后，可以得出如下正交校验方程组:

\[ \left\{ \begin{array}{l} S _ {1} = c _ {1} + b _ {1} \\ S _ {4} = c _ {4} + b _ {1} + b _ {4} \\ S _ {5} = c _ {5} + b _ {1} + b _ {2} + b _ {5} \\ S _ {2} + S _ {6} = c _ {2} + c _ {6} + b _ {1} + b _ {3} + b _ {6} \end{array} \right. \tag {11.7-17} \]

在式 (11.7-17) 中，只有信息位 \(b_{1}\) 出现在每个方程中，监督位和其他信息位均最多只出现一次。因此，在接收端解码时，考察 \(b_{1}, c_{1}\) 至 \(b_{6}, c_{6}\) 等 12 个码元，仅当 \(b_{1}\) 出错时，式 (11.7-17) 中才可能有 3 个或 3 个以上方程等于 “1”。从而能够纠正 \(b_{1}\) 的错误。按照这一原理画出的此 (2,1,6) 卷积码解码器原理方框图示于图 11-16 中。由此图可见，当信息位出现一个错码时，仅当它位于信息位移存器的第 6、3、2 和 1 级时，才使校正子等于 “1”。因此，这时的校正子序列为 100111；反之，当监督位出现一个错码时，校正子序列将为 100000。由此可见，当校正子序列中出现第一个 “1” 时，表示已经检出一个错码。后面的几位校正子则指出是信息位错了，还是监督位错了。图中门限电路的输入为代表式 (11.7-17) 的 4 个方程的 4 个电压。门限电路将这 4 个电压 (非模 2) 相加。当相加结果大于或等于 3 时，门限电路输出 “1”，它除了送到输出端的模 2 加法器上纠正输出码元 \(b_{1}\) 的错码外，还送到校正子移存器纠正其中错误。

11.7 卷积码

96c3acc821a500e62cd8dd3dd8543f4c1ffec7b78cb5a6a7e21ca6079823bb8e.jpg

此卷积码除了能够纠正两位在约束长度中的随机错误外，还能纠正部分多于两位的错误。为了克服突发错误，可以采用更长的约束长度和在约束长度中能纠正更多错误的码。

2. 卷积码的几何表述

以上所述的大数逻辑解码是基于卷积码的代数表述之上的。卷积码的维特比解码算法则是基于卷积码的几何表述之上的。所以在介绍卷积码的解码算法之前，先引入卷积码的三种几何表述方法。

1）码树图

现仍以图 11-11 中的 (3,1,3) 码为例，介绍卷积码的码树图（code tree diagram）。图 11-17 画出了此码树图。将图 11-11 中移存器 \(M_{1}, M_{2}\) 和 \(M_{3}\) 的初始状态 000 作为码树的起点。现在规定：输入信息位为 “0”，则状态向上支路移动；输入信息位为 “1”，则状态向下支路移动。于是，就可以得出图 11-17 中所示的码树图。设现在的输入码元序列为 1101，则当第 1 个信息位 \(b_{1} = 1\) 输入后，各移存器存储的信息分别为 \(M_{1} = 1, M_{2} = M_{3} = 0\) 。由式 (11.7-1) 可知，此时的输出为 \(c_{1}d_{1}e_{1} = 111\) ，码树的状态将从起点 \(a\) 向下到达状态 \(b\) ；此后，第 2 个输入信息位 \(b_{2} = 1\) ，故码树状态将从状态 \(b\) 向下到达状态 \(d\) 。这时 \(M_{2} = 1\) ， \(M_{3} = 0\) ，由式 (11.7-1) 可知， \(c_{2}d_{2}e_{2} = 110\) 。第 3 位和后继各位输入时，编码器将按照图中粗线所示的路径前进，得到输出序列：111 110 010 100 …。由此码树图还可以看到，从第 4 级支路开始，码树的上半部和下半部相同。这意味着，从第 4 个输入信息位开始，输出码元已经与第一位输入信息位无关，即此编码器的约束度 \(N = 3\) 。

若观察在新码元输入时编码器的过去状态，即观察 \(M_{2} M_{3}\) 的状态和输入信息位的关系，则可以得出图中的 a、b、c 和 d 四种状态。这些状态和 \(M_{2} M_{3}\) 的关系也在图 11-17 中给出了。

码树图原则上还可以用于解码。在解码时，按照汉明距离最小的准则沿上面的码树进行搜索。例如，若接收码元序列为 111010010110…，和发送序列相比可知第 4 和第 11 码元为错码。当接收到第 4～第 6 个码元 “010” 时，将这三个码元和对应的第 2 级的上下两个支路比较，它和上支路 “001” 的汉明距离等于 2，和下支路 “110” 的汉明距离等于 1，所以选择走下支路。类似地，当接收到第 10～第 12 个码元 “110” 时，和第 4 级的上下支路比较，它和上支路的 “011” 的汉明距离等于 2，和下支路 “100” 的汉明距离等于 1，所以走下支路。这样，就能够纠正这两个错码。一般说来，码树搜索解码法并不实用，因为随着信息序列的增长，码树分支数目按指数规律增长；在上面的码树图中，只有 4 个信息位，分支已有 \(2^{4}=16\) 个。但是它为以后实用解码算法建立了初步基础。

第 11 章 差错控制编码

f062e2878a06fa9249058a2f8b295c215aa02aeecdf0f071a1310a804f9f7868.jpg

2）状态图

上面的码树可以改进为下述的状态图 (state diagram)。由上例的编码器结构可知，输出码元 \(c_{i}d_{i}e_{i}\) 决定于当前输入信息位 \(b_{i}\) 和前两位信息位 \(b_{i - 1}\) 和 \(b_{i - 2}\) （移存器 \(M_2\) 和 \(M_3\) 的状态）。在图 11-17 中已经为 \(M_2\) 和 \(M_3\) 的四种状态规定了代表符号 \(a,b,c\) 和 \(d\) 。所以，可以将当前输入信息位、移存器前一状态、移存器下一状态和输出码元之间的关系归纳于表 11-9 中。

由表 11-9 看出，前一状态 \(a\) 只能转到下一状态 \(a\) 或 \(b\) ，前一状态 \(b\) 只能转到下一状态 c 或 d，等等。按照表 11-9 中的规律，可以画出状态图如图 11-18 所示。在图 11-18 中，虚线表示输入信息位为 “1” 时状态转变的路线；实线表示输入信息位为 “0” 时状态转变的路线。线条旁的 3 位数字是编码输出比特。利用这种状态图可以方便地从输入序列得到输出序列。

1ecc79fcd812bbc8550135f6888bf9aee1fb50395ca0dcd195de3f5c67965327.jpg

0441a4b24a1b736af1ded95401fd52a143ffa1ebfb863b909c13818b0e013b0c.jpg

11.7 卷积码

表 11-9 移存器状态和输入输出码元的关系

移存器前一状态 $M_3$ $M_2$ 当前输入信息位 $b_i$ 输出码元 $c_i d_i e_i$ 移存器下一状态 $M_3$ $M_2$
a(00)0000a(00)
1111b(01)
b(01)0001c(10)
1110d(11)
c(10)0011a(00)
1100b(01)
d(11)0010c(10)
1101d(11)

3）网格图

将状态图在时间上展开，可以得到网格图 (trellis diagram), 如图 11-19 所示。图中画出了 5 个时隙。在图 11-19 中，仍用虚线表示输入信息位为 “0” 时状态转变的路线；实线表示输入信息位为 “1” 时状态转变的路线。可以看出，在第 4 时隙以后的网格图形完全是重复第 3 时隙的图形。这也反映了此 (3,1,3) 卷积码的约束长度为 3。在图 11-20 中给出了输入信息位为 11010 时，在网格图中的编码路径。图中示出这时的输出编码序列是：111 110 010 100 011 …。由上述可见，用网格图表示编码过程和输入 / 输出关系比码树图更为简练。

209c8fbe144ddfc0dfebffbb06a3d0e238937d12ef7ebdc263038dcba5fe46a7.jpg

dcffd6f2d0ab7d0e3566b359f93b9aea8462731def001ebaf0420082aa8a9566.jpg

有了上面的状态图和网格图，下面就可以讨论维特比解码算法了。

3. 维特比解码算法

维特比解码算法是维特比于 1967 年提出的。由于这种解码方法比较简单，计算快，故得到广泛应用，特别是在卫星通信和蜂窝网通信系统中应用。这种算法的基本原理是将接收到的信号序列和所有可能的发送信号序列比较，选择其中汉明距离最小的序列认为是当前发送信号序列。若发送一个 k 位序列，则有 \(2^{k}\) 种可能的发送序列。计算机应存储这些序列，以便用作比较。当 k 较大时，存储量太大，使实用受到限制。维特比算法对此作了简化，使之能够实用。现在仍用上面 (3,1,3) 卷积码的例子来说明维特比算法的原理。

第 11 章 差错控制编码

设现在的发送信息位为 1101，为了使图 11-11 中移存器的信息位全部移出，在信息位后面加入三个 “0”，故编码后的发送序列为 111 110 010 100 001 011 000，并且假设接收序列为 111 010 010 110 001 011 000，其中第 4 和第 11 个码元为错码。

由于这是一个 \((n,k,N)=(3,1,3)\) 卷积码，发送序列的约束度 N=3，所以首先需考察 nN=9b。第一步考察接收序列前 9 位 “111 010 010”。由此码的网格图 11-19 可见，沿路径每一级有 4 种状态 a,b,c 和 d。每种状态只有两条路径可以到达。故 4 种状态共有 8 条到达路径。现在比较网格图中的这 8 条路径和接收序列之间的汉明距离。例如，由出发点状态 a 经过 3 级路径后到达状态 a 的两条路径中上面一条为 “000 000 000”。它和接收序列 “111 010 010” 的汉明距离等于 5；下面一条为 “111 001 011”，它和接收序列的汉明距离等于 3。同样，由出发点状态 a 经过 3 级路径后到达状态 b、c 和 d 的路径分别都有两条，故总共有 8 条路径。在表 11-10 中列出了这 8 条路径和其汉明距离。

现在将到达每个状态的两条路径的汉明距离作比较，将距离小的一条路径保留，称为幸存路径 (surviving path)。若两条路径的汉明距离相同，则可以任意保存一条。这样就剩下 4 条路径了，即表中第 2,4,6 和 8 条路径。

表11-10 维特比算法解码第一步计算结果
序号路径对应序列汉明距离幸存否序号路径对应序列汉明距离幸存否
1aaaa000 000 0005否5aabc000 111 0017否
2abca111 001 0113是6abdc111 110 0101是
3aaab000 000 1116否7aabd000 111 1106否
4abcb111 001 1004是8abdd111 110 1014是

第二步将继续考察接收序列中的后继 3 位 “110”。现在计算 4 条幸存路径上增加一级后的 8 条可能路径的汉明距离。计算结果列于表 11-11 中。表中最小的总距离等于 2，其路径是 \(abdc+b\) ，相应序列为 111 110 010 100。它和发送序列相同，故对应发送信息位 1101。按照表 11-11 中的幸存路径画出的网格图示于图 11-21 中。图中粗线路径是汉明距离最小（等于 2）的路径。

b4455f3ceb09e0dfe67d1d0b1af9071c199c34118cc4653d5d646b9f33807e9b.jpg

e11f077a2e064422cf4de3947663221d7737a138b52e1ddf87bdd61813549e39.jpg

表 11-11 维特比算法解码第二步计算结果

序号路径原幸存路径的距离新增路径段新增距离总距离幸存否
1abca+a3aa25否
2abdc+a1ca23是
3abca+b3ab14否
4abdc+b1cb12是
5abcb+c4bc37否
6abdd+c4dc15是
7abcb+d4bd04是
8abdd+d4dd26否

上面提到过，为了使输入的信息位全部通过编码器的移存器，使移存器回到初始状态，在信息位 1101 后面加了三个 “0”。若把这三个 “0” 仍然看作是信息位，则可以按照上述算法继续解码。这样得到的幸存路径网格图示于图 11-22 中。图中的粗线仍然是汉明距离最小的路径。但是，若已知这三个码元是 (为结尾而补充的)“0”, 则在解码计算时就预先知道在接收这三个 “0” 码元后，路径必然应该回到状态 a。而由图可见，只有两条路径可以回到 a 状态。所以，这时图 11-22 可以简化成图 11-23。

在上例中卷积码的约束度 N=3，需要存储和计算 8 条路径的参量。由此可见，维特比解码算法的复杂度随约束长度 N 按指数形式 \(2^{N}\) 增长。故维特比解码算法适合约束度较小 (\(N\leqslant10\)) 的编码。对于约束度大的卷积码，可以采用其他解码算法，例如，序贯解码 (sequential decoding) \(^{[4]}\) 、范诺 (Fano) \(^{[5]}\) 算法等。

832ee924d59297d485bdd9b55890053700c23204ea47d7ba7652b412798dc3d6.jpg

1376c57a222be431b6a6ac6c129a0cb18494a963e40feb9fef3e44f8900f465b.jpg

11.8 Turbo 码

Turbo 码是 1993 年才发明的一种特殊的链接码 (concatenated code) \(^{[6]}\) 。由于其性能接近信息理论上能够达到的最好性能，所以这种码的发明在编码理论上是带有革命性的进步。这种码，特别是解码运算，非常复杂，这里只对其基本概念作一简明介绍。

第 11 章 差错控制编码

由于分组码和卷积码的复杂度随码组长度或约束度的增大按指数规律增长，所以为了提高纠错能力，人们大多不是单纯增大一种码的长度，而是将两种或多种简单的编码组合成复合编码。Turbo 码的编码器在两个并联或串联的分量码 (component code) 编码器之间增加一个交织器 (interleaver), 使之具有很大的码组长度，能在低信噪比条件下得到接近理想的性能。Turbo 码的译码器有两个分量码译码器，译码在两个分量译码器之间进行迭代译码，故整个译码过程类似涡轮 (turbo) 工作，所以又形象的称为 Turbo 码。

图 11-24 为 Turbo 码的一种基本结构，它由一对递归系统卷积码 (Recursive Systematic Convolution Code, RSCC) 编码器和一个交织器组成。RSCC 编码器和前面讨论的卷积码编码器之间的主要区别是从移存器输出端到信息位输入端之间有反馈路径。原来的卷积码编码器没有这样的反馈路径，所以像是一个 FIR 数字滤波器。增加了反馈路径后，它就变成了一个 IIR 滤波器，或称递归滤波器，这一点和 Turbo 码的特征有关。在图 11-25 中给出了一个 RSCC 编码器的例子，它是一个码率等于 \(1 / 2\) 的卷积码编码器，输入为 \(b_{i}\) 输出为 \(b_{i}c_{i}\) 。因为输出中第 1 位是信息位，所以它是系统码。图 11-24 中的两个 RSCC 编码器通常是相同的。它们的输入是经过一个交织器并联的。此 Turbo 码的输入信息位是 \(b_{i}\) ，输出是 \(b_{i}c_{1i}c_{2i}\) ，故码率等于 \(1 / 3\) 。

5010fbc2fd01946723e23cb88631356498dc1dba9b5a580f7f0b09e35e84cc1b.jpg

d48079de373b6940822c2e6dab7a7b054589f92a27002f63384b464be5b534ee.jpg

交织器的基本形式是矩阵交织器，它由容量为 \((n-1)m\) 比特的存储器构成。图 11-26 为交织器原理图。将信号码元按行的方向输入存储器，再按列的方向输出。这样，若输入码元序列是 \(a_{11}a_{12}\cdots a_{1m}a_{21}a_{22}\cdots a_{2m}\cdots a_{n1}\cdots a_{nm}\) ，则输出序列是 \(a_{11}a_{21}\cdots a_{n1}a_{12}a_{22}\cdots a_{n2}\cdots a_{1m}\cdots a_{nm}\) 。交织的目的是将集中出现的突发错码分散开，变成随机错码。例如，若图中第 1 行的 m 个码元构成一个码组，并且将其连续发送到信道上，则当此码组遇到脉冲干扰，造成大量错码时，可能因超出纠错能力而无法纠正错误。但是，若在发送前进行了交织，按列发送，则能够将集中的错码分散到各个码组，从而有利于纠错。这种交织器常用于分组码的交织中。

图 11-26 交织器原理图

$a_{11}$ $a_{12}$ ......... $a_{1m}$
$a_{21}$ $a_{22}$ ......... $a_{2m}$
..................
$a_{n1}$ $a_{n2}$ ......... $a_{nm}$

另一种交织器称为卷积交织器。在图 11-27 中给出一个简单的例子。它是由三个移存器构成。第 1 个移存器只有 1b 容量；第 2 个移存器可以存 2b；第 3 个移存器可以存 3b。交织器的输入码元依次进入各个移存器。在图 11.27 (a) 的交织器中示出，第 1 个输入码元没有经过存储而直接输出；第 2 个输入码元存入第 1 个移存器中；第 3 个输入码元存入第 2 个移存器中；第 4 个码元存入第 3 个移存器中。在这 4 个码元期间，交织器的输出为 “1xxx”。这里的 “x” 表示移存器初始的随机状态。在图 11-27 (b) 中的交织器则示出第 5\~ 第 8 个码元输入时的工作状态。在图 11-27 (c) 和 11-27 (d) 中示出的是第 9\~ 第 12 个码元以及第 \(13\sim\) 第 16 个码元输入时的工作状态。这样，交织器输出码元的次序将是： \(1xxx52xx963x131074\) 。接收端解交织器的工作过程与此相反，如图 11-27 所示，解交织器的输出码元的次序将是 xxxxxxxxxx1234，其中前面接收的 12 个码元无意义，从第 13 个码元开始才是有效码元。

b1324c9c1dcf567a1a4e96242092f5574a70ebae3775067926bbeab7ba9cf038.jpg

1f6df087d9826e897335d4493c96d057aa312c737f8c351af2d0e26ab8d22641.jpg

6f26b8b28b939002026045472d8fde8124f6baa194a0eb752de545052d5c61c0.jpg

b2ed0c20e569b3f18372696d1a62ba1bd88096e6fbcaf847d6709bbb4815708a.jpg

e5fb96df2aeb1f2b62fa4a26cefd21a94010bd4bfed45a68729f28a59cad45c1.jpg

上面给出的是一个简单的卷积交织器例子。一般说来，第 1 个移存器的容量可以是 k 比特，第 2 个移存器的容量是 2k 比特，第 3 个移存器的容量是 3k 比特，…，直至第 N 个移存器的容量是 Nk 比特。

卷积交织法和矩阵交织法相比，主要优点是延迟时间短和需要的存储容量小。卷积交织法端到端的总延迟时间和两端所需的总存储容量均为 \(k(N+1)N\) 个码元，是矩阵交织法的一半。

在图 11-28 中给出了 Turbo 码的两条性能曲线。由此曲线可以看到，交织器容量大时误码率低，这是因为交织范围大可以使交织器输入码元得到更好的随机化。

第 11 章 差错控制编码

11.9 低密度奇偶校验码

低密度奇偶校验（Low-Density Parity-Check, LDPC）码在 1962 年已经由 Gallager 发明 [7]。由于此码在码组很长时才具有优良性能，而当时计算机的能力还不足以处理如此长的码组，所以没有引起人们对它注意。直到 1996 年 MacKay 和 Neal 两人才分别独立地重新发明了它。现在，LDPC 码已经较广泛地应用于移动通信、无线局域网和光纤通信等许多领域。

LDPC 码是一种线性分组码，和 Turbo 码同属于复合码类。两者的性能相近，且两者的译码延迟都相当长，所以它们更适用于一些实时性要求不很高的通信。但是 LDPC 码比 Turbo 码的译码简单，更易实现。

LDPC 码又分为规则 LDPC 码和非规则 LDPC 码两类。规则 LDPC 码中 H 矩阵每列具有相同个数的 “1”，否则称为非规则 LDPC 码。非规则 LDPC 码是在规则 LDPC 码基础上发展出的，它使解码性能得到改善，使误码率性能比 Turbo 码还好。图 11-29 为非规则 LDPC 码和 Turbo 码的误码率性能比较 \(^{[8]}\) 。图中的虚线是 Turbo 码的性能，实线是 LDPC 码的性能。码长分别为 \(10^{3}, 10^{4}, 10^{5}\) 和 \(10^{6}\) ，码率都是 1/2。从图可以看出，当码长 n 约为 \(10^{4}\) 以上时，LDPC 码的性能才比 Turbo 码好。而且 n 越大，好得越多。

LDPC 码和普通的奇偶监督码一样，可以由有 n 列、m 行的奇偶监督矩阵 H 确定；n 是码长，m 是校正子个数。但是其 H 矩阵和普通奇偶监督码的有所不同：首先它是稀疏矩阵，即矩阵中 “1” 的个数很少，密度很低；设 H 矩阵每列有 j 个 “1”, 每行有 k 个 “1”, 则应有 \(j \ll m, k \ll n\) , 且 \(j \geqslant 3\) 。其次其 H 矩阵的任意两行的元素不能在相同位置上为 “1”, 即 H 矩阵中没有四角由 “1” 构成的矩形。LDPC 码通常用上述三个参量 \((n, j, k)\) 表示。在编码时，设计好 H 矩阵后，由 H 矩阵可以导出生成矩阵 G。这样，对于给定的信息位，不

11.9

低密度奇偶校验码

The image is too blurry to recognize any text content.

The quick brown fox jumps over the lazy dog.

难算出码组。

LDPC 码的解码方法也和一般的奇偶监督码的解码方法不同。基本的解码算法称为置信传播算法 (Belief Propagation Algorithm)，通常简称 BP 算法。这种算法实质上是求最大后验概率，类似于一般的最大似然准则解码算法，但是它需要进行多次迭代运算，逐步逼近最优的解码值。

LDPC 码的具体编解码算法十分复杂，这里不再深入讨论。

11.10 网格编码调制

11.10.1 网格编码调制的基本概念

应用纠错编码可以在不增加功率的条件下降低误码率，但是付出的代价是占用的带宽增大了。如何才能同时节省功率和带宽，是人们长久追求的目标。将纠错编码和调制相结合的网格编码调制 (TCM) 就是解决这个问题的途径之一。TCM 是由 Ungerboeck 提出的 \(^{[9]}\) 。这种调制在保持信息传输速率和带宽不变的条件下能够获得 3dB\~6dB 的功率增益，因此得到广泛的关注和应用。下面将利用一个实例给出 TCM 的基本概念。

首先来回忆 QPSK 系统。QPSK 是一个 4 相相移键控系统，它的每个码元传输 2b 信息。若在接收端判决时因干扰而将信号相位错判至相邻相位，则将出现错码。现在，将系统改成 8PSK，它的每个码元可以传输 3b 信息。但是我们仍然令每个码元传输 2b 信息。第 3b 用于纠错码，例如，采用码率为 2/3 的卷积码。这时接收端的解调和解码是作为一个步骤完成的，不像传统作法，先解调得到基带信号后再为纠错去解码。

在纠错编码理论中，码组间的最小汉明距离决定着这种编码的纠错能力。在 TCM 中，由于是直接对于已调信号（现在是 8PSK 信号）解码，码元之间的差别是载波相位之差，这个差别是欧氏距离（Euclidian distance）。在图 11-30 中示出了 8PSK 信号星座图中的 8 个信号点。图中已假设信号振幅等于 1，则相邻两信号点的欧几里得距离 \(d_0 = 0.765\) 。两个信号序列的欧几里得距离越大，即它们的差别越大，则因干扰造成互相混淆的可能性越小。应当记住，图中的信号点代表某个确定相位的已调信号波形。

08aa569d7a424acefe21ee30812da9829fd5d90f6e296b244625cbd4f169c1eb.jpg

为了利用卷积码维特比解码的优点，这时仍然需要用到网格图。但是，和卷积码维特比解码时的网格图相比，在 TCM 中是将这些波形映射 (mapping) 为网格图，故 TCM 网格图中的各状态是波形的状态。

11.10.2 TCM 信号的产生

TCM 的编码和调制方法是建立在 Ungerboeck 提出的集划分方法的基础上的。这种划分方法的基本原则是将信号星座图划分成若干子集 (subset)，使子集中的信号点间距离比原来的大。每划分一次，新的子集中信号点间的距离就增大一次。图 11-31 中给出了 8PSK 信号星座图划分的例子。图中 \(A_{0}\) 是 8PSK 信号的星座图，其中任意两个信号点间的距离为 \(d_{0}\) 。这个星座被划分为 \(B_{0}\) 和 \(B_{1}\) 两个子集，在子集中相邻信号点间的距离为 \(d_{1}\) 。在图 11-30 中已经示出 \(d_{1}>d_{0}\) 。将这两个子集再划分一次，得到 4 个子集： \(C_{0},C_{1},C_{2},C_{3}\) ，它们中相邻信号点间的距离为 \(d_{2}=2\) 。显然， \(d_{2}>d_{1}>d_{0}\) 。

第 11 章 差错控制编码

4a8423a446bd517e70a2079ca869266ae394fc2fecd6f2881ba01026bd5435e1.jpg

在这个 TCM 系统的例子中，需要根据已编码的 3b 来选择信号点，即选择波形的相位。这个系统中卷积码编码器的方框图示于图 11-32 中。由图可见，这个卷积码的约束长度等于 3。编码器输出的前两个比特 \(c_{1}\) 和 \(c_{2}\) 用来选择星座图划分的路径，最后 \(1\mathrm{b}, c_{3}\) , 用于选定星座图第 3 级 (最低级) 中的信号点。在图 11-31 中，\(c_{1}, c_{2}\) 和 \(c_{3}\) 表示已编码的三个码元，图中最下一行注明了 \((c_{1}c_{2}c_{3})\) 的值。若 \(c_{1} = "0"\) , 则从 \(A_{0}\) 向左分支走向 \(B_{0}\) ; 若 \(c_{1} = "1"\) , 则从 \(A_{0}\) 向右分支走向 \(B_{1}\) 。第 2 和第 3 个码元 \(c_{2}\) 和 \(c_{3}\) 也按照这一原则选择下一级的信号点。

9075c3403f9f8c15fdaf010c009aa9d319eb73c85c3859108cdeb74b951d22b9.jpg

一般说来，TCM 编码器结构如图 11-33 所示，它将 \(k\) 比特输入信息段分为 \(k_{1}\) 和 \(k_{2}\) 两段；前 \(k_{1}\) 比特通过一个 \((n_1,k_1,m)\) 卷积码编码器，产生 \(n_1\) 比特输出，用于选择信号星座图中 \(2^{n_1}\) 划分之一，后面的 \(k_{2}\) 比特用于选定星座图中的信号点。这表明星座图被划分为 \(2^{n_1}\) 个子集，每个子集中含有 \(2^{k_2}\) 个信号点。在图 11-32 中， \(k_{1} = k_{2} = 1\) 。

TCM 系统中的网格图和卷积码的网格图略有不同。在图 11-34 中示出了这个 8PSK 系统的网格图。由于未编码比特有两种取值，所以每个状态下，有两根线。例如，设初始状态 \(b_{1}b_{2}=00,k_{1}=k_{2}=0\) 。当输入信号序列 \(k_{1}\) 为 “0110100” 时，移存器状态和输出 \(c_{1}\) 与 \(c_{2}\) 之间的关系示于表 11-12 中。在第 1 个输入码元 “1” 到达后，输出码元 \(c_{1}\) 和 \(c_{2}\) 由 “00” 变成 “01”，但是这时的输入信息位 \(k_{2}\) 可能是 “0” 或 “1”，所以输出 \(c_{1}c_{2}c_{3}\) 可能是 “010” 或 “011”，这就是图 11-34 中最高的两条平行虚线。在第 1 个输入码元 “1” 进入 \(b_{1}\) 后， \(b_{1}b_{2}\) 的状态由 “00”(a) 变到 “10”(b)，输出 \(c_{1}c_{2}c_{3}\) 可能是 “110” 或 “111”， \(b_{1}b_{2}\) 的状态由 b 变到 d，如图 11-34 中虚线所示。依此类推。在此图中，用实线表示输入信息位 \(k_{2}\) 为 “0”，用虚线表示输入信息位 \(k_{2}\) 为 “1”。

11.10

网格编码调制

The image is too blurry to recognize any text content.

The quick brown fox jumps over the lazy dog.

60de62915e9c6a3087c09ac127e53dea09083c91e2068eca8a2197f00d52298b.jpg

为了得到最佳的纠错效果，Ungerboeck 研究出上述网格图和星座图之间的对应关系应该符合下列直观规则:

表 11-12 移存器状态和输出之间的关系

$k_1$ $b_1$ $b_2$ 状态 $c_1$ $c_2$
00a00
000a00
100a01
110b11
011d11
101c00
010b10
001c01
000a00

e197cf85ed876c5d31f23bc2b8c93670e11c69354569824cf487599f74fdccbb.jpg

11. 10. 3 TCM 信号的解调

TCM 信号的解调通常都采用维特比算法，但是现在的网格图表示的状态是波形，而不是码组。解码器的任务是计算接收信号序列路径和各种可能的编码网格路径 (简称可能路径) 间的距离。若所有发送信号序列是等概率的，则判定与接收序列距离最小的可能路径 (又称为最大似然路径) 为发送序列。

第 11 章 差错控制编码

因为卷积码是线性码，它具有封闭性 (11.5 节), 故要考察的路径距离与所用的测试序列无关。所以，不失一般性，可以选用全 “0” 序列作为测试序列，如图 11-35 中虚线路径 U 所示。图中还用实线示出另一许用波形序列路径 V, 它从全 “0” 序列路径分开又回到全 “0” 序列路径。若发送序列是全 “0” 序列，但是接收序列中有错误，使接收序列路径离开全 “0” 路径然后又回到全 “0” 序列，且中间没有返回状态 a, 则解码器需要比较此接收序列路径和 U 的距离与接收序列路径和 V 的距离之大小。若后者小，则将发生一次错误判决。这里的距离是指欧几里得距离。

6a6ff2d7ab374c178f25661e1828e8668f31deda41e7f2a812d6e555381b4421.jpg

这里，我们将引入自由欧几里得距离 (Fed) 的概念。自由欧几里得距离是指许用波形序列集合中各元素之间的最小距离。它决定了产生错误判决的概率。自由欧几里得距离越大，错误判决概率越小。在上例中，U 和 V 两条路径间的欧几里得距离 d 由下式决定:

\[ \begin{array}{l} d ^ {2} = d ^ {2} \left(U _ {1}, V _ {1}\right) + d ^ {2} \left(U _ {2}, V _ {2}\right) + d ^ {2} \left(U _ {3}, V _ {3}\right) \\ = d ^ {2} (0 0 0, 0 1 0) + d ^ {2} (0 0 0, 1 0 0) + d ^ {2} (0 0 0, 0 1 0) \tag {11.10-1} \\ = (\sqrt {2}) ^ {2} + (0. 7 6 5) ^ {2} + (\sqrt {2}) ^ {2} = 2 + 0. 5 8 5 + 2 = 4. 5 8 5 \\ \end{array} \]

式 (11.10-1) 是按照在欧几里得空间求矢量和的方法计算的。因此，

\[ d = \sqrt {4 . 5 8 5} = 2. 1 4 \tag {11.10-2} \]

另外一种许用波形序列的路径是 \(U_{1}WU_{3}\) （图 11-35）。它和 V 序列相似，从状态 a 开始，离开 U（虚线路径），再回到状态 a。这个路径和 U 的距离计算如下：

\[ \begin{array}{l} d ^ {2} = d ^ {2} \left(U _ {1}, U _ {1}\right) + d ^ {2} \left(U _ {2}, W\right) + d ^ {2} \left(U _ {3}, U _ {3}\right) \\ = d ^ {2} (0 0 0, 0 0 0) + d ^ {2} (0 0 0, 0 0 1) + d ^ {2} (0 0 0, 0 1 0) \tag {11.10-3} \\ = 0 + (2) ^ {2} + 0 = 4 \\ \end{array} \]

即 \(d = 2\) (11.10-4)

比较式 (11.10-2) 和式 (11.10-4) 可见，路径 \(U_{1}WU_{3}\) 和路径 V 相比，前者和路径 U 的距离更小。并且，可以逐个验证，这是和路径 U 距离最小的许用序列的路径。因此，按照上述定义，式 (11.10-4) 中的距离就是这种编码的自由欧氏距离。故可以将其写为

\[ d _ {\mathrm{Fed}} = 2 \]

14d8fddebae915a9c3cc99d458d026421ddaf08d7b7e6aa133303f0faf3600e5.jpg

11.10 网格编码调制

另外，未编码的 QPSK 信号的相继码元 (波形) 没有约束。若将其自由欧几里得距离作为参考距离 \(d_{ref}\) ，则由图 11-30 可知

\[ d _ {\mathrm{ref}} = d _ {1} = \sqrt {2} \]

所以，可以证明 \(^{[10-11]}\) , 和未编码 QPSK 系统相比，8PSK 的 TCM 系统可以获得的渐近编码增益 (编码增益的定义见 11.3 节) 为

\[ G _ {8 \mathrm{PSK/QPSK}} = 2 0 \log_ {1 0} (d _ {\mathrm{Fed}} / d _ {\mathrm{ref}}) = 3. 0 1 (\mathrm{dB}) \]

在表 11-13 中列出了 Ungerboeck 通过大量仿真计算得出的部分 8PSK/TCM 系统的（渐近）编码增益。

表11-138PSK/TCM的编码增益
状态数目k $G_{8PSK/QPSK}$ 状态数目k $G_{8PSK/QPSK}$
413.016425.01
823.6012825.17
1624.1325625.75
3224.59

11. 11 小结

信道编码的目的是提高信号传输的可靠性。信道编码的基本原理是在信号码元序列中增加监督码元，并利用监督码元去发现或纠正传输中发生的错误。在信道编码只有发现错码能力而无纠正错码能力时，必须结合其他措施来纠正错码，否则只能将发现为错码的码元删除。这些手段统称为差错控制。

按照加性干扰造成错码的统计特性不同，可以将信道分为三类：随机信道、突发信道和混合信道。每种信道中的错码特性不同，所以需要采用不同的差错控制技术来减少或消除其中的错码。差错控制技术共有 4 种，即检错重发、前向纠错、检错删除和反馈校验，其中前三种都需要采用编码。

编码序列中信息码元数量 k 和总码元数量 n 之比 k/n 称为码率。而监督码元数 \((n - k)\) 和信息码元数 k 之比 \((n - k)/k\) 称为冗余度。

检错重发法通常称为 ARQ。ARQ 和前向纠错方法相比的主要优点是：监督码元较少，检错的计算复杂度较低，能适应不同特性的信道。但是 ARQ 系统需要双向信道，并且传输效率较低，不适用于实时性要求高的场合，也不适用于一点到多点的通信系统。

一种编码的纠错和检错能力决定于最小码距。在保持误码率恒定条件下，采用纠错编码所节省的信噪比称为编码增益。

纠错编码分为分组码和卷积码两大类。由代数关系式确定监督位的分组码称为代数码。在代数码中，若监督位和信息位的关系是由线性代数方程式决定的，则称这种编码为线性分组码。奇偶监督码就是一种最常用的线性分组码。汉明码是一种能够纠正 1 位错码的效率较高的线性分组码。具有循环性的线性分组码称为循环码。BCH 码是能够纠正多个随机错码的循环码。而 RS 码则是一种具有很强纠错能力的多进制 BCH 码。

第 11 章 差错控制编码

在线性分组码中，发现错码和纠正错码是利用监督关系式计算校正子来实现的。由监督关系式可以构成监督矩阵。右部形成一个单位矩阵的监督矩阵称为典型监督矩阵。由生成矩阵可以产生整个码组。左部形成单位矩阵的生成矩阵称为典型生成矩阵。由典型生成矩阵得出的码组称为系统码。在系统码中，监督位附加在信息位的后面。线性码具有封闭性。封闭性是指一种线性码中任意两个码组之和仍为这种编码中的一个码组。

循环码的生成多项式 \(g(x)\) 应该是 \((x^{n}+1)\) 的一个 \((n-k)\) 次因子。在设计循环码时可以采用将码长截短的方法，满足设计对码长的要求。

BCH 码分为两类：本原 BCH 码和非本原 BCH 码。在 BCH 码中，(23,12) 码称为戈莱码，它的纠错能力强并且容易解码，故应用较多。为了得到偶数长度 BCH 码，可以将其扩展为 \((n+1,k)\) 的扩展 BCH 码。

RS 码是多进制 BCH 码的一个特殊子类。它的主要优点是：特别适合用于多进制调制的场合，和适合在衰落信道中纠正突发性错码。

卷积码是一类非分组码。卷积码的监督码元不仅和当前的 k 比特信息段有关，而且还同前面 \(m = (N - 1)\) 个信息段有关。所以它监督着 N 个信息段。通常将 N 称为卷积码的约束度。

卷积码有多种解码方法，以维特比解码算法应用最广泛。

Turbo 码是一种特殊的链接码。由于其性能近于理论上能够达到的最好性能，所以它的发明在编码理论上是带有革命性的进步。

TCM 是一种将调制和纠错编码结合在一起的体制。它能同时节省发送功率和带宽。

思考题

1303d7b5d024d2795212c9f69f0492589767dff8d7f7914f27adcfc72a2e545d.jpg

思考题

11-17 试述 Turbo 码和链接码的异同点。

11-18 LDPC 码的全称是什么？

11-19 何谓 TCM? 其中文全称是什么？TCM 中的网格图和卷积码的网格图有何不同？为什么？

11-20 何谓自由欧几里得距离？为什么需要引入这个概念？

习题

11-1 设有 8 个码组 “000000”、“001110”、“010101”、“011011”、“100011”、“101101”、“110110” 和 “111000”，试求它们的最小码距。

11-2 上题给出的码组若用于检错，试问能检出几位错码？若用于纠错，能纠正几位错码？若同时用于检错和纠错，又能有多大的检错和纠错能力？

11-3 已知两个码组为 “0000” 和 “1111”，若用于检错，试问能检出几位错码？若用于纠错，能纠正几位错码？若同时用于检错和纠错，又能检测和纠正几位错码？

11-4 若一个方阵码中的码元错误情况如图 P11-1 所示，试问能否检测出来？

11-5 设有一个码长 \(n = 15\) 的汉明码，试问其监督位 \(r\) 应该等于多少？其码率等于多少？试写出其监督码元和信息码元之间的关系。

603d5f6af8a5f64db33d1012ea07e5b3f7a780328f20198f4c33147b86885dd9.jpg

11-6 已知某线性码的监督矩阵为

\[ \boldsymbol {H} = \left[ \begin{array}{l} 1 1 1 0 1 0 0 \\ 1 1 0 1 0 1 0 \\ 1 0 1 1 0 0 1 \end{array} \right] \]

试列出其所有可能的码组。

11-7 已知一个 (7,3) 码的生成矩阵为

\[ \boldsymbol {G} = \left[ \begin{array}{l} 1 0 0 1 1 1 0 \\ 0 1 0 0 1 1 1 \\ 0 0 1 1 1 0 1 \end{array} \right] \]

试列出其所有许用码组，并求出其监督矩阵。

11-8 已知一个 (7,4) 循环码的全部码组为

0000000100010100010111001110
0010110101001100111011011000
0100111110001001011001101001
0110001111010001110101111111

试写出该循环码的生成多项式 \(g(x)\) 和生成矩阵 \(G(x)\) ，并将 \(G(x)\) 化成典型阵。

11-9 试写出上题中循环码的监督矩阵 \(\pmb{H}\) 和其典型阵。

11-10 已知一个 (15,11) 汉明码的生成多项式为

第 11 章 差错控制编码

\[ g (x) = x ^ {4} + x ^ {3} + 1 \]

试求出其生成矩阵和监督矩阵。

11-11 已知 \(x^{15} + 1 = (x + 1)(x^4 + x + 1)(x^4 + x^3 + 1)(x^4 + x^3 + x^2 + x + 1)(x^2 + x + 1)\) ，试问由它可以构成多少种码长为 15 的循环码？并列出它们的生成多项式。

11-12 已知一个 (7,3) 循环码的监督关系式为

\[ x _ {6} \oplus x _ {3} \oplus x _ {2} \oplus x _ {1} = 0 \]
\[ x _ {5} \oplus x _ {2} \oplus x _ {1} \oplus x _ {0} = 0 \]
\[ x _ {6} \oplus x _ {5} \oplus x _ {1} = 0 \]
\[ x _ {5} \oplus x _ {4} \oplus x _ {0} = 0 \]

试求出该循环码的监督矩阵和生成矩阵。

11-13 试证明 \(x^{10} + x^8 + x^5 + x^4 + x^2 + x + 1\) 为 (15,5) 循环码的生成多项式。求出此循环码的生成矩阵，并写出消息码为 \(m(x) = x^4 + x + 1\) 时的码多项式。

11-14 设一个 (15,7) 循环码由 \(g(x) = x^{8} + x^{7} + x^{6} + x^{4} + 1\) 生成。若接收码组为 \(B(x) = x^{14} + x^{5} + x + 1\) ，试问其中有无错码。

11-15 已知 \(g_{1}(x) = x^{3} + x^{2} + 1; g_{2}(x) = x^{3} + x + 1; g_{3}(x) = x + 1\) 。试分别讨论：

(1) \(g(x) = g_{1}(x) \cdot g_{2}(x), (2) g(x) = g_{3}(x) \cdot g_{2}(x)\)

两种情况下，由 \(g(x)\) 生成的 7 位循环码能检测出哪些类型的错误？

11-16 一卷积码编码器如图 P11-2 所示，已知 \(k = 1, n = 2, N = 3\) 。试写出生成矩阵 \(\pmb{G}\) 的表达式。

7fa5dbdc6ca4418e3a0768787ab1d8f03915d3b5b34f7beaa7ac74c36d841ab3.jpg

11-17 已知 \(k = 1, n = 2, N = 4\) 的卷积码，其基本生成矩阵为 \(\pmb{g} = [11010001]\) 。试求该卷积码的生成矩阵 \(\pmb{G}\) 和监督矩阵 \(\pmb{H}\) 。

11-18 已知一卷积码的参量为: \(N = 4, n = 3, k = 1\) , 其基本生成矩阵为 \(\pmb{g} = [111001010011]\) 。试求该卷积码的生成矩阵 \(\pmb{G}\) 和截短监督矩阵，并写出输入码为 \([1001\dots]\) 时的输出码。

11-19 已知一个 (2,1,2) 卷积码编码器的输出和输入的关系为

\[ c _ {1} = b _ {1} \oplus b _ {2} \]
\[ c _ {2} = b _ {2} \oplus b _ {3} \]

习题

试画出该编码器的电路方框图、码树图、状态图和网格图。

11-20 已知一个 (3,1,4) 卷积码编码器的输出和输入的关系为

\[ \begin{array}{l} c _ {1} = b _ {1} \\ c _ {2} = b _ {1} \oplus b _ {2} \oplus b _ {3} \oplus b _ {4} \\ c _ {3} = b _ {1} \oplus b _ {3} \oplus b _ {4} \\ \end{array} \]

试画出该编码器的电路方框图和码树图。当输入信息序列为 10110 时，试求出其输出码序列。

11-21 已知一个 (2,1,3) 卷积码编码器的输出与输入的关系为

\[ \begin{array}{l} c _ {1} = b _ {1} \oplus b _ {2} \\ c _ {2} = b _ {1} \oplus b _ {2} \oplus b _ {3} \\ \end{array} \]

当接收码序列为 100 010 000 0 时，试用维特比解码算法求出发送信息序列。

11-22 设有一个 TCM 通信系统，其编码器如图 11-32 所示，且初始状态 \(b_{1}b_{2}\) 为 “00”。若发送序列是等概率的，接收端收到的序列为 111001101011 (前后其他码元皆为 “0”), 试用网格图寻找最大似然路径并确定译码得出的前 6 个比特。

参考文献

第 11 章 差错控制编码

12