第11章差错控制编码课件

第11章差错控制编码 111.1 概述z信道分类：从差错控制角度看v随机信道：错码的出现是随机的 v突发信道：错码是成串集中出现的v混合信道：既存在随机错码又存在突发错码 z差错控制技术的种类v 检错重发v前向纠错 v反馈校验v检错删除 2z差错控制编码：常称为纠错编码纠错编码v信息码元信息码元 kv监督码元监督码元 n-kv编码效率编码效率(简称码率码率)信息码元个数与总码元个数之比k/n v冗余度：冗余度：监督码元数(n-k)和信息码元数 k 之比。v差错控制以降低信息传输速率为代价换取提高传输可靠性。311.2 纠错编码的基本原理z分组码基本原理：v所有比特用于传送信息 3位二进制数可构成8种不同组合，若将其全部用来表示8种不同天气，“000”（晴），“001”（云），“010”（阴），“011”（雨），“100”（雪），“101”（霜），“110”（雾），“111”（雹）。w问题：其中任一码组在传输中若发生错码都将变成另一个信息码组 接收端将无法发现错误。许用码组4v部分比特用于传送信息 若在上述8种码组中只准许使用4种来传送天气，例如：“000”（晴），“001”（云），“011”（雨），“010”（阴），“101”（霜），“100”（雪），“110”（雾），“111”（雹）。w发端错一位或三位码，收端可以检测出来w信息量降低，但检错能力提高了w发端错两位码，收端检测不出来?许用码组禁用码组增大冗余度即增加监督位5v分组码的结构w将信息码分组，为每组信息码附加若干监督码的编码称为分组码分组码。w在分组码中，监督码元仅监督本码组中的信息码元。w信息位和监督位的关系，如信息位信息位监督位监督位晴晴000云云011阴阴101雨雨1106w分组码的一般结构v分组码的符号：(n,k)wN 码组的总位数，又称为码组的长度（码长），wk 码组中信息码元的数目，wn k r 码组中的监督码元数目，或称监督位数目。7v分组码的码重和码距w码重：码组中“1”的个数w码距：两个码组中对应位上不同数字的个数，又称汉明距离汉明距离。w最小码距d0：某种编码中各个码组之间距离的最小值)。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)a2a0a18v码距和检纠错能力的关系w一种编码的最小码距d0的大小直接关系着这种编码的检错和纠错能力w为检测e个错码，要求最小码距 d0 e+1w为了纠正t个错码，要求最小码距d0 2t+1w为纠正t个错码，同时检测e个错码，要求最小码距 911.4简单的实用编码z11.4.1 奇偶监督码v奇偶监督码只有一位监督位v偶监督保证码组中“1”的数目为偶数，偶监督关系式：式中a0为监督位，其他位为信息位。v奇监督保证码组中“1”的数目为奇数，奇监督关系式：1011.5 线性分组码z基本概念v代数码代数码：建立在代数学基础上的编码。v线性码线性码：信息位和监督位是由一组线性代数方程联系着的。z汉明码汉明码v定义：能够纠正1位错码且编码效率较高的一种线性分组码11v汉明码的构造原理。w监督关系式监督关系式w校正子校正子若S=0，无错码；若S=1，有错码一个校正子S不能指出错码的位置多个校正子的组合可指出错码位置增多校正子 增多监督关系式 增多监督位r个监督关系式能指示1位错码的 个可能位置指示1位错码的n种可能位置的监督位个数要求12w例：设分组码分组码(n,k)中k=4，为了纠正1位错码，由上式可知，要求监督位数 r 3。若取 r=3，则n=k+r=7。S1 S2 S3错码位错码位置置S1 S2 S3错码位错码位置置001a0101a4010a1110a5100a2111a6011a3000无错码无错码错码位置与校正子关系监督关系式13信息位信息位a6 a5 a4 a3监督位监督位a2 a1 a0信息位信息位a6 a5 a4 a3监督位监督位a2 a1 a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111由监督关系式得出的信息位与监督位接收端收到每个码组后，先计算出S1、S2和S3，再查表判断错码情况。表中所列的(7,4)汉明码的最小码距d0=3。因此，这种码能够纠正1个错码或检测2个错码。由于码率k/n=(n-r)/n=1 r/n，故当n很大和r很小时，码率接近1。可见，汉明码是一种高效码。14z线性分组码的一般原理v线性分组码的构造wH矩阵（监督阵）H AT=0T 或或A HT=0监督阵15H矩阵的性质：H的行数就是监督关系式的数目，等于监督位个数r。典型监督阵可分解为P Ir形式，P为r k阶矩阵，Ir 为r r阶单位方阵。由代数理论可知，H矩阵的各行应该是线性无关的 16wG矩阵（生成矩阵）Q为一为一k r阶矩阵，阶矩阵，Q=PT在信息位给定后，在信息位给定后，用信息位的行矩阵乘用信息位的行矩阵乘矩阵矩阵Q就产生出监督就产生出监督位位17生成阵如果找到了码的生成矩阵G，则编码的方法就完全确定了。具有IkQ形式的生成矩阵称为典型生成矩阵典型生成矩阵。系统码18G矩阵的性质：G矩阵的各行是线性无关的。G的各行本身就是一个码组。如果已有k个线性无关的码组，则可以用其作 为生成矩阵G。19w错误图样 B A=E错误图样接收码发送码20v线性分组码的性质w封闭性：封闭性：是指一种线性码中的任意两个码组之和仍为这种码中的一个码组。w两个码组(A1和A2)之间的距离（即对应位不同的数目）必定是另一个码组(A1+A2)的重量（即“1”的数目）。w码组间的最小距离就是码组的最小重量（除全“0”码组外）。2111.6 循环码z11.6.1 循环码原理v循环性：循环性：指任一码组循环移位（即将最右端的一个码元移至左端，或反之）以后，仍为该码中的一个码组。一种(7,3)循环码的全部码组(an-1 an-2 a0)码组编码组编号号信息位信息位监督位监督位码组编码组编号号信息位信息位监督位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0100000005100101120010111610111003010111071100101401110018111001022v码多项式w码组的多项式表示法把码组中各码元当作是一个多项式的系数，即一个长为n的码组表示为xn仅是码元位置的标记，不关心xn的取值。w码多项式的按模运算整数运算中的模n运算 若一个整数m可以表示为 式中，Q 整数，则在模 n 运算下，有 m p (模n)即，在模 n 运算下，一个整数m等于它被 n 除得的余数。23码多项式运算中的模运算。若一任意多项式F(x)被一 n 次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)，即 则写为 码多项式系数仍按模2 运算，即系数只取 0 和1。如，因为 xx3+1 x4+x2+1 x4+x x2+x+1注意，由于在模2运算中，用加法代替了减法24v循环码的生成矩阵Gwk个线性不相关的已知码组可构成生成矩阵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可得 25w所有码多项式T(x)都可被g(x)整除，且任意一个次数不大于(k 1)的多项式乘g(x)都是码多项式v循环码的码多项式w在循环码中，若T(x)是一个长为n的许用码组，则xiT(x)在按模xn+1运算下，也是该编码中的一个许用码组，即若 则T(x)也是该编码中的一个许用码组。26v如何寻找任一(n,k)循环码的生成多项式循环码的生成多项式应该是(xn+1)的一个(n k)次因式为了求(7,3)循环码的生成多项式g(x)需要从(x7+1)中找到一个(n k)=4次的因子 上两式都可作为生成多项式。选用的生成多项式不同，产生出的循环码码组也不同27z11.6.2 循环码的编解码方法v循环码的编码方法w编码原则从(xn+1)的因子中选一个(n-k)次多项式作为g(x)。所有码多项式T(x)都可以被g(x)整除。w编码步骤：用xn-k乘m(x)用g(x)除xn-k m(x)，得到商Q(x)和余式r(x)编出的码组T(x)为T(x)=xn-k m(x)+r(x)28v循环码的解码方法w解码要求：检错和纠错。w检错解码原理：在接收端将接收码组R(x)用原生成多项式g(x)去除，判断余式。w纠错解码原理：为了能够纠错，要求每个可纠正的错误图样必须与一个特定余式有一一对应关系。步骤如下：用生成多项式g(x)除接收码组R(x)，得出余式r(x)。按余式r(x)，用查表的方法或通过某种计算得到错误图样E(x)；从R(x)中减去E(x)，便得到已经纠正错码的原发送码组T(x)。w通常，一种编码可以有几种纠错解码方法，上述解码方法称为捕错解码法。2911.7 卷积码z非分组码概念：v卷积码是一种非分组码，更适用于前向纠错。v卷积码监督码元不仅和当前的k比特信息段有关，而且还同前面m=(N 1)个信息段有关。v约束度：一个码组中的监督码元监督的信息段的个数Nv卷积码记作(n,k,N)30z11.7.1 卷积码的基本原理v编码器原理方框图编码输出每次输入k比特1k1k1k1k 1 k2k3kNk 12nNk级移存器n个模2加法器每输入k比特旋转1周31v例：(n,k,N)=(3,1,3)卷积码编码器w方框图w设输入信息比特序列是bi-2 bi-1 bi bi+1，输入bi与输出比特ci di ei关系如下：bi-2bi输入bibi-1编码输出dicieiM2M3M132ci-2di-2ei-2ci-1di-1ei-1cidieibi-2bi1bitt输入输出虚线示出了信息位bi的监督位和各信息位之间的约束关系，约束长度nN等于9。33z11.7.2 卷积码的代数表述v卷积码也是一种线性码。v一个线性码完全由一个监督矩阵H或生成矩阵G所确定。v 监督矩阵H设上图中在第1个信息位b1进入编码器之前，各级移存器都处于“0”状态。监督位di、ei和信息位bi之间的关系可表示为：34 左式可以改写为35与11.5节公式H AT=0T对比，可以看出监督矩阵36 卷积码的H是一个有头无尾的半无穷矩阵。监督矩阵的每3列的结构是相同的，只是后3列比前3列向下移了 两行。自第7行起，每两行的左端比上两行多了3个“0”。37截短监督矩阵的结构形式如下图：H1的最左边是n列(n-k)N行的一个子矩阵，且向右的每n列均相对于前n列降低(n-k)行。截短监督矩阵一旦确定，卷积码的监督矩阵就可完全确定。H1=nn k(n k)N38此例中码的截短监督矩阵可以写成如下形式：式中 2阶单位方阵；Pi 2 1阶矩阵，i=1,2,3；O2 2阶全零方阵。39一般说来，卷积码的截短监督矩阵具有如下形式：In-k (n k)阶单位方阵；Pi (n k)k阶矩阵；On-k (n k)阶全零方阵。H1的末行称为基本监督矩阵hh=PN On-k PN-1 On-k PN-2 On-k P1 In-kh是卷积码的一个最重要的矩阵，因为只要给定了h，可完整的监督阵H 就确定了。40v生成矩阵生成矩阵G上例中的输出码元序列可以写成 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)41 此码的生成矩阵G即为上式最右矩阵：42v截短生成矩阵：类似地，也有截短生成矩阵式中 I1 一阶单位方阵；Qi 1 2阶矩阵。w与H1矩阵比较可见，Qi是矩阵Pi的转置：Qi=PiT (i=1,2,)w截短生成矩阵具有如下形式：43式中 Ik k阶单位方阵；Qi k (n k)阶矩阵；Ok k阶全零方阵。w基本生成矩阵：上式中矩阵第一行g Ik Q1 Ok Q2 Ok Q3Ok QN如果基本生成矩阵g已经给定，则可以从已知的信息位得到整个编码序列。44z11.7.3 卷积码的解码v分类：w代数解码：利用编码本身的代数结构进行解码，不考虑信道的统计特性。大数逻辑解码，又称门限解码。w概率解码：又称最大似然解码。它基于信道的统计特性和卷积码的特点进行计算。另一种概率解码方法是维特比算法。45v卷积码的几何表述w码树图：现仍以上面(3,1,3)码为例，介绍卷积码的码树 起点信息位状态 M3M2 a 0 0 b 0 1 c 1 0 d 1 1信息位信息位 11 0 1000111c1d1e1000111001110011100010101000111001110011100010101c4d4e4111000001110c2d2e22000100111011001101110010c3d3e3abcdabcdabcdabcd上半部下半部ba10aabcdabcdcdab01100146移存器前一状态移存器前一状态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状态图将当前输入信息位、移存器前一状态、移存器下一状态和输出码元之间的关系归纳于下表中47虚线表示输入信息位为“1”时状态转变的路线；实线表示输入信息位为“0”时状态转变的路线。线条旁的3位数字是编码输出比特。利用状态图可以方便地从输入序列得到输出序列。abcd000111101110010011100001按照上表中的规律，可以画出状态图如下图所示48w网格图将状态图在时间上展开，可以得到网格图如下：图中画出了5个时隙。虚线表示输入信息位为“1”时状态转变的路线；实线表示输入信息位为“0”时状态转变的路线。在第4时隙以后的网格图形完全是重复第3时隙的图形。110110110110011011011010010010101101101001001001001abcdabcd00000000000000011111111111111110010010049上图中给出了输入信息位为11010时，在网格图中的编码路径。图中示出这时的输出编码序列是：111 110 010 100 011。用网格图表示编码过程和输入输出关系比码树图更为简练。abcdabcd11001000111110050v维特比解码算法w基本原理将接收到的信号序列和所有可能的发送信号序列比较，选择其中汉明距离最小的序列，认为是当前发送信号序列。发送的序列越长，存储量越大。维特比算法对此作了简化，使之能够实用。w例：(3,1,3)卷积码设发送信息位为1101，为使移存器的信息位全部移出，在信息位后面加入3个“0”，故编码后的发送序列为111 110 010 100 001 011 000。并且假设接收序列为111 010 010 110 001 011 000，其中第4和第11个码元为错码。51110110110110011011011010010010101101101001001001001abcdabcd00000000000000011111111111111110010010052将到达每个状态的两条路径的汉明距离作比较，将距离小的一条路径保留，称为幸存路径。若两条路径的汉明距离相同，则可以任意保存一条。序号序号路径路径对应序列对应序列汉明距离汉明距离幸存否幸存否1aaaa000 000 0005否否2abca111 001 0113是是3aaab000 000 1116否否4abcb111 001 1004是是5aabc000 111 0017否否6abdc111 110 0101是是7aabd000 111 1106否否8abdd111 110 1014是是53第2步继续考察接收序列的后继3个比特“110”。计算4条幸存路径上增加1级后的8条可能路径的汉明距离。按照上表中的幸存路径画出的网格图。序号序号路径路径原幸存路径原幸存路径的距离的距离新增新增路径段路径段新增距离新增距离总距离总距离幸存否幸存否1abca+a3aa25否否2abdc+a1ca23是是3abca+b3ab14否否4abdc+b1cb12是是5abcb+c4bc37否否6abdd+c4dc15是是7abcb+d4bd04是是8abdd+d4dd26否否54图中粗红线路径是汉明距离最小（等于2）的路径。维特比解码算法的复杂度随约束长度N按指数形式2N增长。维特比解码算法适合约束度较小（N 10）的编码。abcd011010010101001abcd1111001001101105511.8 Turbo码码z特点v一种特殊的链接码v其性能接近信息论上能够达到的最好性能z基本原理v将两种或多种简单的编码组合成复合编码v Turbo码的编码器在两个并联或串联的分量码编码器之间增加交织器。vTurbo码的译码在两个分量译码器之间进行迭代译码，类似涡轮（turbo）工作，所以称为Turbo码。56z编码器的基本结构 由一对递归系统卷积码(RSCC)编码器和一个交织器组成，vRSCC编码器和卷积码编码器之间的主要区别是从移存器输出端到信息位输入端之间有反馈路径。v两个相同的RSCC编码器的输入经过一个交织器并联。v此Turbo码的输入信息位是bi，输出是bic1ic2i，故码率等于1/3。RSCC编码器交织器RSCC编码器bibic1ic2i57vRSCC编码器举例：w方框图：如下图所示w码率等于1/2的卷积码编码器，输入为bi，输出为bici。w因为输出中第1位是信息位，所以它是系统码。DDbibici58p经常不断地学习,你就什么都知道。你知道得越多,你就越有力量pStudyConstantly,AndYouWillKnowEverything.TheMoreYouKnow,TheMorePowerfulYouWillBe写在最后Thank You在别人的演说中思考，在自己的故事里成长Thinking In Other PeopleS Speeches，Growing Up In Your Own Story讲师：XXXXXX XX年XX月XX日