《第11章差错控制编码课件.ppt》由会员分享，可在线阅读，更多相关《第11章差错控制编码课件.ppt（59页珍藏版）》请在三一办公上搜索。
1、1,通信原理,第11章差错控制编码,2,11.1 概述信道分类：从差错控制角度看随机信道：错码的出现是随机的 突发信道：错码是成串集中出现的混合信道：既存在随机错码又存在突发错码 差错控制技术的种类 检错重发前向纠错 反馈校验检错删除,3,差错控制编码：常称为纠错编码信息码元 k监督码元 n-k编码效率(简称码率)信息码元个数与总码元个数之比k/n 冗余度：监督码元数(n-k)和信息码元数 k 之比。差错控制以降低信息传输速率为代价换取提高传输可靠性。,4,11.2 纠错编码的基本原理分组码基本原理：所有比特用于传送信息 3位二进制数可构成8种不同组合，若将其全部用来表示8种不同天气，“000
2、”（晴），“001”（云），“010”（阴），“011”（雨），“100”（雪），“101”（霜），“110”（雾），“111”（雹）。问题：其中任一码组在传输中若发生错码都将变成另一个信息码组 接收端将无法发现错误。,许用码组,5,部分比特用于传送信息 若在上述8种码组中只准许使用4种来传送天气，例如：“000”（晴），“001”（云），“011”（雨），“010”（阴），“101”（霜），“100”（雪），“110”（雾），“111”（雹）。发端错一位或三位码，收端可以检测出来信息量降低，但检错能力提高了发端错两位码，收端检测不出来?,许用码组,禁用码组,增大冗余度即增加监督位,6,分组码
3、的结构将信息码分组，为每组信息码附加若干监督码的编码称为分组码。在分组码中，监督码元仅监督本码组中的信息码元。信息位和监督位的关系，如,7,分组码的一般结构分组码的符号：(n,k)N 码组的总位数，又称为码组的长度（码长），k 码组中信息码元的数目，n k r 码组中的监督码元数目，或称监督位数目。,8,分组码的码重和码距码重：码组中“1”的个数码距：两个码组中对应位上不同数字的个数，又称汉明距离。最小码距d0：某种编码中各个码组之间距离的最小值)。码距的几何意义每个码组的3个码元的值(a1,a2,a3)就是此立方体各顶点的坐标。码距概念在图中对应于各顶点之间沿立方体各边行走的几何距离。,9,
4、码距和检纠错能力的关系一种编码的最小码距d0的大小直接关系着这种编码的检错和纠错能力为检测e个错码，要求最小码距 d0 e+1为了纠正t个错码，要求最小码距d0 2t+1为纠正t个错码，同时检测e个错码，要求最小码距,10,11.4简单的实用编码11.4.1 奇偶监督码奇偶监督码只有一位监督位偶监督保证码组中“1”的数目为偶数，偶监督关系式：式中a0为监督位，其他位为信息位。奇监督保证码组中“1”的数目为奇数，奇监督关系式：,11,11.5 线性分组码基本概念代数码：建立在代数学基础上的编码。线性码：信息位和监督位是由一组线性代数方程联系着的。汉明码定义：能够纠正1位错码且编码效率较高的一种线
5、性分组码,12,汉明码的构造原理。监督关系式校正子若S=0，无错码；若S=1，有错码一个校正子S不能指出错码的位置多个校正子的组合可指出错码位置增多校正子 增多监督关系式 增多监督位r个监督关系式能指示1位错码的 个可能位置指示1位错码的n种可能位置的监督位个数要求,13,例：设分组码(n,k)中k=4，为了纠正1位错码，由上式可知，要求监督位数 r 3。若取 r=3，则n=k+r=7。,错码位置与校正子关系,监督关系式,14,由监督关系式得出的信息位与监督位,接收端收到每个码组后，先计算出S1、S2和S3，再查表判断错码情况。,表中所列的(7,4)汉明码的最小码距d0=3。因此，这种码能够纠
6、正1个错码或检测2个错码。由于码率k/n=(n-r)/n=1 r/n，故当n很大和r很小时，码率接近1。可见，汉明码是一种高效码。,15,线性分组码的一般原理线性分组码的构造H矩阵（监督阵）,H AT=0T 或A HT=0,监督阵,16,H矩阵的性质：H的行数就是监督关系式的数目，等于监督位个数r。典型监督阵可分解为P Ir形式，P为r k阶矩阵，Ir 为r r阶单位方阵。由代数理论可知，H矩阵的各行应该是线性无关的,17,G矩阵（生成矩阵）,Q为一k r阶矩阵，Q=PT在信息位给定后，用信息位的行矩阵乘矩阵Q就产生出监督位,18,生成阵,如果找到了码的生成矩阵G，则编码的方法就完全确定了。具
7、有IkQ形式的生成矩阵称为典型生成矩阵。,系统码,19,G矩阵的性质：G矩阵的各行是线性无关的。G的各行本身就是一个码组。如果已有k个线性无关的码组，则可以用其作 为生成矩阵G。,20,错误图样,B A=E,错误图样,接收码,发送码,21,线性分组码的性质封闭性：是指一种线性码中的任意两个码组之和仍为这种码中的一个码组。两个码组(A1和A2)之间的距离（即对应位不同的数目）必定是另一个码组(A1+A2)的重量（即“1”的数目）。码组间的最小距离就是码组的最小重量（除全“0”码组外）。,22,11.6 循环码11.6.1 循环码原理循环性：指任一码组循环移位（即将最右端的一个码元移至左端，或反之
8、）以后，仍为该码中的一个码组。一种(7,3)循环码的全部码组(an-1 an-2 a0),23,码多项式码组的多项式表示法把码组中各码元当作是一个多项式的系数，即一个长为n的码组表示为xn仅是码元位置的标记，不关心xn的取值。码多项式的按模运算整数运算中的模n运算 若一个整数m可以表示为 式中，Q 整数，则在模 n 运算下，有 m p(模n)即，在模 n 运算下，一个整数m等于它被 n 除得的余数。,24,码多项式运算中的模运算。若一任意多项式F(x)被一 n 次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)，即则写为码多项式系数仍按模2 运算，即系数只取 0 和1。如，因为
9、,注意，由于在模2运算中，用加法代替了减法,25,循环码的生成矩阵Gk个线性不相关的已知码组可构成生成矩阵G用g(x)表示(n,k)循环码中前(k-1)位皆为“0”的码组，则g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是码组，且是线性无关的。(左移)g(x)必须是一个常数项不为“0”的(n-k)次多项式，而且是(n,k)码中次数为(n k)的唯一多项式（线性无关）唯一的(n k)次多项式g(x)为码的生成多项式循环码的生成矩阵G可得,26,所有码多项式T(x)都可被g(x)整除，且任意一个次数不大于(k 1)的多项式乘g(x)都是码多项式循环码的码多项式在循环码中，若T(x)是
10、一个长为n的许用码组，则xiT(x)在按模xn+1运算下，也是该编码中的一个许用码组，即若 则T(x)也是该编码中的一个许用码组。,27,如何寻找任一(n,k)循环码的生成多项式循环码的生成多项式应该是(xn+1)的一个(n k)次因式为了求(7,3)循环码的生成多项式g(x)需要从(x7+1)中找到一个(n k)=4次的因子,上两式都可作为生成多项式。选用的生成多项式不同，产生出的循环码码组也不同,28,11.6.2 循环码的编解码方法循环码的编码方法编码原则从(xn+1)的因子中选一个(n-k)次多项式作为g(x)。所有码多项式T(x)都可以被g(x)整除。编码步骤：用xn-k乘m(x)用
11、g(x)除xn-k m(x)，得到商Q(x)和余式r(x)编出的码组T(x)为T(x)=xn-k m(x)+r(x),29,循环码的解码方法解码要求：检错和纠错。检错解码原理：在接收端将接收码组R(x)用原生成多项式g(x)去除，判断余式。纠错解码原理：为了能够纠错，要求每个可纠正的错误图样必须与一个特定余式有一一对应关系。步骤如下：用生成多项式g(x)除接收码组R(x)，得出余式r(x)。按余式r(x)，用查表的方法或通过某种计算得到错误图样E(x)；从R(x)中减去E(x)，便得到已经纠正错码的原发送码组T(x)。通常，一种编码可以有几种纠错解码方法，上述解码方法称为捕错解码法。,30,1
12、1.7 卷积码非分组码概念：卷积码是一种非分组码，更适用于前向纠错。卷积码监督码元不仅和当前的k比特信息段有关，而且还同前面m=(N 1)个信息段有关。约束度：一个码组中的监督码元监督的信息段的个数N卷积码记作(n,k,N),31,11.7.1 卷积码的基本原理编码器原理方框图,32,例：(n,k,N)=(3,1,3)卷积码编码器方框图设输入信息比特序列是bi-2 bi-1 bi bi+1，输入bi与输出比特ci di ei关系如下：,33,虚线示出了信息位bi的监督位和各信息位之间的约束关系，约束长度nN等于9。,34,11.7.2 卷积码的代数表述卷积码也是一种线性码。一个线性码完全由一个
13、监督矩阵H或生成矩阵G所确定。监督矩阵H设上图中在第1个信息位b1进入编码器之前，各级移存器都处于“0”状态。监督位di、ei和信息位bi之间的关系可表示为：,35,左式可以改写为,36,与11.5节公式H AT=0T对比，可以看出监督矩阵,37,卷积码的H是一个有头无尾的半无穷矩阵。监督矩阵的每3列的结构是相同的，只是后3列比前3列向下移了 两行。自第7行起，每两行的左端比上两行多了3个“0”。,38,截短监督矩阵的结构形式如下图：H1的最左边是n列(n-k)N行的一个子矩阵，且向右的每n列均相对于前n列降低(n-k)行。截短监督矩阵一旦确定，卷积码的监督矩阵就可完全确定。,39,此例中码的
14、截短监督矩阵可以写成如下形式：式中 2阶单位方阵；Pi 2 1阶矩阵，i=1,2,3；O2 2阶全零方阵。,40,一般说来，卷积码的截短监督矩阵具有如下形式：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 就确定了。,41,生成矩阵G上例中的输出码元序列可以写成 b1 d1 e1 b2 d2 e2 b3 d3 e3 b4 d4 e4=b1 b1 b1 b2 b2(b2+b1)b3(b3+b1)
15、(b3+b2+b1)b4(b4+b2)(b4+b3+b2),42,此码的生成矩阵G即为上式最右矩阵：,43,截短生成矩阵：类似地，也有截短生成矩阵式中I1 一阶单位方阵；Qi 1 2阶矩阵。与H1矩阵比较可见，Qi是矩阵Pi的转置：Qi=PiT(i=1,2,)截短生成矩阵具有如下形式：,44,式中 Ik k阶单位方阵；Qi k(n k)阶矩阵；Ok k阶全零方阵。基本生成矩阵：上式中矩阵第一行g Ik Q1 Ok Q2 Ok Q3Ok QN如果基本生成矩阵g已经给定，则可以从已知的信息位得到整个编码序列。,45,11.7.3 卷积码的解码分类：代数解码：利用编码本身的代数结构进行解码，不考虑信
16、道的统计特性。大数逻辑解码，又称门限解码。概率解码：又称最大似然解码。它基于信道的统计特性和卷积码的特点进行计算。另一种概率解码方法是维特比算法。,46,卷积码的几何表述码树图：现仍以上面(3,1,3)码为例，介绍卷积码的码树,47,状态图将当前输入信息位、移存器前一状态、移存器下一状态和输出码元之间的关系归纳于下表中,48,虚线表示输入信息位为“1”时状态转变的路线；实线表示输入信息位为“0”时状态转变的路线。线条旁的3位数字是编码输出比特。利用状态图可以方便地从输入序列得到输出序列。,按照上表中的规律，可以画出状态图如下图所示,49,网格图将状态图在时间上展开，可以得到网格图如下：图中画出
17、了5个时隙。虚线表示输入信息位为“1”时状态转变的路线；实线表示输入信息位为“0”时状态转变的路线。在第4时隙以后的网格图形完全是重复第3时隙的图形。,50,上图中给出了输入信息位为11010时，在网格图中的编码路径。图中示出这时的输出编码序列是：111 110 010 100 011。用网格图表示编码过程和输入输出关系比码树图更为简练。,51,维特比解码算法基本原理将接收到的信号序列和所有可能的发送信号序列比较，选择其中汉明距离最小的序列，认为是当前发送信号序列。发送的序列越长，存储量越大。维特比算法对此作了简化，使之能够实用。例：(3,1,3)卷积码设发送信息位为1101，为使移存器的信息
18、位全部移出，在信息位后面加入3个“0”，故编码后的发送序列为111 110 010 100 001 011 000。并且假设接收序列为111 010 010 110 001 011 000，其中第4和第11个码元为错码。,52,53,将到达每个状态的两条路径的汉明距离作比较，将距离小的一条路径保留，称为幸存路径。若两条路径的汉明距离相同，则可以任意保存一条。,54,第2步继续考察接收序列的后继3个比特“110”。计算4条幸存路径上增加1级后的8条可能路径的汉明距离。按照上表中的幸存路径画出的网格图。,55,图中粗红线路径是汉明距离最小（等于2）的路径。维特比解码算法的复杂度随约束长度N按指数形
19、式2N增长。维特比解码算法适合约束度较小（N 10）的编码。,56,11.8 Turbo码特点一种特殊的链接码其性能接近信息论上能够达到的最好性能基本原理将两种或多种简单的编码组合成复合编码 Turbo码的编码器在两个并联或串联的分量码编码器之间增加交织器。Turbo码的译码在两个分量译码器之间进行迭代译码，类似涡轮（turbo）工作，所以称为Turbo码。,57,编码器的基本结构 由一对递归系统卷积码(RSCC)编码器和一个交织器组成，RSCC编码器和卷积码编码器之间的主要区别是从移存器输出端到信息位输入端之间有反馈路径。两个相同的RSCC编码器的输入经过一个交织器并联。此Turbo码的输入信息位是bi，输出是bic1ic2i，故码率等于1/3。,58,RSCC编码器举例：方框图：如下图所示码率等于1/2的卷积码编码器，输入为bi，输出为bici。因为输出中第1位是信息位，所以它是系统码。,59,矩阵交织器：其基本形式是矩阵交织器它由容量为(n-1)m比特的存储器构成。将信号码元按行的方向输入存储器，再按列的方向输出。若输入码元序列是：a11a12a1m a21a22a2man1anm，则输出序列是：a11a21an1a12a22an2a1manm。交织的目的是将突发错码分散开，变成随机错码。,
