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 ma ximum-likehbood (ML) soft-decision syndrome decoding based on the LRB is presented. Contrarily to previous LRB-hased ML syndrome decoding al gorithms, this algorithm is more conveniently implementable for codes whose codimension is not small. New sufficient conditions for optimali ty 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 requir ing no soft information and thus can be preprocessed and stored. Based on these conditions, low-complexity soft-derision syndrome decoding a lgorithms for particular classes of codes are proposed. Finally, a sim ple algorithm is analyzed. After the construction of the LRB, this alg orithm computes the syndrome of smallest Hamming weight among o(K-i) c andidates, where K is the dimension of the code, for an order i of rep rocessing, At practical bit-error rates, for codes of length N less th an or equal to 128, this algorithm always outperforms any algebraic de coding algorithm capable of correcting up to t+1 errors with an order of reprocessing of at most 2, where t is the error-correcting capabili ty of the code considered.