第六章-循环码的译码.ppt

第六章-循环码的译码.ppt

《第六章-循环码的译码.ppt》由会员分享，可在线阅读，更多相关《第六章-循环码的译码.ppt（102页珍藏版）》请在冰点文库上搜索。

第第6章章循环码的译码循环码的译码第第6章章循环码的译码循环码的译码6.16.1循环码译码的一般原理循环码译码的一般原理6.26.2捕错译码捕错译码6.36.3大数逻辑译码原理大数逻辑译码原理6.4大数逻辑可译码的构造6.5软判决译码的基本原理6.6码字错误概率最小的软判决译码习题习题第第6章章循环码的译码循环码的译码6.1循环码译码的一般原理循环码译码的一般原理设设发发送送的的码码字字是是C（x）=（cn-1xn-1+c1x+c0）（今今后后不不再再严严格格区区分分码码字字与与码码多多项项式式），通通过过q进进制制输输入入和和输输出出的的信道后，信道后，译码器输入端得到的是译码器输入端得到的是R（x）=C（x）+E（x）=（rn-1xn-1+r1x+r0）ri=ci+ei式式中中，E（x）=（en-1xn-1+e1x+e0）是是信信道道产产生生的的错错误误图图样样，应应当当指指出出，上上述述这这些些式式中中的的ci、ri、ei均均是是GF（q）中中的的元元素，素，也就也就是我们这里仅讨论硬判决时的译码方法。

是我们这里仅讨论硬判决时的译码方法。

第第6章章循环码的译码循环码的译码译译码码器器的的主主要要任任务务就就是是如如何何从从R（x）中中得得到到正正确确的的估估计计错错误误图图样样（x）=E（x），然然后后得得到到C（x），并并由由此此得得到到信息组信息组m（x）。

如如同同所所有有线线性性分分组组码码的的译译码码一一样样，循循环环码码的的译译码码也分为以下也分为以下3步：

步：

（1）计算计算R（x）的伴随式的伴随式S（x）；

（2）根据伴随式根据伴随式S（x）找出估计错误图样找出估计错误图样（x）；第第6章章循环码的译码循环码的译码（3）R（x）-（x）=，得得到到译译码码器器输输出出的的估估值值码码字字，并并送送出出译译码码器器给给用用户户。

若若=C，则则译译码码正正确，确，否则译码错误。

否则译码错误。

如如果果是是非非系系统统码码，则则还还必必须须由由中中得得到到估估值值信信息组息组；如果是系统码，如果是系统码，这一步可省略。

这一步可省略。

由由于于循循环环码码的的循循环环特特性性，在在上上述述各各步步运运算算中中，往往往比非循环码的计算要简单。

往比非循环码的计算要简单。

第第6章章循环码的译码循环码的译码一、一、伴随式计算和错误的检测伴随式计算和错误的检测设设发发送送的的码码字字C=（cn-1，cn-2，c1，c0），信信道道产产生生的的错错误误图图样样为为E=（en-1，en-2，e1，e0），译码器收到的译码器收到的n重重R=C+E=（cn-1+en-1，cn-2+en-2，c1+e1，c0+e0）=（rn-1，rn-2，r1，r0）ri=ci+ei第第6章章循环码的译码循环码的译码由伴随式定义可知，由伴随式定义可知，相应的伴随式是相应的伴随式是S=RHT=（C+E）HT=EHT可可知知伴伴随随式式S仅仅与与错错误误图图样样有有关关，而而与与发发送送的的码码字字无关，无关，由它可计算出错误图样由它可计算出错误图样E。

第第6章章循环码的译码循环码的译码设设n，k循环码的生成多项式为循环码的生成多项式为g（x），且且xn-1=g（x）h（x），g（x）=n-k。

该码的一致校验矩阵该码的一致校验矩阵由式由式（5.1.9）可知为可知为第第6章章循环码的译码循环码的译码所以第第6章章循环码的译码循环码的译码由此式可知相应的多项式表示为由此式可知相应的多项式表示为S（x）C（x）+E（x）R（x）E（x）（modg（x）（6.1.1）或或S（x）=Rg（x）+g（x）q（x）=Eg（x）+g（x）q1（x）（6.1.2）式式中中，Rg（x）和和Eg（x）分分别别是是R（x）和和E（x）被被g（x）除除后后所所得的余式。

得的余式。

第第6章章循环码的译码循环码的译码二、二、伴随式计算电路性质及一般译码器伴随式计算电路性质及一般译码器用用g（x）除除法法电电路路计计算算伴伴随随式式的的电电路路（伴伴随随式式计计算算电电路路）有如下一个很重要的特点。

有如下一个很重要的特点。

定定理理6.1.1若若S（x）是是R（x）的的伴伴随随式式，则则R（x）的的循循环环移移位位xR（x）（在在模模xn-1运运算算下下）的的伴伴随随式式S1（x），是是S（x）在在伴伴随随式式计计算算电电路路中中无无输输入入时时（自自发发运运算算）右右移移一一位位的的结结果果，即即S1（x）xS（x）（modg（x）（6.1.3）第第6章章循环码的译码循环码的译码证明由伴随式定义可知xR（x）之伴随式为S1（x）xR（x）（modg（x）=xRg（x）+q1（x）g（x）（6.1.4）由式（6.1.2）可知：

xS（x）=xRg（x）+xq（x）g（x）该式减去式（6.1.4）可得：

xS（x）-S1（x）=g（x）（xq（x）-q1（x）0（modg（x）因此S1（x）xS（x）（modg（x）第第6章章循环码的译码循环码的译码推论6.1.1xjR（x）的伴随式Sj（x）xjS（x）（modg（x），j=0，1，n-1。

而任意多项式a（x）乘R（x）所对应的伴随式Sa（x）a（x）S（x）（modg（x）（6.1.5）第第6章章循环码的译码循环码的译码在q进制时，若码要纠正t个错误，则错误图样代表共有（6.1.6）个。

译码时，只要知道此代表图样的伴随式，该类其它错误图样的伴随式都可由此代表图样伴随式在伴随式计算电路中得到。

这样，就使得循环码译码器的错误图样识别电路大为简化，由原来识别（6.1.7）个图样减少到N1个。

第第6章章循环码的译码循环码的译码例如二进制码，n=63，t=4，由式（6.1.6）和式（6.1.7）计算译码器所需识别的错误图样个数如表6-1所示。

表6-1N1，N2比较表第第6章章循环码的译码循环码的译码例6.1二进制7，4，3循环汉明码，它的g（x）=x3+x+1，相应的校验矩阵第第6章章循环码的译码循环码的译码由式（6.1.6）知，构造此译码器的错误图样识别电路时，只要识别一个图样E6=（1000000）就够了，该图样的伴随式就是H的第一列（101）。

可知，识别E6错误图样的识别电路就是一个检测伴随式是否是（101）的电路。

由此可得如图6-1所示的译码电路。

图中的伴随式计算电路就是一个g（x）=x3+x+1的除法电路，而有3个输入端的与门和反相器，组成了识别（101）的伴随式识别器。

第第6章章循环码的译码循环码的译码图6-17，4，3循环汉明码译码器第第6章章循环码的译码循环码的译码译码器的译码过程如下：

（1）开始译码时门开，移存器内容全为0。

收到的R（x）=r6x6+r0，以高次项系数（r6）至低次项系数的次序，一方面送入7级缓冲器，一方面送入g（x）除法电路计算伴随式。

7次移位后，R（x）的系数全部存入缓存器，g（x）电路也得到了伴随式S0（x），此时门关，禁止输入。

第第6章章循环码的译码循环码的译码

（2）若S0（x）1+x2x6（modg（x），说明E（x）=x6，r6位有错，伴随式计算（g（x）除法器）电路中的D0、D1、D2存贮的值是（101），它就是S0（x）=1+x2之系数。

D1的0经反相后成了1，与门3个输入端全为1，呈打开状态。

这时译码器继续移位，r6从缓存器输出，与门也输出一个信号“1”与r6相加，使r6由原来的1变成0，或由0变成1，纠正了r6的错误：

r6+1=c6+e6+1=c6+1+1=c6，得到了原来发送的码元。

此时与门的纠错信号“1”也反馈到伴随式计算电路输入端（图中虚线所示），对伴随式进行修正，以消去该错误对伴随式的影响。

第第6章章循环码的译码循环码的译码这由于R（x）=rn-1xn-1+r1x+r0相应的伴随式是S0（x）。

纠错后R（x）成为R1（x）=（rn-1+1）xn-1+r1x+r0与R1（x）相应的伴随式S1（x）S0（x）+xn-1（modg（x）因为纠错是在第n+1次移位进行的，所以R1（x）成为R1（x）=xR1（x）rn-2xn-1+r0x+rn-1+1（modxn-1）第第6章章循环码的译码循环码的译码相应的伴随式S1（x）xS1（x）xS0（x）+xnxS0（x）+1（modg（x）由于S1（x）是xR1（x）的伴随式，而xS0（x）是xR（x）的伴随式，也就是xE（x）的伴随式，因此为了得到真正的xR（x）的伴随式，就必须从S1（x）中消去“1”，也就是在伴随式计算电路输入端加1。

第第6章章循环码的译码循环码的译码（3）若E（x）=x5，则S0（x）x5x2+x+1（modg（x），此时与门不打开，说明r6正确。

这时伴随式计算电路和缓存器各移位一次，r6输出，r5移到缓存器最右一级，伴随式计算电路得到的伴随式是S1（x）xS0（x）xE（x）x2+1（modg（x）第第6章章循环码的译码循环码的译码因此再移动一次，与门输出的纠正信号“1”正好与缓存器输出的r5=c5+1相加，得到了c5，从而完成了纠错。

若r5不错，则重复上述过程一直到译完一个码字为止。

该译码过程可用表6-2表示，已知R（x）=x6+x+1，E（x）=x4。

由该表知，到第10个节拍，与门输出一个“1”纠正r4，最后译码器输出码字（1010011）。

第第6章章循环码的译码循环码的译码表6-2图6-1译码器译码过程第第6章章循环码的译码循环码的译码从上述译码过程可知，译一组码共需14（2n=14）个节拍，仅当第一组的R（x）移出7级缓存器后，才能接收第二组的R（x）。

为了使译码连续，必须再加一个伴随式计算电路，如图6-2。

第第6章章循环码的译码循环码的译码图6-27，4码完整译码器第第6章章循环码的译码循环码的译码开始工作时，所有移存器的存数全为0，门1开、门2关。

当k=4次移位后，4级缓存器接收了前面的4个信息位（对系统码而言），此时门1关，并使4级缓冲器停止移位。

再移动n-k=3次后，g（x）除法电路得到了伴随式S0（x），此时门2开，把上边g（x）除法电路中的伴随式送到下面的伴随式计算电路中，随即门2关闭，且上边g（x）除法电路立即清洗为0。

门1再次打开，4级缓存器一边送出第一组的信息，一边接收第二组R（x）的前k位信息组。

与此同时，上边伴随式计算电路计算第二组R（x）的伴随式，而下边伴随式计算电路，对第一组R（x）中的信息元进行纠错。

第第6章章循环码的译码循环码的译码三、扩展汉明码的译码2m，2m-1-m，4扩展汉明码是由2m-1，2m-1-m，3汉明码加一个全校验位得到。

它的码字（cn-1，c0，c）中前n个码元（cn-1，c0）是汉明码的一个码字，c是全校验位。

扩展汉明码的码长是8的整数倍，特别适用于计算机或微机组成的数据处理或数据传输系统中。

第第6章章循环码的译码循环码的译码扩展汉明码能纠正一个错误同时发现两个错误，虽然它不是循环码，但它译码电路的主要部分与循环汉明码的译码器相同，只要加上检错电路即可。

如8，4，4扩展码，只要在7，4，3循环汉明码译码器中，加一个检错电路即成，如图6-4。

图中，（a）部分的电路基本上与图6-1同，是循环汉明码的译码器，不同的是多加了一个全校验位检查电路，它由一个级移存器加一个模2加法器组成。

图中，（b）部分电路是一个检错电路。

该译码器的译码过程如下：

第第6章章循环码的译码循环码的译码图6-48，4，4扩展码译码器第第6章章循环码的译码循环码的译码

（1）开始时所有寄存器中的内容为0，门1和门2开。

移位4次后门2关，R（x）=r6x6+r0+r中的前4位（r6，r5，r4，r3）存入4级缓存器中，它就是待纠错的4个信息元。

移动7次后门1关，R（x）的前7个码元（r6，r5，r4，r3，r2，r1，r0），已全部送入7，4，3码所决定的伴随式计算电路中，得到了伴随式（s2，s1，s0）。

第8次移位后，在全校验位检查电路中得到了全校验的结果s，此时译码器不再输入。

第第6章章循环码的译码循环码的译码

（2）当s=0、（s0，s1，s2）=（000）时，译码器认为接收R（x）无误，把4级缓存器中的信息元输出。

（3）当s=1、（s0，s1，s2）（000）时，译码器认为有一个错误，此时纠错部分的译码电路，按上面讲的汉明码的方法进行纠错译码，4次移位后已全部输出已纠正过的信息元。

第第6章章循环码的译码循环码的译码（4）s=0、（s0，s1，s2）（000），译码器认为出现了偶数个错误，错误告警电路输出一信号给用户，表示检测到错误。

（5）s=1、（s0，s1，s2）全为0时，译码器认为出现了一个以上的奇数个错误，错误告警电路也输出一个信号给用户。

当然，为了使译码连续，在图6-4的（a）部分电路中，也必须有两个伴随式计算电路，这与图6-2相同。

第第6章章循环码的译码循环码的译码2m-1，2m-2-m，4增余删信汉明码的译码电路与扩展汉明码的译码电路基本相同，只不过全校验位的结果s也要输入到错误图样的识别电路与门中，对7，3，4码来说就是输入到图6-4（a）中有3个输入端的与门，如虚线所示，其它情况相同。

第第6章章循环码的译码循环码的译码四、缩短循环码的译码缩短i个信息位的n-i，k-i缩短循环码，是在n，k循环码中选前i个信息位为0的码字组成。

若n，k循环码的码字C（x）=cn-1xn-1+cn-2xn-2+c0则n-i，k-i缩短循环码的码字C（x）=cn-1-ixn-1-i+c0因此，缩短循环码的译码器必须在原n，k循环码译码器基础上作如下修正：

第第6章章循环码的译码循环码的译码

（1）k级缓存器改为k-i级；

（2）为了与

（1）的改动相适应，R（x）应自动乘以xi，然后再输入伴随式计算电路。

如7，4循环汉明码缩短一位变成6，3码，它的译码器就是把图6-2中的译码器作如下变动：

R（x）从图中（A）虚线所示的地方输入，这相当于R（x）自动乘以x，4级缓存器变成3级。

第第6章章循环码的译码循环码的译码6.2捕捕错错译译码码一、一、基本工作原理基本工作原理设码字设码字C（x）是某一纠是某一纠t个错误的个错误的n，k循环码的循环码的码字，码字，当它通过有扰信道到达接收端译码器时成为当它通过有扰信道到达接收端译码器时成为R（x）=C（x）+E（x）。

相应的伴随式相应的伴随式S（x）R（x）E（x）EI（x）+Ep（x）（modg（x）式中式中EI（x）=en-1xn-1+en-kxn-kEp（x）=en-k-1xn-k-1+e0第第6章章循环码的译码循环码的译码分别是在码字信息组分别是在码字信息组（或前或前k位位）和校验位和校验位（或后或后n-k位位）上的错误图样。

上的错误图样。

若若E（x）=n-k-1，即所有即所有t个错误集个错误集中在校验元的中在校验元的n-k位上，位上，则则EI（x）=0，E（x）=Ep（x）。

Ep（x）的最高次数是的最高次数是n-k-1，而而g（x）=n-k，所以当所以当E（x）=Ep（x）被被g（x）除后的余式仍为除后的余式仍为Ep（x），即即S（x）E（x）=Ep（x）（modg（x）第第6章章循环码的译码循环码的译码对于纠对于纠t个错误的循环码来说，个错误的循环码来说，必须使必须使t个错误能个错误能连续地出现在连续地出现在n-k位以内，位以内，这等价于要求有连续这等价于要求有连续k位码位码元无错，元无错，或错误图样中连续或错误图样中连续k位的值为位的值为0。

由于由于t个错误个错误均匀分布在均匀分布在n位上时最难满足连续位上时最难满足连续k位无错这一要求，位无错这一要求，因此可以用捕错方法译码的因此可以用捕错方法译码的n，k循环码，循环码，n、k、t之间必须满足下列条件：

之间必须满足下列条件：

knt或或tnk，或或R1t（6.2.1）第第6章章循环码的译码循环码的译码定定理理6.2.1纠纠正正t个个错错误误的的GF（q）上上的的n，k循循环环码码，捕捕错错译译码码过过程程中中已已把把t个个错错误误集集中中在在Ri（x）的的最最低次低次n-k位以内的充要条件是此时的伴随式重量位以内的充要条件是此时的伴随式重量（Si（x）t（6.2.2）证明若错误已集中在n-k位低次位码元段以内，则Si（x）xiE（x）=Ei（x）=Eip（x）（modg（x）Si（x）=Eip（x）第第6章章循环码的译码循环码的译码码只能纠正t个错误，若错误图样E（x）是一个可纠正的错误图样，则w（E（x）t，因而E（x）的循环移位i次的错误图样Ei（x）的重量也必小于等于t，所以w（Si（x）=w（Ei（x）t第第6章章循环码的译码循环码的译码反之，若w（Si（x）t，则错误一定集中在n-k位低次位码元段内。

设错误没有集中在该段以内，则Ei（x）（x）g（x），由此Ei（x）=q（x）g（x）+Si（x）Ei（x）-Si（x）=q（x）g（x）=Ci（x）Ci（x）是g（x）的倍式，由循环码性质知它必是n，k循环码的一个码字。

因而w（Ei（x）+（-Si（x）=w（C（x）d=2t+1由三角不等式（3.1.2）式可知w（Ei（x）+w（-Si（x）w（Ei（x）+（-Si（x）2t+1第第6章章循环码的译码循环码的译码因为w（Ei（x）t所以w（-Si（x）t+1t由于w（-Si（x）=w（Si（x），因此上式与假设w（Si（x）t相矛盾，因而错误没有集中在n-k低次位以内的反证法假设不能成立，故错误集中在n-k低次位内。

第第6章章循环码的译码循环码的译码例6.2二进制15，7，5循环码，生成多项式g（x）=x8+x7+x6+x4+1，能纠正两个错误。

t=2157满足捕错译码的必要条件式（6.2.1），可以用捕错译码方法译码，它的译码电路如图6-5。

其译码过程如下：

第第6章章循环码的译码循环码的译码图6-515，7，5循环码捕错译码电路第第6章章循环码的译码循环码的译码

（1）开始工作时，所有移存器和缓存器清洗为0，门2、门3开，门1、门4和门5关闭。

n=15次移位后，R（x）的15个码元全部移入（8+7）=15级缓存器，信息元在前7级，同时伴随式计算电路也完成了伴随式计算得到了S0（x）。

若S0（x）=0，说明无错，打开门5，输出缓存器中的7个信息元。

若S0（x）0，则进行以下各步。

第第6章章循环码的译码循环码的译码

（2）此时门2关，门1开，若w（S0（x）2，检测电路检测到伴随式的重量2，打开门4，关闭门3。

（3）若wS0（x）2，则15级缓存器和g（x）除法电路都循环移位一次，并检查wS1（x）的重量，若仍大于2，则继续循环移位。

n，k循环码的一般捕错译码器如图6-6和图6-7，它们分别称为第一类和第二类捕错译码器。

第第6章章循环码的译码循环码的译码图6-6n，k循环码的第一类捕错译码器第第6章章循环码的译码循环码的译码图6-7n，k循环码的第二类捕错译码器第第6章章循环码的译码循环码的译码第二类译码器与第一类的差别，仅在于第二类译码器是把接收到的R（x）自动乘以xn-k后，再进入g（x）除法电路计算伴随式，即R（x）从g（x）电路的最高次位送入。

所以R（x）xn-k（rn-1xn-1+rn-2xn-2+r0）xn-krn-1xn-k-1+rn-2xn-k-2+rk+rk-1xn-1+r1xn-k+1+r0xn-k（modxn-1）（6.2.3）第第6章章循环码的译码循环码的译码二、捕错译码的修正捕错译码是假定错误能集中在n-k段以内的前提下进行的，要求n，k循环码必须满足式（6.2.1）的必要条件。

但是，能满足此条件的纠随机错误的循环码很少，只有纠正一个错误的循环汉明码和15，7，5码等，而绝大部分循环码均不满足。

可是，有些循环码如15，5，7码，23，12，7Golay码及17，9，5QR码等，虽不满足式（6.2.1）的条件，但k仅比nt稍大或相等，也就是说在译码过程中不能把错误全部集中在n-k个码元段以内，而有个别错误可能在其它码元位上。

为了解决此问题，必须对捕错译码加以适当修正。

第第6章章循环码的译码循环码的译码译码过程中，若译码器能把大部分错误捕捉到n-k个码元段以内，同时使个别错误进入某几个预先指定的位上，则也能确定此时的错误图样。

当然，为了实现这种运算必须附加一些电路，以确定错误是否在某几个指定的位置。

第第6章章循环码的译码循环码的译码设n，k循环码能纠正t个错误，生成多项式是g（x）。

译码器收到R（x）后，计算伴随式S0（x）E（x）=EI（x）+Ep（x）SI（x）+Ep（x）（modg（x）SI（x）EI（x）=en-1xn-1+en-kxn-k（modg（x）Ep（x）So（x）-SI（x）（modg（x）（6.2.4）第第6章章循环码的译码循环码的译码式中，SI（x）是R（x）前k位（对系统码来说就是信息位）码段中错误图样EI（x）的伴随式。

由上式知，若EI（x）及其SI（x）是已知的，则可根据式（6.2.4）得到R（x）中后n-k位内（校验位）的错误图样Ep（x），从而确定出原来的错误图样E（x）=EI（x）+Ep（x）。

设Qj（x）是次数小于等于k-1次的二进制多项式集合，SIj（x）xn-kQj（x）（modg（x）Ij=0，1，第第6章章循环码的译码循环码的译码是xn-kQj（x）的伴随式，即如果在前k位上错误图样EI（x）=xn-kQj（x），则SIj（x）就是它的伴随式。

因此，如果任何一个重量t的错误图样E（x），或它的i次循环移位xiE（x）=Ei（x），在前k位码段内与Qj（x）中的任一个相一致，则把此时的SIj（x）与此时Ei（x）的伴随式Si（x）相减，由式（6.2.4）知：

（6.2.5）第第6章章循环码的译码循环码的译码例6.323，12，7Golay码，它的生成多项式g（x）=x11+x10+x6+x5+x4+x2+1。

该码若用循环码的其它方法译码比较复杂，但用修正捕错译码则比较简单。

该码的n、k与t之间关系不满足式（6.2.1），不能用捕错译码，必须用修正方法。

首先选择在前k位中的覆盖多项式集合Qj（x），经分析可知应选0，x5，x62。

其中，x5，x6是特定在信息位置上的错误（对系统码而言），而0表示错误能全部集中在后n-k位内，不需要在前k位上指定错误的情况。

第第6章章循环码的译码循环码的译码由0，x5，x6可得：

xn-kQ1（x）=x110=0xn-kQ2（x）=x11x5=x16xn-kQ3（x）=x11x6=x17由此得到相应的（x）=0（modg（x）（x）x16x9+x8+x6+x5+x2+x（modg（x）（x）x17x10+x9+x7+x6+x3+x2（modg（x）第第6章章循环码的译码循环码的译码图6-823，12码修正捕错译码器第第6章章循环码的译码循环码的译码

（1）开始时所有移存器中的存数均清洗为0，开关K1、K2和K5接至D=0的位置，K3和K4接至E=0的位置。

接收到的R（x）一方面送入23（=11+12）级缓存器中，一方面送入伴随式计算电路计算伴随式。

23次移位后，得到伴随式S0（x）=s10x10+s9x9+s0把它送至3个错误图样检测电路；第第6章章循环码的译码循环码的译码

（2）开关K1、K2和K5接到D=1的位置，K3和K4仍在E=0的位置，由错误图样检测电路检测可纠正的错误图样：

若w（S0（x）3，认为错误全在后11位中，且错误图样就是S0（x），此时T1=1导致E=1，K3和K4接至E=1位置，并在移位过程中对11级缓存器的输出进行纠错。

第第6章章循