A List-Decoding Approach to Low-Complexity Soft Maximum-Likelihood Decoding of Cyclic Codes

摘要

This paper provides a reduced-complexity approach to maximum likelihood (ML) decoding of cyclic codes. A cyclic code with generator polynomial g_cyclic(x) may be considered a terminated convolutional code with a nominal rate of 1. The trellis termination redundancy lowers the rate from 1 to the actual rate of the cyclic code. The proposed decoder represents g_cyclic(x) as the product of two polynomials, a convolutional code (CC) polynomial g_cc(x) and a cyclic redundancy check (CRC) polynomial g_crc(x), i.e., g_cyclic(x) = g_cc(x)g_crc(x). This representation facilitates serial list Viterbi algorithm (S-LVA) decoding. Viterbi decoding is performed on the natural trellis for g_cc(x), and g_crc(x) is used as a CRC to determine when the S-LVA should conclude. At typical target frame error rates, the expected list size of S-LVA is small, and the average decoding complexity is dominated by the trellis complexity of g_cc(x) rather than g_cyclic(x). Some high-rate binary Bose-Chaudhuri- Hocquenghem (BCH) examples show that the proposed use of S-LVA via factorization significantly lowers complexity as compared to using the minimum-complexity trellis representation of g_cyclic(x) for soft ML decoding.