第9章差错控制编码9.1 学习指导9.1.1 要点差错控制编码常称为纠错编码，或信道编码，其基本思想是在发送端根据一定的规律在待发送的信息码元中加入监督码元，接收端就可以利用监督码元与信息码元的关系来发现或纠正错误，其实质就是通过牺牲有效性来换取可靠性的提高。

本章的要点有差错控制技术和编码分类；最小码距与纠检错能力；线性分组码的生成、监督和纠错；循环码的生成多项式、生成矩阵、编码和译码；卷积码的矩阵、多项式和图形描述方法。

1. 差错控制技术对于不同类型的信道，应该采用不同的差错控制技术。

差错控制技术主要有以下四种。

(1) 检错(error detection)重发(retransmission)：在发送码元序列中加入差错控制码元，接收端利用这些码元检测到有错码时，利用反向信道通知发送端，要求发送端重发，直到正确接收为止。

所谓检测到有错码，是指在一组接收码元中知道有一个或一些错码，但是不知道该错码应该如何纠正。

在二进制系统中，这种情况发生在不知道一组接收码元中哪个码元错了。

因为若知道哪个码元错了，将该码元取反即能纠正，即将错码“0”改为“1”或将错码“1”改为“0”就可以了，不需要重发。

在多进制系统中，即使知道了错码的位置，也无法确定其正确取值。

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

(2)前向纠错(Forward Error Correction)：这时接收端利用发送端在发送码元序列中加入的差错控制码元，不但能够发现错码，还能将错码恢复其正确取值。

在二进制码元情况下，能够确定错码的位置，就相当于能够纠正错码。

采用FEC时，不需要反向信道传送重发指令，也没有因反复重发而产生的时延，故实时性好。

但是为了能够纠正错码，而不是仅仅检测到错码，和检错重发相比，需要加入更多的差错控制码元。

故设备要比检测重发设备复杂。

(3)反馈(feedback)校验(check out)：这时不需要在发送序列中加入差错控制码元。

接收端将接收到的码元原封不动地转发回发送端。

在发送端将它和原发送码元逐一比较。

若发现有不同，就认为接收端收到的序列中有错码，发送端立即重发。

这种技术的原理和设备都很简单。

但是需要双向信道，传输效率也较低，因为每个码元都需要占用两次传输时间。

(4)检错删除(deletion)：它和检错重发的区别在于，在接收端发现错码后，立即将其删除，不要求重发。

这种方法只适用在少数特定系统中，在那里发送码元中有大量多余度，删除部分接收码元不影响应用。

例如，在循环重复发送某些遥测数据时。

又如，用于多次重发仍然存在错码时，这时为了提高传输效率不再重发，而采取删除的方法。

这样做在接收端当然会有少许损失，但是却能够及时接收后续的消息。

以上几种技术可以结合使用。

例如，检错和纠错技术结合使用。

当接收端出现少量错码并有能力纠正时，采用前向纠错技术；当接收端出现较多错码没有能力纠正时，采用检错重发技术。

2. 信道编码分类按照信道特性和设计的码字类型分类，信道编码可以分为纠独立随机差错码，、纠突发差错码和纠混合差错码。

按照码字的功能分类，有检错码和纠错码。

按监督码元与信息码元之间的关系分类，有线性码和非线性码。

按照对信息码元和监督码元的约束关系分类，有分组码和卷积码。

按照信息码元在编码后是否保持原来的形式不变，可划分为系统码和非系统码。

3. 纠错编码的基本概念(1) 码重和码距码重：在分组码中，码组中“1”的个数，例如，110011码组的码重为4。

码距：两个码组中对应位上数字不同的位数。

码距又称为汉明距离。

例如，101010与011011之间的距离为3。

最小码距：某种编码中各个码组之间距离的最小值。

记为d0。

一种编码的最小码距d0的大小直接关系着这种编码的检错和纠错能力。

(2) 最小码距与纠检错能力码率为R c=k/n的(n,k)分组码，纠检错能力为a.检测e个错码，要求最小码距：d0≥e + 1b.纠正t个错码，要求最小码距：d0≥2t + 1c.纠正t个错码同时可检测e个错码，要求d0≥e+t + 1 且e >t4. 线性分组码(n,k)线性分组码是以n长码字的集合构成的独立纠错码。

其组成由k位信息位的线性组合决定n-k个监督位。

在码字集合中任意两个码字模2和仍是该码中的一个码字，即线性分组码具有封闭性。

(1) 生成矩阵和监督矩阵线性分组码的编码可由生成矩阵G和监督矩阵H确定。

线性分组码的信息码元M、码组A、G阵和H阵的关系为H A T= 0T (9-1)A=MG (9-2)式中，M是编码器的输入信息码元序列；A=(a n-1,a n-2,…a1,a0)表示编码器的输出码字；0表示r个0元素组成的行向量；右上标“T”表示将矩阵转置。

只要监督阵H给定，编码时监督位和信息位的关系就完全确定了。

(n,k)线性分组码的生成矩阵G和监督矩阵H满足下列关系GH T= 0 (9-3)标准的监督矩阵H和标准的生成矩阵G之间可以相互转换。

H矩阵可以分成两部分，比如[]11101001101010*******r ⎡⎤⎢⎥==⎢⎥⎢⎥⎣⎦H PI (9-4) 式(9-4)中，P 为r ⨯ k 阶矩阵，I r 为r ⨯ r 阶单位方阵。

他们之间的关系为G =[I r ,P ]= [I r ,Q T ]或H =[Q ,I r ]= [P T ,I r ]一般的生成矩阵G 和监督矩阵H 通过初等行变换可以转化为标准的G 阵和H 阵。

(2) 线性分组码的译码线性分组码可以通过计算伴随式（或监督子）S =RH T 进行译码。

如果S=0，则接收码字无错码，否则有错。

因为H ⋅ A T = 0T 和R =A ⊕E ，所以S T =HR T =H(A ⊕E)T =HE T (9-5)将H=(h 1,h 2,…,h n )代人式(9-5)，可以得到S T =h 1e n-1⊕h 1e n-2⊕…⊕h n e 0 (9-6)式(9-6)中，h i 表示监督矩阵H 的第i 列，i =1,2,…,n 。

由式(9-6)，可以得到如下结论：a.监督子仅与错误图样有关，而与发送的具体码字无关；b.若S =0，则判断没有错码出现，它表明接收的码字是一个许用码字，当然如果错码超过了纠错能力，也无法检测出错码。

若S≠0,判断有错码出现;c.在纠错能力范围内，不同的错误图样具有不同的监督子，监督子是H 阵中“与错误码元相对应”的各列之和。

对于纠一位错码的监督矩阵，监督子就是H 阵中与错误码元位置对应的各列。

(3) 汉明码汉明码是能够纠正单个错误而且编码效率高的线性分组码。

关于线性分组码的分析方法全部适用于汉明码。

一般说来，如果希望用r 个监督码元构造的(n ,k )线性分组码能够纠正一位错码，则要求21r n -≥ (9-7)汉明码满足条件21r n -= (9-8)汉明码的监督矩阵H 的列是由所有非零的互不相同的(n-k )重二元序列组成。

如果码字中哪一位发生错误，其伴随式就是H 中该列的列矢量。

5. 循环码在线性分组码中，有一种重要的码称为循环码(cyclic code)。

它是在严密的代数学理论基础上建立起来的。

这种码的编码和解码设备都不太复杂，而且检纠错的能力较强。

循环码除了具有线性码的一般性质外，还具有循环性。

循环性是指任一码组循环一位（即将最右端的一个码元移至左端，或反之）以后，仍为该码中的一个码组。

(1) 码多项式在代数编码理论中，为了便于计算，通常用多项式去描述循环码，它把码组中各码元当作是一个多项式(poly-nomial)的系数，即把一个长度为n 的码组表示成121210()n n n n T x a x a x a x a ----=++++ (9-9)在循环码中，若T (x )是一个长为n 的许用码组，则x i ﹒T (x )在按模x n +1运算下，也是该编码中的一个许用码组，即若）（模)1()()(+'≡⋅n i x x T x T x (9-10) 则T '(x )也是该编码中的一个许用码组。

(2) 生成多项式在一个(n , k )循环码中，有一个且仅有一个次数为(n-k )的多项式：111()11n k n k n k g x x a x a x -----=⋅+++ (9-11)称此g (x )为该循环码的生成多项式。

g (x )表示该循环码的前(k -1)位皆为“0”的码组。

g (x )有如下性质：a. g (x )是一个常数项为1，最高次数为(n -k )次，且是x n +1的一个因式。

b. 所有码多项式T (x )都可被g (x )整除，而且任意一个次数不大于(k -1)的多项式乘g (x )都是码多项式。

(3) 生成矩阵G在循环码中，一个(n , k )码有2k 个不同的码组。

若用g (x )表示其中前(k -1)位皆为“0”的码组，则g (x )，xg (x )，x 2g (x )，⋯，x k-1g (x )都是码组，而且这k 个码组是线性无关的。

因此它们可以用来构成此循环码的生成矩阵G 。

一旦确定了g (x )，则整个(n , k )循环码就被确定了。

因此，循环码的生成矩阵G 可以写成12()()()()()k k x g x x g x x xg x g x --⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦G (9-12) 由于上面的生成矩阵不是标准阵，这样编码得到的码字一般不是系统码。

(4) 系统循环码的编码思路a. 用信息码元的多项式m (x )表示信息码元。

b. 用x n - k 乘m (x ),得到 x n - k m (x )。

c. 用g (x )除x n - k m (x )，得到商Q (x )和余式r (x )，即()()()()()n k x m x r x Q x g x g x -=+(9-13) d. 编出的码组()T x 为()()()n k T x x m x r x -=+ (9-14)(5) 循环码的译码接收端可以将接收码组R (x )用原生成多项式g (x )去除。

当传输中未发生错误时，接收码组与发送码组相同，即R (x ) = T (x )，故接收码组R (x )必定能被g (x )整除；若码组在传输中发生错误，则R (x ) ≠ T (x )，R (x )被g (x )除时可能除不尽而有余项，从而发现错误。

纠正错码相对复杂。

因此，原则上纠错可按下述步骤进行： a. 用生成多项式g (x )除接收码组R (x )，得出余式r (x )。

b. 按余式r (x )，用查表的方法或通过某种计算得到错误图样E (x )；例如，通过计算校正子S 和表中的关系，就可以确定错码的位置。

c. 从R(x )中减去E (x )，便得到已经纠正错码的原发送码组T (x )。