Reduced complexity decoding algorithms for linear block codes

Abstract

We present an efficient soft decision maximum likelihood decoding algorithm for linear binary block codes. As in the Chase algorithms, test error patterns are generated, added to the received sequence and decoded, using a hard decision decoder. However, the set of test error sequences is adaptively chosen. This significantly reduces decoding complexity. Furthermore a sub-optimal decoding algorithm is developed by introducing constraints on the set of test error patterns used.