第五章 卷积码码.ppt

1、通信工程系移动通信教研室,信道编码,2020/8/16,信道编码,2,第五章 卷积码,5.1 卷积码的基本概念 5.2 卷积码的矩阵描述与编码 5.3 卷积码的状态图与格图描述 5.4 卷积码的概率译码,2020/8/16,信道编码,3,第五章 卷积码,重点掌握： 卷积码的基本概念与编码方法 卷积码的格图描述 重点理解： 卷积码的维特比译码算法,2020/8/16,信道编码,4,第五章 卷积码,5.1 卷积码的基本概念 5.2 卷积码的矩阵描述与编码 5.3 卷积码的状态图与格图描述 5.4 卷积码的概率译码,2020/8/16,信道编码,5,5.1 卷积码的基本概念,卷积码的提出与发展 19

2、54年，埃里斯（Elias）提出卷积码的概念，它是完全不同于线性分组码的一个码类。 1961年，提出卷积码的序列译码方法。 1963年，梅西（Massey）提出了卷积码的代数译码方法门限译码。 1967年，维特比（Vitebi）提出了卷积码的最大似然译码方法，称为维特比算法。直到现在，仍是应用最为广泛的译码算法。,2020/8/16,信道编码,6,5.1 卷积码的基本概念,一个简单的卷积码编码例子 初始状态：00 设输入m=101100 则输出与输入的关系为：,输入：1 状态：00 输出：11,0 10 01,1 01 00,1 10 10,0 11 10,0 01 11,0 00 00, ,

3、码序列,码分组,信息分组,2020/8/16,信道编码,7,5.1 卷积码的基本概念,说明： 可以将卷积码的编码器看作一个由k0个输入端和n0个输出端组成的时序网络，即每输入k0个信息元，输出n0个码元组成的码分组(子码)。例子中k0=1, n0=2； 编码器某个时刻的输出不仅与该时刻编码器的输入有关，而且与以前若干时刻(由编码存储单元的个数决定)的输入编码器的信息有关。 卷积码的码字（码序列）可以看作是由无限多个码分组组成的码向量，即码字是一个无限维向量。,2020/8/16,信道编码,8,5.1 卷积码的基本概念,几个基本概念 信息分组与码分组(子码)：k0，n0 k0:每个时刻输入编码器

4、信息组中的信息元个数； n0 :每个时刻编码器输出一个子码中码元的个数。 系统码与非系统码： 如果在n0位长的码分组中，前k0位是原输入的信息元，则该卷积码为系统码，否则称为非系统码。 编码效率：R=k0/n0,2020/8/16,信道编码,9,5.1 卷积码的基本概念,几个基本概念 编码存储m ：表示编码过程中，输入的信息组在编码器中需要存贮的单位时间。前面例子中，m=2 编码约束度N=m+1 ：表示编码过程中相互约束的码分组个数。 编码约束长度n0N：表示编码过程中相互约束的码元数目。 参数m,N, k0,n0反映了编码器的复杂度 卷积码通常记为：(n0,k0,m)卷积码或N(n0,k0)

5、,2020/8/16,信道编码,10,5.1 卷积码的基本概念,卷积码的特点： 当前码分组输出不仅与当前信息分组输入有关，还与前面m个信息分组有关。 在相同码率、相同译码复杂性条件下，卷积码的性能要好于分组码。 卷积码仍是线性码，满足线性叠加关系。 通常情况下，非系统码的性能好于系统码。 尚没有完善的数学工具有效地分析其结构和性能，须借助计算机搜索来寻找好码。,2020/8/16,信道编码,11,第五章 卷积码,5.1 卷积码的基本概念 5.2 卷积码的矩阵描述与编码 5.3 卷积码的状态图与格图描述 5.4 卷积码的概率译码,2020/8/16,信道编码,12,5.2 卷积码的矩阵描述与编码

6、,卷积码的特点： 当前码分组输出不仅与当前信息分组输入有关，还与前面m个信息分组有关。 在相同码率、相同译码复杂性条件下，卷积码的性能要好于分组码。 卷积码仍是线性码，满足线性叠加关系。 通常情况下，非系统码的性能好于系统码。 尚没有完善的数学工具有效地分析其结构和性能，须借助计算机搜索来寻找好码。,2020/8/16,信道编码,13,5.2 卷积码的矩阵描述与编码,卷积码的生成矩阵与编码 系统卷积码的校验矩阵 初始截短码 卷积码的距离特性,2020/8/16,信道编码,14,5.2 卷积码的矩阵描述与编码,(n0,1,m)卷积码的生成矩阵 为便于理解，仍以(2,1,2)卷积码为例 设：m=(

7、m0,m1,m2,) C=(C0,C1,C2,)，其中Ci=(ci(1),ci(2) 若输入信息序列和编码器相应输出序列为： m =(100) C =(11 01 11) m=(0100.) C=(00 11 01 11) m=(0010.) C=(00 00 11 01 11),2020/8/16,信道编码,15,5.2 卷积码的矩阵描述与编码,(n0,1,m)卷积码的生成矩阵 为便于理解，仍以(2,1,2)卷积码为例 设：m=(m0,m1,m2,) C=(C0,C1,C2,)，其中Ci=(ci(1),ci(2) 若输入信息序列分别为 m=m+m+m =(100)+(0100.)+(0010

8、.)=(1110) 编码器相应输出的码序列为： C=C+C+C =(11 01 11) +(00 11 01 11) +(00 00 11 01 11)=(11 10 01 10 11),2020/8/16,信道编码,16,5.2 卷积码的矩阵描述与编码,(n0,1,m)卷积码的生成矩阵 为便于理解，仍以(2,1,2)卷积码为例 设：m=(m0,m1,m2,) C=(C0,C1,C2,)，其中Ci=(ci(1),ci(2) 若输入信息序列分别为 m=m+m+m =(100)+(0100.)+(0010.)=(1110) 编码器相应输出的码序列为： C=mG=(1110) 11 01 11 00

9、 11 01 11 00 00 11 01 11 ,2020/8/16,信道编码,17,5.2 卷积码的矩阵描述与编码,(n0,1,m)卷积码的生成矩阵 为便于理解，仍以(2,1,2)卷积码为例 设：m=(m0,m1,m2,) C=(C0,C1,C2,)，其中Ci=(ci(1),ci(2) (2,1,2)卷积码的生成矩阵为： 11 01 11 00 00 G= 00 11 01 11 00 00 00 00 11 01 11 00 00 ,g,g0,g1,g2,2020/8/16,信道编码,18,5.2 卷积码的矩阵描述与编码,(n0,1,m)卷积码的生成矩阵 为便于理解，仍以(2,1,2)卷

10、积码为例 g=11 01 11 00 =g0 g1 g2 0 称为(2,1,2)卷积码的基本生成矩阵。 其中：g0=11, g1=01, g2=11 均为1x2 (k0 xn0)阶矩阵，称为该码的子生成矩阵。 子生成矩阵的行构成的向量,称为该码的生成元。 g(1)=11 01 11 生成元g(1)=11 01 11中每一段对应位构成的子向量g(1,1)=101, g(1,2)=111称为该码的子生成元。,2020/8/16,信道编码,19,5.2 卷积码的矩阵描述与编码,(n0,1,m)卷积码的生成矩阵 为便于理解，仍以(2,1,2)卷积码为例 子生成元的物理含义： 子生成元 g(1, j)表

11、示了码分组中第j个码元与参与运算的共m+1个信息元之间的校验关系，它对应于编码器的抽头系数。 生成元的物理含义： 生成元 g(1)表示了码分组与m+1个信息元之间的校验关系。,2020/8/16,信道编码,20,5.2 卷积码的矩阵描述与编码,(n0,1,m)卷积码的生成矩阵 对于一般的(n0,1,m)卷积码： 子生成元一共有n0个，每个子生成元都是一个m+1重向量，记为： g(1,1)=g0(1,1) g1(1,1) gm(1,1) g(1,2)=g0(1,2) g1(1,2) gm(1,2) g(1,n0)=g0(1,n0) g1(1,n0) gm(1,n0) g0,g1,gm为子生成矩阵

12、,2020/8/16,信道编码,21,5.2 卷积码的矩阵描述与编码,(n0,1,m)卷积码的生成矩阵 它们对应编码器的n0组抽头系数 特别地：对于系统卷积码，其第一个子生成元为 g(1,1)=1 0 0 0。 对于一般的(n0,1,m)卷积码： 生成元仅有一个，可以由子生成元得到： g(1)=g0(1,1)g0(1,2)g0(1,n0) g1(1,1)g1(1,2) g1(1,n0) gm(1,1)gm(1,2)gm(1,n0) 子生成矩阵gi为： gi = gi(1,1)gi(1,2)gi(1,n0),2020/8/16,信道编码,22,5.2 卷积码的矩阵描述与编码,(n0,1,m)卷积

13、码的生成矩阵 因此可得到(n0,1,m)卷积码的基本生成矩阵： g=g0 g1 gm 0 (n0,1,m)卷积码的生成矩阵为：,2020/8/16,信道编码,23,5.2 卷积码的矩阵描述与编码,(n0,1,m)卷积码的编码原理 对于线性码均有C=mG，因此对卷积码有：C=mG (n0,1,m)卷积码的编码可由如下电路实现：,2020/8/16,信道编码,24,5.2 卷积码的矩阵描述与编码,(n0,1,m)卷积码的生成矩阵 (n0,1,m)卷积码举例： 给定一卷积码的子生成元为： g(1,1)=10011，g(1,2)=11101 判断该码的参数，写出生成矩阵，给出编码电路； 假设信息序列m

14、=110110000，试求出编码序列C,2020/8/16,信道编码,25,5.2 卷积码的矩阵描述与编码,(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,2020/8/16,信道编码,26,5.2 卷积码的矩阵描述与编码,(n0,1,m)卷积码的生成矩阵 于是该码的生成矩阵为： 11 01 01 10 11 00 00 11 01 01 10 11

15、00 00 00 11 01 01 10 11 00 G= 00 11 01 01 10 11 00 00 11 01 01 10 11 00 ,2020/8/16,信道编码,27,5.2 卷积码的矩阵描述与编码,(n0,1,m)卷积码的生成矩阵 根据子生成元可画出(2,1,4)码的编码电路：,g(1,1)=10011，g(1,2)=11101,2020/8/16,信道编码,28,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

16、 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 ,2020/8/16,信道编码,29,5.2 卷积码的矩阵描述与编码,(n0,k0,m)卷积码的生成矩阵 一般地，对于(n0,k0,m)卷积码： 子生成元：一共有k0 xn0个，记为： 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 ),2020/8/16,信道编码,30,5.2 卷积码的矩阵描述与编码,(n0,k0,m)

17、卷积码的生成矩阵 每个子生成元均为m+1重向量： g(i, j)= g0(i, j) g1(i, j) gm(i, j) 特别地：对于系统卷积码，其子生成元有如下特点：,2020/8/16,信道编码,31,5.2 卷积码的矩阵描述与编码,(n0,k0,m)卷积码的生成矩阵 生成元：一共有k0个，记为： g(1),g(2),g(k0) 每个生成元均为n0 x(m+1)重向量： g(i)=g0(i,1)g0(i,2)g0(i,n0)gm(i,1)gm(i,n0) 其中：gt(i,j) ：子生成元g(i,j) 的第t位 子生成矩阵：一共有m+1个，g0, g1, , gm 每个子生成矩阵均为k0 x

18、n0阶矩阵：,2020/8/16,信道编码,32,5.2 卷积码的矩阵描述与编码,(n0,k0,m)卷积码的生成矩阵 特别地：对于系统卷积码，其子生成矩阵有如下特点： 其中，P0,P1,Pm为k0 xr0阶矩阵,2020/8/16,信道编码,33,5.2 卷积码的矩阵描述与编码,(n0,k0,m)卷积码的生成矩阵 (n0,k0,m)卷积码的生成矩阵,2020/8/16,信道编码,34,5.2 卷积码的矩阵描述与编码,(n0,k0,m)卷积码的生成矩阵 (n0,k0,m)卷积码的编码原理 根据子生成元可构造(n0,k0,m)卷积码的编码电路。 参见教材(Page 198),2020/8/16,信

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

20、1 g(2) = 011 001 000 该码为(3,2,2)系统卷积码,g(1,1)=100 g(1,2)=000 g(1,3)=101 g(2,1)=000 g(2,2)=100 g(2,3)=110,2020/8/16,信道编码,37,5.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

21、001 000 000 ,2020/8/16,信道编码,38,5.2 卷积码的矩阵描述与编码,(n0,k0,m)卷积码的生成矩阵 (n0,k0,m)卷积码举例： 根据子生成元可画出(3,2,2)码的编码电路：,g(1,1)=100 g(1,2)=000 g(1,3)=101 g(2,1)=000 g(2,2)=100 g(2,3)=110,2020/8/16,信道编码,39,5.2 卷积码的矩阵描述与编码,(n0,k0,m)卷积码的生成矩阵 (n0,k0,m)卷积码举例： 已知m=10 11 00 00 由C=m G可得码序列为： C=101 110 000 001 000 ,2020/8/1

22、6,信道编码,40,5.2 卷积码的矩阵描述与编码,系统卷积码的校验矩阵 (n0,k0,m)系统卷积码的校验矩阵 卷积码是线性码，生成矩阵和校验矩阵之间满足：GHT=0 根据上述关系式可由生成矩阵G求得H 对于系统卷积码，G和H之间有简单的转换关系。,2020/8/16,信道编码,41,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 ,h0,h1,hm 均为 r0 xn0阶矩阵(r0=n0-k0)， 称为子校验矩阵 h =

23、 hm hm-1 h1 h0 0 称为基本校验矩阵。,2020/8/16,信道编码,42,5.2 卷积码的矩阵描述与编码,系统卷积码的校验矩阵 对于(n0,k0,m)系统卷积码，子生成矩阵gi与子校验矩阵hi之间有如下关系： 由上述关系可容易地得到(n0,k0,m)系统卷积码的校验矩阵。,2020/8/16,信道编码,43,5.2 卷积码的矩阵描述与编码,系统卷积码的校验矩阵 举例：对前例中的(3,2,2)系统卷积码，子生成元为： g(1,1)=100，g(1,2)=000，g(1,3)=101 g(2,1)=000，g(2,2)=100，g(2,3)=110 则： 子校验矩阵为： h0=11

24、 1 h1=01 0 h2=10 0,2020/8/16,信道编码,44,系统卷积码的校验矩阵 所以可得(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 卷积码的矩阵描述与编码,2020/8/16,信道编码,45,5.2 卷积码的矩阵描述与编码,初始截短码 卷积码的生成矩阵和校验矩阵都是半无限长矩阵，但在任何(m+1)个码分组的约束长度内，码元之间的校验关系都是相同的。 在卷积码的代数译码中，通常只考虑一个编码约束长度内的码序列。

25、 因此我们有必要定义卷积码的初始截短码，研究一个约束长度内的码元校验关系。,2020/8/16,信道编码,46,5.2 卷积码的矩阵描述与编码,初始截短码 定义1：卷积码的编码器初始状态为全0时，编码器输出码序列的首m+1段码分组所构成的码字，称为卷积码的初始截短码字。 定义2：一卷积码的所有初始截短码字的集合，构成一个(m+1)n0,(m+1)k0)线性码，称其为(n0,k0,m)卷积码的初始截短码。 初始截短码具有线性分组码的所有性质。 初始截短码与(n,k)分组码的主要区别在于前者的信息位不是连在一起的，而是间隔地分布在每一段码分组内。,2020/8/16,信道编码,47,5.2 卷积码的矩阵描述与编码,初始截短码 根据定义，(n0,k0,m)系统卷积码初始截短码的生成矩阵为：,2020/8/16,信道编码,48,5.2 卷积码的矩阵描述与编码,初始截短码 初始截短码的校验矩阵为：,2020/8/16,信道编码,49,5.2 卷积码的矩阵描述与编码,初始截短码 举例：(3,2,2)系统卷积码的子生成元为： g(1,3)=101 g(2,3)=110 则初始截短码的生成矩阵和校验矩阵为： 10 1 00 0 00 1 01 1 00 1 00 0 G= 00 0 10 1 00 0 00 0 01 1