卷积码的维特比译码ppt课件.ppt

卷积码是把信源输出的信息序列，以k个码元划分为一段，通过编码器输出长为n(k）的一段码段。但是该码段的n-k个校验元不仅与本组的信息元有关，而且也与其前m段的信息元有关，称m为编码存贮，卷积码用(n，k，m）表示。卷积码的概念卷积编码器卷积编码器（状态空间）（状态空间）12k12n输出输出输入输入卷积编码器卷积编码器卷积码的表示方法表示方法表示方法图解表示法图解表示法解析表示法解析表示法矩阵表示法码树图表示法多项式表示法网格图表示法状态图表示法矩阵表示当m=2,A0=(1 1)T，A1=(0 1)T，A2=(1 1)T时，如前3个输入为110，则前6个输出为11101021021012010210000DDDAAAAAAAAACCCCmmm多项式表示法DcDccDC210如果把输入信息序列M和输出信息序列C都写成迟延操作数D的函数形式：2210)(DmDmmDM因此，卷积码编码过程的多项式表示形式为)()()(DGDMDC 02210, 2 , 1njDcDccDCjjjjM(D)中每一项的系数是一个k重向量，而C(D)中每一项的系数是一个n重向量(子码)，若把式C(D)中所有系数(子码)的第j(j=1,2,n0)个分量写成多项式C (j)(D),则(2,1,2)码状态图码状态图111001001010000101111100S3S0S1 1S2图例图例输入比特输入比特0输入比特输入比特1状态图表示法以两个D触发器的组合值为状态，如D1D2，描述从当前状态在不同的输入时的输出及将到达的状态，每个分支上的标注为y1y2，表示当前的输出。树形图表示码树由分支和节点组成，各连续的分支称为路径，他们对应了不同的码序列。以m=2，A0=(1 1)T，A1=(0 1)T，A2=(1 1)T为例，如前3个输入为110，则前6个输出为111010001101101100100100001101101101000000111111网格图表示法状态流图展示了状态转移的去向,但不能记录状态转移的轨迹，网格图可与以弥补这一缺点,使编码的全过程跃然纸上。网格图以状态为纵轴，将状态转移按时间顺序展开，用于描述从第k时刻的编码器状态到第k+1时刻的编码状态的转移情况，以及在转移过程中的输出情况。状态与状态转移的定义画法与流图法一样 (图见下页)。状态状态00011011012345深度深度670000000000000000000011111111111111111111101010101010101001010101图例输入比特0输入比特1010101(2,1,2)截断篱状图截断篱状图Di ii-1i-1Di-2i-2D编码输出编码输出(2,1,2)码编码电路码编码电路码编码电路解析码编码电路解析信息元信息元输入输入M对信息序列对信息序列M进行编码之前，先进行编码之前，先将它每将它每k个码元分成一组，在每个码元分成一组，在每单元时刻内，单元时刻内，k个码元串行输入个码元串行输入到编码器。信息序列到编码器。信息序列M=m0(1) m1(1) ,其中其中ml(1)表示在第表示在第l个个时刻的第时刻的第k=1个信息元。个信息元。编码器由编码器由m+1个移位寄存器组构成，个移位寄存器组构成，每个移位寄存器组内有每个移位寄存器组内有k级寄存器。级寄存器。Di存储当前输入的码组，存储当前输入的码组，Di-1，Di-m存储前存储前m个码组，这正体个码组，这正体现了卷积码现了卷积码“每个码中的码元不仅每个码中的码元不仅与此时刻的信息元有关，而且还与与此时刻的信息元有关，而且还与前前m个时刻的信息元有关个时刻的信息元有关”的特性。的特性。模模2加法器是将与其相关的加法器是将与其相关的信息元进行模信息元进行模2 加，加法法加，加法法则为：则为：+ 0 10 0 11 1 0用用g(i,j)表示常数乘法表示常数乘法器器, 共有共有(m+1)*n个个,(i=1,2, ,k;j=1,2, ,n)。g(i,j)=1时常数乘法时常数乘法器为一条直通的连接线器为一条直通的连接线; g(i,j)=0时没有连接线。时没有连接线。开关开关K在每一节拍中在每一节拍中移动移动n次，每一次输次，每一次输入入k个信息元而输出个信息元而输出年年n个码元。个码元。输出码子输出码子C是：是：Ci=Mi*Gi维特比译码的描述 从第1时刻的全零状态开始(零状态初始度量为0，其它状态初始度量为负无穷） 在任一时刻t，对每一个状态只记录到达路径中度量最大的一个(残留路径）及其度量(状态度量） 在向t+1时刻前进过程中，对t时刻的每个状态作延伸，即在状态度量基础上加上分支度量，得到M*2k条路径 对所得到的t+1时刻到达每一个状态的2k条路径进行比较，找到一个度量最大的作为残留路径 直到码的终点，如果确定终点是一个确定状态，则最终保留的路径就是译码结果状态状态00011011012345深度深度670000000000000000000011111111111111111111101010101010101001010101累加距离累加距离图例输入比特0输入比特101010101100001110111接受序列10112213213334443331443533245546543445(2,1,2)码维特比译码过程码维特比译码过程译出序列译出序列:00 0 1100分步度量的计算：就是求分步度量的计算：就是求接收码子接收码子(10)与状态输出与状态输出码子码子(00)之间的汉明距离，之间的汉明距离，即对应位不同的个数即对应位不同的个数(1)。 累加度量的计算累加度量的计算:就是求就是求前一时刻的累加度量前一时刻的累加度量(1)与该时刻的分步度量与该时刻的分步度量(1)的和的和(2)。 在深度在深度l=m(=2)，2km(4)个状态都只有一条个状态都只有一条分支与之对应，故在此之前各时刻个分支分支与之对应，故在此之前各时刻个分支都作为信存路径保留；在此之后，各状态都作为信存路径保留；在此之后，各状态都有都有2k(2)个分支输入和输出，此时就要对个分支输入和输出，此时就要对分支进行选择。分支进行选择。信存路径选择：对进入同一信存路径选择：对进入同一状态的状态的2k(2)条分支分别计算条分支分别计算(2和和3)并比较其累加度量，并比较其累加度量，保留累加度量最小保留累加度量最小(2)的分支的分支为信存路径，舍去累加度量为信存路径，舍去累加度量大大(3)的分支。的分支。 深度深度l=L(=5)(L 是编码器所处理的信息序列是编码器所处理的信息序列长度长度 )时刻以后，编码器就会被已知的时刻以后，编码器就会被已知的0信信息比特序列清零，这使得译码器强迫所有息比特序列清零，这使得译码器强迫所有的路径返回全零状态并完成译码。的路径返回全零状态并完成译码。 时间时间t t0 0t t1 1t t2 2t t3 3t t4 4t t5 5t t6 6消息序列消息序列m m00011发送序列发送序列U U00000011010111接收序列接收序列R R10100001110111译码序列译码序列C0001100说明：说明：消息序列消息序列m是进入是进入编码器的序列，编码器的序列，发送序列发送序列U是编码器输出，是编码器输出，接收序列接收序列R是经信道传输后的译码器是经信道传输后的译码器输入，输入，译码序列译码序列C是译码器是译码器输出。白色码子是编码器输出。白色码子是编码器清零的冗余信息，清零的冗余信息，红色比红色比特特是发生错误的比特位。是发生错误的比特位。译码结果分析译码结果分析维特比译码收尾 最大似然序列译码要求序列有限，因此对卷积码来说，要求能收尾。 收尾的原则：在信息序列输入完成后，利用输入一些特定的比特，使M个状态的各残留路径可以到达某一已知状态(一般是全零状态）。这样就变成只有一条残留路径，这就是最大似然序列。卷积码收尾的实现 非递归卷积码：约束长度为m+1的卷积码，只要在信息序列输入完成后连续送入m个0，即可使任一路径都到达最终的状态0。 递归卷积码：也可通过将输入值置成反馈值的负值，而使m个时钟后的状态到达0。卷积码收尾非系统非递归码 递归系统码DDDD维特比译码的复杂度 对信息序列长度为L，信息符号取自GF(p)，R=k/n，约束长度为m+1的卷积码。状态数为pkm，因此对每个时刻要做pkm次加比选得到pkm个状态的残留路径，每次加比选包括pk次加法和pk-1次比较。因此总运算量约为Lpkm次加比选。同时要能保存pkm条残留路径，因此需要Lpkm个存贮单元。维特比译码的特点维特比译码的特点 维特比算法是最大似然的序列译码算法 译码复杂度与信道质量无关 运算量与码长呈线性关系 存贮量与码长呈线性关系 运算量和存贮量都与状态数呈线性关系 状态数随分组大小k及编码深度m呈指数关系吞吐量与存储量 运算量与码长呈线性关系意味着平均吞吐量与码长无关。 存贮量与码长呈线性关系意味着对无限码长(流的情况）要求有无限的存贮量。状态数对维特比译码的影响 由于运算量与k和m呈指数关系，因此维特比译码算法一般只适合于k和m较小的场合。大多数情况下k=1，m10。 对状态数很大的卷积码，维特比算法要经一定的修正后才可能实用，常用的算法是缩减状态的维特比译码，即在每一时刻，只处理部分的状态。序列译码与维特比译码的比较 信道质量对前者运算量影响较大，而对后者运算量没有影响 前者是次优的，后者是最优的 前者运算量与约束长度无关，而后者运算量与约束长度呈指数关系 前者会有译码失败，而后者只有译码错误 在不同场合有不同用途100010010111110011S3S001S1 110S2输入输入输出输出000特别说明：特别说明：1、左图中左图中黄色方框黄色方框表示输入，表示输入，红色方框红色方框表示移位器；表示移位器；2、将初始状态定为、将初始状态定为00将字符用不同颜色表示，只是用于方便区别字符，别无他意。将字符用不同颜色表示，只是用于方便区别字符，别无他意。 0000 0 0=0000000 0=0011001 0 0=11101 0=101 其他各状态之间的转其他各状态之间的转换与换与00状态和状态和01状态之间状态之间的转换完全一致：都是在的转换完全一致：都是在当前状态下，分别输入所当前状态下，分别输入所有可能的输入码字有可能的输入码字(这里这里是是0、1），使各状态之间），使各状态之间发生转换，直至遍历所有发生转换，直至遍历所有状态。状态。状态图生成过程状态图生成过程