纠错码Lecture7-卷积码(II)

Lecture7

卷积码(II)1内容状态转移图和网格图Viterbi译码算法修正的Viterbi译码算法2卷积码的网格图表示右图为(2,1,2)卷积编码示意图，其生成多项式矩阵和生成矩阵分别为3卷积码的状态图表示(2,1,2)码的状态图如右图所示卷积码的自由距离等于编码器从s0出发，又回到该状态时，所有可能非全零路径重量的最小值重量最小的路径：

s0s1s2s0；相应的输出码字序列为：

111011

因此，df

=54卷积码的网格图表示s0s1s2s3s0s1s2s3状态图网格图5Viterbi译码若编码信息序列为1011100，则编码过程即为在Trellis图上寻找一条路径6Viterbi译码译码过程即为在Trellis图上寻找一条路径，该路径对应的编码序列与接收序列之间有最大概率度量7Viterbi译码从第1时刻的全零状态开始（零状态初始度量为0，其它状态初始度量为负无穷）在任一时刻t，对每一个状态只记录到达路径中度量最大的一个（残留路径，硬判决为汉明距离，软判决为欧氏距离）及其度量（状态度量）在向t+1时刻前进过程中，对t时刻的每个状态作延伸，即在状态度量基础上加上分支度量，得到|S|×2k条路径对所得到的t+1时刻到达每一个状态的2k条路径进行比较，找到一个度量最大的作为残留路径直到码的终点，如果确定终点是一个确定状态，则最终保留的路径就是译码结果8Viterbi译码在BSC和BIQO-DMC上，最大概率度量分别等效为最小Hamming距离度量和最小欧氏距离度量距离度量更新公式Theorem：在Viterbi译码算法中，留选路径是有最大似然函数的路径。9Viterbi译码第1个时刻接收子码10汉明距离d11第2个时刻接收子码10汉明距离dExample:M=(1011100)，初始状态为全0的编码器输出序列为C=(11,10,00,01,10,01,11),通过有噪信道后，接收序列为R=(10,10,00,01,11,01,11)1110Viterbi译码第3个时刻接收子码00汉明距离d213211Viterbi译码第4个时刻接收子码01汉明距离d3,43,43,31,5汉明距离d3331213312Viterbi译码第5个时刻接收子码11汉明距离d3,53,52,42,4汉明距离d3322331313Viterbi译码第6个时刻接收子码01汉明距离d3,42,5汉明距离d3233223,43,43314Viterbi译码第7个时刻接收子码11汉明距离d2,5323301/000/101/110/110/011/14,44,43,415Viterbi译码保存的幸存路径为：译码结果为：101110016Viterbi译码——收尾最大似然序列译码要求序列有限，因此对卷积码来说，要求能收尾。收尾的原则在信息序列输入完成后，利用输入一些特定的比特，使|S|个状态的各残留路径可以到达某一已知状态（一般是全零状态）。这样就变成只有一条残留路径，这就是最大似然序列。非递归卷积码约束长度为m+1的卷积码，只要在信息序列输入完成后连续送入m个0，即可使任一路径都到达最终的状态0。递归卷积码可通过将输入值置成反馈值的负值，而使m个时钟后的状态到达0。17Viterbi译码——收尾非系统非递归码递归系统码18Viterbi译码第6个时刻接收子码01汉明距离d3,42,5汉明距离d323322Example(cont.):M=(10111);M’=(1011100)19Viterbi译码第7个时刻接收子码11汉明距离d2,520Viterbi译码保存的幸存路径为：译码结果为：101110021软判决Viterbi译码基本思想为了充分利用信道输出符号的信息，提高译码可靠性，把信道输出的信号进行Q电平量化，然后在输入Viterbi译码器。能适应这种Q进制输入的Viterbi译码器称为软判决Viterbi译码器。例子：Q=4电平量化的信道比特度量0010211211108500581022Viterbi译码的复杂度对信息序列长度为L，信息符号取自GF(p)，R=k/n，约束长度为m+1的卷积码。状态数为pkm因此对每个时刻要做pkm次加比选得到pkm个状态的残留路径每次加比选包括pk次加法和pk-1次比较。因此总运算量约为Lpkm次加比选同时要能保存pkm条残留路径，因此需要Lpkm个存贮单元。23Viterbi译码的特点维特比算法是最大似然的序列译码算法译码复杂度与信道质量无关运算量与码长呈线性关系存贮量与码长呈线性关系运算量和存贮量都与状态数呈线性关系状态数随分组大小k及编码存贮m呈指数关系24修正的Viterbi译码算法基本思想当状态数有限时，给定时刻的各状态残留路径在一定时间（L）之前来自于同一状态的可能性随L的增加而迅速趋近于1。因此当前时刻各残留路径很可能来自于L时刻前的同一路径。25修正的Viterbi算法实现在第k时刻，可以将t-L时刻前的路径结果直接输出，而在存贮空间中不再保存t-L时刻前的内容。因此存贮量控制在Lpkm。这里的L就被称做译码深度，不再随码长的增加而增加。因而特别适合信息流的卷积码编译码。在这种情况下甚至不需要对流分段加尾比特。显然，滑动窗算法是一种准最优算法。但通常译码深度只要有编码约束长度的5到10倍，其性能损失就可以忽略不计了。26修正的Vite