News

 Statistics

Number of Journals34
Number of Issues1,306
Number of Articles9,428
Article View9,191,873
PDF Download5,622,545
Hadi, M., Pakravan, M. (2015). Sequential Decoding Algorithms of Convolutional Codes: Implementation, Improvement and Comparison. Electronic and Cyber Defense, 3(2), 61-73.
Mohammad Hadi; Mohammad Reza Pakravan. "Sequential Decoding Algorithms of Convolutional Codes: Implementation, Improvement and Comparison". Electronic and Cyber Defense, 3, 2, 2015, 61-73.
Hadi, M., Pakravan, M. (2015). 'Sequential Decoding Algorithms of Convolutional Codes: Implementation, Improvement and Comparison', Electronic and Cyber Defense, 3(2), pp. 61-73.
Hadi, M., Pakravan, M. Sequential Decoding Algorithms of Convolutional Codes: Implementation, Improvement and Comparison. Electronic and Cyber Defense, 2015; 3(2): 61-73.

Sequential Decoding Algorithms of Convolutional Codes: Implementation, Improvement and Comparison

پدافند الکترونیکی و سایبری
Article 5, Volume 3, Issue 2, January 2020, Pages 61-73    PDF (875.84 K)
Authors
Mohammad Hadi* 1; Mohammad Reza Pakravan2
1Doctoral student of telecommunications, Sharif University of Technology, Tehran, Iran
2Associate Professor, Sharif University of Technology, Tehran, Iran
Receive Date: 21 March 2015,  Revise Date: 21 June 2023,  Accept Date: 19 September 2018 
Abstract
Error correction capability of convolutional codes is improved by increasing code constraint
length. However, increasing the constraint length results in high complexity of optimum Viterbi
decoding algorithm because the number of computations in Viterbi algorithm is exponentially
proportional to the constraint length. Consequently, decoding of high constraint length convolutional
codes using Viterbi algorithm may practically be impossible. Sub-optimum decoding algorithms such
as Fano and Stack algorithms have been proposed to feasible fast sequential decoding of high
constraint length convolutional codes. In this paper, we introduce different methods of implementing
Fano and Stack algorithms and propose some techniques to improve their speed and required
memory. We compare the introduced implementations of the algorithms in terms of error correction
capability, decoding time and required memory. Furthermore, we use simulation results to show that
if the communication error is low, Fano and Stack algorithms can provide the same error correction
capability as the optimum Viterbi algorithm in very short decoding time
Keywords
Convolutional Codes; Sequential Decoding of Convolutional Codes; Viterbi Algorithm; Fano Algorithm; Stack Algorithm; Convolutional Code Constraint length
References

[1] A. J. Viterbi, “Convolutional Codes and Their Performance in Communication Systems,” IEEE Transaction on Communication Technology, vol. COM-19, no. 5, pp. 751-772, Oct. 1971.
[2] S. Lin and D. J. Costello, “Error Control Coding,”        Prentice Hall, 2004.
[3] S. Kim and S. B. Wicker, “Fundamentals of Codes Graphs and Iterative Decoding,” Springer, 2002.
[4] J. B. Anderson, “Sequential Coding Algorithms: A Survey and Cost Analysis,” IEEE Transaction on Communications, vol. COM-32, no. 2, pp. 169-176, Feb. 1984.
[5] S. H. Yunghsiang and C. Po-Ning, “Sequential Decoding of Convolutional Codes,” Wiley Encyclopedia of Telecommunications, Apr. 2003, Revised Jul. 2015.
[6] J. M. Wozencraft, “Sequential Decoding for Reliable Communication,” IRE Nat. Conv. Rec., vol. 5, no. 2, pp. 11-25, 1957.
[7] J. M. Wozencraft and B. Reiffen, “Sequential Decoding,” IEEE Trans. Inform. Theory, vol. IT-9, no. 2, pp. 64-73, April 1961.
[8] R. M. Fano, “A Heuristic Discussion of Probabilistic Decoding,” IEEE Trans. Inform. Theory, vol. IT-9, no. 2, pp. 64-73, April 1963.
[9] F. Jelinek, “A Fast Sequential Decoding Algorithm Using a Stack,” IBM J. Res. and Dev., vol. 13, pp. 675-685, November 1989.
[10] K. S. Zigangirov, “Some Sequential Decoding Procedures,” Probl. Peredachi Inf., vol. 2, pp. 13-25, 1966.
[11] J. L. Massey, “Variable Length Codes and The Fano  Metric,” IEEE Trans. Inform. Theory, vol. IT-18, no. 1, pp. 196-198, January 1972.
[12] E. A. Bucher, “Sequential Decoding of  Systematic and Nonsystematic  Convolutional Codes with Arbitrary Decoder Bias,” IEEE Trans. Inform. Theory, vol. IT-16, no. 5, pp. 611-624, September 1970.
[13] F. Jelinek, “Upper bound on sequential decoding performance parameters,” IEEE Trans. Inform. Theory, vol. IT-20, no. 2, pp. 227-239, March 1974.
[14] D. Haccoun and M. J. Ferguson, “Generalized Stack Algorithms for Decoding Convolutional Codes,” IEEE Trans. Inform. Theory, vol. IT-21, no. 6, pp. 638-651, November 1975.
[15] J. M. Geist, “An Empirical Comparison of Two Sequential Decoding Algorithms,” IEEE Trans. Commun. Technol., vol. COM-19, no. 4, pp. 415-419, August 1971.

Statistics
Article View: 279
PDF Download: 413