Syndrome Decoding and Some Important Linear Block Codes

Abdullah A. Hashim

Mainak Bhattacharyya, Ankur Raina

Decoding of linear block codes using syndrome decoding and finding whether there exists a codeword of weight$w$in a set of codewords are known to belong to a class of NP-complete problems. For syndrome decoding of linear block codes, we provide an algorithm that gives a probabilistic solution with least Hamming weight. The algorithm can speed up this process significantly with the help of quantum search algorithm. For this, we make use of a search algorithm inspired from Grover's search. We also suggest a general approach for building a quantum circuit for syndrome detection. We test the algorithm in IBM Quantum Experience using qasm simulator and perform the complexity analysis identifying the algorithm's domain of utility.

M.P.C. Fossorier, Shu Lin, Jakov Snyders

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-likelihood (ML) soft-decision syndrome decoding based on the LRB is presented. Contrarily to previous LRB-based 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 conditions exploit both the ordering associated with the LRB and the structure of the code considered. With respect to MRR-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-decision 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/sup 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/spl les/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.

Giuliano G. La Guardia

Zongwang Li, Youyun Xu, Wentao Song

M.P.C. Fossorier, Shu Hwa Lin, J. Synders

Maximum likelihood decoding of binary linear block codes is addressed by combining the approaches of processing the generator matrix G and parity-check matrix H.