编码chapter5

1、第五章 循环码 陆以勤引子)()() 1()() 1()()()(11)(10111001110010011100133332123425236xgxgxxgxxxgxgxgxxxxxxxxxxxGG321ggg7，3（第三章例1） c=mG=(m1 m2 m3)G c(x)=mG(x)= (m1 m2 m3) G(x) c(x)= m1g1(x)+m2 g2(x)+m3 g3(x)= m1x(x+1)g3(x)+ m2(x+1)g3(x)+ m3 g3(x) = (m1x(x+1) + m2(x+1)+m3)g3(x) =(m1x2+(m1 +m2)x+ (m1 + m2 + m3) g3(

2、x)=m(x) g3(x) m(x)=2所有的码字多项式都是g3(x)的倍式因为是系统码，求校验位即可 c(x)= m(x)xn-k+r(x)=m(x)x4+r(x) 0 （mod g3(x)，可得余式：r(x) m(x)x4 （mod g3(x)校验多项式r(x)是信息多项式m(x)移4位除以g3(x)的余式，所以编码电路可用除以g3(x)的电路（除法电路 ）实现引子c(x)=m(x) g3(x) m(x)=2，设为m(x)=ax2+bx+cv 所有的码字多项式都是 g3(x)的倍式g3(x)的小于或等于2次的倍式是码字多项式能否抽象成一个数学模型？v 主理想：由生成元的所有倍式组成。如果想

3、用g3(x)生成的主理想作为码的模型，必须把g3(x)无限个倍式映射为有限个码元。这时，可用剩余类。 因为c(x) 2时， xi g3 (x)6,多重g g已移出左边缘，为了保证fgfg为一个码字，需要把移出边缘的部分作处理，方案有： 把移出部分截掉，即对f(x)g3 (x)取模x7运算。这时，截掉后的多重重量会不断减少，可能不再是一个码字，所以这种处理方法不合理。 把移出部分循环回fgfg的尾部，即对f(x)g3 (x)取模x7-1运算。处理后可能保证多重重量不会减少，是否是一个码字？v 定理4.2.10(p111) Fpx/f(x)中每个理想都是主理想，且该主理想的生成元g(x)|f(x)

4、。 g3 (x)| x7-1，满足（7，3）码是g3 (x)生成的主理想的必要条件，是否满足充要条件？引子下证（7，3）码是在Fpx/(x7-1)中以g3(x)为生成元的主理想。即证g3(x)的倍式模x7-1后仍是一个码字（即是g3(x)小于3次的倍式）设x7-1=h(x)g3(x)f(x)=p(x)h(x)+r(x), r(x) c(x) Vn,k;1)说明每一个码矢都是g(x)的倍式， 即由g(x)循环移位的线性组合2)说明g(x)小于n-1次的倍式（即由g(x)循环移位的线性组合）一定是个码多项式。v g(x)叫循环码的生成元（生成多项式），所以Vn,k是个主理想。一、循环码的数学概念定

5、理3：GF(q)上的n,k循环码的生成多项式g(x)|xn-1;反之，若g(x)|xn-1，则g(x)一定生成一个n,k循环码，其中k=n-g(x)证明：(1)证g(x)|xn-1g(x) Vn,k， 设xn-1=g(x)h(x)+r(x)， r(x) g(x) （欧几里德算法）则0)()()()()()(. )()(. )(1)(0)()(. )(1,xrxgxgxrVxrVxhxgxhxgxxrVxrxhxgxknknnknn所以是生成元，次数最小，而又又一、循环码的数学概念(2)证g(x)|xn-1，则g(x)一定生成一个n,k循环码（课本证得不好）g(x)的倍式h(x)g(x)组成一个

6、理想V,由定理1，V为循环码。下证下证V V的维数为的维数为k k.先证g(x),xg(x),x2g(x),xk-1g(x)线性无关。)()()(g(x)xm g(x)xm xg(x)m g(x)m 101 -k1 -k2210 xgxmxgxmkiii次数小于n,模xn-1不为零，所以g(x),xg(x),x2g(x),xk-1g(x)线性无关。又g(x)|(xn-1),设xn-1 =h(x)g(x)， h(x)=k= n- g(x)任c(x)V,有c(x)=q(x)g(x),设q(x)=p(x)h(x)+r(x), r(x)kc(x)=p(x)h(x)+r(x)g(x)=p(x)(xn-1

7、)+r(x)g(x)c(x)r(x)g(x) mod xn-1）（1010)()()(kiiikiiixgxrxgxrg(x),xg(x),x2g(x),xk-1g(x)是V的一组基二、xn-1的因式分解 由上面的分析可知, 要构造一个Fq上n, k循环码, 关键是要找到生成多项式g(x), 而g(x)是xn-1的n-k次因式. 因此对xn-1的因式分解是构造循环码的关键问题.1.当n = qm-1 根据第四章定理17，把（1）式共轭根的一次因式相乘，得最小多项式(Fp上，是素多项式),所以vssvsripsvsispGFsipxmwxxximsim1101)(1)()1（个共扼根第个共扼根系

8、的第中为其中，r为ws对模n的方次数，n为ws的级数，ms(x)为第s个共扼根系共扼根对应的最小多项式特别地, 当n = 2m-1, n -k =m (g(x)的次数为m)时, 可查表求GF(2)上的m次本原多项式p(x), 由第四章定理20(课本定理4.6.7, p144)可知, p(x)|xn-1, 可以证明(参看华工出版社R.E. Blahut 差错控制码的理论与实践，p.85), 由p(x)生成的循环码d=3, 因此是一个汉明码.二、xn-1的因式分解例：对x15-1进行因式分解 构造GF(16),查表4-4得GF(2)上的本原多项式f(x)=x4+x3+1,求F2x/f(x), 得G

9、F(16)=(0,1,2, 3, 4, 5, 6, 7, 8, 9, 10, 11,12,13,14) 元素阶方次数共轭根最小多项式101x+1154（241mod 15), 2, 4, 8(x-)(x-2)(x-4) (x-8) = x 4 + x 3+1354(241mod 5)3, 6, 9, 12(x-3) (x-6) (x- 9) (x- 12)=x4+x3+x2 +x +1532(221mod 3)5, 10(x-5) (x-10)= x2 +x +17154(241mod 15)7, 14, 13, 11(x-7) (x-14) (x- 13) (x- 11)=x4+x +1显然

10、，3，7的最小多项式都可构成GF(16)，但3不是本原元，由其最小多项式m(x)=x4+x3+x2 +x +1不是本原多项式，由m(x)构造的GF(16)中，x不是本原元,因为其最小多项式m(x)不是本原多项式。由定理17*可知，x的级数是满足m(x)|xl-1的最小l, m(x)(x+1)=x5-1,l=5 满足m(x)| xl-1,所以x的级为5。二、xn-1的因式分解X15-1=(x+1)(x 4 + x 3+1)(x4+x3+x2 +x +1)(x2 +x +1)(x4+x +1)可以任意组合，共有32115101051)(情况）xgCCCCC种组合，即共有3

11、2个循环码例如，g(x)= (x4+x3+x2 +x +1)(x4+x +1)= x8+x7+x6 +x4 +1构成15，7循环码，而g(x)的重量为5，所以d=5(实际上等于5）2. 当n qm-1, 但n |qm-1可在中找阶为n的元素, 则生成的n阶循环群含有xn-1=0的全部根. 3.问题：1肯定为xn-1的根，所以(x+1)| xn-1 xn-1=(x+1)(xn-1+xn-2+x+1)所以g1(x)=(x+1), g2(x)= (xn-1+xn-2+x+1)g1 (x)生成n,n-1码， g2(x)生成n,1码问g1(x)和g2(x)各生成什么码？三、循环码的校验矩阵H H 和生成

12、矩阵G G 由于g(x), x g(x), ., xk-1 g(x)是k个线性无关的码字, 所以生成矩阵G G为)()()(1xgxxgxgxGk（1） g(x)| xn-1,设xn-1=g(x)h(x), h(x) = 称为码校验多项式, 其反多项式h*(x) = ，取kiiixh0kiikixh0)()()(*1xhxxhxhxHkn（2）可证HGHGT T=0 0, 所以(2)确定的H H是校验矩阵。h*(x)=xkh(x-1)由于xn-1=g(x)h(x), 所以 (x-1)n-1=g(x-1)h(x-1)xn(x-1)n-1)=xng(x-1)h(x-1)1-xn xn-kg(x-1

13、) xkh(x-1)=g*(x)h*(x)h*(x)|xn-1可见，循环码的对偶码也是循环码，其生成多项式为h*(x)三、循环码的校验矩阵H H和生成矩阵G G(1)式和(2)式确定G G的H H不是标准形式。系统码的码字应有C(x)=m(x)xn-k+r(x)的形式，其中m(x)是信息多项式，r(x)是监督多项式. 因为C (x) = m(x)xn-k+r(x)0 0 (mod g(x)，所以r(x) - m(x)xn-k (mod g(x)。又G=Ik P取mi(x)=xk-i (i=1,2,.,k), 可得相应的监督多项式ri(x) - mi(x)xn-k xk-i xn-k xn-i

14、(mod g(x) (i=1,2,.,k), 从而可求得构成系统码生成矩阵的k个码字:Ci (x) = mi (x)xn-k+ri (x) (i=1,2,.,k)，因此G G的标准形式为:)()()(11xrxrxrIGkkkk,其中，ri(x) - xn-i (mod g(x) (i=1,2,.,k)。 由G的标准形式可轻易求出H的标准形式.H=-PT In-k=-(r1(x)T -(r2(x)T -(rk(x)T In-k 三、循环码的校验矩阵H H和生成矩阵G G例。求7，4循环码的标准G,H解：g(x)为x7-1的7-4=3次因式。由第4章定理20知3)()(31)()(3)|()(1

15、2)() 1)()(13xfxfxfxfxfxfxfxxfxfx且，为素多项式，且，为素多项式且，为素多项式（所以，只要找出GF(2)上的3次素多项式，则必定是x7-1的因式查表4-4（P138)得GF(2) 的3次本原多项式x 3 +x 2+1所以g(x)= x 3 +x 2+1可生成7，4汉明循环码。r1(x)-x6 x2+x (mod g(x)r2(x)-x5 x+1 (mod g(x)r3(x)-x4 x2+x+1 (mod g(x)r4(x)-x3 x2+1 (mod g(x)1001110010011100111011011000111010011000100110001HG四、循

16、环码的循环子码定理8：C1和C2分别是由g1(x)和g2(x)生成的各异循环码(定理5.1.4)g2(x)| g1(x) C1 C2 X15-1=(x+1)(x 4 + x 3+1)(x4+x3+x2 +x +1)(x2 +x +1)(x4+x +1) g2(x)= x4+x +1, g1(x)=(x4+x3+x2 +x +1)(x4+x +1)g2(x)| g1(x), g2(x)15,11 15,7 g1(x)五、缩短循环码缩短循环码：循环码中前i位为0的码字组成的集合,由于这些码字前i位恒为0，所以可去掉不发送。1,1,1,1, 2, 21, 2, 21, 1, 11, 1, 1.0.0

17、.0.0.0.0nqkqkqiqnkkinkkiikikikikcccccccccccc去掉不发送原n维空间上k维子空间（Hc cT=0 0 的解空间）与n-i维超平面的交集（缩短后的最短汉明距离不会少于原最短汉明距离），纠错能力不会下降. 很实用，在给定码长或信息位数（n或k不能更改），又找不出xn-1的n-k次因式，可以找（n+i,k+i)循环码，如能找到，再将其缩短五、缩短循环码本来是技术上的问题，但等价于另一个线性分组码1.生成矩阵和监督矩阵nkkknikinikinknkggggggggggG,1, 11, 1,1, 21, 2, 11, 1.1.000.0.000.0.000.0.

18、010.0.001去掉i行(系统码)去掉i列GknkknikniknknkiikiiIhhhhhhhhhhhhH,1,1 , 21, 2, 21 , 2, 11, 1, 11 , 1.去掉i列H由此可见，缩短循环码保留了原码监督位（和伴随式）的计算，因此可用原码的编译码电路（稍加修改）五、缩短循环码2.多项式表示缩短循环码的码字多项式是原码中次数小于n-i的码多项式定理9：原码Vn,k是Fqx/xn-1中的主理想，生成元为g(x)缩短码Vn-i,k-i是Fqx/f(x)中的主理想，生成元为g(x)，f(x)=xn-i-r(x),其中r(x) xn-i (mod g(x).可见，g(x)|f(x

19、).证明: (1)证c(x) Vn-i，k-i c(x) Igc(x) Vn-i，k-i c(x) Vn，k且 c(x)n-i g(x) | c(x) c(x) Ig (2) 证c(x) Ig c(x) Vn-i，k-ic(x) Ig g(x)|c(x) f(x)=n-i c(x) Vn，k且 c(x)n-i c(x) Vn-i，k-i定理4.2.10(p111) Fpx/f(x)中每个理想都是主理想，且该主理想的生成元g(x)|f(x)。六、常用的CRC国际标准CRC(Cyclic Redundancy Check)循环冗余校验码是一种缩短循环码，广泛用于帧校验，习惯上把校验位称作CRC校验

20、码HDLC(high-level data link control)HDLC(high-level data link control)FlagAddressControlInformationFlagFCS011111102/4 bytes1-n bytes1/2 bytes01111110HDLC的子集LAPB：平衡式链路访问规程，平衡式链路访问规程，Link access procedure,balancedLAPD (Q.921) ：D信道链路访问规程，信道链路访问规程，Link access procedure for D channelLAPM：调制解调器链路访问规程，调制解调器

21、链路访问规程，link access procedure for modemsLAPF (Q.922) : link access procedure for frame model bearer services 帧帧方式承载业务的数据链路访问规程方式承载业务的数据链路访问规程, 以以LAPD为基础并作延伸为基础并作延伸LAPF分两部分：分两部分： DL-CORE: 数据链路核心协议，支持帧中继承载业务数据链路核心协议，支持帧中继承载业务 DL-CONTROL: 数据链路控制协议数据链路控制协议 X.25 LayersNetworkPacket layer protocol (PLP)Dat

22、a linkLink access procedure, balanced (LAPB)PhysicalEIA-232, V-serials, X.21othersFlag Address ControlInformationFlagFCSHeaderUser payload & headers from upper layersPLP Packet （包层）包层）1 Frame（帧层）帧层）Link control field(a subset of HDLC)(sequence numbers, ACKs, NAKs, flow control, link address)Netw

23、ork interface control field(sequence numbers, ACKs, NAKs, flow control, logical channel number)LAPF (Q.922)LAPF (Q.922)FlagAddressControlInformationFlagFCS011111102/4 bytes2-n bytes1/2 bytes01111110DLCIC/R EADLCIFECN BECNDE EA6 bits4 bits1 bit 1 bit1 bit 1 bit 1 bit1 bitLAPF Control FieldFlagAddress

24、ControlInformationFlagFCS与与HDLC相同相同FlagAddress InformationFCSFlagDLCIC/R EADLCIFECN BECNDE EAFCS:frame check sequenceDLCI:data link connection identifierC/R: command/response, unused in FREA: extended addressFECN:forward explicit congestion notificationBECN:backward explicit congestion notificationD

25、E:discard eligibility6 bit4 bit1 bit 1 bit1 bit 1 bit 1 bit1 bit1 byte1 byte24 byte2 byte=8189 bytes in standards,Normally=1600bytesA ether net packet=1500bytesNo Control FieldFR: LAPF-COREISDN LayersUsers choiceEnd-to-enduser signalingX.25 and otherCall cotrolQ.931LAPB and othersLAPD (Q.921)BRI (I.

26、430) & PRI (I.431)PhysicalData linkNetworkUser definedB channelD channelProtocol discriminator0 0 0 0Length of call reference valueCall reference value0 Message typeOther information elements(as required)Bits8 7 6 5 4 3 2 1 Octets123etcInformation(ISDN layer 3)FCSFlagControlAddressFlagSAPITE1EAC

27、REALink control fieldsequence no.ACKs, NAKs, flow control,link addressesSAPs in the terminalPreambleSFDDestinationaddress(DA)Sourceaddress (SA)Length/type of PDUDataCRC7 bytes1 byte6 bytes6 bytes2 bytes4 bytesDSAPSSAPControlInformationCyclic redundancy checkPreamble:同步前导，101010SFD: 帧定界符10101011MACPA

28、DPDU of EthernetSDH/SONET (Physical layer)、T3ATM SARAAL: ATM adaptation layer SAR: segmentation and reassemblyCS: convergence sublayerCSAAL1 SARCSAAL2 SARCSAAL3/4 SARCSAAL5ATM LayersPAD: added when necessary to fill out the final cell(s) in a segment packetAAL1AAL2AAL3/4AAL5ATM LayerSegment From AAL

29、 layer (48 bytes)Header (5tyes)0 GFCVCIVPI4 VPI 7VCIVCI4 PT 6 CLPHECPayloadData(48bytes)UNI CellVPI4 VCI 70 VPIVCIVCI4 PT 6 CLPHECPayloadData(48bytes)NNI CellGFC: Generic flow control PT:Payload typeVPI: Virtual path identifierCLP: Cell loss priorityVCI: Virtual channel identifierHEC: Header error c

30、ontrol六、常用的CRC国际标准CRC-12: g(x)=x12+x11+x3+x2+x+1 （12 位检验位）CRC-16: g(x)=x16+x15+x2+1 （16 位检验位）CRC-ITU-T: g(x)=x16+x12+x5+1 （16 位检验位）CRC-32: g(x)=x32+x26 +x23 +x22 +x16 +x12 +x11+x10 +x8 +x7 +x5 +x4 +x2 +x+1 （32 位检验位）CRC IS-95 CDMA: g(x)=x30+x29 +x21 +x20 +x15 +x13 +x12+x11 +x8 +x7 +x6 +x2 +x+1（30 位检验

31、位）专用芯片专用芯片： 8273(Intel), MC6854例：CRC-16, g(x)=(x+1)(x15+x+1) 其中x15+x+1为GF(215)的本原多项式，满足（ x15+x+1)|xn-1的最小的n=215-1=32767, 所以未缩短的循环码为（32767，32751）：所有码字数：232751最高位为0的码字数： 232750：可构成缩短码（32766，32750）最高2位为0的码字数： 232749 ：可构成缩短码（32765，32749）最高i位为0的码字数： 232751-i ： 可构成缩短码（32767-i，32751-i）六、常用的CRC国际标准CRC中，（x+1

32、)|g(x), 根据定理8，含有偶校验位CRC中，因为g(x)本身为次数最小的码字，dmin= W(g(x)六、常用的CRC国际标准CRC码生成多项式校验位最大码长最小距离检错能力应用CRC-12x12+x11+x3+x2+x+112211-1 =204761.所有奇数个差错2.所有长度=5的随机错3.所有长度=12的突发错4.以1-12-13的概率检出长度为17的单个突发差错5.以1-12-12的概率检出长度大于17的单个突发差错6.所有长度=2的两个突发错CRC-ITU-Tx16+x12+x5+116215-1 =3276741.所有奇数个差错2.所有长度=3的随机错3.所有长度=16的突

33、发错4.以1-12-17的概率检出长度为17的单个突发差错5.以1-12-16的概率检出长度大于17的单个突发差错6.所有长度=2的两个突发错HDLCSDLCX25SS7ISDNCRC-16x16+x15+x2+116215-1 =327674同CRC-ITU-T美国二进制同步系统CRC-32x32+x26 +x23 +x22 +x16 +x12 +x11+x10 +x8 +x7 +x5 +x4 +x2 +x+132231-1 =151.所有奇数个差错2.所有长度=14的随机错3.所有长度=32的突发错4.以1-12-23的概率检出长度为33的单个突发差错5.以1-12-32的概率检出长度大于

34、33的单个突发差错6.所有长度=2的两个突发错ATM(AAL)七、循环码的编码电路1.多项式运算的逻辑电路（1）基本单元电路七、循环码的编码电路（2）加（减）法七、循环码的编码电路（2）乘法ax3+bx2+cx+d ex2+fx+ggax3+gbx2+gcx+gdfax4+fbx3+fcx2 +fdx eax5+ebx4+ecx3 +edx2 移位相加七、循环码的编码电路（3）除法ax4 + bx3 + cx2 +dx +efx3 +gx2 +hx+iaf-1x + jf-1ax4 +af-1gx3 +af-1hx2+af-1ixjx3 +kx2 +lx +e jx3 +jf-1gx2 +jf-1hx +jf-1i七、循环码的编码电路 2.基于g(x)的n-k级编码器1)非系统码: 乘g(x)电路原理: C(x) m(x)g(x) (mod xn-1), 若m(x)k, 则C(x) = m(x)g(x). 因此可把m(x)作为信息多项式, 这样,编码电路实际上是一个乘g(x)电路. +g0g1gn-k-1