数字电视卷积码

1、15.8卷积码卷积码21 卷积码的一般概念卷积码的一般概念 卷积码与分组码的区别：卷积码与分组码的区别：本组的码元不仅与本组的本组的码元不仅与本组的k个信息元有关，个信息元有关，而且还与以前若干时刻输入至编码器的信而且还与以前若干时刻输入至编码器的信息元有关。息元有关。译码时，不仅从此时刻收到的译码时，不仅从此时刻收到的n个码元中提个码元中提取译码信息，而且还利用以后若干时刻收取译码信息，而且还利用以后若干时刻收到的码组提取有关译码信息。到的码组提取有关译码信息。卷积码各码组之间不再是相互独立。卷积码各码组之间不再是相互独立。3卷积码的编码器可以看作是一个由卷积码的编码器可以看作是一个由k个输

2、入端和个输入端和n个输出端组成的时序网络。个输出端组成的时序网络。设第设第i时刻输入编码器的时刻输入编码器的k个信息为：个信息为：mi（mi(1)，mi(2)，mi(k)）相应输出是由相应输出是由n0个码元组成的子码：个码元组成的子码：ci（ci(1)，ci(2)，ci(n)）4若输入的信息序列：若输入的信息序列：m（m0,m1,m2, ）则输出由子码则输出由子码C（c0,c1,c2, ），），定义：定义：如果如果n位长的子码中，前位长的子码中，前k位是原输入位是原输入的信息元，则称该卷积码为的信息元，则称该卷积码为系统码系统码，否则称，否则称为非系统码。为非系统码。5如图二进制卷积码编码器：

3、如图二进制卷积码编码器：第第i i时刻输入信息元时刻输入信息元m mi i，此时刻的子码：，此时刻的子码：c ci i（m mi i，p pi,1i,1，p pi,2i,2）, p, pi,1i,1，p pi,2i,2为校验元为校验元且满足：且满足：ci(1) m mi i ci(2) p pi,1i,1m mi im mi-1i-1 ci(3) p pi,2i,2m mi im mi-2i-26下一个时间单位输入的信息元为下一个时间单位输入的信息元为mi+1，则对应的校，则对应的校验元：验元：ci1(2) p pi i1,11,1m mi i1 1m mi i ci1(3) p pi i1,

4、21,2m mi i1 1m mi-1i-1第二个子码第二个子码ci1（ mi+1 ， ci1(2) ， ci1(3) ）如此每时刻送入编码器如此每时刻送入编码器1 1个（可为个（可为k k个）信息元，编个）信息元，编码器就送出相应的码器就送出相应的3 3个（可为个（可为n n个）码元组成一个子个）码元组成一个子码码c ci i送入信道。送入信道。这这n n个码元组成的子码个码元组成的子码c ci i称为卷积码的一个码段或称为卷积码的一个码段或子组。子组。7显然，第显然，第i时刻输入的信息时刻输入的信息组组mi及相应码段及相应码段ci，不仅，不仅与前与前m2个码段中的码个码段中的码元有关，而且

5、也参与了元有关，而且也参与了后后m个码段中的校验运算。个码段中的校验运算。如图，组成卷积码的一如图，组成卷积码的一个码序列，产生（个码序列，产生（3,1,2）系统卷积码，系统卷积码，或（或（n,k,m）卷积码。）卷积码。8描述卷积码的主要术语：描述卷积码的主要术语： 输入帧：输入帧：每个时刻同时输入编码器信息组中的每个时刻同时输入编码器信息组中的比特数（信息元个数），用比特数（信息元个数），用k表示。表示。 输出帧：输出帧：每个时刻同时从编码器输出的比特数每个时刻同时从编码器输出的比特数（输出一个子码中码元的个数），用（输出一个子码中码元的个数），用n表示。表示。 储存阶数（编码储存）：储存阶

6、数（编码储存）：表示输入信息组在编表示输入信息组在编码器中需存储的单位时间，即产生输出比特的码器中需存储的单位时间，即产生输出比特的过程中移位寄存器的最大级数，用过程中移位寄存器的最大级数，用m表示。表示。 编码约束度：编码约束度：表示编码过程中相互约束的子码表示编码过程中相互约束的子码个数，用个数，用Nm1表示。表示。9 编码约束长度：编码约束长度：表示编码过程中相互约束表示编码过程中相互约束的码元数目，用的码元数目，用NANn表示。表示。 参数参数m，N，k，n反映了编码器的复杂程反映了编码器的复杂程度，所以卷积码一般用（度，所以卷积码一般用（n，k，m）或）或（n N ，kN）表示，）表

7、示，k和和n比分组码的比分组码的k和和n通通常要小。常要小。 比值比值Rk/n为卷积码的码率，是衡量卷积为卷积码的码率，是衡量卷积码传输信息有效性的一个重要参数。码传输信息有效性的一个重要参数。102 卷积码的矩阵描述和多项式表示卷积码的矩阵描述和多项式表示根据（根据（3，1，2）卷积码编码器框图，设编码）卷积码编码器框图，设编码器的初始状态全为器的初始状态全为0，输入信息序列分别为：，输入信息序列分别为：m1（100），），m2（0100），），m3（00100），），则编码器相应输出的码序列分别为：则编码器相应输出的码序列分别为：c1（111 010 001 000 000）c2（000

8、111 010 001 000 000）c3（000 000 111 010 001 000 000）11当输入信息序列：当输入信息序列：mm1m2m3则输出码序列：则输出码序列：cc1c2c3用矩阵表示：用矩阵表示：可见，卷积码生成矩阵可见，卷积码生成矩阵G是一个半无限矩阵，是一个半无限矩阵，有无限个行与列，且每一行都是前一行右移有无限个行与列，且每一行都是前一行右移3（即（即n）位的结果。）位的结果。12G可以完全由它的第一行决定，写成：可以完全由它的第一行决定，写成： g111,010,001,000,000, g0,g1,g2,0,0,称称g为基本生成矩阵为基本生成矩阵，其中，其中g0

9、，g1，g2等都是一个等都是一个13阶（即阶（即kn阶）矩阵。阶）矩阵。延迟算子延迟算子D：表示卷积码编码过程中一个单位时间：表示卷积码编码过程中一个单位时间（n个码元）的延迟。个码元）的延迟。则则G可写成：可写成：13基本生成矩阵基本生成矩阵g的性质：的性质：1）（）（3，1，2）卷积码中，）卷积码中，g(1)（g0,g1,g2） 可以完全确定可以完全确定g，g(1)称为该码的生成元称为该码的生成元。2）每一个）每一个gi（i=0,1,2）由）由n3个数字决定，个数字决定， 将其第一个分量取出组成一个将其第一个分量取出组成一个3维向量，即：维向量，即： g(1,1)（100），是产生码元），

10、是产生码元ci(1)的抽头，的抽头， 同理：同理：g(1,2)、g(1,3)是产生码元是产生码元ci(2)、ci(3) 的抽头，的抽头，称称g(1,1)、 g(1,2)、g(1,3)为该码的为该码的 子生成元。子生成元。14结论：结论：只要已知一个卷积码的所有只要已知一个卷积码的所有子生成元子生成元，该码的生成元该码的生成元g(1)和基本生成矩阵和基本生成矩阵g就被确定，就被确定，因而可相应确定码的生成矩阵因而可相应确定码的生成矩阵G。子生成元的物理意义：子生成元的物理意义：是编码器电路中产生子是编码器电路中产生子码各码元对应存储器上的抽头。因而，若一个码各码元对应存储器上的抽头。因而，若一个

11、卷积码编码器的存储器级数与产生码序列各抽卷积码编码器的存储器级数与产生码序列各抽头确定了，子生成元也就确定了。头确定了，子生成元也就确定了。由子生成元，将由子生成元，将G写成写成D的函数形式：的函数形式：G(D)为（为（n0,k0,m）卷积码的生成多项式矩阵）卷积码的生成多项式矩阵15把信息序列把信息序列M（11100）也写成）也写成D的函数：的函数：相应的码序列：相应的码序列：称称C(D)为卷积码码序列的多项式，其每一系数为卷积码码序列的多项式，其每一系数ci由由n0个分量组成，将所有系数（子码）的第个分量组成，将所有系数（子码）的第j（j=1,2,.n0）个分量写成多项式）个分量写成多项式

12、C(j)(D)：16（3，1，2）卷积码中：）卷积码中：因此，一旦因此，一旦C(j)(D)确定，则完全确定了确定，则完全确定了C(D)，所，所以，编码器的任务是如何由以，编码器的任务是如何由M(D)得到得到C(j)(D)由由CMG，可得，可得C(D)的多项式：的多项式：17显然，与先前得到的显然，与先前得到的C(D)结果完全相同。结果完全相同。又：又：G(D)C(D)/M(D)，是输出与输入之比。，是输出与输入之比。18例：例：k01时，卷积码的生成矩阵和生成元：时，卷积码的生成矩阵和生成元：如图为信息元并行输入的（如图为信息元并行输入的（3，2，2）系统卷）系统卷积码的编码器，设编码器的初始

13、状态全为积码的编码器，设编码器的初始状态全为0，输入信息序列：输入信息序列：19若第一个信息序列：若第一个信息序列： M(1) （10，00，00，）则相应的输出码序列：则相应的输出码序列： C(1)（c0(1)，c1(1)，c2(1)， ） （101，000，001，000，000，）当当M(2) （01，00，00，）则则C(2)（c0(2)，c1(2)，c2(2)， ） （011，001，000，000，）20所以，当所以，当 MM(1)M(2) （11，00，00，）则相应输出的码序列：则相应输出的码序列：21显然，若输入信息序列：显然，若输入信息序列：则相应输出的码序列：则相应输出的

14、码序列：22写成矩阵形式：写成矩阵形式：显然，显然， G完全由最上面两行决定，则完全由最上面两行决定，则G的的基本生成矩阵：基本生成矩阵：Ik0p00阵阵p1p223所以：所以：gg0 g1 g2 0 上式中，从上式中，从m13段以后开始，取值均为段以后开始，取值均为0，说明某一时刻输入的信息元，至多只影响说明某一时刻输入的信息元，至多只影响此时刻和以后此时刻和以后m个单位时间的子码，而在个单位时间的子码，而在m1个时间单位以后，信息元已移出编码个时间单位以后，信息元已移出编码器，不再对以后各段子码的编码发生影响。器，不再对以后各段子码的编码发生影响。24由于由于k02，就有，就有2个生成元：

15、个生成元： g(1)101，000，001 g(2)011，001，001生成元与子生成元的关系为：生成元与子生成元的关系为：所以，只要码的生成元和子生成元被确定，则所以，只要码的生成元和子生成元被确定，则码的码的G也就完全确定了。也就完全确定了。25利用子生成多项式，将利用子生成多项式，将G表示为：表示为：由编码器输出的码序列：由编码器输出的码序列：263 卷积码的一致校验矩阵卷积码的一致校验矩阵 卷积码是线性码，也与分组码一样，生成卷积码是线性码，也与分组码一样，生成阵与校验阵之间必满足：阵与校验阵之间必满足： （n0,k0,m）卷积码校验矩阵的一般形式：）卷积码校验矩阵的一般形式：校验阵

16、也是半无限的，校验阵也是半无限的，其中：其中：h0,h1.hm及及0均是均是（n0-k0）n0阶阵。阶阵。空白处为空白处为027（3,2,2）卷积码的卷积码的生成阵：生成阵：由：由：28可得到：可得到：因而该码的校验矩阵：因而该码的校验矩阵：显然，校验阵完全由其第一列元素决定。显然，校验阵完全由其第一列元素决定。29（n0,k0,m）系统卷积码的一致校验矩阵：）系统卷积码的一致校验矩阵： 定义该阵的第定义该阵的第m+1行元素所组成的阵为行元素所组成的阵为码的码的基本校验矩阵基本校验矩阵：(n0-k0)k0阶矩阵，是阶矩阵，是生成阵中生成阵中P0,Pm的转置阵的转置阵第第m+1行行(n0-k0)

17、(n0-k0)阶阶单位矩阵单位矩阵空白处全为空白处全为0(n0-k0)(n0-k0)阶阶全全0矩阵矩阵30（3，2，2）卷积码编码器）卷积码编码器m(n0-k0)级串行编码器级串行编码器mk0级并行编码器级并行编码器mk0级串行编码器级串行编码器314 卷积码的树图描述和状态图表示卷积码的树图描述和状态图表示一、卷积码的树图描述一、卷积码的树图描述例例：（：（2，1，2）码的生成多项式矩阵和生成）码的生成多项式矩阵和生成矩阵分别为：矩阵分别为：32若输入编码器的信息序列：若输入编码器的信息序列：M（m0，m1，.）（）（1 1 0 1 1.）则编码器输出的码序列为：则编码器输出的码序列为：编码

18、过程可用半无限码树图说明：设编码器初编码过程可用半无限码树图说明：设编码器初始状态为始状态为0，输入信息序列为，输入信息序列为M，输出的码，输出的码序列相应于码树中的一条序列相应于码树中的一条正确路径正确路径，而其它，而其它所有路径都是它的不正确路径。所有路径都是它的不正确路径。33（2，1，2）码码树图：）码码树图：将码树分成将码树分成上下相等的上下相等的两部分，就是两部分，就是把码序列划分把码序列划分成大小相等的成大小相等的两个子集两个子集s0和和s134 对一般的二进制（对一般的二进制（n0,k0,m）编码器，每次）编码器，每次输入的是输入的是k0个信息元，有个信息元，有2ko个可能的信

19、息个可能的信息组，这相应于从码树每一节点上分出的分组，这相应于从码树每一节点上分出的分支数有支数有2ko条，相应于条，相应于2ko种不同信息组的输种不同信息组的输入，且每条都有入，且每条都有n0个码元，作为与此相应个码元，作为与此相应的输出子码。的输出子码。 因此，码数上所有可能的路径，就是该卷因此，码数上所有可能的路径，就是该卷积码编码器所有可能输出的码序列。积码编码器所有可能输出的码序列。35码树中子集的划分码树中子集的划分36二、卷积码的状态图二、卷积码的状态图编码器寄存器中任一时刻的存数称为编码器编码器寄存器中任一时刻的存数称为编码器的一个状态，以的一个状态，以si表示，每个表示，每个

20、状态都对应一个不同的输入组。状态都对应一个不同的输入组。如图为（如图为（2，1，2）卷积码）卷积码编码器状态图。编码器由两编码器状态图。编码器由两级移存器组成，其存数只有级移存器组成，其存数只有4种可能，即种可能，即4个状态。个状态。实线表实线表示示0输入、输入、虚线表示虚线表示1输入时输入时的状态转的状态转移移37例：信息组例：信息组M（1100），），M(D)1D， 则，输出的码序列：则，输出的码序列： C(D)M(D)G(D)(1+D)1+D+D2,1+D2 (11)+(10)D+(01)D2+(11)D3 相应地相应地C（11，01，01，11）状态图中编码器的状态变化为：状态图中编码

21、器的状态变化为： s0 s1 s3 s2 s0 从从s0开始再回到开始再回到s0，所得码序列称为结尾码字。这，所得码序列称为结尾码字。这要求输完信息序列后，还应再输入要求输完信息序列后，还应再输入mk0个全个全0信息信息元，使编码器回到全元，使编码器回到全0状态。状态。1101011138三、卷积码得距离度量三、卷积码得距离度量衡量卷积码的纠错性能可用其距离特性描述，但其衡量卷积码的纠错性能可用其距离特性描述，但其纠错能力与它采用的译码方法有关，不同的译码方纠错能力与它采用的译码方法有关，不同的译码方法有不同的距离度量。法有不同的距离度量。定义（最小汉明距离）：定义（最小汉明距离）：不同初始截

22、短码字子集之不同初始截短码字子集之间距离的最小值，为（间距离的最小值，为（n,k,m）卷积码的最小汉明）卷积码的最小汉明距离。距离。39 定理：任何相邻定理：任何相邻m+1段以内的错误个数，不段以内的错误个数，不多于多于 个，则最小距离为个，则最小距离为dmin的的（n0,k0,m）卷积码，总可以纠正。当然，）卷积码，总可以纠正。当然，若此卷积码用来检错，则一定可以检测出若此卷积码用来检错，则一定可以检测出m+1段相邻码段内段相邻码段内dmin1个错误。个错误。 定义：卷积码的第定义：卷积码的第j阶阶列距离列距离dj，是，是j+1段长段长截短码树上定义的最小汉明距离：截短码树上定义的最小汉明距

23、离：405 卷积码的译码卷积码的译码 代数译码：代数译码：译码方法具有一定的代数结构，译译码方法具有一定的代数结构，译码简单，便于实施。码简单，便于实施。 概率译码：概率译码：纠错能力强，但算法复杂。较著名纠错能力强，但算法复杂。较著名的有序列译码和维特比译码。的有序列译码和维特比译码。概率译码方法不仅基于码的代数结构基础上，概率译码方法不仅基于码的代数结构基础上，而且还利用了信道的统计特性，因而能充分而且还利用了信道的统计特性，因而能充分发挥卷积码的特点，使译码错误概率达到很发挥卷积码的特点，使译码错误概率达到很小。小。41一、维特比（一、维特比（Viterbi，VB）译码算法）译码算法 V

24、B译码算法是一种最大似然译码算法。译码算法是一种最大似然译码算法。 用栅格图或篱笆图可表示编码器状态转移用栅格图或篱笆图可表示编码器状态转移与时间的关系：与时间的关系：10，10，00，01，11，01，11）42 例：输入编码器的信息序列：例：输入编码器的信息序列： M（1011100） 则编码器输出的码序列：则编码器输出的码序列： C（11 10 00 01 10 01 11） 它相应于篱笆图中红线表示的一条路径。它相应于篱笆图中红线表示的一条路径。编码器送出码序列编码器送出码序列C，经信道传输后，送入，经信道传输后，送入译译码器的序列码器的序列RCE，译码器根据，译码器根据R，按最，按最

25、大似然译码准则力图找出编码器在篱笆图上大似然译码准则力图找出编码器在篱笆图上所走过的路径。所走过的路径。43 卷积码的译码过程就是译码器计算、寻找卷积码的译码过程就是译码器计算、寻找最大似然函数的过程。通过计算似然函数，最大似然函数的过程。通过计算似然函数，相当于每一步都是寻找与相当于每一步都是寻找与R有最小汉明距有最小汉明距离的路径，直接译出码字。离的路径，直接译出码字。 设（设（n0，k0，m）码编码器输入：）码编码器输入：m（m0，m1，.，mL1，0，00）其中其中mi（mi(1)，mi(2)，.，mi(k0)） i0，1，2，L1k0L位信息位信息k0m位全位全044 编码器输出的码

26、序列：编码器输出的码序列： C（C0，C1，CmL1） 其中其中Ci（Ci(1)，Ci(2)，Ci(no)） i0，1，2，Lm1 是长为是长为n0(Lm)的二元序列。的二元序列。显然，信息序列共有显然，信息序列共有2koL个，对应的码序列也个，对应的码序列也有有2koL个，则（个，则（n0，k0，m）码的篱笆图上）码的篱笆图上共有共有2koL条路径。条路径。45 在离散无记忆信道（在离散无记忆信道（DMC）中，发送）中，发送C变变成成R的概率：的概率：P(R/C) 取取C的对数似然函数的对数似然函数logbP(R/C)，称为，称为R与与C的的度量度量，用，用M(R/C)表示。表示。译码器按最

27、大似然译码准则力图寻找最大似译码器按最大似然译码准则力图寻找最大似然函数：然函数：或寻找有最大或寻找有最大度量度量的路径：的路径：46 已经证明：对已经证明：对BSC信道，最大度量的路径等信道，最大度量的路径等价于价于R有最小汉明距离的路径。即：有最小汉明距离的路径。即： 根据最大似然准则，可以把根据最大似然准则，可以把R与篱笆图上的与篱笆图上的2koL条路径的汉明距离逐个进行比较，条路径的汉明距离逐个进行比较，R与与哪条路径距离最小，就把哪条路径距离最小，就把R译成那个码序列。译成那个码序列。 即当即当d(R,Ci)d(R,Cj)时，将把时，将把R译成译成Ci。 但但L较大时，以上译码方法难

28、以实现。较大时，以上译码方法难以实现。47维特比译码算法的步骤：维特比译码算法的步骤：(1)(1)从某一时间单位从某一时间单位j jm m开始，对进入每一状态的所开始，对进入每一状态的所有长为有长为j j段分支的部分路径，计算段分支的部分路径，计算部分路径度量部分路径度量。对每一状态，挑选并存贮一条有最大度量的部分路对每一状态，挑选并存贮一条有最大度量的部分路径及其部分度量值，称此部分路径为径及其部分度量值，称此部分路径为留选留选( (幸存幸存) )路路径。径。(2)j(2)j增加增加l l，把此时刻进入每一状态的所有分支度量，把此时刻进入每一状态的所有分支度量，和同这些分支相连的前一时刻的留

29、选路径的度量相和同这些分支相连的前一时刻的留选路径的度量相加，得到了此时刻进入每一状态的留选路径，加以加，得到了此时刻进入每一状态的留选路径，加以存贮并删去其它所有路径，因此留选路径延长了一存贮并删去其它所有路径，因此留选路径延长了一个分支。个分支。 48(3)(3)若若jL+mjL+m，则重复以上各步，否则停止，则重复以上各步，否则停止，译码器得到了有最大路径度量的路径。译码器得到了有最大路径度量的路径。由此可知，在篱笆图上用由此可知，在篱笆图上用VB译码算法得到的译码算法得到的路径一定是一条最大似然路径，因而这种译路径一定是一条最大似然路径，因而这种译码方法是最佳的。码方法是最佳的。定理：

30、定理： 49例：例：编码器如图，编码器如图，输入信息序列：输入信息序列：M（1011100）输出码序列：输出码序列：C（11，10，00，01，10，01，11）通过通过BSC送入译码器的序列：送入译码器的序列：R （10，10，00，01，11，01，11）求利用求利用VB译码算法时，译码器输出的估值信息序列译码算法时，译码器输出的估值信息序列50解：解：VB译码器译译码器译R的过程：的过程：51由于由于d大，大，红色路径被删除红色路径被删除虽然虽然d相同，均为相同，均为3但绿色路径被舍去但绿色路径被舍去11527.第第7时刻接收子码时刻接收子码 R611能用以上有限状态组成的篱笆图描述其编

31、、译码过程的能用以上有限状态组成的篱笆图描述其编、译码过程的码称为网格码或篱笆码，也称码称为网格码或篱笆码，也称Trellis码，是码树的一个码，是码树的一个大类。大类。最后幸存最后幸存一条最大一条最大似然路径似然路径译码输出：译码输出：11,10,00,01,10,01,1110，10，00，01，11，01，11）53VB译码算法的特点：译码算法的特点：1）（）（n,k,m）卷积码编码器共有）卷积码编码器共有2km个状态，个状态，则译码器必有则译码器必有2km个存储器，存储个存储器，存储2km个幸存个幸存路径（或信息序列）以及每一单个路径与路径（或信息序列）以及每一单个路径与Rj的距离。译

32、码器的复杂性随的距离。译码器的复杂性随km指数增加，指数增加，一般选择一般选择m10。2）信息序列存储器存储的信息长度为）信息序列存储器存储的信息长度为kL，L很大时，译码器的存储量也随之增大，难以很大时，译码器的存储量也随之增大，难以实用。实用。54二、软判决二、软判决VB译码译码 把信道输出的信号进行把信道输出的信号进行Q（Q2m）电平量化，然）电平量化，然后再输入后再输入VB译码器，能适应这种译码器，能适应这种Q进制输入的进制输入的VB译码器称为软判决译码器称为软判决VB译码器。译码器。 软判决软判决VB译码器的结构和译码过程，完全与硬判译码器的结构和译码过程，完全与硬判决相同，只须在决相同，只须在 R与与C中用中用Q进制的值代替二进制进制的值代替二进制值即可。值即可。 软判决输出有更高的度量值，性能更好。一般采软判决输出有更高的度量值，性能更好。一般采用八电平均匀量化，可达最大似然译码性能。用八电平均匀量化，可达最大似然译码性能。556 调制与卷积码的结合（调制与卷积码的结合（T