第十一章 差错控制编码

1、第十一章 差错控制编码l11.1 基本概念l11.2 分组码 l11.3 循环码 l11.4 BCH码 l11.5 纠正和检测突发错误的分组码 l11.6 纠错码的误码性能l误码分类噪声引入的随机误码，均匀分布由干扰、快衰落引起的突发误码l如何减少误码？从信源编码看，误码引起的性能恶化尽可能小，容错技术从传输看，可采用抗干扰能力强的调制方式，信道特性不理想可采用均衡。特别需要差错控制技术。数字通信中，要求误码率108以下，必须采用差错控制。需要双向信道，和前向信道有相同的通信容。引入较大的停顿（不实时）。可以纠正任何错误。分组存储发收收发kIkI控制自动请求重发也需要反向信道，但容量可以降低，

2、也会引入停顿检错编码存储发收收发kIkI检错译码不需要双向信道不会引入停顿靠纠错编码l如用三位二进制编码来代表八个字母000 A100E001 B101F010C110G011D111H不管哪一位发生错误，都会使传输字母错误l如用三位字母传四个字母000 A011B101 C110D发生一位错误，准用码字将变成禁用码字，接收端就能知道出错，但是不能纠错。l如用三位字母传二个字母000 A111B检三个错误，纠正一个错误。l结论具有检错或纠错的码组，其所用的比特数必须大于信息码组原来的比特数引入多余度。l码重(weight)l一个码组中“1”的数目l码距(distance)l两个码组之间对应位置

3、上1、0不同的位数，又叫汉明(Hamming)距。10 1 1 0 码重：301 1 00 2 距离：3l 为检查出 个错误，要求最小码距为l 为纠正 个错误，要求最小码距为l 为纠正 个错误，同时检查出 个错误，要求最小码距为 e1minedt12min td)(1mintetedetl按功能分l检错码 l纠错码l纠删码（发现不可纠正的错误时，可发出指示或删除）l按信息码元和监督码元之间的校验关系分l线性码l非线性码l按信息码元和监督码元之间的约束方式分l分组码l卷积码l纠错码建立在香农理论基础上l香农定理存在噪声干扰的信道，若信道容量为C，只要发送端以低于C的速率R发送信息（R为输入到编码

4、器的二进制码元速率），则一定存在一种编码方式，使编码的错误概率随着码长n的增加将按指数下降到任一的值，即l结论如码长及发送信息速率一定，可以通过增大信道容量，使P减小。如在信道容量及发送信息速率一定，可以通过增加码长，使错误概率下降。RnEePl表示： (n,k)n : 帧长k/n : 编码效率l特点监督码只用来监督本帧中的信息位l分类线性码 信息码与监督码之间为线性关系非线性码 不存在线性关系kn-k信息位监督位nl偶监督l奇监督l如果以上关系被破坏，则出现错误，因此能检查出奇数个错误，但不能检测偶数个错误。最小码距为 dmin=2l这种码检错能力不高，采用什么方法提高呢？01221 aaa

5、aann信息位监督位00121aaaann10121aaaannl又叫 二维奇偶监督码l水平奇偶监督码检码字按行排成方阵，每行采用奇偶监督码，发送时按列的顺序传送，接收时仍将码字排列成发送时方阵形式，然后按行进行奇偶校验。在不增加冗余度时，不仅能发现某一行上奇数个错误，而且也能发现不大于方阵行数的突发错误。l水平垂直奇偶监督码不仅对行进行奇偶校验，而且也对列进行奇偶校验。l在码长一定时，“1”码和“0”码的比例恒定。已用于电报传输中。l五中取三0101111001表示十位数字，C53=10种许用码组。l11.1 基本概念l11.2 分组码 l11.3 循环码 l11.4 BCH码 l11.5

6、纠正和检测突发错误的分组码 l11.6 纠错码的误码性能l汉明码：能纠一位错误(7,4)监督位信息位0123456,aaaaaaa346035614562aaaaaaaaaaaa监督方程：在接收端，按如下规律运算034631356224561aaaaSaaaaSaaaaS无错错码位置0001110111011100010101006543210111aaaaaaaSSS）。称为校正子（或伴随式、因此应纠为：错误。，知道，运算后得到如收到的结果，就可以纠错。、根据32133213210001011100000011SSSaSSSSSSl分组码的监督方程l矩阵形式000034613562456aa

7、aaaaaaaaaa0001001101010101100101110123456Taaaaaaal监督矩阵lH矩阵称为典型形式，各行一定是线性无关的。而一个非典型形式的经过运算可以化成典型形式，通过监督矩阵可以知道监督码和信息码的监督关系。rrkrrrIPH,100110101010110010111l生成矩阵 ，通过生成矩阵可以得到生成码组。l如果输入码组为 00111101010111111000010000100001,QIGkTPQ 0111100110101011111100001000010000111001100GA110 00110011l由这种方式得到的生成矩阵称为典型生成

8、矩阵，由它产生的分组码必定为系统码，也就是信息码字保持不变，监督位附加其后，每行一定是线性无关的，每行都是一个生成码组。汉明码监督位为 位，因此它可以组成 个可能情况，其中一个为无错。因此可以监督码位共 要纠正一个错误，必须满足最小码距l如果 r 位监督位所组成的校正子码组与误码图样一一对应，这种码组称为完备码（取等号时）rr212 r12 ,12rknrr即3mindl如果在汉明码基础上，再加上一位对所有码字进行校验的监督位监督码字由 r 位增加到 r+1 位信息位不变l码长 码结构l纠 1 位错，检测 2 位错l如 （8，4），（16，11） rn2) 12 ,2( rrr如 (7,4)

9、(8,4)0001111HHEl(n,k) (n-s, k-s)l如 (15,11) (12,8)监督矩阵 Hs 是将原 H 的前 3 列 去掉l缩短汉明码的最小码距至少和原来码的码距相同，因为监督位没有变。l能纠 t 个错误的(n,k)应满足取等号时为完备码l不同结构的线性码其纠错能力不同，能力和dmin 有关，dmin 越大越好。tiintnnnknrCCCC021122l上界： 汉明界， 普洛特金界l下界： 吉尔伯特界l问题： 给定码长与编码效率，寻找 dminl例： dmin=5, 码长=63 的分组码设计从汉明界得，因此信息位最多可以取)2, 5(22min2063个错误纠dCiik

10、nr最小监督位数11,20172knrkn上界521163l通过吉尔伯特界求下界l线性码 k 越接近 52， 效率越高。下界信息位481563, 563, 52220rndCdiinrnr5248 kl11.1 基本概念l11.2 分组码 l11.3 循环码 l11.4 BCH码 l11.5 纠正和检测突发错误的分组码 l11.6 纠错码的误码性能l1957 年发现l特点线性分组码循环性任一许用码字经过循环移位后，得到的码组仍为一个许用码组l如 是循环码的一许用码组 l则 也是一许用码组 )(0123456aaaaaaa)(1234560aaaaaaal码组码多项式码组码多项式l左移一位l左移

11、 位)(1012nnaaaaA)()(012211aDaDaDaDAnnnn)1011100(A2346)(DDDDDA)()(102312)1(nnnnnaDaDaDaDA)(0121aaaaAnn)()(12211)(ininninniniaDaDaDaDAi)(121)(ininininiaaaaAl 为许用码组，则 也是许用码组l性质若 是长度为n的循环码组，则 在按模 进行运算后，也是一个循环码组，也就是 用 多项式除后所得之余式，即为所求的码组。 )(DA)()()(DADDAii)(DADi1nD)(DA)(DADi1nD码组左移 3 位去除 得余式如 左移 3 位后，得 是许用

12、码组015566)(aDaDaDaDA304185963)(DaDaDaDaDAD17D455263aDaDaDa1100101A0101110lg(D) 是 D的 (n-k) 次即r 次多项式l信息多项式为M(D),k 位，(k-1)次多项式101)(111或irrrgDgDgDDg0111)(mDmDmDMkkl定理.一个(n,k) 的二进制循环码可以看成是唯一由它的生成多项式产生，即J如(7,3)循环码，n=7, k=3, r=4J如果信息位为 010， M(D)=D 生成码为 0111010)()()(DgDMDA1)(234DDDDgDDDDDgDMDA345)()()(l由于 k

13、位信息位共有 个码组，都可用此法产生，如果现有信息码 生成 k 个码字，且这 k 个码组都线性无关，用这 k 个码组作为一个矩阵G 的 k行 构成生成矩阵 G(D)1)()()(021DDMDDMDDMkk)(1)()()(21DgDgDDgDDGkkk2称为循环码的生成矩阵多项式l(7,3) 循环码1)(234DDDDg1) 1(1) 1() 1()(23434524562342342342DDDDDDDDDDDDDDDDDDDDDDDG010110001011100010111G生成矩阵NK l这样构成的循环码并非是系统码l系统码的生成矩阵典型形式 l非系统码 系统码生成矩阵监督矩阵QIG

14、krTIQH100010011100100111001010110001011100010111GkIQ1000110010001100101110001101H列行NKl系统码的码多项式为l例如，(7,4)码，1011)()()(DrDDMDAkn1)(23DDDg1)(3DDDM3463)(DDDDDM)()()()()(DgDrDqDgDMDkn22454535623346231DDDDDDDDDDDDDDDD 2)(DDr监督位为10111001011l(7,3)码)(1)()()(21DgDgDDgDDGkk所得的余式除是ininknrnrknrkDDgDrDrDDrDDDrDDDG

15、)()()(1)()()(2211101110011100100111001Gl 循环码的生成多项式必须能除尽 h(D)是监督多项式，是 K阶多项式l例：要构成(7,3)循环码，求g(D). 解：g(D)应为4阶 都能生成(7,3)l生成(7,6)循环码l生成(7,1)循环码 1nD)()(1DhDgDn1) 1)(1()(1) 1)(1()() 1)(1)(1(1234324233237DDDDDDDgDDDDDDDgDDDDDD或 1)( DDg) 1)(1()(323DDDDDgl原理：按系统码的生成方式：将信息码多项式升(n-k)次幂后，再除生成多项式，然后将余式置于升幂后的信息多项式

16、之后以(7,4)码为例 )()()(DrDDMDAkn1)(23DDDg)()()()()(DgDrDqDgDMDknD1D2+D3+输入校验位码字输出l译码比编码复杂得多l译码三步伴随式S的计算由S得到错误图样纠正l发送码组 l接收码组l误差码组l校正子只与 E 有关，根本是计算校正子021aaaAnn021bbbbnnEAB021eeeEnn iiiiiibaebae则则如果, 1, 0EABTTTTT)(EHEHAHHEAHBSl生成多项式 g(D)去除接收码字B(D)(Mod)()(DgDBDSl11.1 基本概念l11.2 分组码 l11.3 循环码 l11.4 BCH码 l11.5

17、 纠正和检测突发错误的分组码 l11.6 纠错码的误码性能l特点：它也属于循环码，具有纠多个随机错误的能力，构造容易。因此由码的最小距离，可以很快得到码的生成多项式l即约多项式一个 m 次多项式不能被二元域上任何次数小于m的，但大于0的多项式除尽，如 是即约的。l本原多项式若m次多项式P(x)除尽的 的最小正整数 n 满足 ，就称为本原的。如 能除尽 ，但除不尽 的 。如 ： 是即约的，但不是本原的，因它能除尽 。 125 DD1nx12mn1)(4xxxp115x151 n1nx1234xxxx15xl由本原多项式构成的码称为本原码。l特点码长为它的生成多项式是由若干m阶或以m的因子为最高阶

18、的多项式相乘而构成。l要判定(n,k) 的循环码是否存在，只需要判断 n-k 阶的生成多项式是否能由 Dn+1的因式构成。 为正整数mm, 12l生成多项式的阶次为 r, 该生成多项式是否是 的因此。l一个m阶即约多项式一定能除尽l如，m5，共有6个5阶即约多项式。l再加上 因子， 是以上7个多项式的乘积。 kknrnknmm12, 12),(1nD1112mDDn111111345123535245234525DDDDDDDDDDDDDDDDDDDD ) 1(D131Dl表11-12表示了m12的即约多项式l在表中多项式的系数是用8进制表示的，而且反多项式没有表示 如 m=5, 45, 75

19、, 67 100101 111101 110111l如果循环码的生成多项式具有如下形式l 为纠错个数 ， 为最小多项式， 为最小公倍数，由这种方式生成的循环码是BCH码最小码距 码长为 的BCH码称为 本原BCH码（狭义BCH码） 码长为 则称为非本原BCH码 ),(),(),(LCM)(1231DmDmDmDgt)(DmiLCMt 12mn12mn12 tdl由于g(D)有t个因式，且每个因式的最高次为m，因此监督码元最多有mt位。l对于纠t 个错误的本原BCH码，其生成多项式l纠单个错误的本原BCH码为汉明码。表1113给出了 n511的本原BCH码。 1114给出了部分非本原BCH码。)

20、()()()(1231DmDmDmDgtl纠正 3 个错误，码长为15的BCH码解：n=15, m=4 查表11-12得， 23 37 07 m1(D) m3(D) m5(D) 这是(15,5)码。 1) 1)(1)(1()()()()(24581022344531DDDDDDDDDDDDDDDmDmDmDgl表1114中最重要的非本原BCH码是(23,12)称为格雷码，码距为7，能纠正3个错误。生成多项式 它是一个完备码l在实际通信系统中，所要求的n、k并不是码表中所推荐的值，在这时我们可以采用缩短或扩展的方式加以修正，也就是通过增加信息符号或校验符号来增加码组长度，或减少信息和校验位来减少

21、码组长度。1)(567911DDDDDDDgl如 BCH码的码长为奇数，而有时需要偶数码长，这时可以在原BCH码生成多项式中乘以（D+1)因子，从而得到（n+1,k）扩展BCH码，这时相当于在原BCH码上加一个全校验位，从而将码距增加1，这时的码字不具有循环性。l如果BCH码不是2m-1或它的因式，这时可以采用缩短的方式，去掉s位信息，(n-s , k-s) 缩短BCH码l非二进制BCH码，输入以符号来考虑l假定每组有 K 个符号，每个符号用m比特，输入信息将是 Km 比特。RS码一般写成（n,k,d） 最小码距lRS码适合于纠正突发错误，纠正的错误图样有l对于一个长度为 符号的RS码，每个符

22、号都可以看成是有限域 中的一个元素，如RS码的最小码距为d符号，则生成多项式个突发比特的总长度为个突发比特的总长度为比特的单个突发总长度为iimitbmtbmtb12) 12(23)3(1) 1(11112m)2(mGF)()()()(132dDDDDDg中的一个元素是)(miGRl11.1 基本概念l11.2 分组码 l11.3 循环码 l11.4 BCH码 l11.5 纠正和检测突发错误的分组码 l11.6 纠错码的误码性能l在水平垂直监督码中将信息码排列成方阵，然后对行和列分别进行检验，可以达到检测突发错误的目的。l如果方阵中行码是能纠 t 个随机错误，交织后能纠t个长度为i的突发错误。

23、i称为交织深度。itl如果每行能纠正 b 个突发错误，用上面的同样方法，构成方阵，可以纠正突发长度为bi个突发错误。l通常把i称为交织深度ibl采用循环码构成交织码时，可以不采用方阵就能实现编码。l假设交织码每行为 循环码，其生成多项式为 ， 可以除尽 ，如交织深度为 其交织码为 ,其生成多项式为 可以除尽 ，所以 也是循环码。 1nD),(kini)()(iiDgDg11)(niniDDi),(kn)(Dg)(Dg)(iDg),(kinil如，循环码(7,4)， 其生成多项式为构成交织深度为3 的(21,12)交织码。交织码的生成多项式为它也是循环码，可以用循环码的方式构成。在发送端可以不排成方阵，