第六章 循环码的译码

1、第第6章章 循环码的译码循环码的译码 第第6章章 循环码的译码循环码的译码 6.1 6.1 循环码译码的一般原理循环码译码的一般原理 6.2 6.2 捕错译码捕错译码 6.3 6.3 大数逻辑译码原理大数逻辑译码原理 6.4 大数逻辑可译码的构造 6.5 软判决译码的基本原理 6.6 码字错误概率最小的软判决译码 习题习题 第第6章章 循环码的译码循环码的译码 6.1 循环码译码的一般原理循环码译码的一般原理 设发送的码字是设发送的码字是C(x)=(cn-1x n-1+c1x+c0)(今后不再今后不再严格区分码字与码多项式严格区分码字与码多项式)， 通过通过q进制输入和输出的信进制输入和输出的

2、信道后，道后， 译码器输入端得到的是译码器输入端得到的是 R(x)=C(x)+E(x)=(r n-1 x n-1+r1x+r0) ri=ci+ei 式中，式中， E(x)=(en-1xn-1+e1x+e0)是信道产生的错误图样，是信道产生的错误图样， 应当指出，应当指出， 上述这些式中的上述这些式中的ci、 ri、 ei均是均是GF(q)中的元中的元素，素， 也就也就是我们这里仅讨论硬判决时的译码方法。是我们这里仅讨论硬判决时的译码方法。 第第6章章 循环码的译码循环码的译码 译码器的主要任务就是如何从译码器的主要任务就是如何从R(x)中得到正确的中得到正确的估计错误图样估计错误图样 (x)=

3、E(x)， 然后得到然后得到C(x)， 并由此得到并由此得到信息组信息组m(x)。 如同所有线性分组码的译码一样，如同所有线性分组码的译码一样， 循环码的译码循环码的译码也分为以下也分为以下3步：步： (1) 计算计算R(x)的伴随式的伴随式S(x)； (2) 根据伴随式根据伴随式S(x)找出估计错误图样找出估计错误图样 (x)； 第第6章章 循环码的译码循环码的译码 (3) R(x)- (x)= ， 得到译码器输出的估值码得到译码器输出的估值码字字 ， 并送出译码器给用户。并送出译码器给用户。 若若 =C， 则译码正则译码正确，确， 否则译码错误。否则译码错误。 如果是非系统码，如果是非系统

4、码， 则还必须由则还必须由 中得到估值信中得到估值信息组息组 ； 如果是系统码，如果是系统码， 这一步可省略。这一步可省略。 由于循环码的循环特性，由于循环码的循环特性， 在上述各步运算中，在上述各步运算中， 往往往比非循环码的计算要简单。往比非循环码的计算要简单。 CCCCm 第第6章章 循环码的译码循环码的译码 一、一、 伴随式计算和错误的检测伴随式计算和错误的检测 设发送的码字设发送的码字C=(c n-1， c n-2， ， c 1， c 0)， 信道信道产生的错误图样为产生的错误图样为E=(e n-1， e n-2， ， e 1， e 0)， 译译码器收到的码器收到的n重重 R=C+E

5、=(c n-1+e n-1， c n-2+e n-2， ， c 1+e 1， c 0+e 0) =(r n-1， r n-2， ， r 1， r 0) r i=c i+e i第第6章章 循环码的译码循环码的译码 由伴随式定义可知，由伴随式定义可知， 相应的伴随式是相应的伴随式是 S=RHT=(C+E)HT=EHT 可知伴随式可知伴随式S仅与错误图样有关，仅与错误图样有关， 而与发送的码字而与发送的码字无关，无关， 由它可计算出错误图样由它可计算出错误图样E。 第第6章章 循环码的译码循环码的译码 设设n， k循环码的生成多项式为循环码的生成多项式为g(x)， 且且 xn-1=g(x)h(x)，

6、 g(x)=n-k。 该码的一致校验矩阵该码的一致校验矩阵由式由式(5.1.9)可知为可知为)(mod121xgxxxHTTnTnT第第6章章 循环码的译码循环码的译码 所以 )(mod),()(mod),()(mod),(0101101012101210121xgxxeeexgxxccccxgxxxxrrrrHRSnnnnnnnnnT第第6章章 循环码的译码循环码的译码 由此式可知相应的多项式表示为由此式可知相应的多项式表示为 S(x)C(x)+E(x)R(x)E(x) (mod g(x) (6.1.1) 或或 S(x)=Rg(x)+g(x)q(x)=Eg(x)+g(x)q1(x) (6.1

7、.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)在在伴随式计算电路中无输入时伴随式计算电路

8、中无输入时(自发运算自发运算)右移一位的结果，右移一位的结果， 即即 S1(x)xS(x) (mod g(x) (6.1.3) 第第6章章 循环码的译码循环码的译码 证明 由伴随式定义可知xR(x)之伴随式为 S1(x)xR(x) (mod g(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 (mod g(x)因此 S1(x)xS(x) (mod g(x) 第第6章章 循环码的译码循环码的译码 推论6.1.1 xjR(x)的伴随

9、式Sj(x)xjS(x) (mod g(x)， j=0， 1， ， n-1。 而任意多项式a(x)乘R(x)所对应的伴随式 Sa(x)a(x)S(x) (mod g(x) (6.1.5)第第6章章 循环码的译码循环码的译码 在q进制时， 若码要纠正t个错误， 则错误图样代表共有11) 1(11jnqNjtj (6.1.6) 个。 译码时， 只要知道此代表图样的伴随式， 该类其它错误图样的伴随式都可由此代表图样伴随式在伴随式计算电路中得到。 这样， 就使得循环码译码器的错误图样识别电路大为简化， 由原来识别jtjqjnN) 1(12(6.1.7) 个图样减少到N1个。 第第6章章 循环码的译码循

10、环码的译码 例如二进制码， n=63， t=4， 由式(6.1.6)和式(6.1.7)计算译码器所需识别的错误图样个数如表 6 - 1所示。 表 6 - 1 N1， N2比较表 第第6章章 循环码的译码循环码的译码 例6.1 二进制7， 4， 3循环汉明码， 它的g(x)=x3+x+1， 相应的校验矩阵100101101011100010111)(mod0123456xgxxxxxxxHTTTTTTT第第6章章 循环码的译码循环码的译码 由式(6.1.6)知， 构造此译码器的错误图样识别电路时， 只要识别一个图样E6=(1000000)就够了， 该图样的伴随式就是H的第一列(101)。 可知，

11、 识别E6错误图样的识别电路就是一个检测伴随式是否是(101)的电路。 由此可得如图 6 - 1所示的译码电路。 图中的伴随式计算电路就是一个g(x)=x3+x+1的除法电路， 而有3个输入端的与门和反相器， 组成了识别(101)的伴随式识别器。 第第6章章 循环码的译码循环码的译码 图 6 - 1 7， 4， 3循环汉明码译码器第第6章章 循环码的译码循环码的译码 译码器的译码过程如下： (1) 开始译码时门开， 移存器内容全为0。 收到的R(x)=r6x6+r 0， 以高次项系数(r 6)至低次项系数的次序， 一方面送入7级缓冲器， 一方面送入g(x)除法电路计算伴随式。 7次移位后， R

12、(x)的系数全部存入缓存器， g(x)电路也得到了伴随式S0(x)， 此时门关， 禁止输入。 第第6章章 循环码的译码循环码的译码 (2) 若S0(x)1+x2x6 (mod g(x)， 说明E(x)=x6， r 6位有错， 伴随式计算(g(x)除法器)电路中的D0、 D1、 D2存贮的值是(101)， 它就是S0(x)=1+x2之系数。 D1的0经反相后成了1， 与门3个输入端全为1， 呈打开状态。 这时译码器继续移位， r 6从缓存器输出， 与门也输出一个信号“1”与r 6相加， 使r 6由原来的1变成0， 或由0变成1， 纠正了r 6的错误： r6+1=c6+e 6+1=c 6+1+1=

13、c 6， 得到了原来发送的码元。 此时与门的纠错信号“1”也反馈到伴随式计算电路输入端(图中虚线所示)， 对伴随式进行修正， 以消去该错误对伴随式的影响。 第第6章章 循环码的译码循环码的译码 这由于 R(x)=r n-1 x n-1+r 1x+r 0 相应的伴随式是S0(x)。 纠错后R(x)成为 R1(x)=(r n-1+1)x n-1+r 1x+r 0 与R1(x)相应的伴随式 S1(x)S0(x)+x n-1 (mod g(x) 因为纠错是在第n+1次移位进行的， 所以R1(x)成为 R1(x)=xR1(x) r n-2 x n-1+ r 0 x+r n-1+1 (mod xn-1)第

14、第6章章 循环码的译码循环码的译码 相应的伴随式 S1(x)xS1(x)xS0(x)+xnxS0(x)+1 (mod g(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 (mod g(x)， 此时与门不打开， 说明r 6正确。 这时伴随式计算电路和缓存器各移位一次， r 6输出， r 5移到缓存器最右一级， 伴随式计算电路得到的

15、伴随式是 S1(x)xS0(x)xE(x)x2+1 (mod g(x)第第6章章 循环码的译码循环码的译码 因此再移动一次， 与门输出的纠正信号“1”正好与缓存器输出的r 5=c 5+1相加， 得到了c 5， 从而完成了纠错。 若r 5不错， 则重复上述过程一直到译完一个码字为止。 该译码过程可用表 6 - 2表示， 已知R(x)=x6+x+1， E(x)=x4。 由该表知， 到第10个节拍， 与门输出一个“1”纠正r 4， 最后译码器输出码字(1010011)。 第第6章章 循环码的译码循环码的译码 表 6 - 2 图 6 - 1译码器译码过程 第第6章章 循环码的译码循环码的译码 从上述译

16、码过程可知， 译一组码共需14(2n=14)个节拍， 仅当第一组的R(x)移出7级缓存器后， 才能接收第二组的R(x)。 为了使译码连续， 必须再加一个伴随式计算电路， 如图 6 - 2。 第第6章章 循环码的译码循环码的译码 图 6 - 2 7， 4码完整译码器 第第6章章 循环码的译码循环码的译码 开始工作时， 所有移存器的存数全为0， 门1开、 门2关。 当k=4次移位后， 4级缓存器接收了前面的4个信息位(对系统码而言)， 此时门1关， 并使4级缓冲器停止移位。 再移动n-k=3次后， g(x)除法电路得到了伴随式S0(x)， 此时门2开， 把上边g(x)除法电路中的伴随式送到下面的伴

17、随式计算电路中， 随即门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汉明码加一个全校验位得到。 它的码字(c n-1， ， c 0， c )中前n个码元(c n-1， ， c 0)是汉明码的一个码字， c 是全校验位。 扩展汉明码的码长是8的整数倍，

18、特别适用于计算机或微机组成的数据处理或数据传输系统中。 第第6章章 循环码的译码循环码的译码 扩展汉明码能纠正一个错误同时发现两个错误， 虽然它不是循环码， 但它译码电路的主要部分与循环汉明码的译码器相同， 只要加上检错电路即可。 如8， 4， 4扩展码， 只要在7， 4， 3循环汉明码译码器中， 加一个检错电路即成， 如图 6 - 4。 图中， (a)部分的电路基本上与图 6 - 1同， 是循环汉明码的译码器， 不同的是多加了一个全校验位检查电路， 它由一个级移存器加一个模2加法器组成。 图中， (b)部分电路是一个检错电路。 该译码器的译码过程如下： 第第6章章 循环码的译码循环码的译码

19、图 6 - 4 8， 4， 4扩展码译码器 第第6章章 循环码的译码循环码的译码 (1) 开始时所有寄存器中的内容为0， 门1和门2开。 移位4次后门2关， R(x)=r 6x6+r 0+r 中的前4位(r 6， r 5， r 4， r 3)存入4级缓存器中， 它就是待纠错的4个信息元。 移动7次后门1关， R(x)的前7个码元(r 6， r 5， r 4， r 3， r 2， r 1， r 0)， 已全部送入7， 4， 3码所决定的伴随式计算电路中， 得到了伴随式(s2， s1， s0)。 第8次移位后， 在全校验位检查电路中得到了全校验的结果s， 此时译码器不再输入。 第第6章章 循环码的

20、译码循环码的译码 (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时， 译码器认为出现了一个以上的奇数个错误， 错误

21、告警电路也输出一个信号给用户。 当然， 为了使译码连续， 在图 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的码字组成

22、。 若n， k循环码的码字 C(x)=c n-1 x n-1+c n-2 x n-2+c 0 则n-i， k-i缩短循环码的码字 C(x)=c n-1-ix n-1-i+c 0 因此， 缩短循环码的译码器必须在原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级缓存器变成

23、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) (mod g(x) 式中式中 EI(x)=e n-1 x n-1+e n-k x n-k Ep(x)=e n-k-1 x n-k-1+e 0第第6章章 循环码的译码循环码的译码 分别是在码字信息组分别是在码字信息

24、组(或前或前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) (mod g(x)第第6章章 循环码的译码循环码的译码 对于纠对于纠t个错误的循环码来说，个错误的循环码来说， 必须使必须使t个错误能个错误能连续地出现在连续地出现在n-

25、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循循环码，环码， 捕错译码过程中已把捕错译码过

26、程中已把t个错误集中在个错误集中在Ri(x)的最低的最低次次n-k位以内的充要条件是此时的伴随式重量位以内的充要条件是此时的伴随式重量 (Si(x)t (6.2.2) 证明 若错误已集中在n-k位低次位码元段以内， 则 Si(x)xiE(x)=Ei(x)=Eip(x) (mod g(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(S

27、i(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)， 因

28、此上式与假设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 - 5 15， 7， 5循环码捕错译码电路第第6章章 循环码的译码循环码的译码 (1) 开始工作时， 所有移存器和缓存器清洗为 0， 门 2、 门

29、 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)的重量， 若仍大于

30、2， 则继续循环移位。 n， k循环码的一般捕错译码器如图 6 - 6 和图 6 - 7， 它们分别称为第一类和第二类捕错译码器。 第第6章章 循环码的译码循环码的译码 图 6 - 6 n， k循环码的第一类捕错译码器 第第6章章 循环码的译码循环码的译码 图 6 - 7 n， k循环码的第二类捕错译码器 第第6章章 循环码的译码循环码的译码 第二类译码器与第一类的差别， 仅在于第二类译码器是把接收到的R(x)自动乘以xn-k后， 再进入g(x)除法电路计算伴随式， 即R(x)从g(x)电路的最高次位送入。 所以 R(x)xn-k(r n-1 x n-1+r n-2 x n-2+r 0)x n

31、-k r n-1 x n-k-1+r n-2 x n-k-2+r k+r k-1x n-1 +r 1x n-k+1+r 0 x n-k (mod xn-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)

32、的条件， 但k仅比nt稍大或相等， 也就是说在译码过程中不能把错误全部集中在n-k个码元段以内， 而有个别错误可能在其它码元位上。 为了解决此问题， 必须对捕错译码加以适当修正。 第第6章章 循环码的译码循环码的译码 译码过程中， 若译码器能把大部分错误捕捉到n-k个码元段以内， 同时使个别错误进入某几个预先指定的位上， 则也能确定此时的错误图样。 当然， 为了实现这种运算必须附加一些电路， 以确定错误是否在某几个指定的位置。 第第6章章 循环码的译码循环码的译码 设n， k循环码能纠正t个错误， 生成多项式是g(x)。 译码器收到R(x)后， 计算伴随式 S0(x)E(x)=EI(x)+Ep

33、(x)SI(x)+Ep(x) (mod g(x) SI(x)EI(x)=e n-1 x n-1+e n-k x n-k (mod g(x) Ep(x)So(x)-SI(x) (mod g(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(

34、x)x n-k Qj(x) (mod g(x) Ij=0， 1， 第第6章章 循环码的译码循环码的译码 是x n-k Qj(x)的伴随式， 即如果在前k位上错误图样EI(x)= x n-k Qj(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)()()(xSxSxEjiIip第第6章章 循环码的译码循环码的译码 例 6.3 23， 12， 7Golay码， 它的生

35、成多项式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可得： x n-k Q1(x)=x110=0 x n-k Q2(x)=x11x5=x16 x

36、 n-k Q3(x)=x11x6=x17 由此得到相应的 (x)=0 (mod g(x) (x)x16x9+x8+x6+x5+x2+x (mod g(x) (x)x17x10+x9+x7+x6+x3+x2 (mod g(x)0IS1IS2IS第第6章章 循环码的译码循环码的译码 图 6 - 8 23， 12码修正捕错译码器 第第6章章 循环码的译码循环码的译码 (1) 开始时所有移存器中的存数均清洗为 0， 开关K1、 K2和K5接至D=0 的位置， K3和K4接至E=0 的位置。 接收到的R(x)一方面送入23(=11+12)级缓存器中， 一方面送入伴随式计算电路计算伴随式。 23 次移位后

37、， 得到伴随式 S0(x)=s10 x10+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章章 循环码的译码循环码的译码 若w(S0(x)-SI1(x)2， 则 S0(x)-SI1(x) =(s10 x10+s9x9+s1x+s0)

38、-(x9+x8+x6+x5+x2+x) =s10 x10+s9x9+s8x8+s7x7+s6x6+s5x5 +s4x4+s3x3+s2x2+s1x+s0第第6章章 循环码的译码循环码的译码 若w(S0(x)-SI2(x)2， 则 S0(x)-SI2(x)=(s10 x10+s9x9+s1x+s0) -(x10+x9+x7+x6+x3+x2) =s10 x10+s9x9 +s8x8+s7x7+s6x6+s5x5 +s4x4+s3x3+s2x2+s1x+s0第第6章章 循环码的译码循环码的译码 若w(S0(x)3， 或w(S0(x)-SI1(x)2， 或w(S0(x)-SI2(x)2， 则进行下一

39、步； (3) 把 23 级缓存器和伴随式计算电路同时循环移位一次， 对新得到的伴随式S1(x)， 进行如同第(2)步的检查； 第第6章章 循环码的译码循环码的译码 (4) 当缓存器和伴随式计算电路共移位2n次后， 译完了一个码字。 此时K1、 K2和K5接至D=0的位置， K3 和K4 接到E=0 的位置； (5) 送入第二组R(x)， 同时第一组已纠过错的码元由 23 级缓存器输出。 所以， 接收到的R(x)从输入译码器直至输出完为止， 共需移位3n(323)次。 第第6章章 循环码的译码循环码的译码 三、 覆盖多项式的数目与建立 无论是对二进制还是q进制码， 修正捕错译码器的复杂性主要决定

40、于覆盖多项式集合Qj(x)中， 覆盖多项式数目j的多少， 若j过大， 则译码器太复杂而不能实用。 对于一个特定的循环码是否一定能找到覆盖多项式？ 若能找到， 则应如何找Qj(x)？最小的j应是多少？这些是捕错译码能否实用的关键问题。 第第6章章 循环码的译码循环码的译码 对于满足式(6.2.1)的码， 也就是错误能全部集中到连续的n-k位以内， 或能保证连续k位无错， 则覆盖多项式必定存在， 就是Q0(x)=0， j=1； 如果码不满足式(6.2.1)， 但满足以下关系式： R2t 或 2ntk (6.2.7)第第6章章 循环码的译码循环码的译码 引理 6.2.1 对于纠t个错误的GF(q)上

41、的n， k循环码， 当且仅当R2t时， 覆盖多项式集合必存在。 表 6 - 33， 4给出了某些二进制循环码的覆盖多项式集合及大小， 表中仅列出了Qj(x)中除 0 以外的所有单项式， 并且表中还列出了某些t3二进制循环码的覆盖多项式， 有关寻找这些覆盖多项式的详细讨论， 请参阅文献3、 4。 第第6章章 循环码的译码循环码的译码 表 6 - 3 某些二进制循环码的覆盖多项式 第第6章章 循环码的译码循环码的译码 6.3 大数逻辑译码原理大数逻辑译码原理 循环码译码器的复杂性主要决定于码的代数结构。循环码译码器的复杂性主要决定于码的代数结构。 纠单个错误的汉明码、纠单个错误的汉明码、 纠单个突

42、发错误的循环码，纠单个突发错误的循环码， 以以及某些纠错能力较低的码，及某些纠错能力较低的码， 可以用以前所介绍的比较可以用以前所介绍的比较简单的方法如捕错译码。简单的方法如捕错译码。 但是，但是， 对绝大多数纠多个随对绝大多数纠多个随机错误的循环码来说，机错误的循环码来说， 却没有如此简单的译码方法。却没有如此简单的译码方法。 不过，不过， 有一类循环码的子类，有一类循环码的子类， 码的结构比较特殊，码的结构比较特殊， 可以用较简单的大数逻辑方法译码，可以用较简单的大数逻辑方法译码， 这类码称为大数这类码称为大数逻辑可译码。逻辑可译码。 第第6章章 循环码的译码循环码的译码 大数逻辑译码是大

43、数逻辑译码是 1954 年里德年里德(Re e d)， 在译里德在译里德-马勒尔马勒尔(Re e d-Mulle r ， RM)码时提出的一种较简单码时提出的一种较简单的译码方法的译码方法1， 2。 可是对于一般码长而言，可是对于一般码长而言， 能能用大数逻辑方法译码的大数逻辑可译码，用大数逻辑方法译码的大数逻辑可译码， 其纠错能力其纠错能力和码率都稍次于有相同参数的其它码如和码率都稍次于有相同参数的其它码如BCH码，码， 但由但由于它的译码算法和设备均比相应的于它的译码算法和设备均比相应的BCH码译码方法要码译码方法要简单，简单， 因此在实际中有较广的应用。因此在实际中有较广的应用。 第第6

44、章章 循环码的译码循环码的译码 一、 大数逻辑译码的基本概念 通过以下例子介绍二进制循环码的大数逻辑译码的基本思想。 7， 3， 4增余删信汉明码， 它的生成多项式g(x)=(x+1)(x3+x+1)=x4+x3+x2+1， 校验矩阵是1000110010001100101110001101H第第6章章 循环码的译码循环码的译码 设接收的n重R=C+E， C=(c 6， c 5， ， c 0)是发送的码字， E=(e 6， e 5， ， e 0)是错误图样。 相应的伴随式01230561000110010001100101110001101sssseeeEHSTT第第6章章 循环码的译码循环码

45、的译码 对伴随式的分量s0、 s1、 s2和s3进行线性组合， 也就是对H矩阵的行进行线性组合， 得到以下一组校验方程： A1=s3 =e 6 +e 4+e 3 A2= s1 = e 6+e 5 +e 1 (6.3.1) A3= s2+s0= e 6+ +e 2 +e 0第第6章章 循环码的译码循环码的译码 显然， 上述方程的系数所组成的 3 个七重数组： (1011000)， (1100010)和(1000101)是H行的线性组合， 在H的行空间中。 用A1、 A2和A3代表这 3 个七重， 则码字C满足： CAT1=CAT2=CAT3=0 或010100010100011000110100

46、56TCHccc(6.3.2) 第第6章章 循环码的译码循环码的译码 可知: A1=c 6 +c 4+c 3 =0 A2= c 6+c 5 +c 1 =0 A3= c 6 +c 2 +c 0 =0 得到一组新的校验方程。 它们有以下特点： c 6含在每一方程之中， c 5、 c 4、c 3、 c 2、 c 1和c 0只含在某一方程中。 有这种特点的校验方程称为正交于c 6(或x6、 e 6)码元位的正交校验方程(或正交一致校验和式)， 由它们的系数所组成的矩阵H0， 称为正交一致校验矩阵。 所以， 由式(6.3.2)可得该码的正交校验矩阵第第6章章 循环码的译码循环码的译码 101000101

47、0001100011010H第第6章章 循环码的译码循环码的译码 定义 6.3.1 若某一特定码元位(如xn-i)出现在H0矩阵中J行的每一行中， 而其它码元位至多在其中一行出现， 则称H0为正交于该码元位(xn-i)的正交一致校验矩阵。 7， 3， 4码能纠正一个错误同时发现两个错误， 由上面的H 0矩阵或式(6.3.2)可以发现： 第第6章章 循环码的译码循环码的译码 (1) 发生一个错误， 且在正交码元位上： e 6=1， 则可得A1=1， A2=1， A3=1。 (2) 发生一个错误但不在正交码元位上： e 6=0， e i=1(i取5， 4， 3， 2， 1， 0中的某一个)， 则只

48、有一个Aj=1(j=1， 2， 3)， 其它两个A均为0。 (3) 发生两个错误， 其中一个在正交位上， 另一个在其它位(如e 5)： e 6=1， e 5=1， 则A1=1， A2=0， A3=1。 (4) 发生两个错误， 都不在正交位上， 设e 5=1， e 4=1， 则A1=1， A2=1， A3=0。 第第6章章 循环码的译码循环码的译码 定理 6.3.1 一个循环码若在任一位上能建立J个正交一致校验和式， 则该码能纠正tJ2个错误(式中， x表示取x的整数部分)。 第第6章章 循环码的译码循环码的译码 定义 6.3.2 如果某一码元位置集合c i1， c i2， ， c il的线性组

49、合 ai1c i1+ai2c i2+ailc il 在A1， A2， ， AJ的一致校验和式中均出现， 而其余码元位置集合至多在其中一个校验和式中出现， 则说A1， A2， ， AJ在集合c i1， c i2， ， c il上正交， 称A1， A2， ， AJ是正交于该码元位置集合的正交一致校验和式， 上式中的aij是非0值。 第第6章章 循环码的译码循环码的译码 例如7， 4， 3循环汉明码， g(x)=x3+x2+1。 它的校验矩阵100111001001110011101H由S=EHT=(s2， s1， s0)得到： 第第6章章 循环码的译码循环码的译码 A111=s2=(e 6+e 4

50、)+e 3+e 2 A112=s1=(e 6+e 4)+e 5+e 1 (6.3.4) A121=s1=(e 6+e 5)+e 4+e 1 A122=s2+s0=(e 6+e 5)+e 2+e 0 (6.3.5)第第6章章 循环码的译码循环码的译码 组成了J=2 组对(e6， e4)=E11和对(e6， e5)=E12码元位置集合正交的正交一致校验和式。 若码组中仅出现一个错误， 则根据A111和A112中取值是 1 的个数多少， 正确译得(e 6+e 4)=A11的值。 由A121和A122中取值是1的个数多少， 正确译得(e6+e5)=A12的值。 然后再根据A11， A12中取值为 1

51、的个数， 译出x6 码元位是否错误。如x6码元位发生了错误， e 6=1。 由式(6.3.4)和式(6.3.5)有： 第第6章章 循环码的译码循环码的译码 A111=(e 6+e 4)+e 3+e 2=1 A112=(e 6+e 4)+e 5+e 1=1 A121=(e 6+e 5)+e 4+e 1=1 A122=(e 6+e 5)+e 2+e 0=1 可得： A11=(e 6+e 4)=1 A12=(e 6+e 5)=1 第第6章章 循环码的译码循环码的译码 此两方程正交于e6， 可以根据A11和A12中取1个数的多少， 决定出e 6的值。 这里A11=A12=1， 有两个 1， 所以e 6

52、=1。 从该例看出， 为了译出一个码元需要进行两次大数判决。 每次需要两个正交校验和式， 第一次是对码元位置集合e 6， e 4和e 6， e 5正交， 第二次是对两个码元的位置集中的e6(x6)码元位正交， 所以是两步大数逻辑译码。 7， 4， 3循环汉明码就称为两步大数逻辑可译码。 第第6章章 循环码的译码循环码的译码 二、 大数逻辑译码器 大数逻辑译码器分为两类： 型和型， 它们没有本质上的不同。 下面先介绍一步大数逻辑译码器， 再介绍L步大数逻辑译码器。 1型大数逻辑译码器 以7， 3， 4码的译码器为例， 说明这种类型的一步大数逻辑译码器的构成和工作过程。 由式(6.3.1)和式(6.3.2)可知： 第第6章章 循环码的译码循环码的译码 012345602133210101000101000110001101eeeeeeessssAAAEHT第第6章章 循环码的译码循环码的译码 图 6 - 9 7， 3， 4码型大数逻辑译码器 第第