循环码(7,4)

第3 章 循环码编码和译码

3.1 循环码概念

循环码是线性分组码中一个重要的分支。它的检、纠错能力较强，编码和译码设备并不复杂，而且性能较好，不仅能纠随机错误，也能纠突发错误。

循环码是目前研究得最成熟的一类码，并且有严密的代数理论基础，故有许多特殊的代数性质，这些性质有助于按所要求的纠错能力系统地构造这类码，且易于实现，所以循环码受到人们的高度重视，在FEC系统中得到了广泛应用。

3.1.1、循环码定义

定义：一个线性分组码，若具有下列特性，则称为循环码。设码字

A?(an?1an?2... (3-1) a1a0)若将码元左移一位，得

A(1)?(an?2an?1...a1a0an?1)A(1)也是一个码字。

注意：循环码并非由一个码字的全部循环移位构成。

3.1.2 循环码的特点

表3-1列出了某（7，4）循环码的全部码组

码组 编号 a6 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 信息位 a5 0 0 0 0 1 1 1 1 a4 0 0 1 1 0 0 1 1 a3 0 1 0 1 0 1 0 1 a2 0 1 1 1 0 1 1 0 监督位 a1 0 0 1 0 1 1 0 0 a0 0 1 1 1 1 0 0 1 码组 编号 a6 9 10 11 12 13 14 15 16 1 1 1 1 1 1 1 1 信息位 a5 0 0 0 0 1 1 1 1 a4 0 0 1 1 0 0 1 1 a3 0 1 0 1 0 1 0 1 a2 1 0 0 1 1 0 0 1 监督位 a1 1 1 0 0 0 0 1 1 (3-2)

a0 0 1 1 0 1 0 0 1

循环码有两个数学特征：

1.线性分组码的封闭型：即如果c1，c2，是与消息m1，m2对应的码字，则c1+c2必定是与m1+m2对应的码字。

2.循环性，即任一许用码组经过循环移位后所得到的码组仍为该许用码组集合中的一个码组。

即若（an-1 an-2 … a1 a0）为一循环码组，则（an-2 an-3 … an an-1）、（an-3 an-2 … an-1 an-2）、……还是许用码组。也就是说，不论是左移还是右移，也不论移多少位，仍然是许用的循环码组。

以3号码组（0010111）为例，左移循环一位变成6号码组（0101110），依次左移一位构成的状态图如图1.1-2所示。

1001011 1100101 1110010 0010111 0101110 1011100 0111001

图3-1 （7，4）循环码中的循环圈

可见除全零码组外，不论循环右移或左移，移多少位，其结果均在该循环码组的集合中（全零码组自己构成独立的循环圈）。

3.2 码多项式

为了用代数理论研究循环码，可将码组用多项式表示，循环码组中各码元分别为多项式的系数。长度为n的码组A?(an?1an?2...a1a0)用码多项式表示则为

A(x)?an?1xn?1?an?2xn?2?...?a1x?a0式中，x的幂次是码元位置的标记。若把一个码组左移i位后的码组记为，

(3-3)

A(i)?(an?1?ian?2?i...an?i?1an?i)其码多项式为

(3-4)

A(i)(x)?an?1?ixn?1?an?i?2xn?2?...?an?1?ix?an?iA(i)(x)可以根据xiA(x)按模xn+1运算得到，即

(3-5)

A(i)(x)?xiA(x)mod(xn? (3-6) 1)或

xiA(x)?Q(x)(xn?1)?A(i)( (3-7) x)

式中，Q(x)为xiA(x)除以xn+1的商式，而xiA(x)等于A(i)(x)被xn+1除得之余式。 以码组0100111为例，若将此码左移两位，则由式（3-7）可得x2(x5+x2+x+1)=Q(x)(x7+1)+A(2)(x)易有其余式为A(2)(x)=x4+x3+x2+x，对应的码组为0011101，它与直接对码组进行循环左移的结果相同。

3.3 生成多项式

（n,k）循环码码组集合中（全“0”码除外）幂次最低的多项式（n-k）阶称为生成多项式g(x)。它是能整除xn+1且常数项为1的多项式，具有唯一性。

下面证明g(x)唯一性：

[证明]令g(x)?g0?g1x?...?gr?1xr?1?xr是（n，k）码中一个次数最低的非零码字多项式。若g(x)不是唯一的，则必然存在另一个次数为r的码字多项式，例如

??g1?x?...?gr??1xr?1?xrg?(x)?g0由于（n，k）是线性的，所以

?)?(g1?g1?)x?...?(gr?1?gr??1)xrg(x)?g?(x)?(g0?g0也是一个码字多项式，显然若g(x)?g?(x)?0，则它必是一个次数低于r的非零码字多项式。这与假设g(x)是次数最低非零码字多项式矛盾，所以g(x)?g?(x)?0，因此

g(x)?g?(x)(3-8)

从而g(x)唯一。

集合中其他码多项式，都是按模(xn+1)运算下g(x)的倍式，即可以由多项式g(x)产生循环码的全部码组。

假设信息码多项式为m(x)，则对应的循环码多项式为

A(x)=m(x)g(x) (3-9)

式中，m(x)为次数不大于k-1的多项式，共有2k个（n,k）循环码组。

考查表3-1，其中n-k=4阶的多项式只有编号为2的码组（0011101），所以表中所示（7，4）循环码组的生成多项式g(x)=x4+x3+x2+1，并且该码组集合中的任何码多项式A(x)都可由信息位乘以生成多项式得到

A(x)=(mk-1+mk-2+…+m1+m0)g(x)mod(xn+1) (3-10)

式中，(mk-1mk-2…m1m0)为信息码元。 对于（7，k）循环码，x7+1的因式分解为

x7+1=(x+1)(x3+x+1)(x3+x2+1) (3-11)

由该式可以构成表3-2所示几种（7，k）循环码。

表3-2 （7，k）循环码的生成多项式

(7,k) (7,1) (7,3) (7,4) (7,6)

g(x) (x+x+1)(x3+x2+1) (x+1)(x3+x+1)或(x+1)(x3+x2+1) x3+x+1或x3+x2+1 x+1 3从表（3-2）中可以看出，即使n,k均已确定，也可能由多种生成多项式供选择，选用的多项式不同，产生出的循环码组也不同。

3.4 生成矩阵

根据各码组集合中生成多项式的唯一性，可以构造生成矩阵G。由于g(x)的次数为n-k，则g(x),xg(x),…,xk-1g(x)都是码多项式，而且线性无关，因此以这k各多项式对应的码组作为k行就能构成该循环码的生成矩阵，因此循环码的生成矩阵多项式可以写成

?xk?1g(x)?

?? ...??

G(x)?...?

?.? xg(x)???g(x)???

(3-12)

以生成多项式g(x)=x4+x3+x2+1构造G(x)，相应的矩阵形式为 65422??x?x?x?x??xg(x)

????543

G(x)??xg(x)???x?x?x?x?

?g(x)??x4?x3?x2?1?

????

(3-13)

则G为g(x)升幂排列时的G为

?1

?

G??0 ?0?110100??111010?011101?? (3-14)

对式（3-14）作线性变换，整理成典型形式的生成矩阵

?1001110??G??0100111????0011101??（3-15）

若信息码元与式（3-15）相乘，得到的就是系统循环码。

3.5 监督多项式与监督矩阵

如前所述，在（n，k）循环码中，由于g(x)能除尽,因此xn+1可分解成g(x)和其他因式的乘积，记为

xn+1=g(x)h(x) (3-16)

即可写成

h(x)=xn+1/g(x) (3-17)

由于g(x)是常数项为1的r次多项式，所以h(x)必为k次多项式。称h(x)为监督多项式或一致校验多项式，与式（3.18）给出的G(x)相对应，监督矩阵多项式可表示为

?xh(x)???...???H(x)??...?*??xh(x)??*??h(x)?r?1*

(3-18)

式中，h*(x)式h(x)的逆多项式。

由式（1.1.14）可知，前述生成多项式的g(x)的一致校验多项式为h(x)x3+x2+1，所以其一致校验矩阵（监督矩阵）为

?1?0H(x)???0??0101000?

110100??

011010?

? （3-19）

001001?

3.6 循环码的编码及实现 利用生成多项式g(x)实现编码：

如上所述，一但循环码的生成多项式g(x)确定时，码就完全确定了。现在讨论生成多项式g(x)给定以后，如何实现循环码的编码问题。 若已知

g(x)?gn?kxn?k?gn?k?1xn?k?1?...?g1x?g0并设信息元多项式

(3-20)

m(x)?mk?1xk?1?mk?2xk?2?...?m1x?m0xn?k乘以m(x)，再加上校验元多项式r(x),这样得到的码字多项式c(x)为

(3-21)

要编码成系统循环码形式，即码字的最左边k位是信息元，其余n-k位是校验元，则要用

c(x)?xn?km(x)?r(x)其中r(x)?rn?k?1xn?k?1?...?r1x?r0

由于循环码属于线性分组码C(x)一定是g(x)的倍式，即有

(3-22)

c(x)?xn?km(x)?r(x)?q(x)g(x) (3-23) c(x)?(xn?km(x)?r(x))modg(x)?0 (3-24)

注意到g(x)为n-k次多项式，而r(x)最多为n-k-1次多项式，必有

r(x)?xn?km(x)modg(x) (3-25)

即r(x)必是xn-km(x)除以g(x)的余式。

上述过程指出了系统循环码的编码方法：首先将信息元多项式m(x)乘以xn-k成为xn-km(x)，然后将xn-km(x)除以生成多项式g(x)得到余式r(x)，该余式就是校验元多项式，从而得到式（3-22）所示的码字多项式

综上所述，系统循环码的编码问题，可以归结为两个多项式的除法运算，即将xn-km(x)除以生成多项式g(x)得到余式r(x)的运算。

首先根据给定的(n,k)值来选定生成多项式g(x)。即从(xn+1)的因子中选定一个(n-k)次多项式作为g(x)。所有多项式T(x)都能被g(x)整除。根据这条原则可以对给定的信息位进行编码。设m(x)为信息码多项式，其次数小于k。用xn-k 乘m(x)，得到的xn-k m(x)次数必定小于n。用g(x)除xn-k m(x)，得到余式r(x)，r(x)的次数必定小于g(x)的次数，即小于(n-k)。将此余式r(x)加在信息位后作为监督为，即将r(x)和xn-k m(x)相加，得到的多项式必定是一个码多项式。

m(x)xn?k 确定余式r(x)：xn?k m(x)/ g(x)的余式 确定c(x)，c(x)=xn?k 图3-2 循环码编码过程框

下面以(7,4)码为例演示编码过程 (1)确定g(x)。

由x7+1=(x+1)(x3+x2+1)(x3+x+1)所以g(x)= x3+x2+1或g(x)= x3+x+1；这里选择g(x)= x3+x2+1 (2)用xn-k 乘m(x)，该运算实际上是在信息码后附加上(n-k)个“0”，例如，信息码为1100，它写成多项式为m(x)=x3+x2。当n-k=7-4=3时，xn-k m(x)=x6+x5 它表示码组1100000。

(3)用g(x)除xn-k m(x)，得到商Q(x)和余式r(x)即[xn-k m(x)]/[ g(x)]= Q(x)+r(x)/ g(x) 例如[xn-k m(x)]/[ g(x)]=(x6+x5)/(x3+x2+1)=(x3+1)+(x2+1)/(x3+x2+1) 上式是用码多项式表示的运算。它和下式等效： 1100000/1101=1001+101/1101

(4)编出码组为T(x)= xn-k m(x)+ r(x)即T(x)= 1100000+101=1100101 由以上方法可以算出(7,4)码表：

表3-3(7,4)码表

序号 1 2 3 4 5 6 7 8 输入序列 0000 0001 0010 0011 0100 0101 0110 0111 输出序列 0000000 0001101 0010111 0011010 0100011 0101110 0110100 0111001 序号 9 10 11 12 13 14 15 16 输入序列 1000 1001 1010 1011 1100 1101 1110 1111 输出序列 1000110 1001011 1010001 1011100 1100101 1101000 1110010 1111111

根据表3-3所显示的计算结果，可用vb进行编程，流程图如下：

该程序以j为循环变量反复从输入序列中读取4位，然后根据码码表添加后3位，再累加到输出序列。当输入序列全部读取时即j等于输入序列长度len时，显示输出序列。当输入序列不能被4整除时，程序不对序列做任何处理，也没有输出序列。这时可重新输

图3-3 查表法编码流程图

j=len？ Y Len被4整除？ 开始 在text1输入序列 点击编码触发单击事件 计算text1序列长度len N 序列长度len对4求余 Y 初始化循环变量j 读入从j开始的4位序列 读入序列后查表加3位，累加到输出 N j+4 输出到text2 结束 入序列，保证其能被4整除。

图3-4 输入“0011”时程序运行结果

图3-5 输入“10100011”时程序运行结果

当输入序列位“0011”和“10100011”时的结果如图3-4和图3-5所示，经查表验证结果正确。说明此程序可以正确将输入序列分段并添加后三位，最后显示输出序列。程序符合设计要求。

3.7 循环码的译码及实现

设发送的码字为C(x),接收到的码字为R(x),如果C(x)= R(x)，则说明收到的码字正确；如果C(x)≠R(x)，则说明收到的码字出现错误，则有：

R(x)?C(x)?E(x)(3-26)

公式⑴中的E(x)称为错误图样。当E(x)=0时说明没有错误，用g(x)去除R(x)，得

R(x)C(x)?E(x)C(x)E(x)?== (3-27)

g(x)g(x)g(x)g(x)因为C(x)是由g(x)生成的,故C(x)必能为g(x)除尽，显然R(x)与E(x)同余式（R(x)≡ E(x)mod g(x)）,以g(x)除E(x)所得余式称为伴随式S(x)。

由公式⑴可知，R(x)HT=（C(x)+E(x)）H(x)= E(x)H(x)。若E(x)=0，则E(x)H(x)=0；若E(x)≠0，则E(x)H(x)≠0。这说明，R(x)HT仅与错误图样有关，而与发送的码字无关,由此可以确定错误图样表。

由于g(x)的次数为n-k次，g(x)除E(x)后得到余式（即伴随式S(x)）的次数为n-k-1次，

表3-4 伴随式与错误图像关系表

错误图样 错误图样码字 1000000 伴随式S(x) 2伴随式 100 E6(x)?x6 E5(x)?x5 x 110 0100000 x2?x x2?x+1 E4(x)?x4 E3(x)?x30010000 111 0001000 0000100 0000010 0000001 x?1 x?1 x 1 2011 E2(x)?x2101 E1(x)?x1010 E0(x)?x0 001 E(x)?0 0000000 0 000 故S(x)共有2n?k个表达式，每个可能的表达式对应一个错误格式，可以知道（7，4）循环码的S(x)共有27?4=8个表达式，可以根据错误图样表来纠正（7，4）循环码的一位错误。其伴随式如表3-4所示。

综上所述循环码的译码可按以下三个步骤进行： 1.接收到的y(x)计算伴随式式s(x);

?2.根据伴随式s(x)找到对应的估值错误图样e(x);

????3.计算c=y(x)+e(x),得到估值码字c(x)。若c(x)=c(x),则译码正确，否则，若?c(x)≠c(x),则译码错误。 由上述方法可计算出（7,4）码译码码表：

图3-5 （7,4）码译码表

序号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 输入序列 0000000及其1位出错码组 0001101及其1位出错码组 0010111及其1位出错码组 0011010及其1位出错码组 0100011及其1位出错码组 0101110及其1位出错码组 0110100及其1位出错码组 0111001及其1位出错码组 1000110及其1位出错码组 1001011及其1位出错码组 1010001及其1位出错码组 1011100及其1位出错码组 1100101及其1位出错码组 1101000及其1位出错码组 1110010及其1位出错码组 1111111及其1位出错码组 输出序列 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

开始 在text1输入序列 点击译码触发单击事件 计算text1序列长度len N

序列长度len对7求余 Len被7整除？ Y 初始化循环变量j 读入从j开始的7位序列 读入序列后查表求对应的4位码，累加到输出 N

j+7 j=len？ Y 输出到text2 结束 图3-6查表法译码流程图

该程序以j为循环变量反复从输入序列中读取7位，然后根据码码表去掉后3位，再累加到输出序列。当输入序列全部读取时即j等于输入序列长度len时，显示输出序列。

当输入序列不能被7整除时，程序不对序列做任何处理，也没有输出序列。这时可重新输入序列，保证其能被7整除。

图3-7输入“0011110”时译码结果

图3-8输入“10100100011110”译码结果

当输入序列位“0011110”和“10100100011110”时的结果如图3-7和图3-8所示，经查表验证结果正确。说明此程序可以正确将输入序列分段并去除后三位，最后显示输出序列。程序符合设计要求。

图3-9 “0000000”a0位出错时输出结果

图3-10 “0011110”a3位出错时输出结果

当输入序列位“0000000”a0位出错和“0011110”a3位出错时的结果如图3-9和图3-10所示，经查表验证结果正确。说明此程序可以正确纠正一位错码，并显示输出序列。程序符合设计要求。

图3-11 “0000000”a2，a3位出错时输出结果

当输入序列位“0000000” a2，a3位出错时的结果如图3-11所示，“0000000” a2，a3位出错会被认为是“0001101”a0位出错进行译码，所以该程序不能纠正和检测出两位错码。该结果验证了式（2-5）的正确性。

第4 章 总结

本文第1章介绍了纠错码的大致分类，回顾了纠错码的发展。按照对信息元处理方法的不同，分为分组码与卷积码两大类；根据校验元与信息元之间的关系分为线性码与非线性码；按照所纠错误的类型可分为纠随机错误的码、纠突发错误的码以及既能纠随机错误又能纠突发错误的码；按照每个码元取值来分，可分为二进制码与q进制码（q = pm，p为素数，m为正整数）；按照对每个信息元保护能力是否相等可分为等保护纠错码与不等保护（UEP）纠错码。

第2章简单介绍了线性分组码原理和编码译码方式。对于分组码一般用符号（n，k）表示，其中n是码组的总位数，又成为码组的长度（码长），k是码组中信息码元的数目，n–k= r 为码组中的监督码元数目。分组码（n，k）当信息码元与监督码元之间的关系为线性关系时，这种分组码就称为线性分组码。

对于长度为n的二进制线性分组码，它有M=

种可能的码组

，从种码组中，可以选择

个码组（k

个码组构成的码集中选出来的，这样剩下的码组就可以

度为n码组上，该码组是从M=

对这个分组码进行检错或纠错。

在分组码中，把码组中“1”的个数目称为码组的重量，简称码重。编码中所有码字重量的集合形 成该码的重量分布。如果全部M个码字都具有相同的重量，这种码叫做固定重量码，或叫恒重码。把两个码组中对应位上数字不同的位数称为码组的距离，简称码距。码距又称汉明距离。

一般而言，对于任意一种编码，其中各个码组之间的距离不一定相等。这时，将其中最小的距离称为码距dmin。一种编码的纠错，检错能力决定于最小码距dmin的值。下面将用几何关系证明纠错，检错能力和最小码距的关系。

为了能检测e个错码，要求最小码距：

(2-3) dmin?e?1纠正t个错误，要求最小码距

(2-4) dmin?2t?1为纠正t个错码，同时检测e个错码，则要求最小码距

dmin?e?t?1 (2-5)

第3章以（7,4）循环码为例在vb下实现了线性分组码的编码和译码。系统循环码的编码问题，可以归结为两个多项式的除法运算，即将xn-km(x)除以生成多项式g(x)得到余式r(x)的运算。

首先根据给定的(n,k)值来选定生成多项式g(x)。即从(xn+1)的因子中选定一个(n-k)次多项式作为g(x)。所有多项式T(x)都能被g(x)整除。根据这条原则可以对给定的信息位进行编码。设m(x)为信息码多项式，其次数小于k。用xn-k 乘m(x)，得到的xn-k m(x)次数必定小于n。用g(x)除xn-k m(x)，得到余式r(x)，r(x)的次数必定小于g(x)的次数，即小于(n-k)。将此余式r(x)加在信息位后作为监督为，即将r(x)和xn-k m(x)相加，得到的多项式必定是一个码多项式。

循环码的译码可按以下三个步骤进行： 1.接收到的y(x)计算伴随式式s(x);

?2.根据伴随式s(x)找到对应的估值错误图样e(x);

????cecc3.计算=y(x)+(x),得到估值码字(x)。若(x)=c(x),则译码正确，否则，若?c(x)≠c(x),则译码错误。

通过对线性分组码中的循环码的编译码编程实现，了解到线性分组码的构成方式是把信息序列分成每k个码元一段，并由这k个码元按一定规则产生r 个校验位，组成长度为n=k+r的码字，用(n，k)表示。信息码元与校验位之间为线性关系。并且知道了线性分组码的编码过程信息码元与校验位之间的线性关系实现起来是十分简单的。

程序运行结果验证了汉明距离与纠错能力的关系：对于码组长度为n、信息码元为k位、监督码元为r＝n－k位的分组码，如果满足2r－1≥n，则有可能构造出纠正一位或一位以上错误的线性码。就像本设计的（7，4）分组码的（n，k）中，n=7，k = 4，r≥3能纠正一位误码，检测到两位误码。

运用vb语言进行编程，可以较明显的知道编码的过程和译码时出现的错误，码字的最小距离是3时，可以纠正一位错误，当输入特定的两位错误时，该码字还可以纠正这两位错误，这种情况在编程结果的命令窗口中可以明显看到。

线性分组码具有编译码简单，封闭性好等特点，采用差错控制编码技术是提高数字通信可靠性的有效方法，是目前较为流行的差错控制编码技术之一。

本文来源：https://www.bwwdw.com/article/qzhw.html