信息论与编码理论2012ch6 信道编码循环码2

1、第六章 信道编码2022/3/141 Please enjoy the pain which is unable to avoid.第六章 信道编码2022/3/1426.3.1 循环码的多项式描述循环码的多项式描述6.3.2 循环码的生成多项式循环码的生成多项式6.3.3 系统循环码系统循环码6.3.4 多项式运算电路多项式运算电路6.3.5 循环码的编码电路循环码的编码电路6.3.6 循环码的译码循环码的译码6.3.7 循环汉明码循环汉明码6.3.8 缩短循环码缩短循环码6.3.9 循环码的其它译码方法循环码的其它译码方法6.3 循环码循环码第六章 信道编码2022/3/1436.3.5.

2、1 非系统码编码电路非系统码编码电路6.3.5.2 系统码编码电路系统码编码电路(1) 循环码编码的基本原理循环码编码的基本原理(2) 用用 (nk) 级移位寄存器实现的编码电路级移位寄存器实现的编码电路(3) 用用 k 级移位寄存器实现的编码电路级移位寄存器实现的编码电路6.3.5 循环码的编码电路循环码的编码电路第六章 信道编码2022/3/1446.3.5 循环码的编码电路循环码的编码电路第六章 信道编码2022/3/145循环码码式是生成多项式倍式。循环码码式是生成多项式倍式。非系统编码电路非系统编码电路/循环码乘法编码电路循环码乘法编码电路输入输入 a a(x)=mm(x)， mm(

3、x)的次数的次数 k输出输出 a a(x)g g(x)=C C(x)即是码式，即是码式，C C(x)的次数的次数 n举例：举例：生成生成 (7,4) 汉明码的生成多项式为汉明码的生成多项式为 g g(x)=x3+ x2+1，非系，非系统编码电路如图统编码电路如图6.3.13所示。电路共工作所示。电路共工作7个时钟节拍。个时钟节拍。6.3.5.1 非系统码编码电路非系统码编码电路第六章 信道编码2022/3/146由表由表6.3.2可见，当可见，当 mm(x)=x3 + x时，非系统码字时，非系统码字 C C(x) 为为 C C(x)= x6 + x5 +x4 + x =(x3+x)(x3 +

4、x2 +1)6.3.5.1 非系统码编码电路非系统码编码电路第六章 信道编码2022/3/147(1) 系统码编码的基本原理系统码编码的基本原理求生成多项式求生成多项式g g(x)：分解多项式分解多项式 (xn+1)，取，取 (nk)次次 因式作生因式作生成多项式成多项式 g g(x)，一般可通过查表完成。，一般可通过查表完成。利用利用 g g(x) 实现实现编码编码设设信息多项式信息多项式为为 mm(x)=mk1xk1+mk2 xk2+m0设设校验多项式校验多项式为为 r r(x)=rr1xr1+rr2 xr2+r0(n,k) 循环码的循环码的码多项式码多项式为为C C(x)=Cn1xn1+

5、Cn2xn2+Cnkxnk+Cnk1xnk1+C1x+C0 前前 k 项系数为信息位，后项系数为信息位，后 r= nk 项为校验位。项为校验位。所以所以 Cn1xn1+Cnkxnk=xnk(mk1xk1+m0)=xnkmm(x) Cnk1xnk1+C0=rr1xr1+r0=r r(x)6.3.5.2 系统码编码电路系统码编码电路第六章 信道编码2022/3/148(2) 用用 (nk) 级移位寄存器实现的编码电路级移位寄存器实现的编码电路循环码编码电路结构和工作原理循环码编码电路结构和工作原理工作原理工作原理：二元：二元 (n,k) 循环码的编码是将信息多项式循环码的编码是将信息多项式 mm(

6、x) 乘乘 xnk 后再除以生成多项式后再除以生成多项式 g g(x) 求出它的余式，即为监求出它的余式，即为监督数字多项式督数字多项式 r r(x)。C C(x)= xnkmm(x)+ (xnkmm(x) mod g g(x)二元二元 (n,k) 循环码的编码电路就是以循环码的编码电路就是以 g g(x) 为除式的除法电为除式的除法电路，而输入的被除式为路，而输入的被除式为 xnkmm(x) 。实际的编码电路如图实际的编码电路如图6.3.15所示。所示。其级数等于其级数等于 g g(x) 的次数的次数 (nk) ；反馈连接决定于反馈连接决定于 g g(x) 的系数的系数 当当 gi=0 时时

7、 (i=0,1,2, nk)，反馈断开；，反馈断开； 当当 gi=1 时，对应级加入反馈。时，对应级加入反馈。6.3.5.2 系统码编码电路系统码编码电路第六章 信道编码2022/3/149由于被除式中含有因子由于被除式中含有因子 xnk ，使被除式各项的次数都，使被除式各项的次数都 g g(x) 的次数，所以被除式输入端可由第一级移到末级之的次数，所以被除式输入端可由第一级移到末级之后，使移位次数减少后，使移位次数减少 (nk) 次。这样编一个码字求监督数次。这样编一个码字求监督数字所需的移位次数只要字所需的移位次数只要 k 次。次。6.3.5.2 系统码编码电路系统码编码电路第六章 信道编

8、码2022/3/1410工作过程工作过程：各级移位寄存器清各级移位寄存器清“0”，控制门开，开关，控制门开，开关 K 设置为设置为位置位置1；k 位信息数字位信息数字 mk1, mk2,m1, m0 依次从末端输入编码电依次从末端输入编码电路；同时送入信道，路；同时送入信道，在每加入一位信息数字时，各级移位在每加入一位信息数字时，各级移位寄存器移位一次寄存器移位一次。当。当 k 位信息数字都输入移位寄存器后，位信息数字都输入移位寄存器后，移位寄存器中移位寄存器中 (nk) 位数字即为监督数字；位数字即为监督数字；控制门关，断开反馈，开关控制门关，断开反馈，开关 K 由由位置位置1转到转到位置位

9、置2，寄存器，寄存器中的存数（监督数字）依次移出，送入信道。中的存数（监督数字）依次移出，送入信道。k 位信息数位信息数字和字和 (nk) 位监督数字组成一个码字。位监督数字组成一个码字。6.3.5.2 系统码编码电路系统码编码电路第六章 信道编码2022/3/1411举例：举例：由由 g g(x)=(x3+x +1) 作生成多项式所生成的作生成多项式所生成的 (7,4) 循环码的编循环码的编码电路如图码电路如图6.3.16所示。所示。它包括它包括 3 级寄存器级寄存器g1=1，第一级反馈接通；，第一级反馈接通；g2=0，到第二级的反馈断开。，到第二级的反馈断开。6.3.5.2 系统码编码电路

10、系统码编码电路 每经四次移位，输入一个每经四次移位，输入一个四位信息组；寄存器中的四位信息组；寄存器中的内容即为监督数字；内容即为监督数字； 监督数字跟在信息数字之监督数字跟在信息数字之后，便构成一个码字。后，便构成一个码字。第六章 信道编码2022/3/1412(3) 用用 k 级移位寄存器实现的编码电路级移位寄存器实现的编码电路循环码的监督方程循环码的监督方程在在 (nk) 循环码中，若循环码中，若 k (1/2)n，即信息位比监督位少时，即信息位比监督位少时，可采用可采用 k 级移位寄存器的编码电路。级移位寄存器的编码电路。根据线性码的监督方程根据线性码的监督方程为任意码字。式中位监督数

11、字位信息数字),(02121knknknkknnnTTCCCCCCC0HC6.3.5.2 系统码编码电路系统码编码电路001110110110011111111),(kkkknknhhhhhhhhHH用下式代入第六章 信道编码2022/3/1413 得得 由此得到由此得到 (nk) 个监督方程，进而得到个监督方程，进而得到 (nk) 个监督数字的个监督数字的表示式表示式6.3.5.2 系统码编码电路系统码编码电路TknknnkkkkCCCChhhhhhhh00111111111100111011011001111011312212111ChChCCChChCCChChCCkkkknknnknk

12、nknnkn位11111kkhh位11111kkhh第六章 信道编码2022/3/1414监督数字表示式特点监督数字表示式特点每个监督码元都是由它前面的每个监督码元都是由它前面的 k 个码元按同一规律确定的；个码元按同一规律确定的；第一个监督元第一个监督元 Cnk1 是是 k 个信息元与个信息元与 h h(x) 的系数决定的；的系数决定的；第二个监督元是前面第二个监督元是前面 (k1) 个信息元和第一个监督元与个信息元和第一个监督元与 h h(x) 的系数决定的；的系数决定的；，如此类推；，如此类推；最后一个监督元最后一个监督元 C0 都按同一规律决定。都按同一规律决定。6.3.5.2 系统码

13、编码电路系统码编码电路1111011312212111ChChCCChChCCChChCCkkkknknnknknknnkn第六章 信道编码2022/3/1415电路如图电路如图6.3.17所示所示6.3.5.2 系统码编码电路系统码编码电路第六章 信道编码2022/3/1416工作过程工作过程：门门1开，门开，门2关，关，k 位信息串行送入位信息串行送入 k 级移位寄存器，并同级移位寄存器，并同时送入信道；时送入信道；门门1关，门关，门2开，每移位一次输出一位监督数字，并同时送开，每移位一次输出一位监督数字，并同时送入信道，经入信道，经 (nk) 次移位，就在次移位，就在 k 位信息数字之后

14、附加上位信息数字之后附加上 (nk) 位监督数字，构成了一个码字。位监督数字，构成了一个码字。举例：举例：利用监督多项式构造利用监督多项式构造 (7,3) 循环码的编码电路。循环码的编码电路。x7+1=(x+1)(x3+x+1)(x3+x2+1)任取一个三次因式为监督多项式任取一个三次因式为监督多项式 h h(x)=x3+x+1得得 h3=1, h2=0, h1=1, h0=16.3.5.2 系统码编码电路系统码编码电路第六章 信道编码2022/3/1417由三级移位寄存器构成的由三级移位寄存器构成的 (7,3) 循环码的编码电路如图循环码的编码电路如图6.3.18所示。所示。6.3.5.2

15、系统码编码电路系统码编码电路第六章 信道编码2022/3/1418线性码的译码是根据线性码的译码是根据接收字多项式的伴随式接收字多项式的伴随式和和可纠的错误图可纠的错误图样样间的一一对应关系，间的一一对应关系，由伴随式得到错误图样由伴随式得到错误图样；循环码是线性码的一个特殊子类，循环码的译码与线性码的循环码是线性码的一个特殊子类，循环码的译码与线性码的译码步骤基本一致。不过由于循环码的循环特性，使它的译译码步骤基本一致。不过由于循环码的循环特性，使它的译码更加码更加简单易行简单易行；循环码的译码过程仍包括三个步骤：循环码的译码过程仍包括三个步骤：接收多项式的伴随式计算；接收多项式的伴随式计算

16、；求伴随式对应的错误图样；求伴随式对应的错误图样；用错误图样纠错。用错误图样纠错。6.3.6.1 接收矢量伴随式计算接收矢量伴随式计算6.3.6.2 循环码的通用译码法循环码的通用译码法6.3.6 循环码的译码循环码的译码第六章 信道编码2022/3/1419(1) 根据伴随式定义根据伴随式定义 S ST=HRHRT 计算伴随式计算伴随式S S(2) 用用 k 级移位寄存器的伴随式计算电路级移位寄存器的伴随式计算电路(3) 用用 nk 级移位寄存器的伴随式计算电路级移位寄存器的伴随式计算电路(4) 接收字循环移位的伴随式与伴随式循环移位的关系接收字循环移位的伴随式与伴随式循环移位的关系6.3.

17、6.1 接收矢量伴随式计算接收矢量伴随式计算第六章 信道编码2022/3/1420(1) 根据伴随式定义根据伴随式定义 S ST=HRHRT 计算伴随式计算伴随式S S设设设设的行矢量。表示其中HhhhhH)0 , 2, 1(021knkniiknkn6.3.6.1 接收矢量伴随式计算接收矢量伴随式计算TTknTknTknknknknTTTknknSSSSSSRhRhRhRhhhSHRSS021021021021),(表示式，得到伴随式各分量的第六章 信道编码2022/3/1421这是前面介绍过的由接收矢量相应分量直接求和计算伴随式这是前面介绍过的由接收矢量相应分量直接求和计算伴随式的方法，对

18、所有线性码都适用。的方法，对所有线性码都适用。电路是电路是 (nk) 个多输入的奇偶校验器，每个奇偶校验器的输个多输入的奇偶校验器，每个奇偶校验器的输入端由入端由 H H 阵的相应行阵的相应行 h hi 中的中的1决定（参看图决定（参看图6.2.7）6.3.6.1 接收矢量伴随式计算接收矢量伴随式计算TTknknTknknSSSRhRhRh002211所以第六章 信道编码2022/3/14226.3.6.1 接收矢量伴随式计算接收矢量伴随式计算0123045156345634601234561000110010001100101110001101SSSSRRRRRRRRRRRRRRRRRRRR

19、TTRHS)11. 2 . 6(11nkknGmC)12. 2 . 6(rkknkQIGkrTrkTkrrkrkrSrkkSPQPQIPHQIG)()(或第六章 信道编码2022/3/1423(2) 用用 k 级移位寄存器的伴随式计算电路级移位寄存器的伴随式计算电路定理定理6.3.66.3.6：二元线性系统码中，接收矢量：二元线性系统码中，接收矢量 R R 的伴随式的伴随式 S S 等于等于对对 R R 的信息部分所计算的监督数字的信息部分所计算的监督数字（相当于对（相当于对 R R 的信息部分的信息部分重新编码）与重新编码）与接收的监督数字接收的监督数字的矢量和。的矢量和。证明证明：设接收矢

20、量设接收矢量 R R=(R RI R RP)R RI 是是 R R 的信息部分，长度为的信息部分，长度为 k 的矢量的矢量R RP 是是 R R 的监督数字部分，长为的监督数字部分，长为 r=(nk) 的矢量的矢量监督矩阵为监督矩阵为 HH=(P Prk I Ir)由伴随式的定义由伴随式的定义6.3.6.1 接收矢量伴随式计算接收矢量伴随式计算第六章 信道编码2022/3/1424由由111111111111SRHPRRPIRRIRPRIRPRRQRr kkrkrkr krkr krkk rrTrnn rTTIPr krIPrTIPrTIPIP1PH()RPRkr kr kTIIrk注意到是

21、阵除单位子阵外的阶子阵，所以是把作信息元重新编码计算的监督元。6.3.6.1 接收矢量伴随式计算接收矢量伴随式计算第六章 信道编码2022/3/1425由由6.3.6.1 接收矢量伴随式计算接收矢量伴随式计算11121()21222()12()1120120()1 1220100010GIQ(6.2.12)001C(,)(,)G1,2,n kn kk nkk rkkk n knnnkkk nn ik inkjkjkjkjqqqqqqqqqCCCmmm,CmikCmqmqm qj将上式代入得11121()121222()212012()0120120(6.2.13)1,2,QPn kn kn k

22、n kkkkkk n kTkkk rkkr knkqqqCqqqCmmmqqqCmmmmmm 第六章 信道编码2022/3/1426电路的工作步骤电路的工作步骤门门1通，门通，门2、3、4关，接收字关，接收字R R的的 k 位信息部分输入编码器；位信息部分输入编码器；门门1关，门关，门2、3、4通，接收信息编码所得的监督数字与接收通，接收信息编码所得的监督数字与接收监督数字逐位模监督数字逐位模2和，得到伴随式。但这种伴随式计算方法只和，得到伴随式。但这种伴随式计算方法只适用于线性适用于线性系统码系统码。6.3.6.1 接收矢量伴随式计算接收矢量伴随式计算第六章 信道编码2022/3/1427(

23、3) 用用 (nk) 级移位寄存器的伴随式计算电路级移位寄存器的伴随式计算电路设接收多项式为设接收多项式为 R R(x)，它的信息部分表示为，它的信息部分表示为 R RI(x)，监督部分表，监督部分表示为示为 R RP(x)；由由定理定理6.3.6知知 S S(x)=r r (x)+R RP(x)，其中，其中 r r (x) 是对是对 R RI(x) 重新编重新编码的监督数字多项式；码的监督数字多项式；若码的生成多项式为若码的生成多项式为 g g(x)，则，则 r r (x)R RI(x) (mod g g(x) C C(x)= xnkmm(x)+q q(x)=a a(x)g g(x)0 0

24、(mod g g(x) q q(x)=C C(x)+ xnkmm(x)xnkmm(x) (mod g g(x)6.3.6.1 接收矢量伴随式计算接收矢量伴随式计算第六章 信道编码2022/3/14286.3.6.1 接收矢量伴随式计算接收矢量伴随式计算)4 . 3 . 6()(mod)()()()()()(xxxxxxxPIPgRRRSgR，所以又因为又因为上式表明上式表明：循环码接收多项式的伴随式是接收多项式：循环码接收多项式的伴随式是接收多项式 R R(x) 除除以以 g g(x) 的余式。的余式。设设 E E(x) 为为 R R(x) 的错误图样，那么的错误图样，那么 R R(x)=C

25、C(x)+E E(x)，由于，由于 C C(x)为为 g g(x) 的倍式，所以的倍式，所以S S(x)C C(x)+E E(x)E E(x) (mod g g(x)上式表明上式表明：伴随式是由错误图样决定的，与具体码字无关伴随式是由错误图样决定的，与具体码字无关。说明说明：循环码伴随式的表示式循环码伴随式的表示式 (6.3.4) 是由系统码推出的，但是由系统码推出的，但由于伴随式仅与错误图样有关，因而对非系统码也是适用的由于伴随式仅与错误图样有关，因而对非系统码也是适用的。第六章 信道编码2022/3/1429由式由式 (6.3.4) 可画出用可画出用 (nk) 级移位寄存器计算循环码伴随式

26、级移位寄存器计算循环码伴随式的电路，如图的电路，如图6.3.20所示。所示。这是一个这是一个 (nk) 级除法求余电路，它与编码除法电路的区别级除法求余电路，它与编码除法电路的区别是：由于被除式是：由于被除式 R R(x) 不含不含 x 的幂的因子，所以接收矢量（被的幂的因子，所以接收矢量（被除式）应由第一级前加入。除式）应由第一级前加入。6.3.6.1 接收矢量伴随式计算接收矢量伴随式计算第六章 信道编码2022/3/1430(4) 接收字循环移位的伴随式与伴随式循环移位的关系接收字循环移位的伴随式与伴随式循环移位的关系定理定理6.3.76.3.7：设设 S S(x) 为接收矢量为接收矢量

27、R R(x) 的伴随式，则的伴随式，则 R R(x) 的循的循环移位环移位 xR R(x) (mod (xn+1) ) 的伴随式的伴随式 S S(1)(x) 等于伴随式等于伴随式 S S(x) 的循环移位的循环移位 xS S(x) (mod g g(x) )，即，即S S(1)(x)xS S(x) (mod g g(x) ) 证明证明：由伴随式计算式由伴随式计算式(6.3.4)知知S S(x)R R(x) (mod g g(x) ) 对上式两边作同余运算得对上式两边作同余运算得 xS S(x)xR R(x) (mod g g(x) ) (6.3.5)令令 R R(1)(x)xR R(x) (m

28、od (xn+1) ) (6.3.6)即用即用 R R(1)(x) 表示表示 R R(x) 循环移位一次循环移位一次 (mod (xn+1) ) 的码多的码多项式。项式。6.3.6.1 接收矢量伴随式计算接收矢量伴随式计算第六章 信道编码2022/3/1431对式对式 (6.3.6) 进行模进行模 g g(x) 运算，得到运算，得到 R R(x) 循环移位循环移位 xR R(x) 的伴随式的伴随式 S S(1)(x)xR R(x) (mod g g(x) ) 考虑到式考虑到式(6.3.5)，则有，则有 S S(1)(x)xS S(x) (mod g g(x) ) 上式说明：上式说明：接收矢量的

29、循环移位（接收矢量的循环移位（mod (xn+1) 运算运算下）与伴随式在模下）与伴随式在模 g g(x) 运算下（即在除以运算下（即在除以 g g(x) 的伴的伴随式计算电路中）的循环移位是一一对应的。随式计算电路中）的循环移位是一一对应的。6.3.6.1 接收矢量伴随式计算接收矢量伴随式计算 xS S(x)xR R(x) (mod g g(x) ) (6.3.5)R R(1)(x)xR R(x) (mod (xn+1) ) (6.3.6)第六章 信道编码2022/3/1432(1) 循环码的译码器的组成循环码的译码器的组成（梅吉特译码法）（梅吉特译码法）循环码的译码基本上按线性分组码的译码

30、步骤进行循环码的译码基本上按线性分组码的译码步骤进行,不过由于不过由于码的循环移位特性使译码电路大为简化。码的循环移位特性使译码电路大为简化。通用的循环码译码器如图通用的循环码译码器如图6.3.21所示。所示。6.3.6.2 循环码的通用译码法循环码的通用译码法第六章 信道编码2022/3/1433循环码通用译码器三个组成部分循环码通用译码器三个组成部分 伴随式计算电路伴随式计算电路：可根据实际情况选取不同的伴随式电路。：可根据实际情况选取不同的伴随式电路。 错误图样检测器错误图样检测器：是一个组合逻辑电路，其作用是将伴随式：是一个组合逻辑电路，其作用是将伴随式译为错误图样。它的工作原理为：译

31、为错误图样。它的工作原理为：当且仅当错误图样是一个可纠的错误图样，并且此错误当且仅当错误图样是一个可纠的错误图样，并且此错误图样包含最高阶位上的一个错误时，伴随式计算电路计图样包含最高阶位上的一个错误时，伴随式计算电路计算得到的伴随式才使检测电路输出为算得到的伴随式才使检测电路输出为“1”。 即如果错误图样检测器输出为即如果错误图样检测器输出为“1”，则认为最高阶，则认为最高阶位上接收符号是错误的，应该给以纠正；位上接收符号是错误的，应该给以纠正； 即如果检测器输出为即如果检测器输出为“0”，则认为最高阶位上接收，则认为最高阶位上接收符号是正确的，不必纠正。符号是正确的，不必纠正。6.3.6.

32、2 循环码的通用译码法循环码的通用译码法第六章 信道编码2022/3/1434对于码组中任何位置上的错误，通过码组和伴随式同时对于码组中任何位置上的错误，通过码组和伴随式同时循环移位，当错误符号移到最高阶位上时，伴随式则使循环移位，当错误符号移到最高阶位上时，伴随式则使检测器输出为检测器输出为“1” ，将其错误纠正。，将其错误纠正。通过循环移位后，能使可纠错误图样中的全部错误都得通过循环移位后，能使可纠错误图样中的全部错误都得到纠正。到纠正。 接收矢量缓存器和模接收矢量缓存器和模2 2和纠错电路和纠错电路。6.3.6.2 循环码的通用译码法循环码的通用译码法第六章 信道编码2022/3/143

33、5(2) 循环码译码电路工作过程循环码译码电路工作过程将接收矢量移入伴随式计算电路，计算出伴随式；同时将接将接收矢量移入伴随式计算电路，计算出伴随式；同时将接收矢量移入缓存器。收矢量移入缓存器。伴随式写入错误图样检测器，并在检测器中循环移位伴随式写入错误图样检测器，并在检测器中循环移位 (mod g g(x)，同时将接收矢量移出缓存器。，同时将接收矢量移出缓存器。当检测器输出当检测器输出“1”时，表示缓存器此时输出符号是错误的，时，表示缓存器此时输出符号是错误的，并将错误纠正；同时检测器输出反馈到伴随式计算电路的输并将错误纠正；同时检测器输出反馈到伴随式计算电路的输入端，去修改伴随式，从而消除

34、错误对伴随式所产生的影响。入端，去修改伴随式，从而消除错误对伴随式所产生的影响。直到接收矢量全部移出缓存器，该接收矢量纠错完毕。直到接收矢量全部移出缓存器，该接收矢量纠错完毕。若最后伴随式寄存器中为全若最后伴随式寄存器中为全“0”，则表示错误全部被纠正，则表示错误全部被纠正，否则检出了不可纠的错误图样。否则检出了不可纠的错误图样。说明说明：随着码长随着码长 n 和纠错能力和纠错能力 t 的增加，错误图样检测器的组的增加，错误图样检测器的组合逻辑电路变得很复杂，甚至难以实现。合逻辑电路变得很复杂，甚至难以实现。6.3.6.2 循环码的通用译码法循环码的通用译码法第六章 信道编码2022/3/14

35、36(1) 循环汉明码的性能循环汉明码的性能(2) (7,4)循环汉明码的译码循环汉明码的译码(3) (15,11)循环汉明码的译码循环汉明码的译码6.3.7 循环汉明码循环汉明码第六章 信道编码2022/3/1437(1) 循环汉明码的性能循环汉明码的性能既约多项式既约多项式：设设 f(x) 是次数大于零的多项式，若除了常数和是次数大于零的多项式，若除了常数和常数与本身的乘积以外，再不能被域常数与本身的乘积以外，再不能被域 Fp 上的其它多项式除尽，上的其它多项式除尽，则称则称 f(x) 为域为域 Fp 上的既约多项式。上的既约多项式。本原多项式本原多项式：GF(2)上的上的 m 次既约多项

36、式有两大类。一类是能次既约多项式有两大类。一类是能够被够被 (xn+1) 整除，但不能被整除，但不能被(xs+1) 整除（整除（n=2m1,sn），它的），它的根是根是 GF(2m) 扩域中的本原元素，这一类称为本原多项式扩域中的本原元素，这一类称为本原多项式。另一另一类多项式，它不仅能被类多项式，它不仅能被 (xn+1) 整除，也能整除整除，也能整除(xs+1)，它的根不，它的根不是扩域是扩域 GF(2m) 中的本原元素，称这类既约多项式为中的本原元素，称这类既约多项式为非本原多项非本原多项式式。循环汉明码循环汉明码：以以 r (n= 2r1) 次本原多项式为生成多项式的循次本原多项式为生成

37、多项式的循环码，称为循环汉明码。环码，称为循环汉明码。6.3.7 循环汉明码循环汉明码第六章 信道编码2022/3/1438循环汉明码的参数循环汉明码的参数码长码长 n= 2r1监督位数监督位数 nk = r = g g(x) 的次数的次数信息元数目信息元数目 k= 2rr1码的最小距离码的最小距离 dmin=3(t=1)汉明码的纠错能力汉明码的纠错能力以以 g g(x)=x3+x+1 为例。为例。r=3, n=7, k=4该码的监督矩阵为该码的监督矩阵为6.3.7 循环汉明码循环汉明码100101101011100010111H第六章 信道编码2022/3/1439H H 矩阵共有矩阵共有

38、n= 2r1 列，每列都是列，每列都是 r 维向量，但没有全维向量，但没有全0的的列，而且各列均不相同。列，而且各列均不相同。H H 矩阵中已包含了所有的矩阵中已包含了所有的 (2r1) 个非个非0列，它们任意两列列，它们任意两列之和不为之和不为0，而三列之和可以为，而三列之和可以为0。说明由。说明由 H H 矩阵所确定的矩阵所确定的循环汉明码的最小距离为循环汉明码的最小距离为3，可以纠正一个随机错误。，可以纠正一个随机错误。汉明码是完备码，因而是高效码。汉明码是完备码，因而是高效码。在构造汉明码时，只要选择不同的本原多项式（可查在构造汉明码时，只要选择不同的本原多项式（可查表）作为生成多项式

39、，就可以得到不同的表）作为生成多项式，就可以得到不同的 (n,k) 循环循环汉明码。例如汉明码。例如(7,4)、(15,11)、(31,26)等等。等等。循环汉明码的编码、译码与一般循环码相同。不过由循环汉明码的编码、译码与一般循环码相同。不过由于它是纠正一个错误的循环码，所以译码电路特别简于它是纠正一个错误的循环码，所以译码电路特别简单。单。6.3.7循环汉明码循环汉明码第六章 信道编码2022/3/1440(2) (7,4)循环汉明码的译码循环汉明码的译码(7,4)循环码是纠一个错误的循环汉明码；循环码是纠一个错误的循环汉明码；由于由于码矢和伴随式的循环移位特性码矢和伴随式的循环移位特性，

40、可将译码电路设，可将译码电路设计成纠正最高阶位上的一个错误；计成纠正最高阶位上的一个错误；当实际错误不在最高阶而在其它位上时，接收矢量和当实际错误不在最高阶而在其它位上时，接收矢量和伴随式（在伴随式（在 g g(x) 除法运算电路中）同时进行移位，一除法运算电路中）同时进行移位，一旦错误到达最高阶位上，就将产生确定的伴随式；旦错误到达最高阶位上，就将产生确定的伴随式；只需要一个简单的组合逻辑电路对这一确定的伴随式只需要一个简单的组合逻辑电路对这一确定的伴随式进行检测就可完成纠错。进行检测就可完成纠错。6.3.7 循环汉明码循环汉明码第六章 信道编码2022/3/1441由由 g g(x)=x3

41、+x+1 生成的生成的(7,4)循环汉明码的译码电路如循环汉明码的译码电路如图图6.3.22所示。所示。6.3.7 循环汉明码循环汉明码第六章 信道编码2022/3/1442(7,4) 循环汉明码的译码电路工作过程循环汉明码的译码电路工作过程 接收矢量送入伴随式计算电路，经接收矢量送入伴随式计算电路，经 7 次移位得到伴随式，同时次移位得到伴随式，同时接收矢量移入缓存器；接收矢量移入缓存器； 将前一步所计算的伴随式转入伴随式自发运算电路，当错误恰将前一步所计算的伴随式转入伴随式自发运算电路，当错误恰好在最高阶位上时，伴随式为好在最高阶位上时，伴随式为 (101)，与门检测此状态并输出，与门检测

42、此状态并输出“1”，而当最高阶位移出缓存器时即被纠正；若错误不在最高，而当最高阶位移出缓存器时即被纠正；若错误不在最高阶位上而在其它位上，比如在阶位上而在其它位上，比如在 x4 位上时，错误图样经过两次移位上时，错误图样经过两次移位变成位变成 x2 x4=x6，经两次移位后的伴随式为，经两次移位后的伴随式为 S S2=x2+1(mod g g(x)，检测到此状态时与门输出检测到此状态时与门输出“1”，而对应的接收符号也正好移到，而对应的接收符号也正好移到最高阶位上，因而错误得到纠正；最高阶位上，因而错误得到纠正；x6/(x3+x+1)=x2+1 当接收矢量全部移出缓存器后，完成一个码组的译码。

43、在接收当接收矢量全部移出缓存器后，完成一个码组的译码。在接收矢量开始移出缓存器时，下一个接收矢量紧跟着移入伴随式计矢量开始移出缓存器时，下一个接收矢量紧跟着移入伴随式计算电路和缓存器，重复第算电路和缓存器，重复第步的的过程，可实现连续对接收矢步的的过程，可实现连续对接收矢量进行纠错。量进行纠错。6.3.7 循环汉明码循环汉明码第六章 信道编码2022/3/1443(3) (15,11) 循环汉明码译码电路设计循环汉明码译码电路设计设计由设计由 g g(x)=x4+x+1 生成的生成的 (15,11) 循环汉明码的译码循环汉明码的译码电路；电路；(15,11)循环汉明码是纠一个错误的循环汉明码，

44、所以循环汉明码是纠一个错误的循环汉明码，所以把译码器设计成纠正最高阶位把译码器设计成纠正最高阶位 x14 上的一个错误；上的一个错误；错误图样错误图样 x14 的伴随式为的伴随式为 S S(x)x14x3+1 (mod g g(x)，因而伴随式输出状态为因而伴随式输出状态为 (1001) 时，应使错误图样检测时，应使错误图样检测器输出器输出“1”。(15,11) 循环汉明码的译码电路如图循环汉明码的译码电路如图6.3.23所示。所示。6.3.7 循环汉明码循环汉明码第六章 信道编码2022/3/1444电路说明电路说明：工作原理与工作原理与 (7,4) 循环汉明码译码电路的工作原理相同。循环汉

45、明码译码电路的工作原理相同。但未加自发运算电路，在每接收完一个接收矢量后，伴随式还但未加自发运算电路，在每接收完一个接收矢量后，伴随式还需要在伴随式计算电路循环一周，以纠正所有码元位上可能的需要在伴随式计算电路循环一周，以纠正所有码元位上可能的错误。所以这种电路所需译码时间较长，不能进行连续译码。错误。所以这种电路所需译码时间较长，不能进行连续译码。采用哪种形式的电路要由信号的要求来决定。采用哪种形式的电路要由信号的要求来决定。6.3.7 循环汉明码循环汉明码第六章 信道编码2022/3/1445(1) 为什么要用缩短循环码为什么要用缩短循环码(2) 缩短循环码的构造缩短循环码的构造(3) 缩

46、短循环码的性能缩短循环码的性能(4) 举例举例6.3.8 缩短循环码缩短循环码第六章 信道编码2022/3/1446(1) 为什么要用缩短循环码为什么要用缩短循环码 在系统设计中，如果不能找到一种合适自然长度在系统设计中，如果不能找到一种合适自然长度或合适信息位数目的码，则需要将码组缩短，以满足或合适信息位数目的码，则需要将码组缩短，以满足系统的要求。系统的要求。(2) 缩短循环码的构造缩短循环码的构造 将码组缩短的基本方法是：设法使满足前面若干将码组缩短的基本方法是：设法使满足前面若干个码元符号为个码元符号为0，且不发送这些符号。对，且不发送这些符号。对 (n,k) 系统循系统循环码，只要令

47、前环码，只要令前 l 个信息数字为个信息数字为0 (lk)，就可将，就可将 (n,k) 循环码缩短为循环码缩短为 (nl,kl) 线性码。称这种码组长度缩线性码。称这种码组长度缩短了的循环码为缩短循环码。短了的循环码为缩短循环码。6.3.8 缩短循环码缩短循环码第六章 信道编码2022/3/1447(3) 缩短循环码的性能缩短循环码的性能一般情况下，删去前一般情况下，删去前 l 个个0之后的缩短码，就失去了循环特性。之后的缩短码，就失去了循环特性。在纠错能力上缩短码至少与原码相同。在纠错能力上缩短码至少与原码相同。由于删去前面由于删去前面 l 个个0信息元并不影响监督位和伴随式的计算，可信息元

48、并不影响监督位和伴随式的计算，可用原循环码的编译码电路来完成缩短码的编译码。用原循环码的编译码电路来完成缩短码的编译码。若用原循环码译码电路来译缩短循环码，则应修改错误图样检测若用原循环码译码电路来译缩短循环码，则应修改错误图样检测电路，使原来对包含最高阶位电路，使原来对包含最高阶位 xn1上的一个错误图样进行检测，上的一个错误图样进行检测，修改为对包含修改为对包含 xnl1位上的一个错误图样进行检测。位上的一个错误图样进行检测。错误图样检测电路的输出是和包含错误图样检测电路的输出是和包含 xnl1位上的错误相对应的，位上的错误相对应的，即当即当 xnl1位上的接收符号是错误的时，检测电路输出为位上的接收符号是错误的时，检测电路输出为“1”，否则为否则为“0”。当当 xnl1位上错误被纠正时，还应消除位上错误被纠正时，还应消除 enl1 对伴随式的影响。对伴随式的影响。在检测到在检测到xnl1位上有错时，将位上有错时，将 g g(x) 除除 xnl1 的余式加入此时的的余式加入此时的伴随式即可消