卷积码的维特比译码ppt

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

2、形式：2M (m ()+m j D+ m 2 D+C (D) = c()+c D+ c 2 Q+M(D)中每一项的系数是一个k重向量，而C(D)中每一 项的系数是一个n重向量(子码)，若把式C(D)中所有 系数(子码)的第j (j=l, 2, .g)个分量写成多项式C °)(D),则C(£)二 cOy +cIyD + c2y£)2 + J = l,2,，o因此，卷积码编码过程的多项式表示形式为状态图表示法(2,1,2)码状态图以两个D触发器的组合值为 状态，如D1D2,描述从当 前状态在不同的输入时的 输出及将到达的状态，每 个分支上的标注为yly2, 表示当前的

3、输出。树形图表示0001100101110L1011101100丄丄10100码树由分支和节点组成， 各连续的分支称为路径， 他们对应了不同的码序列。 以m二2, A0二(1 1)T, Al二(0 1)T, A2=(l 1)T为例,如前 3个输入为110,则前6个输 岀为111010网格图表示法状态流图展示了状态转移的去向，但不能记录状态 转移的轨迹，网格图可与以弥补这一缺点，使编码 的全过程跃然纸上。网格图以状态为纵轴，将状态 转移按时间顺序展开，用于描述从第k时刻的编码 器状态到第k+1时刻的编码状态的转移情况，以及 在转移过程中的输出情况。状态与状态转移的定义 画法与流图法一样（图见下页

4、）。（2丄2）截断篱状图码编码电路解析对¥用建口）表示常数乘法先霧器，共有（m+l）*n<5个,（i=l,2，k;j=l，2,由入 到纟小）。g（ij）=l时常数乘 三每绅租與出”“木玮后去右與的峋成,#模2加法器是将与其相关的$器。占 一 7L 乂一上丄_、丄，土E体 不仅 丕与开关K在每一节拍中、 :移动n次，每一次输® 入信息元而输出凸元。接线。输出码子c是:1信息元 输入14（2儿2）码编码电路维特比译码的描述从第1时刻的全零状态开始（零状态初始度量为0,其它 状态初始度量为负无穷）在任一时刻t,对每一个状态只记录到达路径中度量最 大的一个（残留路径）及其度量

5、（状态度量）在向t+1时刻前进过程中，对t时刻的每个状态作延伸，' 即在状态度量基础上加上分支度量，得到M*2k条路径对所得到的t+1时刻到达每一个状态的2k条路径进行比 较，找到一个度量最大的作为残留路径<直到码的终点，如果确定终点是一个确定状态，则最 终保留的路径就是译码结果ft犬态累加距离译出序列：00 0接受100001序列f 1011011100 A0011(X)0000译码结果分析1100000011 5:10时间totl七2七3t4t消息序列m0001发送序列U0000001101接收序列R1010000111译码序列C0|o0111101 L01的路径返回全零状态

6、并完成译码。图例:输入比讐510说明:醴曲是进入屛 编码器的序列，flilll 是编码器输出， 是经信道传输后的译码器 输入，隸烤是译码器 输出。白色码子是编码器 清零的冗余信息， 沁 o 窗是发生番滾的比特位。七61111,653（2丄2）码维特比译码过程1106维特比译码收尾最大似然序列译码要求序列有限，因此 对卷积码来说，要求能收尾。收尾的原则:在信息序列输入完成后， 利用输入一些特定的比特，使M个状态 的各残留路径可以到达某一已知状态（一 般是全零状态）。这样就变成只有一条 残留路径，这就是最大似然序列。卷积码收尾的实现非递归卷积码:约束长度为m+1的卷积 码，只要在信息序列输入完成后

7、连续送 入ni个0,即可使任一路径都到达最终的 状态0。递归卷积码:也可通过将输入值置成反 馈值的负值，而使m个时钟后的状态到达 0o卷积码收尾维特比译码的复杂度对信息序列长度为L,信息符号取自GF(p), R=k/n,约束长度为m+1的卷积码。状态数为 pkm,因此对每个时刻要做pkm次加比选得到 pkm个状态的残留路径，每次加比选包括pk次 加法和pkl次比较。因此总运算量约为Lpkm次 加比选。同时要能保存pkm条残留路径，因此 需要Lpkm个存贮单元。维特比译码的特点维特比算法是最大似然的序列译码算法译码复杂度与信道质量无关运算量与码长呈线性关系存贮量与码长呈线性关系运算量和存贮量都与

8、状态数呈线性关系状态数随分组大小k及编码深度m呈指数 关系吞吐量与存储量运算量与码长呈线性关系意味着平均吞吐 量号码长无关。存贮量与码长呈线性关系意味着对无限码长（流的情况）要求有无限的存贮量。状态数对维特比译码的影响由于运算量与k和ni呈指数关系，因此维 特比译码算法一般只适合于k和m较小的 场合。大多数情况下k=l, m<10o对状态数很大的卷积码，维特比算法要 经一定的修正后才可能实用，常用的算 法是缩减状态的维特比译码，即在每一 时刻，只处理部分的状态。序列译码与维特比译码的比较信道质量对前者运算量影响较大，而对 后者运算量没有影响前者是次优的，后者是最优的前者运算量与约束长度无关，而后者运 負量与药束