Reliability-based syndrome decoding of linear block codes

In this correspondence, various aspects of reliability-based syndrome decoding of binary codes are investigated. First, it is shown that the least reliable basis (LRB) and the most reliable basis (MRB) are dual of each other. By exploiting this duality, an algorithm performing maximum-likehbood (ML) soft-decision syndrome decoding based on the LRB is presented. Contrarily to previous LRB-hased ML syndrome decoding algorithms, this algorithm is more conveniently implementable for codes whose codimension is not small. New sufficient conditions for optimality are derived. These renditions exploit both the ordering associated with the LRB and the structure of the code considered. With respect to MRB based sufficient conditions, they present the advantage of requiring no soft information and thus can be preprocessed and stored. Based on these conditions, low-complexity soft-derision syndrome decoding algorithms for particular classes of codes are proposed. Finally, a simple algorithm is analyzed. After the construction of the LRB, this algorithm computes the syndrome of smallest Hamming weight among o(K-i) candidates, where K is the dimension of the code, for an order i of reprocessing, At practical bit-error rates, for codes of length N less than or equal to 128, this algorithm always outperforms any algebraic decoding algorithm capable of correcting up to t+1 errors with an order of reprocessing of at most 2, where t is the error-correcting capability of the code considered.