2017/10/31 by Masato Tajima, Tajima, Masato
Computer Science · Engineering · Mathematics · #Advanced Wireless Communication Techniques #Algorithms and Data Compression #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1710.11310
Accepted for publication in IEEE Trans. Inf. Theory
openalex publication_date 2017/10/31 · arxiv created 2018/11/04 · arxiv updated 2018/11/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce the notion of innovations for Viterbi decoding of convolutional codes. First we define a kind of innovation corresponding to the received data, i.e., the input to a Viterbi decoder. Then the structure of a Scarce-State-Transition (SST) Viterbi decoder is derived in a natural manner. It is shown that the newly defined innovation is just the input to the main decoder in an SST Viterbi decoder and generates the same syndrome as the original received data does. A similar result holds for Quick-Look-In (QLI) codes as well. In this case, however, the precise innovation is not defined. We see that this innovation-like quantity is related to the linear smoothed estimate of the information. The essence of innovations approach to a linear filtering problem is first to whiten the observed data, and then to treat the resulting simpler white-noise observations problem. In our case, this corresponds to the reduction of decoding complexity in the main decoder in an SST Viterbi decoder. We show the distributions related to the main decoder (i.e., the input distribution and the state distribution in the code trellis for the main decoder) are much biased under moderately noisy conditions. We see that these biased distributions actually lead to the complexity reduction in the main decoder. Furthermore, it is shown that the proposed innovations approach can be extended to maximum-likelihood (ML) decoding of block codes as well.