循环码BCH码卷积码.ppt

1,10.6 循环码10.6.1 循环码的概念：循环性是指任一码组循环一位后仍然是该编码中的一个码组。例：一种(7,3)循环码的全部码组如下 表中第2码组向右移一位即得到第5码组；第5码组向右移一位即得到第7码组。,2,一般情况 若(an-1 an-2 a0)是循环码的一个码组，则循环移位后的码组：(an-2 an-3 a0 an-1)(an-3 an-4 an-1 an-2)(a0 an-1 a2 a1)仍然是该编码中的码组。多项式表示法一个长度为n的码组(an-1 an-2 a0)可以表示成 上式中x 的值没有任何意义，仅用它的幂代表码元的位置。例：码组1 1 0 0 1 0 1可以表示为,3,10.6.2 循环码的运算 整数的按模运算在整数运算中，有模n运算。例如，在模2运算中，有1+1=2 0(模2)，1+2=3 1(模2)，2 3=6 0(模2)等等。一般说来，若一个整数m可以表示为式中，Q为整数，则在模n运算下，有m p(模n)所以，在模n运算下，一个整数m等于它被n除得的余数。,4,码多项式的按模运算 若任意一个多项式F(x)被一个n次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)，即则在按模N(x)运算下，有这时，码多项式系数仍按模2运算。例1：x3被(x3+1)除，得到余项1，即 例2：因为xx3+1 x4+x2+1x4+x x2+x+1 在模2运算中加法和减法一样。,5,循环码的数学表示法 在循环码中，设T(x)是一个长度为n的码组，若则T(x)也是该编码中的一个码组。上式中的T(x)正是码组T(x)向左循环移位 i 次的结果。例：一循环码为1100101，即 若给定 i=3，则有 上式对应的码组为0101110，它正是T(x)向左移3位的结果。结论：一个长为n的循环码必定为按模(xn+1)运算的一个余式。,6,循环码的生成 有了生成矩阵G，就可以由k个信息位得出整个码组：例：式中，生成矩阵G的每一行都是一个码组。因此，若能找到 k 个已知的码组，就能构成矩阵G。如前所述，这k个已知码组必须是线性不相关的。在循环码中，一个(n,k)码有2k个不同的码组。若用g(x)表示其中前(k-1)位皆为“0”的码组，则g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是码组，而且这k个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵G。,7,在循环码中除全“0”码组外，再没有连续k位均为“0”的码组。否则，在经过若干次循环移位后将得到k位信息位全为“0”，但监督位不全为“0”的一个码组。这在线性码中显然是不可能的。因此，g(x)必须是一个常数项不为“0”的(n-k)次多项式，而且这个g(x)还是这种(n,k)码中次数为(n k)的唯一一个多项式。因为如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码组多项式的次数将小于(n k)，即连续“0”的个数多于(k 1)。显然，这是与前面的结论矛盾的。我们称这唯一的(n k)次多项式g(x)为码的生成多项式。一旦确定了g(x)，则整个(n,k)循环码就被确定了。,8,生多项式的性质：（1）g(x)是一(n-k)次多项式；（2）g(x)的常数项不为0；（3）g(x)必须是（xn+1）的一个因子。,9,因此，循环码的生成矩阵G可以写成例：上表中的编码为(7,3)循环码，n=7,k=3,n k=4，其中唯一的一个(n k)=4次码多项式代表的码组是第二码组0010111，与它对应的码多项式，即生成多项式，为g(x)=x4+x2+x+1。,10,g(x)=x4+x2+x+1 即“1 0 1 1 1”将此g(x)代入上矩阵，得到 或上式不符合G=IkQ形式，所以它不是典型生成矩阵。但它经过线性变换后，不难化成典型阵。此循环码组的多项式表示式T(x)：上式表明，所有码多项式T(x)都能够被g(x)整除，而且任意一个次数不大于(k 1)的多项式乘g(x)都是码多项式。,11,寻求码生成多项式 因为任意一个循环码T(x)都是g(x)的倍式，故它可以写成T(x)=h(x)g(x)而生成多项式g(x)本身也是一个码组，即有 T(x)=g(x)由于码组T(x)是一个(n k)次多项式，故xk T(x)是一个n次多项式。由可知，xk T(x)在模(xn+1)运算下也是一个码组，所以有上式左端分子和分母都是n次多项式，故相除的商式Q(x)=1。因此，上式可以写成,12,将 T(x)=h(x)g(x)和 T(x)=g(x)代入化简后，得到上式表明，生成多项式g(x)应该是(xn+1)的一个因子。例：(x7+1)可以分解为为了求出(7,3)循环码的生成多项式 g(x)，需要从上式中找到一个(n k)=4次的因子。这样的因子有两个，即以上两式都可以作为生成多项式。选用的生成多项式不同，产生出的循环码码组也不同。,13,10.6.3 循环码的编码方法用xn-k乘m(x)。这一运算实际上是在信息码后附加上(n k)个“0”。例如，信息码为110，它写成多项式为m(x)=x2+x。当n k=7 3=4时，xn-k m(x)=x4(x2+x)=x6+x5，它表示码组1100000。用g(x)除xn-k m(x)，得到商Q(x)和余式r(x)，即有例：若选定g(x)=x4+x2+x+1，则有 上式是用码多项式表示的运算。它和下式等效：编出的码组T(x)为：T(x)=xn-k m(x)+r(x)在上例中，T(x)=1100000+101=1100101,14,10.6.4 循环码的解码方法在检错时：当接收码组没有错码时，接收码组R(x)必定能被g(x)整除，即下式中余项r(x)应为零；否则，有误码。当接收码组中的错码数量过多，超出了编码的检错能力时，有错码的接收码组也可能被g(x)整除。这时，错码就不能检出了。在纠错时：用生成多项式g(x)除接收码组R(x)，得出余式r(x)。按照余式r(x)，用查表的方法或计算方法得出错误图样E(x)。从R(x)中减去E(x)，便得到已经纠正错码的原发送码组T(x)。,15,.BCH码BCH码是具有纠正多个随机差错功能的循环码，它是循环码的一个重要子类。这种码是建立在现代代数理论基础之上的，数学结构严谨，在译码同步等方面有许多独特的优点，故在数字微波以及数字卫星传输设备中常使用这种能纠正多重错误的BCH码来降低传输误码率。BCH码可分为两类，一类是原本BCH码，另一类是非原本BCH码。原本BCH码的特点是码长为2 m1(m为正整数)，其生成多项式是由若干最高次数为m的因式相乘构成的，且具有如下形式：,16,(2-5)其中，t为纠错个数，mi(t)为最小多项式，LCM代表最小公倍式。具有上述特点的循环码就是BCH码，其最小码距d2t1(在一种编码中，任意两个许用码组之间的对应位上所具有的最小不同二进制码元数，称为最小码距)。由此可见，一个(2m1，k)循环码的2m1k阶生成多项式必定是由x2m11的全部或部分因式组成的。而非原本BCH码的生成多项式中却不包含这种原本多项式，并且码长n是2m1的一个因子，即2m1一定是码长n的倍数。,17,下面以码长为15的BCH码为例来进行说明。可见此时m=4(24115)，即表示最高次数为4。由xn1的因式分解可知：,18,其中，m7(x)是m1(x)的反多项式(若有限域上的m次多项式为则称为f(x)的反多项式)。对于(15，5)BCH码的生成多项式为,19,可见它能纠正3(由2t1=5得到)个随机差错。,20,BCH码是能够纠正多个随机错码的循环码。BCH码分为两类：本原BCH码和非本原BCH码。本原BCH码：码长n=2m 1(m 3，任意正整数)，它的生成多项式g(x)中含有最高次数为m次的本原多项式；非本原BCH码：码长n是(2m 1)的一个因子，它的生成多项式g(x)中不含有最高次数为m的本原多项式。BCH码的工程设计：可以用查表法找到所需的生成多项式。例：二进制非本原BCH码的生成多项式系数 表中g(x)是用8进制数字表示的；t 为纠错能力。,21,常用BCH码：戈莱(Golay)码：(23,12)非本原BCH码，它能纠正3个随机错码，并且容易解码。扩展BCH码(n+1,k)：BCH码的长度为奇数。在应用中，为了得到偶数长度的码，并增大检错能力，可以在BCH码生成多项式中乘上一个因式(x+1)，从而得到扩展BCH码(n+1,k)。扩展BCH码已经不再具有循环性。扩展戈莱码(24,12)：其最小码距为8，码率为1/2，能够纠正3个错码和检测4个错码。,22,前面所介绍的BCH码都是二进制的，即BCH码的每一个码元(元素)的取值为0或1。如果BCH中的每一个元素用多进制表示的话，例如2 m进制，那么BCH中的每个元素就可以用一个m位的二进制码组表示，我们称这种多进制的BCH码为RS码。例如对于其信息位为10011的(15，5)BCH码序列是。如果进行RS编码，取m=2，即每一位将用一个2位的二进制码表示(若用01代表“0”码，用10代表“1”码)，那么输出的RS码就是。可见，当以2比特为一组计算，一旦出现00或11或不符合循环码的循环关系时，则可以断定，该序列出现差错。因此，RS码是一个具有很强的纠错能力的多进制码。,23,一个纠t个符号错误的(n，k)RS码的参数如下：码长 n=2m1符号 或 m(2m1)比特信息段k符号或 km比特 监督段nk=2t符号或 m(nk)比特 最小码距d=2t1符号或 m(2t1)比特RS码特别适合于纠正突发性错误，它可以纠正的差错长度(第1位误码与最后1位误码之间的比特序列)如下：总长度为b1=(t1)m1比特的1个突发差错；总长度为b2=(t3)m3比特的2个突发差错；总长度为bi=(t2i1)m2i1比特的i个突发差错。,24,10.6.7 RS码RS码：是q进制BCH码的一个特殊子类，并且具有很强的纠错能力。RS码的主要优点：它是多进制纠错编码，所以特别适合用于多进制调制的场合；它能够纠正t个q位二进制错码，即能够纠正不超过q个连续的二进制错码，所以适合在衰落信道中纠正突发性错码。,25,10.7 卷积码卷积码的特点：监督码元不仅和当前的k比特信息段有关，而且还同前面m=(N 1)个信息段有关。将N称为码组的约束度。将卷积码记作(n,k,m)，其码率为k/n。,26,卷积码的编码一般原理方框图,27,卷积码编码器的实例方框图：(n,k,m)=（3,1,2）每当输入1比特时，此编码器输出3比特c1c2 c3：编码器的工作状态,28,10.7.2 卷积码的解码码树搜索法：(3,1,2)卷积码的码树图此法不实用：因为随信息位增多，分支数目按指数规律增长,29,状态图和网格图移存器状态和输入输出码元的关系状态图,30,(3,1,2)卷积码网格图网格图中的编码路径举例输入信息位为11010时输出编码序列是：111 110 010 100 011,31,维特比算法基本原理：将接收到的序列和所有可能的发送序列作比较，选择其中汉明距离最小的序列当作是现在的发送序列例：设卷积码为(n,k,m)=(3,1,2)码 现在的发送信息位为1101为了使移存器中的信息位全部移出，在信息位后面加入了3个“0”，即1101000编码后的发送序列：111 110 010 100 001 011 000接收序列：111 010 010 110 001 011 000(红色为错码)由于这是一个(3,1,2)卷积码，发送序列的约束度为N=m+1 3，所以首先需考察3个信息段，即考察3n 9比特，即接收序列前9位“111 010 010”。,32,解码第1步由网格图可见，沿路径每一级有4种状态a,b,c和d。每种状态只有两条路径可以到达。故4种状态共有8条到达路径。比较网格图中的这8条路径和接收序列之间的汉明距离。例如，由出发点状态a经过3级路径后到达状态a的两条路径中上面一条为“000 000 000”。它和接收序列“111 010 010”的汉明距离等于5；下面一条为“111 001 011”,它和接收序列的汉明距离等于3。,33,将这8个比较结果列表如下：比较到达每个状态的两条路径的汉明距离，将距离小的一条路径保留，称为幸存路径。这样，就剩下4条路径了，即表中第2,4,6和8条路径。,34,解码第2步：继续考察接收序列中的后继3个比特“110”计算4条幸存路径上增加1级后的8条可能路径的汉明距离。计算结果列于下表中。表中总距离最小为2，其路径是abdc+b，相应序列为111 110 010 100。它和发送序列相同，故对应发送信息位1101。,35,按照上表中的幸存路径画出的网格图示于下图中。图中粗线路径是距汉明离最小（等于2）的路径。,36,在编码时，信息位后面加了3个“0”。若把这3个“0”仍然看作是信息位，则可以按照上述算法继续解码。这样得到的幸存路径网格图示于下图中。图中的粗线仍然是汉明距离最小的路径。,37,若已知这3个码元是（为结尾而补充的）“0”，则在解码时就预先知道在接收这3个“0”码元后，路径必然应该回到状态a。而由图可见，只有两条路径可以回到a状态。所以，这时上图可以简化成：,38,在上例中卷积码的约束度为N=3，需要存储和计算8条路径的参量。由此可见，维特比算法的复杂度随约束度N按指数形式2N增长。故维特比算法适合约束度较小（N 10）的编码。对于约束度大的卷积码，可以采用其他解码算法，,39,10.8 Turbo码和LDPC码Turbo码基本原理：复合编码：将两种或多种简单的编码组合成复合编码。链接码：链接码是复合编码的一种，它包括一个内（部）码和一个外（部）码，如下图所示：内码是二进制分组码或卷积码，而典型的外码则是多进制的RS码。Turbo码：是一种特殊的链接码。它在两个并联或串联的编码器之间增加一个交织器，使之具有很大的码组长度和在低信噪比条件下得到接近理想的性能。,40,Turbo码的基本结构编码器：由一对递归系统卷积码（RSCC）编码器和一个交织器组成。输入信息位是bi，输出是bic1ic2i，故码率等于1/3。RSCC编码器：和前面讨论的卷积码编码器之间的主要区别是从移存器输出到信息位输入端之间有反馈路径：上图为码率等于1/2的RSCC编码器,41,交织器：基本形式是矩阵交织器。交织目的：将集中出现的突发错码分散，变成随机错码交织原理：交织器由容量为(n-1)m比特的存储器构成。码元按行的方向输入存储器，再按列的方向输出。,42,卷积交织器举例,43,卷积交织法优点：延迟时间短和需要的存储容量小。端到端的总延迟时间和两端所需的总存储容量均为k(N+1)N个码元，是矩阵交织法的一半。Turbo码的性能：由此曲线可以看到，交织器容量大时误码率低，这是因为交织范围大可以使交织器输入码元得到更好的随机化。,44,LDPC码LDPC码的全称：低密度奇偶校验(Low-Density Parity-Check)码。LDPC码的特点：是线性分组码；它和Turbo码都是复合码，两者的性能也接近；两者的解码延迟时间都相当长；比Turbo码的解码简单，更容易实现。,45,LDPC码的基本原理：LDPC码和普通的奇偶监督码一样，可以由n列m行的奇偶监督矩阵H确定。n是码长，m是校正子个数。LDPC码的H矩阵和普通奇偶监督码的H矩阵不同：首先，它是一个稀疏矩阵，即其中“1”的个数很少，或者说密度很低。设H矩阵每列有j个“1”，每行有k个“1”，则应有j m，k n，且j 3。其次，LDPC码的H矩阵的任意两行的元素不能在相同位置上为“1”，即H矩阵中没有四角由“1”构成的矩形。在编码时设计好H矩阵后，由H矩阵可以导出生成矩阵G。这样，对于给定的信息位不难算出码组。,46,LDPC码的解码方法：和一般的奇偶监督码的解码方法不同。基本的解码算法称为置信传播算法(Belief Propagation Algorithm)，通常简称BP算法。这种算法实质上是求最大后验概率，但是需要进行多次迭代运算，逐步逼近最优的解码值。,47,10.9 小结,