第五章-卷积码码1课件.ppt

1、3/27/2022信道编码信道编码1第五章 卷积码5.1 卷积码的基本概念卷积码的基本概念5.2 卷积码的矩阵描述与编码卷积码的矩阵描述与编码5.3 卷积码的状态图与格图描述卷积码的状态图与格图描述5.4 卷积码的概率译码卷积码的概率译码3/27/2022信道编码信道编码2第五章 卷积码p重点掌握：重点掌握：卷积码的基本概念与编码方法卷积码的格图描述p重点理解：重点理解：n卷积码的维特比译码算法3/27/2022信道编码信道编码3第五章 卷积码5.1 卷积码的基本概念卷积码的基本概念5.2 卷积码的矩阵描述与编码卷积码的矩阵描述与编码5.3 卷积码的状态图与格图描述卷积码的状态图与格图描述5.

2、4 卷积码的概率译码卷积码的概率译码3/27/2022信道编码信道编码45.1 卷积码的基本概念p卷积码的提出与发展卷积码的提出与发展n1954年，埃里斯（Elias）提出卷积码的概念，它是完全不同于线性分组码的一个码类。n1961年，提出卷积码的序列译码方法。n1963年，梅西（Massey）提出了卷积码的代数译码方法门限译码。n1967年，维特比（Vitebi）提出了卷积码的最大似然译码方法，称为维特比算法。直到现在，仍是应用最为广泛的译码算法。3/27/2022信道编码信道编码55.1 卷积码的基本概念p一个简单的卷积码编码例子一个简单的卷积码编码例子初始状态：00设输入m=101100

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

4、27/2022信道编码信道编码75.1 卷积码的基本概念p几个基本概念几个基本概念n信息分组与码分组(子码)：k0，n0k0:每个时刻输入编码器信息组中的信息元个数；n0 :每个时刻编码器输出一个子码中码元的个数。n系统码与非系统码：如果在n0位长的码分组中，前k0位是原输入的信息元，则该卷积码为系统码，否则称为非系统码。n编码效率：R=k0/n03/27/2022信道编码信道编码85.1 卷积码的基本概念p几个基本概念几个基本概念n编码存储m ：表示编码过程中，输入的信息组在编码器中需要存贮的单位时间。前面例子中，m=2n编码约束度N=m+1 ：表示编码过程中相互约束的码分组个数。n编码约束

5、长度n0N：表示编码过程中相互约束的码元数目。参数m,N, k0,n0反映了编码器的复杂度卷积码通常记为：(n0,k0,m)卷积码或N(n0,k0)3/27/2022信道编码信道编码95.1 卷积码的基本概念p卷积码的特点：卷积码的特点：n当前码分组输出不仅与当前信息分组输入有关，还与前面m个信息分组有关。n在相同码率、相同译码复杂性条件下，卷积码的性能要好于分组码。n卷积码仍是线性码，满足线性叠加关系。n通常情况下，非系统码的性能好于系统码。n尚没有完善的数学工具有效地分析其结构和性能，须借助计算机搜索来寻找好码。3/27/2022信道编码信道编码10第五章 卷积码5.1 卷积码的基本概念卷

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

7、阵描述与编码p卷积码的生成矩阵与编码卷积码的生成矩阵与编码p系统卷积码的校验矩阵系统卷积码的校验矩阵p初始截短码初始截短码p卷积码的距离特性卷积码的距离特性3/27/2022信道编码信道编码135.2 卷积码的矩阵描述与编码p(n0,1,m)卷积码的生成矩阵卷积码的生成矩阵为便于理解，仍以为便于理解，仍以(2,1,2)卷积码为例卷积码为例设：设：m=(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

8、 00 11 01 11)DDmC3/27/2022信道编码信道编码145.2 卷积码的矩阵描述与编码p(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=C+C+C =(11 01 11) +(00 11 01 11) +(00 00 11 01 11)=(11 10 01 10 11)DDmC3/27/2022

9、信道编码信道编码155.2 卷积码的矩阵描述与编码p(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 11 01 11 00 00 11 01 11 DDmC3/27/2022信道编码信道编码165.2 卷积码的矩阵描述与编码p(n0,1,m)卷积码的生成矩阵卷积码的

10、生成矩阵为便于理解，仍以为便于理解，仍以(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 DDmCgg0g1g23/27/2022信道编码信道编码175.2 卷积码的矩阵描述与编码p(n0,1,m)卷积码的生成矩阵卷积码的生成矩阵为便于理解，仍以为便于理解，仍以(2,1,2)卷积码为例卷积码为例ng=11 01 11 00 =g0 g1 g2 0 称为(2,1,2)

11、卷积码的基本生成矩阵。其中：g0=11, g1=01, g2=11 均为1x2 (k0 xn0)阶矩阵，称为该码的子生成矩阵。n子生成矩阵的行构成的向量,称为该码的生成元。 g(1)=11 01 11 n生成元g(1)=11 01 11中每一段对应位构成的子向量g(1,1)=101, g(1,2)=111称为该码的子生成元。DDmC3/27/2022信道编码信道编码185.2 卷积码的矩阵描述与编码p(n0,1,m)卷积码的生成矩阵卷积码的生成矩阵为便于理解，仍以为便于理解，仍以(2,1,2)卷积码为例卷积码为例n子生成元的物理含义： 子生成元 g(1, j)表示了码分组中第j个码元与参与运算

12、的共m+1个信息元之间的校验关系，它对应于编码器的抽头系数。n生成元的物理含义： 生成元 g(1)表示了码分组与m+1个信息元之间的校验关系。DDmC3/27/2022信道编码信道编码195.2 卷积码的矩阵描述与编码p(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

13、(1,n0) gm(1,n0)g0,g1,gm为子生成矩阵3/27/2022信道编码信道编码205.2 卷积码的矩阵描述与编码p(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

14、)3/27/2022信道编码信道编码215.2 卷积码的矩阵描述与编码p(n0,1,m)卷积码的生成矩阵卷积码的生成矩阵因此可得到(n0,1,m)卷积码的基本生成矩阵： g=g0 g1 gm 0 (n0,1,m)卷积码的生成矩阵为：.00.0.0.00.101010mmmgggggggggG3/27/2022信道编码信道编码225.2 卷积码的矩阵描述与编码p(n0,1,m)卷积码的编码原理卷积码的编码原理对于线性码均有C=mG，因此对卷积码有：C=mG(n0,1,m)卷积码的编码可由如下电路实现：D1D2Dmmc(1)c(n0)Cg0(1,1)g1(1,1)g2(1,1)gm(1,1)g0(

15、1,n0)g1(1,n0)g2(1,n0)gm(1,n0).3/27/2022信道编码信道编码235.2 卷积码的矩阵描述与编码p(n0,1,m)卷积码的生成矩阵卷积码的生成矩阵 (n0,1,m)卷积码举例：卷积码举例：给定一卷积码的子生成元为： g(1,1)=10011，g(1,2)=11101判断该码的参数，写出生成矩阵，给出编码电路；假设信息序列m=110110000，试求出编码序列C3/27/2022信道编码信道编码245.2 卷积码的矩阵描述与编码p(n0,1,m)卷积码的生成矩阵卷积码的生成矩阵由子生成元 g(1,1)=10011，g(1,2)=11101可得：m=4，n0=2，k

16、0=1该码为(2,1,4)非系统卷积码其生成元为：g(1)=11 01 01 10 11子生成矩阵为： g0=11,g1=01,g2=01,g3=10,g4=11 3/27/2022信道编码信道编码255.2 卷积码的矩阵描述与编码p(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 3/27/2022信道编码信道编码265.2 卷积码的矩阵描述与编码p(n0,1

17、,m)卷积码的生成矩阵卷积码的生成矩阵根据子生成元可画出(2,1,4)码的编码电路：DDmCDDg(1,1)=10011，g(1,2)=111013/27/2022信道编码信道编码275.2 卷积码的矩阵描述与编码p(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

18、 3/27/2022信道编码信道编码285.2 卷积码的矩阵描述与编码p(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 )3/27/2022信道编码信道编码295.2 卷积码的矩阵描述与编码p(n0,k0,m)卷积码的生成矩阵卷积码的生成矩阵每个子生成元均为m+1重向量： g(i, j)= g0(i, j) g1(i, j) gm(i, j)特别地：对于系统卷积码，其子生成元有如下

19、特点：0),(,0.0000.100kjijijigji3/27/2022信道编码信道编码305.2 卷积码的矩阵描述与编码p(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 xn0阶矩阵：3/27/2022信道编码信道编码315.2 卷积码的矩阵描述与编码p(n0,k0,m)卷

20、积码的生成矩阵卷积码的生成矩阵特别地：对于系统卷积码，其子生成矩阵有如下特点： 其中，P0,P1,Pm为k0 xr0阶矩阵 lkkllkkPOgPIg00000,003/27/2022信道编码信道编码325.2 卷积码的矩阵描述与编码p(n0,k0,m)卷积码的生成矩阵卷积码的生成矩阵n(n0,k0,m)卷积码的生成矩阵.00.0.0.00.101010mmmgggggggggG3/27/2022信道编码信道编码335.2 卷积码的矩阵描述与编码p(n0,k0,m)卷积码的生成矩阵卷积码的生成矩阵n(n0,k0,m)卷积码的编码原理 根据子生成元可构造(n0,k0,m)卷积码的编码电路。 参见

21、教材(Page 198)3/27/2022信道编码信道编码345.2 卷积码的矩阵描述与编码p(n0,k0,m)卷积码的生成矩阵卷积码的生成矩阵n(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，试求出编码序列C3/27/2022信道编码信道编码355.2 卷积码的矩阵描述与编码p(n0,k0,m)卷积码的生成矩阵卷积码的生成矩阵n(n0,k0,m)卷积码举例： 由子生成元可得：

22、 m=2，n0=3，k0=2其生成元为： g(1) = 101 000 001 g(2) = 011 001 000该码为(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)=1103/27/2022信道编码信道编码365.2 卷积码的矩阵描述与编码p(n0,k0,m)卷积码的生成矩阵卷积码的生成矩阵n(n0,k0,m)卷积码举例：其子生成矩阵为:该码的生成矩阵为： 101 000 001 000 011 001 000 000 000 101 000 001 000 G=000 011 001 000

23、 000 000 000 101 000 001 000 000 000 011 001 000 000 000100100000110101210ggg3/27/2022信道编码信道编码375.2 卷积码的矩阵描述与编码p(n0,k0,m)卷积码的生成矩阵卷积码的生成矩阵n(n0,k0,m)卷积码举例：根据子生成元可画出(3,2,2)码的编码电路：DDm(1)CDm(2)串并m并串c(1)c(2)c(3)g(1,1)=100 g(1,2)=000 g(1,3)=101g(2,1)=000 g(2,2)=100 g(2,3)=1103/27/2022信道编码信道编码385.2 卷积码的矩阵描述

24、与编码p(n0,k0,m)卷积码的生成矩阵卷积码的生成矩阵n(n0,k0,m)卷积码举例：已知m=10 11 00 00 由C=m G可得码序列为： C=101 110 000 001 000 3/27/2022信道编码信道编码395.2 卷积码的矩阵描述与编码p系统卷积码的校验矩阵系统卷积码的校验矩阵n(n0,k0,m)系统卷积码的校验矩阵 卷积码是线性码，生成矩阵和校验矩阵之间满足：GHT=0 根据上述关系式可由生成矩阵G求得H 对于系统卷积码，G和H之间有简单的转换关系。3/27/2022信道编码信道编码405.2 卷积码的矩阵描述与编码p系统卷积码的校验矩阵系统卷积码的校验矩阵n(n0

25、,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 = hm hm-1 h1 h0 0 称为基本校验矩阵。3/27/2022信道编码信道编码415.2 卷积码的矩阵描述与编码p系统卷积码的校验矩阵系统卷积码的校验矩阵对于(n0,k0,m)系统卷积码，子生成矩阵gi与子校验矩阵hi之间有如下关系：由上述关系可容易地得到(n0,k0,m)系统卷积码的校验矩阵。00000000000000iOPhPOgIPhPIg

26、rrTiikkirrTkk3/27/2022信道编码信道编码425.2 卷积码的矩阵描述与编码p系统卷积码的校验矩阵系统卷积码的校验矩阵举例：对前例中的(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 1 h1=01 0 h2=10 0000100100000110101210ggg3/27/2022信道编码信道编码43p系统卷积码的校验矩阵系统卷积码的校验矩阵所以可得(3,2,2)系统卷积码的校验矩阵为： 111 000 010 111 00

27、0 H = 100 010 111 000 000 100 010 111 000 h0=11 1 h1=01 0 h2=10 05.2 卷积码的矩阵描述与编码 h0 0 h1 h0 0 h2 h1 h0 0 H= hm hm-1 h1 h0 0 0 hm h2 h1 h0 0 3/27/2022信道编码信道编码445.2 卷积码的矩阵描述与编码p初始截短码初始截短码 卷积码的生成矩阵和校验矩阵都是半无限长矩阵，但在任何(m+1)个码分组的约束长度内，码元之间的校验关系都是相同的。在卷积码的代数译码中，通常只考虑一个编码约束长度内的码序列。因此我们有必要定义卷积码的初始截短码，研究一个约束长度

28、内的码元校验关系。3/27/2022信道编码信道编码455.2 卷积码的矩阵描述与编码p初始截短码初始截短码n定义1：卷积码的编码器初始状态为全0时，编码器输出码序列的首m+1段码分组所构成的码字，称为卷积码的初始截短码字。n定义2：一卷积码的所有初始截短码字的集合，构成一个(m+1)n0,(m+1)k0)线性码，称其为(n0,k0,m)卷积码的初始截短码。n初始截短码具有线性分组码的所有性质。n初始截短码与(n,k)分组码的主要区别在于前者的信息位不是连在一起的，而是间隔地分布在每一段码分组内。3/27/2022信道编码信道编码465.2 卷积码的矩阵描述与编码p初始截短码初始截短码n根据定

29、义，(n0,k0,m)系统卷积码初始截短码的生成矩阵为：011021000000000.PIPOPOPIPOPOPOPIGkmkkkmkkkk3/27/2022信道编码信道编码475.2 卷积码的矩阵描述与编码p初始截短码初始截短码n初始截短码的校验矩阵为：00000001010.rTrTmrTmrTrTrTIPOPOPIPOPIPH3/27/2022信道编码信道编码485.2 卷积码的矩阵描述与编码p初始截短码初始截短码举例：(3,2,2)系统卷积码的子生成元为： g(1,3)=101 g(2,3)=110则初始截短码的生成矩阵和校验矩阵为： 10 1 00 0 00 1 01 1 00 1

30、 00 0G= 00 0 10 1 00 0 00 0 01 1 00 1 00 0 00 0 10 1 00 0 00 0 01 1 11 1 00 0 00 0H= 01 0 11 1 00 0 10 0 01 0 11 13/27/2022信道编码信道编码495.2 卷积码的矩阵描述与编码p卷积码的距离特性卷积码的距离特性n卷积码不同于分组码，有多种距离定义。n最小汉明距离定义： (n0,k0,m)卷积码的最小汉明距离定义为所有第0码分组不同的初始截短码字之间的最小距离，记为dm。定理1： (n0,k0,m)卷积码的最小汉明距离等于第0码分组为非全0的初始截短码字的最小重量。定理2：在(

31、n0,k0,m)卷积码的校验矩阵中，若任意小于等于d-1列线性无关（其中至少有一列在首n0列），且有d列线性相关，则码的最小汉明距离为d。3/27/2022信道编码信道编码505.2 卷积码的矩阵描述与编码p卷积码的距离特性卷积码的距离特性n自由距离定义： (n0,k0,m)卷积码的自由距离定义为所有非0半无限长码序列之间的最小距离。定理1： (n0,k0,m)卷积码的自由距离等于第0码分组为非全0的半无限长码序列的最小汉明重量。 卷积码的自由距离df大于等于最小汉明距离dm通常情况下：非系统码的df大于系统码的df。3/27/2022信道编码信道编码515.2 卷积码的矩阵描述与编码p小结：

32、小结：n卷积码的当前码分组不仅与当前信息分组有关，还与前m个信息分组有关n卷积码由子生成元定义（编码电路）n类似于分组码，卷积码也可采用生成矩阵和校验矩阵描述n初始截短码定义在卷积码的一个约束长度内n卷积码最小汉明距离定义为初始截短码的最小距离n卷积码的自由距离大于等于其最小汉明距离3/27/2022信道编码信道编码525.2 卷积码的矩阵描述与编码作业：作业：1、已知一卷积码的子生成元为： g(1,1)=100,g(1,2)=110,g(1,3)=101 判断该码的参数，写出其生成矩阵、校验矩阵，给出编码电路； 假设信息序列m=1011000，试求出编码序列C； 给出该码的初始截短码的生成矩阵与校验矩阵。