循环,卷积,交织编码理论概述

1、9.1 概述概述n误码分类误码分类u噪声引入的随机误码，均匀分布噪声引入的随机误码，均匀分布u由干扰、快衰由干扰、快衰a落引起的突发误码落引起的突发误码n如何减少误码？如何减少误码？u从信源编码看，误码引起的性能恶化尽可能小，从信源编码看，误码引起的性能恶化尽可能小，容错技术容错技术u从传输看，可采用抗干扰能力强的调制方式，信从传输看，可采用抗干扰能力强的调制方式，信道特性不理想可采用均衡。特别需要差错控制技道特性不理想可采用均衡。特别需要差错控制技术。数字通信中，要求误码率术。数字通信中，要求误码率108以下，必须采以下，必须采用差错控制。用差错控制。9.1.1 差错控制分类差错控制分类 需

2、要双向信道，和前向信道有相同的通信容。u引入较大的停顿（不实时）。引入较大的停顿（不实时）。u可以纠正任何错误。可以纠正任何错误。分组存储发收收发kIkI1.1. 反馈检验法反馈检验法2. 检错重发法（检错重发法（ARQ）u自动请求重发自动请求重发u也需要反向信道，但容量可以降低，也需要反向信道，但容量可以降低，也会引入停顿也会引入停顿检错编码存储发收收发kIkI检错译码3. 前向纠错（前向纠错（FEC）u不需要双向信道不需要双向信道u不会引入停顿不会引入停顿u靠纠错编码靠纠错编码9.1.2 差错控制编码的基本原理差错控制编码的基本原理n如用三位二进制编码来代表八个字母如用三位二进制编码来代表

3、八个字母000 A100E001 B101F010C110G011D111Hu不管哪一位发生错误，都会使传输字母错误不管哪一位发生错误，都会使传输字母错误n如用三位字母传四个字母如用三位字母传四个字母000 A011B101 C110Du发生一位错误，准用码字将变成禁用码字，接发生一位错误，准用码字将变成禁用码字，接收端就能知道出错，但是不能纠错。收端就能知道出错，但是不能纠错。差错控制编码差错控制编码n如用三位字母传二个字母如用三位字母传二个字母000 000 A A111111B Bu检三个错误，纠正一个错误。检三个错误，纠正一个错误。n结论结论u具有检错或纠错的码组，其所用的比特具有检错

4、或纠错的码组，其所用的比特数必须大于信息码组原来的比特数数必须大于信息码组原来的比特数 引入余度。引入余度。码重、码距码重、码距n码重码重(weight)v一一个码组中个码组中“1”1”的数目的数目n码距码距(distance)v两个码组之间对应位置上两个码组之间对应位置上1 1、0 0不同的位数，不同的位数，又叫汉明又叫汉明(Hamming)(Hamming)距。距。10 1 1 0 码重：码重：301 1 0 0 2 距离：距离：3检错、纠错能力检错、纠错能力1) 为检查出为检查出 个错误，要求最小码距为个错误，要求最小码距为2) 为纠正为纠正 个错误，要求最小码距为个错误，要求最小码距为

5、3) 为纠正为纠正 个错误，同时检查出个错误，同时检查出 个错个错误，要求最小码距为误，要求最小码距为lmin1dl min21dtmin1()dltlt ttl9.1.3. 差错控制编码分类差错控制编码分类n按功能分按功能分v检错码检错码 v纠错码纠错码v纠删码纠删码（发现不可纠正的错误时，可发出指示或删除）（发现不可纠正的错误时，可发出指示或删除）n按信息码元和监督码元之间的校验关系分按信息码元和监督码元之间的校验关系分v线性码线性码v非线性码非线性码n按信息码元和监督码元之间的约束方式分按信息码元和监督码元之间的约束方式分v分组码分组码v卷积码卷积码香农理香农理 纠错码的理论基础纠错码的

6、理论基础n香农定理香农定理u存在噪声干扰的信道，若信道容量为存在噪声干扰的信道，若信道容量为C C，只要发送端以，只要发送端以低于低于C C的速率的速率R R发送信息（发送信息（R R为输入道编码器的二进制码为输入道编码器的二进制码元速率），则一定存在一种编码方式，使编码的错误元速率），则一定存在一种编码方式，使编码的错误概率随着码长概率随着码长n n的增加将按指数下降道任一的值，即的增加将按指数下降道任一的值，即n结论结论u如码长及发送信息速率一定，可以通过增大信如码长及发送信息速率一定，可以通过增大信道容量，使道容量，使P P减小。减小。u如在信道容量及发送信息速率一定，可以通过如在信道容

7、量及发送信息速率一定，可以通过增加码长，使错误概率下降。增加码长，使错误概率下降。nE RPe分组码分组码n表示：表示： (n,k)n : 帧长帧长k/n : 编码效率编码效率n特点特点u监督码只用来监督本帧中的信息位监督码只用来监督本帧中的信息位n分类分类u线性码线性码 信息码与监督码之间为线性关系信息码与监督码之间为线性关系u非线性码非线性码 不存在线性关系不存在线性关系 奇偶监督码奇偶监督码n偶监督偶监督n奇监督奇监督n如果以上关系被破坏，则出现错误，因此能检查如果以上关系被破坏，则出现错误，因此能检查出奇数个错误，但不能检测偶数个错误。出奇数个错误，但不能检测偶数个错误。最小码距为最小

8、码距为 dmin=2n这种码检错能力不高，采用什么方法提高呢？这种码检错能力不高，采用什么方法提高呢？01221 aaaaann信息位监督位12100nnaaaa12101nnaaaa水平奇偶监督码和水平垂直监督码水平奇偶监督码和水平垂直监督码n又叫又叫 二维奇偶监督码二维奇偶监督码n水平奇偶监督码水平奇偶监督码u检码字按行排成方阵，每行采用奇偶监督码，检码字按行排成方阵，每行采用奇偶监督码，发送时按列的顺序传送，接收时仍将码字排列发送时按列的顺序传送，接收时仍将码字排列成发送时方阵形式，然后按行进行奇偶校验。成发送时方阵形式，然后按行进行奇偶校验。u在不增加冗余度时，不仅发现某一行上奇数个在

9、不增加冗余度时，不仅发现某一行上奇数个错误，而且也能发现不大于方阵行数的突发错错误，而且也能发现不大于方阵行数的突发错误。误。n水平垂直奇偶监督码水平垂直奇偶监督码u不仅对行进行奇偶校验，而且也对列进行奇偶不仅对行进行奇偶校验，而且也对列进行奇偶校验。校验。等比码等比码n在码长一定时，在码长一定时，“1”码和码和“0”码的比例恒码的比例恒定。已用于电报传输中。定。已用于电报传输中。n五中取三五中取三0101111001表示十位数字，表示十位数字，C53=10种许用码组。种许用码组。分组码分组码 (1)n分组码的监督方程分组码的监督方程n矩阵形式矩阵形式654265316430000aaaaaa

10、aaaaaa6543210111010001101010010110010Taaaaaaa 9.2 线性分组码线性分组码分组码分组码 (2)n监督矩阵监督矩阵nH矩阵称为典型形式，各行一定是线性无关的。矩阵称为典型形式，各行一定是线性无关的。而一个非典型形式的经过运算可以化成典型形而一个非典型形式的经过运算可以化成典型形式，通过监督矩阵可以知道监督码和信息码的式，通过监督矩阵可以知道监督码和信息码的监督关系。监督关系。11101001101010,1011001r rr kr rHPI分组码分组码 (3)n生成矩阵生成矩阵 ，通过生成矩阵可以得到生成码组。，通过生成矩阵可以得到生成码组。n如果

11、输入码组为如果输入码组为 001110001110100110,00101010001011kGIQTQP10001110100110001 1001 1001 1 1 1000101010001011AG分组码分组码 (4)n由这种方式得到的生成矩阵称为典型生成矩阵，由这种方式得到的生成矩阵称为典型生成矩阵，由它产生的分组码必定为系统码，也就是信息码由它产生的分组码必定为系统码，也就是信息码字保持不变，监督位附加其后，每行一定是线性字保持不变，监督位附加其后，每行一定是线性无关的，每行都是一个生成码组。无关的，每行都是一个生成码组。00110011 110汉明码汉明码汉明码监督位为汉明码监督

12、位为 位，因此它可以组成位，因此它可以组成 种可种可能情况，其中一个为无错。因此可以监督码位能情况，其中一个为无错。因此可以监督码位共共 要纠正一个错误，必须满足要纠正一个错误，必须满足最小码距最小码距v如果如果 r r 位监督位所组成的校正子码组与误码图位监督位所组成的校正子码组与误码图样一一对应，这种码组称为完备码（取等号时）样一一对应，这种码组称为完备码（取等号时）r2r21r21, 21rrnkr 即min3d扩展汉明码扩展汉明码n如果在汉明码基础上，再加上一位对所有码字如果在汉明码基础上，再加上一位对所有码字进行校验的监督位进行校验的监督位u监督码字由监督码字由 r r 位增加到位增

13、加到 r r+1 +1 位位u信息位不变信息位不变v码长码长 码结构码结构v纠纠 1 位错，检测位错，检测 2 位错位错v如如 （8，4），（），（16，11）rn2) 12 ,2( rrr扩展汉明码矩阵扩展汉明码矩阵如如 (7,4) (8,4)1111000EHH缩短汉明码缩短汉明码n(n,k) (n-s, k-s)n如如 (15,11) (12,8)监督矩阵监督矩阵 Hs 是将原是将原 H 的前的前 3 列列 去掉去掉n缩短汉明码的最小码距至少和原来码的码缩短汉明码的最小码距至少和原来码的码距相同，因为监督位没有变。距相同，因为监督位没有变。n能纠能纠 t 个错误的个错误的(n,k)应满足

14、应满足取等号时为完备码取等号时为完备码n不同结构的线性码其纠错能力不同，能力和不同结构的线性码其纠错能力不同，能力和dmin 有关，有关，dmin 越大越好。越大越好。120221trn ktinnnniCCCC 最小码距界限最小码距界限n上界：上界： 汉明界，汉明界， 普洛特金界普洛特金界n下界：下界： 吉尔伯特界吉尔伯特界n问题：问题： 给定码长与编码效率，寻找给定码长与编码效率，寻找 dminn例：例： dmin=5, 码长码长=63 的分组码设计的分组码设计从汉明界得，从汉明界得，因此信息位最多可以取因此信息位最多可以取263min022(5,2)rn kiiCd纠 个错误22017,

15、11n krnk 最小监督位数63 11 52 上界最小码距界限最小码距界限n通过吉尔伯特界求下界通过吉尔伯特界求下界n线性码线性码 k 越接近越接近 52， 效率越高。效率越高。20225,635,63 15 48drn riniCdnr信息位 下界4852k9.3 循环码循环码 (Cyclic code) n1957 年发现年发现n特点特点u线性分组码线性分组码u循环性循环性任一许用码字经过循环移位后，得任一许用码字经过循环移位后，得到的码组仍为一个许用码组到的码组仍为一个许用码组v如如 是循环码的一许用码组是循环码的一许用码组 v则则 也是一许用码组也是一许用码组 6543210()a

16、a a a a a a0654321()a a a a a a a码多项式表示码多项式表示n码组码组码多项式码多项式u码组u码多项式n左移一位左移一位n左移左移 位位1210()nnAaaa a121210( )()nnnnA DaDaDa Da(1011100)A 6432()A DDDDD2101()nnAaa a a(1)122301()()nnnnnADaDaDa Da121()nininin iAaaaa ( )12121()()innnininin iADaDaDaDa i循环码性质循环码性质n 为许用码组，则为许用码组，则 也是许用码组也是许用码组n性质性质若若 是长度为是长度为

17、n的循环码组，则的循环码组，则 在按模在按模 进行运算后，也是一个循环码组，也进行运算后，也是一个循环码组，也就是就是 用用 多项式除后所得之余式，多项式除后所得之余式，即为所求的码组。即为所求的码组。()A D()()iiA DD A D( )iD A D1nD ()A D( )iD A D1nD 循环码例子循环码例子码组码组左移左移 3 位位去除去除 得余式得余式如如 左移左移 3 位后，得位后，得 是许用码组是许用码组656510()A Da Da Da Da398436510()D A Da Da Da Da D71D 653254a Da Da Da1100101A 0101110循

18、环码生成多项式循环码生成多项式g(D)ng(D) 是是 D的的 (n-k) 次即次即r 次多项式次多项式n信息多项式为信息多项式为M(D),k 位，位，(k-1)次多项式次多项式111( )10 1rrrig DDgDg Dg或1110()kkM DmDm DmnTheo.一个一个(n,k) 的二进制循环码可以看成是唯一的二进制循环码可以看成是唯一由它的生成多项式产生，即由它的生成多项式产生，即J如如(7,3)循环码，循环码，n=7, k=3, r=4J如果信息位为如果信息位为 010010， M(D)=DM(D)=D 生成码为生成码为 01110100111010()( ) ()A DM d

19、 g D432()1g DDDD543()() ()A DM D g DDDDD循环码生成多项式循环码生成多项式g(D)生成矩阵生成矩阵 G(D)n由于由于 k 位信息位共有位信息位共有 个码组，都可用此法产生，个码组，都可用此法产生，如果现有信息码如果现有信息码 生成生成 k 个码字，且这个码字，且这 k 个码字都线性无关，用这个码字都线性无关，用这 k 个码字作为一个矩阵个码字作为一个矩阵G 的的 k行行 构成生成矩阵构成生成矩阵 G(D)120()()()1kkMDDMDDMDD12()()()1()kkDg DDg DG Dg D2k循环码循环码n(7,3) 循环码循环码432()1g

20、 DDDD24326542432543432432(1)()(1)1 (1)1DDDDDDDDG DDDDDDDDDDDDDDD1110100()01110100011010G D生成矩阵和监督矩阵生成矩阵和监督矩阵n这样构成的循环码并非是系统码这样构成的循环码并非是系统码n系统码的生成矩阵典型形式系统码的生成矩阵典型形式 n非系统码非系统码 系统码系统码u生成矩阵生成矩阵u监督矩阵监督矩阵kGIQrTIQH100010011100100111001010110001011100010111)(DGkIQ101011001001110011101H非系统码非系统码 系统码系统码n系统码的码多项

21、式为系统码的码多项式为n例如，例如，(7,4)码，码，1011()()()n kA DM DDr D32()1g DDD3()1M DDD3643()M DDDDD()()()()()n kDM Dr Dq Dg Dg D32326436535454221DDDDDDDDDDDDDDDD2()r DD监督位为10111011100非系统码非系统码 系统码系统码12()()()1()kkDg DDg DG Dg D1122()()()1()()()krnkrnrn kn in iDDrDDDrDG DDrDrDg DD是除所得的余式1110100()01110100011010G D寻找生成多项

22、式寻找生成多项式nTheo. 循环码的生成多项式必须能除尽循环码的生成多项式必须能除尽 h(D)是监督多项式是监督多项式n例：要构成例：要构成(7,3)循环码，求循环码，求g(D). 解：解：g(D)应为应为4阶阶 v生成生成(7,6)(7,6)循环码循环码v生成生成(7,1)(7,1)循环码循环码1nD 1() ()nDg D h D 7323324234321(1)(1)(1)()(1)(1)1()(1)(1)1DDDDDDg DDDDDDDg DDDDDDDD 或()1g DD323()(1)(1)g DDDDD循环码的编码器循环码的编码器n原理：按系统码的生成方式原理：按系统码的生成方

23、式以以(7,4)码为例码为例 ()()()n kA DM DDr D32()1g DDD()()()()()n kDM Dr Dq Dg Dg DD1D2+D3+输入校验位码字输出循环码的译码器循环码的译码器n译码比编码复杂得多译码比编码复杂得多n译码三步译码三步u伴随式伴随式S S的计算的计算u由由S S得到错误图样得到错误图样u纠正纠正伴随式的计算伴随式的计算n发送码组发送码组 n接收码组接收码组n误差码组误差码组v校正子只与校正子只与 E E 有关，根本是计算校正子有关，根本是计算校正子120nnAaaa120nnbbbbBAE120nnElll0,1,iiiiiilablab如果则则B

24、AETTTTT()SB HAEHAHEHEH9.4 BCH码码n即约多项式即约多项式u一个一个 m m 次多项式不能被二元域上任何二次数小于次多项式不能被二元域上任何二次数小于的，但大于的，但大于0 0的多项式除尽，如的多项式除尽，如 是即约的。是即约的。n本原多项式本原多项式u若m次多项式P(x)除尽的 的最小正整数 n 满足 ，就称为本原的。u如 能除尽 ，但除不尽 的。u如 ： 是即约的，但不是本原的，因它能除尽 。521DD1nx 21mn 4( )1p xxx151x115n1nx 4321xxxx51x 9.4.1 本原循环码本原循环码n由本原多项式构成的码称为本原码。由本原多项式

25、构成的码称为本原码。n特点特点u码长为码长为u它的生成多项式是由若干它的生成多项式是由若干m m阶或以阶或以m m的因的因子为最高阶的多项式相乘而构成。子为最高阶的多项式相乘而构成。v要判定要判定(n,k) (n,k) 的循环码是否存在，只需要判的循环码是否存在，只需要判断断 n-k n-k 阶的生成多项式是否能由阶的生成多项式是否能由 D Dn n+1+1的因的因式构成。式构成。21,mm为正整数循环码例子循环码例子n生成多项式的阶次为生成多项式的阶次为 r, 该生成多项式是否是该生成多项式是否是 的因此。的因此。n一个一个m阶即约多项式一定能除尽阶即约多项式一定能除尽n如，如，m5，共有，

26、共有6个个5阶即约多项式。阶即约多项式。n再加上再加上 因子，因子， 是以上是以上7个多项式的乘积。个多项式的乘积。( , ),21,21mmn k nrnkk 1nD 2111mnDD 525432542535321543111111DDDDDDDDDDDDDDDDDDDD(1)D 311D9.4.2 BCH 码的生成多项式码的生成多项式n如果循环码形式的形式为如果循环码形式的形式为v 为纠错个数为纠错个数 ， 为最小多项式，为最小多项式， 为最小公倍数为最小公倍数最小码距最小码距 码长为码长为 的的BCH码称为码称为 本本BCH码（侠义）码（侠义） 码长为码长为 则称为非本原则称为非本原B

27、CH码码1321()LCM(),(),(),tg Dm D m DmD()im DLCMt21mn 21mn 21dtBCH 码码n由于由于g(D)有有t个因式，且每个因式的最高次为个因式，且每个因式的最高次为m，因此监督码元最多有因此监督码元最多有mt位。位。n对于纠对于纠t 个错误的本原个错误的本原BCH码，其生成多项式码，其生成多项式n纠单个错误的本原纠单个错误的本原BCH码字为汉明码。码字为汉明码。u表表11111313给出了给出了 n5n5的本原的本原BCHBCH码。码。 1114给出了部分非本原给出了部分非本原BCH码。码。1321()()()()tg Dm D m DmDBCH

28、码例子码例子n纠正纠正 3 个错误，码长为个错误，码长为15的的BCH码码解：解：n=15, m=5 查表查表11-12得，得，233707 这是这是(15,5)码。码。 13544322108542( )( )( )( )(1)(1)(1)1g Dm D m D m DDDDDDDDDDDDDDD 重要的重要的BCH码码 (23,12)n表表1114中最重要的中最重要的BCH码是码是(23,12)称为格雷码，码间为称为格雷码，码间为7，能纠正，能纠正3个错误。个错误。生成多项式生成多项式n在实际通信系统中，所要求的在实际通信系统中，所要求的n、k并不是码表中所推荐并不是码表中所推荐的值，在这

29、时我们可以采用缩短或扩展的方式加以修正，的值，在这时我们可以采用缩短或扩展的方式加以修正，也就是通过增加信息符号或校验符号来增加码组长度，或也就是通过增加信息符号或校验符号来增加码组长度，或减少信息和校验位来减少码组长度。减少信息和校验位来减少码组长度。119765()1g DDDDDDDBCH码码n如如 BCH码的码长为奇数，而有时需要偶数码长，码的码长为奇数，而有时需要偶数码长，这时可以在原这时可以在原BCH码生成多项式中乘以（码生成多项式中乘以（D+1)因子，从而得到（因子，从而得到（n+1,k）扩展）扩展BCH码，这时相码，这时相当于在原当于在原BCH码上加一个全校验位，从而将码距码上

30、加一个全校验位，从而将码距增加增加1，这时的码字不具有循环性。，这时的码字不具有循环性。n如果如果BCH码不是码不是2m-1或它的因式，这时可以采用或它的因式，这时可以采用缩短的方式，去掉缩短的方式，去掉s位信息，位信息，(n-s , k-s)RS码码 Reed-Solomonn非二进制非二进制BCH码，输入以符号来考虑码，输入以符号来考虑n假定每组有假定每组有 K 个符号，每个符号用个符号，每个符号用m比特，输比特，输入信息将是入信息将是 Km 比特。比特。RS码码nRS码适合于纠正突发错误，纠正的错误图样有码适合于纠正突发错误，纠正的错误图样有n对于一个长度为对于一个长度为 符号的符号的RS码，每个符号码，每个符号都可以看成是有限域都可以看成是有限域 中的一个元素，如中的一个元素，如RS码的最小码距为码的最小码距为d符号，则生成多项式符号，则生成多项式111(1)1(3)13(21)21btmbtmbtimii总长度为比特的单个突发总长度为比特的 个突发总长度为比特的 个突发21m(2 )mGRs231()()()()()dg DDDDD()imGR是中 的 一 个 元 素9.5 纠正和检测突发错误的分组码纠正和检测突发错误的分组码交织码交织码interlea