信息论与编码第五讲

信息论与编码第五讲第1页，共103页，2023年，2月20日，星期日主要内容RS编译码卷积编译码第2页，共103页，2023年，2月20日，星期日5.1RS码第3页，共103页，2023年，2月20日，星期日5.1.1RS编码RS码=Reed-Solomoncode=里德-索洛蒙码是BCH码最重要的一个子类。可视为BCH码的特例,是m=1,m0=1时的q元本原BCH码。由于最小多项式的次数不会超过m,当m=1时，2t个连续幂次的根(x-)(x-2)…(x-2t)既是q元扩域GF(q1)上的根多项式，又是q元基域GF(q)上的最小多项式。这种性质给多元BCH码的设计带来了很多的方便，因为我们在前面已经看到，由扩域i次幂根i求基域对应的最小多项式是十分麻烦的事，而RS码的一次根式(x-)就是最小多项式，无需另外再去计算。第4页，共103页，2023年，2月20日，星期日本原RS码具有如下参数：码长：n=q-1校验位：n-k=2t最小距离：dmin=2t+1生成多项式：g(x)=(x-)(x-2)…(x-2t)=an-kxn-k+an-k-1xn-k-1+…+a1x+a0(4-32)

式中，g(x)的各次系数ai取自扩域GF(q1)ai

{0,1,,2,…,q-2}(i=0…n-k) (4-33)由以上参数可见

dmin=2t+1=n-k+1

因此，RS码也是MDC码（极大最小距离）第5页，共103页，2023年，2月20日，星期日注意：GF(q)和GF(q1)含义不同GF(q)是数域，q必须是素数GF(q1)是多项式域，q不一定是素数，工程上，q通常取为2的幂次。GF(8)???01234567表4-9用x3+x+1产生的GF(81)GF(81)多项式3重0000011001010221003+101142+11052++111162+11014+5=1mod83+

4=64的乘法逆元？第6页，共103页，2023年，2月20日，星期日例4.10

试设计一个(7,3,5)本原RS码。解：由于码长n=q-1＝7，可断定码元是8进制的。8进制域元素可以用根的幂次、多项式或3重矢量表示。

若令是本原多项式p(x)=x3+x+1的根，即3=+1，我们可以列出表4-9。因题中要求dm=5∴t=INT[(dm-1)/2]=2这说明生成多项式g(x)有4个连续根、2、3、4。由(式4-32):g(x)=(x-)(x-2)(x-3)(x-4)=[x2-(+2)x+3][x2-(3+4)x+7]=[x2-4x+3][x2-6x+1]

=x4-(6+4)x3+(1+10+3)x2-(4+9)x+

10

=

x4+

3x3+x2+

x+

3

在上式运算中用到了关系式3=+1以及二元扩域的一些运算规则，比如i+

i=0、7=1等。第7页，共103页，2023年，2月20日，星期日此8进制(7,3,5)RS码的生成矩阵为：

G=

通过矩阵行运算可以将它系统化,得G=13

1

3

0

0第①行013

1

3

0第②行0013

1

3

第③行

100

41

45

①+②×3+③×201021

66②+③×300131

3③生成多项式的运算同样可用除法器实现，只是所作的运算是GF(81)域的乘、加运算。第8页，共103页，2023年，2月20日，星期日例：用上面设计的(7,3,5)本原RS码，对一个二元序列（111011010……）实行编码。解：将二元序列化作GF(81)元素，得

m:（111011010）(53)

C=mG=(53)=(5,3,,9+5+4,5+3+,2+2+2,

3+2+4)=(5,

3,

,6,

4,

2,

1)对应的(21,9)二进制衍生码字是：（111011010101110100001）100

41

4501021

6600131

3第9页，共103页，2023年，2月20日，星期日(7,3,5)RS码的t=2,能纠2个差错。衍生为(21,9)二元码后，纠随机差错能力与原(7,3)RS码一样t=2，还能纠长度≤4的任何突发差错。这是因为信道上长度为4的突发差错最多影响到两个二进制3重矢量，相当于两个8进码元出错，仍在t=2范围之内。

(5,

3,

,6,

4,

2,

1)（111,011,010,101,110,100,001）能纠的随机差错

（111,011,010,101,110,100,001）能纠的突发差错（111,011,010,101,110,100,001）（111,011,010,101,110,100,001）不能纠第10页，共103页，2023年，2月20日，星期日

上述这种用二进制码表示的q进制RS码称为该RS码的二进衍生码，衍生指GF(q1)和GF(2)两个域间的映射。可以证明，这种映射是把线性码映射成线性码，映射后的二进衍生码一定是线性分组码，但不一定是循环码。一般来说，一个随机差错能力为t的RS码，其二进衍生码可以纠正小于等于t个随机差错，或者纠正单个长度为b的突发差错，

b≤(t-1)m+1 (4-35)以及其它大量错误图样。

可见，二进衍生码特别适用于纠突发差错，这就是它在无线通信中被广泛采用的原因。

第11页，共103页，2023年，2月20日，星期日

q进制RS码也可以扩展。对于(n,k,d)RS码(n=q-1)，我们可以给每个码字：(C0,C1,…,Cn-1)增加一个全校验位Cn(modq) (4-36)使此扩展RS码字的全体码元C0,C1,…,Cn-1之和为零。可以证明：如果该码字生成多项式g(x)不含(x-1)因子

(或1不是g(x)的根)，那么加了一个全校验位后，能使扩展码的最小距离增加1，即得到(n+1,k,d+1)扩展RS码。比如上例

(7,3,5)RS码扩展出来的(8,3,6)码，其二进衍生码是(24,9)二元码。

第12页，共103页，2023年，2月20日，星期日IBM3370磁盘存储系统采用256进制(255,252)RS码的缩短码，并对应成8比特(1字节)一组的二进制衍生码。该码的基本参数是：q=28=256,n=q-1=255,t=1。

该RS码的码元取自本原多项式P(x)=x8+x4+x3+x2+1生成的扩域GF(28),通过列出类似表4-9那样的对照表，可以找出域元素运算及与二进制8重矢量映射（衍生）关系，其生成多项式是： g(x)=(x--1)(x-1)(x-)使用时，一个扇区的512字节加一个0字节变为513字节，分成3组、每组5133＝171字节，编成3个由(255，252)缩短下来的(174，171)RS码字。实际介质中使用的是（8×174，8×171）RS衍生码。

第13页，共103页，2023年，2月20日，星期日在CD唱片中，采用了两级纠错加交织器的差错控制方案。纠错码用的是q=28=256进制的(255，251)RS码，纠错能力t=2。使用时，将它缩短为(28,24)的外码和(32,28)的内码两种。每秒44.1k采样、每采样16比特的数字音频码流(16×44.1k=1.41Mb/s)被分割成24字节（192bit）的信息组，每字节对应一个256进制的码元，经（28，24）RS编码器编出28字节（224bit）一组的256进制的外码码元。这些码元经4行5列(4×5字节交织器)交织后由(32，28)RS编码器二次编码，输出32字节（256bit）一组内码码元，每码元写入CD盘的一个字节。读出是写入的逆过程，包括RS（32，28）内码译码、去交织和RS（28，24）外码译码。第14页，共103页，2023年，2月20日，星期日

整个过程中，24字节音频信号转为32字节磁盘存储，码率为0.75，要求CD盘的读出速率至少大于1.410.75=1.88Mb/s(没考虑其它任何开销)。具体译码中，当内码遇到一个可检不可纠的差错时将会对外码发送一个信息以提高外码的纠错能力；当差错超过外码的纠错能力时，会对播放系统发送一个信息，将该译码样值删除而改用前、后样值的插值(interpolating)。如果差错太多而超出了插值运算的能力，播放系统将插入一段静音(mute)替代这个突发差错。

第15页，共103页，2023年，2月20日，星期日

在宇航中，RS码和卷积码是一对黄金搭配，用于深空(deepspace)通信中的纠错编码。

深空信道属随机差错信道，用卷积码比较合适。但一旦信道噪声超出卷积码的纠错能力，就将导致突发性质的译码差错，这时用RS码来对付将是最佳选择。

在“探险者号”(Voyager)飞向木星和土星的旅程中，信息就是以RS码为外码、卷积码为内码的级联码实现信道编码的。这种级联码性能优良，已被认为是一种宇航通信标准而称为‘NASA’码，可带来5～7dB的编码增益。第16页，共103页，2023年，2月20日，星期日

探险者Voyager采用了(255,223)RS码，在误比特率Pb=10-6时可获得2.5dB额外编码增益（与仅用卷积码相比）。该RS码每码字的255个码元取值于256进制GF（256）的衍生二进制扩域GF（28），生成扩域元素的本原多项式是P(x)=x8+x4+x3+x2+

1，生成多项式是g(x)=（x-）（x-2）（x-3）…（x-32）式中是本原多项式P(x)的根。由于生成多项式含32个连续幂次的根，可知该码的纠错能力t=16码元（256进制），或长度121(式4-35)的二进制突发差错。第17页，共103页，2023年，2月20日，星期日5.1.2RS码迭代译码

RS码是BCH码的子类，必然存在某些构码特点和能最大程度发挥其纠错潜力的专用译码方法。RS码译码方法主要有：迭代译码和快速译码。RS码是MDC码，码的最小距离d=n-k+1=2t-1，因此g(x)有2t个即d-1个连续幂次的根。RS码可以用类似于BCH码的迭代方式来译码，但必须增加一个步骤：确定了差错码元位置后还要确定差错幅度。第18页，共103页，2023年，2月20日，星期日假设有个差错分布在j1、j2、…、j位上，而差错幅值分别是ej1

、ej2…

ej

，则

E(x)=ej1xj1+ej2

xj2

+…ej

xj (4-80)

（0

j1<j2…<j

n-1）

令xjl=l

（l=1,2…,是差错位置序号）

E(x)=ej11+ej2

2+…ej

(4-81)将2t个连续根依次代入式(4-79)，由于C()=C(2)=…=C(2t)=0，可得2t个伴随式元素：

S1=R()=E()=ej11+ej22+…ejS2=R(2)=E(2)=ej112+ej222+…ej2(4-82)

┇S2t

=R(2t)=E(2t)=ej112t+ej222t+…ej2t第19页，共103页，2023年，2月20日，星期日上式含1、2…

和ej1

、ej2…

ej

共2个未知数，而方程有2t个。只要

t，方程就可解。因此译码方法就是先求出2t个伴随式元素S1、S2、…S2t(P121）

，然后解方程算出所有未知数。由于RS码的根所在的域与码元取值的域相同，根i对应的最小多项式必是一次项(x+i)。令bi是R(x)除以(x+i)的余式，即R(x)=qi(x)(x+i)+bi，由式(4-62)，必有

Si=R(i)=bi(4-83)用图4-22的(x+i)除法电路可方便地完成Si的计算。

R(x)

模q加模q乘

q元寄存器图4-22(x+i)除法电路i第20页，共103页，2023年，2月20日，星期日已知Si后分两步求解2个未知数，先计算差错位置1、2…

，再差错幅值第一步：利用错误位置多项式求出差错位置数1、2…，令(x)=(1-1x)(1-2x)…(1-x)=1+1x+…+x

与式(4-66)相同，可利用伯利坎普迭代解牛顿恒等式，得1、2、…、，进而求出1、2、…、。第21页，共103页，2023年，2月20日，星期日第二步：利用伴随式和的系数求出差错幅值。此时，差错个数和(x)系数1、2、…、，以及差错位置1、2、…均为已知数。

(4-66)(4-84)其中，0=1。定义如下函数

(4-85)(4-86)

第22页，共103页，2023年，2月20日，星期日j(x)是去除了第j个根后(x)的剩余式。上式可写成比较它们同次项系数，或者写作

(4-88)这是解的递推公式，变为已知。第23页，共103页，2023年，2月20日，星期日由式(4-83)，

Si=R(i)=1i+2i+…i=

代入下式

=对照式(4-86)，

(4-89)第24页，共103页，2023年，2月20日，星期日由于j(x)有除了j-1外的-1个根，的值仅当k=j时不为零（不是根），k为其余值时均是0，所以式(4-89)可以简化为单项

==最后得：

(4-91)第25页，共103页，2023年，2月20日，星期日5.2卷积码第26页，共103页，2023年，2月20日，星期日

卷积码是一个有限记忆系统。当信息序列切割成长度k的一个个分组后，分组码单独对各分组编码，而卷积码不仅根据本时刻的分组，而且根据本时刻以前的L个分组共同来决定编码。由于编码过程受L+1个信息分组的制约，因此称L+1为约束长度（ConstraintLength），也有的人直接把L称为约束长度。约束长度是卷积码的一个基本参数，我们常用(n，k，L)来表示某一码长n、信息位k、约束长度L+1的卷积码。约束长度的单位用“分组”而不用“码元”，是因为编码和译码时的约束分组数是一样的，而约束码元数却是不同的，编、译码时的约束码元数分别是(L+1)k与(L+1)n。第27页，共103页，2023年，2月20日，星期日

卷积编码器（线性组合器）ci0c

i1…cin-2cin-1

第i分组第i-1分组第i-2分组……第i-L分组mi0mi1…mik-1mi-10…mi-1k-1m

i-20…m

i-2k-1…mi-L

0mi-L

1…mi-L

k-1输入编码输出Ci图5-1卷积编码示意第28页，共103页，2023年，2月20日，星期日串/

并变换并/

串变换线性组合器m

i0mi-10mi-20…mi-L

0mi1mi-11mi-21…mi-L

1m

ik-1mi-1k-1m

i-2k-1…mi-L

k-1信号入

m

i

编码输出

Ci

┇┇……┇┇图5-2卷积编码器的一般结构

第29页，共103页，2023年，2月20日，星期日

图5-2记忆阵列中的每一存储单元都有一条连线将数据送到线性组合器，但实际上无需每个单元都有连接。这是因为二元域线性组合时的系数只能选“0”或者“1”，选“0”时表示该项在线性组合中不起作用，对应存储单元就不需要连接到线性组合器。从图上看到，每一个码元都是k×(L+1)个数据线性组合的结果，需要有k×(L+1)个系数来描述组合规则，于是每一个码字需用

n×k×(L+1)个系数才能描述。显然，只有将这些系数归纳为矩阵才能理顺它们的关系和便于使用。

第30页，共103页，2023年，2月20日，星期日设（n,k,L）卷积码在时刻i及i之前L个时刻的输入、输出矢量分别是：时刻输入矢量(信息) 输出矢量(码字)i

Mi=(mi0,mi1

,…,mik-1) Ci=(ci0,ci1

,…,cin-1)i-1Mi-1=(mi-10,mi-11…mi-1k-1) Ci-1=(ci-10,ci-11…ci-1n-1)┇

┇

┇i-LMi-L=(mi-L0,mi-L1…mi-Lk-1)Ci-L=(ci-L0,ci-L1…ci-Ln-1)这里,大写字母表示码组，小写字母表示码元，上标表示码字中的码元顺序，下标表示时序。在任意时刻i,卷积码码字的第j个码元是约束长度内所有信息比特的线性组合，写作：第31页，共103页，2023年，2月20日，星期日

j=0,1,2,…n-1

(5-1)式中，{0,1}表示图5-2中第l列（l时刻的信息组,l=0,…,L）、第k行（信息组的第k个码元，k=0,…,K-1）对第j个输出码元的影响。

=0表示该位不参与线性组合，

=1表示该位参与线性组合。

第32页，共103页，2023年，2月20日，星期日例5.1

某二进制(3,1,2)卷积编码器如图5-3所示，写出表达其线性组合关系的全部系数。解：本例为码率R=1/3的卷积码，n=3,k=1,L=2。由编码器电路图，可写出nk(L+1)=9个系数如下：

=1=0=0=1=1=0=1 =1=1

信号 ci0入Mi

输出

ci1C

i

c

i2

图5-3二元(3,1,2)卷积编码器mi0mi-10mi-20输入信息行时延列输出码元行第33页，共103页，2023年，2月20日，星期日例5.2某二进制(3,2,1)卷积编码器如图5-4，写出表达线性组合关系的全部系数。解：本例为码率R=2/3的卷积码,n=3,k=2,L=1。由编码器电路图，可写出nk(L+1)=12个系数如下：

=1,=1,=0,=1=0,=1,=1,=0=1,=1,=1,=0

输入信息行时延列输出码元行

c

i0

信号 Ci

入Mi

ci1输出

c

i2图5-4二进制(3,2,1)卷积编码器mi

0mi-10mi

1m

i-11第34页，共103页，2023年，2月20日，星期日上面两例表明，

从已知的编码电路可以找出对应的系数，反之，已知系数即可画出相应的编码电路。因此，从电路结构角度，(5-1)是很好的表达形式。但是，我们通常需要从另外各种不同的角度去研究卷积码，或侧重于卷积码的物理意义，或强调卷积码的距离特性，或研究编码器的状态变迁等。在不同角度，存在着描述卷积码的不同方法。以下我们将介绍四种卷积码的描述方法：生成矩阵表示法，转移函数矩阵表示法，状态流图法，网格图表示法。

第35页，共103页，2023年，2月20日，星期日5.2.1生成矩阵表示法

由式(5-1)，

CiT

┇┇┇┇

=

=

=

+…第36页，共103页，2023年，2月20日，星期日 … … = … +…+…

┇┇┇┇ … …=

求转置，上式写成：

(5-2)式中，G0、G1、…GL

是k×n矩阵，称作生成子矩阵：

…

Gl

= …l=0,1,…,L(5-3)

┇┇…第37页，共103页，2023年，2月20日，星期日时刻i=0 C0=M0G0

时刻i=1 C1=M0G1+M1G0

时刻i=2 C2=M0G2+M1G1+M2G0┆┆时刻i=L

CL=M0GL+M1GL-1+…+ML-1G1+MLG0

时刻i=L+1 CL+1=M1GL+M2GL-1+…+MLG1+ML+1G0

式(5-2)可写成： (5-4)式(5-4)说明：输出码字Ci是i时刻之前(含i时刻)的信息组(MiMi-1…Mi-L)与生成子矩阵组(G0G1…GL)的卷积，这也就是卷积码名称的来历。(5-2)第38页，共103页，2023年，2月20日，星期日39

令

G0 G1G2…GL00……

gG= G0G1G2…GL0……

=

Dg

(5-6) G0G1G2…GL

0… D2g ┆ ┆

定义g

为基本生成矩阵，定义G为生成矩阵若码字序列是一个从0时刻开始的无限长右边序列，可写成有头无尾的半无限矩阵形式：C=C0,C1,

…，CL,CL+1,…）

G0G1G2…GL0

……=(M0,…,ML,ML+1,…)

G0G1G2…GL0…

(5-5)

G0G1G2…GL0

…

┆第39页，共103页，2023年，2月20日，星期日例5.1(续1)

二进制(3,1,2)卷积编码器如图5-3。如果输入信息流是(101101011100…),求输出码字序列。解：对照例5.1算得的系数及式(5-3)生成子矩阵的定义，可知本题G0=[]=[111]，G1=[ ]=[011]G2=[ ]=[001] 111011001 111011001Ci=(101101011100…)111011001 111011001 ┆=(111,011,110,100,010,110,011,110,100,101,010,001┄)

第40页，共103页，2023年，2月20日，星期日例5.2(续1)

某二进制(3,2,1)卷积编码器如图5-4,若输入信息流是(101101011100…)，求输出码字序列解：对照例5.2算得的系数及式(5-3)生成子矩阵的定义，可知本题G0= =，G1==于是

101111 011100C=(10,11,01,01,11,00…) 101111 011100 101111 011100┄=(101,001,000,111,010,011,…)101011111100第41页，共103页，2023年，2月20日，星期日5.2.2多项式及转移函数矩阵表示法若M(D)=m0+m1D…+mkDk+mk+1Dk+1+…

…

+m2kD2k+m2k+1D2k+1+…，则串/并变换后M0

(D)=m0+mkD+m2kD2+…M1

(D)=m1+mk+1

D+m2k+1D2+…┇

MP(D) CP(D)

M0(D) C0(D) M1(D) C1(D)M(D)┆ C(D)Mk-1(D) Cn-1(D)

图5-5卷积码的转移函数矩阵串/并卷积编码器G(D)并/串第42页，共103页，2023年，2月20日，星期日卷积编码器可视作一个k端口入、n端口出的线性多端口网络，可以用转移函数矩阵来描述其输入、输出间的数量关系。卷积编码器的特殊之处，在于其输入、输出均是无限长多项式，转移函数矩阵元素也是多项式。定义输入、输出多项式矩阵MP(D)、CP(D)为：

M(D)串/并

MP(D)=[M0

(D),M1

(D),…Mk-1

(D)]C

(D)串/并

CP(D)=[C0

(D),C1

(D),…Cn-1

(D)]

这里，MP(D)、CP(D)的下标P表示“并行”。虽然M

(D)和

MP(D)数量上有对应关系，然而在数学上有不同含义，M

(D)是多项式而MP(D)是矩阵第43页，共103页，2023年，2月20日，星期日编码器k路输入和n路输出之间的转移关系为

CP(D)

=MP(D)G

(D) (5-8)G(D)是k×n

转移函数矩阵，

g00(D)g10(D)…gn-10(D)

G

(D)= g01(D)g11(D)…gn-11(D)(5-9)┆┆┆

g0k-1(D)g1k-1(D)…gn-1k-1(D)矩阵G

(D)的第i行第j列元素gji(D)描述了第i个输入支路如何对第j个输出支路产生影响的转移关系，也称子多项式，而第j个输出支路最终输出由全体k个输入支路共同决定。

第44页，共103页，2023年，2月20日，星期日由于约束长度是L+1,任何一个子多项式gji(D)的阶次不会大于L，可用通式表示为

=+…+ (5-10)式(5-10)定义的子多项式gji(D)的各次系数与式(5-1)(5-3)中的系数是一致的，代表第k个输入支路中第l个移存器对第j个输出支路的影响。可见多项式表示法与矩阵表示法本质是一样的，只是多项式表示法通过时延因子D将L+1个生成子矩阵(式5-3)合成一个，而使矩阵元素由“数”变为“多项式”。其优点是能够一目了然地看到并行输入序列和输出序列之间的转移关系，而这正是卷积编码器的主要特征第45页，共103页，2023年，2月20日，星期日由式(5-9)、(5-10)，可知第j个支路的输出是所有输入支路对它影响的总和，即

(5-11)最后，利用并/串变换公式将n个输出多项式合并成一个多项式

(5-12)转移函数矩阵用法归纳如下①输入信息序列经串/并变换得并行的输入多项式②用式(5-11)算出各并行支路的输出多项式③用并/串转换公式(5-12)算出输出多项式C(D)。

第46页，共103页，2023年，2月20日，星期日例5.1(续2)

二进制(3,1,2)卷积编码器如图5-3。如果输入信息流(101101011100…),求输出码字序列。解：本题为一路输入(k=1)、三路输出(n=3)，因此转移函数矩阵是1×3的多项式矩阵。一路输入为M0(D)=1+D2+D3+D5+D7+D8+D9+…根据例5.1中算出的系数及通式(5-10)定义，

g00(D)=+D+D2=1

g10(D)=+D+ D2=1+D

g20(D)=+D+ D2=1+D+D2由式(5-9)，该卷积编码器的转移函数矩阵是：

G(D)=[11+D1+D+D2]第47页，共103页，2023年，2月20日，星期日由式(5-11)C0(D)=M0(D)g00(D)=(1+D2+D3+D5+D7+D8+D9…)1=1+D2+D3+D5+D7+D8+D9…C1(D)=M0(D)g10(D)=(1+D2+D3+D5+D7+D8+…)(1+D)=(1+D)+(D2+D3)+(D3+D4)… =1+D+D2+D4+D5+D6+D7…C2(D)=M0(D)g20(D)=(1+D2+D3+D5+D7+…)(1+D+D2)=(1+D+D2)+(D2+D3+D4)+(D3+D4+D5)+(D5+D6+D7)…=1+D+D6+D9+…它们的系数序列分别是：C0(D):10110101┅

C1(D):11101111┅

C2(D):11000010┅并/串变换，得输出序列

C＝{111,011,110,100,010,110,011,110┅}第48页，共103页，2023年，2月20日，星期日例5.2(续2)

二进制(3,2,1)卷积编码器如图5-4，若输入信息流是(101101011100…)，求输出码字序列。解：本题k=2,n=3,转移函数矩阵是2×3多项式矩阵。输入M0(D)=1+D2+D3+D5+D7+D8+D9+D12+D13+D14…串/并变换后的两个并行输入是：(101101011100…)M(D)=1+D2+D3+D5+D7+D8+D9+…(110010…)M0(D)=1+D+D4+…(

011110…)M1(D)=D+D2+D3+D4+…该卷积编码器的转移函数矩阵是：

G(D)=g00(D)g10(D)g20(D)=1+DD1+D g01(D)g11(D)g21(D)=D11第49页，共103页，2023年，2月20日，星期日C0(D)=M0(D)g00(D)+M1(D)g01(D)=(1+D+D4+…)(1+D)+(D+D2+D3+…)D=1+D3+D6+…C1(D)=M0(D)g10(D)+M1(D)g11(D)=(1+D+D4+…)D+(D+D2+D3+…)1=D3+D4+D5+D6+…C2(D)=M0(D)g20(D)+M1(D)g21(D)=(1+D+D4+…)(1+D)+(D+D2+D3+…)1=1+D+D3+D5+…利用公式(5-12)并/串变换

=[1+(D3)3+(D3)6+…]+[(D3)3+(D3)4+(D3)5+(D3)6…]D+[1+(D3)+(D3)3+(D3)5+…]D2 =1+D2+D5+D9+D10+D11+D13+D16+D17+…其系数正是输出码元序列(101001000111010011┅)。

第50页，共103页，2023年，2月20日，星期日5.2.3卷积码编码矩阵和状态流图生成矩阵、转移函数矩阵重在描述编码器结构，状态流图和网格图则利于揭示卷积码内在特性。状态：编码器记忆阵列的内容，记作Si

比如图5-3卷积编码器，除本时刻输入外还有两个存储器存放前两时刻的输入，其内容组合有00,01,10,11四种可能，该编码器有四种状态。一般地，图5-2的移存器阵列有k行L列共k×L个存储单元，如果这些单元都参与编码，最多可以有2kL个状态。可以认为输出码组Ci

是本时刻输入信息组Mi

和本时刻编码器状态Si

的函数，表示为：Ci=f(Mi,Mi-1,…,Mi-L

)=f(Mi,Si

) (5-13)第51页，共103页，2023年，2月20日，星期日状态Si=h(Mi-1,…,Mi-L+1,Mi-L

),如图5-6所示

图5-6

状态和状态转移串/

并变换线性组合器m

i0mi-10…mi-L

0m

i1mi-11…mi-L

1m

ik-1mi-1k-1…mi-L

k-1┇┇MiSiLMi-1

Mi-L…

时刻i的状态Si向下一时刻状态Si+1的过渡称为状态转移。从图5-6可见，卷积编码器状态的转移不是任意的，因为移存的规则决定了下一个状态必然是：第52页，共103页，2023年，2月20日，星期日Si+1=h(Mi,Mi-1,…,Mi-L+1

)将Si与Si+1作比较，可知Si+1中的(Mi-1,…,Mi-L+1)是在Si中就已确定的，Si+1的可变因素只有Mi即本时刻输入信息组一项。对于二进码，Mi可以有2k种组合，所以状态转移也只能有2k种。于是，同样可以把状态转移写成是本时刻信息组Mi

和本时刻编码器状态Si

的函数

Si+1=h(Mi,Si

) (5-14)式(5-13)、(5-14)的含义是：本时刻输入信息组Mi和编码器状态Si一起决定了编码输出Ci和下一状态Si+1。由于编码器状态和信息组花样都是有限数量的，所以卷积编码器可以看成是一个有限状态机，用输入信息组Mi触发的状态转移图来描述。第53页，共103页，2023年，2月20日，星期日

在式(5-14)决定状态转移的同时，式(5-13)也决定了输出码组，因此确定的状态转移必定伴随着确定的码组。二元码的kL个移存器最多可以有2kL个状态，但是作为状态机触发信号的k重信息分组Mi只能有2k种组合方式，

因此从Si出发，转移到的下一状态只可能是2k种之一，而不是所有的2kL个状态。若某卷积编码器有n个移存器(nkL)，那么编码器的状态数是2n个。我们可以构造一个2n×2n的编码矩阵，其i行j列的元素cij代表从i状态出发转移到下一时刻j状态时发出的码组。如果从i状态出发不可能转移到j状态，则相应的矩阵元素用“.”来表示第54页，共103页，2023年，2月20日，星期日

根据编码矩阵，可以画出卷积编码器的状态流图。以状态为节点、状态转移为分支、伴随转移的输入/输出码元与各分支对应，就不难得到卷积码的状态流图。下面举两个例子：

例5.1(续3)二进制(3,1,2)卷积编码器如图5-3。试分别用编码矩阵和状态流图来描述该码。如果输入信息流是

(101101011100…),求输出码字序列。

第55页，共103页，2023年，2月20日，星期日状态mi-10mi-20S0 0 0S1 0 1S2 1 0S3 1 1

表5-1(a)编码器状态定义

状态输入

m0i=0m0i=1S0 000 111S1 001 110S2 011 100S3 010 101

表5-1(b)不同状态与输入时编出的码字状态输入

m0i=0m0i=1S0 S0 S2S1 S0 S2S2 S1 S3S3 S1 S3

表5-1(c)不同状态Si与输入时的下一状态Si+1信号 ci0入Mi

输出

ci1C

i

c

i2

mi0mi-10mi-20第56页，共103页，2023年，2月20日，星期日由表5-1(a)(b)(c)，可用比表更为简练和直观的编码矩阵来表示该卷积码：编码矩阵

若输入信息序列是1011010111…结果是：S0

1/111S2

0/011

S11/110S2

1/100S30/010

S1……

0/000S01/1110/0011/110S2S10/0111/1000/010S31/101

图5-7(3,1,2)卷积码状态流图第57页，共103页，2023年，2月20日，星期日

例5.2(续3)

某二进制(3,2,1)卷积编码器如图5-4，分别用编码矩阵和状态流图来描述该码。如果输入信息流是(101101011100…),求输出码字序列。解：本题k=2,n=3,有2个移存器、4种状态。由于每次并行输入2比特，即有限状态机触发信号2比特，所以从某一状态出发，下一个状态可以是4种状态之一。由图5-4列出类似于表5-1(a)(b)(c)的表后可得(3,2,1)卷积码的编码矩阵如下。

S0 S1 S2 S3

S0

000 101 011 110 C=S1 111 010 100 001

S2

100 001 111 010

S3

011 110 000 101第58页，共103页，2023年，2月20日，星期日状态流图

00/000

S000/10001/01100/11110/10100/01111/11001/11110/00110/010

S2

S101/10001/00011/01010/11011/001

S311/101

输入序列(10,11,01,01,11,00,┅)2bit/信息组S0

10/101S111/001S301/000S2

01/111S211/010S300/011S0

…对应码字序列为(101,001,000,111,010,011,…)第59页，共103页，2023年，2月20日，星期日5.2.4卷积码的网格图状态流图展示了状态转移去向，但不能记录下状态转移轨迹。网格图可弥补这一缺陷。它可将状态转移展开在时间轴上，使编码全过程跃然纸上，是分析卷积码有力工具。网格图以状态为纵轴，以时间（抽样周期T）为横轴，将平面分割成格状。状态和状态转移的定义画法与流图法一样，也是用一个箭头表示转移，伴随转移的Mi/Ci表示转移发生时的输入信息组/输出码组。所不同的是网格图还体现时间变化，一次转移与下一次转移在图上头尾相联。第60页，共103页，2023年，2月20日，星期日例5.1(续4)用网格图描述图5-3二进制(3,1,2)卷积编码器。若信息序列是(1011010…),求输出码字序列。解：由例5.1(续3)所得的编码矩阵和状态流图，可得1/1100/0110/0101/1010/0001/1000/0000/0000/0000/0000/0000/0001/1111/1100/0011/1110/0101/1000/0010/0111/110S0S1

S2S3网格图编码轨迹图第61页，共103页，2023年，2月20日，星期日当输入5位信息10110时，输出码字和状态转移是

S0

1/111S2

0/011S11/110S2

1/100 S30/010S1如果继续输入第6位信息，信息为0或1时，状态将分别转移到S0或S2，而不可能转移到S1或S3。网格图顶上的一条路径代表输入全0信息/输出全0码字时的路径，这条路径在卷积码分析时常被用作为参考路径。

第62页，共103页，2023年，2月20日，星期日例5.2(续4)

二进制(3,2,1)卷积编码器如图5-4，用网格图描述该码。对于输入(101101011100…),求输出码字序列。解：由例5-2(续3)结果，可得网格图如下

10/010001/10011/01010/10100/00001/11101/01111/11000/11111/00100/10010/00110/11001/00011/10100/01110/10111/00101/00001/11111/01000/011网格图编码轨迹图第63页，共103页，2023年，2月20日，星期日卷积码的生成矩阵、转移函数矩阵、状态流图和网格图从不同侧面描述卷积码。生成矩阵和转移函数矩阵属同一大类，它们沿用了分组码的描述方法，建立了代数与编码器的关联。特点是物理意义清楚，代数量（多项式系数，矩阵元素）与编码电路连接线之间的对应关系十分明确，非常利于用VHDL等硬件描述语言来表达以及用FPGA、DSP等来物理实现。状态流图和网格图属于另外一类表示法，状态流图借助信号流图等图论工具或理论来分析卷积码特性，网格图则适合用于计算机的穷尽搜索上，它使状态能在时域展开，所得状态轨迹是研究差错事件、卷积码距离特性以及维特比最大似然序列译码有力工具。

第64页，共103页，2023年，2月20日，星期日5.3

卷积码的特性对于有限长信息序列如M个k重，当M个分组全部输入编码器后，虽然再没有新的信息分组输入，但由于编码器内L组（约束长度）移存器的记忆效应，编码器将继续输出L个码字才能将记忆阵列中的内容完全移出，这就导致卷积码码率由R=k/n降低为。将码率下降的相对值定义为码率损失系数：码率损失系数= (5-15)第65页，共103页，2023年，2月20日，星期日

显然，M相对于L越大则效率损失越小。当信息序列很长而使M>>L时，效率损失趋于0因而可忽略不计，每一个k位信息组产生一个n位码字，卷积编码码率与分组码码率一样为R=k/n。相反，M相对于L越小则效率损失越大，当M=1时码率损失系数接近1。由此可见，卷积码的适用对象是电路交换的连续信息流，或包交换的“流媒体”，或复用级的信息流，而不适合短突发、目的地分散的用户端包交换纠错编码。第66页，共103页，2023年，2月20日，星期日5.3.1

卷积码的距离特性卷积码的性能取决于卷积码距离特性和译码算法。其中，距离特性是卷积码本身的属性，它决定了该码的纠错能力，而译码方法只是研究如何将这种潜在的纠错能力转化为现实的纠错能力。表述距离特性的最好方法是利用网格图。若序列C‘、C”是从同一时刻（不妨称为0时刻）由零状态出发的两个不同的码字序列，它们所对应的信息序列分别是M’和M”，且M‘M”。对于二元码，序列距离d(C’,C”)指汉明距离，等于C‘、C”的对应项逐一模2加后所得的序列C的重量，也等于序列C和全零序列0的距离或序列C的重量。d(C',C”)=W(C'C”)=W(C0)=d(C,0)(5-16)第67页，共103页，2023年，2月20日，星期日

式(5-16)默认：两码字序列之和仍是码字序列，这样任意两码字序列间最小距离才能等效于全零序列与某非全零序列的距离。全零序列在网格图上表现为保持在零状态的一条横线，故两序列的最小距离也就是非全零路径与全零状态路径距离最小者。序列距离还与序列长度有关，同一序列对在不同长度比较时显然距离也不同。将长度l的任意两序列间的最小距离定义为l阶列距离。以长度l为变量的列距离特性称之为列距离函数，用dc(l)来表示：

dc(l)min{d([C']l,[C”]l):[M']0[M”]0}(5-17)＝第68页，共103页，2023年，2月20日，星期日所谓[M‘]0[M”]0即“不同”的两序列，在网格图上的表现就是从零时刻起两序列轨迹从零状态分道扬镳形成分叉点。由式(5-16)，式(5-17)可改写为dc(l)＝min{W([C']l＋[C”]l):