卷积码收尾的实现
• 非递归卷积码：约束长度为m+1的卷积 码，只要在信息序列输入完成后连续送 入m个0，即可使任一路径都到达最终的 状态0。 • 递归卷积码：也可通过将输入值置成反 馈值的负值，而使m个时钟后的状态到达 0。
卷积码收尾
非系统非递归码
D D
D
D
递归系统码
维特比译码的复杂度
• 对信息序列长度为L，信息符号取自 GF(p)，R=k/n，约束长度为m+1的卷积码。 状态数为pkm，因此对每个时刻要做pkm次 加比选得到pkm个状态的残留路径，每次 加比选包括pk次加法和pk-1次比较。因此 总运算量约为Lpkm次加比选。同时要能 保存pkm条残留路径，因此需要Lpkm个存 贮单元。
• 显然，两条路径分离后一般并不会立即合并， 而是要经过一段时间后才可能合并，这段时 间可长可短，是随机的。因此卷积码中出现 的误码一般也有较强的突发性，一般突发长 度不小于约束长度。 • 对半无限的卷积码而言，总是开始于状态0， 我们要研究的就是什么时候会发生第一次错 误事件？这一次错误事件的长度是多少？它 引起了多少比特错误？错误概率如何？等等。
第九讲
卷积码的维特比译码及卷积码性能分析
回顾
• • • • 卷积码的编码：有记忆的信道编码 卷积码的概率译码 序列译码：费诺算法和堆栈算法 最大似然译码：维特比算法
维特比译码的描述
• 从第1时刻的全零状态开始（零状态初始度量为0，其 它状态初始度量为负无穷） • 在任一时刻t，对每一个状态只记录到达路径中度量最 大的一个（残留路径）及其度量（状态度量） • 在向t+1时刻前进过程中，对t时刻的每个状态作延伸， 即在状态度量基础上加上分支度量，得到M*2k条路径 • 对所得到的t+1时刻到达每一个状态的2k条路径进行比 较，找到一个度量最大的作为残留路径 • 直到码的终点，如果确定终点是一个确定状态，则最 终保留的路径就是译码结果
01
10 0/10 11
0/10 1/01
0/10 1/01
0/10 1/01
维特比译码——收尾
• 最大似然序列译码要求序列有限，因此 对卷积码来说，要求能收尾。 • 收尾的原则：在信息序列输入完成后， 利用输入一些特定的比态 （一般是全零状态）。这样就变成只有 一条残留路径，这就是最大似然序列。
F(N,S,D)的含义
• 它表示，在所有可能路径中，长度是i个 时刻，输入重量为j，输出重量为k的路径 共有A(i,j,k)条。 • 这个式子包含了有关卷积码性能的大量 信息，可以从它得到误比特率、误事件 率及误帧率的性能界。
如何计算F(N,S,D)
• 为了得到F(N,S,D)，我们可以借助流图的 方法，即将各分支的乘积增量做为该分 支的转移函数或增益，而计算从0状态注 入到0’状态输出的总增益，这个总增益 就是F(N,S,D)。
维特比译码的特点
• • • • • • 维特比算法是最大似然的序列译码算法 译码复杂度与信道质量无关 运算量与码长呈线性关系 存贮量与码长呈线性关系 运算量和存贮量都与状态数呈线性关系 状态数随分组大小k及编码深度m呈指数 关系
吞吐量与存储量
• 运算量与码长呈线性关系意味着平均吞 吐量与码长无关 • 存贮量与码长呈线性关系意味着对无限 码长（流的情况）要求有无限的存贮量。
状态数对维特比译码的影响
• 由于运算量与k和m呈指数关系，因此维 特比译码算法一般只适合于k和m较小的 场合。大多数情况下k=1，m<10。 • 对状态数很大的卷积码，维特比算法要 经一定的修正后才可能实用，常用的算 法是缩减状态的维特比译码，即在每一 时刻，只处理部分的状态。
序列译码与维特比译码的比较
图解维特比译码
00 0/00 1/11 0/01 0/11 1/00 1/10 1/10 0/01 0/00 1/11 0/11 1/00 1/10 1/10 0/00 1/11 0/11 0/01 1/00 1/10 1/10 0/10 1/01 1/01 0/01 0/00 1/11 0/11 1/00 1/10 1/10 0/01 0/00 1/11 0/11 1/00 1/10 1/10
• 信道质量对前者运算量影响较大，而对 后者运算量没有影响 • 前者是次优的，后者是最优的 • 前者运算量与约束长度无关，而后者运 算量与约束长度呈指数关系 • 前者会有译码失败，而后者只有译码错 误 • 在不同场合有不同用途
卷积码的性能分析
• 误码分析 • 重量或距离谱 • 首次差错率
两个序列间差异的扩大
对于线性卷积码
• 对线性卷积码而言，输入全0时输出也是 全0，构成一条全0序列，这是一个合法 的编码序列。因此研究误码可以假设发 的是全0序列，而研究译成非0序列的概 率。为此我们要研究卷积码的距离谱或 重量谱。
线性卷积码的首次错误事件
• 在研究首次错误事件概率时，要研究的是第一次与 全0序列分离并再次回到全0序列的事件。它等价于 在网格图上第一次离开状态0并再次回到状态0的路 径。 • 由于这些事件要离开状态0，而再次回到状态0后就 不允许离开状态0，因此状态0要分解成两个状态：0 和0’，其中0为注入态，而0’为吸收态。我们要研究 的就是从注入到吸收所有可能的路径，及它们的各 种特性，如长度、输入重量、输出重量等等。
• 对于有限状态的流编码传输而言，如果 两个序列不起始于同一状态且终于同一 状态，则可以通过网格图的继续延伸而 呈现出更大的差别。而只有有限的差别 才有可能造成误判。 • 因此对卷积码而言，我们关心的是某一 时刻两条路径分离，而在有限时间内又 再次合并的情形。这就是流编码中的一 次错误事件。
首次错误事件
重量表示
• 由于路径每走一步，长度、输入重量、输出重 量等参数都要随各自的分支而进行累加，因此 如果将这些参数在每个分支上的值用指数标注， 则可以用乘积的方式表示一条路径的各项值。 例如，一条路径的乘积项为NiSjDk，表示该路径 长度是i个时刻，输入重量为j，输出重量为k。 当将所有可能路径的乘积项加起来，合并同类 项，就可以得到下面的式子： • F(N,S,D)=i,j,kA(i,j,k) NiSjDk
滑动窗维特比译码算法
• 基本思想：当状态数有限时，给定时刻 的各状态残留路径在一定时间（L）之前 来自于同一状态的可能性随L的增加而迅 速趋近于1。因此当前时刻各残留路径很 可能来自于L时刻前的同一路径。
滑动窗维特比译码算法实现
• 在第k时刻，可以将t-L时刻前的路径结果直接 输出，而在存贮空间中不再保存t-L时刻前的内 容。因此存贮量控制在Lpkm。这里的L就被称 做译码深度。不再随码长的增加而增加。因而 特别适合信息流的卷积码编译码。在这种情况 下甚至不需要对流分段加尾比特。这里的L就 被称做译码深度。 • 显然，滑动窗算法是一种准最优算法。但通常 译码深度只要有编码约束长度的5到10倍，其 性能损失就可以忽略不计了。