信息论-第六章-信道编码概要课件.ppt

1、循循 环环 码码本章节教学内容、基本要求、重点与难点本章节教学内容、基本要求、重点与难点 1.1.教学内容：教学内容：循环码的多项式描述与生成多项式。循环码的多项式描述与生成多项式。系统循环码。系统循环码。多项式运算电路。多项式运算电路。循环码的编码与译码电路。循环码的编码与译码电路。2.2.教学基本要求：教学基本要求：掌握掌握循环码循环码的编码方法。的编码方法。了解了解循环码的生成多项式的求法。循环码的生成多项式的求法。掌握掌握循环码循环码的编码电路的实现方法。的编码电路的实现方法。掌握循环码的解码算法和解码电路的实现方法。掌握循环码的解码算法和解码电路的实现方法。3.3.重点与难点：重点与

2、难点：循环码的生成多项式和编码电路。循环码的生成多项式和编码电路。循环码的译码。循环码的译码。循环码的特点循环码的特点:循环码是线性分组码的一个重要子类；循环码是线性分组码的一个重要子类；由于循环码具有由于循环码具有优良的代数结构优良的代数结构，使得循环码可用简单，使得循环码可用简单的反馈移位寄存器实现编码和伴随式计算，并可使用多的反馈移位寄存器实现编码和伴随式计算，并可使用多种简单而有效的译码方法；种简单而有效的译码方法；循环码是研究最循环码是研究最深入深入、理论最、理论最成熟成熟、应用最、应用最广泛广泛的一类的一类线性分组码。线性分组码。循环码的定义循环码的定义循环码循环码：如果：如果(n

3、,k)线性分组码的任意码矢线性分组码的任意码矢C C=(C Cn1,C Cn2,C C0)的的 i 次循环移位，所得矢量次循环移位，所得矢量C C(i)=(C Cn1i,C Cn2i,C C0,C Cn1,C Cni)仍是一个码矢，则称此线性码为仍是一个码矢，则称此线性码为(n,k)循环码。循环码。第六章信道编码循环码举例例 分析二进制码组000,110,101,011,00000,01111,10100,11011,0000,1101,0111,1011,1110是不是循环码。解 看码组符不符合线性和循环的条件。对于码组000,110,101,011，它既是线性码又是循环码。事实上，它是对0

4、0,01,10,11进行偶校验得到的码，是(3,2)循环码。对于码组00000,01111,10100,11011，它是线性码但不是循环码。事实上，它是对消息序列00,01,10,11进行编码得到的线性分组码(5,2)码。对于码组0000,1101,0111,1011,1110，它尽管满足循环性但由于不是线性码，故也不是循环码。循环码的多项式描述循环码的多项式循环码的多项式码多项式码多项式：为了运算的方便，将码矢的各分量作为多：为了运算的方便，将码矢的各分量作为多项式的系数，把码矢表示成多项式，称为码多项式。项式的系数，把码矢表示成多项式，称为码多项式。其一般表示式为其一般表示式为C C(x)

5、=Cn1xn1+Cn2xn2+C0)码多项式码多项式 i 次循环移位的表示方法次循环移位的表示方法 记码多项式记码多项式C C(x)的一次左移循环为的一次左移循环为 C C(1)(x)，i 次左移循次左移循环为环为 C C(i)(x)ininininnininnnnnnnnnCxCxCxCxCxCxCxCxCxCxCxCx1102211)(102312)1(02211)(C)(C)(C码多项式的模码多项式的模(xn+1)运算运算0和和1两个元素模两个元素模2运算下构成域。运算下构成域。若若 p 为素数，则整数全体在模为素数，则整数全体在模 p 运算下的剩余类全运算下的剩余类全 体体 在模在模

6、p 下构成域。下构成域。以以 p=3 为模的剩余类全体为模的剩余类全体 模模2运算的规则如下：运算的规则如下：1,3,2,1,0p120221010000210102202112100210构成域。2,1,0码矢码矢 C C 循环循环 1 次所得码矢的码多项式次所得码矢的码多项式C C(1)(x)相当于相当于C C(x)乘以乘以 x，再除以再除以(xn+1)所得的余式：所得的余式：上式表明上式表明：码矢循环一次的码多项式：码矢循环一次的码多项式 C C(1)(x)是原码多是原码多项式项式 C C(x)乘以乘以 x 除以除以(xn+1)的余式。写作的余式。写作同理可得同理可得：C C(x)的的

7、i 次循环移位次循环移位 C C(i)(x)是是 C C(x)乘以乘以 xi 除以除以(xn+1)的余式，即的余式，即1)(11)()1(1102123121nnnnnnnnnnxxCxCxCxCxCxCCxxxCC)1()()()1(nxxxx模CC)1()()()(niixxxx模CC第六章信道编码举例：(7,3)循环码，可由任一个码矢，比如(0011101)经过循环移位，得到其它6个非0码矢；也可由相应的码多项式(x4+x3+x2+1)，乘以xi(i=1,2,6)，再模(x7+1)运算得到其它6个非0码多项式。移位过程和相应的多项式运算如表6.3.1所示。循环码的多项式描述(7,3)循环

8、码的循环移位 移位次数 码 字 码多项式 0 0011101 x4+x3+x2+1(模 x7+1)1 0111010 x(x4+x3+x2+1)x5+x4+x3+x(模 x7+1)2 1110100 x2(x4+x3+x2+1)x6+x5+x4+x2(模 x7+1)3 1101001 x3(x4+x3+x2+1)x6+x5+x3+1(模 x7+1)4 1010011 x4(x4+x3+x2+1)x6+x4+x+1(模 x7+1)5 0100111 x5(x4+x3+x2+1)x5+x2+x+1(模 x7+1)6 1001110 x6(x4+x3+x2+1)x6+x3+x2+x(模 x7+1)循

9、环码的生成矩阵循环码的生成矩阵根据循环码的循环特性，可由一个码字的循环移位得根据循环码的循环特性，可由一个码字的循环移位得到其它的非到其它的非0 0码字。在码字。在(n,k)循环码的循环码的 2k 个码字中，取个码字中，取前前(k1)位皆为位皆为0的码字的码字 g g(x)（其次数其次数r=nk），），再再经经(k1)次循环移位，共得到次循环移位，共得到 k 个码字：个码字：g g(x),xg g(x),xk1 g g(x)循环码的生成多项式循环码的生成多项式)()()()()(21xxxxxxxxkkggggG 这 k 个码字显然是相互独立的，可作为码生成矩阵的 k 行，于是得到循环码的生成

10、矩阵 G(x)循环码的生成多项式循环码的生成多项式码的生成矩阵一旦确定，码就确定了；码的生成矩阵一旦确定，码就确定了；这就说明：这就说明：(n,k)循环码可由它的一个循环码可由它的一个(nk)次码多次码多项式项式 g g(x)来确定；来确定；所以说所以说 g g(x)生成了生成了(n,k)循环码，因此循环码，因此称称 g g(x)为码的为码的生成多项式生成多项式。多项式。次首是一个1)()()(0111knxxxxxknknknggggg设信息组设信息组 mm=(mk1,mk2,m0)，则相应的码字为则相应的码字为 C C(x)=mm GG(x)=(mk1xk1+mk2 1xk2+m0)g g

11、(x)=mm(x)g g(x)C C(x)n1；mm(x)是是 2k 个信息多项式的表示式；个信息多项式的表示式；所以所以 C C(x)即为相应即为相应 2k 个码多项式的表示式。个码多项式的表示式。因此，因此，g g(x)生成一个生成一个(n,k)线性码。线性码。C C(x)是是(nk)次多项式次多项式 g g(x)的倍式，所以的倍式，所以 g g(x)生成一个生成一个(n,k)循环码。循环码。结论：当求作一个当求作一个(n,k)循环码时，只要分解多项式循环码时，只要分解多项式(xn+1)，从从中取出中取出(nk)次因式作生成多项式即可次因式作生成多项式即可。例例(7,3)循环码的生成多项式

12、：循环码的生成多项式：分解多项式分解多项式 xn+1，取其取其4次因式作生成多项式次因式作生成多项式x7+1=(x+1)(x3+x2+1)(x3+x+1)可将一次和任一个三次因式的乘积作为生成多项式，可将一次和任一个三次因式的乘积作为生成多项式，因而可取因而可取 g g1(x)=(x+1)(x3+x2+1)=x4+x2+x+1 或或 g g2(x)=(x+1)(x3+x+1)=x4+x3+x2+1循环码的监督多项式和监督矩阵循环码的监督多项式和监督矩阵循环码的监督多项式循环码的监督多项式：设：设 g g(x)为为(n,k)循环码的生成多循环码的生成多项式，必为项式，必为(xn+1)的因式，则有

13、的因式，则有 xn+1=h h(x)g g(x)，式中式中h h(x)为为 k 次多项式，称为次多项式，称为(n,k)循环码的监督多项式。循环码的监督多项式。(n,k)循环码也可由其监督多项式完全确定。循环码也可由其监督多项式完全确定。例例：(7,3)循环码循环码 x7+1=(x3+x+1)(x4+x2+x+1)l4次多项式为生成多项式次多项式为生成多项式g g(x)=x4+x2+x+1=g4x4+g3x3+g2x2+g1x+g0l3次多项式是监督多项式次多项式是监督多项式h h(x)=x3+x+1=h3x3+h2x2+h1x+h0循环码的监督矩阵循环码的监督矩阵由等式由等式 x7+1=h h

14、(x)g g(x)两端同次项系数相等得两端同次项系数相等得将上面的方程组将上面的方程组 写成矩阵形式写成矩阵形式0000332463223145312213044302112033hghgxhghghgxhghghghgxhghghghgx的系数的系数的系数的系数Tggggghhhhhhhhhhhhhhhh001234321032103210321000000000000000上式中，列阵的元素是生成多项式上式中，列阵的元素是生成多项式 g g(x)的系数，是一个码字，的系数，是一个码字，那么第一个矩阵则为那么第一个矩阵则为(7,3)循环码的循环码的监督矩阵，即，即循环码监督矩阵的构成由上式可

15、见，监督矩阵的第一行是码的监督多项式由上式可见，监督矩阵的第一行是码的监督多项式 h h(x)的系数的系数的的反序排列反序排列，第二、三、四行是第一行的移位；，第二、三、四行是第一行的移位；可用监督多项式的系数来构成监督矩阵可用监督多项式的系数来构成监督矩阵000000000000H3210321032103210)3,7(hhhhhhhhhhhhhhhh的反多项式。表示其中)(h)(h0001011001011001011001011000)(h)(h)(h)(hH*3*2*)3,7(xxxxxxxxx系统循环码构成系统循环码构成设信息向量设信息向量 mm=(mk1,mk2,m0)信息多项式

16、信息多项式 mm(x)=mk1xk1+mk2 xk2+m0 码多项式码多项式的高次幂部分等于的高次幂部分等于mm(x)，即即 C C(x)=cn1xn1+cnkxnk+cnk1xnk1+c1x+c0 =xnk mm(x)+q q(x)q q(x)的次数的次数nk校验位多项式校验位多项式 q q(x)由于码多项式是生成多项式的倍式，所以由于码多项式是生成多项式的倍式，所以C C(x)=xnkmm(x)+q q(x)=a a(x)g g(x)0 0(mod g g(x)q q(x)=C C(x)+xnkmm(x)xnkmm(x)(mod g g(x)因此，因此，循环码的系统码形式为循环码的系统码形

17、式为C C(x)=xnkmm(x)+(xnkmm(x)mod g g(x)系统循环码系统循环码系统循环码构造过程步骤系统循环码构造过程步骤信息多项式乘信息多项式乘 xnk：xnkmm(x)对对 xnkmm(x)求余式：求余式：q q(x)xnkmm(x)(mod g g(x)求码多项式：求码多项式：C C(x)=xnkmm(x)+(xnkmm(x)mod g g(x)=xnkmm(x)+q q(x)令令 mm(x)为单项式为单项式 xnk+i，i=0,1,2,k1xnk+i=a a(x)g g(x)+q qi(x)，q qi(x)的次数的次数nkC Ci(x)=xnk+i+q qi(x)可见：

18、可见：C Ci(x)对应的向量对应的向量C Ci，i=0,1,2,k1是线性无关的，是线性无关的，从而得到循环码系统码的生成矩阵从而得到循环码系统码的生成矩阵 GGs 为为1,01,00,01,21,20,21,11,10,1021100010001100010001knknkkkknkkkkksqqqqqqqqqqqqG例例：(7,4)循环码循环码 g g(x)=x3+x+1，x6=(x3+x2+1)g g(x)+(x2+1)q q3(x)=(x2+1)C C3(x)=x6+x2+1 x5=(x2+1)g g(x)+(x2+x+1)q q2(x)=(x2+x+1)C C2(x)=x5+x2+

19、x+1 x4=xg g(x)+(x2+x)q q1(x)=(x2+x)C C1(x)=x4+x2+xx3=g g(x)+(x+1)q q0(x)=(x+1)C C0(x)=x3+x+1)()()()1()()1(1101000011010011100101010001223xxxxxxxxsggggG线性码的译码是根据线性码的译码是根据接收字多项式的伴随式接收字多项式的伴随式和和可纠的可纠的错误图样错误图样间的一一对应关系，间的一一对应关系，由伴随式得到错误图样由伴随式得到错误图样；循环码是线性码的一个特殊子类，循环码的译码与线循环码是线性码的一个特殊子类，循环码的译码与线性码的译码步骤基本一

20、致。不过由于循环码的循环特性码的译码步骤基本一致。不过由于循环码的循环特性，使它的译码更加性，使它的译码更加简单易行简单易行；循环码的译码过程仍包括三个步骤：循环码的译码过程仍包括三个步骤：接收多项式的伴随式计算；接收多项式的伴随式计算；求伴随式对应的错误图样；求伴随式对应的错误图样；用错误图样纠错。用错误图样纠错。循环码的译码循环码的译码1.伴随式s(x)定义 s(x)=r(x)(mod g(x)r-1次多项式于是，s(x)=e(x)(mod g(x)因为 r(x)=c(x)+e(x)2.检错s(x)=0?方法多项式求余电路(图6.3.17)循环码的译码循环码的译码1.已知（7,4）循环码的

21、生成多项式 ，求它的系统形式的生成矩阵。解答：例一3()1g xxx10110000101 10000101 10000101 1G将第四行加到第二行把第三、四行加到第一行101010101001 1 100101 10000101 1sG1.已知（7,4）循环码的生成多项式 ，若已知接收码的最高码元发生错误，求伴随多项式；若已知接收码字为（0001110），求发送码字。例二3()1g xxx 623()()(1)mod()()1e xxs xxg xg xxx求s(x)的计算实际上是对g(x)做除法求余运算解答：已知E=(1000000)，对应的错误图样多项式为e(x)=x6，则对应的伴随式

22、为S=(101)接收码字(0001110)的码多项式为32()R xxxx3223()()()(1)mod()()()1e xR xxxxs xxg xg xg xxx解答：根据s(x)从译码表中找对应的错误图样多项式为x6，可得到发送码字的估值：326()()()(1001110)C xR xe xxxxx(1)根据伴随式定义根据伴随式定义 S ST=HRHRT 计算伴随式计算伴随式S S(2)用用 k 级移位寄存器的伴随式计算电路级移位寄存器的伴随式计算电路(3)用用 nk 级移位寄存器的伴随式计算电路级移位寄存器的伴随式计算电路(4)接收字循环移位的伴随式与伴随式循环移位的关系接收字循环

23、移位的伴随式与伴随式循环移位的关系接收矢量伴随式计算接收矢量伴随式计算(1)根据伴随式定义根据伴随式定义 S ST=HRHRT 计算伴随式计算伴随式S S设设设设的行矢量。表示其中HhhhhH)0,2,1(021knkniiknknTTknTknTknknknknTTTknknSSSSSSRhRhRhRhhhSHRSS021021021021),(表示式，得到伴随式各分量的这是前面介绍过的由接收矢量相应分量直接求和计算伴这是前面介绍过的由接收矢量相应分量直接求和计算伴随式的方法，对所有线性码都适用。随式的方法，对所有线性码都适用。电路是电路是(nk)个多输入的奇偶校验器，每个奇偶校验器个多输入

24、的奇偶校验器，每个奇偶校验器的输入端由的输入端由 H H 阵的相应行阵的相应行 h hi 中的中的1决定（参看上图）决定（参看上图）TTknknTknknSSSRhRhRh002211所以R0R1R2R3R4R5R6输入S0(7,3)码伴随式计算电路S3S2S1输出0123045156345634601234561000110010001100101110001101SSSSRRRRRRRRRRRRRRRRRRRRTTRHSnkknGmC11rkknkQIGkrTrkTkrrkrkrSrkkSPQPQIPHQIG)()(或(2)用用 k 级移位寄存器的伴随式计算电路级移位寄存器的伴随式计算电路

25、定理：二元线性系统码中，接收矢量：二元线性系统码中，接收矢量 R R 的伴随式的伴随式 S S 等于等于对 R 的信息部分所计算的监督数字（相当于对（相当于对 R R 的信息部分重新编码）与的信息部分重新编码）与接收的监督数字的矢量和。的矢量和。证明证明：设接收矢量设接收矢量 R R=(R RI R RP)R RI 是是 R R 的信息部分，长度为的信息部分，长度为 k 的矢量的矢量R RP 是是 R R 的监督数字部分，长为的监督数字部分，长为 r=(nk)的矢量的矢量监督矩阵为监督矩阵为 HH=(P Prk I Ir)由伴随式的定义由伴随式的定义(见上页见上页,续下页续下页)由由rrkkr

26、rkkrrkkrkrkrkPIPTIrPTIrTPITrkrPITrnnr111111111111RQRRPRIRPRIPRRIPRRHRS的监督元。作信息元重新编码计算是把阶子阵，所以阵除单位子阵外的是注意到ITIkrrkkkrRPRHP1)(由由TrkkkrkkkknkkkknknkkknknkjjkjkjknikinnkkknnnrkkknkkkknknnkmmmmmmqqqqqqqqqmmmCCCknjqmqmqmCkimC,mmmCCCqqqqqqqqqPQ,2,1,2,1G),(),(CQI100010001G021021)(21)(22221)(1121102102102211)

27、(0210211)(21)(22221)(11211得将上式代入(1)为什么要用缩短循环码为什么要用缩短循环码 在系统设计中，如果不能找到一种合适自然长度或合在系统设计中，如果不能找到一种合适自然长度或合适信息位数目的码，则需要将码组缩短，以满足系统的要适信息位数目的码，则需要将码组缩短，以满足系统的要求。求。(2)缩短循环码的构造缩短循环码的构造 将码组缩短的基本方法是：设法使满足前面若干个码将码组缩短的基本方法是：设法使满足前面若干个码元符号为元符号为0，且不发送这些符号。对，且不发送这些符号。对(n,k)系统循环码，只系统循环码，只要令前要令前 l 个信息数字为个信息数字为0(lk)，就

28、可将就可将(n,k)循环码缩短为循环码缩短为(nl,kl)线性码。称这种码组长度缩短了的循环码为缩线性码。称这种码组长度缩短了的循环码为缩短循环码。短循环码。缩短循环码缩短循环码(3)缩短循环码的性能缩短循环码的性能一般情况下，删去前一般情况下，删去前 l 个个0之后的缩短码，就失去了循环特性。在纠之后的缩短码，就失去了循环特性。在纠错能力上缩短码至少与原码相同。错能力上缩短码至少与原码相同。由于删去前面由于删去前面 l 个个0信息元并不影响监督位和伴随式的计算，可用原信息元并不影响监督位和伴随式的计算，可用原循环码的编译码电路来完成缩短码的编译码。循环码的编译码电路来完成缩短码的编译码。若用

29、原循环码译码电路来译缩短循环码，则应修改错误图样检测电路，若用原循环码译码电路来译缩短循环码，则应修改错误图样检测电路，使原来对包含最高阶位使原来对包含最高阶位 xn1上的一个错误图样进行检测，修改为对上的一个错误图样进行检测，修改为对包含包含 xnl1位上的一个错误图样进行检测。位上的一个错误图样进行检测。错误图样检测电路的输出是和包含错误图样检测电路的输出是和包含 xnl1位上的错误相对应的，即当位上的错误相对应的，即当 xnl1位上的接收符号是错误的时，检测电路输出为位上的接收符号是错误的时，检测电路输出为“1”，否则为，否则为“0”。当当 xnl1位上错误被纠正时，还应消除位上错误被纠

30、正时，还应消除 enl1 对伴随式的影响。在检对伴随式的影响。在检测到测到xnl1位上有错时，将位上有错时，将 g g(x)除除 xnl1 的余式加入此时的伴随式即的余式加入此时的伴随式即可消除。可消除。循环码的捕错译码循环码的捕错译码一般适用于短码或低码率的译码；一般适用于短码或低码率的译码；用于纠突发错误的译码是很有效的。用于纠突发错误的译码是很有效的。循环码的大数逻辑译码循环码的大数逻辑译码从码的结构出发，可导出大数逻辑译码法；从码的结构出发，可导出大数逻辑译码法；具有译码设备简单、速度快的优点，因而应用相当广具有译码设备简单、速度快的优点，因而应用相当广泛。泛。循环码的其它译码方法循环码的其它译码方法BCH码：码：由由 Hocgenghem 和和 Bose 及及 Chaudhuri 分分别提出的纠正多个随机错误的循环码。别提出的纠正多个随机错误的循环码。多元多元BCH码：码：多元多元 BCH 码的生成多项式是以码的生成多项式是以 GF(q)的扩域的扩域GF(qr)上的元素为根的多项式。上的元素为根的多项式。RS码：码：当当 r=1 时的时的 q 元元 BCH 码是多元码是多元 BCH 码的特码的特殊子类，称为殊子类，称为 Reed-Solomon码码，简称，简称 RS 码。码。BCH码和码和RS码码