好久没有更新通信相关的博客了，最近在做关于维特比译码的相关工作，这两周也是把维特比算法摸了个门清，下面来简单说一下维特比译码的关键思想，重要步骤。
维特比译码
首先，我们要对维特比译码有个大概的认识。
维特比算法是基于状态转移的一种算法。在我的程序中，涉及到的是相位状态，对于CPM（连续相位调制）信号，相位是随着时间连续变化的，这边是一种状态转移，由于这种状态是具有记忆性的，我们在译码的时候，便可以利用这种记忆性，从前向后，或者从后向前译码。通过找到最优路径，来将信号恢复。
在CPM信号的译码中，我们可以画出这样一种状态转移网格图
其中，纵坐标代表的是状态，横坐标代表每个时刻的符号。第 n 时刻输入的符号不同，对应的状态也就不同。
约束长度
在网格中，对于某些路径，Viterbi 算法递归地累积直到 k 个符号间隔分支量，并选择具有最大路径度量的路径。这个k便为约束长度。理想的情况下，约束长度等于信号长度，但是时间复杂度是O(2^N)，对于通信中的信号来说，复杂度太高，且难于实现，所以，在实际中约束长度一般不会等于信号长度。在我的程序中，约束长度等于2。
简化状态
我们可以看，在上面的网格图中，有 4 种状态，计算起来复杂度比较高。我的项目中采取了简化状态的方法，通过观察状态转移网格，偶数时刻的状态只有两种情况，0 和 π。如下图所示
状态与分支度量
说了那么多，到底是如何找到这个最优路径的呢？对接收到的信号，对于第 n 个时刻，下一种状态对应的所有可能分支状态进行相关计算，我们把得到的这个量成为分支度量，我们比较使第 n 个时刻的分支度量最大的分支状态，保存下来。假设 n 时刻可能有两种状态，每种状态对应 2 种分支（我的项目中是4种），所以每个时刻要计算的度量总共有4个。
我们把最大似然分支找到之后，保存下来，然后往后进行递推，保存的分支数即为约束长度。
提前祝大家双十一快乐！