通信原理樊昌信曹丽娜第六差错控制编码学习教案

1、会计学1通信原理通信原理(yunl)樊昌信曹丽娜第六差错控樊昌信曹丽娜第六差错控制编码制编码第一页，共150页。2第1页/共150页第二页，共150页。3差错控制 error-control信道(xn do)编码器 channel encoder反馈信道(xn do) feedback channel检错重发 error detection and retransmission前向纠错 forward error correction自动请求重发 automatic-repeat request第2页/共150页第三页，共150页。4nn前向纠错n反馈校验n检错删除第3页/共150页第四页，共

2、150页。5n理论上，差错控制以降低(jingd)信息传输速率为代价换取提高传输可靠性。第4页/共150页第五页，共150页。6n有得到充分利用，传输效率较低。接收码组ACKACKNAKACKACKNAKACKt1233455发送码组12334556t有错码组有错码组第5页/共150页第六页，共150页。7接收数据有 错 码组有错码组910 1110 1112214365798576ACK1NAK5NAK9ACK5发送数据576952143679810 1110 11 12重发码组重发码组第6页/共150页第七页，共150页。8接收数据有错码组有错码组9214365759810 1113141

3、2发送数据995852143671011131412重发码组重发码组NAK9ACK1NAK5ACK5ACK9第7页/共150页第八页，共150页。9第8页/共150页第九页，共150页。10n发出不需重发指令。发送端收到此指令后，即继续发送后一码组，发送端的(dund)缓冲存储器中的内容也随之更新。第9页/共150页第十页，共150页。11000(晴晴) 001(云云) 010(阴阴) 011(雨雨) 100(雪雪) 101(霜霜) 110(雾雾) 111(雹雹)000(晴晴) 011(云云) 101(阴阴) 110(雨雨)000(晴晴) 111(雨雨)只允许只允许(ynx)使用使用4组组使用

4、使用2组组不能发现错误不能发现错误可能发现一个错误或可能发现一个错误或检测检测3个错码个错码检测检测2个以下错个以下错码，或能纠正码，或能纠正一个错码一个错码第10页/共150页第十一页，共150页。12信息位监督位晴000云011阴101雨110如果不要求检如果不要求检(纠纠)错，为了传输错，为了传输(chun sh)4种不同种不同的信息，我们用两位码组：的信息，我们用两位码组：00，01，10，11。代表所。代表所传信息的这些两位码，称为信息位。传信息的这些两位码，称为信息位。第11页/共150页第十二页，共150页。13将信息码分组，为每组信码附加若干监督将信息码分组，为每组信码附加若干

5、监督(jind)码的编码码的编码集合，称为分组码。集合，称为分组码。分组码一般用符号分组码一般用符号(n,k)表示，其中表示，其中k是每组二进信息码元的是每组二进信息码元的数目，数目，n是编码组的总位数，又称为码组长度（码长），是编码组的总位数，又称为码组长度（码长），n-k=r为每码组中的监督为每码组中的监督(jind)码元数目，或称监督码元数目，或称监督(jind)位数目。位数目。第12页/共150页第十三页，共150页。14第13页/共150页第十四页，共150页。15(jl)。n由此图可以直观看出，上例中4个准用码组之间的距离(jl)均为2。(0,0,0)(0,0,1)(1,0,1)(

6、1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a1第14页/共150页第十五页，共150页。16组A发生两位以下错码时，n不可能变成另一个准用n码组，因而能检测(jin c)错码n的位数等于2。0123BA汉明距离ed0第15页/共150页第十六页，共150页。17BtA汉明距离012345td0第16页/共150页第十七页，共150页。18第17页/共150页第十八页，共150页。19BtA汉明距离012345td0第18页/共150页第十九页，共150页。20ABe1tt汉明距离)(10teted第19页/共150页第二十页，共150页。21第20页/共150

7、页第二十一页，共150页。22采用纠错编码后，误码率总是能够得到很大改善的。改善的程度和所用的编码有关。第21页/共150页第二十二页，共150页。2310-610-510-410-310-210-1编码后PeCDEAB信噪比 (dB)第22页/共150页第二十三页，共150页。2410-610-510-410-310-210-1编码后PeCDEAB信噪比 (dB)第23页/共150页第二十四页，共150页。25n代价仍是带宽增大。10-610-510-410-310-210-1编码后PeCDEAB信噪比 (dB)第24页/共150页第二十五页，共150页。26n用于纠错，由dmin 2t+1

8、得t=1，能纠正1位错码。第25页/共150页第二十六页，共150页。27线性分组码 linear block codes循环码 cyclic codes卷积码 convolutional codes纠错(ji cu)码 error-correcting codes检错 error detection纠错(ji cu) error correcting混合纠错(ji cu) hybrid error correct第26页/共150页第二十七页，共150页。28端，按照上式求“模2和”，若计算结果为“1”就说明存在错码，结果为“0”就认为无错码。n奇数监督码与偶数监督码相似，只不过其码组中“1

9、”的数目为奇数：第27页/共150页第二十八页，共150页。29m个监督位。ncn-1 cn-2 c1 c0为按列进行第二次编码所增加的监督位，它们构成了一监督位行。第28页/共150页第二十九页，共150页。30n由于方阵码只对构成矩形四角的错码无法检测，故其检错能力较强。n二维奇偶监督码不仅可用来检错，还可以用来纠正一些(yxi)错码。 例如，仅在一行中有奇数个错码时。第29页/共150页第三十页，共150页。31使用了。第30页/共150页第三十一页，共150页。32n当信息位有偶数个当信息位有偶数个“1”时，监督位是时，监督位是信息位的反码。信息位的反码。n例如，若信息位为例如，若信息

10、位为11001，则码组为，则码组为1100111001；若信息位为；若信息位为10001，则码，则码组为组为1000101110。第31页/共150页第三十二页，共150页。33现的错码。第32页/共150页第三十三页，共150页。34校验码组的组成错码情况1全为“0”无错码2有4个“1”和1个“0”信息码中有1位错码，其位置对应校验码组中“0”的位置3有4个“0”和1个“1”监督码中有1位错码，其位置对应校验码组中“1”的位置4其他组成错码多于1个第33页/共150页第三十四页，共150页。35101并能检测全部2位以下的错码和大部分2位以上的错码。第34页/共150页第三十五页，共150页

11、。36般原理。第35页/共150页第三十六页，共150页。37n若若S = 0，就认为无错码；若，就认为无错码；若S = 1，就认为有错码。现将上式称为监督就认为有错码。现将上式称为监督关系式，关系式，S称为校正子。由于校正称为校正子。由于校正子子S只有只有(zhyu)两种取值，故它只两种取值，故它只能代表有错和无错这两种信息，而能代表有错和无错这两种信息，而不能指出错码的位置。不能指出错码的位置。0021aaann第36页/共150页第三十七页，共150页。38第37页/共150页第三十八页，共150页。39S1 S2 S3错码位置S1 S2 S3错码位置001a0101a4010a1110

12、a5100a2111a6011a3000无错码第38页/共150页第三十九页，共150页。40第39页/共150页第四十页，共150页。41n给定信息位后，可以直接按上式算出监督(jind)位， 结果见下表：第40页/共150页第四十一页，共150页。42信息位a6 a5 a4 a3监督位a2 a1 a0信息位a6 a5 a4 a3监督位a2 a1 a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111第41页/共150页

13、第四十二页，共150页。43第42页/共150页第四十三页，共150页。44n上式中已经将“”简写成“+”。n000034613562456aaaaaaaaaaaa第43页/共150页第四十四页，共150页。45010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa第44页/共150页第四十五页，共150页。46第45页/共150页第四十六页，共150页。47第46页/共150页第四十七页，共150页。48346035614562aaaaaaaaaaaa第47页/共150页第四十八页，共150页。4934560121

14、01111011110aaaaaaa第48页/共150页第四十九页，共150页。50附加于其后。这种形式的码称为系统码。第49页/共150页第五十页，共150页。51第50页/共150页第五十一页，共150页。52第51页/共150页第五十二页，共150页。53第52页/共150页第五十三页，共150页。54nS = E H Tn式中S称为校正子。它能用来指示错码的位置。nS和错码E之间有确定(qudng)的线性变换关系。若S和E之间一一对应，则S将能代表错码的位置。第53页/共150页第五十四页，共150页。55n由于线性码具有封闭性，所以两个码组(A1和A2)之间的距离（即对应位不同的数目

15、）必定是另一个码组(A1 + A2)的重量（即“1”的数目）。因此(ync)，码的最小距离就是码的最小重量（除全“0”码组外）。第54页/共150页第五十五页，共150页。56第55页/共150页第五十六页，共150页。57第56页/共150页第五十七页，共150页。58生成(shn chn)多项式 generator polynomial奇偶校验 parity-check移位寄存器 shift register约束长度 constraint length编码器 encoder系统码systematic code 第57页/共150页第五十八页，共150页。59n例如，表中的第2码组向右移一位

16、即得到第5码组；第6码组向右移一位即得到第7码组。码组编号信息位监督位码组编号信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010第58页/共150页第五十九页，共150页。60第59页/共150页第六十页，共150页。61第60页/共150页第六十一页，共150页。62 n 第61页/共150页第六十二页，共150页。63 xx3 + 1 x4 +x2 + 1 x4 + x x2 +x +1应当注意，由于在模2运算中，用加法代替了减法(jinf)，故

17、余项不是x2 x + 1，而是x2 + x + 1。第62页/共150页第六十三页，共150页。64n（模(xn + 1)）n所以，这时有第63页/共150页第六十四页，共150页。65ininininninaxaxaxaxaxT1102211)(第64页/共150页第六十五页，共150页。66GA3456aaaa第65页/共150页第六十六页，共150页。67式g(x)为码的生成多项式。一旦确定了g(x)，则整个(n, k)循环码就被确定了。第66页/共150页第六十七页，共150页。68第67页/共150页第六十八页，共150页。69第68页/共150页第六十九页，共150页。70n可知(

18、k zh)，xk T (x)在模(xn + 1)运算下也是一个码组，故可以写成）（模) 1()()(nixxTxTx第69页/共150页第七十页，共150页。711)()(1)(nnkxxTxQxxTx第70页/共150页第七十一页，共150页。72第71页/共150页第七十二页，共150页。73于k。用xn - k乘m(x)，得到的xn-k m(x)的次数必定小于n。用g(x)除xn - k m(x)，得到余式r(x)，r(x)的次数必定小于g(x)的次数，即小于(n k)。将此余式r(x)加于信息位之后作为监督位，即将r(x)和xn - k m(x)相加，得到的多项式必定是一个码多项式。因

19、为它必须能被g(x)整除，且商的次数不大于(k 1)。第72页/共150页第七十三页，共150页。74第73页/共150页第七十四页，共150页。75第74页/共150页第七十五页，共150页。76收码组中有无错码。n需要(xyo)指出，有错码的接收码组也有可能被g(x)整除。这时的错码就不能检出了。这种错误称为不可检错误。不可检错误中的误码数必定超过了这种编码的检错能力。第75页/共150页第七十六页，共150页。77n目前(mqin)多采用软件运算实现上述编解码运算。第76页/共150页第七十七页，共150页。78到一个到一个(n i, k i)的线性码。将这的线性码。将这种码称为截短循环

20、码。种码称为截短循环码。n截短循环码性能：循环码截短前后截短循环码性能：循环码截短前后至少具有相同的纠错能力，并且编至少具有相同的纠错能力，并且编解码方法仍和截短前的方法一样。解码方法仍和截短前的方法一样。n例：要求构造一个能够纠正例：要求构造一个能够纠正1位错位错码的码的(13, 9)码。这时可以由码。这时可以由(15, 11)循环码的循环码的11种码组中选出前两信息种码组中选出前两信息位均为位均为“0”的码组，构成的码组，构成(guchng)一个新的码组集合。然后在发送时一个新的码组集合。然后在发送时不发送这两位不发送这两位“0”。于是发送码组。于是发送码组成为成为(13, 9)截短循环码

21、。截短循环码。第77页/共150页第七十八页，共150页。79n本原BCH码：其生成多项式g(x)中含有最高次数(csh)为m的本原多项式，且码长为n = 2m 1，(m 3，为正整数)。n非本原BCH码：其生成多项式中不含这种本原多项式，且码长n是(2m 1)的一个因子，即码长n一定除得尽2m 1。第78页/共150页第七十九页，共150页。80而用g3(x) = x4 + x + 1或g4(x) = x4 + x3 + 1都能生成(15, 11)汉明码。第79页/共150页第八十页，共150页。81第80页/共150页第八十一页，共150页。82n = 3k t g(x)1 1 7n =

22、63k t g(x)57 1 10351 2 1247145 3 170131739 4 16662356736 5 103350042330 6 15746416534724 7 1732326040444118 10 136302651235172516 11 633114136723545310 13 4726223055272501557 15 52310455435032717371 31 全部为1n = 7k t g(x)4 1 131 3 77n = 15k t g(x)11 1 23 7 2 721 5 3 2467 1 7 77777第81页/共150页第八十二页，共150页

23、。83n = 31 k t g(x)26 1 4521 2 355116 3 10765711 5 54233256 7 3133650471 15 = 127 k t g(x)120 1 211113 2 41567106 3 11554743 99 4 3447023271 92 5 624730022327 85 6 130704476322273 78 7 26230002166130115 71 9 6255010713253127753 64 10 1206534025570773100045 57 11 235265252505705053517721

24、50 13 54446512523314012421501421 43 15 17721772213651227521220574343 36 15 3146074666522075044764574721735 29 22 403114461367670603667530141176155 22 23 123376070404722522435445626637647043 15 27 22057042445604554770523013762217604353 8 31 7047264052751030651476224271567733130217 1 63 全部为1第82页/共150页

25、第八十三页，共150页。84nktg(x)nktg(x)17212333419121222212232472716635343514566471334765657324534046524443073357107613543000671717773537第83页/共150页第八十四页，共150页。85第84页/共150页第八十五页，共150页。86+2t)n式中，式中， 伽罗华域伽罗华域GF(2q)中的中的本原元。本原元。n若将每个若将每个m进制码元表示成相应的进制码元表示成相应的q位二进制码元，则得到的二进制码位二进制码元，则得到的二进制码的参数为：的参数为：n码长：码长：n = q(2q 1

26、)（二进制（二进制码元）码元）n监督码：监督码：r = 2qt（二进制码（二进制码元）元）第85页/共150页第八十六页，共150页。87第86页/共150页第八十七页，共150页。88第87页/共150页第八十八页，共150页。89第88页/共150页第八十九页，共150页。90第89页/共150页第九十页，共150页。91码树 code tree网格图 trellis diagram状态图 state diagram维特比算法 the Viterbi algorithm幸存(xn cn)路径surviving path第90页/共150页第九十一页，共150页。92nN一般说来，对于卷积码

27、，k 和 n 的值是比较小的整数。我们将卷积码记作(n, k, N)。码率则仍定义为k / n。第91页/共150页第九十二页，共150页。93编码输出每次输入k比特1k1k1k1k 1 k2k3kNk 12nNk级移存器n个模2加法器每输入k比特旋转1周第92页/共150页第九十三页，共150页。94bi-2bi输入bibi-1编码输出dicieiM2M3M1第93页/共150页第九十四页，共150页。95ci-2di-2ei-2ci-1di-1ei-1cidieibi-2bi1bitt输入输出第94页/共150页第九十五页，共150页。96第95页/共150页第九十六页，共150页。97第

28、96页/共150页第九十七页，共150页。98第97页/共150页第九十八页，共150页。99的左端比上两行多了3个“0”。第98页/共150页第九十九页，共150页。100H1 =nn k(n k)N第99页/共150页第一百页，共150页。101第100页/共150页第一百零一页，共150页。102从给定的h不难构造出H1。第101页/共150页第一百零二页，共150页。103第102页/共150页第一百零三页，共150页。104第103页/共150页第一百零四页，共150页。105n一般说来，截短生成矩阵具有如下形式：第104页/共150页第一百零五页，共150页。106第105页/共1

29、50页第一百零六页，共150页。107提出的序贯解码就是概率解码方法之一。另一种概率解码方法是维特比算法。当码的约束长度较短时，它比序贯解码算法的效率更高、速度更快，目前得到广泛的应用。第106页/共150页第一百零七页，共150页。108校正子计算信息位移存器校正子移存器错码检测 输入输出修正校正子信息位监督位第107页/共150页第一百零八页，共150页。109第108页/共150页第一百零九页，共150页。110nb6b5b4b3b2b1bi ci输入输出bici第109页/共150页第一百一十页，共150页。111第110页/共150页第一百一十一页，共150页。112第111页/共1

30、50页第一百一十二页，共150页。113输入输出Yb6b5b4b3b2b1S6S5S4S3S2S1门限电路：“1”的个数 3？校正子Si校正子移存器信息位移存器重算监督位ci接收监督位计算校正子Si6 5 4 3 2 1此卷积码除了能够(nnggu)纠正两位在约束长度中的随机错误外，还能纠正部分多于两位的错误。 第112页/共150页第一百一十三页，共150页。114起点信息位状态 M3M2 a 0 0 b 0 1 c 1 0 d 1 1信 息 位信 息 位 11 0 1000111c1d1e1000111001110011100010101000111001110011100010101c4

31、d4e4111000001110c2d2e22000100111011001101110010c3d3e3abcdabcdabcdabcd上半部下半部ba10aabcdabcdcdab011001由此码树图还可以看到，从第4级支路开始，码树的上半部和下半部相同。这意味着，从第4个输入(shr)信息位开始，输出码元已经与第1位输入(shr)信息位无关，即此编码器的约束度N = 3。第113页/共150页第一百一十四页，共150页。115个信息位，分支已有24 = 16个。但是它为以后实用解码算法建立了初步(chb)基础。第114页/共150页第一百一十五页，共150页。116第115页/共150

32、页第一百一十六页，共150页。117移存器前一状态M3 M2当前输入信息位 bi输出码元cidiei移存器下一状态M3 M2a (00)01000111a (00)b (01)b (01)01001110c (10)d (11)c (10)01011100a (00)b (01)d (11)01010101c (10)d (11)第116页/共150页第一百一十七页，共150页。118abcd000111101110010011100001第117页/共150页第一百一十八页，共150页。11911011011011001101101101001001010110110100100100100

33、1abcdabcd000000000000000111111111111111100100100第118页/共150页第一百一十九页，共150页。120abcdabcd110010001111100第119页/共150页第一百二十页，共150页。121第120页/共150页第一百二十一页，共150页。122第121页/共150页第一百二十二页，共150页。123110110110110011011011010010010101101101001001001001abcdabcd000000000000000111111111111111100100100第122页/共150页第一百二十三页，共

34、150页。124序号路径对应序列汉明距离幸存否1aaaa000 000 0005否2abca111 001 0113是3aaab000 000 1116否4abcb111 001 1004是5aabc000 111 0017否6abdc111 110 0101是7aabd000 111 1106否8abdd111 110 1014是第123页/共150页第一百二十四页，共150页。125按照表中的幸存(xn cn)路径画出的网格图示于下图中。序号路径原幸存路径的距离新增路径段新增距离总距离幸存否1abca+a3aa25否2abdc+a1ca23是3abca+b3ab14否4abdc+b1cb1

35、2是5abcb+c4bc37否6abdd+c4dc15是7abcb+d4bd04是8abdd+d4dd26否第124页/共150页第一百二十五页，共150页。126abcd011010010101001abcd111100100110110第125页/共150页第一百二十六页，共150页。127“0”(zhungti)a。而由图可见，只有两条路径可以回到a状态(zhungti)。所以，这时上图可以简化成下图。1 100 110 100 101 011 010 010 01abcdabcd0 00 1 111 001 000 00 0 110 110 011 01第126页/共150页第一百二十

36、七页，共150页。1281 100 110 100 101 011 010 010 01abcdabcd0 00 1111 001 000 00 0 110 110 01第127页/共150页第一百二十八页，共150页。129第128页/共150页第一百二十九页，共150页。130第129页/共150页第一百三十页，共150页。131第130页/共150页第一百三十一页，共150页。132则将出现错码。现在，将系统改成8PSK，它的每个码元可以传输3 比特信息。但是我们仍然令每个码元传输2 比特信息。第3 比特用于纠错码，例如，采用码率为2/3的卷积码。这时接收端的解调和解码是作为一个步骤完成的，不像传统作法，先解调得到(d do)基带信号后再为纠错去解码。第131页/共150页第一百三十二页，共15