关于信息:最大似然译码与维特比卷积译码算法

8次阅读

共计 1852 个字符，预计需要花费 5 分钟才能阅读完成。

本专栏蕴含信息论与编码的外围常识，按知识点组织，可作为教学或学习的参考。markdown 版本已归档至【Github 仓库：https://github.com/timerring/information-theory】或者公众号【AIShareLab】回复 信息论 获取。

如果所有的输出信息序列等概, 则通过比拟各个条件概率, 也称为似然函数 $\mathbf{P}\left(\mathbf{Z} \mid \mathbf{U}^{(\mathbf{m})}\right)$ , 就能够失去具备最小过错概率的译码器, 这里 $\mathbf{Z}$ 是接管序列 , $\mathbf{U}^{(\mathrm{m})}$ 是可能发送的序列。如果满足如下公式, 译码器就抉择 $\mathbf{U}^{\left(\mathrm{m}^{\prime}\right)}$

$$
\mathbf{P}\left(\mathbf{Z} \mid \mathbf{U}^{\left(\mathbf{m}^{\prime}\right)}\right)=\max \mathbf{P}\left(\mathbf{Z} \mid \mathbf{U}^{(\mathbf{m})}\right) \text {over all} \mathbf{U}^{(\mathbf{m})}
$$

对于 BSC 信道, 上式相当于 抉择和序列 Z 具备最小汉明间隔的码字 $\mathbf{U}^{\left(\mathrm{m}^{\prime}\right)}$。译码器总是从所有可能的发送序列 $\mathbf{U}^{(\mathrm{m})}$ 中抉择和 Z 间隔最小的序列 $\mathbf{U}^{\left(\mathrm{m}^{\prime}\right)}$。

对于高斯信道, 间隔为欧式间隔。

假如接收端收到的码序列为 1011010010010010, 如何译码？

计算下图中所有可能门路的概率, 而后比拟, 选出最大值。

有多少条门路 ? $\leq 2^{8}$ (穷举法, 须要比拟 $2^{l}$ , 其中 l 为码序列长度)

维特比译码算法是维特比在 1967 年提出。维特比算法的本质是最大似然译码，但它利用了编码网格图的非凡构造，从而升高了计算的复杂度，与齐全比拟译码相比，它的长处是使得译码器的复杂性不再是码字序列中所含码元数的函数。

该算法包含计算网格图上在时刻 t 达到各个状态的门路和接管序列之间的类似度，或者说间隔。维特比算法思考的是，去除不可能成为最大似然选择对象的网格图上的门路，即如果 有两条门路达到同一个状态，则具备最佳量度的门路被选中，称为幸存门路。

对所有状态都将进行这样的选路操作，译码器一直的在网格图上深刻，通过去除可能性最小的门路实现裁决。较早地摈弃不可能的门路升高了译码的复杂性。留神，抉择最优门路能够表述为抉择具备最大似然度量的码字，或者抉择具备最小间隔的码字。

假如为 BSC 信道，汉明间隔为适合的间隔度量。

维特比译码算法的精华能够总结为: 加、比、选。

加: 间隔（概率，分支度量值)相加;
比: 累加间隔（概率，累计度量值）的比拟;
选: 选出间隔小（概率大）的门路作为幸存门路

维特比译码算法是基于网格图进行的。译码时先将接管序列依照 n 分组，而后计算每分组与相应网格图中各分支的输入之间的汉明间隔。

下图所示的 (2,1,3) 卷积码，若接管序列为:11 01 10 11 00 10 11, 求译码后果。
译码的门路，译码后果是:10011
输出为:10011 时，编码后果是 11 01 11 11 10 10 11
比照接管序列 11 01 10 11 00 10 11
错了 2 位，译码过程中都纠正了过去。

卷积码的间隔个性: 自在距: 从 0 状态回到 0 状态的间隔

$d_{\text {free}}=5 \quad t=\left[\left(d_{f}-1\right) / 2\right]$

参考文献：

Proakis, John G., et al. Communication systems engineering. Vol. 2. New Jersey: Prentice Hall, 1994.
Proakis, John G., et al. SOLUTIONS MANUAL Communication Systems Engineering. Vol. 2. New Jersey: Prentice Hall, 1994.
周炯槃. 通信原理（第 3 版）[M]. 北京：北京邮电大学出版社, 2008.
樊昌信, 曹丽娜. 通信原理（第 7 版）[M]. 北京：国防工业出版社, 2012.

正文完