A new adaptive two-stage maximum-likelihood decoding algorithm for linear block codes

In this paper, we propose a new two-stage (TS) structure for computationally efficient maximum-likelihood decoding (MLD) of linear block codes. With this structure, near optimal MLD performance can be achieved at low complexity through TS processing. The first stage of processing estimates a minimum sufficient set (MSS) of candidate codewords that contains the optimal codeword, while the second stage performs optimal or suboptimal decoding search within the estimated MSS of small size. Based on the new structure, we propose a decoding algorithm that systematically trades off between the decoding complexity and the bounded block error rate performance. A low-complexity complementary decoding algorithm is developed to estimate the MSS, followed by an ordered algebraic decoding (OAD) algorithm to achieve flexible system design. Since the size of the MSS changes with the signal-to-noise ratio, the overall decoding complexity adaptively scales with the quality of the communication link. Theoretical analysis is provided to evaluate the potential complexity reduction enabled by the proposed decoding structure.