循环码的编码电路6.6循环码的译码6.7循环汉明码.ppt

《循环码的编码电路6.6循环码的译码6.7循环汉明码.ppt》由会员分享，可在线阅读，更多相关《循环码的编码电路6.6循环码的译码6.7循环汉明码.ppt（49页珍藏版）》请在三一办公上搜索。

1、2023/8/14,1,6.1 循环码的多项式描述6.2 循环码的生成多项式6.3 系统循环码6.4 多项式运算电路6.5 循环码的编码电路6.6 循环码的译码6.7 循环汉明码6.8 缩短循环码6.9 循环码的其它译码方法,第六讲 循环码,2023/8/14,2,6.5.1 非系统码编码电路6.2 系统码编码电路(1)循环码编码的基本原理(2)用(nk)级移位寄存器实现的编码电路(3)用 k 级移位寄存器实现的编码电路,6.5 循环码的编码电路,2023/8/14,3,6.5 循环码的编码电路,2023/8/14,4,循环码码式是生成多项式倍式。非系统编码电路/循环码乘法编码电路输入 a(x

2、)=m(x)，m(x)的次数 k输出 a(x)g(x)=C(x)即是码式，C(x)的次数 n举例：生成(7,4)汉明码的生成多项式为 g(x)=x3+x2+1，非系统编码电路如图6.13所示。电路共工作7个时钟节拍。,6.5.1 非系统码编码电路,2023/8/14,5,由表6.2可见，当 m(x)=x3+x时，非系统码字 C(x)为 C(x)=x6+x5+x4+x=(x3+x)(x3+x2+1),6.5.1 非系统码编码电路,2023/8/14,6,(1)系统码编码的基本原理求生成多项式g(x)：分解多项式(xn+1)，取(nk)次 因式作生成多项式 g(x)，一般可通过查表完成。利用 g(

3、x)实现编码设信息多项式为 m(x)=mk1xk1+mk2 xk2+m0设校验多项式为 r(x)=rr1xr1+rr2 xr2+r0(n,k)循环码的码多项式为C(x)=Cn1xn1+Cn2xn2+Cnkxnk+Cnk1xnk1+C1x+C0 前 k 项系数为信息位，后 r=nk 项为校验位。所以 Cn1xn1+Cnkxnk=xnk(mk1xk1+m0)=xnkm(x)Cnk1xnk1+C0=rr1xr1+r0=r(x),6.5.2 系统码编码电路,2023/8/14,7,(2)用(nk)级移位寄存器实现的编码电路循环码编码电路结构和工作原理工作原理：二元(n,k)循环码的编码是将信息多项式

4、m(x)乘 xnk 后再除以生成多项式 g(x)求出它的余式，即为监督数字多项式 r(x)。二元(n,k)循环码的编码电路就是以 g(x)为除式的除法电路，而输入的被除式为 xnkm(x)。实际的编码电路如图6.15所示。其级数等于 g(x)的次数(nk)；反馈连接决定于 g(x)的系数当 gi=0 时(i=0,1,2,nk)，反馈断开；当 gi=1 时，对应级加入反馈。,6.5.2 系统码编码电路,2023/8/14,8,由于被除式中含有因子 xnk，使被除式各项的次数都 g(x)的次数，所以被除式输入端可由第一级移到末级之后，使移位次数减少(nk)次。这样编一个码字求监督数字所需的移位次数

5、只要 k 次。,6.5.2 系统码编码电路,2023/8/14,9,工作过程：各级移位寄存器清“0”，控制门开；k 位信息数字 mk1,mk2,m1,m0 依次从末端输入编码电路；同时送入信道，在每加入一位信息数字时，各级移位寄存器移位一次。当 k 位信息数字都输入移位寄存器后，移位寄存器中(nk)位数字即为监督数字；控制门关，断开反馈，开关 K 由位置1转到位置2，寄存器中的存数（监督数字）依次移出，送入信道。k 位信息数字和(nk)位监督数字组成一个码字。,6.5.2 系统码编码电路,2023/8/14,10,举例：由 g(x)=(x3+x+1)作生成多项式所生成的(7,4)循环码的编码电

6、路如图6.16所示。它包括 3 级寄存器g1=1，第一级反馈接通；g2=0，到第二级的反馈断开。,6.5.2 系统码编码电路,每经四次移位，输入一个四位信息组；寄存器中的内容即为监督数字；监督数字跟在信息数字之后，便构成一个码字。,2023/8/14,11,(3)用 k 级移位寄存器实现的编码电路循环码的监督方程在(nk)循环码中，若 k(1/2)n，即信息位比监督位少时，可采用 k 级移位寄存器的编码电路。根据线性码的监督方程,6.5.2 系统码编码电路,2023/8/14,12,得 由此得到(nk)个监督方程，进而得到(nk)个监督数字的表示式,6.5.2 系统码编码电路,2023/8/1

7、4,13,监督数字表示式特点每个监督码元都是由它前面的 k 个码元按同一规律确定的；第一个监督元 Cnk1 是 k 个信息元与 h(x)的系数决定的；第二个监督元是前面(k1)个信息元和第一个监督元与 h(x)的系数决定的；，如此类推；最后一个监督元 C0 都按同一规律决定。,6.5.2 系统码编码电路,2023/8/14,14,电路如图6.17所示,6.5.2 系统码编码电路,2023/8/14,15,工作过程：门1开，门2关，k 位信息串行送入 k 级移位寄存器，并同时送入信道；门1关，门2开，每移位一次输出一位监督数字，并同时送入信道，经(nk)次移位，就在 k 位信息数字之后附加上(n

8、k)位监督数字，构成了一个码字。举例：利用监督多项式构造(7,3)循环码的编码电路。x7+1=(x+1)(x3+x+1)(x3+x2+1)任取一个三次因式为监督多项式 h(x)=x3+x+1得 h3=1,h2=0,h1=1,h0=1,6.5.2 系统码编码电路,2023/8/14,16,由三级移位寄存器构成的(7,3)循环码的编码电路如图6.18所示。,6.5.2 系统码编码电路,2023/8/14,17,线性码的译码是根据接收字多项式的伴随式和可纠的错误图样间的一一对应关系，由伴随式得到错误图样；循环码是线性码的一个特殊子类，循环码的译码与线性码的译码步骤基本一致。不过由于循环码的循环特性，

9、使它的译码更加简单易行；循环码的译码过程仍包括三个步骤：接收多项式的伴随式计算；求伴随式对应的错误图样；用错误图样纠错。6.6.1 接收矢量伴随式计算6.6.2 循环码的通用译码法,6.6 循环码的译码,2023/8/14,18,(1)根据伴随式定义 ST=HRT 计算伴随式S(2)用 k 级移位寄存器的伴随式计算电路(3)用 nk 级移位寄存器的伴随式计算电路(4)接收字循环移位的伴随式与伴随式循环移位的关系,6.6.1 接收矢量伴随式计算,2023/8/14,19,(1)根据伴随式定义 ST=HRT 计算伴随式S设设,6.6.1 接收矢量伴随式计算,2023/8/14,20,这是前面介绍过

10、的由接收矢量相应分量直接求和计算伴随式的方法，对所有线性码都适用。电路是(nk)个多输入的奇偶校验器，每个奇偶校验器的输入端由 H 阵的相应行 hi 中的1决定（参看图6.7）,6.6.1 接收矢量伴随式计算,2023/8/14,21,6.6.1 接收矢量伴随式计算,2023/8/14,22,(2)用 k 级移位寄存器的伴随式计算电路定理6.6：二元线性系统码中，接收矢量 R 的伴随式 S 等于对 R 的信息部分所计算的监督数字（相当于对 R 的信息部分重新编码）与接收的监督数字的矢量和。证明：设接收矢量 R=(RI RP)RI 是 R 的信息部分，长度为 k 的矢量RP 是 R 的监督数字部

11、分，长为 r=(nk)的矢量监督矩阵为 H=(Prk Ir)由伴随式的定义,6.6.1 接收矢量伴随式计算,2023/8/14,23,6.6.1 接收矢量伴随式计算,2023/8/14,24,电路的工作步骤门1通，门2、3、4关，接收字R的 k 位信息部分输入编码器；门1关，门2、3、4通，接收信息编码所得的监督数字与接收监督数字逐位模2和，得到伴随式。但这种伴随式计算方法只适用于线性系统码。,6.6.1 接收矢量伴随式计算,2023/8/14,25,(3)用(nk)级移位寄存器的伴随式计算电路设接收多项式为 R(x)，它的信息部分表示为 RI(x)，监督部分表示为 RP(x)；由定理6.6知

12、 S(x)=r(x)+RP(x)，其中 r(x)是对RI(x)重新编码的监督数字多项式；若码的生成多项式为 g(x)，则 r(x)RI(x)(mod g(x)r(x)xnkm(x)(mod g(x)又因为上式表明：循环码接收多项式的伴随式是接收多项式 R(x)除以 g(x)的余式。,6.6.1 接收矢量伴随式计算,2023/8/14,26,设 E(x)为 R(x)的错误图样，那么 R(x)=C(x)+E(x)，由于 C(x)为 g(x)的倍式，所以S(x)C(x)+E(x)E(x)(mod g(x)上式表明：伴随式是由错误图样决定的，与具体码字无关。说明：循环码伴随式的表示式(6.4)是由系统

13、码推出的，但由于伴随式仅与错误图样有关，因而对非系统码也是适用的。,6.6.1 接收矢量伴随式计算,2023/8/14,27,由式(6.4)可画出用(nk)级移位寄存器计算循环码伴随式的电路，如图6.20所示。这是一个(nk)级除法求余电路，它与编码除法电路的区别是：由于被除式 R(x)不含 x 的幂的因子，所以接收矢量（被除式）应由第一级前加入。,6.3.6.1 接收矢量伴随式计算,2023/8/14,28,(4)接收字循环移位的伴随式与伴随式循环移位的关系定理6.7：设 S(x)为接收矢量 R(x)的伴随式，则 R(x)的循环移位 xR(x)(mod(xn+1)的伴随式 S(1)(x)等于

14、伴随式 S(x)的循环移位 xS(x)(mod g(x)，即S(1)(x)xS(x)(mod g(x)证明：由伴随式计算式(6.3.4)知S(x)R(x)(mod g(x)对上式两边作同余运算得 xS(x)xR(x)(mod g(x)(6.5)令 R(1)(x)xR(x)(mod(xn+1)(6.6)即用 R(1)(x)表示 R(x)循环移位一次(mod(xn+1)的码多项式。,6.6.1 接收矢量伴随式计算,2023/8/14,29,对式(6.6)进行模 g(x)运算，得到 R(x)循环移位 xR(x)的伴随式 S(1)(x)xR(x)(mod g(x)考虑到式(6.3.5)，则有 S(1)

15、(x)xS(x)(mod g(x)上式说明：接收矢量的循环移位（mod(xn+1)运算下）与伴随式在模 g(x)运算下（即在除以 g(x)的伴随式计算电路中）的循环移位是一一对应的。,6.6.1 接收矢量伴随式计算,2023/8/14,30,(1)循环码的译码器的组成（梅吉特译码法）循环码的译码基本上按线性分组码的译码步骤进行,不过由于码的循环移位特性使译码电路大为简化。通用的循环码译码器如图6.21所示。,6.6.2 循环码的通用译码法,2023/8/14,31,循环码通用译码器三个组成部分 伴随式计算电路：可根据实际情况选取不同的伴随式电路。错误图样检测器：是一个组合逻辑电路，其作用是将伴

16、随式译为错误图样。它的工作原理为：当且仅当错误图样是一个可纠的错误图样，并且此错误图样包含最高阶位上的一个错误时，伴随式计算电路计算得到的伴随式才使检测电路输出为“1”。即如果错误图样检测器输出为“1”，则认为最高阶位上接收符号是错误的，应该给以纠正；即如果检测器输出为“0”，则认为最高阶位上接收符号是正确的，不必纠正。,6.6.2 循环码的通用译码法,2023/8/14,32,对于码组中任何位置上的错误，通过码组和伴随式同时循环移位，当错误符号移到移到最高阶位上时，伴随式则使检测器输出为“1”，将其错误纠正。通过循环移位后，能使可纠错误图样中的全部错误都得到纠正。接收矢量缓存器和模2和纠错电

17、路。,6.6.2 循环码的通用译码法,2023/8/14,33,(2)循环码译码电路工作过程将接收矢量移入伴随式计算电路，计算出伴随式；同时将接收矢量移入缓存器。伴随式写入错误图样检测器，并在检测器中循环移位(mod g(x)，同时将接收矢量移出缓存器。当检测器输出“1”时，表示缓存器此时输出符号是错误的，并将错误纠正；同时检测器输出反馈到伴随式计算电路的输入端，去修改伴随式，从而消除错误对伴随式所产生的影响。直到接收矢量全部移出缓存器，该接收矢量纠错完毕。若最后伴随式寄存器中为全“0”，则表示错误全部被纠正，否则检出了不可纠的错误图样。说明：随着码长 n 和纠错能力 t 的增加，错误图样检测

18、器的组合逻辑电路变得很复杂，甚至难以实现。,6.6.2 循环码的通用译码法,2023/8/14,34,(1)循环汉明码的性能(2)(7,4)循环汉明码的译码(3)(15,11)循环汉明码的译码,6.7 循环汉明码,2023/8/14,35,(1)循环汉明码的性能既约多项式：设 f(x)是次数大于零的多项式，若除了常数和常数与本身的乘积以外，再不能被域 Fp 上的其它多项式除尽，则称 f(x)为域 Fp 上的既约多项式。本原多项式：GF(2)上的 m 次既约多项式有两大类。一类是能够被(xn+1)整除，但不能被(xs+1)整除（n=2m1,sn），它的根是 GF(2m)扩域中的本原元素，这一类称

19、为本原多项式。另一类多项式，它不仅能被(xn+1)整除，也能整除(xs+1)，它的根不是扩域 GF(2m)中的本原元素，称这类既约多项式为非原多项式。循环汉明码：以 r(n=2r1)次本原多项式为生成多项式的循环码，称为循环汉明码。,6.7 循环汉明码,2023/8/14,36,循环汉明码的参数码长 n=2r1监督位数 nk=r=g(x)的次数信息元数目 k=2rr1码的最小距离 dmin=3(t=1)汉明码的纠错能力以 g(x)=x3+x+1 为例。r=3,n=7,k=4该码的监督矩阵为,6.7 循环汉明码,2023/8/14,37,H 矩阵共有 n=2r1 列，每列都是 r 维向量，但没有

20、全0的列，而且各列均不相同。H 矩阵中已包含了所有的(2r1)个非0列，它们任意两列之和不为0，而三列之和可以为0。说明由 H 矩阵所确定的循环汉明码的最小距离为3，可以纠正一个随机错误。汉明码是完备码，因而是高效码。在构造汉明码时，只要选择不同的本原多项式（可查表）作为生成多项式，就可以得到不同的(n,k)循环汉明码。例如(7,4)、(15,11)、(31,26)等等。循环汉明码的编码、译码与一般循环码相同。不过由于它是纠正一个错误的循环码，所以译码电路特别简单。,6.7循环汉明码,2023/8/14,38,(2)(7,4)循环汉明码的译码(7,4)循环码是纠一个错误的循环汉明码；由于码矢和

21、伴随式的循环移位特性，可将译码电路设计成纠正最高阶位上的一个错误；当实际错误不在最高阶而在其它位上时，接收矢量和伴随式（在 g(x)除法运算电路中）同时进行移位，一旦错误到达最高阶位上，就将产生确定的伴随式；只需要一个简单的组合逻辑电路对这一确定的伴随式进行检测就可完成纠错。,6.7 循环汉明码,2023/8/14,39,由 g(x)=x3+x+1 生成的(7,4)循环汉明码的译码电路如图6.22所示。,6.7 循环汉明码,2023/8/14,40,(7,4)循环汉明码的译码电路工作过程 接收矢量送入伴随式计算电路，经7次移位得到伴随式，同时接收矢量移入缓存器；将前一步所计算的伴随式转入伴随式

22、自发运算电路，当错误恰好在最高阶位上时，伴随式为(101)，与门检测此状态并输出“1”，而当最高阶位移出缓存器时即被纠正；若错误不在最高阶位上而在其它位上，比如在 x4 位上时，错误图样经过两次移位变成 x2x4=x6，经两次移位后的伴随式为 S2=x2+1(mod g(x)，检测到此状态时与门输出“1”，而对应的接收符号也正好移到最高阶位上，因而错误得到纠正；x6/(x3+x+1)=x2+1 当接收矢量全部移出缓存器后，完成一个码组的译码。在接收矢量开始移出缓存器时，下一个接收矢量紧跟着移入伴随式计算电路和缓存器，重复第步的的过程，可实现连续对接收矢量进行纠错。,6.7 循环汉明码,2023

23、/8/14,41,(3)(15,11)循环汉明码译码电路设计设计由 g(x)=x4+x+1 生成的(15,11)循环汉明码的译码电路；(15,11)循环汉明码是纠一个错误的循环汉明码，所以把译码器设计成纠正最高阶位 x14 上的一个错误；错误图样 x14 的伴随式为 S(x)x14x3+1(mod g(x)，因而伴随式输出状态为(1001)时，应使错误图样检测器输出“1”。(15,11)循环汉明码的译码电路如图6.23所示。,6.7 循环汉明码,2023/8/14,42,电路说明：工作原理与(7,4)循环汉明码译码电路的工作原理相同。但未加自发运算电路，在每接收完一个接收矢量后，伴随式还需要在

24、伴随式计算电路循环一周，以纠正所有码元位上可能的错误。所以这种电路所需译码时间较长，不能进行连续译码。采用哪种形式的电路要由信号的要求来决定。,6.7 循环汉明码,2023/8/14,43,(1)为什么要用缩短循环码(2)缩短循环码的构造(3)缩短循环码的性能(4)举例,6.8 缩短循环码,2023/8/14,44,(1)为什么要用缩短循环码 在系统设计中，如果不能找到一种合适自然长度或合适信息位数目的码，则需要将码组缩短，以满足系统的要求。(2)缩短循环码的构造 将码组缩短的基本方法是：设法使满足前面若干个码元符号为0，且不发送这些符号。对(n,k)系统循环码，只要令前 l 个信息数字为0(

25、lk)，就可将(n,k)循环码缩短为(nl,kl)线性码。称这种码组长度缩短了的循环码为缩短循环码。,6.8 缩短循环码,2023/8/14,45,(3)缩短循环码的性能一般情况下，删去前 l 个0之后的缩短码，就失去了循环特性。在纠错能力上缩短码至少与原码相同。由于删去前面 l 个0信息元并不影响监督位和伴随式的计算，可用原循环码的编译码电路来完成缩短码的编译码。若用原循环码译码电路来译缩短循环码，则应修改错误图样检测电路，使原来对包含最高阶位 xn1上的一个错误图样进行检测，修改为对包含 xnl1位上的一个错误图样进行检测。错误图样检测电路的输出是和包含 xnl1位上的错误相对应的，即当

26、xnl1位上的接收符号是错误的时，检测电路输出为“1”，否则为“0”。当 xnl1位上错误被纠正时，还应消除 enl1 对伴随式的影响。在检测到xnl1位上有错时，将 g(x)除 xnl1 的余式加入此时的伴随式即可消除。,6.8 缩短循环码,2023/8/14,46,(4)举例：设计(15,11)循环码的缩短码(8,4)码的译码器。解：(15,11)循环汉明码是纠一个错误的码，它的(8,4)缩短码译码电路如图6.24。,6.8 缩短循环码,2023/8/14,47,图中包含三个部分：八位缓冲移位寄存器；由本原多项式 g(x)=x4+x+1 决定的伴随式计算电路。对当x7位上发生错误时的错误图

27、样检测电路。错误图样x7的伴随式为 S(x)x7x3+x+1(mod g(x)，当伴随式输出状态为(1011)时，检测电路应输出“1”。随着码长 n 和纠错能力 t 的增加，错误图样检测器的组合逻辑电路变得很复杂，甚至难以实现。但纠单个错误的循环汉明码，译码器中的组合逻辑电路却很简单，因而汉明码在实际中得到了广泛的应用。,6.8 缩短循环码,2023/8/14,48,循环码的捕错译码一般适用于短码或低码率的译码；用于纠突发错误的码的译码是很有效的。循环码的大数逻辑译码从码的结构出发，可导出大数逻辑译码法；具有译码设备简单、速度快的优点，因而应用相当广泛。,6.9 循环码的其它译码方法,2023/8/14,49,补充：已知(7,3)循环码的全部码字 0000000 0011101 0111010 1101001 1010011 0100111 1001110(1)写出该循环码的生成多项式 g(x)和生成矩阵G；(2)写出一致监督矩阵 H；(3)画出译码电路。,课外思考题,