Two dimensional viterbi algorithm improves convolutional code decoding
Error-correction Decoding for 2D Convolutional Codes with a Generalized Viterbi Algorithm
Information Theory
Summary
Decoding 2D convolutional codes used for two-dimensional data has been difficult because there was no efficient algorithm like the Viterbi algorithm for 1D codes. The authors created a new algorithm that extends the Viterbi method to work with 2D convolutional codes, enabling error correction in two-dimensional settings. They also developed ways to simplify the related mathematical systems to make this decoding approach more practical.
What this means in practice
- •For communications engineers: Implement error-correction decoding for two-dimensional data transmissions using the new 2D Viterbi algorithm.
- •For image and video codec developers: Enhance compression and transmission fidelity by applying 2D convolutional code decoding to signals inherently structured in two dimensions.
Authors
Zita Abreu, Elisa Junghans, Julia Lieb, Raquel Pinto
Abstract
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.