第8讲 信道编码：卷积码

信道编码BCH码是一类能纠正多个随机错误的循环码其生成多项式为：其中mi(x)为素多项式，t为纠错个数，LCM表示取最小公倍数，最小码距d≥2t+1BCH码分为两种：1）本原BCH码：码长n=2m-12）非本原BCH码：码长n为2m-1的因子其中m表示素多项式的次数1321()(),(),,()tgxLCMmxmxmx多项式的序号英文字母的含义：ABCD表示本原多项式；EFGH表示非本原多项式多项式系数的八进制形式BCH码的构造例如，(15,5)BCH码可纠正3个错误，确定其生成多项式1）t=3，所以d≥72）n=15，即2m–1=15，所以m=43）查既约多项式表可知4阶多项式分别有：m1(x)=(23)8=010011=x4+x+1m3(x)=(37)8=011111=x4+x3+x2+x+1m5(x)=(07)8=000111=x2+x+1g(x)=LCM[m1(x),m3(x),m5(x)]=x10+x8+x5+x4+x2+x+1非本原BCH码当码组长度为23，其中信息位占12的非本原BCH码称为格雷码，其生成多项式：(5343)8=101011100011，g1(x)=x11+x9+x7+x6+x5+x+1其逆多项式g2(x)=x11+x10+x6+x5+x4+x2+x+1也是生成多项式且有：x23+1=(x+1)g1(x)g2(x)格雷码是除汉明码外，迄今为止唯一的一个完备码01231123122323232322CCCCn-k位的校正子与误码不超过t个的所有错误图样一一对应n位长的码组中有i个误码的错误图样的数目n-k位长的校正子的数目卷积码又名连环码，是一种非线性码，卷积码定义：1）将信息序列分成长度为k的子组2）然后编成长为n的子码，而监督码元长为n-k3）监督码元不仅与本子码的k个信息码元有关，而且还与前N-1个子组有关，即各子码内的监督码元不仅对本子码有监督作用，而且还对前面N–1个子组内的信息有监督作用一般用(n,k,N)表示卷积码，其中n表示码组长度，k表示编码的码元数，N表示约束长度卷积码的编码器一般有k个输入位、n个输出位，具有m=N–1级移位寄存器构成的记忆系统如(2,1,3)卷积码，码长为n=2，信息位即输入码元k=1，约束长度N=3的编码器，其编码器由2个移位寄存器和两个模2加法器组成ju2ju1ju输出序列输入序列1g2g1c2c卷积码的解析表示—延时多项式编码器中输入、输出序列可表示为延时算子x的多项式。比如输入序列101110…表达为：x的幂次表示相对于时间起点的单位延时数目，一般情况下输入序列可表示为：01234234()101111uxxxxxxxxx0123401234()uxuxuxuxuxuxju2ju1ju输出序列输入序列1g2g1c2c同样可以用x延时算子表达式表示各输入点与模2加法器连接关系，若某输入点与某个模2加法器相连，则多项式中的系数为1，否则为0。以(2,1,3)卷积码编码器为例01210122()111()101gxxxxgxxxx2122()1()1gxxxgxx通常称这两个多项式为生成多项式。将所要编码的信息序列与生成多项式相乘即可得到卷积码编码序列以输入序列1101110…为例：则两个输出端c1c2以及输出序列c分别为：234511234522()()(1)(1)()()(1)(1)cgxuxxxxxxxcgxuxxxxxx11,01,11,222,02,12,21,02,01,12,11,22,2(,,,)10000101(,,,)11101011(,,,,,,)1101010001100111ccccccccccccccc一般常用二进制序列表示生成多项式，即：则上例为：211222()1(111)()1(101)gxxxggxxg234511234522()()(1)(1)(111)(1101110)10000101()()(1)(1)(101)(1101110)11101011cgxuxxxxxxxcgxuxxxxxx1,02,01,12,11,22,2(,,,,,,)1101010001100111ccccccc卷积码的解析表示—半无限矩阵在半无限矩阵表示方法中输入的信息序列和输出序列都用半无限矢量表示：当第一个信息比特输入时，假设移位寄存器起始状态为全0，则输出的两个输出比特为：当第二个信息比特输入时，前一比特右移一位，则输出的两个输出比特为：当第三个信息比特输入时，前两比特又移一位，则输出的两个输出比特为：输入第k个信息比特时，输出为：012uuuu1,002,00,cucu1,02,01,12,11,22,2ccccccc1,1012,11,cuucu1,20122,202,cuuucuu1,11232,113,kkkkkkkcuuucuu将上述表达式写成矩阵形式，输入的第一、二个信息比特时：输入的第三个比特及之后矩阵形式：3211,12,1111110,101111kkkkkuuuccA011,02,00121,12,100,0uTccuuTcc12111000,110000TT把三个系数矩阵综合起来，可以得到它的矩阵表示为：12111011001110110000111011111011111011TTAAGAA211222()1(111)()1(101)gxxxggxxg观察G矩阵与生成多项式：12111,011TTgg111011g可知生成矩阵和生成多项式存在确定的关系，生成多项式改写为：12312311112222(111)(),(101)()gggggggg33221112121233221112121233221112121233221212ggggggggggggGgggggggggg123123123GGGGGGGGGG111122221233312GggGggGgg卷积码的图解表示—状态图卷积码除了可用解析式表示外，还可以用图表示，包括状态图、树状图和网格图卷积码与当前信息位有关，与之前的信息位也有关系，以(2,1,3)码为例，卷积码序列取决于c1和c2端的输出，而c1和c2与两个相加器的三个数据输入位ujuj-1和uj-2有关，即：c1=uj+uj-1+uj-2c2=uj+uj-2当前比特uj编码完毕后存入第一寄存器，前一比特uj-1存入第二个寄存器，那么下一时刻比特的编码就与这两个寄存器保存的值有关ju2ju1ju输出序列输入序列1g2g1c2c00111001c1=uj+uj-1+uj-2c2=uj+uj-200(0)11(1)假设寄存器当前状态为00若当前输入比特为0，则c1和c2输出为00，状态不变：若当前输入比特为1，则c1和c2输出为11，状态变为10：假设寄存器当前状态为10若当前输入比特为0，则c1和c2输出为10，状态变为01：若当前输入比特为1，则c1和c2输出为01，状态变为11：10(0)01(1)假设寄存器当前状态为11若当前输入比特为0，则c1和c2输出为01，状态变为01：若当前输入比特为1，则c1和c2输出为10，状态不变：10(1)01(0)00(1)11(0)假设寄存器当前状态为01若当前输入比特为0，则c1和c2输出为11，状态变为00：若当前输入比特为1，则c1和c2输出为00，状态变为10：编码方法：1）从寄存器当前的状态出发，依据输入值进行状态转移；2）将迁移路径上的序列依次写下来即可得到编码序列abcd因此这两个寄存器可能保存的值有四种：00、10、01、11，每一种值称为编码器的一种状态，分别依次用a、b、c、d表示，编码器就在这四种状态间转移，如下图所示：卷积码的图解表示—树状图观察卷积码的状态迁移图，可知根据输入值的不同，编码器只向两种状态迁移，因此也可以用二叉树来描述卷积码树状图绘制方法：1）先假设其从某一状态开始；2）输入为0时，树状图向上延伸；输入为1时，向下延伸；3）按照状态图在时间上的迁移顺序依次绘制，分支上的数字为编码器的输出编码方法：1）从树根开始编码，每一节点为码元输入点；2）到达每一节点时按照下一输入的码元向上（0）或向下（1）走；3）编码完毕后，将行走路径上的依次进行排列，即可得到卷积码序列右图为从状态00开始的树状图，假设编码序列为0110，确定其卷积码序列卷积码的图解表示—网格图网格图的绘制方法（与树状图类似）：1）将编码器的四种状态用黑点画出，排成一列；2）每一时刻，即每个输入点画一列状态点；3）用“实线”表示输入为0时的迁移路径；用“虚线”表示输入为1时的迁移路径；4）路径上标出每次迁移所得到编码输出；5）按照状态迁移图的时间顺序进行绘制编码方法与树状图类似将序列信息11011编成(2,1,3)卷积码，假设初始状态为00