卷积码的维特比译码PPT课件

1、.,1,卷积码是把信源输出的信息序列，以k个码元划分为一段，通过编码器输出长为n(k）的一段码段。但是该码段的n-k个校验元不仅与本组的信息元有关，而且也与其前m段的信息元有关，称m为编码存贮，卷积码用(n，k，m）表示。,卷积码的概念,.,2,卷积码的表示方法,矩阵表示法,码树图表示法,多项式表示法,网格图表示法,状态图表示法,.,3,矩阵表示,当m=2,A0=(1 1)T，A1=(0 1)T，A2=(1 1)T时，如前3个输入为110，则前6个输出为111010,.,4,多项式表示法,如果把输入信息序列M和输出信息序列C都写成迟延操作数D的函数形式：,因此，卷积码编码过程的多项式表示形式为

2、,M(D)中每一项的系数是一个k重向量，而C(D)中每一项的系数是一个n重向量(子码)，若把式C(D)中所有系数(子码)的第j(j=1,2,n0)个分量写成多项式C (j)(D),则,.,5,(2,1,2)码状态图,状态图表示法,以两个D触发器的组合值为状态，如D1D2，描述从当前状态在不同的输入时的输出及将到达的状态，每个分支上的标注为y1y2，表示当前的输出。,.,6,树形图表示,码树由分支和节点组成，各连续的分支称为路径，他们对应了不同的码序列。以m=2，A0=(1 1)T，A1=(0 1)T，A2=(1 1)T为例，如前3个输入为110，则前6个输出为111010,.,7,网格图表示法

3、,状态流图展示了状态转移的去向,但不能记录状态转移的轨迹，网格图可与以弥补这一缺点,使编码的全过程跃然纸上。网格图以状态为纵轴，将状态转移按时间顺序展开，用于描述从第k时刻的编码器状态到第k+1时刻的编码状态的转移情况，以及在转移过程中的输出情况。状态与状态转移的定义画法与流图法一样 (图见下页)。,.,8,00,00,00,00,00,00,00,00,00,00,11,11,11,11,11,11,11,11,11,11,10,10,10,10,10,10,10,10,01,01,01,01,图例 输入比特0 输入比特1,01,01,01,(2,1,2)截断篱状图,.,9,编码输出,(2,

4、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 加，加法法则为：,用g(i,j)表示常数乘法器, 共有(m+1)*n个,(i=1,2, ,k;j=1,

5、2, ,n)。g(i,j)=1时常数乘法器为一条直通的连接线; g(i,j)=0时没有连接线。,开关K在每一节拍中移动n次，每一次输入k个信息元而输出年n个码元。,输出码子C是： Ci=Mi*Gi,.,10,维特比译码的描述,从第1时刻的全零状态开始(零状态初始度量为0，其它状态初始度量为负无穷） 在任一时刻t，对每一个状态只记录到达路径中度量最大的一个(残留路径）及其度量(状态度量） 在向t+1时刻前进过程中，对t时刻的每个状态作延伸，即在状态度量基础上加上分支度量，得到M*2k条路径 对所得到的t+1时刻到达每一个状态的2k条路径进行比较，找到一个度量最大的作为残留路径 直到码的终点，如果

6、确定终点是一个确定状态，则最终保留的路径就是译码结果,.,11,10,00,01,11,01,11,(2,1,2)码维特比译码过程,分步度量的计算：就是求接收码子(10)与状态输出码子(00)之间的汉明距离，即对应位不同的个数(1)。,累加度量的计算:就是求前一时刻的累加度量(1)与该时刻的分步度量(1)的和(2)。,在深度l=m(=2)，2km(4)个状态都只有一条分支与之对应，故在此之前各时刻个分支都作为信存路径保留；在此之后，各状态都有2k(2)个分支输入和输出，此时就要对分支进行选择。,信存路径选择：对进入同一状态的2k(2)条分支分别计算(2和3)并比较其累加度量，保留累加度量最小(

7、2)的分支为信存路径，舍去累加度量大(3)的分支。,深度l=L(=5)(L 是编码器所处理的信息序列长度 )时刻以后，编码器就会被已知的0信息比特序列清零，这使得译码器强迫所有的路径返回全零状态并完成译码。,说明：消息序列m是进入编码器的序列，发送序列U是编码器输出，接收序列R是经信道传输后的译码器输入，译码序列C是译码器输出。白色码子是编码器清零的冗余信息，红色比特是发生错误的比特位。,译码结果分析,.,12,维特比译码收尾,最大似然序列译码要求序列有限，因此对卷积码来说，要求能收尾。 收尾的原则：在信息序列输入完成后，利用输入一些特定的比特，使M个状态的各残留路径可以到达某一已知状态(一般

8、是全零状态）。这样就变成只有一条残留路径，这就是最大似然序列。,.,13,卷积码收尾的实现,非递归卷积码：约束长度为m+1的卷积码，只要在信息序列输入完成后连续送入m个0，即可使任一路径都到达最终的状态0。 递归卷积码：也可通过将输入值置成反馈值的负值，而使m个时钟后的状态到达0。,.,14,卷积码收尾,非系统非递归码 递归系统码,.,15,维特比译码的复杂度,对信息序列长度为L，信息符号取自GF(p)，R=k/n，约束长度为m+1的卷积码。状态数为pkm，因此对每个时刻要做pkm次加比选得到pkm个状态的残留路径，每次加比选包括pk次加法和pk-1次比较。因此总运算量约为Lpkm次加比选。同

9、时要能保存pkm条残留路径，因此需要Lpkm个存贮单元。,.,16,维特比译码的特点,维特比算法是最大似然的序列译码算法 译码复杂度与信道质量无关 运算量与码长呈线性关系 存贮量与码长呈线性关系 运算量和存贮量都与状态数呈线性关系 状态数随分组大小k及编码深度m呈指数关系,.,17,吞吐量与存储量,运算量与码长呈线性关系意味着平均吞吐量与码长无关。 存贮量与码长呈线性关系意味着对无限码长(流的情况）要求有无限的存贮量。,.,18,状态数对维特比译码的影响,由于运算量与k和m呈指数关系，因此维特比译码算法一般只适合于k和m较小的场合。大多数情况下k=1，m10。 对状态数很大的卷积码，维特比算法要经一定的修正后才可能实用，常用的算法是缩减状态的维特比译码，即在每一时刻，只处理部分的状态。,.,19,序列译码与维特比译码的比较,信道质量对前者运算量影响较大，而对后者运算量没有影响 前者是次优的，后者是最优的 前者运算量与约束长度无关，而后者运算量与约束长度呈指数关系 前者会有译码失败，而后者只有译码错误 在不同场合有不同用途,.,20,10,10,01,01,11,S0,0,0,0,特别说明： 1、左图中黄色方框表示输入，红色方框表示移位器； 2、将初始状态定为00将字符用不同颜色表示，只是用于方便区别字符，