Error-correction Decoding for 2D Convolutional Codes with a Generalized Viterbi Algorithm

Overview & Synopsis

Two-dimensional (2D) convolutional codes are a generalization of one-dimensional (1D) convolutional codes and are naturally suitable for encoding two-dimensional data. Although their theoretical properties are well established, practical applications are limited due to the lack of error-correction decoding algorithms. While the Viterbi algorithm provides an efficient decoding method for 1D convolutional codes, no analogous approach exists for the 2D case. In this paper, we introduce a decoding algorithm for 2D convolutional codes, called the 2D Viterbi algorithm, extending the principles of the classical Viterbi algorithm to the two-dimensional setting. The presented 2D Viterbi algorithm works with linear systems representations of 2D convolutional codes and its complexity depends on the dimension of the corresponding 2D linear system. Hence, we also provide several algorithms to obtain 2D realizations of small dimension.