Implementing gradient descent decoding (Q1024881): Difference between revisions

The paper is devoted to the development of a gradient decoding algorithm. The study gives answers to two questions: ``What information, if any, does Low-Density Parity Check (LDPC) decoding use that classical syndrome decoding does not?'', and ``What is a reasonable global measure of decoding progress that could be used to avoid pseudo-codewords?''. The proposed answer is formulated in the area of Iterative decoding, that makes use of ``characteristic crossing'' maps systematic, whereas classical texts have only one such map. In the paper is shown how to construct a gradient function for any linear code on a binary symmetric channel. An optimal iterative decoding algorithm, with proven accuracy, is presented. It has not implementation complexity advantage over classical syndrome decoding for an arbitrary code, but it is proposed a way to reduce the implementation cost of some highly geometric codes. An example is given in the end of the paper. Details are given for constructing a new (weighted) parity check matrix whose syndrome weight equals twice the cost-leader Hamming weight. It is shown that the constructed bit-flipping algorithm always converges in at most tree steps.