Implementing gradient descent decoding
Robert A. Liebler · The Michigan Mathematical Journal · 2009
Abstract Given a linear block code on a BSC channel, and arbitrary pre-determined information about the coset of each possible received sequence, a method is given for construction of a new kind of parity check matrix that carries the given information. This pre-determined coset data is easily reconstructed by a simple decoder. When this coset information is related to coset leader weight, there is simple iterative gradient descent algorithm that is optimal, provably accurate and potentially of low complexity. An explicit gradient function construction is given for an code for which pseudo-codewords obstruct LDPC decoding convergence. 1 Introduction Many communication channels accept as input binary strings and return output strings of the same length that have been altered and whose terms can be interpreted as "the probability that 1 was sent in this position. " This paper is restricted to the binary symmetric channel (BSC) for which the output is also binary although the basic ideas seem to apply more generally. The task of a decoding algorithm is to reconstruct sent message(s) from the channel output. There are several critical attributes of a decoding algorithm. The design complexity is a measure of the effort required to design and implement an instance of the algorithm. The implementation cost is a measure of the (time and space) resources required to decode messages once the algorithm is implemented. The apparent accuracy of an algorithm is a measure of its ability to actually identify a nearest codeword to a given message in practice. The proven accuracy is a measure of the algorithm's proven ability to correctly move from message to nearest codeword without failure of any kind. A decoding algorithm is optimal if it correctly identifies the most likely channel error for each channel output for which there is a unique such error.