差错控制编码实用教案

1、2021年12月1日18.1 差错控制编码(bin m)的基本概念 数字通信中，根据不同的目的，编码可分为信源编码和信道编码。 信源编码是为了提高数字通信的有效性，以及为了使模拟信号数字化而采取的编码。 信道编码是为了降低误码率，提高数字通信的可靠性而采取的编码。 数字信号在传输的过程中，加性噪声、码间串扰等都会产生误码。为了提高系统的抗干扰性能，可以加大发射功率，降低接收设备本身(bnshn)的噪声，以及合理选择调制、解调方法等。此外，还可以采用信道编码技术。第1页/共48页第一页，共49页。2021年12月1日2差错控制编码(bin m)的基本思想： 在发送端根据要传输的数字序列（信息码元

2、）按一定的规律加入多余码元，使原来不相关的数字序列变为相关，然后把这些多余码元和有关的信息码元一起传送，接收端根据信息码元与多余码元之间的相关规则进行检验，从而发现错误(cuw)。这时，或者通过反馈信道要求对方重发有错的信息，以进行纠错；或者由接收端的译码器自动把错误(cuw)纠正。 这些多余码元称为校验元或监督元。它的加入不改变信息本身，也就是说，它不传送新的信息，它的作用只是使信道译码器能够检测和纠正差错，从而控制系统差错概率，提高可靠性但这是以系统的有效性为代价的。第2页/共48页第二页，共49页。2021年12月1日38.1.1 差错控制方式(fngsh)第3页/共48页第三页，共49

3、页。2021年12月1日4前向纠错(ji cu)方式 前向纠错方式记作FEC（Forword Error Correction） 发端编码器将数字信息按一定规则附加多余码元，组成有纠错能力的码，发端发送能够纠正错误的码；收端译码器按预先规定的规则译码；若发现错误，确定其出错位置并进行纠正。 优点： 单向传输，只有正向信道；适合于只能提供单向信道的场合；一点发送多点接收的同播方式；译码延迟固定，适用于实时传输系统。 缺点： 编译码设备(shbi)复杂，为了纠正较多的错误，需要附加的多余码元较多，因而传输效率较低。第4页/共48页第四页，共49页。2021年12月1日5检错重发方式(fngsh)

4、又称自动请求重传方式，记作ARQ（Automatic Repeat Request）。 发端编码器将数字信息按一定规则附加多余码元，使之具有一定的检错能力，收端译码器按一定规则对数据码元组进行错误判决，并把判决结果形成应答信号，通过反馈信道回送到发端，发端根据收到的应答信号，把收端认为有错的那组数据码元再次重传，直到码元组无错为止。 优点： 只需要少量(sholing)的多余码元就能获得极低的输出误码率，并且其成本和复杂性均比前向纠错低缺点。 缺点： 必须提供反向信道；不能进行同播（一点发多点收），收发端应有缓冲存储器和控制器；此外当信道干扰较大时，整个系统可能处在重传循环中，因而通信效率降低

5、，信息传输连贯性差，不适于实时传输系统，主要在计算机通信中应用。 常用的检错重发系统有三种，即停发等候重发、返回重发和选择重发。第5页/共48页第五页，共49页。第6页/共48页第六页，共49页。2021年12月1日7混合(hnh)纠错方式 混合纠错方式记作HEC（Hybrid Error Correction） 发端发送具有自动纠错同时又具有检错能力的码。收端收到码后，检查差错情况，如果错误在码的纠错能力范围以内，则自动纠错，如果超过了码的纠错能力但能检测出来，则经过反馈信道请求发端重发。 这种方式具有自动纠错和检错重发的优点，可达到(d do)较低的误码率，因此，近年来得到广泛应用。 在实

6、际通信系统中，选择那种差错控制方式，要视具体情况而定，可以根据信源的性质，信息传输的特点信道干扰的种类和对误码率的要求而适当选择差错控制方式。第7页/共48页第七页，共49页。2021年12月1日88.1.2 差错控制编码(bin m)的分类 根据信息元和监督(jind)元的函数关系，可分为线性码和非线性码。如果函数关系是线性的，即满足一组线性方程式，则称为线性码，否则为非线性码。 根据上述关系涉及的范围，可分为分组码和卷积码。分组码的各码元仅与本组的信息元有关；卷积码中的码元不仅与本组的信息元有关，而且还与前面若干组的信息元有关。 根据码的用途，可分为检错码和纠错码。检错码以检错为目的，不一

7、定能纠错；而纠错码以纠错为目的，一定能检错。 第8页/共48页第八页，共49页。2021年12月1日98.1.3 几种(j zhn)简单的检错码(1) 奇偶(q u)监督码设码字A=an-1,an-2,a1,a0，对偶(du u)监督码有： an-1 an-2 a1 a0 = 0 奇监督码情况相似， 只是码组中“1”的数目为奇数， 即 满足条件： an-1 an-2 a1 a0 = 1 而检错能力与偶监督码相同。 第9页/共48页第九页，共49页。2021年12月1日10奇偶(q u)监督码 编码方法：把信息码元分组，在每组信息码元 的后面附加一位监督码元，使得 码组中1的数目为奇数或偶数即可

8、 编码规则：码组长度n；信息位n-1 特点：是一种能发现(fxin)奇数个差错的分组码；n 较大，即编码码组较长时，编码效率 接近于1;（n-1）/n 信息码元比 码组码元 适用于检测随机的零星错码加性白噪声造 成的第10页/共48页第十页，共49页。2021年12月1日118.1.3 几种(j zhn)简单的检错码(2) 二维奇偶(q u)监督码 (6,11)行列(hng li)监督码 第11页/共48页第十一页，共49页。2021年12月1日12二维奇偶(q u)监督码 编码方法：把码元排成方阵，按行列进行奇偶校验 分别附加一位监督码元 特点：不仅可检测每行（每列）中奇数个错误(cuw)，

9、而且 可通过水平监督和垂直监督来确定错码的位置 纠正仅一行（一列）出现的奇数个错误(cuw) 通过水平监督和垂直监督的关系可以发现单行中出现 的偶数个错误(cuw)；但不能发现构成矩形的4个错误(cuw)码元 适用于突发差错由突发干扰（突发脉冲，如： 闪电，电火花等）在短时间内错码成串出现，在某 一行中出现多个错码第12页/共48页第十二页，共49页。2021年12月1日138.1.3 几种(j zhn)简单的检错码(3) 重复码 在每位信息码元之后，用简单重复多次的方法编码。 例：重复两次时，用111传输1码，用000传输0码 编码方法：每位信息码元简单重复多次； 收端 译码采用(ciyng

10、)多数表决法； 例：重复2次 特点：纠正1个错，检出2个错第13页/共48页第十三页，共49页。2021年12月1日148.1.3 几种(j zhn)简单的检错码(4) 恒比码码字中码字中 1 1 的数目与的数目与 0 0 的数目保持恒定比例的码称为恒比的数目保持恒定比例的码称为恒比码。码。这种码在检测时，只要计算接收码元中这种码在检测时，只要计算接收码元中 1 1 的数目是否的数目是否(sh fu)(sh fu)正确，正确，就知道有无错误。就知道有无错误。第14页/共48页第十四页，共49页。2021年12月1日15恒比码 例：5中取3恒比码用于电报电码 每个码组长度为5，共有25=32种不

11、同的码组， 其中有3个1的码组为可用码组，共有10种 表示10个阿拉伯数字，用它拼成汉字（每4阿拉 伯数字组成1个汉字电码）；其余的22个为禁用 码组。 特点：简单；除了1错为0与0错为1成对出现（对换 性）差错不能检测外，其它任何奇数个或偶数 个错码都可以被检测出来。 只适用(shyng)于传输种类较少且有固定代码的字符，而不适用(shyng)于表示由信源来的二进制随机，数字序列。第15页/共48页第十五页，共49页。2021年12月1日168.1.3 几种(j zhn)简单的检错码(4) ISBN国际(guj)统一图书编号 例 ISBN 0471029777第16页/共48页第十六页，共4

12、9页。2021年12月1日178.1.4 检错和纠错(ji cu)的基本原理 如用三位二进制编码来代表八个字母000 A100E001 B101F010C110G011D111H 不管哪一位发生错误，都会使传输(chun sh)字母错误 如用三位字母传四个字母 000 A011B101 C110D 发生一位错误，准用码字将变成禁用码字，接收端就能知道出错，但是不能纠错。 如果进一步将许用码组限制为两种 000 A 111 B检错和纠错检错和纠错(jicu)能力是用信息量的冗余度来换取的。能力是用信息量的冗余度来换取的。第17页/共48页第十七页，共49页。2021年12月1日18检错和纠错(j

13、i cu)的基本原理 检错和纠错能力是用信息量的冗余度换取的与码组之间的差别有关；不同(b tn)的编码方法和形式，检错和纠错能力不同(b tn)。 例： n = 3，共有8种组合，都用于传输消息，在传输过程中若发生一个误码，则一种码组就会错误地变成另一种码组，但接收端却不能发现错误，因为任何一个码组都是许用码组。第18页/共48页第十八页，共49页。 在差错控制编码中，定义码组中非零码元的数目为码字的汉明在差错控制编码中，定义码组中非零码元的数目为码字的汉明(Hamming)(Hamming)重量，重量， 简称码重。例如，码字简称码重。例如，码字 10110 10110，码重，码重w=3w=

14、3。 定义两个等长码组之间相应位取值不同的数目为这两个码组的汉明定义两个等长码组之间相应位取值不同的数目为这两个码组的汉明(Hamming)(Hamming)距离，距离， 简称码距。例如简称码距。例如 11000 11000 与与 10011 10011之间的距离之间的距离d=3d=3。 码组集中任意两个码字之间距离的最小值称为码的最小距离，用码组集中任意两个码字之间距离的最小值称为码的最小距离，用dmindmin表示。最表示。最小码距是码的一个重要小码距是码的一个重要(zhngyo)(zhngyo)参数，参数， 它是衡量码检错、纠错能力的依据。它是衡量码检错、纠错能力的依据。 第19页/共4

15、8页第十九页，共49页。2021年12月1日20最小码距与检错纠错能力(nngl)的关系 码组内的距离反映了码组之间的差别，最小距离越大，说明两个码组间的最小差别越大，或者说其中一个码组错为另一个码组的可能性就越小，那么其检错和纠错能力也就越强，因此(ync)可以说最小码距是衡量一种纠错编码的检错，纠错能力大小的标准。第20页/共48页第二十页，共49页。 码的最小距离直接关系着码的检错和纠错能力；任一(n,k)分组码，若要在码字内: (1) 检测e个随机错误，则要求(yoqi)码的最小距离dmine+1; (2) 纠正t个随机错误， 则要求(yoqi)码的最小距离dmin2t+1; (3)

16、纠正t个同时检测e(t)个随机错误，则要求(yoqi)码的最小距离dmint+e+1。 t1eAB第21页/共48页第二十一页，共49页。2021年12月1日22 用差错控制编码提高通信系统的可靠性， 是以降低有效性为代价换来的。我们定义编码效率R来衡量有效性: Rc=k/n其中, k是信息元的个数，n为码长。 对纠错码的基本要求是: 检错和纠错能力尽量强； 编码效率尽量高；编码规律尽量简单。实际中要根据具体指标要求，保证有一定(ydng)纠、检错能力和编码效率，并且易于实现。 编码编码(binm)效率效率第22页/共48页第二十二页，共49页。2021年12月1日238.2 线性分组码 线性

17、分组码的构成 将信息序列划分为等长(k位)的序列段 共有2k个不同的序列段，在每一信息 段之后(zhhu)，附加m位监督元，构成长度 n = k + m的分组码(n ，k) 监督元与信息码元为线性关系第23页/共48页第二十三页，共49页。2021年12月1日24例 信息元长度k = 3共有2k = 8个不同(b tn)的信息组 每组信息组加4个监督元，构成一个长度为7 的(7，3)线性分组码。 设： 每组信息元为C1C2C3监督元为C4 C5 C6C7 根据下列线性方程组求监督元 C4 = C1 + C3 C5 = C1 + C2 + C3 C6 = C1 + C2 C7 = C2 + C3

18、第24页/共48页第二十四页，共49页。2021年12月1日25例 (7，3)码有8个信息组，信息组按上方程组求得每个 信息组的4个监督元，得到(7，3)码的所有(suyu)8个码字 信息组 码元 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 0 0 1 1 1 1 0 1 1 0 1 0 0 1 1 1 1 1 1 1 0 1 0 0 重要特性，线性码有封闭性 第25页/共48页第二十五页，共49页。2021年12月

19、1日268.2 线性分组码 设分组码由n位码组构成，记为c1，c2，cn，信息码组由k位码组成，记为d1，d2，dk。则该分组码记为（n，k）码。 码组和信息码组可用行矩阵C和D表示(biosh) 若为线性分组码，C中的n个元素都是由D中的k个元素经线性组合形成的。可用一联立方程表示(biosh)为1212,nkCc ccDd dd第26页/共48页第二十六页，共49页。112211111221221122221122,kkkkkkkknmmmkcdcdcdch dh dh dch dh dh dch dh dh dmnk其中是校验位数将码组将码组C写成矩阵写成矩阵(jzhn)形式形式GC=D

20、矩阵矩阵G称为称为(chnwi)生成矩阵，它是一个生成矩阵，它是一个kn的矩阵的矩阵第27页/共48页第二十七页，共49页。2021年12月1日28生成(shn chn)矩阵G 112111222212112111222212100001000001,100001000001C,mmkkmkkkkkkkmkkkmhhhhhhGhhhGIPhhhhhhIPhhhCD IPDIDPD DPD C码组 又可表示为第28页/共48页第二十八页，共49页。2021年12月1日29生成(shn chn)矩阵G Ik 单位矩阵，k行k列(k x k阶) P矩阵，k行m列(k x m阶) 编码前k位，编码后有

21、n位，2n 2k； 选择P矩阵，可得到有较强检错纠错能力(nngl)，实现 方法尽可能简单，编码效率又高的线性分组码 由于线性码具有封闭性，故任何二个码组之间的距离必须与某一个码组中“1”的个数相等，而码组中非零码元的数目“1”的个数为码组的重量（码重）所以线性码任意二个码字之间的距离必须等于码中某一个码字的重量线性码最小码距正好等于非零码的最小码重 估算线性码的差错控制能力(nngl)： 求最小码距最小码重第29页/共48页第二十九页，共49页。2021年12月1日30例 已知（6，3）码的生成(shn chn)距阵，求：编码码组第30页/共48页第三十页，共49页。2021年12月1日31

22、监督(jind)矩阵H0,00,mmTTTmmmmDPCDPCPPD CCHHorHPIII写成矩阵形式，有或写成其中校验矩阵校验矩阵(jzhn)或监或监督矩阵督矩阵(jzhn)H：mxn阶阶PT:m行行k列列k+m=n列列第31页/共48页第三十一页，共49页。2021年12月1日32伴随(bn su)式（校正子）S 设发送码组C=cn-1,cn-2,c1,c0，在传输过程中可能 发生误码。接收(jishu)码组R =rn-1,rn-2,r1,r0，则收发码组之差定义为错误图样E， 也称为误差矢量， 即 E E =R=RC C=en-1,en-2,e1,e0，且且01ie= 当ri=ci 当

23、rici 令令S=RHT，称为伴随，称为伴随(bnsu)式或校正子式或校正子S=RHT=CHT EHT=EHTS只与错误图形有关，与发送的码组只与错误图形有关，与发送的码组C无关无关HT：nxm阶；阶；E：1xn阶；阶；S：1xm阶；阶；S=s1s2sm解得误差矢量解得误差矢量E E，求得纠错后的码组求得纠错后的码组 C = R C = R E E第32页/共48页第三十二页，共49页。2021年12月1日33检错与纠错(ji cu) 检错：当码组出现错误S为非零矢量 纠错： S = RHT = CHT EHT = EHT S与E之间有着确定的线性关系由H矩阵 确定（也就是与G（P）矩阵有关）

24、 S=s1 s2 sm 共有2m种不同的形式，除全 0外，可代表2m -1种有错误的图形 信息码组有2k个错误图形，有多种不同的形式可能有2k种解答；为了(wi le)选择正确的结果，要使用最大似然比准则，选择与R最相似的C（与R距离最小的码组E是1码最小的矢量）。第33页/共48页第三十三页，共49页。2021年12月1日34例：（6，3）码第34页/共48页第三十四页，共49页。2021年12月1日35S与E对照表 E S 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0

25、1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 1 1 1 （ 6 ， 3 ） 码 具 有 纠 1 位 错 的 能 力发 生 1 个 错 误 的 情 况 ： S 是 H T 的 第 i 行 ， 说 明 R 中 第 i 位 产 生 了 错 误 ， 可 以 把 它 纠 正发 生 2 个 错 误 的 情 况 ： 除 S = 1 1 1 对 应 第 1 ， 5 位 有 错 其 它 的 双 错 不 能 得 到 ( d d o ) 纠 正 例 ： 接 收 码 组 R 1 1 1 0 1 1 第35页/共48页第三十五页，共49页。2021年12月

26、1日36查表法译码器的原理(yunl)S=RHT=CHT EHT=EHT算出伴随式S与最小码重的差错矢量(shling)E的对照表，提供译码使用第36页/共48页第三十六页，共49页。2021年12月1日37汉明码 按上述方法(fngf)构造的能纠正单个错误的线性分组码称为 汉明码。 对于线性分组码，为了指示所有单错位置和无错的情况，必须满足不等式 汉明码具有以下特点： 汉明码的编码效率213211mmndkmtmnk码长最小码距信息码位纠错能力监督码位21mn（取等号时即为汉明码）2112121mcmmkmmRn 第37页/共48页第三十七页，共49页。2021年12月1日38汉明界 如果码

27、组有纠t个差错的能力，则应能指出(zh ch)无错、单错到t个差错所有可能的情况，校验位数m应满足不等式：02tmjnjC汉明界，是纠正(jizhng)t个差错的一个必要条件第38页/共48页第三十八页，共49页。2021年12月1日398.3 循环码特点线性分组码循环(xnhun)性任一许用码字经过循环(xnhun)移位后，得到的码组仍为一个许用码组如 是循环(xnhun)码的一许用码组 则 也是一许用码组 移位i次得到 也是许用码组12,nCc cc(1)231,nCc cc c( )121,iiiniCccc cc第39页/共48页第三十九页，共49页。2021年12月1日408.3.1

28、 循环码的特点(tdin)及表达 码多项式表示(biosh) 以此类推，码组C移位i次，相应的码多项式c(i)(x)是xic(x)除以（xn+1)后的余式。 在模（xn+1)意义下，若c(x)是码多项式，则xic(x)都是码多项式。1212(1)(1)122311(1)121( )( )( )(1)( )nnnnnnnnnnCc xc xc xcCcxc xc xc xcx c xc xc xc xc xcx (1)( )( )1ncxx c xx正好是除以后的余式第40页/共48页第四十页，共49页。2021年12月1日41循环码的编码(bin m)过程 一个k位的信息码组 可用信息多项式表

29、示(biosh) 假设码组多项式可表示(biosh)为12,kDd dd1212( )kkkd xd xd xd( )( )( )c xd xg x1212(1)1(1)1( )( )( )( )( )( )( )( )(1)( )( )( )kkknc xd xg xd xg xd g xx c xx d xg xg xx c xcxcxcxdx g x ）是的 倍 式而）如果(n +1)是g()的倍式 C（1）()=d()g()+ aC1g() =d()+ aC1g()= d1()g() d1()对应某个(mu )信息码组第41页/共48页第四十一页，共49页。2021年12月1日42生成

30、(shn chn)多项式g() (n +1)是g()的倍式，且g()为n-k次多项式，所以对(n +1)进行(jnxng)因式分解，便可得到相应的g()。对(n +1)进行(jnxng)因式分解可由计算机完成，有表格给出。 由信息多项式求解码多项式 C() = d() g() n-1次 k-1次 n-k次第42页/共48页第四十二页，共49页。2021年12月1日43例 (7，4) n=7k=4 m=n-k=3 g()应为(7 + 1 )的3次因式 + 1 = (+ 1 ) ( + + 1 ) ( + + 1 ) g1() = ( + + 1 ) g2() = ( + + 1 )D = 101

31、0 d() = ( + )C1() = d()g1() = ( + ) ( + + 1 ) = + + + C1 = 1001110C2() = d()g2() = ( + ) ( + + 1 ) = + + + C = 1110010注： 1.不同的生成多项式得到(d do)不同的码组 2.由此编码法得到(d do)的不是系统码（前4位不是D=1010）第43页/共48页第四十三页，共49页。2021年12月1日44非系统(xtng)码系统(xtng)码 系统码用多项式表示(biosh)为 k-1次 m-1次 由式（831）码组多项式表示(biosh)为 综合两式有( )( )( )n kc xxd xR x校验位多项式1( )( ) ( )c xd x g x111( )( )( ) ( )( )( ) ( )( )( )( )( )( )( )( )( )( )n kn kn kn kxd xR xd x g xxd xd x g xR xxd xR xd xg xg xxd xR xremg x第44页/共48页第四十四页，共49页。2021年12月1日45例 (7，4) n=7k=4 m=n-k=3 g()应为(7 + 1 )的3次因式 + 1 = (+ 1 ) ( + +