信道编码(中)

第三章信道编码3.4循环码本节的主要内容码多项式循环移位的数学表达循环码的生成多项式循环码的编码循环码的译码编、译码的电路实现循环码：cycliccode码多项式：codepolynomial生成多项式：generatorpolynomial求模运算：modulararithmetic系统码：systematic（regular）code循环移位运算：cycleshiftoperation外语关键词上节回顾：线性分组码基本概念：表达方式：(n,k)码，k是信息位数，r是监督位数，n=k+r是码长。编码：已知信息K（k位二进序列），求相应码字的方法是C=KG，G叫生成矩阵，是k行n列的，一般G具有[IkQ]的形式，Ik是k行k列单位方阵，Q是k行r列的矩阵。生成矩阵的设计，应使许用码字之间的最小汉明距离尽量地大。译玛：当收到码字R时，首先计算伴随子向量：S=RHT；若S=0，则R=C为正确码字；若S≠0，则R≠C为错误码字。这里H叫一致监督矩阵，是r行n列的。一般H具有[PIr]的形式，Ir是r行r列单位方阵，P是r行k列的矩阵，P与Q互为转置关系。纠正1位错：当S≠0时，由S=R·HT求出S，比较S与HT，HT的那一行与S相同，相应的错误格式向量E的那一位就等于1，于是R的那一位就是错误的。最后根据C=R⊕E进行将其纠正。纠正多位错错：当S≠0时，根据S=R·HT=E·HT，可以预先由S=E·HT计算出各种错误格式E所对应的伴随子向量S，得到E~S对照表。查表就能找到接收码字R（即S=R·HT）所对应的E。纠错能力不等式：2r≥Cno+Cn1+Cn2+……+Cnt这是因为伴随子S是1行r列的向量，它有2r种不同的状态，除了用全零态表示正确码之外，最多只能区别开2r–1种不同的错误格式。r2引言：构造线性分组码关键是设计出一个好的生成矩阵，使所有码字之间的汉明距离尽量大。怎样找这样的矩阵呢？循环码的出现提供了一整套理论和方法，使人们能够借助数学工具来寻找更好的线性分组码，并由此引发出一大类很常用检、纠错编译码。3.4循环码上节讨论过(7,3)线性分组码:C0=(0000000);C1=(0011101);C2=(0100111);C3=(0111010);C4=(1001110);C5=(1010011);C6=(1101001);C7=(1110100);不难发现它们具有循环移位特性：C0=(0000000);C1=(0011101);C3=(0111010);C7=(1110100);C6=(1101001);C5=(1010011);C2=(0100111);C4=(1001110);循环码是线性分组码中的一个子集。对于循环码，有了一个的码字，按循环移位规律就能写出n个码字。从中选出k个来构造生成矩阵G，就能生成全部2k个许用码字。循环码与近代数学有密切联系。使我们可以借助数学工具来设计编码。3.4.1码多项式二进制自然码可表达为以2为底的多项式表达，如：C=(1010111)==1×26+0×25+1×24+0×23+1×22+1×21+1×20；把底换为x，则得到“码多项式”：C(x)=1·x6+0·x5+1·x4+0·x3+1·x2+1·x1+1·x0=x6+x4+x2+x+1码长为n时，可写：C(x)=cn-1xn-1+cn-2xn-2+……+c1×x1+c0x0如三位二元码的8个码字对应的码多项式为：000，001，010，011，100，101，110，111；0，1，x,x+1,x2,x2+1,x2+x,x2+x+13.4.2循环移位的数学表达对二进数，左移一位相当于乘以2，而将最高位的进位(2n位)上的数码拿回到20位，叫做循环移位，相当于作模2n-1运算。如：101→1010→011实际是5×2mod7=3码多项式的循环移位，实际是乘x后作模xn-1运算。如：1100010→11000100→1000101(x6+x5+x)→x(x6+x5+x)mod(x7-1)=(x7+x6+x2)mod(x7-1)=x6+x2+1（7,4）循环码及其码多项式的循环移位：循环次数循环码码多项式模x7-1运算后00001011x3+x+1x3+x+110010110x(x3+x+1)x4+x2+x20101100x2(x3+x+1)x5+x3+x231011000x3(x3+x+1)x6+x4+x340110001x4(x3+x+1)x5+x4+151100010x5(x3+x+1)x6+x5+x61000101x6(x3+x+1)x6+x2+13.4.3循环码的生成多项式(1)生成多项式的定义和特点循环码的码多项式中幂次最低的非零多项式叫做生成多项式，记做g(x)。如(7,4)码的x3+x+1。有了它，其它码字都可由xi·g(x)的模xn-1得到。生成多项式的常数项为1。否则，通过循环移位还能继续降低幂次，它就不是幂次最低的多项式了。生成多项式的幂次为r。因为幂次最低的码多项式是信息为00……01,后面跟上r个监督位的那个码字所对应的码多项式，它的最高位是xr，是r次的多项式。(2)生成多项式的两个性质：1．任意码多项式T(x)都是生成多项式g(x)的倍式。证明：（n,k）循环码作为线性分组码，其生成矩阵G是k行n列的，可由k个不同的码字构成：任给一个信息码K=(cn-1cn-2……cn-k)，利用生成矩阵和公式C=K•G，不难求出它对应的码字T(x)=K·G=(cn-1cn-2……cn-k)·=（cn-1xk-1+cn-2xk-2+……+cn-k）·g(x)；即：T(x)=h(x)·g(x)；表明任意码多项式T(x)都应能被g(x)整除。2．生成多项式g(x)是xn-1的一个因式。证明：因为g(x)循环左移k位,即g(x)乘以xk后再作模xn-1运算,应当仍为一个码多项式。xk·g(x)为n次多项式，除以xn-1的商式必为1，设余式为T(x),于是有：移项即证得：xn-1=g(x)·[xk–h(x)]；即：xk·g(x)=xn-1+T(x)=xn-1+h(x)·g(x)（3）生成多项式g(x)的确定：由性质2知，g(x)是xn-1的一个因式。可根据设定的码长n和监督位r，将xn-1因式分解，从中选择一个r次的因子作为g(x)。例如：(7,4)码，n=7，k=4，r=3；分解：x7-1=(x-1)(x3+x+1)(x3+x2+1)g(x)应是x7-1的一个r=3次的因子，可取为：g(x)=x3+x+1或g(x)=x3+x2+1；二者任选其一，一旦选定，就不再考虑另一个了。插件1：查表分解xn-1的方法（1）并非所有的xn-1都具有r次的既约(不能再分解)的因式。但只要满足n=2r-1，xn-1就具有r次的既约因式。因此P194页表4中只列出满足n=2m-1的xn-1的分解情况。（2）不论n取何值，xn-1总有一个m0(x)=x+1的因式。（3）xn-1其它因式是mi(x),i=1,3,5,7……（4）mi(x)的表达由8进制数给出，将它换成二进制自然码就是mi(x)各位的系数。如m=5阶时，n=31，可分解x31-1为：第i=1类因式查表得到(45)8=(100101)2，表示m1(x)=x5+x2+1；第i=3类因式查表得到(75)8=(111101)2，m3(x)=x5+x4+x3+x2+1；第i=5类因式查表得到(67)8=(110111)2，m5(x)=x5+x4+x2+x+1；（5）表中并未列出xn-1所有的因式，与已列出因式对偶的因式都被省略了。所谓对偶指的是将二进制自然码高低位倒置的表达，如：与(100101)2对称的是(101001)2，表示m15(x)=x5+x3+1；与(111101)2对称的是(101111)2，表示m7(x)=x5+x3+x2+x+1；与(110111)2对称的是(111011)2，表示m11(x)=x5+x4+x3+x+1；值得注意的是，有的二进制自然码本身就是对称的，如：(11111)2与(10001)2，高低位倒置后不变,不会出现新的因式。（6）xn-1分解为以上因式之积，诸因式中幂次最高为r。（7）类序号i与n互素的那些因式mi(x)被称为本原多项式；类序号i与n可约的那些因式mi(x)被称为非本原多项式。如果n为素数，所有的因式都是本原多项式。[例]查表分解x63-1因为26-1=63，所以应查P194页表4中m=6阶。i=1：(103)8=(1000011)2，得知m1(x)=x6+x+1；由对偶式(1100001)2和187页表得知m31(x)=x6+x5+1；i=3：(127)8=(1010111)2，得知m3(x)=x6+x4+x2+x+1；由对偶式(1110101)2和187页表知m15(x)=x6+x5+x4+x2+1；i=5：(147)8=(1100111)2，得知m5(x)=x6+x5+x2+x+1；由对偶式(1110011)2和187页表知m23(x)=x6+x5+x4+x+1；i=7：(111)8=(1001001)2，得知m7(x)=x6+x3+1；对偶式还是自己。i=9：(015)8=(1101)2，得知m9(x)=x3+x2+1；由对偶式(1011)2和187页表知m27(x)=x3+x+1；i=11：(155)8=(1101101)2，得知m11(x)=x6+x5+x3+x2+1；由对偶式(1011011)2和187页表知m13(x)=x6+x4+x3+x+1；i=21：(007)8=(111)2，得知m21(x)=x2+x+1；其对偶式仍是自己；最终结果：1）x63-1=m0(x)m1(x)m3(x)m5(x)m7(x)m9(x)m11(x)·m13(x)m15(x)m21(x)m23(x)m27(x)m31(x)；2)本原多项式是m1(x),m5(x),m11(x),m13(x),m23(x)和m31(x)；(1)循环码的生成矩阵求出了生成多项式g(x)，等于得到了一个码字，通过循环移位不难得到其它码字。果然如此简单吗？实际上，通过循环移位最多可写出n个码字，得不到全部码字，因为(n,k)码应当共有2k个许用码字。例如(7,4)循环码共有16个许用码字。取g(x)=x3+x+1，等于知道了中信息K=(0001)所对应的那个码字：C1=(0001011)。3.4.4循环码的编码C1经过循环移位只能得到7个码字：序号信息位许用码字C10001(0001011)C20010（0010110）C50101（0101100）C111011（1011000）C60110（0110001）C121100（1100010）C81000（1000101）（7,4）共有16个许用码字，还缺9个。从循环组中随便取4个许用码字，比如前4个，用它们构成的生成矩阵为G1：再利用C=K•G1就能求得全部许用码字。比如：(0100)•G1=(0101100);(1000)•G1=(1011000);然而发现码字不具备信息位在前，监督位在后的形式。原因是G1不具备G=[IkQ]的形式，这样编码叫非系统码，非系统码在译码时是比较困难的。实际上，为了构造G=[IkQ]形式的生成矩阵。需要如下的4个码字：1000⁩⁩⁩0100⁩⁩⁩0010⁩⁩⁩0001⁩⁩⁩才能排列出4×4的单位矩阵Ik。通过对C1=(0001011)的循环移位可以得到（0010110）和（1000101)，但是却无法得到(0100⁩⁩⁩)011110101原因何在？原来0100所对应的码字（0100111)位于另一循环组中:第一循环组第二循环组序号信息许用码字序号信息许用码字C10001（0001011)C40100（0100111)C20010（0010110）C91001（1001110）C50101（0101100）C30011（0011101）C111011（1011000）C70111（0111010）C60110（0110001）C141110（1110100）C