第11章差错控制编码课件.ppt

1、1通信原理第11章差错控制编码 211.1 概述z信道分类：从差错控制角度看v随机信道：错码的出现是随机的 v突发信道：错码是成串集中出现的v混合信道：既存在随机错码又存在突发错码 z差错控制技术的种类v 检错重发v前向纠错 v反馈校验v检错删除 3z差错控制编码：常称为纠错编码纠错编码v信息码元信息码元 kv监督码元监督码元 n-kv编码效率编码效率(简称码率码率)信息码元个数与总码元个数之比k/n v冗余度：冗余度：监督码元数(n-k)和信息码元数 k 之比。v差错控制以降低信息传输速率为代价换取提高传输可靠性。411.2 纠错编码的基本原理z分组码基本原理：v所有比特用于传送信息 3位二

2、进制数可构成8种不同组合，若将其全部用来表示8种不同天气，“000”（晴），“001”（云），“010”（阴），“011”（雨），“100”（雪），“101”（霜），“110”（雾），“111”（雹）。w问题：其中任一码组在传输中若发生错码都将变成另一个信息码组 接收端将无法发现错误。许用码组5v部分比特用于传送信息 若在上述8种码组中只准许使用4种来传送天气，例如：“000”（晴），“001”（云），“011”（雨），“010”（阴），“101”（霜），“100”（雪），“110”（雾），“111”（雹）。w发端错一位或三位码，收端可以检测出来w信息量降低，但检错能力提高了w发端错两位码，收

3、端检测不出来?许用码组禁用码组增大冗余度即增加监督位6v分组码的结构w将信息码分组，为每组信息码附加若干监督码的编码称为分组码分组码。w在分组码中，监督码元仅监督本码组中的信息码元。w信息位和监督位的关系，如信息位信息位监督位监督位晴晴000云云011阴阴101雨雨1107w分组码的一般结构v分组码的符号：(n,k)wN 码组的总位数，又称为码组的长度（码长），wk 码组中信息码元的数目，wn k r 码组中的监督码元数目，或称监督位数目。8v分组码的码重和码距w码重：码组中“1”的个数w码距：两个码组中对应位上不同数字的个数，又称汉明距离汉明距离。w最小码距d0：某种编码中各个码组之间距离的

4、最小值)。v码距的几何意义w每个码组的3个码元的值(a1,a2,a3)就是此立方体各顶点的坐标。w码距概念在图中对应于各顶点之间沿立方体各边行走的几何距离。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a19v码距和检纠错能力的关系w一种编码的最小码距d0的大小直接关系着这种编码的检错和纠错能力w为检测e个错码，要求最小码距 d0 e+1w为了纠正t个错码，要求最小码距d0 2t+1w为纠正t个错码，同时检测e个错码，要求最小码距)(10teted1011.4简单的实用编码z11.4.1 奇偶监督码v奇偶监督码只有一位监

5、督位v偶监督保证码组中“1”的数目为偶数，偶监督关系式：式中a0为监督位，其他位为信息位。v奇监督保证码组中“1”的数目为奇数，奇监督关系式：0021aaann1021aaann1111.5 线性分组码z基本概念v代数码代数码：建立在代数学基础上的编码。v线性码线性码：信息位和监督位是由一组线性代数方程联系着的。z汉明码汉明码v定义：能够纠正1位错码且编码效率较高的一种线性分组码12v汉明码的构造原理。w监督关系式监督关系式w校正子校正子G若S=0，无错码；若S=1，有错码G一个校正子S不能指出错码的位置G多个校正子的组合可指出错码位置G增多校正子 增多监督关系式 增多监督位Gr个监督关系式能

6、指示1位错码的 个可能位置G指示1位错码的n种可能位置的监督位个数要求12r0021aaann021aaaSnn1212rknrr或13w例：设分组码分组码(n,k)中k=4，为了纠正1位错码，由上式可知，要求监督位数 r 3。若取 r=3，则n=k+r=7。S1 S2 S3错码位错码位置置S1 S2 S3错码位错码位置置001a0101a4010a1110a5100a2111a6011a3000无错码无错码错码位置与校正子关系监督关系式24561aaaaS13562aaaaS03463aaaaS14信息位信息位a6 a5 a4 a3监督位监督位a2 a1 a0信息位信息位a6 a5 a4 a

7、3监督位监督位a2 a1 a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111由监督关系式得出的信息位与监督位接收端收到每个码组后，先计算出S1、S2和S3，再查表判断错码情况。表中所列的(7,4)汉明码的最小码距d0=3。因此，这种码能够纠正1个错码或检测2个错码。由于码率k/n=(n-r)/n=1 r/n，故当n很大和r很小时，码率接近1。可见，汉明码是一种高效码。15z线性分组码的一般原理v线性分组码的构造wH矩阵

8、（监督阵）000034613562456aaaaaaaaaaaa010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa）（模20001011001110101011101000123456aaaaaaaH AT=0T 或或A HT=0监督阵16GH矩阵的性质：G H的行数就是监督关系式的数目，等于监督位个数r。G 典型监督阵可分解为P Ir形式，P为r k阶矩阵，Ir 为r r阶单位方阵。G由代数理论可知，H矩阵的各行应该是线性无关的 rPIH00110110101101100111017wG矩阵（生成矩阵）3460

9、35614562aaaaaaaaaaaa3456012101111011110aaaaaaaQ34563456012011101110111aaaaaaaaaaaQ为一为一k r阶矩阵，阶矩阵，Q=PT在信息位给定后，用在信息位给定后，用信息位的行矩阵乘矩信息位的行矩阵乘矩阵阵Q就产生出监督位就产生出监督位180110001101001011001001111000QGkI I G34560123456aaaaaaaaaaaGA3456aaaa生成阵G如果找到了码的生成矩阵G，则编码的方法就完全确定了。G具有IkQ形式的生成矩阵称为典型生成矩阵典型生成矩阵。系统码19GG矩阵的性质：G G矩阵

10、的各行是线性无关的。G G的各行本身就是一个码组。G如果已有k个线性无关的码组，则可以用其作 为生成矩阵G。20w错误图样 0121bbbbnnB0121eeeennEiiiiiababe当当,1,00121aaaannAB A=E错误图样接收码发送码21v线性分组码的性质w封闭性：封闭性：是指一种线性码中的任意两个码组之和仍为这种码中的一个码组。w两个码组(A1和A2)之间的距离（即对应位不同的数目）必定是另一个码组(A1+A2)的重量（即“1”的数目）。w码组间的最小距离就是码组的最小重量（除全“0”码组外）。2211.6 循环码z11.6.1 循环码原理v循环性：循环性：指任一码组循环移

11、位（即将最右端的一个码元移至左端，或反之）以后，仍为该码中的一个码组。一种(7,3)循环码的全部码组(an-1 an-2 a0)码组编码组编号号信息位信息位监督位监督位码组编码组编号号信息位信息位监督位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0100000005100101120010111610111003010111071100101401110018111001023v码多项式w码组的多项式表示法把码组中各码元当作是一个多项式的系数，即一个长为n的码组表示为Gxn仅是码元位置的标记，不关心xn的取值。w码多项式的按模运算G整数运算中的模n运算 若一个整数m可以表示为

12、式中，Q 整数，则在模 n 运算下，有 m p (模n)即，在模 n 运算下，一个整数m等于它被 n 除得的余数。npnpQnm,012211)(axaxaxaxTnnnn24G码多项式运算中的模运算。若一任意多项式F(x)被一 n 次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)，即则写为G码多项式系数仍按模2 运算，即系数只取 0 和1。如，因为)()()()(xRxQxNxF）（模)()()(xNxRxF）（模)1(113224xxxxx xx3+1 x4+x2+1 x4+x x2+x+1注意，由于在模2运算中，用加法代替了减法25v循环码的生成矩阵Gwk个线性不相关的

13、已知码组可构成生成矩阵Gw用g(x)表示(n,k)循环码中前(k-1)位皆为“0”的码组，则g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是码组，且是线性无关的。(左移)wg(x)必须是一个常数项不为“0”的(n-k)次多项式，而且是(n,k)码中次数为(n k)的唯一多项式（线性无关）w唯一的(n k)次多项式g(x)为码的生成多项式w循环码的生成矩阵G可得)()()()()(21xgxxgxgxxgxxkkG26w所有码多项式T(x)都可被g(x)整除，且任意一个次数不大于(k 1)的多项式乘g(x)都是码多项式v循环码的码多项式w在循环码中，若T(x)是一个长为n的许用码组

14、，则xiT(x)在按模xn+1运算下，也是该编码中的一个许用码组，即若 则T(x)也是该编码中的一个许用码组。)()()()()()()()()()(452645262456456xgaxaxaxgaxxgaxgxaxgxxgxgxaaaxaaaxTG）（模)1()()(nixxTxTx27v如何寻找任一(n,k)循环码的生成多项式循环码的生成多项式应该是(xn+1)的一个(n k)次因式为了求(7,3)循环码的生成多项式g(x)需要从(x7+1)中找到一个(n k)=4次的因子)1)(1)(1(13237xxxxxx1)1)(1(2423xxxxxx1)1)(1(2343xxxxxx上两式都

15、可作为生成多项式。选用的生成多项式不同，产生出的循环码码组也不同28z11.6.2 循环码的编解码方法v循环码的编码方法w编码原则G从(xn+1)的因子中选一个(n-k)次多项式作为g(x)。G所有码多项式T(x)都可以被g(x)整除。w编码步骤：G用xn-k乘m(x)G用g(x)除xn-k m(x)，得到商Q(x)和余式r(x)G编出的码组T(x)为T(x)=xn-k m(x)+r(x)29v循环码的解码方法w解码要求：检错和纠错。w检错解码原理：在接收端将接收码组R(x)用原生成多项式g(x)去除，判断余式。w纠错解码原理：为了能够纠错，要求每个可纠正的错误图样必须与一个特定余式有一一对应

16、关系。步骤如下：G用生成多项式g(x)除接收码组R(x)，得出余式r(x)。G按余式r(x)，用查表的方法或通过某种计算得到错误图样E(x)；G从R(x)中减去E(x)，便得到已经纠正错码的原发送码组T(x)。w通常，一种编码可以有几种纠错解码方法，上述解码方法称为捕错解码法。3011.7 卷积码z非分组码概念：v卷积码是一种非分组码，更适用于前向纠错。v卷积码监督码元不仅和当前的k比特信息段有关，而且还同前面m=(N 1)个信息段有关。v约束度：一个码组中的监督码元监督的信息段的个数Nv卷积码记作(n,k,N)31z11.7.1 卷积码的基本原理v编码器原理方框图编码输出每次输入k比特1k1

17、k1k1k 1 k2k3kNk 12nNk级移存器n个模2加法器每输入k比特旋转1周32v例：(n,k,N)=(3,1,3)卷积码编码器w方框图w设输入信息比特序列是bi-2 bi-1 bi bi+1，输入bi与输出比特ci di ei关系如下：bi-2bi输入bibi-1编码输出dicieiM2M3M121 2iiiiiiiiibbbebbdbc33ci-2di-2ei-2ci-1di-1ei-1cidieibi-2bi1bitt输入输出虚线示出了信息位bi的监督位和各信息位之间的约束关系，约束长度nN等于9。34z11.7.2 卷积码的代数表述v卷积码也是一种线性码。v一个线性码完全由一个

18、监督矩阵H或生成矩阵G所确定。v 监督矩阵HG设上图中在第1个信息位b1进入编码器之前，各级移存器都处于“0”状态。G监督位di、ei和信息位bi之间的关系可表示为：35 左式可以改写为11112222133133214424432dbebdbebbdbbebbbdbbebbb 1111221221331233244234400000000bdbebdbbebbdbbbebbdbbbe 36与11.5节公式H AT=0T对比，可以看出监督矩阵Oedbedbedbedb4443332221110100010010011000100000110010010110000011100101000111

19、011137G卷积码的H是一个有头无尾的半无穷矩阵。G监督矩阵的每3列的结构是相同的，只是后3列比前3列向下移了 两行。G自第7行起，每两行的左端比上两行多了3个“0”。01000100100110001000001100100101100000111001010001110111H38截短监督矩阵的结构形式如下图：GH1的最左边是n列(n-k)N行的一个子矩阵，且向右的每n列均相对于前n列降低(n-k)行。G截短监督矩阵一旦确定，卷积码的监督矩阵就可完全确定。H1=nn k(n k)N39此例中码的截短监督矩阵可以写成如下形式：式中 2阶单位方阵；Pi 2 1阶矩阵，i=1,2,3；O2 2

20、阶全零方阵。2122232122211100100101100000111001010001110111IPOPOPIPOPIPH01102I40一般说来，卷积码的截短监督矩阵具有如下形式：G In-k (n k)阶单位方阵；Pi (n k)k阶矩阵；On-k (n k)阶全零方阵。GH1的末行称为基本监督矩阵hh=PN On-k PN-1 On-k PN-2 On-k P1 In-kGh是卷积码的一个最重要的矩阵，因为只要给定了h，可完整的监督阵H 就确定了。knknNknNknNknknknknknknIPOPOPOPIPOPOPIPOPIPH121123121141v生成矩阵生成矩阵G上

21、例中的输出码元序列可以写成 b1 d1 e1 b2 d2 e2 b3 d3 e3 b4 d4 e4 =b1 b1 b1 b2 b2(b2+b1)b3(b3+b1)(b3+b2+b1)b4(b4+b2)(b4+b3+b2)00000000000000000000000000100000000000001110000000000001111000000001100111100000000110011114321bbbb42此码的生成矩阵G即为上式最右矩阵：000000000000000000000000001000000000000011100000000000011110000000011001

22、1110000000011001111G43v截短生成矩阵：类似地，也有截短生成矩阵式中 I1 一阶单位方阵；Qi 1 2阶矩阵。w与H1矩阵比较可见，Qi是矩阵Pi的转置：Qi=PiT (i=1,2,)w截短生成矩阵具有如下形式：1121132111111000000001111000011001111QIQOQIQOQOQIG44式中 Ik k阶单位方阵；Qi k (n k)阶矩阵；Ok k阶全零方阵。w基本生成矩阵：上式中矩阵第一行g Ik Q1 Ok Q2 Ok Q3Ok QNG如果基本生成矩阵g已经给定，则可以从已知的信息位得到整个编码序列。1211213211QIQOQIQOQOQ

23、IQOQOQOQIGkNkkNkkkNkkkk45z11.7.3 卷积码的解码v分类：w代数解码：利用编码本身的代数结构进行解码，不考虑信道的统计特性。大数逻辑解码，又称门限解码。w概率解码：又称最大似然解码。它基于信道的统计特性和卷积码的特点进行计算。另一种概率解码方法是维特比算法。46v卷积码的几何表述w码树图：现仍以上面(3,1,3)码为例，介绍卷积码的码树 起点信息位状态 M3M2 a 0 0 b 0 1 c 1 0 d 1 1信息位信息位 11 0 1000111c1d1e1000111001110011100010101000111001110011100010101c4d4e41

24、11000001110c2d2e22000100111011001101110010c3d3e3abcdabcdabcdabcd上半部下半部ba10aabcdabcdcdab01100147移存器前一状态移存器前一状态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)w状态图G将当前输入信息位、移存器前一状态、移存器下一状态和输出码元之间的关系归纳于下表

25、中48G虚线表示输入信息位为“1”时状态转变的路线；G实线表示输入信息位为“0”时状态转变的路线。G线条旁的3位数字是编码输出比特。G利用状态图可以方便地从输入序列得到输出序列。abcd000111101110010011100001G按照上表中的规律，可以画出状态图如下图所示49w网格图G将状态图在时间上展开，可以得到网格图如下：G图中画出了5个时隙。G虚线表示输入信息位为“1”时状态转变的路线；G实线表示输入信息位为“0”时状态转变的路线。G在第4时隙以后的网格图形完全是重复第3时隙的图形。11011011011001101101101001001010110110100100100100

26、1abcdabcd00000000000000011111111111111110010010050G上图中给出了输入信息位为11010时，在网格图中的编码路径。G图中示出这时的输出编码序列是：111 110 010 100 011。G用网格图表示编码过程和输入输出关系比码树图更为简练。abcdabcd11001000111110051v维特比解码算法w基本原理G将接收到的信号序列和所有可能的发送信号序列比较，选择其中汉明距离最小的序列，认为是当前发送信号序列。G发送的序列越长，存储量越大。维特比算法对此作了简化，使之能够实用。w例：(3,1,3)卷积码G设发送信息位为1101，G为使移存器的

27、信息位全部移出，在信息位后面加入3个“0”，故编码后的发送序列为111 110 010 100 001 011 000。G并且假设接收序列为111 010 010 110 001 011 000，其中第4和第11个码元为错码。52110110110110011011011010010010101101101001001001001abcdabcd00000000000000011111111111111110010010053G将到达每个状态的两条路径的汉明距离作比较，G将距离小的一条路径保留，称为幸存路径。G若两条路径的汉明距离相同，则可以任意保存一条。序号序号路径路径对应序列对应序列汉明距

28、离汉明距离幸存否幸存否1aaaa000 000 0005否否2abca111 001 0113是是3aaab000 000 1116否否4abcb111 001 1004是是5aabc000 111 0017否否6abdc111 110 0101是是7aabd000 111 1106否否8abdd111 110 1014是是54G第2步继续考察接收序列的后继3个比特“110”。计算4条幸存路径上增加1级后的8条可能路径的汉明距离。G按照上表中的幸存路径画出的网格图。序号序号路径路径原幸存路径原幸存路径的距离的距离新增新增路径段路径段新增距新增距离离总距离总距离幸存否幸存否1abca+a3aa2

29、5否否2abdc+a1ca23是是3abca+b3ab14否否4abdc+b1cb12是是5abcb+c4bc37否否6abdd+c4dc15是是7abcb+d4bd04是是8abdd+d4dd26否否55G图中粗红线路径是汉明距离最小（等于2）的路径。G维特比解码算法的复杂度随约束长度N按指数形式2N增长。G维特比解码算法适合约束度较小（N 10）的编码。abcd011010010101001abcd1111001001101105611.8 Turbo码码z特点v一种特殊的链接码v其性能接近信息论上能够达到的最好性能z基本原理v将两种或多种简单的编码组合成复合编码v Turbo码的编码器在

30、两个并联或串联的分量码编码器之间增加交织器。vTurbo码的译码在两个分量译码器之间进行迭代译码，类似涡轮（turbo）工作，所以称为Turbo码。57z编码器的基本结构 由一对递归系统卷积码(RSCC)编码器和一个交织器组成，vRSCC编码器和卷积码编码器之间的主要区别是从移存器输出端到信息位输入端之间有反馈路径。v两个相同的RSCC编码器的输入经过一个交织器并联。v此Turbo码的输入信息位是bi，输出是bic1ic2i，故码率等于1/3。RSCC编码器交织器RSCC编码器bibic1ic2i58vRSCC编码器举例：w方框图：如下图所示w码率等于1/2的卷积码编码器，输入为bi，输出为bici。w因为输出中第1位是信息位，所以它是系统码。DDbibici59v矩阵交织器：w其基本形式是矩阵交织器G它由容量为(n-1)m比特的存储器构成。G将信号码元按行的方向输入存储器，再按列的方向输出。w若输入码元序列是：a11a12a1m a21a22a2man1anm，则输出序列是：a11a21an1a12a22an2a1manm。w交织的目的是将突发错码分散开，变成随机错码。a11a12a1ma21a22a2man1an2anm