第5章卷积码 分组码在编码时，先将输入信息码元序列分为长度为k的段，然后按照编码规则，给每段附加上r位监督码元，构成长度为n的码组。各个码组间没有约束关系，即监督码元只监督本码组的码元有无错码。因此在解码时各个接收码组也是独立地进行解码的。从信息论角度而言，一方面信息流分割为独立码块而不能利用组间的相关信息，且编码定理表明分组码的码长n越长越好，另一方面译码运算量却随着码长n的增加而增加。 为了解决上述矛盾，提出了另外一种编码，称为卷积码。卷积码的特点是信息进行编码时，信息组之间不是独立编码的，而是具有一定的相关性，系统译码时可以利用这种相关性进行译码。 卷积码是一种非常重要的差错控制编码。 卷积码编码时虽然也是将k比特的信息段编成n比特的码组，但是监督码元不仅和当前的信息段有关，而且与前面若干时刻输入至编码器的信息段有关。同样，卷积码译码时也要结合当前时刻和以前各时刻接收到的码段来提取有关信息。由于卷积码充分利用了前后码段之间的相关性，故与分组码比较，卷积码的性能更好，译码更容易。 5.1卷积码的基本概念 卷积码编码时，首先将信息序列划分为长度为k的组，当前时刻编码输出不仅取决于当前输入的信息组，而且与前若干时刻的信息组有关。为了表示这种关联性，卷积码一般表示为(n,k,m)，其中，k为信息组的长度，n表示每组信息对应输出的码长度，m表示与此前输入的m个信息关联，N=m+1称为信息组约束长度。与分组码一样，(n,k,m)卷积码的码率为R=k/n。 卷积码编码器的一般框图如图51所示。输入的信息序列被分成长度为k的段，并经过串/并转换输入到离散线性系统的k个输入端。该系统的输出端为n个(一般n＞k)，且系统最大延时为m。输出的n个编码数字经过并/串转换送入信道就完成了编码过程，这就是可表示为(n,k,m)码的典型卷积码。一般选n和k较小，但m值较大(m为10左右)。 图51卷积码编码器原理图 卷积码的纠错性能随m的增大而增大，而复杂度随m的增大呈指数增加。在编码器复杂性相当的情况下，卷积码的性能优于分组码。但卷积码没有分组码那样严密的数学分析手段，目前大多通过计算机进行好码的搜索。 卷积码编码器是一个由k个输入端、n个输出端及m个移位寄存器所构成的有限状态有记忆系统。 描述卷积码的方法很多，大致可划分为两大类： 解析法和图形法。解析法包括离散卷积码法、矩阵生成法及码多项式法等，主要用于编码部分的描述； 图形法包括状态图法、树图法及网格法等，主要用于译码的描述和说明。 5.2卷积码的编码过程 图52给出了一个二进制卷积码的编码器。若每一时间单位输入编码器一个新的信息元ui，且存储器内的数据往右移一位，则ui一方面直接输出至信道，另一方面与前两个单位时间送入的信息元ui-1和ui-2按图52中线路所确定的规则进行运算，得到此时刻的两个输出(校验元)c1i和c2i，跟随在ui后面组成一个子码ci=(uic1ic2i)送入信道。由图52可知 c1i=uiui-1 c2i=uiui-2(51) 下一个时间单位输入的信息元为ui+1，其相应的两个输出(校验元) c1i+1=ui+1ui c2i+1=ui+1ui-1 组成第二个子码ci+1=(ui+1c1i+1c2i+1)送至信道，如此循环。在每一时间单位，送入编码器k(这里为1)个信息元，编码器就送出相应的n(这里为3)个码元组成一个子码ci送入信道，在卷积码中，这n个码元组成的子码ci有时也称卷积码的一个码段或子组。 图 52(3,1,2)卷积码编码器 由式(51)和图52可知，用这种卷积码编码器输出的每一子码中的校验元，是此时刻输入的信息元与前m(这里为2)个子码中信息元的模2加，它们是线性关系，所以由这类编码器编出的卷积码是线性码。 当m=0时，卷积码就可以被看作一个分组码，此时编码系统就是一个无记忆系统。 下面用具体的例子来说明二元域上卷积码的编码过程。 例51如图53给出一个(2,1,3)卷积码编码器结构，此时n=2，k=1， m=3，编码速率R=k/n=1/2，约束长度N=m+1=4。求该卷积码编码器的输出。 图53(2,1,3)卷积码编码器结构 卷积码编码时，在信息输入的同时，移位寄存器组进行信息移位，原来最低位置的信息移往下一个寄存器组，最后一个寄存器组的信息移出。移位操作结束后，编码器输出寄存器内容的运算结果，经过n节拍即可输出编码器当前的编码码字。 该编码器由三个移位寄存器和两个模2加法器组成，每输入一个码元就会产生两个输出，输出端第j时刻分别由下式确定： c1j=ujuj-2uj-3 c2j=ujuj-1uj-2uj-3(52) 假设输入信息序列为 u=(u0u1u2…)(53) 则对应输出的两码组为 c1=(c10c11c12…) c2=(c20c21c22…)(54) 最终的编码输出是在上下两码组中交替取值 c=(c10c20c11c21c12c22…)(55) 假设输入为u=(10111)，编码开始前先对移位寄存器进行复位(即置零)，输入的顺序为10111，则编码的过程结合式(52)、式(53)、式(54)为 （1） 输入uj=1，则c1j=ujuj-2uj-3=100=1，则 c2j=ujuj-1uj-2uj-3=1000=1 编码输出为11。 （2） 输入uj+1=0，则c1j+1=uj+1uj-1uj-2=000=0，则 c2j+1=uj+1ujuj-1uj-2=0100=1 编码输出为01。 （3） 输入uj+2=1，则c1j+2=uj+2ujuj-1=110=0，则 c2j+2=uj+2uj+1ujuj-1=1010=0 编码输出为00。 （4） 输入uj+3=1，则c1j+3=uj+3uj+1uj=101=0，则 c2j+3=uj+3uj+2uj+1mj=1101=1 编码输出为01。 （5） 输入uj+4=1，则c1j+4=uj+4uj+2uj+1=110=0，则 c2j+4=uj+4uj+3uj+2uj+1=1110=1 编码输出为01。 所以编码器的输出为1101000101，由于是1/2码率，所以共有10位输出。 如果考虑信息序列输入完移位寄存器的清零位，即增加3位零输入，则有如下几种： （6） 输入uj+5=0，则c1j+5=uj+5uj+3uj+2=011=0，则 c2j+5=uj+5uj+4uj+3uj+2=0111=1 编码输出为01。 （7） 输入uj+6=0，则c1j+6=uj+6uj+4uj+3=011=0，则 c2j+6=uj+6uj+5uj+4uj+3=0011=0 编码输出为00。 （8） 输入uj+7=0，则c1j+7=uj+7uj+5uj+4=001=1，则 c2j+7=uj+7uj+6uj+5uj+4=0001=1 编码输出为11。 故加入清零的码元后，编码器的最终输出为1101000101010011。 例52图54是(3,2,2)系统卷积码编码器，分析输入为u=(100000)和u=(010000)时的输出码序列。 例52 图54(3,2,2)系统卷积码编码器 由图54可知 c1i=u1i，c2i=u2i，c3i=u1iu1i-1u2i-1u2i-2 第i时刻的信息段ui=（u1iu2i），码段ci=（c1ic2ic3i），编码器由两个移位寄存器构成，所以是(3,2,2)码，输入u=(100000)的编码过程如表51所示，输出码序列c=(101001000)。 表51(3,2,2)卷积码编码过程 输入u 移存器初态 移存器次态 输出c 10 00 01 101 00 01 00 001 00 00 00 000 同理可得输入u=(010000)的编码输出c=(010001001)。可以看出码段的左边两个码元和输入的两个信息元始终一致，是系统码。 5.3卷积码的数学描述 5.3.1卷积码的码多项式法描述 卷积码的一般编码器如图55所示。在某一时刻i,输入到编码器的是由k个信息元组成的信息组ui，相应的输出序列是由n个码元组成的子码ci。若输入的信息序列u0u1u2u3…ui…是一个半无限序列，则由卷积码编码器输出的序列，也是一个由各子码c0c1c2c3…ci…组成的半无限序列，称此序列为卷积码的一个码序列或码字。 图55卷积码编码器 类似于前面的表示，可以将输入的序列对应写成多项式的形式。 若u=(u0u1u2u3…)，则 u(x)=u0+u1x+u2x2+u3x3+…(56) 所以有 u=(10111)→u(x)=1+x2+x3+x4(57) 在分析中，可以用 g1k=(g1k,0g1k,1g1k,2…g1k,m) g2k=(g2k,0g2k,1g2k,2…g2k,m)  gnk=(gnk,0gnk,1gnk,2…gnk,m)(58) 来表示第k个输入端在输出端c1，c2，…，cn的求和式的系数，则对于图53的卷积码编码器，k=1，为了书写简便，可以忽略k的角标。由式（52）可得 c1j=1·uj0·uj-11·uj-21·uj-3 c2j=1·uj1-uj-11·uj-21·uj-3 所以有 g1=(1011)，g2=(1111) 对应的多项式为 g1(x)=1+x2+x3，g2(x)=1+x+x2+x3 编码后的多项式为(乘积后合并也是模2加) c1=u(x)·g1(x) c2=u(x)·g2(x)(59) 所以有 c1=u(x)·g1(x)=(1+x2+x3+x4)(1+x2+x3) =1+x2+x3+x4+x2+x4+x5+x6+x3+x5+x6+x7=1+x7 c2=u(x)·g2(x)=(1+x2+x3+x4)(1+x+x2+x3) =1+x2+x3+x4+x+x3+x4+x5+x2+x4+x5+x6+x3+x5+x6+x7 =1+x+x3+x4+x5+x7 故对应的码序列为 c1=(10000001) c2=(11011101) 则编码器的输出为1101000101010011。 5.3.2卷积码的矩阵生成法描述 以如图56所示的(2,1,2)卷积码为例来讨论生成矩阵。 图56(2,1,2) 卷积码编码器 由图56可列出表达式。 设 u=(u0u1u2…) 则 c1i=uiui-1ui-2，c2i=uiui-2，c1=c10c11c12…，c2=c20c21c22… c=c10c20c11c21c12c22… 假设移位寄存器初始状态全为0，当输入信息序列u=(100)时，编码器的工作过程如表52所示。 表52(2,1,2)卷积码编码过程 输入u 移存器初态 移存器次态 输出c 1 00 10 11 0 10 01 10 0 01 00 11 输入信息序列u=(100)时，输出码字c=(111011)。 假设移位寄存器初始状态全为0，则有 c10=u0c20=u0 c11=u1u0c21=u1 c12=u2u1u0c22=u2u0 c13=u3u2u1c23=u3u1  上述方程组的矩阵形式为 c=［c10c20c11c21c12c22…］=［u0u1u2u3…］·11101100… 00111011… 00001110… 00000011…  即 c=uG∞(510) G∞称为(2,1,2)卷积码的生成矩阵，这是一个半无限矩阵，重写为 G∞=111011 1110110 111011 0111011  仔细观察G∞可发现它的每一行都是前一行右移n位的结果，也就是说，它完全是由矩阵的第一行确定的。将第一行取出并表示为 g∞=［11101100…］(511) g∞称为该码的基本生成矩阵，通过与表52比较，g∞其实就是当u=(100…0)，即输入信息序列为冲激序列时卷积码编码器的冲激响应。 令输入信息序列为u=(10101)，则输出码字 c=uG∞=［10101］111011 1110110 111011 0111011 111011… =［11100010001011…］ 再如例52所示的(3,2,2)系统卷积码，当u=(100000…)时，相应的冲激响应为c=(101001000…)； 当u=(010000…)时，c=(010001001…)。 由u=(100000…)和u=(010000…)的冲激响应，得该码的基本生成矩阵为 g∞=101001000… 010001001… 将g∞作为生成矩阵G∞的最上面两行，并经位移得该码的生成矩阵为 G∞=101001000 010001001 1010010000 010001001 101001000 010001001 0101001000 010001001  显然，若输入信息序列u=(10110111…)，则相应的输出码序列应为 c=uG∞=［10110111…］101001000000000000 010001001000000000 000101001000000000 000010001001000000 000000101001000000 000000010001001000 000000000101001000 000000000010001001 … =［101110010111001001…］ 一般情况下，(n,k,m)卷积码的生成矩阵可表示为 G∞=G0G1G2…Gm G0G1…Gm-1Gm0 G0…Gm-2Gm-1Gm 0(512) 基本生成矩阵为 g∞=G0G1G2…Gm0…(513) 其中，生成子矩阵为 Gl=g11,lg21,l…gn1,l g12,lg22,l…gn2,l  g1k,lg2k,l…gnk,l（0≤l≤m）(514) 生成矩阵中每一行的分组数(即码段数)为编码的约束长度，矩阵的总行数取决于输入信息序列的长度。 例53由例51给出的(2,1,3)卷积码编码器结构， n=2，k=1，m=3，可知 c1j=ujuj-2uj-3 c2j=ujuj-1uj-2uj-3 则有 g1=(1011)，g2=(1111) Gl=g11,lg21,l…gn1,l g12,lg22,l…gn2,l … g1k,lg2k,l…gnk,l=g11,lg21,l G0=［g11,0g21,0］=11，G1=［g11,1g21,1］=01 G2=［g11,2g21,2］=11，G3=［g11,3g21,3］=11 所以基本生成矩阵为 g∞=G0G1G2…Gm0…=11011111… 所以生成矩阵为 G=11011111 11011111 11011111 11011111 11011111 当输入为u=(10111)时，有 c=uG=［10111］11011111 11011111 11011111 11011111 11011111 =［1101000101010011］ 例54如图57是一个(3,2,1)卷积码编码器结构， n=3，k=2，m=1。编码速率为R=2/3，假设输入为u=(110110)，求编码器的输出。 图57(3,2,1)卷积码编码器结构 图57中的编码器有两个输入端，所以分析会更复杂一些，但是分析过程更具有代表性。 （1） 矩阵生成法。 第一个输入端与三个输出端的关系为 c1,1j=u1ju1j-1，c1,2j=u1j，c1,3j=u1ju1j-1 第二个输入端与三个输出端的关系为 c2,1j=u2j-1，c2,2j=u2ju2j-1，c2,3j=0 也就是 g11=u1ju1j-1，g21=u1j，g31=u1ju1j-1 g12=u2j-1，g22=u2ju2j-1，g32=0 可知 g11,0=1，g11,1=1 g21,0=1，g21,1=0 g31,0=1，g31,1=1 g12,0=0，g12,1=1 g22,0=1，g22,1=1 g32,0=0，g32,1=0 因为k=2，所以 Gl=g11,lg21,lg31,l g12,lg22,lg32,l(0≤l≤m) 因为m=1，所以 G0=111 010，G1=101 110 于是 G∞=G0G1G2…Gm G0G1…Gm-1Gm0 G0…Gm-2Gm-1Gm 0=G0G1 G0G1 G0G1 =111 010101 110 111 010101 110 111 010101 110 所以 c=uG=［110110］111 010101 110 111 010101 110 111 010101 110=［101001001101］ （2） 多项式生成法。 因为输入序列为u=(110110)，所以经过串/并转换可以得到两个输入子序列 u1=(101)，u2=(110)，所以得到输入序列的多项式形式 u1=(101)→u1(x)=1+x2 u2=(110)→u2(x)=1+x 由于 g11=u1ju1j-1，g21=u1j，g31=u1ju1j-1 g12=u2j-1，g22=u2ju2j-1，g32=0 得 g11=(11)→g11(x)=1+x g21=(10)→g21(x)=1 g31=(11)→g31(x)=1+x g12=(01)→g12(x)=x g22=(11)→g22(x)=1+x g32=(00)→g32(x)=0 G=g11,lg21,lg31,l g12,lg22,lg32,l=1+x11+x x1+x0 c=u1(x) u2(x)T·G(x)=1+x21+x·1+x11+x x1+x0 =1+x301+x+x2+x3 所以有 c1(x)=1+x3→c1=(1001) c2(x)=0→c2=(0000) c3(x)=1+x+x2+x3→c3=(1111) 所以，卷积码编码器的输出为c=(101001001101)，最终的输出结果与矩阵法输出结果相同。 5.3.3卷积码的离散卷积法描述 对于例51，编码后多项式表示为 c1(x)=u(x)·g1(x) c2(x)=u(x)·g2(x)(515) 其对应的编码方程为 c1=ug1 c2=ug2(516) 式中，“”表示卷积运算，卷积码因此而得名。g1和g2表示编码器的两个冲激响应。 由前面的分析知g1=(1011)，g2=(1111)， 且u=(10111)，最后求得 c1=ug1=(10111)(1011)=(10000001) c2=ug2=(10111)(1111)=(11011101) 交织后可得编码器的输出为1101000101010011。 5.4卷积码的图形描述 5.4.1状态图 编码过程可以用状态图来表示。在卷积码编码器中，寄存器任一时刻存储的数据称为编码器的一个状态，随着信息序列的不断输入，编码器的状态在不断变化，同时输出的码元序列也相应地发生改变。所谓状态图就是反映编码器中寄存器存储状态转移的关系图，它用编码器中寄存器的状态及其随输入序列而发生的转移关系来描述编码过程。 例55图56的(2,1,2)卷积码编码器由两级移位寄存器组成，因此状态只有4种可能，即00、10、01、11，用符号Si表示，分别将其对应为S0、S1、S2和S3。 表53和图58分别为(2,1,2)卷积码的状态表和状态图。 状态图中，用实线表示信息0输入，虚线表示1输入，若输入信息u=(10101)，状态转移为S0→S1→S2→S1→S2→S1→S2→S0，相应输出码元序列为(11100010001011)。 编码器输出的码元序列是在信息序列的第一个码元输入直到最后一个码元完全移出移位寄存器所产生的。要求有用信息序列输入完毕后，应再向编码器输入mk个全零码元，所以最终状态应回到初始状态S0。 表53(2，1，2)卷积码的状态表 输入u初态Si 次态Sj输出c 0000000 1001011 0100110 1101101 0010011 1011000 0110101 1111110 图58(2,1,2)卷积码的状态图 5.4.2树图 树图结构是由状态图按时间展开的。即将输入信息序列u的输入顺序按时间顺序（l=0,1,2,…）展开，并展开所有可能的输入输出情况。 如果(n,k,m)卷积码编码器的输入信息序列是半无限长序列，则它的输出码元序列也应是半无限长序列，这种半无限长序列的输入、输出编码过程可用半无限码树来表示。 如图59所示为图56的(2,1,2)卷积码的树图。 图59(2,1,2)卷积码的树图 图59中，节点处符号为移存器状态，分支上的数据为输出码段，上分支为输入信息0，下分支为输入信息1。设移位寄存器初始状态S0=00，当输入信息元u0=0时，由树根出发走上支路，移存器右移一位，状态仍为S0，输出码段c0=00； 当u0=1时，由树根出发走下支路，移存器状态转为S1=10，此时输出码段为c0=11。 在输入第二位信息元时，编码器已处于1阶节点处，若在S0点，则输入u1=0时走上分支，输出c1=00，新状态为S0； 输入u1=1时下分支，输出c1=11，新状态为S1； 若在S1点，则输入u1=0时走上分支，输出c1=10，新状态为S2=10； 输入u1=1时走下分支，输出c1=01，新状态为S3=11。 再输入u2，编码器从2阶节点处出发，此时起始状态有4种： S0、S1、S2和S3，按输入0走上分支，输入1走下分支码段的规则，得到相应的输出c2和新状态。依次类推，输入无限长信息序列，就可以得到一个无限延伸的树结构图。 从码树图上观察，输入无限长信息序列，就可以得到一个无限延伸的树结构图。输入不同的信息序列，编码器就走不同的路径，输出不同的码元序列。 在树图中，编码的过程相当于以输入信息序列为指令沿码树游走，在树图中所经过的路径代码就是相应输出的码序列。 树图最大特点是按时间顺序展开的(l=0,1,2,…)，且能将所有时序状态表示为不相重合的路径。 一般地，对于二元(n,k,m)卷积码来说，从每个节点发出2k条分支，每条分支上标有n长输出数据，最多可有2km种不同状态。 状态图从状态上看最为简洁，但时序关系不清晰。码树的最大特点是时序关系清晰，且对于每一个输入信息序列都有一个唯一的不重复的树枝结构相对应，它的主要缺点是进行到一定时序后，状态将产生重复，且树图越来越复杂。 若输入信息为u=(10101)，则由图59可知卷积编码序列为11100010，如图59中点划线所示。由于树图只展示到第3个节点，所以第4个节点输入信息的编码看不到，这也正是树图的缺点所在。 5.4.3网格图 网格图又称篱笆图，它综合了状态图和树图的特点，是将码树中处于同一级节点合并而成的，是一个纵深宽度或者高为2km的网格图，结构简单，而且时序关系清晰。 网格图的最大特点是保持了树图的时序展开性，同时又克服了树图中太复杂的缺点，它将树图中产生的重复状态合并起来。 树图中，从某一阶节点开始所长出的分支从纵向看是周期重复的。如图59(2,1,2)码的树图中，当节点数大于m+1=3时，状态S0、S1、S2和S3重复出现，因此在第（m+1）阶节点以后，将树图上处于同一状态的同一节点折叠起来加以合并，就可以得到网格图。 图510是信息序列长度l为5的(2,1,2)码网格图，实线表示输入为0的分支，虚线表示输入为1的分支。分支上标准的n位数据表示相应的编码输出c。从第m至l节点，编码器处于稳定的状态转移中，并且各节点的网格结构均相同。在l节点后m个移存器尚需转移m个状态，才能回到初始状态S0。由于l到（l+m）节点的过程中输入0，所以只有实线分支。 图510(2,1,2)卷积码网格图 与树图一样，网格图中每一种信息序列有唯一的网格编码路径，图中输入信息序列u=(10101)路径对应的输出码元序列c=(11100010001011)，如图510中点划线所示，编码后面多出了1011四位，是因为在输入信息序列后加入了两位移位寄存器清零码元，因此实际上输入为u=(1010100)。 5.5卷积码的译码 卷积码的译码可分为三大类： 序列译码、门限译码和Viterbi译码。序列译码基于码的树图结构，能很好地处理约束度很长的卷积码，缺点是它的译码时间是可变的； 门限译码基于码的代数结构，通过计算伴随式集合实现，缺点是在误码率方面表现较差； Viterbi译码基于码的网格图结构，是一种极大似然译码方法。 5.5.1卷积码的硬判决和软判决 图511所示为卷积码编译码系统的简要框图。信息序列u编码成为传输序列c，经过有噪声的信道后接收端接收到序列y，由卷积译码器给出译码序列u^。 在图511中，噪声信道的输入序列c是一个二进制符号序列，对其输出序列y如果也按二进制数据进行判决，给出译码序列u^，则一般称为硬判决(硬量化)卷积译码。如果为了充分利用信道输出序列的数据信息以提高译码可靠性，可将信道输出的数据做多电平量化，例如8电平量化，再进行卷积译码，则通常称为软判决(软量化)卷积译码。对AWGN信道来说，软判决译码比硬判决译码可获得2dB的性能改善。 图511卷积码编译码系统框图 5.5.2硬判决的Viterbi译码 硬判决的Viterbi算法是一种汉明距离译码。通常所说的Viterbi译码就是硬判决的Viterbi译码。 Viterbi译码方法采用分段处理，每个码段根据接收的码元序列，按照极大似然译码准则，寻找发送端编码器在网格图上所经过的最佳路径，也就是在网格图上寻找与接收码相比差距最小的可行路径。对于BSC信道，这种寻找可等价为确定与接收码段具有最小汉明距离的路径。由于接收序列通常很长，所以Viterbi译码时最大似然译码作了简化，即它把接收码字分段累接处理，每接收一段码字，计算比较一次，保留码距最小的路径，直至译完整个序列。 Viterbi译码具有以下优点： (1) 有固定的译码时间； (2) 适于译码器的硬件实现，运行速度快； (3) 译码的错误概率可以达到很小； (4) 容易实现，成本低。 1. Viterbi译码算法的步骤 对于(n,k,m)卷积码，假设已接收l个码段，Viterbi译码算法可归纳为以下步骤： (1) 在j=m节点处，对进入每一状态的长度为j=m的部分路径，计算输出数据与对应接收的j个n长码段的汉明距离。将部分路径存储作为被留选的幸存路径(部分路径是指前m个码段的路径，是全路径的一部分，而不是前m个码段路径的不同分支路径)。 (2) j增加1，把此时进入每一状态的所有分支与前一阶节点处留选的幸存路径累积，计算这些路径与相应接收码段的汉明距离，每个状态留选汉明距离最小者为对应的幸存路径，其余路径则删除。 (3) 重复步骤（2），直至j=l+m，最终整个网格图中只剩一条幸存路径，译码结束。 由m至l阶节点，网格图中2km个状态中每一个状态有一条幸存路径； 但在l阶节点后，状态数目减少，幸存路径随之相应减少； 至l+m阶节点时，仅剩一条幸存路径，它就是译码器输出的最佳估值码元序列路径。 如果在某阶节点时，某状态的两条路径具有相同的汉明距离，这时需观察下一阶节点累积的汉明距离，再选定最小距离的路径。 2. Viterbi译码过程 对于图56的编码器，设输入信息序列u=（10101），通过BSC后送入译码器的序列y=（11100111001011），采用Viterbi译码算法对信息序列和码序列进行估值。 前面已经推导出，当输入信息序列u=（10101）时，正确的输出码序列是c=（11100010001011），与实际接收序列y比较有2个码元错误。根据图510的网格图，Viterbi译码器对接收序列y的译码过程示于图512中，yi为接收码段，d为汉明距离，u^为信息估值。 在图512(a)中，从初始状态到达j=2阶节点的4种状态有4条路径，这4条路径与接收序列y0y1=(1110)的汉明距离分别为3、3、0、2，依次作为4种状态的幸存路径。 当j=3时，如图512(b)所示，沿前一阶节点的幸存路径到达S0状态有两条路径S000S000S000S0和S011S110S211S0，与y0y1y2=(111001)的汉明距离分别为4和1，选取距离最小者为S0状态的幸存路径。同样S1、S2、S3状态也都有两条路径，分别留选距离最小者为幸存路径，其余路径则删除。 接着由j=3的S0、S1、S2状态转移到j=4的S0、S1、S2、S3状态，如图512(c)所示，有4条路径与y0y1y2y3=(11100111)比较，具有最小汉明距离，被留选下来。 同样由j=4到j=5节点，如图512(d)所示，每一种状态都各自留选了一条幸存路径。 在图512(e)当j=6时，有用信息已输入完毕，输入端补零至编码器，所以只剩下S0和S2两种状态，而S0状态的两条路径与y0y1y2y3y4y5=(111001110010)的距离都是3，因此都被留存。 当j=7时，如图512(f)回到初始状态S0，只剩唯一的一条幸存路径，其对应的输出码序列就是接收码序列的最佳估值y^=(11100010001011)，相应的信息序列估值u^=(10101)。 图512Viterbi译码过程 图512(续) 可见，译码结果与编码器的输出结果一致，实现了正确译码。 由于幸存路径长度为L，共需L·2m个段存储单元存储全部幸存路径，因此对实际中几乎无穷大的传送序列，若记L=Ld为译码输出时刻，Ld的值不可能太大，通常Ld选择为约束长度N的5~10倍，称为译码深度，Ld=(5~10)N。当实际序列长度LLd时，译码器可以是逐Ld段长进行译码。 5.5.3软判决的Viterbi译码 为了充分利用接收信号的全部信息，提高译码性能，可将硬判决改为软判决。即对接收信号进行多电平判决或进行多进制Viterbi译码。 硬判决Viterbi译码是二电平判决，适合于二进制对称信道(BSC)。对于二电平判决，当噪声干扰较大时判决容易丢失有用信息。而采用多电平判决，可改善Viterbi译码器性能(1.5~2dB)。软判决Viterbi译码适合于离散无记忆信道(DMC)，通常采用４~８电平。 软判决Viterbi译码与硬判决Viterbi译码的算法大体相同，不同之处主要表现在路径量度的求法不同，因为多进制的最大似然度不再是简单的汉明距离。因此路径量度要用对数似然函数来计算。 5.6卷积码举例 如图513所示的卷积码编码器，n=3,k=1,m=2，码率等于1/3。下面以该卷积码编码器为例对卷积码做较详细地分析和讨论。 图513一种(3,1,2)卷积码编码器的方框图 由图可知 c1i=ui c2i=uiui-2 c3i=uiui-1ui-2 输出码字为ci=(c1ic2ic3i)。 1. 状态表 由5.4的内容可知，一个卷积码编码器的状态图、树图、网格图是由编码器决定的，与输入信息无关。此卷积码编码器由两级移位寄存器组成，因此只有4种状态， 00、10、01和11，分别用符号S0、S1、S2和S3表示。而对于每一种状态都有“0”和“1”两种输入，于是根据图513的编码器可得到如表54（a）所示的状态表。 表54（a）（3,1,2）卷积码的状态表 输入u 初态Si 初态Sj 输出c 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 0 0 0 1 1 0 1 0 1 0 1 1 1 1 1 1 0 1 若输入信息位是1101，则由编码器得到如表54（b）的状态变换表。 表54（b）（3,1,2）卷积码的状态变换表 输入u 初态Si 初态Sj 输出c 1 0 0 1 0 1 1 1 1 1 0 1 1 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 由表54（b）可以得到对应的编码为111 110 010 100 001 010。此处输入信息增加了两位清零码元“0”。 2. 状态图 由表54(a)可得到如图514所示的状态图，图中实线表示输入信息位为“0”时的状态转变路线，虚线表示输入信息位为“1”时的状态转变路线。 图514(3,1,2)卷积码的状态图 若输入信息位是1101，由状态图514可得编码输出为111 110 010 100。 3. 树图 规定输入信息为“0”，状态向上支路移动，输入信息为“1”，则状态向下支路移动，于是由表54得出如图515所示的树图。 图515(3,1,2)卷积码的树图 若输入信息位是1101，由树图可得编码输出为111 110 010 100，图515中的虚线所示。 4. 网格图 将状态图在时间上展开，可以得到网格图，如图516所示。 图516(3,1,2)卷积码的网格图 进一步可以得到(3,1,2)卷积码路径图，如图517所示。 图517(3,1,2)卷积码路径图 5. Viterbi译码 这种算法的基本原理是将接收到的信号序列和所有可能的信号序列作比较，选择其中汉明距离最小的序列译为发送信号序列。 前面已知发送信息位为1101，为了使移位寄存器中的信息全部移出，在信息位后面加入3个“0”，编码后的发送序列为111 110 010 100 001 011 000，若接收序列为111 010 010 110 001 011 000， 则第4个码元和第11个码元为错码。 由于这是一个(n,k,m)=(3,1,2)卷积码，发送序列的约束长度为N=m+1=3，所以首先要考虑3个信息段，即考察3n=9位。 由图516可知，沿路径每一级有4种状态，S0、S1、S2和S3，每种状态只有两条路径可以到达，故4种状态共有8条路径。比较这8条路径和接收序列之间的汉明距离，如表55所示。 表55Viterbi算法解码第一步计算结果 序号 对 应 序 列 汉 明 距 离 幸存否 1 000 000 000 5 否 2 111 001 011 3 是 3 000 000 111 6 否 4 111 001 100 4 是 5 000 111 001 7 否 6 111 110 010 1 是 7 000 111 110 6 否 8 111 110 101 4 是 将距离较小的路径保存(若几条路径的汉明距离相同，则可以任意保存一条)为幸存路径，如图518(a)所示。 第二步继续考察接收序列中后继的“110”，如图518(b)所示。 图518(3,1,2)卷积码译码幸存路径网格图 在编码时，为了使输入的信息位全部通过移位寄存器，使移位寄存器回归到初始状态，在信息位后面加入3个“0”。若把这3个“0”仍看做信息位，则可以按照上述的方法继续解码，如图519所示。 图519(3,1,2)卷积码译码幸存路径图(补“0”码) 最终得到的幸存路径网格图如图520所示。 图520对应信息位1101000的幸存路径网格图 已知最后3个码元是(为结尾而补充的)“0”，则在解码计算时就预先知道在接收这 3个“0”码元后，路径必然应该回归到状态S0，由图520可见，只有两条路径可以回到状态S0，所以，这时的图520可以简化为图521。 图521对应信息位1101及以000结束的幸存路径网格图 因为接收序列为111 010 010 110 001 011 000，而幸存的两条路径的序列分别为111 110 010 011 111 001 011和111 110 010 100 001 011 000，对应的码距分别为8和2，因此最佳估值为111 110 010 100 001 011 000，相应的信息序列估值为1101000。 在该例中卷积码的约束长度为N=3，需要存储和计算8条路径的参量。由此可见，Viterbi算法的复杂度随约束长度N按指数形式2N增长。故Viterbi算法适合约束长度较小的编码。 5.7卷积码的编码实现与仿真 5.7.1与卷积码有关的几个函数 1. convenc函数 功能： 卷积编码。 语法： code = convenc(msg,trellis)； code = convenc(msg,trellis,puncpat)； code = convenc(msg,trellis,…,init_state)； ［code,final_state］ = convenc(…)； 说明： 用code=convenc (msg, trellis )可对k位信息进行卷积编码，trellis是网格结构。 code = convenc(msg,trellis,puncpat)中，puncpat是指定一个打孔模式，允许更高的编码速率。 code = convenc(msg,trellis,…,init_state)中，init_state是寄存器的初始状态。 ［code,final_state］ = convenc(…)同时输出编码和寄存器的最终状态。 2. poly2trellis函数 功能： 将卷积码多项式转换为网格形式。 语法： trellis = poly2trellis(ConstraintLength,CodeGenerator)； trellis = poly2trellis(ConstraintLength,CodeGenerator, FeedbackConnection)； 说明： 用trellis = poly2trellis(ConstraintLength,CodeGenerator)输入卷积编码器的多项式描述，输出相应的网格结构。ConstraintLength是约束长度，等于m+1,CodeGenerator是生成矩阵。 trellis = poly2trellis(ConstraintLength,CodeGenerator, FeedbackConnection)可输出网格结构，参数FeedbackConnection是反馈连接。 3. vitdec函数 功能： 利用Viterbi算法的卷积译码。 语法： msg = vitdec(code,trellis,tblen,opmode,dectype)； msg =vitdec(code,trellis,tblen,opmode,'soft',nsdec)； msg =vitdec(code,trellis,tblen,opmode,dectype,puncpat)； msg =vitdec(code,trellis,tblen,opmode,dectype,puncpat,eraspat)； msg =vitdec(…,'cont',…,initmetric,initstates,initinputs)； ［decoded,finalmetric,finalstates,finalinputs］ = vitdec(…,'cont',…)； 说明： tblen是一个正整数,表示反馈深度，也称回溯长度。 opmode指在假设编码器模式的情况下解码器的模式。当opmode='cont'时，编码器是全零的初始状态，这种方式有延迟； 当opmode='term'时，编码器是全零的初始状态和最终状态； 当opmode='trunc'时，这种方式没有延迟。 dectype指判决方式。当dectype='unquant'时，非量化判决，输出为实数； 当dectype='hard'时，硬判决，输出0或1； 当dectype='soft'时，软判决，输出0~(2b-1)之间的整数，b是软判决的位数。 5.7.2编码 1. 利用库函数来实现编码 对于图53的(2，1，3)卷积码编码器，k=1，n=2，m=3，已知 c1j=ujuj-2uj-3 c2j=ujuj-1uj-2uj-3 则g1=(1011)，g2=(1111)，如果信息序列为已知，如u=［1 0 1 1 1］。 利用convenc函数，则代码如下： msg=［1 0 1 1 1］； %信息序列 trellis=poly2trellis(［4］,［13 ,17］)；%产生上述(2，1，3)卷积码编码器的网格 code=convenc(msg,trellis)； %卷积编码 运行结果如下： code = 1101000101 注： 此运行结果只包含信息序列的编码。 2. 离散卷积编码的实现方法 代码如下： 程序5_1(program5_1.m) %离散卷积编码的实现方法 u = ［1 0 1 1 1］； %信息序列 g1 = ［1 0 1 1］； g2 = ［1 1 1 1］； %g1,g2长度必须相同，为编码器的两个冲击响应 c1 = conv(u,g1)； %卷积运算 c2 = conv(u,g2)； %卷积运算 %---------------------------------- %交替读出两个卷积编码器的输出数据，得到编码结果 len = length(c1)； for i = 1： 1： len output((2*i-1)) = rem(c1(i),2)； output(2*i) = rem(c2(i),2)； end %---------------------------------- %结果显示 disp('卷积编码为： ') disp(output)； 运行结果如下： 卷积编码为： 1101000101010011 3. 利用自定义函数来实现编码 自定义函数jjmencode.m，代码如下： function code=jjmencode(G,k,msg) %卷积码编码函数 % G： 决定输入序列的生成矩阵 % k： 每一时钟周期输入编码器的比特数 % msg： 输入数据 % code： 输入数据 %---------------------------------- %判断输入信息序列是否需要添零，若需要则添零 if rem(length(msg),k)0 msg=［msg,zeros(size(1： k-rem(length(msg),k)))］； end %---------------------------------- % 把输入信息比特按k分组，m为所得的组数 m=length(msg)/k； %---------------------------------- % 检查生成矩阵 G 的维数是否和 k 一致 if rem(size(G,1),k)0 error('Error,G is not of the right size.') end %---------------------------------- % 从生成矩阵G可得到约束长度 L 和输出比特数 n L=size(G,2)/k； n=size(G,1)； %---------------------------------- % 在信息前后加零，使移位寄存器清零，加零个数为(L-1)k个 u=［zeros(1,(L-1)*k),msg,zeros(1,(L-1)*k)］； %---------------------------------- %将添零后的输入序列按每组 Lk 个分组，分组是按 k 比特增加 %从 1 到 Lk 比特为第一组，从 1+k到 Lk+k 为第二组，依次类推，并将分组按倒序排列 u1=u(L*k： -1： 1)； for i=1： m+L-2 u1=［u1,u((i+L)*k： -1： i*k+1)］； end U=reshape(u1,L*k,m+L-1)； %---------------------------------- % 卷积编码输出 code=reshape(rem(G*U,2),1,n*(L+m-1))； 对于前面的例子，利用自定义函数jjmencode.m实现编码。 程序5_2(program5_2.m) msg=［1 0 1 1 1］； %信息序列 g1=［1 0 1 1］； g2=［1 1 1 1］； k=1；%每一时钟周期输入编码器的比特数 code=jjmencode(［g1； g2］,k,msg)； %调用卷积编码函数 disp('卷积编码为')； disp(output)； 运行结果如下： 卷积编码为： 1101000101010011 5.7.3译码 对于图53的(2，1，3)卷积码编码器，k=1，n=2，m=3，已知 c1j=ujuj-2uj-3 c2j=ujuj-1uj-2uj-3 则g1=(1011)，g2=(1111)。 1. 利用库函数(vitdec)来实现译码 采用vitdec函数进行译码，执行以下3行代码： r=［0 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 0 0 1 1］;%接收序列 trellis=poly2trellis(［4］,［13 ,17］);%网格参数 msg =vitdec(r,trellis,3,'trunc','hard');%没有延时，硬判决 运行结果如下: msg = 0010111000 执行以下3行代码： r=［0 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 0 0 1 1］;%接收序列 trellis=poly2trellis(［4］,［13 ,17］);%网格参数 msg =vitdec(r,trellis,3,'term','hard'); %编码器是全零的初始状态和最终状态，硬判决 运行结果如下: msg = 0010111000 执行以下3行代码： r=［0 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 0 0 1 1］;%接收序列 trellis=poly2trellis(［4］,［13 ,17］);%网格参数 msg =vitdec(r,trellis,3,'cont','hard'); %编码器是全零的初始状态，有延迟，硬判决 运行结果如下： msg = 0000010111 由以上代码可以看出，译码函数vitdec的参数设置不同，译码结果不同。 2. 利用自定义的函数实现译码 自定义函数viterbidecode.m，代码如下： function ［msg,survivor_state,cumulated_metric］=viterbidecode(G,k,r) %viterbi译码函数 n=size(G,1)； %n： 编码输出端口数量,(2,1,3)中n=2 %---------------------------------- if rem(size(G,2),k)~=0%当G列数不是k的整数倍时 error('G和k大小不一致')%发出出错信息 end %---------------------------------- if rem(size(r,2),n)~=0%当输出元素个数不是输出端口的整数倍时 error('接收序列的形式不对') end %---------------------------------- %基本参数 N=size(G,2)/k； %得出移位数，即寄存器的个数 M=2^k； %信号组成的状态数 statenumber=2^(k*(N-1))； %寄存器状态数 %---------------------------------- %产生状态转移矩阵、输出矩阵和输入矩阵 for j=0： statenumber-1%j表示当前寄存器组的状态 for m=0： M-1%m为由k个输入端的信号组成的状态 ［next_state,memory_contents］=nextstate(j,m,N,k)； %调用nextstate函数，由寄存器当 %前状态和输入确定寄存器的下一个状态和寄存器内容 input(j+1,next_state+1)=m； branch_output=rem(memory_contents*G',2)； %输出分支 nstate(j+1,m+1)=next_state； %下一个状态 output(j+1,m+1)=bin2deci(branch_output)； end end state_metric=zeros(statenumber,2)； %state_metric数组用于记录译码过程在每状态时的汉明距离 depth_of_trellis=length(r)/n； %网格深度 r_matrix=reshape(r,n,depth_of_trellis)； %信道输出的汉明距离 survivor_state=zeros(statenumber,depth_of_trellis+1)；%幸存状态 %---------------------------------- %开始无尾信道输出的解码 for i=1： depth_of_trellis-N+1 flag=zeros(1,statenumber)； if(i=N) step=2^(k*(N-i))； else step=1； end for j=0： step： statenumber-1 for m=0： M-1 branch_metric=0； binary_output=deci2bin(output(j+1,m+1),n)； for ll=1： n branch_metric=branch_metric+metric(r_matrix(ll,i),binary_output(ll))； end %选择码间距离较小的那条路径，当下一个状态没有被访问时就直接赋值，否则，用比它小的路径将 %其覆盖 if(( state_metric(nstate(j+1,m+1)+1,2)state_metric(j+1,1)+branch_metric)|… flag(nstate(j+1,m+1)+1)==0 ) state_metric(nstate(j+1,m+1)+1,2)=state_metric(j+1,1)+branch_metric； survivor_state(nstate(j+1,m+1)+1,i+1)=j； flag(nstate(j+1,m+1)+1)=1； end end end state_metric=state_metric(： ,2： -1： 1)； end %---------------------------------- %开始尾部信道输出的解码 for i=depth_of_trellis-N+2： depth_of_trellis flag=zeros(1,statenumber)； %状态数从statenumber→statenumber/2→…→2→1 last_stop=statenumber/(2^(k*(i-depth_of_trellis+N-2)))； for j=0： last_stop-1 branch_metric=0； binary_output=deci2bin(output(j+1,1),n)； for ll=1： n branch_metric=branch_metric+metric(r_matrix(ll,i),binary_output(ll))； end if( (state_metric(nstate(j+1,1)+1,2)state_metric(j+1,1)+branch_metric)|… flag(nstate(j+1,1)+1)==0 ) state_metric(nstate(j+1,1)+1,2)=state_metric(j+1,1)+branch_metric； survivor_state(nstate(j+1,1)+1,i+1)=j； flag(nstate(j+1,1)+1)=1； end end state_metric=state_metric(： ,2： -1： 1)； end %---------------------------------- %从最佳路径中产生解码 %译码过程可从数组survivor_state的最后一个位置向前逐级译码 state_sequence=zeros(1,depth_of_trellis+1)； state_sequence(1,depth_of_trellis)=survivor_state(1,depth_of_trellis+1)； for i=1： depth_of_trellis state_sequence(1,depth_of_trellis-i+1)=survivor_state((state_sequence… (1,depth_of_trellis+2-i)+1),depth_of_trellis-i+2)； end %---------------------------------- %译码输出 msg_matrix=zeros(k,depth_of_trellis-N+1)； for i=1： depth_of_trellis-N+1 %根据数组input的定义得出从当前状态到下一个状态的输入信号矢量 dec_output_deci=input(state_sequence(1,i)+1,state_sequence(1,i+1)+1)； dec_output_bin=deci2bin(dec_output_deci,k)； %将一次译码存入译码输出矩阵msg_matrix相应的位置 msg_matrix(： ,i)=dec_output_bin(k： -1： 1)'； end msg=reshape(msg_matrix,1,k*(depth_of_trellis-N+1))； %译码结果 cumulated_metric=state_metric(1,1)； disp('译码结果为') disp(msg) 本函数中调用的其他自定义函数如下： （1) nextstate.m。 %由寄存器当前状态和输入确定寄存器的下一个状态和寄存器内容 %current_state为当前状态，next_state为下一个状态，memory_contents为寄存器内容 %input为输入，binary_input为二进制输入，binary_state为二进制状态 function ［next_state,memory_contents］=nextstate(current_state,input,L,k) binary_state=deci2bin(current_state,k*(L-1))； binary_input=deci2bin(input,k)； next_state_binary=［binary_input,binary_state(1： (L-2)*k)］； next_state=bin2deci(next_state_binary)； memory_contents=［binary_input,binary_state］； （2) deci2bin.m。 %十进制转换为二进制 function y=deci2bin(x,l) y=zeros(1,l)； i=1； while x=0 & i=l y(i)=rem(x,2)； x=(x-y(i))/2； i=i+1； end y=y(l： -1： 1)； (3) bin2deci.m。 %二进制转换为十进制 function y=bin2deci(x) l=length(x)； y=(l-1： -1： 0)； y=2.^y； y=x*y'； (4) metric.m。 %求汉明距离 function distance=metric(x,y) if x==y distance=0； else distance=1； end 程序5_3(program5_3.m) %已知G、k、r时利用自定义的Viterbi译码算法函数得出译码结果 G=［1 0 1 1； 1 1 1 1］； %G： 卷积编码矩阵，可以根据自己的需要输入编码矩阵 k=1； %k： 信息源输入端口数 r=［1101000101010011］； %接收到的序列 ［msg,survivor_state,cumulated_metric］=viterbidecode(G,k,r)；%调用译码函数 运行结果如下： 译码结果为 10111 5.7.4通信过程的编程仿真 下面利用MATLAB对通信过程进行仿真，以此说明卷积码对系统通信性能的改善，并对不同编码方式的性能进行比较。 1. 卷积码与未编码的性能比较 程序5_4(program5_4.m) %卷积码与未编码的性能比较 SNR=0： 1： 12；%信噪比 msg=randi(［0,1］,1,100000); % 输入信息 BER0=zeros(1,length(SNR))； BER1=zeros(1,length(SNR))； %---------------------------------- % 网格结构 trellis=poly2trellis(3,［5 7］)； %由编码器得到，此处由图56得，m=2,g1=［101］,g2=［111］ %---------------------------------- %未编码的误码率 for k=1： length(SNR) modbit0=pskmod(msg,2)； %调制 y0=awgn(modbit0,SNR(k),'measured')； %在传输序列中加入AWGN噪声 demmsg0=pskdemod(y0,2)； %解调 recode0=reshape(demmsg0',1,［］)； ［num0,rat0］=biterr(recode0,msg)； %误码计算 BER0(k)=rat0； end %---------------------------------- %编码的误码率 for k=1： length(SNR) code=convenc(msg,trellis)； %编码 modbit1=pskmod(code,2)； %调制 y1=awgn(modbit1,SNR(k),'measured')； %在传输序列中加入AWGN噪声 demmsg1=pskdemod(y1,2)； %解调 recode1=reshape(demmsg1',1,［］)； tblen=5； %回溯长度 decoded1=vitdec( recode1,trellis,tblen,'cont','hard')； %译码 ［num1,rat1］=biterr(double(decoded1(tblen+1： end)),msg(1： end-tblen))； %误码计算 BER1(k)=rat1； end %---------------------------------- %画图 semilogy(SNR,BER0,'b-o',SNR,BER1,'r-s')； xlabel('SNR/dB')； ylabel('BER')； legend('未编码','卷积编码（码率为1/2）')； title('卷积编码(码率为1/2)与未编码性能比较')； grid on 运行结果如图522所示。 图522卷积编码与未编码的性能比较 由图522可见，卷积编码对通信系统的性能有较大的改善，当然对于不同的编码参数，通信系统的性能改善程度不同。 注： 每次运行结果都会有差异，为了避免这种情况，可以增加运行次数，然后给出误码率的平均值，再利用平均值得出仿真曲线。 2. 译码回溯深度和长度对卷积码性能的影响 卷积码译码器中有个回溯判决单元，是得到译码信息的核心单元，该单元会根据加比选单元（ACS）时得到的最小状态标号和相应的译码信息，通过回溯的办法得到译码信息。因此回溯长度对卷积码译码性能有一定的影响。译码回溯深度，一般为寄存器个数的4~10倍。因此，回溯长度可以简单地理解为想要开始判决时离最开始计算度量时刻的距离，当然这个距离一般就是比特长度，z 程序5_5(program5_5.m) %卷积码译码时不同回溯长度的性能比较 clear all;clc; cycl=20;%运行次数 SNR=0:1:10; %信噪比 msg=randi(［0,1］,1,100000);%输入信息 BER0=zeros(1,length(SNR)); %------------------------------------------------------------------ % 网格结构 trellis=poly2trellis(3,［5 7］); %移位寄存器的个数为2，约束长度为3 %------------------------------------------------------------------ for i=1:4:21 %回溯长度的取值 for n=1:cycl for k=1:length(SNR) code=convenc(msg,trellis); %编码 modbit0=pskmod(code,2);%调制 y0=awgn(modbit0,SNR(k),'measured');%在传输序列中加入AWGN噪声 demmsg0=pskdemod(y0,2);%解调 recode0=reshape(demmsg0',1,［］); tblen=i;%回溯长度 decoded0=vitdec( recode0,trellis,tblen,'cont','hard');% 译码 ［num0,rat0］=biterr(double(decoded0(tblen+1:end)),msg(1:end-tblen)); %误码计算 BER0(n,k)=rat0; end end BER0=mean(BER0); BER(i,:)=BER0; end %------------------------------------------------------------------ %画图 figure(1) semilogy(SNR,BER(1,:),'b-o',SNR,BER(5,:),'r-s',SNR,BER(9,:),'k-+',SNR,BER(13,:),'m-p',SNR,BER(17,:),'b-d',SNR,BER(21,:),'r-*'); xlabel('SNR (dB)'); ylabel('BER'); legend('回溯长度为1','回溯长度为5','回溯长度为9','回溯长度为13','回溯长度为17','回溯长度为21'); title('译码时不同回溯长度的性能比较'); grid on 运行结果如图523所示。 图523不同回溯长度的卷积编码性能比较 由图523可见，当卷积码的回溯长度增加时，系统的误码率则越小，卷积码的性能也越来越好。但是当回溯长度大于5倍的编码约束长度时（本仿真采用的编码器约束长度为3），误码率变化越来越小，逐渐趋于一个稳定值。 3. 未编码、卷积码、汉明码的性能比较 下面就卷积码和汉明码对通信系统性能的改善进行比较。 程序5_6(program5_6.m) %未编码、卷积码、汉明码的性能比较 cycl=50； %运行次数 SNR=0： 1： 12；%信噪比 msg=randi(［0,1］,1,100000); %输入信息 BER0=zeros(1,length(SNR))； BER1=zeros(1,length(SNR))； BER2=zeros(1,length(SNR))； %---------------------------------- % 网格结构 trellis=poly2trellis(3,［5 7］)； %从电路求出参数，或已知参数 %---------------------------------- %未编码的误码率 for n=1： cycl for k=1： length(SNR) modbit0=pskmod(msg,2)； %调制 y0=awgn(modbit0,SNR(k),'measured')； %在传输序列中加入AWGN噪声 demmsg0=pskdemod(y0,2)； %解调 recode0=reshape(demmsg0',1,［］)； ［num0,rat0］=biterr(recode0,msg)； %误码计算 BER0(n,k)=rat0； end end BER0=mean(BER0)； %---------------------------------- %卷积编码的误码率 code=convenc(msg,trellis)； %编码 modbit1=pskmod(code,2)； %调制 for n=1： cycl for k=1： length(SNR) y1=awgn(modbit1,SNR(k),'measured')； %在传输序列中加入AWGN噪声 demmsg1=pskdemod(y1,2)； %解调 recode1=reshape(demmsg1',1,［］)； tblen=5； % 回溯长度 decoded1=vitdec(recode1,trellis,tblen,'cont','hard')； %译码 ［num1,rat1］=biterr(double(decoded1(tblen+1： end)),msg(1： end-tblen))； %误码计算 BER1(n,k)=rat1； end end BER1=mean(BER1)； %---------------------------------- %汉明编码的误码率 code2=encode(msg,7,4,'hamming')； %(7，4)汉明编码 modbit2=pskmod(code2,2)； %调制 for n=1： cycl for k=1： length(SNR)%编码的序列，调制后经过高斯白噪声信道，再解调制，再纠错后求误码 y2=awgn(modbit2,SNR(k),'measured')； %在传输序列中加入AWGN噪声 demmsg2=pskdemod(y2,2)； %解调 recode=reshape(demmsg2',1,［］)； bitdecoded=decode(recode,7,4,'hamming')； %译码 %---------------------------------- %计算误码率 error2=(bitdecoded~=msg)； errorbits=sum(error2)； BER2(n,k)=errorbits/length(msg)； end end BER2=mean(BER2)； %---------------------------------- %画图 semilogy(SNR,BER0,'b-o',SNR,BER1,'r-s',SNR,BER2,'k-+')； xlabel('SNR/dB')； ylabel('BER')； legend('未编码','卷积编码（码率为1/2）','汉明编码')； title('未编码、卷积编码(码率为1/2)与汉明码性能比较')； grid on 运行结果如图524所示。 图524未编码、卷积编码(码率为1/2)与汉明码性能比较 由图524可知，此处比较结果是卷积码的性能较好。也可以加入循环码进行比较。值得注意的是，比较结果与具体的编码方式以及编码采用的参数有关，对于编码性能的好坏不能轻易下结论。 5.7.5Simulink仿真 (1) 利用Display模块显示仿真结果，网格结构为poly2trellis(［5,4］,［23,35,0； 0,05,13］) 采用AWGN信道时，卷积码系统仿真模型(jjm_awgn_1.slx)如图525 所示。 jjm_awgn_ 1_V 图525AWGN信道卷积码系统仿真模型1 图525中各模块参数设置如图526~图529所示。 图526Bernoulli Binary Generator模块参数 图527Convolutional Encoder模块参数 图528AWGN Channel模块参数 图529Viterbi Decoder模块参数 运行图525，显示器的第一行显示的信号误码率为0.0003604。 (2) 利用曲线显示仿真结果 如果要得到高斯信道中卷积编码误码率与信道信噪比之间的关系曲线，卷积码系统仿真模型(jjm_awgn_2.slx)如图530 所示。 jjm_awgn_ 2_V 图530AWGN信道卷积码系统仿真模型2 图530中主要模块的参数设置如图531和图532所示。 图531AWGN Channel模块参数 图532To Workspace模块参数 其余模块的参数设置同前。 程序5_7(program5_7.m) %高斯白噪声信道卷积码性能 SNR=-1:1:8;%信噪比 %------------------------------------------------------------------ for n=1:length(SNR)%误码率计算 snr=SNR(n); sim('jjm_awgn_2') S2(n)=［mean(jjm_awgn)］'; S3(n)=S2(n)+eps; EN(n)=［SNR(n)］'; end %------------------------------------------------------------------ semilogy(EN,S3,'b-*')%画图 axis(［-1,8,1e-7,1］);grid xlabel('高斯白噪声信道信噪比SNR(dB)'); ylabel('误码率'); title('高斯白噪声信道卷积码性能'); 运行结果如图533所示。 图533高斯白噪声信道卷积码性能 （3） 几种卷积编码的性能比较 仿真模型如图534所示（jjm_awgn_bj.slx），卷积码的网格结构分别为poly2trellis(［5,4］, ［23,35,0； 0,05,13］)、poly2trellis(［7］, ［171,133］)和poly2trellis(［4］, ［13,17］)，其中第一种卷积码的码率为2/3，后两者的码率为1/2。其余模块的参数设置略。 程序58（program5_8.m） %三种卷积码编码的性能比较 SNR=-1:1:8;%信噪比 %------------------------------------------------------------------ for n=1:length(SNR)%误码率计算 snr=SNR(n); sim('jjm_awgn_bj') S1(n)=［mean(jjm_awgn1)］'; S1(n)=S1(n)+eps; EN(n)=［SNR(n)］'; S2(n)=［mean(jjm_awgn2)］'; S2(n)=S2(n)+eps; S3(n)=［mean(jjm_awgn3)］'; S3(n)=S3(n)+eps; end %------------------------------------------------------------------ semilogy(EN,S1,'b-*')%画图 jjm_awgn_ bj_V 图534AWGN信道卷积编码前后比较 hold on semilogy(EN,S2,'r-o')%画图 hold on semilogy(EN,S3,'k-s')%画图 legend('poly2trellis(［4］, ［13,17］)','poly2trellis(［7］, ［171,133］)','poly2trellis(［5,4］, ［23,35,0;0,05,13］)'); axis(［-1,8,1e-7,1］);grid xlabel('高斯白噪声信道信噪比SNR(dB)'); ylabel('误码率'); title('三种卷积编码的性能比较'); 运行程序结果如图535所示。 由图535可见，码率小的码的纠错能力好，而两个码率相同的码的纠错能力也基本一致。 图535卷积编码性能比较 （4） 卷积码的纠错能力与回溯长度的关系 仿真模型如图536所示，图536中Viterbi Decoder的参数设置如图537所示，AWGN模块的信噪比设置为4，其余模块参数设置略。 图536卷积码译码硬判决中的回溯长度对纠错性能的影响 图537Viterbi Decoder模块参数 程序59（program5_9.m） %卷积码译码硬判决中的回溯长度对纠错性能的影响 tblen=1:2:40;%硬判决中的回溯长度 %------------------------------------------------------------------ for n=1:length(tblen)%误码率计算 tbl=tblen(n); sim('jjm_awgn_tbl') S2(n)=［mean(err_awgn)］'; S3(n)=S2(n)+eps; TBN(n)=［tblen(n)］'; end %------------------------------------------------------------------ semilogy(TBN,S3,'b-*')%画图 axis(［0,40,1e-4,1］);grid xlabel('回溯长度'); ylabel('误码率'); title('回溯长度与纠错能力的关系'); jjm_awgn_ tbl_V 运行程序，结果如图538所示。由图可见，硬判决的回溯长度会影响卷积码的纠错能力，但是当回溯长度的取值大于某个值以后误码率就不会再降低了。 图538卷积码译码硬判决中的回溯长度对纠错性能的影响 5.7.6卷积码编码电路的Simulink实现 图53是一个（2,1,3）卷积码编码器结构，其中n=2，k=1，m=3。假设输入信息序列为u=（10111），经过计算得编码器输出为1101000101，由于是1/2码率，所以共有10位输出。以此为例来介绍卷积码编码电路的Simulink实现。 1. （2,1,3）卷积码编码电路的Simulink仿真模型 对于图53给出的（2,1,3）卷积码编码电路，其Simulink仿真模型如图539所示（jjmbmdl_1.slx）,这里输入信息序列采用Repeating Sequence Stair模块，目的是为了得到确定的输入信息，如这里输入信息序列为10111，则参数设置如图540所示，其他模块的参数设置略。 jjmbmdl_1_V 图539Repeating Sequence Stair模块参数1 移位寄存器采用Unit Delay模块，模2加法器采用Logical Operator模块，切换开关采用Switch模块。四个To Workspace模块用来查看输出序列，一个Scope模块用来查看序列的波形，并进行比较。Switch模块采用Pulse Generator来控制。Repeating Sequence Stair模块和Unit Delay模块的采样时间均设置为1，参数u、c1和c2的采样时间也设置为1。 由于输出序列为上下两个模2加法器的交替取值，因此Switch模块和参数c的采样时间均设置为0.5，Scope模块的采样时间也设置为0.5。 图540Repeating Sequence Stair模块参数2 2． 运行结果 对于图539所示的仿真模型，仿真模型的运行时间设为4.99（因为Matlab是两边采样，若采样时间设为1，为了使信息长度为5，运行时间必须大于等于4.5，小于5）。运行仿真模型，仿真结果如图541和图542所示。 图542示波器的显示波形从上到下分别对应于信息序列u、编码序列c1、编码序列c2以及编码输出序列c。由图541和图542可以看出，该输出结果与前面计算得到的结果完全一致。 图541命令窗口看到的运行结果 图542示波器显示的波形 3. 卷积码的通信过程仿真 卷积码通信系统仿真模型如图543所示（jjmbmdl_2.slx），各模块的参数设置略。这里信源采用Bernoulli Binary Generator模块。信源为随机产生的10000个二进制码元，通过编码电路后成为20000个二进制码元，这些码元经过BPSK调制后，送入加性高斯白噪声信道传输，接收端收到信息后先进行解调，然后送入To Workspace模块，模块变量名设为rcode。再利用MATLAB编程实现译码，译码调用vitdec函数，采用硬判决译码。 jjmbmdl_2_V 图543卷积码通信系统仿真模型 程序5_10（program5_10.m） %卷积编码的误码率 SNR=-1:1:5;%信噪比 trellis=poly2trellis(4,［13 17］); %从电路求出参数，或已知参数 %------------------------------------------------------------------ for n=1:length(SNR)%误码率计算 errB=SNR(n); sim('jjmbmdl_2') recode=permute(rcode,［3,1,2］); recode1=reshape(recode',1,［］); tblen=15;% 回溯长度 decoded1=vitdec(recode1,trellis,tblen,'cont','hard');% 译码 decoded1=decoded1'; xxu=permute(u,［3,1,2］); ［num1,rat1］=biterr(double(decoded1(tblen+1:end)),xxu(1:end-tblen));%误码计算 S2(n)=［mean(rat1)］'; S3(n)=S2(n)+eps; EN(n)=［SNR(n)］'; end %------------------------------------------------------------------ semilogy(EN,S3,'b-*')%画图 axis(［-1,5,1e-5,1］);grid xlabel('高斯白噪声信道信噪比SNR(dB)'); ylabel('误码率'); title('高斯白噪声信道卷积码性能'); 仿真结果如图544所示。 由图544可以看出，卷积码的误码率随信道信噪比的增大而减小。当然误码率还与编码方式、译码方式等因素有关。 图544卷积码通信性能 习题 1. Viterbi译码就是极大似然译码，这种说法对吗？ 2. 已知(2,1,3)码，生成序列g1=(1101)，g2=(1111)。 (1) 求出该码的生成矩阵G∞和生成多项式G(x)。 (2) 求对应于信息序列u=(11101)的码序列。 (3) 此码是否是系统码？ 3. 某(3,1,2)卷积码，生成序列有g1=(100)，g2=(101)，g3=(111)。 (1) 画出该码编码器。 (2) 写出该码生成矩阵。 (3) 若输入信息序列为110101，求输出的码序列是多少？ 4. 已知(3,1,2)卷积码，生成多项式有g1(x)=1+x+x2，g2(x)=1+x，g3(x)=1+x2。 (1) 画出该码的状态图。 (2) 画出l=4的树图和网格图。 (3) 用Viterbi译码算法对接收序列101100001011111101译码。 5. 已知(3,2,1)卷积码，g11(x)=1，g21(x)=x，g31(x)=1+x，g12(x)=x，g22(x)=1，g32(x)=1，求u(x)=［1+x+x3，1+x2+x3］时的码多项式c(x)。 6. 某卷积码编码器如题图51所示。 (1) (n,k,m)=?(2) G=?G(x)=?(3) u=［110011101］时c=? 题图51卷积码编码器 7. 已知(2,1,2)卷积码编码器的输出与信息位的关系为c1=u1+u2，c2=u1+u2+u3，当接收序列为1000100000时，试用Viterbi译码算法求解发送信息序列。 8. 设(3,1,2)卷积码的生成多项式为： g11=x2+x+1，g21=x2+x+1，g31=x2+1 (1) 试画出该编码的树图、网格图和状态转移图。 (2) 画出编码电路。 (3) 如果输入序列为1011，求出编码后的序列。 (4) 假设接收序列为110011001001，根据Viterbi译码算法进行译码。 9. 利用MATLAB实现题8(3)。 10. 对于（2，1，3）卷积码编码器，已知 c1j=ujuj－2uj－3c2j=ujuj－1uj－2uj－3 利用Simulink搭建仿真模型，要求得出（2，1，3）卷积码在AWGN信道时信噪比与误码率的关系曲线。