第6章634几种重要的码

第6章信道编码6.1信道编码的概念6.2线性分组码6.3循环码6.4卷积码16.3循环码线性分组码对码的选取做了线性约束，使得计算量变小。译码算法是一种通用译码算法，效率不高。循环码是1957年由一个叫Prange的科学家开始研究。循环码在线性约束的基础上增加了约束条件，是目前研究最为成熟的一类码，大多数有实用价值的纠错码都属于循环码的范畴。2定义定义：对于一个（n，k）线性分组码，若某一码字为C=[c1,c2,...

,cn]该码字向左循环1位后为C(1)=[c2,c3,...

,cn,c1]该码字向左循环i位后为C(i)=[ci+1,ci+2,...

,cn,c1,...

,ci]直至向左循环n－1位为

C(n-1)=[cn,cn-1,...

,c1]若C(i),i=1,2,...,n－1均为码字，则称这个（n，k）线性分组码为循环码。循环码一般也记为（n，k）码，其中n为码字的长度，k为信息位的长度。3循环码的码多项式循环码的特点是，若C是一个码字，那么它的循环移位所形成的新序列同样也是一个码字。循环码是线性分组码的一个重要子类，它具有完整的代数结构，其编码和译码相对比较简单，易于实现。

循环码也是线性分组码，因此可用校验矩阵或生成矩阵来构成。但由于循环码具有循环移位特性，且是自封闭的，故采用多项式的方法描述更为方便。

n长的循环码字C=[c1,c2,...

,cn]可以用一个xn-1次多项式来表示，称为码多项式，表示为

C(x)=c1xn-1

+c2xn-2+...+

cn-1x+cn

4码多项式的运算一元多项式多项式的次数定义为：零次多项式：零多项式：多项式加法：多项式乘法：5码多项式的运算码多项式的模运算和整数的模运算类似：长除法。例如：6码多项式的运算因式和倍式：余式：7码多项式的运算循环码的循环特性可由多项式的模运算来表示

当码字向左移1位，相当于乘以x后的模(xn+1)

运算，即C(1)(x)=xC(x)mod(xn+1)

C(1)(x)=c1xn+c2xn-1+...+cn-1x2+cnxmod(xn+1)C(1)(x)=c2xn-1+c3xn-2+...+cnx+c1如果码字向左移i位，相当于乘以xi后的模(xn+1)运算，即C(i)(x)=xiC(x)mod(xn+1)

C(i)(x)=c1xn+i-1+c2xn+i-2+...+cn-1xi+1+cnximod(xn+1)C(i)(x)=ci+1xn-1+ci+2xn-2+...+ci-1x+ci8例子：例如：其中：CA是线性循环码，CB是非循环线性分组码，而CC是非线性循环码。CA的码字可用多项式：0,x2+x,x+1,x2+1表示。n=3循环码仍是线性码，由循环码构成的线性子空间为循环子空间。将码表示成C或C(x)。9生成多项式g(x)的两个定理定理一

(n,k)循环码C(x)中存在唯一的一个非零的、首一的和最低次数为r(r<n)的码多项式g(x)满足并且，c(x)是码式当且仅当c(x)是g(x)的倍式。10定理一证明唯一性：g0证明:若g0=0，则

即g(x)是另一个更底的码式g’(x)的循环移位，矛盾。码式是g(x)的倍式：

由循环移位特性知：xi

g(x)，i=1,2…n-1-r均是码式。11定理一证明（续）由码的线性分组特性：an-1-rg(x)xn-1-r+…+a1g(x)x+a0g(x)=a(x)g(x)(1)

也是码式。故g(x)的倍式若次数小于n则是码式。反之：f(x)若是码式，则可表示为：

f(x)=a(x)g(x)+r(x)，r(x)的次数小于g(x)的次数，或r(x)=0。若r(x)0，则r(x)＝f(x)－a(x)g(x)也是码式，但r(x)的次数<r，矛盾。所以r(x)＝０=>f(x)是g(x)的倍式。r=n-k证明：由码式必是g(x)的倍式及(1)式知a0，

a1…

an-1-r有n-r个，故可组成2n-r个码式，而(n，k)码的码字个数为2k个且码式必是g(x)的倍式=>n-r=k。证毕12生成多项式定义：由定理一确定的码式g(x)称为（n，k）循环码的生成多项式。循环码由生成多项式g(x)的倍式组成，表示为：定理二

g(x)是(n,k)循环码的生成多项式，当且仅当g(x)是xn-1的r=n–k次因式。证明：必要性

若g(x)是生成多项式，则有：由循环移位定义得，r(x)是g(x)的循环移位码式，所以

故g(x)是xn-1

的因式。13定理二证明（续）充分性：

设n-k=r次g(x)是xn-1的因式，则线性组合：共有２k个多项式。其中：故c(x)的一次循环c(1)(x)均是g(x)的倍式。同理c(x)的任意次循环c(i)(x)均是g(x)的倍式。所以，此２k个多项式组成（n,k）循环码。证毕14例题—构造循环码例题：构造一个（7，3）循环码。解：由于n＝7，对(x7+1)因式分解得：x7+1=(x+1)(x3+x2+1)(x3+x+1)

由于k=3，则n–k=4，因此(7,3)

循环码的两个可选的生成多项式为：g1(x)=(x+1)(x3+x2+1)g2(x)=(x+1)(x3+x+1)15循环码的生成矩阵

由于（n，k）循环码共有2k

个码字，从码组中取出一个前面k－1位都是0的码字，用g(x)

表示，不难看出g(x)的多项式次数为（n－k）。因为xig(x),i=0,1,2,...,k-1均是码字且相互独立，故可用xig(x),i=0,1,2,...,k-1作为生成矩阵G的k行。综上所述，由多项式g(x)可以构成生成多项式矩阵为

16生成矩阵G(n,k)循环码的生成矩阵在g(x)确定后可以表示为G17生成多项式g(x)与循环码的生成由于循环码是线性分组码，因此对于码字C有

C(x)=[m1m2...mk]G(x)式中[m1m2...mk]为k位信息元矢量。

上式表明，循环码的所有码字可由g(x)产生，g(x)称为循环码的生成多项式。在(n，k)循环码中，g(x)是唯一的一个(n－k)次多项式，且次数最低。每个码多项式C(x)都是g(x)的倍式，而每个为g(x)的倍式且次数小于或等于(n－1)的多项式必是一个码多项式。

18校验多项式h(x)循环码的生成多项式g(x)是xn＋1的因式，即

xn＋1=

h(x)g(x)

k次多项式h(x)称为码的校验多项式。设则g(x)和h(x)的系数满足以下关系

19校验方程的获得校验方程可由如下方法得到：20循环码的校验矩阵H和生成矩阵G校验矩阵可以表示为右边矩阵H，满足xn+1=h(x)g(x)。注意到生成矩阵G的行向量为g(x)系数的升幂排列，校验矩阵H的行向量为h(x)系数的降幂排列。如果G为降幂排列，则对应的H为升幂排列。21循环码的伴随多项式假设发送的码多项式C(x)和错误图样多项式e(x)以及接收端接收的码多项式R(x)分别为则对于加性信道有

R(x)=C(x)+e(x)

设g(x)为码的生成多项式，由于码字多项式C(x)能够被g(x)除尽，故有R(x)modg(x)=e(x)modg(x)即：定义伴随多项式为S(x)=e(x)modg(x)22循环码的检纠错根据伴随式的定义，若无错误传输，则S(x)=0，否则S(x)≠0，由此可实现循环码的检错。

因为g(x)的次数为n－k，e(x)的次数为n－1，所以伴随式的最高次数为n－k－1，那么S(x)共有n－k项，故有2n-k种可能的伴随式。若满足2n-k≥n+1，则循环码具有纠错能力。

BCH码是一类重要的循环码，它能够最有效地纠正多个独立错误。BCH码把生成多项式与码的最小距离和纠错能力联系起来，根据所需要的纠错能力，选取适当的g(x)，可以编出非常有效地纠正多个独立错误的BCH码。（略）

23例题—校验多项式和生成矩阵例题：对上例的（7,3）循环码，求其校验多项式和生成矩阵。解：校验多项式为h(x)=(x7+1)/g(x)=(x3+x+1)

生成多项式矩阵为G(x)、生成矩阵为G

24例题—循环码的生成例题：对上例的（7,3）循环码，若输入信息码字为110，求其循环码字。解：信息码字110的码式为m(x)=x2+x

得循环码式为c(x)=m(x)g(x)=(x2+x)(x4+x2+x+1)=x6+x5+x4+x则其循环码字为1110010。25例题—循环码的检错例题：对上例的（7,3）循环码，若接收码字为1100100，判断是否是许用码字。解：接收码字1100100的码式为R(x)=x6+x5+x2

由伴随式S(x)=e(x)modg(x)=R(x)modg(x)S(x)=x6+x5+x2

mod(x4+x2+x+1)=1因为S(x)≠0

，因此该码字不是（7，3）循环码的许用码字。26小结循环码为线性分组码；卷积码为线性非分组码。循环码的特点是具有循环移位特性，因此可以用多项式法描述。本节介绍了循环码利用多项式的编译码方法，包括生成多项式的构造，利用生成多项式生成码字，校验多项式及其与生成多项式的关系、利用伴随多项式译码等。讨论了多项式描述与一般线性分组码的矩阵描述（生成矩阵、校验矩阵、伴随式）间的关系。27第6章信道编码6.1信道编码的概念6.2线性分组码6.3循环码6.4卷积码286.4卷积码在分组码中，任何特定的时间单位内编码器所产生的n个码元的码组，仅取决于该时间单位内k个消息位。存在着另一种码，由编码器在特定的时间内所产生的码元不但取决于这个特定的时间段内进入的信息组，而且也与前面的时间段内的信息组有关，这种码称为卷积码。卷积码的编码可用移位寄存器来完成。卷积码与分组码相似，具有纠正随机错误、突发错误或同时纠正这两类错误的能力。对于许多实际的误差控制，卷积码的性能优于分组码。

29卷积码的概念定义：对于任一给定时刻，编码器的一个输出码字不仅与该时刻的当前输入码字有关，还与编码器的移位寄存器中存贮的前面m个输入信息码字有关。因此卷积码记为(n,k,m)卷积码。其中n为输出的每个码字的位数k为输入的每个信息码字的位数m为移位寄存器中存贮的信息码字个数。

定义m为卷积码的记忆长度，而(m+1)为卷积码的码字约束长度，相应的比特（码元）约束长度为(m+1)n。对L段输入的信息码进行编码，由于初始寄存器为全0，结束时也要额外输入m段无效的全0码字，故共产生L+m段输出码字，所以卷积码的码率为R=Lk/(L+m)n。当L很大时，R=>

k/n，我们一般用R=

k/n表示卷积码的编码效率。卷积码是线性码，但不是分组码，因为卷积码是有记忆的编码。

30(3，2，1)

卷积码举例以下给出了一个(3，2，1)卷积码编码器的原理图。

mi(1)

ci(1)

mi(2)

ci(2)

ci(3)

该编码器由2个移位寄存器构成。编码器每并行输入一个2位信息码字mi=[

mi(1),

mi(2)]，则并行输出一个3位卷积码码字ci=[

ci(1),

ci(2),

ci(3)]=[

mi(1),

mi(2),pi]

其中pi为监督元，有

pi=

mi(1)+

mi(2)+mi-1(1)+

mi-1(2)可见，卷积码当前输出的码字的监督元不仅与当前输入的信息元有关，还与前次输入的2个信息码元有关。

31卷积码的校验关系式下面以（3，1，3）卷积码为例，讨论卷积码的生成矩阵和校验矩阵。把给定的信息序列(m1,m2,m3,...)进行分组，使每个信息组只包含一个信息位。输出的每组码字由三位组成，其中有一个信息位和两个校验位，则输出的码序列为

(m1p11p12,m2p21p22,m3p31p32,...)设校验位与信息位满足以下校验关系：pi1=mi+mi-1+mi-3;pi2=mi+mi-1+mi-2校验关系式表明，当前的校验位与当前的信息位和过去的三个信息位有关，且满足一定的线性关系。某一信息码字会影响4个卷积码字，为此称这个卷积码为约束长度为4个码字的卷积码。

32编码器框图下图为（3，1，3）卷积码的编码器原理框图输入信息序列为m=(m1,m2,m3,...)

输出码字序列为C=(c11c12c13,c21c22c23,c31c32c33,...)C=(m1p11p12,m2p21p22,m3p31p32,...)33生成矩阵G改写校验关系式pi1=mi+mi-1+mi-3

pi2=mi+mi-1+mi-2可以得到m和C满足以下关系

34生成矩阵G（续）改写的校验关系式若写成矩阵形式，则得到m和C间的矩阵关系为

式中的矩阵G称为卷积码的生成矩阵。

35卷积码的描述方法：卷积码的描述方法有两类：1)解析法：包括离散卷积法、生成矩阵法、码多项式法等，多用于编码。2)图形法：包括状态图、树图、栅格图等，常用于译码，特别是网格图。特点：用码多项式法表示卷积码编码器的生成多项式最为方便；栅格图对于分析卷积码的译码算法十分有用；状态图表明卷积码编码器是一种有限状态的马尔科夫过程。36１离散卷积法设在l时段，输入的信息码组为：输出的卷积码组为：移位寄存器中存有前m个时段输入的m个信息码组。由于v(l)与当前时段及此前m个时段的输入码组呈线性关系。若以v(l-i,l)表示l-I时段的输入u(l-i)对v(l)的贡献，则有：v(l)=v(l,l)+v(l-1,l)+v(l-2,l)+…+v(l-m,l)各v(l-i,l)与u(l-i,l)为线性关系，类似线性分组中C=mG。可表示为：37离散卷积法（续）

38２生成矩阵描述法卷积码的矩阵描述：卷积码是线性码，故有生成矩阵和一致校验矩阵。由以上的离散卷积式，展开得：39生成矩阵描述法（续）若将输入的信息码字序列表示为如下的半无限矩阵：

u={u(0),u(1),…,u(m),…,u(l)…}输出卷积码字也表示为如下的半无限矩阵：

v={v(0),v(1),…,,v(m),…,,v(l)…}则生成矩阵与信息码的关系可表示为：其中：为卷积码的生成矩阵。40生成矩阵描述法（续）为一个半无限矩阵，特点：每一个k行都是前一k行右移n列的结果。故中的第一个k行的前(m+1)列完全决定了，将其提出，称为卷积码的基本生成矩阵GB。式中，G0,G1…Gm都是k行n列矩阵，其中第i行表示各组信息码字的第i位对输出v(l)的贡献。41生成矩阵描述法（续）将GB中第i行第j列表示为gi,t，则其中，t可表示为t=j+hm，j=1,2,…,n，h=0,1,2…,n则gi,t＝１表示输入移位寄存器中的第h段的第i位输入比特u(l-t,i)参与第j位输出比特的编码，gi,t＝０则不参与输出编码．由于记忆长度为m，即第i位输入比特u(l-t,i)将对m+1位输出产生作用．这种影响可用如下构造的m+1元组g(i,j)来描述：｛gi,j｝称为卷积码的子生成元或生成序列．(n，k，m)卷积码共有个生成元．42生成矩阵描述法（例子）例子：一个(2,1,2)非系统卷积码如图所示：uu(l-2)/v2(l)/v2v1(l)/v1u(l)/u(l-1)/++原理图u(l)u(l-1)u(l-2)++v(l)电路图43生成矩阵描述法（例子）44系统码的生成矩阵形式以上（3，1，3）卷积码是系统码，其码字的第一位总是信息码字。其生成矩阵可以写成下列形式

式中I

为k×k＝1×1阶单位阵0为k×k＝1×1阶全0方阵，Pi为k×（n－k）＝1×2阶矩阵，有生成矩阵具有如上形式时生成的卷积码为系统码，一般的表示为。

45由生成矩阵产生码序列已知生成矩阵，可以产生所有卷积码字。对以上（3，1，3）码，若输入信息序列为（0100101011…），则对应的码字序列为

对于所生成的码序列，每3个数字组成一个码字，其中包括一个信息位和两个校验位。

46基本一致校验矩阵（3，1，3）卷积码的校验关系式可以表示为

mi-3+mi-1+mi+pi1=0;mi-2+pi2+mi-1+mi=0令C0=(mi-3pi-3,1pi-3,2,mi-2pi-2,1pi-2,2,mi-1pi-1,1pi-1,2,mipi1pi2)

则校验关系式可写成矩阵形式：

其中

称为（3，1，3）卷积码的基本一致校验矩阵。基本一致校验矩阵可以判断第i－3，i－2，i－1，i个输出码字是否码序列中的4个码字，与线性码的一致校验矩阵一样，起着校验作用，但它只对4个码字起校验作用。

47一致校验矩阵令C=(m1p11p12,m2p21p22,m3p31p32,...)由校验关系式展开得如下关系式

48一致校验矩阵（续）校验关系式的展开式写成矩阵形式为系数矩阵为H称为（3，1，3）卷积码的一致校验矩阵。

49校验矩阵的表示式以上校验矩阵可以写为如下表示式：式中PiT为（n－k）×k＝2×1维矩阵0为（n－k）×（n－k）＝2×2维全方阵I

为（n－k）×（n－k）＝2×2维单位矩阵。由卷积码的生成矩阵G和校验矩阵H的表示式可知，G和H有一定的关系，即GHT＝0。对于系统码，由G可以得到H，反之，由H可以得到G。

50３卷积码的多项式描述法记信息码字序列u={u(0),u(1),…u(m),…,u(l),…}对应的多项式为51卷积码的多项式描述法（续）同理，输出的卷积码字序列为v={v(0),v(1),…v(m),…,v(l),…}对应的多项式为52卷积码的多项式描述法（续）线性(n,k,m)卷积码得多项式表达式为：

[v(x)]T=[u(x)]TG(x)G(x)为k×n的多项式矩阵，称为线性卷积码得多项式生成矩阵．G(x)的第i行第j列元素为

g(i,j)(x)=gi,j+gi,n+jx+…+gi,mn+jxm是生成元g(i,j)的多项式表达，故G(x)可写成

G(x)＝[g(i,j)(x)]k×n前例(2,1,2)非系统卷积码中，G(x)＝[1+x+x21+x2]．53４卷积码的状态转移图描述法卷积码和分组码的主要区别在于卷积码的编码要存储m段消息，这些消息随新的输入而改变，并影响当前输出．因此可将这些存储数据作为描述编码器变化的内部状态．对二元(n,k,m)卷积码，存储器（移位寄存器）共有M=km个单元，即共有2M个不同的状态，记为：l时刻的状态用状态矢量表示：下一时刻的状态取决于当前状态和当前输入u(l)，其关系成为状态转移方程：54卷积码的状态转移图描述法(续）当前时刻的输出v(l)取决于当前时刻的输入u(l)和当前状态，其关系称为输出方程：卷积码有2M个可能状态，在某一时刻同时输入一段k位信息码，有2k个可能取值，故每一时刻的状态转移只能有个可能．状态图有两种:开放型和闭合型.如(2,1,2)非系统卷积码：状态向量，共有S0,S1,S2,S3四种状态，其状态变化如下：55卷积码的状态转移图描述法(续）(01)/(0)=(v1v2)/(u)(01)=S1(10)=S2(00)=S0(11)=S3(11)/(1)(01)/(1)(00)/(1)(10)/(0)(00)/(0)(11)/(0)(10)/(1)(2,1,2)码状态转移图（闭合型）56卷积码的状态转移图描述法(续）S0S3S2S1(00/0,11/1)(10/0,01/1)(11/0,00/1)(01/0,10/1)(2,1,2)码状态转移图（开放型）57栅格图（网格图、篱笆图）闭合型的状态转移图直接反映了编码器在任一时刻的工作状态；而开放型的状态转移图则更适合描述特定输入序列的编码过程，但