信道编码-循环码

1、yyyy/M/d1/491. 循环码的多项式描述2. 循环码的生成多项式3. 系统循环码4. 多项式运算电路5. 循环码的编码电路6. 循环码的译码7. 循环汉明码8. 缩短循环码3. 循环码yyyy/M/d2/49(1) 循环码的性质循环码是线性分组码的一个重要子类；由于循环码具有优良的代数结构，使得可用简单的反馈移位寄存器实现编码和伴随式计算，并可使用多种简单而有效的译码方法；循环码是研究最深入、理论最成熟、应用最广泛的一类线性分组码。1. 循环码的多项式描述yyyy/M/d3/49(2) 循环码的定义循环码：如果 (n,k) 线性分组码的任意码矢C=(Cn1,Cn2,C0) 的 i 次循

2、环移位，所得矢量C(i)=(Cn1i,Cn2i,C0,Cn1,Cni) 仍是一个码矢，则称此线性码为 (n,k) 循环码。1. 循环码的多项式描述yyyy/M/d4/49(3) 码多项式码多项式：为了运算的方便，将码矢的各分量作为多项式的系数，把码矢表示成多项式，称为码多项式。其一般表示式为C(x)=Cn1xn1+Cn2xn2+C0)码多项式 i 次循环移位的表示方法 记码多项式C(x)的一次左移循环为 C(1)(x) ，i 次左移循环为 C(i)(x)1. 循环码的多项式描述ininiinininininnnnnnnnnCxCxCxCxCxCxCxCxCxCxCxCx1102211)(102

3、312)1(02211)(C)(C)(Cyyyy/M/d5/49码多项式的模 (xn+1) 运算0和1两个元素模2运算下构成域。1. 循环码的多项式描述yyyy/M/d6/49若 p 为素数，则整数全体在模 p 运算下的剩余类全 体 在模 p 下构成域。以 p=3 为模的剩余类全体 模3运算的规则如下：1, 3,2, 1,0p1. 循环码的多项式描述120221010000210102202112100210构成域。2,1,0yyyy/M/d7/49码矢 C 循环 i 次所得码矢的码多项式 C(x) 乘以 x，再除以 (xn+1)，得1. 循环码的多项式描述ininiinininininnnn

4、CxCxCxCxCxCxCxCx1102211)(02211)()(CC1)(11)()1(1102123121nnnnnnnnnnxxCxCxCxCxCxCCxxxCCyyyy/M/d8/49上式表明：码矢循环一次的码多项式 C(1)(x) 是原码多项式 C(x)乘以 x 除以 (xn+1) 的余式。写作因此， C(x) 的 i 次循环移位 C(i)(x) 是 C(x) 乘以 xi 除以 (xn+1) 的余式，即结论：循环码的码矢的 i 次循环移位等效于将码多项式乘 xi 后再模 (xn+1)。) 1()()()1(nxxxx模CC1. 循环码的多项式描述) 1()()()(niixxxx模

5、CCyyyy/M/d9/49(4) 举例：(7,3) 循环码，可由任一个码矢，比如 (0011101) 经过循环移位，得到其它6个非0码矢；也可由相应的码多项式(x4+x3+x2+1)，乘以xi(i=1,2,6)，再模(x7+1)运算得到其它6个非0码多项式。移位过程和相应的多项式运算如表6.3.1所示。1. 循环码的多项式描述yyyy/M/d10/491. 循环码的多项式描述yyyy/M/d11/49(1) 循环码的生成矩阵根据循环码的循环特性，可由一个码字的循环移位得到其它的非0码字。在 (n,k) 循环码的 2k 个码字中，取前 (k1) 位皆为0的码字 g(x)（其次数r=nk），再经

6、 (k1) 次循环移位，共得到 k 个码字：g(x),xg(x),xk1 g(x) 2. 循环码的生成多项式)()()()()(21xxxxxxxxkkggggG 这 k 个码字显然是相互独立的，可作为码生成矩阵的 k 行，于是得到循环码的生成矩阵 G(x)yyyy/M/d12/49(2) 循环码的生成多项式码的生成矩阵一旦确定，码就确定了；这就说明： (n,k) 循环码可由它的一个 (nk) 次码多项式 g(x) 来确定；所以说 g(x) 生成了 (n,k) 循环码，因此称 g(x) 为码的生成多项式。2. 循环码的生成多项式多项式。次首是一个1)()()(0111knxxxxxknknkn

7、gggggyyyy/M/d13/49(3) 生成多项式和码多项式的关系定理定理1 1：在 (n,k) 循环码中，生成多项式 g(x) 是惟一的 (nk) 次码多项式，且次数是最低的。 证明：先证在 (n,k) 循环码系统中存在 (nk) 次码多项式。 因为在 2k 个信息组中，有一个信息组为 ，它的对应码多项式的次数为n1(k1)=nk(nk) 次码多项式是最低次码多项式。l若 g(x) 不是最低次码多项式，那么设更低次的码多项式为g(x) ，其次数为 (nk1)。 g(x) 的前面 k 位为0，即 k个信息位全为0，而监督位不为0，这对线性码来说是不可能的，因此 g(x) 是最低次的码多项式

8、，即 gnk 必为1。l续下页2. 循环码的生成多项式10001个kyyyy/M/d14/49lg0=1，否则经 (n1) 次左移循环后将得到低于 (nk) 次的码多项式。g(x) 是惟一的 (nk) 次多项式。 如果存在另一个 (nk) 次码多项式，设为 g(x) ，根据线性码的封闭性，则 g(x) + g(x) 也必为一个码多项式。由于 g(x)和 g(x) 的次数相同，它们的和式的 (nk) 次项系数为0，那么 g(x) + g(x) 是一个次数低于 (nk) 次的码多项式，前面已证明 g(x) 的次数是最低的，因此 g(x) 不能存在，所以 g(x) 是惟一的 (nk) 次码多项式。2

9、. 循环码的生成多项式yyyy/M/d15/49定理定理2 2：在 (n,k) 循环码中，每个码多项式 C(x) 都是 g(x) 的倍式；而每个为 g(x) 倍式且次数小于或等于 (n1) 的多项式，必是一个码多项式。 证明(续下页)设 m=(mk1,mk2,m0) 为任一信息组，G(x) 为该 (n,k) 循环码的生成矩阵，则相应的码多项式为2. 循环码的生成多项式)()()()()()(),()()()(0221121021xmxmxmxxxxxxxmmmxxxkkkkkkkkgggggCGmCyyyy/M/d16/49上式表明：循环码的任一码多项式为 g(x) 的倍式。显然，凡是为 g(

10、x) 的倍式且次数小于或等于 (n1) 的多项式，一定能分解成上式的形式，因而它就是信息多项式 m(x)=(mk1xk1+mk2 1xk2+m0) 并由生成矩阵 G(x) 所生成的码多项式。定理定理3 3(逆定理2)：在一个 (n,k) 线性码中，如果全部码多项式都是最低次的 (nk) 次码多项式的倍式，则此线性码为一个 (n,k) 循环码。 注注：一般说来，这种循环码仍具有把 (n,k) 线性码码中任一非0码矢循环移位必为一码矢的循环特性，但从一个非0码矢出发，进行循环移位，就未必能得到码的所有非0码矢了。所以称这种循环码为推广循环码。2. 循环码的生成多项式yyyy/M/d17/49码字循

11、环关系图单纯循环码的码字循环图：(7,3)循环码2. 循环码的生成多项式yyyy/M/d18/49推广循环码的码字循环图：(6,3)循环码2. 循环码的生成多项式yyyy/M/d19/49(4) 如何寻找一个合适的生成多项式由下面式子可知：循环码的多项式等于信息多项式乘以生成多项式。 这说明：对一个循环码只要生成多项式一旦确定，码就确定了，编码问题就解决了。 所以：作一循环码的关键，就在于寻找一个适当的生成多项式。2. 循环码的生成多项式)()()()()()(),()(0221121021xmxmxmxxxxxxxmmmxkkkkkkkkgggggCyyyy/M/d20/49定理定理4 4：

12、 (n,k) 循环码的生成多项式 g(x) 是 (xn+1)的因式，即 xn+1=h(x)g(x)。 证明：由于 xk g(x) 是 n 次多项式，可表示为xk g(x)=1(xn+1)+ g(k)(x) (6.3.1) 式中 g(k)(x) 是码多项式 g(x) 乘以 xk 除以 (xn+1) 的余式。 根据循环码的移位关系，它是 g(x) 循环移位 k 次所得到的码多项式，因而 g(k)(x) 是 g(x) 的倍式。设 g(k)(x)=m(x)g(x) 代入式(6.3.1)得(xn+1)=xk+m(x)g(x)上式表明： g(x) 是 (xn+1) 的因式。2. 循环码的生成多项式yyyy

13、/M/d21/49定理定理5 5：若 g(x) 是一个 (nk) 次 多项式，且为(xn+1) 的因式，则 g(x) 生成一个 (n,k) 循环码。 证明：(续下页)由于 g(x) 是一个 (nk) 次多项式，且为 (xn+1) 的因式，所以 g(x), xg(x), xk1 g(x) 是 k 个次数小于 n，并且彼此独立的多项式；2. 循环码的生成多项式)()()()()(21xxxxxxxxkkggggG将此多项式用作码的生成矩阵的 k 行，得到 (n,k) 线性码的生成矩阵；yyyy/M/d22/49设信息组 m=(mk1,mk2,m0)，则相应的码字为 C(x)=mG(x)=(mk1x

14、k1+mk2 1xk2+m0)g(x)= m(x)g(x)lC(x)n1；lm(x) 是 2k 个信息多项式的表示式；l所以 C(x) 即为相应 2k 个码多项式的表示式。因此，g(x) 生成一个 (n,k) 线性码。C(x) 是 (nk) 次多项式 g(x) 的倍式，所以 g(x) 生成一个 (n,k)循环码。 结论结论：当求作一个(n,k)循环码时，只要分解多项式(xn+1) ，从中取出(nk)次因式作生成多项式即可。2. 循环码的生成多项式yyyy/M/d23/49举例：求 (7,3) 循环码的生成多项式。解：分解多项式 xn+1，取其4次因式作生成多项式x7+1= (x+1) (x3+

15、x2+1) (x3+x+1)可将一次和任一个三次因式的乘积作为生成多项式，因而可取 g1(x)= (x+1) (x3+x2+1) = x4+x2+x+1 或 g2(x)= (x+1) (x3+x+1) = x4+x3+x2+12. 循环码的生成多项式yyyy/M/d24/49(5) 循环码的监督多项式和监督矩阵循环码的监督多项式：设 g(x) 为 (n,k) 循环码的生成多项式，必为 (xn+1) 的因式，则有 xn+1=h(x)g(x)，式中h(x) 为 k 次多项式，称为 (n,k) 循环码的监督多项式。(n,k) 循环码也可由其监督多项式完全确定。举例： (7,3) 循环码 x7+1=

16、(x3+x+1)(x4+x2+x+1)l4次多项式为生成多项式g(x)=x4+x2+x+1=g4x4+g3x3+g2x2+g1x+g0l3次多项式是监督多项式h(x)=x3+x+1=h3x3+h2x2+h1x+h02. 循环码的生成多项式yyyy/M/d25/49循环码的监督矩阵由等式 x7+1= h(x)g(x) 两端同次项系数相等得将上面的方程组 写成矩阵形式0000332463223145312213044302112033hghgxhghghgxhghghghgxhghghghgx的系数的系数的系数的系数2. 循环码的生成多项式Tggggghhhhhhhhhhhhhhhh0012343

17、21032103210321000000000000000yyyy/M/d26/49上式中，列阵的元素是生成多项式 g(x) 的系数，是一个码字，那么第一个矩阵则为(7,3)循环码的监督矩阵监督矩阵，即2. 循环码的生成多项式)2 . 3 . 6(0000000000003210321032103210)3 ,7(hhhhhhhhhhhhhhhhHyyyy/M/d27/49循环码监督矩阵的构成循环码监督矩阵的构成由式 (6.3.2) 可见，监督矩阵的第一行是码的监督多项式 h(x) 的系数的反序排列反序排列，第二、三、四行是第一行的移位；可用监督多项式的系数来构成监督矩阵2. 循环码的生成多项

18、式的反多项式。表示其中)()()3 . 3 . 6(0001011001011001011001011000)()()()(*3*2*)3 ,7(xxxxxxxxxhhhhhhHyyyy/M/d28/49(n,k) 循环码的监督矩阵对偶问题如果 xn+1=h(x)g(x)，其中 g(x) 为 (nk) 次多项式，以 g(x)为生成多项式，则生成一个 (n,k) 循环码；以 h(x) 为生成多项式，则生成 (n,nk) 循环码；这两个循环码互为对偶码。0011101101100)()()(11111111*1*),(kkkkknknhhhhhhhhxxxxxhhhH2. 循环码的生成多项式yyy

19、y/M/d29/49(1) 系统循环码构成设信息向量 m=(mk1,mk2,m0)信息多项式 m(x)=mk1xk1+mk2 xk2+m0 码多项式的高次幂部分等于m(x)，即 C(x)=cn1xn1+ cnkxnk+ cnk1xnk1 +c1x +c0 =xnk m(x)+q(x) q(x)的次数nk校验位多项式 q(x)由于码多项式是生成多项式的倍式，所以C(x)= xnkm(x)+q(x)=a(x)g(x)0 (mod g(x)q(x)=C(x)+ xnkm(x)xnkm(x) (mod g(x)因此，循环码的系统码形式为C(x)= xnkm(x)+ (xnkm(x) mod g(x)3

20、. 系统循环码yyyy/M/d30/49系统循环码构造过程步骤信息多项式乘 xnk： xnkm(x)对 xnkm(x) 求余式：q(x)xnkm(x) (mod g(x)求码多项式： C(x)=xnkm(x)+ ( xnkm(x) mod g(x) =xnkm(x)+ q(x)令 m(x) 为单项式 xnk+i，i=0,1,2,k1xnk+i= a(x)g(x)+qi(x)，qi(x)的次数nkCi(x)= xnk+i+qi(x)可见： Ci(x)对应的向量Ci，i=0,1,2,k1是线性无关的，从而得到循环码系统码的生成矩阵 Gs 为3. 系统循环码yyyy/M/d31/493. 系统循环码

21、1, 01 , 00, 01, 21 , 20, 21, 11 , 10, 1021100010001100010001knknkkkknkkkkksqqqqqqqqqqqqGyyyy/M/d32/49(2) 举例例： (7,4) 循环码 g(x)=x3+x+1，x6=(x3 + x2 +1)g(x)+(x2+1) q3(x)=(x2+1) C3(x)=x6+x2+1 x5=(x2+1)g(x)+(x2+x+1) q2(x)=(x2+x+1) C2(x)=x5+x2+x+1 x4= xg(x)+(x2+x) q1(x)=(x2+x) C1(x)=x4+x2+xx3= g(x)+(x+1) q0

22、(x)=(x+1) C0(x)=x3+x+1 3. 系统循环码)()()() 1()() 1(1101000011010011100101010001223xxxxxxxxsggggGyyyy/M/d33/49(1) 多项式加法电路多项式 a(x)=anxn+an1xn1+a1x+a0 表示的是时间序列 a=(an,an1,a1,a0)，因此多项式的计算表现为对时间序列的操作；4. 多项式运算电路 对二进制多项式系数的基 本操作为模模2加加和模模2乘乘； 电路图运算符号的意义：yyyy/M/d34/49a(x) 与 b(x) 的相加电路。如图6.3.3。4. 多项式运算电路yyyy/M/d35

23、/49(2) 多项式乘法电路多项式乘以 x 等价为时间序列 a 延迟一位；多项式与多项式相乘等价为不同位移后的相加： a(x)g(x)=a(x)(g1(x)+ g2(x)= a(x)g1(x)+ a(x)g2(x) 多项式乘法电路如图6.3.4。假设多项式的低位在前，电路中所有寄存器初态为0。4. 多项式运算电路yyyy/M/d36/49图6.3.5表示了多项式乘法电路。4. 多项式运算电路yyyy/M/d37/49(3) 多项式除法电路当 g(x) =1,多项式 a(x) 模 g(x) 的余式为0,电路如图6.3.7所示。4. 多项式运算电路yyyy/M/d38/49当 g(x)是单项式 g

24、(x)=xk， a(x) 模 g(x) 的余式的次数小于 k，进入电路的输入顺序为 an,an1,a1,a0。a(x)ak1xk1+ak2xk2+a1x+a0 (mod xk) 运算电路如图6.3.8所示。4. 多项式运算电路yyyy/M/d39/49由于 xk1 mod(x+1), i=0,1,2,。若 a(x) 的次数为 n，则 a(x) mod(x+1)an1+an2+a1+a0 =q0 (mod 2) 运算电路如图6.3.9所示。4. 多项式运算电路yyyy/M/d40/49同样由长除法得 运算电路如图6.3.10所示。4. 多项式运算电路niiiniiiniiiniiiaqaqxqq

25、aax5 , 3 , 114, 2, 002105 , 3 , 14, 2, 0)1(mod()(其中ayyyy/M/d41/49类似地：多项式a(x)模(x2+x+1)的运算电路如图6.3.11所示。4. 多项式运算电路yyyy/M/d42/49一般的多项式模 g(x)=grxr+gr1xr1+g1x+g0 的运算电路如图6.3.12所示。移位寄存器初态全为0；当 a(x) 输入完后，移位寄存器内容(qr, qr1,q1,q0 )就是余式q(x)=pr1xr1+ pr2xr2+ +p1x+p0 a(x) (mod g(x)4. 多项式运算电路yyyy/M/d43/49多项式除法电路的构造多项式除法电路是一个由除式(这里就是生成多项式g(x) g(x)=gnkxnk+gnk1xnk1+g1x+g0 所确定的反馈移位寄存器。除法电路的构造方法移位寄存器的级数等于除式的次数 nk；移位寄存器的反馈抽头，由除式的各项系数 gi(i=0,1,nk) 决定：p当某个抽头=0时，对应的反馈断开；p当某个抽头=1时，对应的反馈接通。完成除法所需的移位次数等于被除式的次数加1。4. 多项式运算电路yyyy/M/d44/49多项式除法电路举例利用除法电路完成两个多项式除法运算，求其余式的过程和将两个多项式进行长除运算是完全一致的；例如 (x5