第 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) 最小码距与纠检错能力码率为 Rc=k/n 的(n,k)分组码，纠检错能力为a. 检测 e个错码，要求最小码距：d0 e + 1 b. 纠正 t 个错码，要求最小码距：d02 t + 1 c.纠正 t 个错码同时可检测e个错码，要求 d0 e+t + 1 且 e t4. 线性分组码(n,k)线性分组码是以 n 长码字的集合构成的独立纠错码其组成由 k 位信息位的线性组合决定n-k 个监督位在码字集合中任意两个码字模2 和仍是该码中的一个码字，即线性分组码具有封闭性1) 生成矩阵和监督矩阵线性分组码的编码可由生成矩阵G 和监督矩阵 H 确定线性分组码的信息码元 M、码组 A、G 阵和 H 阵的关系为H AT= 0T (9-1)A=MG (9-2)式中， M 是编码器的输入信息码元序列；A=(an-1,an-2, a1,a0)表示编码器的输出码字；0 表示 r 个 0 元素组成的行向量； 右上标 “T”表示将矩阵转置 只要监督阵H 给定，编码时监督位和信息位的关系就完全确定了n,k)线性分组码的生成矩阵G 和监督矩阵 H 满足下列关系GHT= 0 (9-3)标准的监督矩阵 H 和标准的生成矩阵G 之间可以相互转换。
H 矩阵可以分成两部分，比如111010011010101011001rHPI(9-4) 式(9-4)中，P 为 r k 阶矩阵， Ir为 rr 阶单位方阵他们之间的关系为G=Ir ,P= Ir ,QT或 H=Q,Ir= PT,Ir 一般的生成矩阵 G和监督矩阵 H通过初等行变换可以转化为标准的G阵和 H 阵2) 线性分组码的译码线性分组码可以通过计算伴随式（或监督子）S=RHT进行译码如果 S=0，则接收码字无错码，否则有错因为 H AT = 0T和 R=AE，所以ST=HRT=H(AE)T=HET (9-5)将 H=(h1,h2, , hn)代人式 (9-5)，可以得到ST=h1en-1h1en-2hne0 (9-6)式(9-6)中，hi表示监督矩阵 H 的第 i 列，i=1,2, ,n 由式(9-6)，可以得到如下结论：a.监督子仅与错误图样有关，而与发送的具体码字无关；b.若 S=0，则判断没有错码出现，它表明接收的码字是一个许用码字，当然如果错码超过了纠错能力，也无法检测出错码若S0, 判断有错码出现 ; c.在纠错能力范围内， 不同的错误图样具有不同的监督子，监督子是 H 阵中“ 与错误码元相对应 ” 的各列之和。
对于纠一位错码的监督矩阵，监督子就是H阵中与错误码元位置对应的各列3) 汉明码汉明码是能够纠正单个错误而且编码效率高的线性分组码关于线性分组码的分析方法全部适用于汉明码一般说来，如果希望用 r 个监督码元构造的 (n,k)线性分组码能够纠正一位错码，则要求21rn(9-7) 汉明码满足条件21rn(9-8) 汉明码的监督矩阵 H 的列是由所有非零的互不相同的(n-k)重二元序列组成如果码字中哪一位发生错误，其伴随式就是H 中该列的列矢量5. 循环码性分组码中，有一种重要的码称为循环码(cyclic code)它是在严密的代数学理论基础上建立起来的 这种码的编码和解码设备都不太复杂，而且检纠错的能力较强 循环码除了具有线性码的一般性质外，还具有循环性 循环性是指任一码组循环一位（即将最右端的一个码元移至左端，或反之）以后，仍为该码中的一个码组1) 码多项式在代数编码理论中， 为了便于计算， 通常用多项式去描述循环码， 它把码组中各码元当作是一个多项式(poly-nomial)的系数，即把一个长度为n 的码组表示成121210( )nnnnT xaxaxa xa(9-9) 在循环码中，若 T(x)是一个长为 n 的许用码组，则 xiT(x)在按模 xn+1 运算下，也是该编码中的一个许用码组，即若）（模) 1()()(nixxTxTx(9-10) 则 T (x)也是该编码中的一个许用码组。
2) 生成多项式在一个 (n, k)循环码中，有一个且仅有一个次数为(n-k)的多项式：111( )11n kn kn kg xxaxa x(9-11) 称此 g(x)为该循环码的生成多项式 g(x)表示该循环码的前 (k-1)位皆为 “0”的码组 g(x)有如下性质：a. g(x)是一个常数项为 1，最高次数为 (n-k)次，且是 xn+1 的一个因式b. 所有码多项式 T(x)都可被 g(x)整除，而且任意一个次数不大于(k-1)的多项式乘 g(x)都是码多项式3) 生成矩阵 G 在循环码中，一个 (n, k)码有 2k个不同的码组若用g(x)表示其中前 (k-1)位皆为“0”的码组，则 g(x)，xg(x)，x2g(x)，xk-1g(x)都是码组，而且这k 个码组是线性无关的因此它们可以用来构成此循环码的生成矩阵G 一旦确定了 g(x)，则整个 (n, k)循环码就被确定了因此，循环码的生成矩阵G 可以写成12( )( )( )( )( )kkxg xxg xxxg xg xG(9-12) 由于上面的生成矩阵不是标准阵，这样编码得到的码字一般不是系统码4) 系统循环码的编码思路a. 用信息码元的多项式m(x)表示信息码元。
b. 用 xn - k乘 m(x),得到 xn - k m(x)c. 用 g(x)除 xn - k m(x)，得到商 Q(x)和余式 r(x)，即( )( )( )( )( )nkxm xr xQ xg xg x(9-13) d. 编出的码组( )T x为()()()n kT xxm xr 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)6. 卷积码卷积码是指把信源输出的信息序列，以 k 个信息码元划分为一组， 通过编码器输出长为n( k)的码段。
与线性分组码不同的是：卷积码的子码中(n-k)个监督码不仅与本组的信息码元有关， 而且也与其前 m组的信息码元有关一般用 (n,k,m)表示，其中 m 为编码存储器，它表示输入信息在编码器中需存储的单位时间编码效率 R=k/n类似于线性分组码，卷积码的输入序列A=ak-2ak-1akak+1，输出序列0:10:20:31:11:21:32:12:22:3,Cccccccccc， 监督矩阵 H 和生成矩阵 G 具有下列关系,0 ,0TTTCMGH CGH(9-15) 卷积码可以采用解析表示法， 即采用码的生成矩阵、 监督矩阵和码的多项式来计算分析此外，由于卷积码的特点，还可以采用图形表示法来研究，即从树状图、网格图和状态图的观点进行研究卷积码的译码方法主要有三种：序列译码、大数逻辑解码(门限译码 )和概率解码(最大似然译码 )9.1.2 难点本章的难点主要有汉明码的特点及检验接收码组B 是否出错的方法1. 汉明码汉明码是纠 1 位错码时，最小码距d0具有最小值且编码效率最高的(n,k)线性分组码其参数：监督位 r=n-k=m，码长 n=2m-1，信息位 k=2m-1-m；最小码距 d0=3， 纠错能力 t=1， 码率为121cmkmRn， 当 n 很大时，1cR。
汉明码是完备码这里 “ 完备” 的含义是 “ 用完了 ” 的意思，是指H 矩阵中 n个非全 “0”列，正好用完了全部21n kn组的 (n-k)各元素的列例如：在(7,4)汉明码的 H=PIr矩阵中，23-1=7 个非全 “0”列全部被利用。