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

2024/6/231

Thestudycertainlyisnotthelifecomplete.But,sincecontinuallylifepartof-studiesalsoareunabletoconquer,whatbutalsocanmake?2024/6/2326.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循环码2024/6/233(1)循环码的性质循环码是线性分组码的一个重要子类；循环码具有优良的代数结构。在结构上，它的循环性使得更容易用数学语言来描述；在性能上，具有明确的纠、检错能力，对于给定的码长n和信息位数k，已提出的各类循环码都有确定的纠、检错能力的理论计算值；在实现上，编码和译码都可以通过简单的反馈移位寄存器来完成,并可使用多种简单而有效的译码方法。循环码是研究最深入、理论最成熟、应用最广泛的一类线性分组码。6.3.1循环码的多项式描述2024/6/234(2)循环码的定义循环码：如果(n,k)线性分组码的任意码矢C=(Cn－1,Cn－2,…,C0)

的i次循环移位，所得矢量C(i)=(Cn－1－i,Cn－2－i,…,C0,Cn－1,…,Cn－i)

仍是一个码矢，则称此线性码为(n,k)循环码。6.3.1循环码的多项式描述2024/6/235循环码举例例分析二进制码组{000,110,101,011},{00000,01111,10100,11011},{0000,1101,0111,1011,1110}是不是循环码。 解看码组符不符合线性和循环的条件。对于码组{000,110,101,011}，它既是线性码又是循环码。事实上，它是对00,01,10,11进行偶校验得到的码，是(3,2)循环码。对于码组{00000,01111,10100,11011}，它是线性码但不是循环码。事实上，它是对消息序列00,01,10,11进行编码得到的线性分组码(5,2)码。对于码组{0000,1101,0111,1011,1110}，它尽管满足循环性但由于不是线性码，故也不是循环码。6.3.1循环码的多项式描述2024/6/236(3)码多项式码多项式：为了运算的方便，将码矢的各分量作为多项式的系数，把码矢表示成多项式，称为码多项式。其一般表示式为C(x)=Cn－1xn－1+Cn－2xn－2+…+C0码多项式i次循环移位的表示方法记码多项式C(x)的一次左移循环为C(1)(x)

，i次左移循环为C(i)(x)6.3.1循环码的多项式描述2024/6/237码多项式的模(xn+1)运算0和1两个元素模2运算下构成域。6.3.1循环码的多项式描述2024/6/238若p为素数，则整数全体在模p运算下的剩余类全体在模p下构成域。以p=3为模的剩余类全体模3运算的规则如下：6.3.1循环码的多项式描述2024/6/239码矢C循环i次所得码矢的码多项式

C(x)乘以x，再除以(xn+1)，得6.3.1循环码的多项式描述2024/6/2310上式表明：码矢循环一次的码多项式C(1)(x)是原码多项式C(x)乘以x除以(xn+1)的余式。写作因此，

C(x)的i次循环移位C(i)(x)是C(x)乘以xi除以(xn+1)的余式，即结论：循环码码矢的i次循环移位等效于将码多项式乘xi后再模(xn+1)。6.3.1循环码的多项式描述2024/6/2311(4)举例：(7,3)循环码，可由任一个码矢，比如(0011101)经过循环移位，得到其它6个非0码矢；也可由相应的码多项式(x4+x3+x2+1)，乘以xi(i=1,2,…,6)，再模(x7+1)运算得到其它6个非0码多项式。移位过程和相应的多项式运算如表6.3.1所示。6.3.1循环码的多项式描述2024/6/23126.3.1循环码的多项式描述2024/6/2313(1)循环码的生成矩阵根据循环码的循环特性，可由一个码字的循环移位得到其它的非0码字。在(n,k)循环码的2k个码字中，取前(k－1)位皆为0的码字g(x)（其次数r=n－k），再经(k－1)次循环移位，共得到k个码字：g(x),xg(x),…,xk－1g(x)

6.3.2循环码的生成多项式

这k个码字显然是相互独立的，可作为码生成矩阵的k行，于是得到循环码的生成矩阵G(x)2024/6/2314(2)循环码的生成多项式码的生成矩阵一旦确定，码就确定了；这就说明：(n,k)循环码可由它的一个(n－k)次码多项式g(x)来确定；所以说g(x)生成了(n,k)循环码，因此称g(x)为码的生成多项式。6.3.2循环码的生成多项式2024/6/2315(3)生成多项式和码多项式的关系定理6.3.1：在(n,k)循环码中，生成多项式g(x)是惟一的(n－k)次码多项式，且次数是最低的。

[证明]：先证在(n,k)循环码系统中存在(n－k)次码多项式。因为在2k个信息组中，有一个信息组为，它的对应码多项式的次数为n－1－(k－1)=n－k(n－k)次码多项式是最低次码多项式。若g(x)不是最低次码多项式，那么设更低次的码多项式为g’(x)，其次数为(n－k－1)。g’(x)的前面k位为0，即k个信息位全为0，而监督位不为0，这对线性码来说是不可能的，因此g(x)是最低次的码多项式，即gn－k必为1。6.3.2循环码的生成多项式2024/6/2316g0=1，否则经(n－1)次左移循环后将得到低于(n－k)

次的码多项式。g(x)是惟一的(n－k)

次多项式。如果存在另一个(n－k)次码多项式，设为g’’(x)，根据线性码的封闭性，则g(x)+g’’(x)也必为一个码多项式。由于g(x)和g’’(x)的次数相同，它们的和式的(n－k)

次项系数为0，那么g(x)+g’’(x)是一个次数低于(n－k)

次的码多项式，前面已证明g(x)的次数是最低的，因此g’’(x)不能存在，所以g(x)是惟一的(n－k)

次码多项式。6.3.2循环码的生成多项式2024/6/2317令是(n,k)循环码C中最低次数的非零码多项式，则常数项g0必为1。证明设g0=0则将g(x)循环右移1位或循环左移n–1位，记为有它是一个次数小于r的非零码多项式，与g(x)是最低次数的非零码多项式的假设相矛盾，故g0必为1。因此证毕。 （实质上是论证了生成多项式必有常数项）6.3.2循环码的生成多项式2024/6/2318定理6.3.2：在(n,k)循环码中，每个码多项式C(x)都是g(x)的倍式；而每个为g(x)倍式且次数小于或等于(n－1)的多项式，必是一个码多项式。

[证明]：设m=(mk－1,mk－2,…,m0)为任一信息组，G(x)为该(n,k)循环码的生成矩阵，则相应的码多项式为6.3.2循环码的生成多项式Here2024/6/2319上式表明：循环码的任一码多项式为g(x)的倍式。显然，凡是为

g(x)的倍式且次数小于或等于(n－1)的多项式，一定能分解成上式的形式，因而它就是信息多项式

m(x)=(mk－1xk－1+mk－2xk－2+…+m0)并由生成矩阵G(x)所生成的码多项式。定理6.3.3(定理6.3.2的逆定理)：在一个(n,k)线性码中，如果全部码多项式都是最低次的(n－k)次码多项式的倍式，则此线性码为一个(n,k)循环码。

注：一般说来，这种循环码仍具有把(n,k)线性码码中任一非0码矢循环移位必为一码矢的循环特性，但从一个非0码矢出发，进行循环移位，就未必能得到码的所有非0码矢了。所以称这种循环码为推广循环码。6.3.2循环码的生成多项式2024/6/2320码字循环关系图单纯循环码的码字循环图：(7,3)循环码6.3.2循环码的生成多项式2024/6/2321推广循环码的码字循环图：(6,3)循环码6.3.2循环码的生成多项式2024/6/2322(4)如何寻找一个合适的生成多项式由下面式子可知：循环码的多项式等于信息多项式乘以生成多项式。

这说明：对一个循环码只要生成多项式一旦确定，码就确定了，编码问题就解决了。

所以：作一循环码的关键，就在于寻找一个适当的生成多项式。6.3.2循环码的生成多项式2024/6/2323定理6.3.4：(n,k)循环码的生成多项式g(x)是(xn+1)的因式，即xn+1=h(x)

g(x)。

[证明]：由于xkg(x)是n次多项式，可表示为xkg(x)=1

(xn+1)+g(k)(x)(6.3.1)

式中g(k)(x)是码多项式g(x)乘以xk除以(xn+1)的余式。根据循环码的移位关系，它是g(x)循环移位k次所得到的码多项式，因而g(k)(x)是g(x)的倍式。设g(k)(x)=m(x)g(x)代入式(6.3.1)得(xn+1)=[xk+m(x)]g(x)上式表明：g(x)是(xn+1)的因式。6.3.2循环码的生成多项式2024/6/2324定理6.3.5：若g(x)是一个(n－k)次多项式，且为(xn+1)的因式，则g(x)生成一个(n,k)循环码。

[证明]：由于

g(x)是一个(n－k)

次多项式，且为(xn+1)的因式，所以

g(x),x

g(x),…,xk－1

g(x)是k个次数小于n，并且彼此独立的多项式；6.3.2循环码的生成多项式

将此多项式用作码的生成矩阵的k行，得到(n,k)线性码的生成矩阵；2024/6/2325设信息组m=(mk－1,mk－2,…,m0)，则相应的码字为

C(x)=m

G(x)=(mk－1xk－1+mk－21xk－2+…+m0)

g(x)=m(x)

g(x)C(x)≤n－1；m(x)是2k个信息多项式的表示式；所以C(x)即为相应2k个码多项式的表示式。因此，g(x)生成一个(n,k)线性码。C(x)是(n－k)次多项式g(x)的倍式，所以g(x)生成一个(n,k)循环码。

结论：当求作一个(n,k)循环码时，只要分解多项式(xn+1)，从中取出(n－k)次因式作生成多项式即可。6.3.2循环码的生成多项式2024/6/2326举例：求(7,3)循环码的生成多项式。[解]：分解多项式xn+1，取其4次因式作生成多项式x7+1=(x+1)(x3+x2+1)(x3+x+1)可将一次和任一个三次因式的乘积作为生成多项式，因而可取

g1(x)=(x+1)(x3+x2+1)=x4+x2+x+1

或g2(x)=(x+1)(x3+x+1)=x4+x3+x2+16.3.2循环码的生成多项式2024/6/2327(n,k)循环码的生成多项式g(x)在代数结构上是xn+1的一个(n–k)次因式。但由定理(6.3.5)可见，xn+1可能有不止一个(n–k)次因式。其含义是，对于一个(n,k)循环码可能会有多个生成多项式。因此分析这些生成多项式所生成的码的性能，从而选择好的生成多项式，是研究循环码的主要目的之一，尤其当n较大时，需用计算机搜索的方法来寻找好的生成多项式，通常称为搜索好码。6.3.2循环码的生成多项式2024/6/2328

例试构造n=10和n=15时可能的二进制循环码。解对各种可能的k值求出其对应的生成多项式。对于n=10的情况，求k=1,2,…,8,9时对应的生成多项式，就是求x10+1的各(10–k)次因式；对于n=15的情况，求k=1,2,…,13,14时对应的生成多项式，就是求x15+1的各(15–k)次因式。两种情况的计算结果如下表所示，表中给出了g(x)以及对应的汉明距离，其中g(x)用其系数表示，例如110101代表x5+x4+x2+1。6.3.2循环码的生成多项式2024/6/23296.3.2循环码的生成多项式2024/6/2330由上表可见，x10+1不含有(10,3)、(10,7)循环码，因为它没有7次和3次因式；而对于k=5,6,8,9，其距离都是2，故它们的纠、检错能力是一样的，但编码效率显然大不一样，说明同是循环码，性能却有所不同，这就提出了所谓搜索好码的问题。n=15情况，

x15+1有[1,14]区间的各次因式，但有超过一半的k值有2个同次因式，对应的情况就可以构造出2个循环码，但注意到对应的dmin值就会发现，有的情况却不相等，这说明注入同样的冗余度得到的效果却不一样，同样说明寻找性能好的循环码的重要性。6.3.2循环码的生成多项式2024/6/2331通过实例可以发现，随着n的增大，同次生成多项式的个数将会增加，因此搜索好码具有重要的意义。给定n，对于不同的k，寻找g(x)，计算dmin及重量分布，可以构造出符合需要的循环码，循环码中的许多好码都是这么发现的。直到n=99的循环码，已有表格。6.3.2循环码的生成多项式2024/6/2332(5)循环码的监督多项式和监督矩阵循环码的监督多项式：设g(x)为(n,k)循环码的生成多项式，必为(xn+1)的因式，则有xn+1=h(x)

g(x)，式中h(x)为k次多项式，称为(n,k)循环码的监督多项式。(n,k)循环码也可由其监督多项式完全确定。举例：(7,3)循环码x7+1=(x3+x+1)(x4+x2+x+1)4次多项式为生成多项式g(x)=x4+x2+x+1=g4x4+g3x3+g2x2+g1x+g03次多项式是监督多项式h(x)=x3+x+1=h3x3+h2x2+h1x+h06.3.2循环码的生成多项式2024/6/2333循环码的监督矩阵由等式x7+1=h(x)

g(x)两端同次项系数相等得将上面的方程组写成矩阵形式6.3.2循环码的生成多项式2024/6/2334上式中，列阵的元素是生成多项式g(x)的系数，是一个码字，那么第一个矩阵则为(7,3)循环码的监督矩阵，即6.3.2循环码的生成多项式2024/6/2335循环码监督矩阵的构成由式(6.3.2)可见，监督矩阵的第一行是码的监督多项式h(x)的系数的反序排列，第二、三、四行是第一行的移位；可用监督多项式的系数来构成监督矩阵6.3.2循环码的生成多项式2024/6/2336(n,k)循环码的监督矩阵对偶问题如果xn+1=h(x)

g(x)，其中g(x)为(n－k)

次多项式，以g(x)为生成多项式，则生成一个(n,k)循环码；以h(x)为生成多项式，则生成(n,n－k)循环码；这两个循环码互为对偶码。6.3.2循环码的生成多项式2024/6/2337(1)系统循环码构成设信息向量

m=(mk－1,mk－2,…,m0)信息多项式

m(x)=mk－1xk－1+mk－2xk－2+…+m0

码多项式的高次幂部分等于m(x)，即

C(x)=cn－1xn－1+…+cn－kxn－k+cn－k－1xn－k－1…+c1x+c0

=xn－km(x)+q(x)q(x)的次数<n－k校验位多项式

q(x)由于码多项式是生成多项式的倍式，所以C(x)=xn－km(x)+q(x)=a(x)g(x)≡0(modg(x))q(x)=C(x)+xn－km(x)≡xn－km(x)(modg(x))因此，循环码的系统码形式为C(x)=xn－km(x)+

(xn－km(x)modg(x))6.3.3系统循环码2024/6/2338系统循环码构造过程步骤信息多项式乘xn－k：xn－km(x)对xn－km(x)求余式：q(x)≡xn－km(x)(modg(x))求码多项式：C(x)=xn－km(x)+(xn－km(x)modg(x))=xn－km(x)+q(x)对所有的i=0,1,2,…,k－1，用生成多项式g(x)除xn－k+i（即令m(x)为单项式）xn－k+i=a(x)g(x)+qi(x)，qi(x)的次数<n－k因此xn-k+i+qi(x)是g(x)的倍式，即码多项式Ci(x)=xn－k+i+qi(x)可见：Ci(x)对应的向量Ci，i=0,1,2,…,k－1是线性无关的，从而得到循环码系统码的生成矩阵Gs为6.3.3系统循环码2024/6/23396.3.3系统循环码2024/6/2340(2)举例[例6.3.5]：(7,4)循环码g(x)=x3+x+1，x6=(x3+x2+1)g(x)+(x2+1)

q3(x)=(x2+1)C3(x)=x6+x2+1x5=(x2+1)g(x)+(x2+x+1)

q2(x)=(x2+x+1)C2(x)=x5+x2+x+1x4=xg(x)+(x2+x)q1(x)=(x2+x)C1(x)=x4+x2+xx3=g(x)+(x+1)

q0(x)=(x+1)C0(x)=x3+x+16.3.3系统循环码2024/6/2341(1)多项式加法电路多项式a(x)=anxn+an－1xn－1+…+a1x+a0表示的是时间序列a=(an,an－1,…,a1,a0)，因此多项式的计算表现为对时间序列的操作；6.3.4多项式运算电路

对二进制多项式系数的基本操作为模2加和模2乘；电路图运算符号的意义：2024/6/2342a(x)与b(x)的相加电路。如图6.3.3。6.3.4多项式运算电路2024/6/2343(2)多项式乘法电路多项式乘以x等价为时间序列a

延迟一位；多项式与多项式的乘等价为a的不同位移后的相加：a(x)g(x)=a(x)(g1(x)+g2(x))=a(x)g1(x)+a(x)g2(x)多项式乘法电路如图6.3.4。假设多项式的低位在前，电路中所有寄存器初态为0。6.3.4多项式运算电路2024/6/2344图6.3.5表示了多项式乘法电路。6.3.4多项式运算电路2024/6/2345(3)多项式除法电路当g(x)=1,多项式a(x)模g(x)的余式为0,电路如图6.3.7所示。6.3.4多项式运算电路2024/6/2346当g(x)是单项式g(x)=xk，a(x)模g(x)的余式的次数小于k，进入电路的输入顺序为an,an－1,…,a1,a0。a(x)≡ak－1xk－1+ak－2xk－2+…+a1x+a0(modxk)

运算电路如图6.3.8所示。6.3.4多项式运算电路2024/6/2347由于xk≡1

mod(x+1),i=0,1,2,…。若a(x)的次数为n，则a(x)mod(x+1)≡an－1+an－2+…+a1+a0=q0(mod2)

运算电路如图6.3.9所示。6.3.4多项式运算电路2024/6/2348同样由长除法得运算电路如图6.3.10所示。6.3.4多项式运算电路2024/6/2349类似地：多项式a(x)模(x2+x+1)的运算电路如图6.3.11所示。6.3.4多项式运算电路2024/6/2350一般的多项式模g(x)=grxr+gr－1xr－1+…+g1x+g0