卷积码编码和译码(九)
栅格图 Trellis Diagram
栅格图看起来似乎有点乱,但是总的来讲,在表示编译码原理方面还是优于树状图和状态图,因为栅格图能一直按照时间顺序表示编译码的过程. X 轴表示时间, y 轴表示所有可能的状态. 随着时间的增加,我们沿着栅格图水平方向移动. 每次状态转移都表示有一个新的比特输入进来.
画栅格图时,垂直方向画所有可能的 $$2^L$$ 种状态. 然后,我们在允许的状态转移之间连线.每个状态只有两种状态转移路径,转移到哪个,由输入比特是 0 还是 1 决定. 箭头线上写上输入的比特和用括号括起来的输出比特. 箭头线向斜上方表示输入的比特为0,向斜下方表示输入的比特为1. 就像状态图和树状图一样,每个不同的编码器都有唯一的一个栅格图. 我们可以画任意长度的栅格图. 每次延展都是可能的状态转移.
通常我们从状态000开始, 然后延展了 L 个输入比特后，则所有的状态就都被遍历到了。然后，状态转移就开始重复了。
用栅格图怎么实现编码
图10a 中，输入比特显示在最上面. 我们只能从状态000开始。编码过程很简单. 输入为0则向上走，输入为1则向下走. 例如输入为1011000时走的路线,在图中用连线表示了出来. 我们可以看到,得到的结果与前面提到的其他三种方法(冲激响应,状态图,树状图)都是一样的.
译码
有几种不同的方法来译卷积码. 这些方法被分为两大类:
1. 顺序译码 Sequential Decoding
- Fano 算法
2. 最大似然译码 Maximum likely-hood decoding
- 维特比译码 Viterbi Decoding
这些算法都是基于相同的译码思想推导出来的两类方法.
译码的基本思想
假如通过1/2码率的编码器来编码 3 个比特. 我们收到 6 个比特(忽略清空用的比特). 这 6 个比特可能有也可能没有错误.从编码的过程我们知道,这6个比特是唯一的. 但是,由于出错,我们可能收到所有可能的6个比特. 那么输入的3个比特有8种情况.然后每种情况都有唯一的一种6 比特输出. 这些输出就是所有可能的正确的输出,译码的任务就是确定发送的是哪一种3比特.
我们收到的比特序列为111100,不是上面8 种情况中的任何一种,那么我们如何译码? 我们可以做两件事情:
1. 用接收到的比特序列同所有可能的输出序列做对比,选最小汉明距离的( 或者说是 比特不匹配的).
2. 做相关运算,取相关度最好的
第一种方法就是硬判决译码的方法.第二种方法是软判决译码的方法. 比特的不匹配,也就是接收序列和码字的点积,可能仍然得到模糊的答案,无法确定发送的比特是什么.
随着比特数增加,这种粗暴的译码方法的计算量急剧增加,导致完全不再可行.我们需要找更有效率的方法,不用检查所有可能的情况,并且能消除模糊性(有两种可能的选择,如果表 4 中粗体所示)
如果发送 s 个比特, 则有 种可能的码字,那么接收到数据后, 我们如何译码才不需要检查所有这些可能? 这是译码算法的基本出发点.
顺序译码 Sequential Decoding
顺序译码算法是最早被提出来用于译码卷积码的算法. 最早由 Wozencraft 提出,后来 Fano 提出了一个更好的版本.
我们可以对顺序译码做一个比喻. 假如你要去某地,有人给了你一些指引标记. 但是,这些指引标记可能有错误,或者你不认识其中的一个标记, 最后导致你走到了一个错误的路径上. 如果你看不到任何标记了,则表明你走了一个错误的路径.你可能回到某个点,然后选择一个不同路径继续,按照这种方式,你可以到达目的地.但是,在这个过程中你可能需要回退很多次, 这依赖于给的指引是否清晰准确.
类似上面的比喻,顺序译码算法在每一时刻只处理一条路径. 你可以放弃一条路径然后回退再走另外一条路径, 但是重要的是,你在同一时刻只能处理一条路径.
顺序译码可以在栅格图上可以前向或者后向移动. 译码器记录每次决策的结果,每次都是对某一个状态转移做决定,然后在栅格图上移动. 如果某种统计值超过了某个设定的阈值,则放弃这条路径, 然后延当前路径回退到上一个分叉,此处的分叉,其统计值低于设定的阈值.
我们来做一个实例. 编码器是(2,1,4),同前面的例子中用的编码器相同, 假设输入比特序列为1011 000(记得:最后三个比特是清空用的比特,他们对应的输出称为 尾比特 tail bits).
如果没有错误发生,我们将收到 11 11 01 11 01 01 11
假如我们收到的数据为 01 11 01 11 01 01 11. 有一个比特发生了错误. 第一个比特被错误接收为 0 .
用顺序译码算法来译码
1. 决策点1,译码器审视接收到的前两个比特 01. 现在看起来有一个错误发生,因为正确的输出只有00或者11. 但是, 是哪种情况出错了呢? 译码器随机选择 00 往下走. 对应00的输入比特是 0. 我们把错误数记为 1. 现在到决策点2.
2. 在决策点2. 译码器审视接下来的两个接收比特11. 在这里,可以正确决策出发送比特为1,因为其输出恰好就是 11. 到决策点 3.
3. 在决策点3,收到的两个比特是01. 但是,实际输出要么是11,要么是00. 看起来有一个比特错误发生, 错误数增长到2. 但是由于错误数少于设定的阈值3(这个根据信道的统计特性设立的),译码器继续往下走. 我们随机选择上面分支往下走,认为输入的比特是0,到决策点4.
4. 决策点4,译码器检测到又有一个错误发生,因为接收到的数据是11,而实际正确的输出只有10或者01. 错误数增长到3, 达到阈值,译码器回退.
5. 译码器回退到决策点3, 此处的错误数小于3. 选择另外一条路径走,到决策点5. 又是碰到有一个错误发生的情况. 接收比特是11,但是正确的只有01或者10. 错误数又累积到3, 回退.
6. 从决策点3 出发的两个路径都已经不能满足条件. 所以,译码器必须继续回退直到错误数小于3的地方,所以,译码器必须回到到决策点2,再回退到决策点1.
从决策点1开始,译码器将都是碰到完美匹配的情况,译码器成功译码出比特序列 1011000.
顺序译码算法需要的内存是可控的,这个方法适用于长约束长度的编码器, S/N(信噪比?)比较低的情况. 甚至 NASA 的行星际间的通信,也利用了顺序译码的优点.
