《通信原理-08差错控制编码.ppt

1、 8.1 差错控制的基本概念差错控制的基本概念 差错控制是对传输差错采取的技术措施，目的是提高传输的可靠性。8.1.1 差错控制的基本思想 差错控制的基本思想是通过对信息序列作某种变换，使原来彼此独立的、没有相关性的信息码元序列，经过某种变换后，产生某种规律性（相关性），从而在接收端有可能根据这种规律性来检查，进而纠正传输序列中的差错。差错控制的核心是抗干扰编码，即差错控制编码，简称纠错编码，也叫信道编码。8.1.2 差错类型 随机差错，又称独立差错，是指错码的出现是随机的，且错码之间是统计独立的。突发差错，是指成串集中出现的错码，即在一些短促的时间区内会出现大量错码，而在这些短促的时间区间之

2、间又存在较长的无错码区间。8.1.3 差错控制方式（1）检错重发（ARQ）（2）前向纠错（FEC）（3）混合纠错检错（HEC）（4）反馈校验8.1.3 差错控制方式（1）检错重发（）检错重发（ARQ）优点优点：检错码构造简单，插入的监督码位不多，：检错码构造简单，插入的监督码位不多，设备不太复杂设备不太复杂缺点缺点：实时性差实时性差 必须有反向信道必须有反向信道 发收检错码应答信号8.1.3 差错控制方式（2）前向纠错（）前向纠错（FEC）优点优点：不需反馈信道：不需反馈信道 实时性好实时性好缺点缺点：要求附加的监督码较多，传输效率低：要求附加的监督码较多，传输效率低 设备复杂设备复杂 发收纠

3、错码8.1.3 差错控制方式 （3）混合纠错检错（）混合纠错检错（HEC）检错重发前向纠错检错重发前向纠错发收纠检错码应答信号8.1.3 差错控制方式（4）反馈校验）反馈校验优点优点：不要纠错、检错的编解码器，设备简单：不要纠错、检错的编解码器，设备简单缺点缺点：需要双向信道需要双向信道 实时性差实时性差 传输效率低传输效率低8.1.4 差错控制编码原理1差错控制编码的基本原理 差错控制的核心是差错控制的核心是差错控制编码差错控制编码，不同的编码方法，有，不同的编码方法，有不同的检错或纠错能力。不同的检错或纠错能力。差错控制编码一般是在用户信息序列后插入一定数量的差错控制编码一般是在用户信息序

4、列后插入一定数量的新码元，这些新插入的码元称为新码元，这些新插入的码元称为监督码元监督码元。它们不受用户的。它们不受用户的控制，最终也不送给接收用户，只是系统在传输过程中为了控制，最终也不送给接收用户，只是系统在传输过程中为了减少传输差错而采用的一种处理过程。减少传输差错而采用的一种处理过程。如果信道的传输速率一定，加入差错控制编码，就降低如果信道的传输速率一定，加入差错控制编码，就降低了用户输入的信息速率，了用户输入的信息速率，新加入的码元越多，冗余度越大，新加入的码元越多，冗余度越大，检错纠错越强，但效率越低。检错纠错越强，但效率越低。由此可见，由此可见，通过差错控制编码通过差错控制编码提

5、高传输的可靠性是以牺牲传输效率为代价换取的提高传输的可靠性是以牺牲传输效率为代价换取的。8.1.4 差错控制编码原理1差错控制编码的基本原理举例举例1 1通知：通知：“明天明天1414：00001616：0000开会开会”通知后变成：通知后变成：“明天明天1010：00001616：0000开会开会”“明天明天下午下午1414：00001616：0000开会开会”“明天明天下午下午1414：00001616：0000两个小时两个小时开会开会”8.1.4 差错控制编码原理1差错控制编码的基本原理（1）如果要传送A和B两个信息，可以用1位二进制编码表示，例如用“0”码表示信息A，用“1”码表示信息

6、B。（2）如果分别在“0”和“1”后面附加一个“0”和“1”，变为“00”和“11”，还是传送A和B两个信息，即“00”表示A，“11”表示B。（3）若在信息码之后附加两位监督码，即用“000”表示A，“111”表示B。如用如用1位二进制编码来代表两个消息位二进制编码来代表两个消息A，B0 A 1 B传输产生错码，不能检错和纠错传输产生错码，不能检错和纠错如用如用2位二进制编码代表两个消息位二进制编码代表两个消息A，B00 A 11B 发生一位错误，许用码字将变成禁用码字，接收端发生一位错误，许用码字将变成禁用码字，接收端就能知道出错，但是不能纠错。就能知道出错，但是不能纠错。如用如用3 3位

7、二进制编码代表位二进制编码代表两个消息两个消息A，B0 00000 A 1 11111 B检二个错误，纠正一个错误。检二个错误，纠正一个错误。举例举例28.1.4 差错控制编码原理1差错控制编码的基本原理表8-1 差错控制编码原理举例编码方法编码方法信息信息检、纠错能力检、纠错能力AB1位编码方法位编码方法01无检、纠错能力无检、纠错能力2位编码方法位编码方法0011检错检错1位，不能纠错位，不能纠错3位编码方法位编码方法000111检错检错2位，纠错位，纠错1位位 编码效率 其中，k为信息码元的数目 n为编码后码组的总数目（n=k+r，r为监督码元的数目）。R越大，编码效率越高，它是衡量编码

8、性能的一个重要参数。nrnnkR8.1.4 差错控制编码原理1差错控制编码的基本原理8.1.4 差错控制编码原理2码重和码距的概念（1）码重 在信道编码中，定义码组中非零码元的数目为码组的重量，简称码重。（2）码距与汉明距离 把两个码组中对应码位上具有不同二进制码元的个数定义为两码组的距离，简称码距。而在一种编码中，任意两个许用码组间的距离的最小值，称为这一编码的汉明（Hamming）距离，用dmin来表示。码字11010例如：码重=3码字11010和10100码距=3 1010011010=01110两个码字的模二相加得到的新码字的码重就是这两个码字之间的汉明距离。码字集合 000 011

9、101 110汉明距离dmin=28.1.4 差错控制编码原理3汉明距离与检错和纠错能力的关系 把3位码元构成的8个码组用一个三维立方体来表示。图中立方体的各顶点分别为8个码组，每个码组的3位码元的值就是此立方体各顶点的坐标。由图中可以看出，码距对应于各顶点之间沿立方体各边行走的几何距离（最少边数）。3、汉明码距与纠检错能力的关系 纠错码的纠检错能力完全取决于许用码字之间的距离，最小码距越大，纠检错能力就越强。(1)检测错误时，如果要检测e个错误，则 d0 e+1；(2)纠正错误时，如果要纠正t个错误，则 d0 2t+1；(3)纠t个错误，同时检e个错误时(et)，则d0 t+e+1。eBAd

10、0tAtB1tAeB1(a)(b)(c)d0d08.1.5 差错控制编码的分类（1）按码组的功能分，有）按码组的功能分，有检错码检错码和和纠错码纠错码两类。两类。（2）按码组中监督码元与信息码元之间的关系分，有）按码组中监督码元与信息码元之间的关系分，有线性线性码码和和非线性码非线性码两类。两类。（3）按照信息码元与监督码元的约束关系，又可分为）按照信息码元与监督码元的约束关系，又可分为分组分组码码和和卷积码卷积码两类。两类。（4）按照信息码元在编码前后是否保持原来的形式不变，）按照信息码元在编码前后是否保持原来的形式不变，可划分为可划分为系统码系统码和和非系统码非系统码。（5）按纠正差错的类

11、型可分为）按纠正差错的类型可分为纠正随机错误的码纠正随机错误的码和和纠正突纠正突发错误的码发错误的码。（6）按照每个码元取值来分，可分为）按照每个码元取值来分，可分为二进制码二进制码与与多进制码多进制码。8.2 简单的差错控制编码简单的差错控制编码 1奇偶校验码 奇偶校验码分为奇偶校验码分为奇校验码奇校验码和和偶校验码偶校验码，其编码规则是先，其编码规则是先将所要传输的数据码元（信息码）分组，在分组信息码元将所要传输的数据码元（信息码）分组，在分组信息码元后面后面附加附加1 1位监督位位监督位，使得该码组中信息码和监督码合在一，使得该码组中信息码和监督码合在一起起“1”的个数为偶数（偶监督）或

12、奇数（奇监督）。的个数为偶数（偶监督）或奇数（奇监督）。消息消息信息位信息位监督位监督位消息消息信息位信息位 监督位监督位晴晴0 00阴阴1 01云云0 11雨雨1 10表表8-2 奇奇偶偶校验码校验码1 0 1 0 0 1 1 0 不能确定不能确定1 0 1 0 0 0 1 0 有错有错1 0 1 1 0 0 1 0信息码元监督码元111010110100练习练习 0010在偶校验时，有在奇校验时，有 奇偶校验码只能发现单个或奇数个错误，而不能检测出偶数个错误，奇偶校验码的最小码距为2，所以没有纠错能力。00121aaaann10121aaaann2水平奇偶校验码 它的构成思路是：将信息码序

13、列按行排成方阵，它的构成思路是：将信息码序列按行排成方阵，每行后面加一个奇或偶校验码，即每行后面加一个奇或偶校验码，即每行为一个奇偶每行为一个奇偶校验码组，校验码组，但发送时按方阵中但发送时按方阵中列的顺序进行传输列的顺序进行传输，到了接收端仍将码元排成与发送端一样的方阵形式，到了接收端仍将码元排成与发送端一样的方阵形式，然后按行进行奇偶校验。由于这种差错控制编码是然后按行进行奇偶校验。由于这种差错控制编码是按行进行奇偶校验，因此称为水平奇偶校验码。按行进行奇偶校验，因此称为水平奇偶校验码。表表8-3 水平奇偶校验码水平奇偶校验码 信息码元信息码元监督码元监督码元111001100011101

14、0011010100001110110001000010011001110111 水平奇偶校验码可以发现某一行上水平奇偶校验码可以发现某一行上奇数个错误奇数个错误，以及所有长度不大于方阵中行数的以及所有长度不大于方阵中行数的突发错误突发错误，但仍，但仍没没有纠错能力有纠错能力。11101 11001 10000 010103二维奇偶校验码 二维奇偶校验码是将水平奇偶校验码改进而得，二维奇偶校验码是将水平奇偶校验码改进而得，又称为水平垂直奇偶校验码。它的编码方法是在水又称为水平垂直奇偶校验码。它的编码方法是在水平校验基础上对方阵中每一列再进行奇偶校验，发平校验基础上对方阵中每一列再进行奇偶校验，

15、发送时按行或列的顺序传输。到了接收端重新将码元送时按行或列的顺序传输。到了接收端重新将码元排成发送时方阵形式，然后排成发送时方阵形式，然后每行、每列都进行奇偶每行、每列都进行奇偶校验校验。表表8-4 二维奇偶校验码二维奇偶校验码信息码元信息码元监督监督码元码元1110011000111010011010100001110110001000010011001110111监督码元监督码元01101100001 信息码元信息码元 监督码元监督码元 信息码元信息码元 监督码元监督码元 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 1 1 0 1 0 1 1 0 1 0 0

16、 1 0 0 0 1 0 0 1 1 1 0 1 1 0 0 1 1 1 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1监督码元监督码元 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1（1）这种码比水平奇偶校验码有更强的检错能力。它能发）这种码比水平奇偶校验码有更强的检错能力。它能发现某行或某列上现某行或某列上奇数个错误奇数个错误和和长度不大于方阵中行数（或长度不大于方阵中行数（或列数）的突发错误列数）的突发错误。（2）这种码还有可能检测出一部分）这种码还有可能检测出一部分偶数个错误偶数个错误。当然

17、，若。当然，若偶数个错误恰好分布在矩阵的偶数个错误恰好分布在矩阵的4个顶点上时，这样的偶数个顶点上时，这样的偶数个错误是检测不出来的。个错误是检测不出来的。（3）这种码还可以）这种码还可以纠正一些错误纠正一些错误，例如，某行某列均不满，例如，某行某列均不满足监督关系而判定该行该列交叉位置的码元有错，从而纠足监督关系而判定该行该列交叉位置的码元有错，从而纠正这一位上的错误。正这一位上的错误。8.3 线性分组码和汉明码线性分组码和汉明码8.3.1 线性分组码 （1）线性分组码的基本概念 线性码线性码：监督码元与信息码元之间的关系可以 用线性方程表示分组码分组码：监督码元仅与本组中的信息码元有关 线

18、性分组码线性分组码：将信息序列分为每k位一组的信息序列段，每个信息序列段按照一定的规律添加r个监督码元，构成总码长为（nk+r）的分组码，记为（n，k）。（2）线性分组码的监督矩阵H和生成矩阵G 例：（7，4）线性分组码346035614562cccccccccccc0123456cccccccC 信息码元信息码元 监督码元监督码元表表8-5 （7，4）线性分组码的编码表）线性分组码的编码表信息位信息位监督位监督位信息位信息位监督位监督位c6 c5 c4 c3c2 c1 c0c6 c5 c4 c3c2 c1 c00 0 0 00 0 01 0 0 01 1 10 0 0 10 1 11 0 0

19、 11 0 00 0 1 01 0 11 0 1 00 1 00 0 1 11 1 01 0 1 10 0 10 1 0 01 1 01 1 0 00 0 10 1 0 11 0 11 1 0 10 1 00 1 1 00 1 11 1 1 01 0 00 1 1 10 0 01 1 1 11 1 1（2）线性分组码的监督矩阵和生成矩阵监督方程组可以改写为000034613562456cccccccccccc进一步，写成矩阵形式为0001001101010101100101110123456ccccccc（2）线性分组码的监督矩阵和生成矩阵000100110101010110010111012

20、34560CHccccccc若令0CH0HCTTT或则有（2）线性分组码的监督矩阵和生成矩阵监督矩阵H可以分成两部分 rkrIPH100010001110110110111某系统（某系统（8，4）码，其）码，其4位校验位位校验位vi，i0，1，2，3与与4位信息位位信息位ui，i0，1，2，3的关系是的关系是求：该码的生成矩阵和监督矩阵，对信息码求：该码的生成矩阵和监督矩阵，对信息码（1100）进行编码。）进行编码。1230012101320233uuuvuuuvuuuvuuuv练习练习346035614562cccccccccccc（2）线性分组码的监督矩阵和生成矩阵345601211011

21、0110111ccccccc改写成矩阵形式 QccccPcccccccccccT345634563456012110101011111Q 信息码监督码1101000101010001100101110001QIGk（2）线性分组码的监督矩阵和生成矩阵GC 信息码生成矩阵GQIGPQIPHkTr已知（7,3）线性分组码的生成矩阵为求：（1）所有的码字。（2）监督矩阵H。（3）最小码距及纠、检错能力。（4）编码效率。001110101011101000111G 已知汉明码的监督矩阵为求：（1）n和k是多少？（2）编码效率是多少？（3）生成矩阵G。（4）若信息位全为“1”，求监督码元。（5）校验01

22、00110和0000011是否为许用码字，若有错，请纠正。00010011010101011001011101234560CHccccccc【例8.3.1】某（7，4）线性分组码，监督方程如下，求监督矩阵H和生成矩阵G。如信息码为0010，求整个码组C。345034613562cccccccccccc（3）线性分组码的检错和纠错发送码组C在传输过程中可能发生误码，设接收到码组为021rrrnnR则收发码组之差（模2）为021eeeCRnnCRE1,2,110nicrcreiiiii当当差错图案差错图案1、已知C=1001110,R=1001100,则E=？2、已知C=1001110,E=010

23、0000,则R=？3、已知R=1000110,E=0000001,则C=？E=0000010R=1101110C=1000111（3）线性分组码的检错和纠错ECECRTTTTEHCHHECRHS)(由于0CHT所以00EHSTS称为接收码组R的校正子，也称为伴随式。R为正确码字R为出错码字1行行r列列1、求出错误图样E与伴随式S之间的关系2、计算接收码字的伴随式S，然后查表得错误图样E3、用错误图样E纠正接收码字中的错误译码步骤译码步骤E RCTTHEHS R已知汉明码监督矩阵H：试求（1）对信息码元1101编码。（2）验证0111011是否有错。若错，试改正。1001110010011100

24、11011H（4）线性分组码的主要性质 封闭性 码的最小距离等于非零码的最小重量 监督关系 监督码元共同监督所有信息码元及监督码元A1HT+A2HT=（A1+A2）HT=0 已知某（n，k）线性分组码的生成矩阵为（1）求监督矩阵H，确定n，k。（2）写出监督位的关系式及该（n，k）的所有码字。（3）确定最小码距。011010101001110100G8.3.2 汉明码 汉明码是一种能够纠正一位错码且编码效率较高的线性分组码。rknrr12,12,汉明码：（7,4）（15,11）（31,26）（63,57）【例8.3.2】已知某汉明码的监督矩阵H：试求：（1）n，k，编码效率分别是多少？（2）验

25、证1111001和0100010是否有错，若有错，请纠正之。（3）若信息码元为1001，写出其对应的汉明码组。rIPH1000111010111000111018.4 循环码循环码8.4.1 循环码的特性 循环码是一种线性分组码，它除了具有线性分组码的封闭性之外，还具有循环性。循环性是指循环码中任一许用码组经过循环移位后（左移或右移）所得到的码组仍为该码中一个许用码组。码组编号信息位监督位码组编号信息位监督位c6 c5 c4c3 c2 c1 c0c6 c5 c4c3 c2 c1 c010 0 00 0 0 051 0 01 0 1 120 0 10 1 1 161 0 11 1 0 030 1

26、 01 1 1 071 1 00 1 0 140 1 11 0 0 181 1 10 0 1 0表8-7 （7，3）循环码的一种码组00000000010111100101111001011110010 01011101011100 0111001右移左移0010111010111010111000111001 10010111100101 11100108.4.2 循环码的码多项式若一个码组C=（cn-1，cn-2，c1，c0），则用相应的多项式表示为012211)(cxcxcxcxCnnnn称C（x）为码组C的码多项式码多项式。例如：1 0 1 1 1 x4+x2+x+1 C1(x)=x6

27、+x3+x2+x C2(x)=x4+x3+x2+1则 C1(x)+C2(x)=?1011 x3+x+1 C1(x)=x6+x3+x2+x 1001110 C2(x)=x4+x3+x2+1 0011101 C1(x)+C2(x)=x6+x4+x+1 10100118.4.3 码多项式的按模运算若一整数m可以表示为 npQnm（pn）则 pm（模n）在多项式中同样可以进行类似的按模运算，如：)()()()()(xGxRxMxGxA)()()()(xRxGxMxA上式可写为：所以)()(xRxA（模G（x）)1(1111133333xxxxx模1111333xxx)1(111111322432324

28、xxxxxxxxxxxx模11124243xxxxxxxx例如：8.4.4 循环码的生成多项式和生成矩阵（1）循环码的生成多项式之所以第k位码元和第n位（最后一位）码元必须为“1”，是因为：在（n，k）循环码中，除全“0”码组外，连连“0”的长度最多的长度最多只能有只能有k-1位位。否则，在经过若干次循环移位后，将得到一个k位信息位全为“0”，但监督码位不全为“0”的码组，这在线性码中显然是不可能的（信息位全为“0”，督码位也必定全为“0”）；若第n位（最后一位）码元不为“1”，该码组（前k-1位码元均为“0”）循环右移后，将成为前k位信息位都是“0”，而后面（n-k）位监督位不都为“0”的码

29、组，这是不允许的。110001211gggknk（1）循环码的生成多项式1)(111xgxgxxgknknkng（x）具有唯一性唯一性；生成多项式g（x），其最高幂次为xn-k次。【例8.4.1】求表8-7所示的（7，3）循环码的生成多项式。1)(24xxxxg（2）循环码的生成矩阵生成矩阵G（x）为：)()()()()()(22-1-xgxxgxgxxgxxgxxGkk典型的生成矩阵为：QIGk1)(24xxxxg111010001110100011101)()()()(2345623456234562xxxxxxxxxxxxxxxxxxxgxxgxgxxG例如表8-7中（7，3）循环码 1

30、11010001110100011101G111010001110101101001G典型的生成矩阵G（3）生成多项式g（x）的另一种求法 xhxxgxkn1上式表明，生成多项式生成多项式g（x）必定是（）必定是（xn+1）的一个（）的一个（n-k）次因式）次因式 11113237xxxxxx（7，3）循环码的生成多项式g（x）有两个：1112423xxxxxx1112343xxxxxx8.4.5 循环码的编码方法012211)(mxmxmxmxmkkkk信息位对应的码多项式为 xn-km（x）的前一部分为连续k位信息码（mk-1，mk-2，m0），后一部分为n-k位的“0”，n-k=r正好是

31、监督码的位数。所以在它的后一部分添上监督码，就编出了相应的系统码系统码。)()()()()(-xgxrxqxgxmxknC（x）=h（x）g（x）)()()()(xgxqxrxmxkn编码步骤可归纳如下：（1）用xn-k乘以信息码多项式m（x），得到xn-km（x）。（2）用g（x）除xn-km（x），得到商q（x）和余式r（x）即（3）求多项式C（x）=xn-km（x）+r（x）。【例8.4.2】已知一种（7，3）循环码，生成多项式为g（x）=x4+x3+x2+1，求信息码为111时，编出的循环码组。【例8.4.3】已知信息码为1101，生成多项式G（x）=x3+x+1，编一个（7，4）循环

32、码。【例8.4.4】使用生成多项式g（x）=x4+x3+1产生m（x）=x7+x6+x5+x2+x对应的循环码组。8.4.6 循环码的解码方法（1）检错的实现)()(+)(=)()(xgxrxqxgxR以余项是否为零余项是否为零来判别码组中有无错码。0，无错0，有错（2）纠错的实现 用生成多项式g（x）除接收码组R（x）=C（x）+E（x）（模2加），得到余式；按余式用查表的方法或通过某种运算得到错误图样E（x）；从R（x）中减去E（x）（模2加），得到纠错后的原发送码组C（x）。8.4.7 循环冗余校验码（CRC）在数据通信中，广泛采用循环冗余校验（Cyclic Redundancy Che

33、ck，CRC），CRC码采用了循环码的多项式除法生成监督位的方法。在常用的CRC生成器协议中采用的标准生成多项式如表8-9所示，码生成多项式CRC-12x12+x11+x3+x2+x+1CRC-16x16+x15+x2+1CRC-ITUx16+x12+x5+1CRC-32x 32+x26+x23+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1表8-9 常用的CRC码1、已知（、已知（7，3）循环码的生成多项式是）循环码的生成多项式是g（x）=x4+x2+x+1，对信息码，对信息码011进行编码。进行编码。2、已知（、已知（10，6）循环码，生成多项式是）循环码，生成多项式是g（x）=x4+x+1，求信息码，求信息码110001对应的码字。对应的码字。练习练习