第十章-差错控制编码学习教案

1、会计学1第十章第十章-差错控制编码差错控制编码(bin m)第一页，共67页。2022-4-14210.1 差错控制编码(bin m)的基本原理发生误码原因：系统特性不理想（乘性干扰），数字信号通过系统时 产生(chnshng)波形失真，在接收端判决时会产生(chnshng)判决错误。信道中的噪声（加性干扰），这种干扰随机地与信号 叠加，使信号波形产生(chnshng)失真，引起判决错误。 解决办法：（1）适当增加发送信号功率。 (2) 选择抗噪声性能好的调制解调方式。 (3) 采用(ciyng)最佳接收 。（4）采用(ciyng)差错控制编码。 第1页/共67页第二页，共67页。2022-4

2、-14310.1 差错控制编码(bin m)的基本原理信源编码目的：提高通信系统(xtng)的有效性。差错控制编码（信道编码、抗干扰编码或纠错编码）目的：提高通信的可靠性。 差错控制编码方法：通过人为地加入多余度，使信 号在一定的干扰条件(tiojin)下，具有 检测或纠正错码的能力。第2页/共67页第三页，共67页。2022-4-14410.1 差错控制编码(bin m)的基本原理信道分类：随机(su j)信道、突发信道、混合信道。 （1 ） 随机信道：错码出现互不相关、统计独立。 如：高斯白噪声引起的错码。（2）突发信道：错码的出现前后相关。错码出现时， 在短时间内有一连串的错码，而该时间

3、过后又 有较长的时间无错码。如：随机的强突发脉冲 干扰引起的错码。（3）混合(hnh)信道：产生的错码既有随机错码又有突发 错码。第3页/共67页第四页，共67页。2022-4-14510.1 差错控制编码(bin m)的基本原理常用(chn yn)的差错控制方式1. ARQ(Automatic Repeat Request)方式(自动(zdng)请求重发或检错重发) 发端发送出可以发现错误的码字。经过传输到接收端译码后，如果没有发现错误，则输出。如果发现错误，则自动请求发端重发，直到正确接收到码字为止。第4页/共67页第五页，共67页。2022-4-14610.1 差错控制编码(bin m)

4、的基本原理ARQ系统(xtng)组成特点：设备简单(jindn)、双向信道、传输效率低。第5页/共67页第六页，共67页。2022-4-14710.1 差错控制编码(bin m)的基本原理2.反馈(fnku)校验方式 接收端收到码字后，立即将接收到的码字返回发送端。发送端将返回的码字与发端缓冲存储器中相应的码字比较，若发现与发送码不同，即认为(rnwi)产生了错误，就重发上一次的码字。 特点：设备简单、双向信道、传输效率低。第6页/共67页第七页，共67页。2022-4-14810.1 差错控制编码(bin m)的基本原理 发送端发出的码字不仅能够发现错误，而且(r qi)能够纠正错误。在接收

5、端译码后，若没有错误则直接输出。若有错误，则在接收端自动纠正后，再输出。 特点：不需要反向信道、实时性好、传输效率高。 但纠错编译码方法复杂。第7页/共67页第八页，共67页。2022-4-14910.1 差错控制编码(bin m)的基本原理 将ARQ方式和前向纠错方式结合使用。传输错码较少时，采用前向纠错方式，自动(zdng)纠正错码。在错码较多时，采用ARQ方式自动(zdng)请求重发。 4.HEC（Hybrid Error Control,混合纠错(ji cu)）方式第8页/共67页第九页，共67页。2022-4-141010.1 差错控制编码(bin m)的基本原理 在有扰信道中只要信

6、息的传输速率R小于信道容量C，总可以找一种编码方法，使信息以任意(rny)小的差错概率通过信道传送到接收端，即误码率Pe可以任意(rny)小，而且传输速率R可以接近信道容量C。但若R C，在传输过程中必定带来不可纠正错误，不存在使差错概率任意(rny)小的编码。 香农有扰信道编码定理(dngl)： 香农有扰信道的编码定理本身并未给出具体的纠错编码方法，但它为信道编码奠定了理论基础。从理论上指出了信道编码的发展方向。第9页/共67页第十页，共67页。2022-4-141110.1 差错控制编码(bin m)的基本原理误码率： 式中，n为编码的码字长度(chngd)(简称码长)； E(R)为误码指

7、数。第10页/共67页第十一页，共67页。2022-4-141210.1 差错控制编码(bin m)的基本原理减小误码率Pe的两种途径(tjng)：（2）在C及 R一定的情况(qngkung)下，增加n可以使Pe指数减小。（1）n 及 R一定时，增加信道容量C。由图可见，E(R) 随C的增加而增大。由信道容量公式知， 增加C， 可通过增加S和B来实现；第11页/共67页第十二页，共67页。2022-4-141310.1 差错控制编码(bin m)的基本原理重复编码的例子：天气预报消息(xio xi)发布晴 雨 纠检错能力(nngl) 第一种编码方法许用码、禁用码、最大似然准则纠检错能力 第二种

8、编码方法可检1位错（01、10）、纠错能力 第三种编码方法可检2位错、纠1位错（001、010、100 000 011、101、110 111 ）第12页/共67页第十三页，共67页。2022-4-141410.1 差错控制编码(bin m)的基本原理码间距离d 及检错纠错(ji cu)能力码字：由信息位和监督(jind)位组成的一组码元。 用C = ( cn-1 cn-2 c0 )表示。 码元： 组成码字的元素，用Ci表示。码长：码字中码元的个数，用n表示。（许用码、禁用码）码组：由多个许用码组成的一组码字。 第13页/共67页第十四页，共67页。2022-4-1415码间距离(jl)d（c

9、ode distances）10,()nijipjppd c ccc10.1 差错控制编码(bin m)的基本原理第14页/共67页第十五页，共67页。2022-4-1416码间距离的几何(j h)意义10.1 差错控制编码(bin m)的基本原理最小码间距离(jl)d0：码组中各码字之间最小的码距。第15页/共67页第十六页，共67页。2022-4-141710.1 差错控制编码(bin m)的基本原理最小码间距离(jl)d0与检错纠错能力的关系第16页/共67页第十七页，共67页。2022-4-141810.1 差错控制编码(bin m)的基本原理第17页/共67页第十八页，共67页。20

10、22-4-141910.1 差错控制编码(bin m)的基本原理第18页/共67页第十九页，共67页。2022-4-1420差错控制编码(bin m)的效果 在码长为n的码字中刚好发生(fshng)r个错误的概率为： 1n rrrnnP rC PP10.1 差错控制编码(bin m)的基本原理P7(1)710-3 P7(2)2.110-5 P7(3)3.510-8当n =7，P=10-3 时，有：第19页/共67页第二十页，共67页。2022-4-1421纠错(ji cu)编码的分类 10.1 差错控制编码(bin m)的基本原理第20页/共67页第二十一页，共67页。2022-4-14221

11、0.1 差错控制编码(bin m)的基本原理knrnn编码(bin m)效率K：码字的信息(xnx)码元个数r：监督码元个数n: 码元总的个数（总码长）nkr第21页/共67页第二十二页，共67页。2022-4-142310.2常用的简单(jindn)编码1.奇偶(q u)监督码2.二维奇偶(q u)监督码3.恒比码（等重码）第22页/共67页第二十三页，共67页。2022-4-142410.2常用(chn yn)的简单编码广泛应用于计算机数据传输中。偶监督(jind)码：给信息位后增加一位监督(jind)位，使码字中“1” 的数目为偶数。编码规则：在每个分组的信息位后增加监督位，无论 信息位

12、有多少(dusho)位，监督位只有一位。上式为偶监督码的监督关系，也称为校验方程。检测能力：检测奇数个错。12100nnCCCC1.奇偶监督码（奇偶校验码）第23页/共67页第二十四页，共67页。2022-4-142510.2常用的简单(jindn)编码奇监督码：给信息位后增加一位监督位，使码字 中“1”的数目(shm)为奇数。其校验方程为 奇偶监督码的编码效率较高，尤其是当码长 n 较大时这一特点更为明显。121010nnCCCC 第24页/共67页第二十五页，共67页。2022-4-142610.2常用的简单(jindn)编码2.二维奇偶(q u)监督码（方阵码、行列监督码或水平垂直奇偶(

13、q u)监督码）编码方法：把m 个信息码字排列成一个方阵，每个码字构成方阵的一行，在每一行的最后按奇偶(q u)监督规则增加一位水平监督位，再按列的方向每列增加一位垂直监督位（包括行监督位的列）第25页/共67页第二十六页，共67页。2022-4-1427可以检测每行的奇数个错和每列的奇数个错；行列交叉可以检测每行或每列的偶数个错；但 当发生的错误为刚好(gngho)构成矩形的四个错码时， 则不能检测出错误。检测(jin c)能力：10.2常用(chn yn)的简单编码 只有一行出现奇数个错码时，按行检测可以判断出错在那一行，按列检测可以确定该行的那一列发生了错误，行列交叉可以判断错误的位置，

14、即可纠错。此外，此种编码的效率较高。纠错能力：第26页/共67页第二十七页，共67页。2022-4-14283.恒比码（等重码(zhn m)） 每个许用码含有相同数目的“1”。码字中“1”与“0”的个数之比是恒定的，故称恒比码。码字中“1”的个数称为(chn wi)码重，因此恒比码又称等重码。 对于某种特定(tdng)的恒比码，当码长确定后，其“1”的个数就确定了。所以在检测中只要计算“1”的个数就可以确定是否发生错误。恒比码多用于电传机中。 我国电传机传输汉字采用的是“5中取3” 恒比码，其码长为5，码字中“1”的个数为3。这种码我国称为保护电码。码长为5的二进制数共有32种组合，选择其中含

15、有3个“1”的组合作为许用码，为10个。10.2常用的简单编码第27页/共67页第二十八页，共67页。2022-4-1429 我国的保护电码(dinm)与国际电码(dinm)阿拉伯阿拉伯数字数字保护电保护电码码国际电国际电码码阿拉伯阿拉伯数字数字保护电保护电码码国际电国际电码码00110101101500111000011010111110161010110101211001110017111001110031011010000801110011004110100101091001100011 10.2常用(chn yn)的简单编码第28页/共67页第二十九页，共67页。2022-4-1430

16、10.3 线性分组码一、线性分组码概念(ginin) 线性分组码是指信息位和监督(jind)位满足一组线性方程，即其编码规则可用一组线性方程来描述的分组码。信息(xnx)位k信息位k 监督位r记为（n, k）nkrn: 码元总的个数（总码长）第29页/共67页第三十页，共67页。2022-4-143110.3 线性分组码系统码：码字的前一部分是连续k 位信息码元，后一部 分是连续r 位监督码元，具有这种结构的线性 分组码称为(chn wi)系统码。否则称为(chn wi)非系统码。 纠错(ji cu)原理n 位长的二进制码共有(n yu) 码字。2nk 位长的二进制码共有 码字, 故 个信息段

17、仅构成 个n 位长的码字，称为许用码字而其他 个码字为禁用码字，当出现禁用码字时就可以发现或纠正错误。2k2k2k22nk第30页/共67页第三十一页，共67页。2022-4-143210.3 线性分组码二、线性分组码的一致检验(jinyn)（监督矩阵）矩阵HH矩阵是用来(yn li)说明监督码元与信息码元之间关系的矩阵。以（7，3）码 ( k=3, r =4, n =7) 为例：码字矢量(shling) C= c6c5c4c3c2c1c0 信息码元： c6c5c4 监督码元 ：c3c2c1c0监督方程为：3642654165054ccccccccccccc64365426515400000c

18、cccccccccccc第31页/共67页第三十二页，共67页。2022-4-143310.3 线性分组码65432101 0 1 1 0 0 001 1 1 0 1 0 001 1 0 0 0 1 000 1 1 0 0 0 10ccccccc 4 7 ()rn7 14 3 ()Pr k444()Irr将上方程(fngchng)系数写为矩阵形式第32页/共67页第三十三页，共67页。2022-4-143410.3 线性分组码1 0 1 1 0 0 01 1 1 0 1 0 01 1 0 0 0 1 00 1 1 0 0 0 1令 H=称H为线性分组码的一致检验(jinyn)矩阵（监督矩阵）。

19、H=P I4 0TTHC 0TCH第33页/共67页第三十四页，共67页。2022-4-143510.3 线性分组码（1）H是 阶矩阵，即行数为监督码元个数， 列数为码长。 H中每行元素(yun s)表明监督方程 中线性相关的码元系数。故若H已知，则码 元之间的监督关系唯一确定。()rn（2）H=P I4，即H由两部分组成，前半部称 为P矩阵 ，后 半部称为(chn wi)I矩阵 。 此时，称 H为典型矩阵，只有系统码才具有。()rk()rr（3）H是接收端检错的依据。 0TRH第34页/共67页第三十五页，共67页。2022-4-143610.3 线性分组码三、线性分组码的生成(shn ch

20、n)矩阵GG矩阵是在给定信息位的条件下，如何(rh)生成码字的矩阵。仍以（7，3）码 ( k=3, r =4, n =7) 为例：码字矢量(shling) C= c6c5c4c3c2c1c0 信息码元： c6c5c4 ；监督码元 ：c3c2c1c0在监督方程基础上，加上信息码元方程。3642654165054ccccccccccccc监督方程第35页/共67页第三十六页，共67页。2022-4-143710.3 线性分组码3642654165054ccccccccccccc6655443642654165054ccccccccccccccccccc 6541 0 00 1 00 0 11 0

21、11 1 11 1 00 11TccCc 第36页/共67页第三十七页，共67页。2022-4-143810.3 线性分组码 6541 0 00 1 00 0 11 0 11 1 11 1 00 11TccCc 6 5 41 0 0 1 11 00 1 0 0 11 10 0 1 1 10 1c c cC生成(shn chn)矩阵G码字矩阵(j zhn) 6 5 4c c cGC第37页/共67页第三十八页，共67页。2022-4-143910.3 线性分组码 1 0 0 1 11 00 1 0 0 11 10 0 1 1 10 1kGIQ生成(shn chn)矩阵3 7 ()kn3 3 ()

22、kIk k3 4 ()Qk r第38页/共67页第三十九页，共67页。2022-4-144010.3 线性分组码（1）G是 阶矩阵，即行数为信息码元个数， 列数为码长。 故若G给定，则在已知信息码 元的情况(qngkung)下，就可得到码字（生成矩阵）。()kn（2）G=IK Q为标准生成矩阵，G中每行是互相(h xing) 独立的（线性不相关）。实际上，G中每行就是 一个许用码字。推论：由K互相独立的码字可构成生成矩阵。第39页/共67页第四十页，共67页。2022-4-144110.3 线性分组码（3）G与H的 关系(gun x)G=IK QH=P Ir TQP TPQ 1 0 11 1

23、11 1 00 1 1P 1 1 1 00 1 1 11 1 0 1Q第40页/共67页第四十一页，共67页。2022-4-144210.3 线性分组码（4）对偶(du u)码将一码组（A）中的H当作(dn zu)另一码组（B）中的G，或反之，则称B为A的对偶码。 7,37,4HG 7,37,4GH则（7，4）为（7，3）的对偶码。（5）封闭性 线性分组码组中，任意两个码字之和仍是此码组中的一个码字。第41页/共67页第四十二页，共67页。2022-4-144310.3 线性分组码四、线性分组码的译码及伴随(bn su)式1.译码译码是判断(pndun)接收码字是否为许用码，即根据 0TCH判

24、断接收码字 是否(sh fu)满足 120,nnRrrr 0TRH定义 为错误图样， ECR 0E 当 时，无误码。第42页/共67页第四十三页，共67页。2022-4-144410.3 线性分组码 110, ,nEee e当 时，认为(rnwi)第i 位发生了误码。1ie RCE 0TRH将 代入 中，得： 1TTTrCHEHEHS称 为伴随(bn su)式，又称校验子。 110, ,rSss s 10,0nE 10,0rS当 时， 无错误(cuw)出现。第43页/共67页第四十四页，共67页。2022-4-144510.3 线性分组码21r当 时，认为(rnwi)第i 位发生了误码。1ie

25、 由 伴随(bn su)式可检测 个错误。 110, ,rSss s此时(c sh)， 为 中的第i列（从右起），故可用 的列来表示误码位置。H 1TrSEHH第44页/共67页第四十五页，共67页。2022-4-144610.3 线性分组码21r当 时，认为(rnwi)第i 位发生了误码。1ie 由 伴随式可检测(jin c) 个错误。 110, ,rSss s要纠正小于或等于(dngy)t 个错，必须满足此时， 为 中的第i列（从右起），故可用 的列来表示误码位置。H 1TrSEHH1221rtnnnCCC 02triniC或第45页/共67页第四十六页，共67页。2022-4-14471

26、0.3 线性分组码编码(bin m)效率 汉明码是一种可以(ky)纠正单个随机错误的线性分组码。它是一种完备码，编码效率很高。汉明码21rn ,21 , 21rrn kr 21112121rrrknrrrrnnn第46页/共67页第四十七页，共67页。2022-4-144810.3 线性分组码例：7 ,21 127,120127,120rrnknr 457%7kn3,217,47, 4rrnknr 12094%127kn第47页/共67页第四十八页，共67页。2022-4-144910.3 线性分组码（4）编码(bin m)效率高。 （1）汉明码长汉明码特点(tdin)21,3rnr（2）信息

27、(xnx)位21rknrr （3）最小码距 ，纠错能力为 。03d 1t n第48页/共67页第四十九页，共67页。2022-4-145010.4 循环码一、 循环码的基本概念及码多项式定义(dngy)：具有循环性的线性分组码。循环(xnhun)性：码组中任一许用码字（全“0”码除外）循环(xnhun)左移 （或循环(xnhun)右移）后所得到的码字仍为该循环(xnhun)码组 中的另一许用码字。 1210,nnCccc c121023010121,nnnnnnccc cccc cc cc c第49页/共67页第五十页，共67页。2022-4-145110.4 循环码一种(y zhn)（7，3

28、）循环码序序号号移移位位次次数数信信 息息 位位监监 督督 位位序序号号移移位位次次数数信信 息息 位位监监 督督 位位000000004610011101 10 000111015410100112 25 501001116311010013 31 10111010721110100第50页/共67页第五十一页，共67页。2022-4-145210.4 循环码码多项式：把循环码中的码字用多项式来表示(biosh)，码字中各 码元的取值作为码多项式的系数。 1210,nnCccc c 121210nnnnT xcxcxc x c 6321001110T xxxxx7,3例：对 码第51页/共6

29、7页第五十二页，共67页。2022-4-145310.4 循环码码多项式运算(yn sun)： 4321T xxxx定理定理 若若T (x )是长为是长为n 的循环码中某个的循环码中某个(mu )许用码字许用码字的码的码 多项式，则多项式，则xi T(x) 在按模在按模 xn +1运算下，也运算下，也是该是该 循环码中一个许用码字的码多项式。循环码中一个许用码字的码多项式。 ( )( )( )r xF xQ xN xN x ( )( )F xQ x N xr x如：（7，3）循环码中许用码字0011101的码多项式为则 3653771111x T xxxxxx （模 运算(yn sun)）(

30、)N x第52页/共67页第五十三页，共67页。2022-4-145410.4 循环码71x 36531x T xxxx（模 运算(yn sun)） 对应(duyng)的码字为1101001，它是该（7，3）循环码中的一另一许用码字，它是循环码0011101左移3次后形成的。1356xxx第53页/共67页第五十四页，共67页。2022-4-145510.4 循环码定理定理 在循环码（在循环码（n，k）中，）中，n-k 次幂的码多项式有一次幂的码多项式有一 个，且仅有一个，用个，且仅有一个，用g(x)表示表示(biosh)。称这唯。称这唯一的一的n-k次次 多项式多项式g(x)为循环码的生成多

31、项式。为循环码的生成多项式。g(x)的常数的常数项项 不为零。不为零。生成(shn chn)多项式及生成(shn chn)矩阵 一旦g(x)确定，则该（n，k）循环码就被确定了。g(x)是循环码中幂次最低的码多项式。由它左移就可产生其它码多项式。比如xg(x)、x2g(x)、x3g(x)等。用k个互相独立的码多项式g(x)、xg(x)、x2g(x) xk-1g(x)可以(ky)构造出循环码的生成矩阵G(x)为第54页/共67页第五十五页，共67页。2022-4-145610.4 循环码 121kkxg xxg xG xx g xg x生成(shn chn)矩阵第55页/共67页第五十六页，共6

32、7页。2022-4-145710.4 循环码例如，（7，3）循环码中最高次幂为n-k次的码字为0010111， 其生成(shn chn)多项式g(x)= x4+ x2+x+1。则利用上式可得其 生成(shn chn)矩阵G(x)为 21101110001011100010111x g xG xx g xG xg x 上式不符合典型生成矩阵的形式，所以它不是典型生成矩阵，由它编出的码字不是系统码。但是对此矩阵作线性变化(binhu)可以变换成典型生成矩阵的形式。第56页/共67页第五十七页，共67页。2022-4-145810.4 循环码例如，（7，3）循环码中最高次幂为n-k次的码字为0010

33、111， 其生成(shn chn)多项式g(x)= x4+ x2+x+1。则利用上式可得其 生成(shn chn)矩阵G(x)为 21101110001011100010111x g xG xx g xG xg x 上式不符合典型生成矩阵(j zhn)的形式，所以它不是典型生成矩阵(j zhn)，由它编出的码字不是系统码。但是对此矩阵(j zhn)作线性变化可以变换成典型生成矩阵(j zhn)的形式。第57页/共67页第五十八页，共67页。2022-4-145910.4 循环码定理定理(dngl) 循环码（循环码（n，k）的生成多项式）的生成多项式g(x)是是xn +1的一个因式。的一个因式。

34、 产生g(x)的方法(fngf)：对（xn+1）进行因式分解，从中找出一个最 高次幂为（n -k）次且常数项不为零的因式， 作为生成多项式g(x)。例如(lr)：对于（7，3）循环码，g(x)的最高次幂为4。可从（x7+1） 中分解得到g(x)。x7+1=（x+1）（x3+x2+1）（x3+x+1）生成多项式可选为g1(x)=（x+1）（x3+x2+1）=x4+x2+x+1或g2(x)=（x+1）（x3+x+1）=x4+ x3+x2+第58页/共67页第五十九页，共67页。2022-4-146010.4 循环码循环码的编码(bin m)及解码1. 编码(bin m)设信息(xnx)码多项式为m(x) m(x)=mk-1 x k-1+ mk-2 x k-2+ m1 x+ m0 m(x)的最高次幂为k-1。 将m(x)左移n-k位成为xn-km(x)，其最高次幂为n-1。xn-km(x)的前一部分为连续k位信息码，后一部分为r=n-k位的“0”，r正好是监督码的位数。所以在它的后一