信息论与编码补充循环码

信息论与编码补充循环码1第一页，共六十页，2022年，8月28日内容提要循环码是线性分组码中一个重要的子类。将介绍循环码的基本概念以及循环码的多项式描述方法；循环码的基本定理及其矩阵描述

；简单的循环码的编译码方法及其实现电路。2第二页，共六十页，2022年，8月28日多项式的引入如果将码字描述成n阶多项式的形式，A(x)=an-1xn-1+an-2xn-2+an-3xn-3+…+a2x2+a1,x+a0，则循环算法就可以描述为L(A(x))=xA(x)mod(xn-1)便于描述：对任何一个多项式D(x)，有D(x)A(x)mod(xn-1)为许用码字，这里并没有限定D(x)的幂次，但可以肯定的一点是不同的D(x)A(x)mod(xn-1)是有限的，其个数由A(x)决定，这也决定了码集的冗余度和纠错能力，什么样的A(x)可以得到什么样的冗余度？哪些A(x)是等价的？复习几个概念:同余、剩余类;群;环;域第三页，共六十页，2022年，8月28日同余和剩余类同余：若整数a和b被同一正整数m除时，有相同的余数，则称a、b关于模m同余，记为剩余类(Residue)：给定正整数m，可将全体整数按余数相同进行分类，可获得m个剩余类，分别用第四页，共六十页，2022年，8月28日群(Group)的定义

设G是一个非空集合，并在G内定义了一种代数运算“。”，若满足：1)封闭性。对任意，恒有2)结合律。对任意，恒有3)G中存在一恒等元e,对任意，使4)对任意，存在a的逆元，使则称G构成一个群。若加法，恒等元用0表示，若为乘法，恒等元称为单位元第五页，共六十页，2022年，8月28日环(Ring)的定义非空集合R中，若定义了两种代数运算加和乘，且满足：

1)集合R在加法运算下构成阿贝尔群

2)乘法有封闭性

3)乘法结合律成立，且加和乘之间有分配律阿贝尔群，又称交换群或可交换群，是这样一类群(G,*)：对任意a，b属于G，满足a*b=b*a。阿贝尔群以挪威数学家尼尔斯·阿贝尔命名。第六页，共六十页，2022年，8月28日子环、理想和主理想子环：若环R中的子集S，在环R中的定义的代数运算也构成环，则称S为R的子环。理想：S是R的一个子环，若S中的元素由某几个元素及其所有可能的倍数构成，则S是一个理想.主理想：若理想中的元素由一个元素的所有倍数及其线性组合生成，则称这个理想为主理想。第七页，共六十页，2022年，8月28日多项式

f(x)=fnxn+fn-1xn-1+…+f1x+f0其中i=0,1,…n，该多项式称为域Fp上的多项式多项式次数degf(x)

系数不为零的x的最高次数称为多项式f(x)的次数首一多项式最高次数的系数为1的多项式有关多项式的几个概念第八页，共六十页，2022年，8月28日

既约多项式设f(x)是次数大于零的多项式，若除常数和常数与本身的乘积以外，再不能被域Fp上的其他多项式整除，则称f(x)为域Fp上的既约多项式

多项式的因式分解问题、根的问题有关多项式的几个概念第九页，共六十页，2022年，8月28日f(x)=fnxn+fn-1xn-1+…+f1x+f0g(x)=gnxn+gn-1xn-1+…+g1x+g0若对所有i,fi=gi,则f(x)=g(x)多项式加法f(x)+g(x)=(fn+

gn)xn+(fn-1

+

gn-1)xn-1+…+(f1

+

g1)x+(f0

+

g0)多项式乘法结论：按上述定义的加法和乘法运算，Fp[x]构成一个具有单位元、无零因子的可换环.多项式的加法和乘法第十页，共六十页，2022年，8月28日定义：以一个Fp上的多项式f(x)=fnxn+fn-1xn-1+…+f1x+f0为模的剩余类全体构成一个多项式剩余类环

Fp上的所有次数小于n-1的多项式构成n次多项式的剩余类全体

剩余类之间的加法和乘法运算规则多项式剩余类环第十一页，共六十页，2022年，8月28日有限域GF(2)上的运算定义12第十二页，共六十页，2022年，8月28日1、GF(2)上的多项式f(x)=x2+1的剩余类全体为：2、GF(2)上的多项式f(x)=x2+x+1的剩余类全体为：对所定义的加法和乘法运算，前者构成剩余类环，后者构成域.结论：若n次首一多项式f(x)在域Fp上既约，则f(x)的剩余类环构成一个有pn个元素的有限域.Examples第十三页，共六十页，2022年，8月28日两个结论多项式环Fp[x]的一切理想均是主理想多项式剩余类环Fp[x]/f(x)中的每一个理想都是主理想。第十四页，共六十页，2022年，8月28日

循环码的概念一．定义

设一个（n，k）线性分组码C，如果它的任一码字的每一次循环移位都还是C的一个码字，则称C是循环码。由于循环码是线性分组码，所有这些具有循环关系的码字的全体构成了n维矢量空间中具有循环特性的k维子空间。15第十五页，共六十页，2022年，8月28日将任一码字中的7个码元排在一个圆周上，则从圆周的任一码元开始，按顺时针方向移动一周，都将构成该码的一个码字。这就是循环码的由来。（见图）16图（7，4）汉明码的码字循环图第二循环第一循环16第十六页，共六十页，2022年，8月28日二．循环码的数学描述1．循环码的特点：（1）它是线性分组码，其数学模型应具有线性特性；（2）具有循环特性。

故循环码的数学模型必须能兼具线性和循环特性→多项式描述。2．线性分组码的多项式描述字：

字多项式

码字：

码字多项式

对于线性分组码C，可以表示成码字多项式构成的集合：

17第十七页，共六十页，2022年，8月28日3．循环特性的表示以前面的（7，3）循环码为例：（任取一码字）移一位移两位移三位?此时：7>n-1=6，超出了n=7的矢量空间。

要求：

则：，即18第十八页，共六十页，2022年，8月28日下面用去除，得余对于上面第三次移位结果，可重新表示如下：

结论：如果将一个循环码的某一非零码字用码多项式表示出来，那么其他的非零码字多项式就可以用这个码字多项式（或码字多项式的和）乘上x的一个幂，再求（xn+1）的余得到。说明：一个码字的移位最多能得到n个码字，因此“循环码字的循环仍是码字”并不意味着循环码集可以从一个码字循环而得，还应包含码字的一些线性组合。19第十九页，共六十页，2022年，8月28日设c＝（cn-1cn-2

…c1c0）是（n，k）循环码的一个码字，则与其对应的多项式

c(x)＝cn-1xn-1＋cn-2xn-2＋…＋c1x＋c0

称为码字c的码字多项式（或码多项式）。如果c＝（cn-1cn-2

…c1c0）是（n，k）循环码的一个码字，则c(1)＝（cn-2…c1c0cn-1）也是该循环码的一个码字。这就是说c(x)＝cn-1xn-1＋cn-2xn-2＋…＋c1x＋c0和c

(1)(x)＝cn-2xn-1＋…＋c1x2＋c0x＋cn-1都是（n，k）循环码的码字多项式。循环码的多项式描述20第二十页，共六十页，2022年，8月28日比较c(x)和c(1)(x)后可得c

(1)(x)＝xc(x),modxn－1以及c(i)(x)＝xic(x)（i＝1,2,…,n－1）,modxn+1定理在以多项式xn+1为模的剩余类全体所构成的n维线性空间Vn中，其一个子空间Vn,k是一个循环子空间（循环码）的充要条件是：Vn,k是一个理想。一个（n，k）循环码的码字多项式都是模xn+1运算下多项式剩余类环中的一个理想，而且一定是一个主理想子环。反之，多项式剩余类环的一个主理想子环也一定生成一个循环码。21第二十一页，共六十页，2022年，8月28日§循环码的基本定理及其矩阵描述

一．循环码的生成多项式1．定义：若g(x)是一个(n-k)次多项式，且是(xn+1)的因式，则由g(x)可以生成一个（n，k）循环码，g(x)称为该循环码的生成多项式。两个结论：（1）GF(2)上的（n，k）循环码中，存在着一个次数为(n-k)的首一码多项式g(x)（首一：多项式最高幂次项系数

gn-k=1

）（gn-k=1）

使得所有码多项式都是g(x)的倍式，即：

且所有小于n次的g(x)的倍式都是码多项式。故循环码完全由它的生成多项式确定。22第二十二页，共六十页，2022年，8月28日（2）（n，k）循环码的生成多项式g(x)一定是(xn+1)的因子，即

或写成相反，如果g(x)是xn+1的n-k次因子，则g(x)一定是（n，k）循环码的生成多项式。生成多项式不唯一。2．（n，k）循环码的构造（1）对(xn+1)做因式分解，找出(n–k)次因式；（2）以该(n–k)次因式为生成多项式g(x)与不高于k–1次信息多项式u(x)相乘，即得到对应消息序列的码多项式。23第二十三页，共六十页，2022年，8月28日【例】一个长度n=7的循环码的构造方法。（1）对x7+1作因式分解

故x7+1有如下因式：

一次因式：

三次因式：

四次因式：

六次因式：

（一个）

（两个）

（一个）

（两个）

24第二十四页，共六十页，2022年，8月28日n–k=1，k=6，生成一种（7，6）循环码；n–k=3，k=4，生成两种（7，4）循环码；n–k=4，k=3，生成两种（7，3）循环码；n–k=6，k=1，生成一种（7，1）循环码；例：要得到一（7，4）循环码，可选n–k=3次多项式1+x2+x3或1+x+x3

为生成多项式：

以g（x）=1+x2+x3为例，（信息位长度为4）

设信息多项式为：

则：循环码编码后的码多项式为：

（2）若以n-k次因式作为生成多项式，可供选择的有25第二十五页，共六十页，2022年，8月28日例：

对于上述（7，4）循环码，有4个信息位，对应有16个信息序列，利用16个信息序列多项式与生成多项式的乘法运算，可得全部（7，4）循环码得16个码字，如表：信息位码字信息位码字信息位码字信息位码字00010010010010000111111010110001011001011001011001011000011000111000101000101001101101100111110010101101000111010111010111010011010011010011010011110011100000000000011011111111循环组1循环组2循环组3循环组426第二十六页，共六十页，2022年，8月28日任何码字的循环移位仍是码字，并非由一个码字循环移位可以得到所有码字，上述（7，4）码的码集由4组码字循环构成。结论：当一个循环码给定其生成多项式g（x）后，根据生成多项式就可以进行编码（但编出的码不一定为系统码）27第二十七页，共六十页，2022年，8月28日二．循环码的生成矩阵（n，k）循环码是n维线性空间一个具有循环特性的k维的子空间，故（n，k）循环码的生成矩阵可用码空间中任一组k个线性无关的码字构成，即k个线性无关的码字构成（n，k）循环码的基底，基底不唯一。如何得到k个线性无关的码字？

方法：当循环码的生成多项式g（x）给定后，可以取g（x）本身加上移位k–1次所得到的k–1码字作为k个基底，即：

→构成基底

若：

则：

28第二十八页，共六十页，2022年，8月28日各多项式对应的矢量分别为：

这k个矢量是线性无关的，且由g（x）循环移位得到，故都是码字，由它们构成一个k×n的矩阵，它们就是循环码的生成矩阵。

29第二十九页，共六十页，2022年，8月28日【例】（7，4）循环码：

当一个循环码的生成矩阵确定后，其编码规则为：

如：30第三十页，共六十页，2022年，8月28日（次数）

设：

则：三．循环码的系统码由上述方法作出的生成矩阵所编出的码不是系统形式，如何得到系统形式的循环码？1．系统循环码的编码：设

用xn–k

和u（x）相乘，再除以g(x)31第三十一页，共六十页，2022年，8月28日a(x)g(x)是g(x)的一个倍式，则它是一个码多项式，对应的码矢量为：码矢量为系统形式的码字，信息位在尾部。※系统码的编码步骤：(1)将k个消息位按升幂排列的次序写成消息多项式u（x）

；

(2)用xn–k

乘以u（x）得到一个次数的多项式；

(3)用生成多项式g（x）除xn–k

u（x）得余b（x）（一致校验元）；

(4)联合b(x)和xn–k

u(x)得到系统码多项式v(x)=b(x)+xn–k

u(x)；

(5)将码多项式转换为码字。32第三十二页，共六十页，2022年，8月28日【例】（7，4）循环码：

求

的系统码字。

，

【解】

，n＝7，k＝4

（1）

（2）（3）（4）33第三十三页，共六十页，2022年，8月28日2．系统码的生成矩阵（1）由生成矩阵做初等行变换，将其变为形式，即为系统形式的生成矩阵（单位阵在后，信息位在尾部）。

，求系统形式的生成矩阵。

【例】（7，4）循环码：

（2）分别求g（x）除的余式（记为），由余式对应的矢量作行矢量构成的k×n-k的分块矩阵P联合k×k的单位阵I就构成系统形式的生成矩阵：34第三十四页，共六十页，2022年，8月28日，求系统形式的生成矩阵。

【例】（7，4）循环码：

35第三十五页，共六十页，2022年，8月28日四．循环码的校验矩阵一般情况下，多项式xn+1可因式分解为xn+1=g(x)·h(x)

g(x)—（n，k）循环码的生成多项式，

h(x)—（n，k）循环码的一致校验多项式，在因式分解中，g(x)和h(x)处于同等地位，既可以用g(x)去生成一个循环码，也可以用h(x)去生成一个循环码。设由g(x)生成的码为C，在由h(x)生成的码就是C的对偶码C⊥。

循环码C的对偶码C⊥的基底由

构成。

36第三十六页，共六十页，2022年，8月28日设

则：将上述矢量按逆序排列作为一个（n-k）×n矩阵的行矢量，则该矩阵就是码C的校验矩阵。37第三十七页，共六十页，2022年，8月28日【例】（7，4）循环码：

则：C⊥的基底（n-k-1=2）

38第三十八页，共六十页，2022年，8月28日※系统形式的校验矩阵

（1）对非系统形式的校验矩阵作初等行变换，变成[In-k，PT]的形式；（2）分别求h（x）除的余式（记为），由余式对应的逆矢量可得到系统形式的校验矩阵：（3）

39第三十九页，共六十页，2022年，8月28日【例】（7，4）循环码：

（1）（2）k=4，n–k–1=2

（3）40第四十页，共六十页，2022年，8月28日循环码的编码

循环码是线性分组码的一个子类，因此循环码可以按一般线性分组码利用常用的组合逻辑电路来实现编码。但对于线性分组码，当其信息位分组长度较长，编码位数较多时，其编码电路非常复杂。由于循环码具有循环特性，其编码器通常用简单的具有反馈连接的移位寄存器就可以实现，大大简化了编码器的复杂度。利用具有反馈连接的移位寄存器实现的循环码编码电路，实际上是多项式运算电路。首先研究多项式运算电路。41第四十一页，共六十页，2022年，8月28日一．G(F2)上的多项式除法电路

设（被除式）（除式）q(x)→商，r(x)→余除法电路：42第四十二页，共六十页，2022年，8月28日（1）除法电路的结构由除式b（x）决定；（2）组成：由r个存储单元组成r级移位寄存器（D0～Dr-1）

bi：常乘器，（bi=1，输出＝输入；bi=0，输出＝0）当bi=1，对应支路连通（直通）；当bi=0，对应支路断开，对应的模2加法器可去掉。

故：电路有r个移位寄存器，最多r+1个常乘器，最多r个模2加法器。说明：43第四十三页，共六十页，2022年，8月28日（3）工作原理简述：①电路清零，被除式系数按高次到低次依次进入电路（ak首先进入），r次移位后，移存器自右至左内容为：（a

k，a

k-1，...，ak-r+1）②第r+1次移位后，输出商的最高次位的系数（a

k

b

r

或ak

b

r-1），并反馈到前面作模2加运算后存入各级寄存器中，以后每次移位输出商的对应次位的系数并反馈回去。③依次类推，经过k+1次移位后，完成整个除法运算，最后输出商常数项系数，此时移存器中的内容就是余式r（x）各次项对应的系数（高位寄存器对应高次项系数）。44第四十四页，共六十页，2022年，8月28日【例】工作过程:(r=3)节拍输入D0D1D2输出清零010000111000201100r次300110r＋1次411111（x）k＋1次5-0011（x0）45第四十五页，共六十页，2022年，8月28日二．循环码编码器1．基于生成多项式g（x）的编码器（n－k级编码器）编码器电路的结构由生成多项式决定，生成多项式g（x）的最高次数为n-k，故编码器有n-k级移存器，故称n-k级编码器。对于循环码的系统编码，首先要得到u(x)xn-k除以g(x)的余式p(x)，再组合成系统码，即：对于除法电路：一方面我们可以得到商，还可以得到余式。对于系统码编码我们可以先输出信息位，再输出余式（校验位）就可以得到系统码，另外由于被除式为u(x)x

n-k，u(x)应从n-k级移存器的最前端输入。46第四十六页，共六十页，2022年，8月28日编码过程：（1）门打开，k接“1”，消息数据uk-1,...u0移入电路，并同时送入信道，一旦k个消息全部移入电路，移存器中的n-k个数据就构成了余式的系数；（2）门关，断开反馈连接，k接“2”；（3）移出移存器中的数据(校验元)，并送入信道，与k个信息位组成码字。47第四十七页，共六十页，2022年，8月28日【例】（7，4）循环码，

若：48第四十八页，共六十页，2022年，8月28日编码过程：（k＝4）节拍输入D0D1D2输出门开，k→1010001111012010113110004－1001门关，k→25－01006－00107－000149第四十九页，共六十页，2022年，8月28日2．基于校验多项式h（x）的编码器（k级编码器）编码器电路的结构由校验多项式决定，生成多项式h(x)的最高次数为k，故编码器有k级移存器，故称

k级编码器。编码器电路编码过程（1）门1打开，门2关闭，k位消息数据u0，u1，...，uk-1移入电路，并同时送入信道；（2）k位消息全部移入，门1关，门2开；（3）以后的每次移位产生一个校验元并送入信道，直到n－k个校验元全部产生并送入信道为止。然后门2关，门1开，准备下一组消息编码；50第五十页，共六十页，2022年，8月28日【例】（7，4）循环码，

k＝4级编码器编码过程

输入节拍D0D1D2D3输出门1开，门2关100000111000102010001310101－411011门1关，门2开－501100－600110－70001051第五十一页，共六十页，2022年，8月28日3．两种编码器的比较（1）基于g（x）的编码器为n－k级编码器，需要n－k级移存器；基于h（x）的编码器为k级编码器，需要k级移存器。（2）当n－k<k时，采用n－k级编码器需要资源少；当n－k>k时，采用k级编码器需要资源少。

52第五十二页，共六十页，2022年，8月28日§8.4循环码译码

一．译码步骤：和线性分组码一样，循环码译码步骤分三步：（1）计算接收多项式r(x)的伴随多项式s(x)；（2）根据s

(x)找出相应错误图样多项式e(x)；（3）将e

(x)和r(x)模2加，得到译码输出v

(x)。二．伴随式计算及错误检测1．伴随式及计算设接收多项式为r(x)，码多项式为v(x)，错误图样多项式为e(x)，则用生成多项式g（x）除r（x），得

（求余运算）

53第五十三页，共六十页，2022年，8月28日【定理】设g(x)是(n，k)系统循环码的生成多项式，接收字多项式为r(x)，对应错误图样为e(x),则

且它们的系数就是该接收字的伴随式。即

可见，循环码的伴随式计算电路就是一个接收多项式r(x)除以生成多项式g（x）的除法电路。电路初始状态为0，当r(x)全部移入后，移存器中的内容为伴随式多项式s(x)。

54第五十四页，共六十页，2022年，8月28日2．伴随式计算电路的性质由于码的循环结构，伴随式有个重要的性质，用定理描述。

【定理】设s(x)是r(