Decoding Received Blocks

If the received data was +1: (1-p) / p
If the received data was -1: p / (1-p)

exp ( 2y / s² )

It is usual to consider codewords to be equally likely a priori. This is reasonable if the source messages are all equally likely (any source redundancy being ignored, or remove by a preliminary data compression stage), provided that the mapping from source messages to codewords is onto. Decoding can then be done using only the parity check matrix defining the codewords, without reference to the generator matrix defining the mapping from source messages to codewords. Note that the condition that this mapping be onto isn't true with this software in the atypical case where the code is defined by a parity check matrix with redundant rows; see the discussion of linear dependence in parity check matrices. This minor complication is mostly ignored here, except by the exhaustive enumeration decoding methods.

Assuming equal a priori probabilities for codewords, the probability of correctly decoding an entire codeword is minimized by picking the codeword with the highest likelihood. One might instead wish to decode each bit to the value that is most probable. This minimizes the bit error rate, but is not in general guaranteed to lead a decoding for each block to the most probable complete codeword; indeed, the decoding may not be a codeword at all. Minimizing the bit error rate seems nevertheless to be the most sensible objective, unless block boundaries have some significance in a wider context.

Optimal decoding by either criterion is infeasible for general linear codes when messages are more than about 20 or 30 bits in length. The fundamental advantage of Low Density Parity Check codes is that good (though not optimal) decodings can be obtained by using a probability propagation algorithm, as described next.

Decoding by probability propagation

The probability propagation algorithm was originally devised by Robert Gallager in the early 1960's and later reinvented by David MacKay and myself. It can be seen as an instance of the sum-product algorithm for inference on factor graphs. See the references for details. Below, I give a fairly intuitive description of the algorithm.

The algorithm uses only the parity check matrix for the code, whose columns correspond to codeword bits, and whose rows correspond to parity checks, and the likelihood ratios for the bits derived from the data. It aims to find the probability of each bit of the transmitted codeword being 1, though the results of the algorithm are in general only approximate.

The begin, information about each bit of the codeword derived from the received data for that bit alone is expressed as a probability ratio, the probability of the bit being 1 divided by the probability of the bit being 0. This probability ratio is equal to the likelihood ratio (see above) for that bit, since 0 and 1 are assumed to be equally likely a priori. As the algorithm progresses, these probability ratios will be modified to take account of information obtained from other bits, in conjunction with the requirement that the parity checks be satisfied. To avoid double counting of information, for every bit, the algorithm maintains a separate probability ratio for each parity check that that bit participates in, giving the probability for that bit to be 1 versus 0 based only on information derived from other parity checks, along with the data received for the bit.

For each parity check, the algorithm maintains separate likelihood ratios (analogous to, but distinct from, the likelihood ratios based on received data), for every bit that participates in that parity check. These ratios give the probability of that parity check being satisfied if the bit in question is 1 divided by the probability of the check being satisfied if the bit is 0, taking account of the probabilities of each of the other bits participating in this check being 1, as derived from the probability ratios for these bits with respect to this check.

The algorithm alternates between recalculating the likelihood ratios for each check, which are stored in the lr fields of the parity check matrix entries, and recalculating the probability ratios for each bit, which are stored in the pr fields of the entries in the sparse matrix representation of the parity check matrix. (See the documentation on representation of sparse matrices for details on these entries.)

Recalculating the likelihood ratio for a check with respect to some bit may appear time consuming, requiring that all possible combinations of values for the other bits participating in the check be considered. Fortunately, there is a short cut. One can calculate

t = product of [ 1 / (1+p_i) - p_i / (1+p_i) ] = product of [ 2 / (1+p_i) - 1 ]

For a particular check, the product above differs for different bits, with respect to which we wish to calculate a likelihood ratio, only in that for each bit the factor corresponding to that bit is left out. We can calculate all these products easily by ordering the bits arbitrarily, computing running products of the factor for the first bit, the factors for the first two bits, etc., and also running products of the factor for the last bit, the factors for the last two bits, etc. Multiplying the running product of the factors up to i-1 by the running product of the factors from i+1 on gives the product needed for bit i. The second form of the factors above is used, as it requires less computation, and is still well defined even if some ratios are infinite.

To recalculate the probability ratio for a bit with respect to a check, all that is need is to multiply together the likelihood ratio for this bit derived from the received data (see above), and the current values of the likelihood ratios for all the other checks that this bit participates in, with respect to this bit. To save time, these products are computed by combining forward and backward products, similarly to the method used for likelihood ratios.

By including likelihood ratios from all checks, a similar calculation produces the current probability ratio for the bit to be 1 versus 0 based on all information that has propagated to the bit so far. This ratio can be thresholded at one to produce the current best guess as to whether this bit is a 1 or a 0.

The hope is that this algorithm will eventually converge to a state where these bit probabilities give a near-optimal decoding. This is does not always occur, but the algorithm behaves well enough to produce very good results at rates approaching (though not yet reaching) the theoretical Shannon limit.

Following the channel specification is a specification of the decoding method to use. The enum-block and enum-bit methods find the optimal decoding by exhaustive enumeration of codewords derived from all possible source messages. They differ in that enum-block decodes to the most likely codeword, whereas enum-bit decodes to the bits that are individually most probable. These methods require that a file containing a representation of a generator matrix be given, to allow enumeration of codewords. If the parity check matrix has no redundant rows, any valid generator matrix will give the same decoding (except perhaps if there is a tie). If redundant rows exist, the generator matrix should specify the same set of message bits as the generator matrix that was used for the actual encoding, since the redundancy will lead to some codeword bits being fixed at zero (see linear dependence in parity check matrices).

The prprp decoding method decodes using probability propagation. The maximum number of iterations of probability propagation to do is given following prprp. If a minus sign precedes this number, the maximum number of iterations is always done. If no minus sign is present, the algorithm stops once the tentative decoding, based on bit-by-bit probabilities, is a valid codeword. Note that continuing to the maximum number of iterations may possibly change the decoding compared to stopping at the first a valid codeword, and will usually result in at least slightly different bit probabilities (as written to bp-file, if specified).

A summary is displayed on standard error, giving the total number of blocks decoded, the number of blocks that decoded to valid codewords, and the average number of iterations of the decoding algorithm used.

If the -t option is given, block by block information is written to standard output, giving the block number (from zero), the number of iterations of the decoding algorithm, and whether the final decoded block was a valid codeword (0 or 1). These columns are preceded by a line of headers, so that the file is suitable for reading into the S-Plus or R statistics packages, with a command such as

data <- read.table(file,header=T)

Given a file of codewords in decoded-file (usually, decoded blocks output by decode), and a generator matrix from gen-file (needed only to determine where the message bits are located in a codeword), this program writes the message bits extracted from these codewords to the file extracted-file.

A newline is output at the end of each block written to extracted-file. Newlines in decoded-file are ignored. A warning is displayed on standard error if the number of bits in decoded-file is not a multiple of the block length.