作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2006, Vol. 32 ›› Issue (17): 178-180,. doi: 10.3969/j.issn.1000-3428.2006.17.062

• 网络与通信 • 上一篇    下一篇

基于Viterbi算法LFSR的恢复与设计

罗向阳1,陆佩忠2,刘粉林1   

  1. (1. 解放军信息工程大学信息工程学院,郑州450002;2. 复旦大学计算机科学与工程系,上海 200433)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2006-09-05 发布日期:2006-09-05

Initial States of LFSRs Restoring Based on Optimized Viterbi Algorithm

LUO Xiangyang1, LU Peizhong2, LIU Fenlin1   

  1. (1. Institute of Information Engineering, Information Engineering University of PLA, Zhengzhou 450002; 2. Department of Computer Science and Engineering, Fudan University, Shanghai 200433)
  • Received:1900-01-01 Revised:1900-01-01 Online:2006-09-05 Published:2006-09-05

摘要: 通过优化传统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

中图分类号: