摘要: 通过优化传统Viterbi算法的存储结构,使其能够对约束长度较大、码率很低卷积码进行译码。离线构造Hamming距离对照表,给出了一种可查表的Viterbi硬判决快速译码算法。实验表明,当误码率为37%以下时,生成多项式的次数在60以内的LFSR(线性反馈移位寄存器)序列的初始状态,可进行快速恢复。与传统的Viterbi译码算法相比,算法的译码效率提高了几乎10倍左右。
关键词:
Viterbi算法,
卷积码,
LFSR序列,
初态恢复
Abstract: This paper optimizes the conventional Viterbi algorithm’s storage structure such that it can be used for decoding the convolutional codes with big constraint length and very small code rate. Furthermore, the algorithm constructs a Hamming distance table to improve the original Viterbi algorithm’s performance. Simulation results indicates that the optimized algorithm id successfully applied in attacking on the stream cipher whose LFSR (Linear Feedback Shift Register) sequence has 37% error rate and feedback polynomial degree is under 60, and the decode efficiency of this approach is about 10 times than that of the conventional Viterbi algorithm.
Key words:
Viterbi algorithm,
Convolutional codes,
LFSR sequence,
Initial state restore
中图分类号:
罗向阳;陆佩忠;刘粉林. 基于Viterbi算法LFSR的恢复与设计[J]. 计算机工程, 2006, 32(17): 178-180,.
LUO Xiangyang; LU Peizhong; LIU Fenlin. Initial States of LFSRs Restoring Based on Optimized Viterbi Algorithm[J]. Computer Engineering, 2006, 32(17): 178-180,.