第五章卷积码码课件

通信工程系移动通信教研室信道编码第五章 卷积码9/21/20232信道编码卷积码的基本概念卷积码的矩阵描述与编码卷积码的状态图与格图描述卷积码的概率译码第五章 卷积码9/21/20233信道编码重点掌握：卷积码的基本概念与编码方法卷积码的格图描述重点理解：卷积码的维特比译码算法第五章 卷积码9/23/20234信道编码卷积码的基本概念卷积码的矩阵描述与编码卷积码的状态图与格图描述卷积码的概率译码5.1卷积码的基本概念9/23/20235信道编码卷积码的提出与发展1954年，埃里斯（Elias）提出卷积码的概念，它是完全不同于线性分组码的一个码类。1961年，提出卷积码的序列译码方法。1963年，梅西（Massey）提出了卷积码的代数译码方法—门限译码。1967年，维特比（Vitebi）提出了卷积码的最大似然译码方法，称为维特比算法。直到现在，仍是应用最为广泛的译码算法。5.1卷积码的基本概念一个简单的卷积码编码例子初始状态：00设输入m=101100……则输出与输入的关系为：列9/23/20236信道编码输入：1011000…码序状态码：分0组0100110110100…输出：11010010101100…编码码序存列储信息分组5.1卷积码的基本概念9/23/20237信道编码说明：可以将卷积码的编码器看作一个由k0个输入端和n0个输出端组成的时序网络，即每输入k0个信息元，输出n0个码元组成的码分组(子码)。例子中k0=1,n0=2；编码器某个时刻的输出不仅与该时刻编码器的输入有关，而且与以前若干时刻(由编码存储单元的个数决定)的输

入编码器的信息有关。卷积码的码字（码序列）可以看作是由无限多个码分组组成的码向量，即码字是一个无限维向量。5.1卷积码的基本概念9/23/20238信道编码几个基本概念信息分组与码分组(子码)：k0，n0k0:每个时刻输入编码器信息组中的信息元个数；n0

:每个时刻编码器输出一个子码中码元的个数。系统码与非系统码：如果在n0位长的码分组中，前k0位是原输入的信息元，则该卷积码为系统码，否则称为非系统码。编码效率：R=k0/n05.1卷积码的基本概念9/23/20239信道编码几个基本概念编码存储m

：表示编码过程中，输入的信息组在编码器中需要存贮的单位时间。前面例子中，m=2编码约束度N=m+1

：表示编码过程中相互约束的码分组个数。编码约束长度n0N：表示编码过程中相互约束的码元数目。参数m,N,k0,n0反映了编码器的复杂度卷积码通常记为：(n0,k0,m)卷积码或N(n0,k0)5.1卷积码的基本概念9/23/202310信道编码卷积码的特点：当前码分组输出不仅与当前信息分组输入有关，还与前面m个信息分组有关。在相同码率、相同译码复杂性条件下，卷积码的性能要好于分组码。卷积码仍是线性码，满足线性叠加关系。通常情况下，非系统码的性能好于系统码。尚没有完善的数学工具有效地分析其结构和性能，须借助计算机搜索来寻找好码。第五章 卷积码9/23/202311信道编码卷积码的基本概念卷积码的矩阵描述与编码卷积码的状态图与格图描述卷积码的概率译码5.2卷积码的矩阵描述与编码9/23/202312信道编码卷积码的特点：当前码分组输出不仅与当前信息分组输入有关，还与前面m个信息分组有关。在相同码率、相同译码复杂性条件下，卷积码的性能要好于分组码。卷积码仍是线性码，满足线性叠加关系。通常情况下，非系统码的性能好于系统码。尚没有完善的数学工具有效地分析其结构和性能，须借助计算机搜索来寻找好码。5.2卷积码的矩阵描述与编码9/23/202313信道编码卷积码的生成矩阵与编码系统卷积码的校验矩阵初始截短码卷积码的距离特性5.2卷积码的矩阵描述与编码(n0,1,m)卷积码的生成矩阵为便于理解，仍以(2,1,2)卷积码为例设：m=(m0,m1,m2,…)C=(C0,C1,C2,…)，其中Ci=(ci

,ci

)(1)

(2)若输入信息序列和编码器相应输出序列为：m’

=(100…)m’’=(0100..)m’’’=(0010...)C’

=(11

01

11…)C’’=(00

11

01

11…)C’’’=(00

00

11

01

11…)9/23/202314信道编码5.2卷积码的矩阵描述与编码(n0,1,m)卷积码的生成矩阵为便于理解，仍以(2,1,2)卷积码为例设：m=(m0,m1,m2,…)C=(C0,C1,C2,…)，其中Ci=(ci

,ci

)(1)

(2)若输入信息序列分别为m=m’+m’’+m’’’

=(100…)+(0100..)+(0010...)=(1110…)编码器相应输出的码序列为：C=C’+C’’+C’’=(11

01

11…)+(00

11

01

11…)+(00

00

11

01

11…)=(11

10

01

10

11…)9/23/202315信道编码5.2卷积码的矩阵描述与编码(n0,1,m)卷积码的生成矩阵为便于理解，仍以(2,1,2)卷积码为例设：m=(m0,m1,m2,…)C=(C0,C1,C2,…)，其中Ci=(ci

,ci

)(1)

(2)若输入信息序列分别为m=m’+m’’+m’’’

=(100…)+(0100..)+(0010...)=(1110…)编码器相应输出的码序列为：C=mG∞=(1110…) 11

01

11…00

11

01

11…00

00

11

01

11…169/23/2023

信道编码

…

…

…5.2卷积码的矩阵描述与编码(n0,1,m)卷积码的生成矩阵为便于理解，仍以(2,1,2)卷积码为例设：m=(m0,m1,m2,…)0

1

2C=(C

,C

,C

,…)，其中C

=(ci

i(1)

(2),c

)ig∞g9/23/202317信道编码(2,10,2)卷积码的生成矩阵为：11

01

11

00

00

…G∞=

00

11

01

11

00

00

…00

00

11

01

11

00

00

……

…g1g25.2卷积码的矩阵描述与编码(n0,1,m)卷积码的生成矩阵为便于理解，仍以(2,1,2)卷积码为例g∞=[11011100…]=[g0

g1

g2

0…]称为(2,1,2)卷积码的基本生成矩阵。其中：g0=[11],g1=[01],g2=[11]均为1x2

(k0xn0)阶矩阵，称为该码的子生成矩阵。子生成矩阵的行构成的向量,称为该码的生成元。g(1)=11

01

11生成元g(1)=11

01

11中每一段对应位构成的子向量

g(1,1)=101,g(1,2)=111称为该码的子生成元。9/23/202318信道编码5.2卷积码的矩阵描述与编码(n0,1,m)卷积码的生成矩阵为便于理解，仍以(2,1,2)卷积码为例子生成元的物理含义：子生成元g(1,

j)表示了码分组中第j个码元与参与运算的共m+1个信息元之间的校验关系，它对应于编码器的抽头系数。生成元的物理含义：生成元g(1)表示了码分组与m+1个信息元之间的校验关系。9/23/202319信道编码5.2卷积码的矩阵描述与编码9/23/202320信道编码(n0,1,m)卷积码的生成矩阵

对于一般的(n0,1,m)卷积码：子生成元一共有n0个，每个子生成元都是一个m+1重向量，记为：g(1,1)=[g0

,1)

g1

,1)

…

gm(1,1)](1

(1g(1,2)=[g0

,2)

g1

,2)

…

gm(1,2)](1

(1……g(1,n0)=[g0

,n0)

g1

,n0)

…

gm(1,n0)](1

(1g0,g1,…,gm为子生成矩阵5.2卷积码的矩阵描述与编码9/23/202321信道编码(n0,1,m)卷积码的生成矩阵它们对应编码器的n0组抽头系数特别地：对于系统卷积码，其第一个子生成元为g(1,1)=[1

0

0…0]。对于一般的(n0,1,m)卷积码：生成元仅有一个，可以由子生成元得到：g(1)=[g0

g0

…g0

g1

g1

…(1,1)

(1,2)

(1,n0)

(1,1)

(1,2)0(1,n

)g …

g1

mm

m(1,1)g

(1,2)…g

(1,n0)]子生成矩阵gi为：i

ig

=

[g

gi(1,1)

(1,2)i0(1,n

)…g

]5.2卷积码的矩阵描述与编码(n0,1,m)卷积码的生成矩阵因此可得到(n0,1,m)卷积码的基本生成矩阵：g∞=[g0

g1

…

gm

0

…](n0,1,m)卷积码的生成矩阵为：9/23/202322信道编码5.2卷积码的矩阵描述与编码(n0,1,m)卷积码的编码原理对于线性码均有C=mG，因此对卷积码有：C∞=m∞G∞(n0,1,m)卷积码的编码可由如下电路实现：9/23/202323信道编码5.2卷积码的矩阵描述与编码9/23/202324信道编码(n0,1,m)卷积码的生成矩阵(n0,1,m)卷积码举例：给定一卷积码的子生成元为：g(1,1)=10011，g(1,2)=11101判断该码的参数，写出生成矩阵，给出编码电路；假设信息序列m=110110000…，试求出编码序列C∞5.2卷积码的矩阵描述与编码9/23/202325信道编码(n0,1,m)卷积码的生成矩阵由子生成元g(1,1)=10011，g(1,2)=11101可得：m=4，n0=2，k0=1该码为(2,1,4)非系统卷积码其生成元为：g(1)=11

01

01

10

11子生成矩阵为：g0=[11],g1=[01],g2=[01],g3=[10],g4=[11]5.2卷积码的矩阵描述与编码(n0,1,m)卷积码的生成矩阵于是该码的生成矩阵为：11

01

01

10

11

00

…00

11

01

01

10

11

00

…00

00

11

01

01

10

11

00

…G∞=……00

11

01

01

10

11

00

…00

11

01

01

10

11

00

……9/23/202326信道编码5.2卷积码的矩阵描述与编码(n0,1,m)卷积码的生成矩阵根据子生成元可画出(2,1,4)码的编码电路：g(1,1)=10011，g(1,2)=111019/23/202327信道编码5.2卷积码的矩阵描述与编码(n0,1,m)卷积码的生成矩阵已知m=110110000…由C∞=m∞G∞可得码序列为：C∞

=11

10

00

00

11

11

11

01

11

00

…11

01

01

10

11

00

…00

11

01

01

10

11

00

…00

00

11

01

01

10

11

00

…G∞=……00

11

01

01

10

11

00

…00

11

01

01

10

11

00

……9/23/202328信道编码5.2卷积码的矩阵描述与编码9/23/202329信道编码(n0,k0,m)卷积码的生成矩阵一般地，对于(n0,k0,m)卷积码：子生成元：一共有k0xn0个，记为：g(1,1),g(1,2),…,g(1,n0)g(2,1),g(2,2),…,g(2,n0)……g(k0,1),g(k0,2),…,g(k0,n0

)5.2卷积码的矩阵描述与编码(n0,k0,m)卷积码的生成矩阵每个子生成元均为m+1重向量：g(i,

j)=

g0

,

j)

g1

,

j)

…

gm(i,

j)(i

(i特别地：对于系统卷积码，其子生成元有如下特点：9/23/202330信道编码5.2卷积码的矩阵描述与编码9/23/202331信道编码(n0,k0,m)卷积码的生成矩阵生成元：一共有k0个，记为：g(1),g(2),…,g(k0)每个生成元均为n0x(m+1)重向量：g(i)=g0

,1)g0

,2)…g0

,n0)…gm(i,1)…gm(i,n0)(i

(i

(i其中：gt

：子生成元g

的第t位(i,j)

(i,j)子生成矩阵：一共有m+1个，g0,g1,…,gm每个子生成矩阵均为k0xn0阶矩阵：5.2卷积码的矩阵描述与编码(n0,k0,m)卷积码的生成矩阵特别地：对于系统卷积码，其子生成矩阵有如下特点：其中，P0,P1,…,Pm为k0xr0阶矩阵9/23/202332信道编码5.2卷积码的矩阵描述与编码(n0,k0,m)卷积码的生成矩阵(n0,k0,m)卷积码的生成矩阵9/23/202333信道编码5.2卷积码的矩阵描述与编码信道编码9/23/202334(n0,k0,m)卷积码的生成矩阵(n0,k0,m)卷积码的编码原理根据子生成元可构造(n0,k0,m)卷积码的编码电路。参见教材(Page

198)5.2卷积码的矩阵描述与编码信道编码9/23/202335(n0,k0,m)卷积码的生成矩阵(n0,k0,m)卷积码举例：给定一卷积码的子生成元为：

g(1,1)=100，g(1,2)=000，g(1,3)=101g(2,1)=000，g(2,2)=100，g(2,3)=110判断该码的参数，写出生成矩阵，给出编码电路；假设信息序列m=10110000…，试求出编码序列C∞5.2卷积码的矩阵描述与编码(n0,k0,m)卷积码的生成矩阵(n0,k0,m)卷积码举例：由子生成元可得：m=2，n0=3，k0=2其生成元为：g(1)

=101000001g(2)

=011001000该码为(3,2,2)系统卷积码g(1,1)=100

g(1,2)=000

g(1,3)=101g(2,1)=000

g(2,2)=100

g(2,3)=110信道编码9/23/2023365.2卷积码的矩阵描述与编码(n0,k0,m)卷积码的生成矩阵(n0,k0,m)卷积码举例：其子生成矩阵为:该码的生成矩阵为：101

000

001

000

…011

001

000

000

…000

101

000

001

000

…G∞= 000

011

001

000

000

…000

000

101

000

001

000

…000

000

011

001

000

000

………9/23/202337信道编码5.2卷积码的矩阵描述与编码(n0,k0,m)卷积码的生成矩阵(n0,k0,m)卷积码举例：根据子生成元可画出(3,2,2)码的编码电路：g(1,1)=100

g(1,2)=000

g(1,3)=101g(2,1)=000

g(2,2)=100

g(2,3)=1109/23/202338信道编码5.2卷积码的矩阵描述与编码(n0,k0,m)卷积码的生成矩阵(n0,k0,m)卷积码举例：已知m=10

11

00

00…由C∞=m∞G∞可得码序列为：

C=101

110

000

001

000…9/23/202339信道编码5.2卷积码的矩阵描述与编码9/23/202340信道编码系统卷积码的校验矩阵(n0,k0,m)系统卷积码的校验矩阵卷积码是线性码，生成矩阵和校验矩阵之间满足：GHT=0根据上述关系式可由生成矩阵G∞求得H∞对于系统卷积码，G∞和H∞之间有简单的转换关系。5.2卷积码的矩阵描述与编码系统卷积码的校验矩阵(n0,k0,m)卷积码的校验矩阵具有如下形式：h0

0

…h1

h0

0

…h2

h1

h0

0

…H∞= …

…hm

hm-1

…

h1

h0

0

…0 hm

… h2

h1

h0

0

……

…0

1

mh,h,…,h

均为0

0

0

0

0r

xn

阶矩阵(r=n-k)，称为子校验矩阵1

0h∞

=

[hm

hm-1

…

h

h

0

…]称为基本校验矩阵。9/23/202341信道编码5.2卷积码的矩阵描述与编码系统卷积码的校验矩阵对于(n0,k0,m)系统卷积码，子生成矩阵gi与子校验矩阵hi之间有如下关系：由上述关系可容易地得到(n0,k0,m)系统卷积码的校验矩阵。9/23/202342信道编码5.2卷积码的矩阵描述与编码系统卷积码的校验矩阵[举例]：对前例中的(3,2,2)系统卷积码，子生成元为：

g(1,1)=100，g(1,2)=000，g(1,3)=101g(2,1)=000，g(2,2)=100，g(2,3)=110则：子校验矩阵为：h0=[111] h1=[01

0] h2=[10

0]9/23/202343信道编码系统卷积码的校验矩阵所以可得(3,2,2)系统卷积码的校验矩阵为：111

000

…010

111

000

…H∞

=

100

010

111

000

…000

100

010

111

000

……

…h0=[11

1]h1=[01

0]h2=[10

0]5.2卷积码的矩阵描述与编码h0

0

…h1

h0

0

…h2

h1

h0

0

…H∞= …

…hm

hm-1

…

h1

h0

0

…m

2

1

00

h

…

h

h

h

0

……

…9/23/202344信道编码5.2卷积码的矩阵描述与编码9/23/202345信道编码初始截短码卷积码的生成矩阵和校验矩阵都是半无限长矩阵，但在任何(m+1)个码分组的约束长度内，码元之间的校验关系都是相同的。在卷积码的代数译码中，通常只考虑一个编码约束长度内的码序列。因此我们有必要定义卷积码的初始截短码，研究一个约束长度内的码元校验关系。5.2卷积码的矩阵描述与编码9/23/202346信道编码初始截短码[定义1]：卷积码的编码器初始状态为全0时，编码器输出码序列的首m+1段码分组所构成的码字，称为卷积码的初始截短码字。[定义2]：一卷积码的所有初始截短码字的集合，构成一个((m+1)n0,(m+1)k0)线性码，称其为(n0,k0,m)卷积码的初始截短码。初始截短码具有线性分组码的所有性质。初始截短码与(n,k)分组码的主要区别在于前者的信息位不是连在一起的，而是间隔地分布在每一段码分组内。5.2卷积码的矩阵描述与编码初始截短码根据定义，(n0,k0,m)系统卷积码初始截短码的生成矩阵为：9/23/202347信道编码5.2卷积码的矩阵描述与编码初始截短码初始截短码的校验矩阵为：9/23/202348信道编码5.2卷积码的矩阵描述与编码初始截短码[举例]：(3,2,2)系统卷积码的子生成元为：g(1,3)=101

g(2,3)=110则初始截短码的生成矩阵和校验矩阵为：G=10

1 00