循环卷积交织编码理论

循环卷积交织编码理论第一页，共五十四页，2022年，8月28日9.1.1差错控制分类需要双向信道，和前向信道有相同的通信容。引入较大的停顿（不实时）。可以纠正任何错误。1.反馈检验法第二页，共五十四页，2022年，8月28日2.检错重发法（ARQ）自动请求重发也需要反向信道，但容量可以降低，也会引入停顿第三页，共五十四页，2022年，8月28日3.前向纠错（FEC）不需要双向信道不会引入停顿靠纠错编码第四页，共五十四页，2022年，8月28日9.1.2差错控制编码的基本原理如用三位二进制编码来代表八个字母

000 A 100 E 001 B 101 F 010 C 110 G 011 D 111 H不管哪一位发生错误，都会使传输字母错误如用三位字母传四个字母

000 A 011 B 101 C 110 D发生一位错误，准用码字将变成禁用码字，接收端就能知道出错，但是不能纠错。第五页，共五十四页，2022年，8月28日差错控制编码如用三位字母传二个字母

000 A 111 B 检三个错误，纠正一个错误。结论具有检错或纠错的码组，其所用的比特数必须大于信息码组原来的比特数 －>引入余度。第六页，共五十四页，2022年，8月28日码重、码距码重(weight)一个码组中“1”的数目码距(distance)两个码组之间对应位置上1、0不同的位数，又叫汉明(Hamming)距。

10110码重：3 011002距离：3第七页，共五十四页，2022年，8月28日检错、纠错能力为检查出

个错误，要求最小码距为为纠正个错误，要求最小码距为为纠正个错误，同时检查出个错误，要求最小码距为第八页，共五十四页，2022年，8月28日9.1.3.差错控制编码分类按功能分检错码纠错码纠删码（发现不可纠正的错误时，可发出指示或删除）按信息码元和监督码元之间的校验关系分线性码非线性码按信息码元和监督码元之间的约束方式分分组码卷积码第九页，共五十四页，2022年，8月28日香农理纠错码的理论基础香农定理存在噪声干扰的信道，若信道容量为C，只要发送端以低于C的速率R发送信息（R为输入道编码器的二进制码元速率），则一定存在一种编码方式，使编码的错误概率随着码长n的增加将按指数下降道任一的值，即结论如码长及发送信息速率一定，可以通过增大信道容量，使P减小。如在信道容量及发送信息速率一定，可以通过增加码长，使错误概率下降。第十页，共五十四页，2022年，8月28日分组码表示：(n,k) n:帧长 k/n:编码效率特点监督码只用来监督本帧中的信息位分类线性码－信息码与监督码之间为线性关系非线性码－不存在线性关系第十一页，共五十四页，2022年，8月28日奇偶监督码偶监督奇监督如果以上关系被破坏，则出现错误，因此能检查出奇数个错误，但不能检测偶数个错误。 最小码距为dmin=2这种码检错能力不高，采用什么方法提高呢？第十二页，共五十四页，2022年，8月28日水平奇偶监督码和水平垂直监督码又叫二维奇偶监督码水平奇偶监督码检码字按行排成方阵，每行采用奇偶监督码，发送时按列的顺序传送，接收时仍将码字排列成发送时方阵形式，然后按行进行奇偶校验。在不增加冗余度时，不仅发现某一行上奇数个错误，而且也能发现不大于方阵行数的突发错误。水平垂直奇偶监督码不仅对行进行奇偶校验，而且也对列进行奇偶校验。第十三页，共五十四页，2022年，8月28日等比码在码长一定时，“1”码和“0”码的比例恒定。已用于电报传输中。五中取三

01011 11001

表示十位数字，C53=10种许用码组。第十四页，共五十四页，2022年，8月28日分组码(1)分组码的监督方程矩阵形式9.2线性分组码第十五页，共五十四页，2022年，8月28日分组码(2)监督矩阵H矩阵称为典型形式，各行一定是线性无关的。而一个非典型形式的经过运算可以化成典型形式，通过监督矩阵可以知道监督码和信息码的监督关系。第十六页，共五十四页，2022年，8月28日分组码(3)生成矩阵

，通过生成矩阵可以得到生成码组。如果输入码组为0011第十七页，共五十四页，2022年，8月28日分组码(4)由这种方式得到的生成矩阵称为典型生成矩阵，由它产生的分组码必定为系统码，也就是信息码字保持不变，监督位附加其后，每行一定是线性无关的，每行都是一个生成码组。第十八页，共五十四页，2022年，8月28日汉明码 汉明码监督位为位，因此它可以组成种可能情况，其中一个为无错。因此可以监督码位共 要纠正一个错误，必须满足 最小码距如果r位监督位所组成的校正子码组与误码图样一一对应，这种码组称为完备码（取等号时）第十九页，共五十四页，2022年，8月28日扩展汉明码如果在汉明码基础上，再加上一位对所有码字进行校验的监督位监督码字由r

位增加到

r+1位信息位不变码长 码结构纠1位错，检测2位错如（8，4），（16，11）第二十页，共五十四页，2022年，8月28日扩展汉明码矩阵如(7,4)－>(8,4)第二十一页，共五十四页，2022年，8月28日缩短汉明码(n,k)－>(n-s,k-s)如(15,11)－>(12,8)

监督矩阵Hs是将原H的前3列去掉缩短汉明码的最小码距至少和原来码的码距相同，因为监督位没有变。第二十二页，共五十四页，2022年，8月28日能纠t个错误的(n,k)应满足

取等号时为完备码不同结构的线性码其纠错能力不同，能力和dmin有关，dmin越大越好。第二十三页，共五十四页，2022年，8月28日最小码距界限上界：汉明界，普洛特金界下界：吉尔伯特界问题：给定码长与编码效率，寻找dmin例：dmin=5,码长=63的分组码设计

从汉明界得，

因此信息位最多可以取第二十四页，共五十四页，2022年，8月28日最小码距界限通过吉尔伯特界求下界线性码

k越接近52，效率越高。第二十五页，共五十四页，2022年，8月28日9.3循环码(Cycliccode)

1957年发现特点线性分组码循环性——任一许用码字经过循环移位后，得到的码组仍为一个许用码组如是循环码的一许用码组

则也是一许用码组

第二十六页，共五十四页，2022年，8月28日码多项式表示码组 码多项式码组码多项式左移一位左移位第二十七页，共五十四页，2022年，8月28日循环码性质

为许用码组，则也是许用码组性质 若是长度为n的循环码组，则在按模进行运算后，也是一个循环码组，也就是用多项式除后所得之余式，即为所求的码组。第二十八页，共五十四页，2022年，8月28日循环码例子码组左移3位去除得余式如左移3位后，得是许用码组第二十九页，共五十四页，2022年，8月28日循环码生成多项式g(D)g(D)是D的(n-k)次即r次多项式信息多项式为M(D),k位，(k-1)次多项式第三十页，共五十四页，2022年，8月28日Theo.一个(n,k)的二进制循环码可以看成是唯一由它的生成多项式产生，即如(7,3)循环码，n=7,k=3,r=4如果信息位为010，M(D)=D

生成码为0111010循环码生成多项式g(D)第三十一页，共五十四页，2022年，8月28日生成矩阵G(D)由于k位信息位共有个码组，都可用此法产生，如果现有信息码生成k个码字，且这k个码字都线性无关，用这k个码字作为一个矩阵G的k行构成生成矩阵G(D)第三十二页，共五十四页，2022年，8月28日循环码(7,3)循环码第三十三页，共五十四页，2022年，8月28日生成矩阵和监督矩阵这样构成的循环码并非是系统码系统码的生成矩阵典型形式非系统码系统码生成矩阵监督矩阵第三十四页，共五十四页，2022年，8月28日非系统码系统码系统码的码多项式为例如，(7,4)码，1011第三十五页，共五十四页，2022年，8月28日非系统码系统码第三十六页，共五十四页，2022年，8月28日寻找生成多项式Theo.循环码的生成多项式必须能除尽

h(D)是监督多项式例：要构成(7,3)循环码，求g(D).

解：g(D)应为4阶

生成(7,6)循环码生成(7,1)循环码第三十七页，共五十四页，2022年，8月28日循环码的编码器原理：按系统码的生成方式 以(7,4)码为例

第三十八页，共五十四页，2022年，8月28日循环码的译码器译码比编码复杂得多译码三步伴随式S的计算由S得到错误图样纠正第三十九页，共五十四页，2022年，8月28日伴随式的计算发送码组接收码组误差码组校正子只与E有关，根本是计算校正子第四十页，共五十四页，2022年，8月28日9.4BCH码即约多项式一个m次多项式不能被二元域上任何二次数小于的，但大于0的多项式除尽，如是即约的。本原多项式若m次多项式P(x)除尽的的最小正整数n满足，就称为本原的。如能除尽，但除不尽的 。如：是即约的，但不是本原的，因它能除尽。第四十一页，共五十四页，2022年，8月28日9.4.1本原循环码由本原多项式构成的码称为本原码。特点码长为它的生成多项式是由若干m阶或以m的因子为最高阶的多项式相乘而构成。要判定(n,k)的循环码是否存在，只需要判断n-k阶的生成多项式是否能由Dn+1的因式构成。第四十二页，共五十四页，2022年，8月28日循环码例子生成多项式的阶次为r,该生成多项式是否是的因此。一个m阶即约多项式一定能除尽如，m＝5，共有6个5阶即约多项式。再加上因子，是以上7个多项式的乘积。第四十三页，共五十四页，2022年，8月28日9.4.2BCH码的生成多项式如果循环码形式的形式为为纠错个数，为最小多项式， 为最小公倍数最小码距码长为的BCH码称为本BCH码（侠义）码长为则称为非本原BCH码第四十四页，共五十四页，2022年，8月28日BCH码由于g(D)有t个因式，且每个因式的最高次为m，因此监督码元最多有mt位。对于纠t个错误的本原BCH码，其生成多项式纠单个错误的本原BCH码字为汉明码。表11－13给出了n<5的本原BCH码。

11－14给出了部分非本原BCH码。第四十五页，共五十四页，2022年，8月28日BCH码例子纠正3个错误，码长为15的BCH码 解：n=15,m=5查表11-12得，

23 37 07

这是(15,5)码。

第四十六页，共五十四页，2022年，8月28日重要的BCH码(23,12)表11－14中最重要的BCH码是(23,12)

称为格雷码，码间为7，能纠正3个错误。 生成多项式在实际通信系统中，所要求的n、k并不是码表中所推荐的值，在这时我们可以采用缩短或扩展的方式加以修正，也就是通过增加信息符号或校验符号来增加码组长度，或减少信息和校验位来减少码组长度。第四十七页，共五十四页，2022年，8月28日BCH码如BCH码的码长为奇数，而有时需要偶数码长，这时可以在原BCH码生成多项式中乘以（D+1)因子，从而得到（n+1,k）扩展BCH码，这时相当于在原BCH码上加一个全校验位，从而将码距增加1，这时的码字不具有循环性。如果BCH码不是2m-1或它的因式，这时可以采用缩短的方式，去掉s位信息，(n-s,k-s)第四十八页，共五十四页，2022年，8月28日RS码Reed-Solomon非二进制BCH码，输入以符号来考虑假定每组有K个符号，每个符号用m比特，输入信息将是K×m比特。第四十九页，共五十四页，2022年，8月28日RS码RS码适合于纠正突发错误，纠正的错误图样有对于一个长度为符号的RS码，每个符号都可以看成是有限域中的一个元素，如RS码的最小码距为d符号，则生成多项式第五十页，共五十四页，2022年，8月28日9.5纠正和检测突发错误的分组码

－交织码interleaved在水平垂直监督码中将信息码排列成方阵，然后对行和列分别进行检验，可以达到检测突发错误的目的。如