编码理论第6章课件

编码理论第六章 卷积码李丽香卷积码的发展历史v1955年，埃利斯年，埃利斯(P.Elias)首次提出卷积码首次提出卷积码的概念的概念v1957年，年，J.M.Wozencraft提出卷积码的序提出卷积码的序列译码算法列译码算法v1963年，年，J.L.Massey提出较易实现的门限提出较易实现的门限译码算法译码算法v1967年，年，A.J.Viterbi提出卷积码的一种最提出卷积码的一种最大似然译码算法大似然译码算法v卷积码在深空通信、卫星通信、移动通讯卷积码在深空通信、卫星通信、移动通讯等领域得到了应用等领域得到了应用卷积码与分组码的区别v卷积码是同分组码相对应的另一大类纠错码卷积码是同分组码相对应的另一大类纠错码v卷积码必须用卷积码必须用序列逻辑电路序列逻辑电路来实现，更适用于前来实现，更适用于前向纠错系统向纠错系统v分组码是用分组码是用组合逻辑电路组合逻辑电路来实现来实现v有记忆性：有记忆性：在任意给定的时间单元内，卷积码编在任意给定的时间单元内，卷积码编码器输出的码器输出的n个码元，其中每个码元不仅与此单个码元，其中每个码元不仅与此单位时间内输入的位时间内输入的k个信息有关系，而且与此前连个信息有关系，而且与此前连续输入的续输入的m个信息有关系，称个信息有关系，称(n,k,m)卷积码卷积码v无记忆性：无记忆性：分组码编码器输出的分组码编码器输出的n个码元，仅与个码元，仅与此单位时间内输入的此单位时间内输入的k个信息有关系个信息有关系卷积码与分组码的区别v卷积码充分利用了各组信息之间的相关性，卷积码充分利用了各组信息之间的相关性，信息序列不被分段，而是被连续处理信息序列不被分段，而是被连续处理v通常，卷积码的通常，卷积码的n和和k比分组码的比分组码的n和和k要小要小的多的多v在同样的编码效率下，卷积码的性能优于在同样的编码效率下，卷积码的性能优于分组码分组码v在相似的纠错能力下，卷积码的实现比分在相似的纠错能力下，卷积码的实现比分组码简单组码简单离散序列的非循环卷积运算v定义：定义：设设f(n)和和g(n)是两个序列，则序列是两个序列，则序列f和和g的离的离散卷积运算为散卷积运算为v例子：例子：若若f=(10011),g=(111),则则f*g的计算过程如的计算过程如下下 (f*g)(0)=11001 111 +=1 (f*g)(1)=11001 111 +=1离散序列的非循环卷积运算 (f*g)(2)=11001 111 +=1 (f*g)(3)=11001 111 +=1 (f*g)(4)=11001 111 +=0离散序列的非循环卷积运算 (f*g)(5)=11001 111 +=0 (f*g)(6)=11001 111 +=1 故故 f*g=(1001111)二元(2,1,2)卷积码的编码器+D0D1+V(1)V(2)u图图6.1 二元二元(2,1,2)(2,1,2)卷积码的编码器的电路图卷积码的编码器的电路图二元(2,1,2)卷积码的编码器v该编码器主要由该编码器主要由m=2级移位寄存器，级移位寄存器，n=2个个模模2加法器组成加法器组成v所有的卷积码编码器都可以用这种类型的所有的卷积码编码器都可以用这种类型的线性前馈移位寄存器线性前馈移位寄存器来实现来实现(2,1,2)卷积码的冲激响应v该编码器的冲激响应就是通过令该编码器的冲激响应就是通过令u=(100)所得所得到的两个输出序列到的两个输出序列v因为编码器有因为编码器有m个存储单元，所以冲激响应个存储单元，所以冲激响应(生生成序列成序列)至多持续至多持续m+1个时间单元，且可以写成个时间单元，且可以写成v其中上标表示第几个输出端其中上标表示第几个输出端v图图6.1的的(2,1,2)卷积码的冲激响应为卷积码的冲激响应为g(1)=(111),g(2)=(101)v另外，冲激响应向量还可以表示输入、移位寄另外，冲激响应向量还可以表示输入、移位寄存器和输出之间的连接关系，存器和输出之间的连接关系，1表示有连接，表示有连接，0表示没有连接表示没有连接(2,1,2)卷积码的输出序列v信息序列信息序列u=(u1,u2,u3,)每次进入编码器每次进入编码器1比特比特v编码器的两个输出序列编码器的两个输出序列v可以通过输入序列可以通过输入序列u和编码器的两个冲激响应作和编码器的两个冲激响应作卷积运算而得到卷积运算而得到v若若u=(1011),图图6.1的的(2,1,2)卷积码的冲激响应为卷积码的冲激响应为g(1)=(111),g(2)=(101)，则该卷积码的输出序列为则该卷积码的输出序列为V(1)=u*g(1)=(110001),V(2)=u*g(2)=(100111)(2,1,2)卷积码的码字v输出序列分别为输出序列分别为的的(2,1,m)的卷积码的码字，为的卷积码的码字，为V(1)和和V(2)的交错的交错v即即v举例：举例：图图6.1的的(2,1,2)卷积码，若卷积码，若u=(1011),冲激冲激响应为响应为g(1)=(111),g(2)=(101)，该卷积码的输出序该卷积码的输出序列为列为V(1)=u*g(1)=(110001),V(2)=u*g(2)=(100111)，得到的码字为得到的码字为v=(11,10,00,01,01,11)(2,1,2)卷积码的编码方程v以以u=(u1,u2,u3,)为输入为输入,以以为生成序列的为生成序列的(2,1,m)卷积码的输出序列分别由方卷积码的输出序列分别由方程程V(1)=u*g(1)和和V(2)=u*g(2)得到得到v举例：举例：图图6.1的的(2,1,2)卷积码的编码方程为卷积码的编码方程为v另外，编码方程中每一项的系数，还可以表示输另外，编码方程中每一项的系数，还可以表示输入、移位寄存器和输出之间的连接关系，入、移位寄存器和输出之间的连接关系，1表示表示有连接，有连接，0表示没有连接表示没有连接(2,1,2)卷积码的生成矩阵v(2,1,m)卷积码卷积码的生成矩阵：将生成序列的生成矩阵：将生成序列g(1)和和g(2)交织后形成的半无限矩阵交织后形成的半无限矩阵v举例：举例：图图6.1的的(2,1,2)卷积码冲激响应为卷积码冲激响应为g(1)=(111),g(2)=(101)，该码，该码的生成矩阵为的生成矩阵为(2,1,2)卷积码的生成矩阵v以以u=(u1,u2,u3,)为输入为输入,G为生成矩阵的为生成矩阵的(2,1,m)的卷积码的码字为的卷积码的码字为V=uGv举例：举例：图图6.1的的(2,1,2)卷积码，若卷积码，若u=(1011),则则码码字为字为v=(11,10,00,01,01,11)二元(2,1,3)卷积码的编码器+D0D1+V(1)V(2)u图图6.2 二元二元(2,1,3)(2,1,3)卷积码的编码器的电路图卷积码的编码器的电路图D2(2,1,3)卷积码的冲激响应v该编码器的冲激响应就是通过令该编码器的冲激响应就是通过令u=(100)所得所得到的两个输出序列到的两个输出序列v因为编码器有因为编码器有m个存储单元，所以冲激响应个存储单元，所以冲激响应(生生成序列成序列)至多持续至多持续m+1个时间单元，且可以写成个时间单元，且可以写成v其中上标表示第几个输出端其中上标表示第几个输出端v图图6.2的的(2,1,3)卷积码的冲激响应为卷积码的冲激响应为g(1)=(1011),g(2)=(1111)v另外，冲激响应向量还可以表示输入、移位寄另外，冲激响应向量还可以表示输入、移位寄存器和输出之间的连接关系，存器和输出之间的连接关系，1表示有连接，表示有连接，0表示没有连接表示没有连接(2,1,3)卷积码的输出序列v信息序列信息序列u=(u1,u2,u3,)每次进入编码器每次进入编码器1比特比特v编码器的两个输出序列编码器的两个输出序列v可以通过输入序列可以通过输入序列u和编码器的两个冲激响应作和编码器的两个冲激响应作卷积运算而得到卷积运算而得到v若若u=(10111),图图6.2的的(2,1,3)卷积码的冲激响应为卷积码的冲激响应为g(1)=(1011),g(2)=(1111)，则该卷积码的输出序列则该卷积码的输出序列为为V(1)=u*g(1)=(10000001),V(2)=u*g(2)=(11011101)(2,1,3)卷积码的码字v输出序列分别为输出序列分别为的的(2,1,m)的卷积码的码字，为的卷积码的码字，为V(1)和和V(2)的交错的交错v即即v举例：举例：图图6.2的的(2,1,3)卷积码，若卷积码，若u=(10111),冲激冲激响应为响应为g(1)=(1011),g(2)=(1111)，该卷积码的输出该卷积码的输出序列为序列为V(1)=u*g(1)=(10000001),V(2)=u*g(2)=(11011101)，得到的码字为，得到的码字为v=(11,01,00,01,01,01,00,11)(2,1,3)卷积码的编码方程v以以u=(u1,u2,u3,)为输入为输入,以以为生成序列的为生成序列的(2,1,m)卷积码的输出序列分别由方卷积码的输出序列分别由方程程V(1)=u*g(1)和和V(2)=u*g(2)得到得到v举例：举例：图图6.2的的(2,1,3)卷积码的编码方程为卷积码的编码方程为v另外，编码方程中每一项的系数，还可以表示输另外，编码方程中每一项的系数，还可以表示输入、移位寄存器和输出之间的连接关系，入、移位寄存器和输出之间的连接关系，1表示表示有连接，有连接，0表示没有连接表示没有连接(2,1,3)卷积码的生成矩阵v(2,1,m)卷积码卷积码的生成矩阵：将生成序列的生成矩阵：将生成序列g(1)和和g(2)交织后形成的半无限矩阵交织后形成的半无限矩阵v举例：举例：图图6.2的的(2,1,3)卷积码冲激响应为卷积码冲激响应为g(1)=(1011),g(2)=(1111)，该码，该码的生成矩阵为的生成矩阵为(2,1,3)卷积码的生成矩阵v以以u=(u1,u2,u3,)为输入为输入,G为生成矩阵的为生成矩阵的(2,1,m)的卷积码的码字为的卷积码的码字为V=uGv举例：举例：图图6.2的的(2,1,3)卷积码，若卷积码，若u=(10111),则则码码字为字为v=(11,01,00,01,01,01,00,11)二元(3,2,1)卷积码的编码器+D0+V(1)V(2)u图图6.3 二元二元(3,2,1)(3,2,1)卷积码的编码器的电路图卷积码的编码器的电路图+D0V(3)V二元(3,2,m)卷积码的输入序列v该编码器有该编码器有2个输入，个输入，3个输出，主要由个输出，主要由m=1级移级移位寄存器，位寄存器，n=3个模个模2加法器组成加法器组成v对于一般的对于一般的(3,2,m)卷积码，由于卷积码，由于k=2，即每次有，即每次有2比特进入编码器，所以输入序列比特进入编码器，所以输入序列u可以写成可以写成v或分开写成或分开写成2 2个序列个序列(3,2,m)卷积码的冲激响应v令令u(1)=(100),得到得到3个输出序列个输出序列(长度均为长度均为m+1)v再令再令u(2)=(100),又得到又得到3个输出序列个输出序列v则称下面的序列为则称下面的序列为(3,2,m)卷积码的生成序列卷积码的生成序列(3,2,1)卷积码的冲激响应v举例：举例：图图6.3的的(3,2,1)卷积码的生成序列为卷积码的生成序列为(3,2,1)卷积码的码字v输出序列为输出序列为的的(3,2,m)的卷积码的码字，为的卷积码的码字，为v举例：举例：图图6.3的的(3,2,1)卷积码，若卷积码，若u(1)=(101),u(2)=(110)v得到的码字为得到的码字为v=(110,000,001,111)(3,2,1)卷积码的编码方程v图图6.3的的(3,2,1)卷积码的编码方程为卷积码的编码方程为v另外，编码方程中每一项的系数，还可以表示输另外，编码方程中每一项的系数，还可以表示输入、移位寄存器和输出之间的连接关系，入、移位寄存器和输出之间的连接关系，1表示表示有连接，有连接，0表示没有连接表示没有连接(3,2,1)卷积码的生成矩阵v(3,2,m)卷积码卷积码的生成矩阵：生成序列为的生成矩阵：生成序列为v举例：举例：图图6.3的的(3,2,1)的生成矩阵为的生成矩阵为(3,2,m)卷积码的码字v以以u为输入为输入,G为生成矩阵的为生成矩阵的(3,2,m)的卷积码的码的卷积码的码字为字为V=uGv举例：举例：图图6.3的的(3,2,1)卷积码，若卷积码，若u(1)=(101),u(2)=(110),即即u=(11,01,10),则则码字为码字为V=uG=(110,000,001,111)(n,k,m)卷积码的生成矩阵v(3,2,m)卷积码卷积码的生成矩阵为的生成矩阵为v其中每个其中每个GL都是一个都是一个kn阶子阵阶子阵卷积码编码器的存储级数v对于对于(n,k,m)卷积码，图卷积码，图6.1-6.3这几个例子充分表这几个例子充分表明，当明，当k1时，编码器及用来描述它的符号都比时，编码器及用来描述它的符号都比较复杂，并且该编码器所含的较复杂，并且该编码器所含的k个移位寄存器的个移位寄存器的长度未必相同长度未必相同v例如：例如：图图6.3中，中，m=1v存储级数：存储级数：若若ki是第是第i个移位寄存器的长度，则称个移位寄存器的长度，则称所有所有k个移位寄存器中的最大长度为存储级数，个移位寄存器中的最大长度为存储级数，即编码器的存储级数即编码器的存储级数m定义为定义为卷积码编码器的约束长度v对于对于(n,k,m)卷积码，编码器中每个信息位要保持卷积码，编码器中每个信息位要保持m+1时间个单位，每个时间单位都可以影响编码时间个单位，每个时间单位都可以影响编码器输出中的任何一个，这由移位寄存器的连接决器输出中的任何一个，这由移位寄存器的连接决定定v约束长度：约束长度：对于对于(n,k,m)卷积码，编码器的约束长卷积码，编码器的约束长度定义为度定义为v约束长度可以解释成约束长度可以解释成1比特信息对编码器输出可比特信息对编码器输出可以造成影响的最大数目以造成影响的最大数目v例如：例如：图图6.1中中(2,1,2)卷积码卷积码nA=6，图，图6.2中中(2,1,3)卷积码卷积码nA=8，图，图6.3中中(3,2,1)卷积码卷积码nA=6卷积码的码速率v对于对于(n,k,m)卷积码，其码速度卷积码，其码速度r=k/nv注意：注意：对于对于(n,k,m)卷积码，信息序列为有限长卷积码，信息序列为有限长kL时，对应的码字长度为时，对应的码字长度为n(L+m)v例如：例如：图图6.1中中(2,1,2)卷积码，若卷积码，若L=4，信息序列，信息序列长度为长度为4，则码字长度为，则码字长度为12；图；图6.2中中(2,1,3)卷积卷积码，若码，若L=5，信息序列长度为，信息序列长度为5，则码字长度为，则码字长度为16；图；图6.3中中(3,2,1)卷积码，若卷积码，若L=3，信息序列长度，信息序列长度为为3，则码字长度为，则码字长度为12v其中其中nm个输出是为了使得编码器的存储器最后个输出是为了使得编码器的存储器最后全部能够清零全部能够清零卷积码的码速率v若把卷积码看成是由生成矩阵得到的线性分组码，若把卷积码看成是由生成矩阵得到的线性分组码，则其码速度则其码速度r=kL/n(L+m)v注意：注意：当当L远大于远大于m的时候，的时候，L/(L+m)近似等于近似等于1，此时，卷积码和分组码的速率就近似相等，此时，卷积码和分组码的速率就近似相等v速率损失系数：速率损失系数：当当L较小的时候，信息传输的有较小的时候，信息传输的有效率，即效率，即kL/n(L+m)将比码速率降低一个分数将比码速率降低一个分数v称称m/(L+m)为速率损失系数。为了使得速率损失为速率损失系数。为了使得速率损失系数尽量小，一般假定系数尽量小，一般假定L远大于远大于m卷积码的码速率v例例1：图图6.2中中(2,1,3)卷积码，若卷积码，若L=5，则速率损失，则速率损失系数为系数为m/(L+m)=3/(5+3)=3/8=37.5%v例例2：图图6.2中中(2,1,3)卷积码，若卷积码，若L=1000，则速率，则速率损失系数为损失系数为m/(L+m)=3/(1000+3)=3/10030.299%卷积码的多项式描述方法v在任一线性系统中，涉及卷积的时域运算，都可在任一线性系统中，涉及卷积的时域运算，都可以转换成多项式乘法的变换域运算来实现以转换成多项式乘法的变换域运算来实现v由于卷积码是线性系统，编码方程中的每一序列由于卷积码是线性系统，编码方程中的每一序列都可以用相应的多项式来表示，卷积运算可以用都可以用相应的多项式来表示，卷积运算可以用多项式乘法运算来替代多项式乘法运算来替代v在二元序列的多项式表示中，序列本身可以用多在二元序列的多项式表示中，序列本身可以用多项式的系数来表示，序列项式的系数来表示，序列a=(a0a1)被表示成多被表示成多项式项式(2,1,m)卷积码的多项式描述v信息序列：信息序列：u表示成表示成u(x)v生成多项式：生成多项式：g(1)表示成表示成g(1)(x),g(2)表示成表示成g(2)(x)v输出序列：输出序列：V(1)表示成表示成V(1)(x),V(2)表示成表示成V(2)(x)v码字：码字：V表示成表示成V(x)v于是于是V(1)(x)=u(x)g(1)(x)，V(2)(x)=u(x)g(2)(x)v码字码字V(x)=V(1)(x2)+xV(2)(x2)(2,1,2)卷积码的多项式描述v例如：例如：图图6.1的的(2,1,2)卷积码卷积码v信息序列：信息序列：若若u=(1011),则则u(x)=1+x2+x3v生成多项式：生成多项式：冲激响应为冲激响应为g(1)=(111),g(2)=(101),则则g(1)(x)=1+x+x2,g(2)(x)=1+x2v于是于是,编码方程为编码方程为V(1)(x)=u(x)g(1)(x)=(1+x2+x3)(1+x+x2)=1+x+x5，V(2)(x)=u(x)g(2)(x)=(1+x2+x3)(1+x2)=1+x3+x4+x5v码字为码字为V(x)=V(1)(x2)+xV(2)(x2)=1+x+x2+x7+x9+x10+x11(2,1,3)卷积码的多项式描述v例如：例如：图图6.2的的(2,1,3)卷积码卷积码v信息序列：信息序列：若若u=(10111),则则u(x)=1+x2+x3+x4v生成多项式：生成多项式：冲激响应为冲激响应为g(1)=(1011),g(2)=(1111),则则g(1)(x)=1+x2+x3,g(2)(x)=1+x+x2+x3v于是于是,编码方程为编码方程为V(1)(x)=u(x)g(1)(x)=(1+x2+x3+x4)(1+x2+x3)=1+x7，V(2)(x)=u(x)g(2)(x)=(1+x2+x3+x4)(1+x+x2+x3)=1+x+x3+x4+x5+x7v码字为码字为V(x)=V(1)(x2)+xV(2)(x2)=1+x+x3+x7+x9+x10+x11+x14+x15(n,k,m)卷积码的转移函数矩阵vu(x)=(u(1)(x),u(2)(x),u(k)(x)vV(x)=(V(1)(x),V(2)(x),V(n)(x)v在在k1的的(n,k)码中，对码中，对k个输入的每一个，都有个输入的每一个，都有n个生成多项式个生成多项式v由于编码器是线性系统由于编码器是线性系统,u(i)(x)表示第表示第i个输入序列个输入序列,V(j)(x)表示第表示第j个输出序列个输出序列,所以生成多项式所以生成多项式 可以看成是输入可以看成是输入i和输出和输出j之间的编码器转之间的编码器转移函数移函数v同任何有同任何有k个输入个输入n个输出的线性系统一样，总共个输出的线性系统一样，总共有有kn个转移函数个转移函数(n,k,m)卷积码的转移函数矩阵vkn阶转移函数矩阵为阶转移函数矩阵为v于是，码字于是，码字V(x)=u(x)G(x)v其中其中u(x)=(u(1)(x),u(2)(x),u(k)(x)，V(x)=(V(1)(x),V(2)(x),V(n)(x)v并路之后，码字变成并路之后，码字变成V(x)=V(1)(xn)+xV(2)(xn)+xn-1V(n)(xn)(n,k,m)卷积码的转移函数矩阵v例如：图例如：图6.3的的(3,2,1)卷积码，卷积码，23阶转移函数矩阶转移函数矩阵为阵为v对于输入序列对于输入序列u(1)(x)=1+x2,u(2)(x)=1+x v于是，编码方程于是，编码方程v并路之后，码字变成并路之后，码字变成V(x)=V(1)(x3)+xV(2)(x3)+x2V(3)(xn)=1+x+x8+x9+x10+x11