Application of Shortest Path Algorithms in Telecommunication Channel Coding: A Comparative Study
Keywords:
Channel Coding, Shortest Path Algorithm, Viterbi Algorithm, Bellman–Ford, Dijkstra, Trellis GraphAbstract
Reliable communication over noisy channels requires efficient error-correcting mechanisms. Convolutional channel codes enable error correction by introducing redundancy, while decoding algorithms reconstruct the most probable transmitted sequence. The decoding process can be formulated as a shortest path problem in a weighted directed graph known as a trellis. The Viterbi algorithm performs maximum likelihood decoding by minimizing cumulative path metrics. This paper presents a mathematical formulation of convolutional decoding as a shortest path problem and compares the Viterbi algorithm with classical shortest path algorithms, including the Bellman–Ford algorithm and Dijkstra's algorithm. Structural similarities, complexity differences, and practical implications are analyzed.
Downloads
References
A. J. Viterbi, “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm,” IEEE Transactions on Information Theory, vol. 13, no. 2, pp. 260–269, Apr. 1967.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. Cambridge, MA, USA: MIT Press, 2009.
S. Haykin, Communication Systems, 5th ed. New York, NY, USA: Wiley, 2009.
J. G. Proakis and M. Salehi, Digital Communications, 5th ed. New York, NY, USA: McGraw-Hill, 2008.
