Finite Alphabet Iterative decoders for LDPC codes surpassing BP
At the heart of modern coding theory lies the fact that low-density parity-check (LDPC) codes can be efficiently decoded by belief propagation (BP). The BP is an inference algorithm which operates on a graphical model of a code, and lends itself to low-complexity and high-speed implementations, making it the algorithm of choice in many applications. It has unprecedentedly good error rate performance, so good that when decoded by the BP, LDPC codes approach theoretical limits of channel capacity.
However, this capacity approaching property holds only in the asymptotic limit of code length, while codes of practical lengths suffer abrupt performance degradation in the low noise regime known as the error floor phenomenon. Our study of error floor has led to an interesting and surprising finding that it is possible to design iterative decoders which are much simpler yet better than belief propagation! These decoders do not propagate beliefs but a rather different kind of messages that reflect the local structure of the code graph. This has opened a plethora of exciting theoretical problems and applications.
A simple motivating example is shown in the figure below. Let us consider decoding over the binary symmetric channel (BSC) and assume that the all-zero codeword was transmitted. The figure below illustrates how the incorporation of an additional bit in the messages can be used to capture the local neighborhood of an error pattern that the Gallager-A algorithm would fail on.
In the above figure, circles denote the variable nodes, and squares denote the check nodes. The induced subgraph of the error pattern forms a cycle of length 6. denotes the variable nodes of the cycle that are initially wrong, and denotes the variable nodes initially correct outside the cycle. Figure (a) shows the message passing of the Gallager-A algorithm. The Gallager-A algorithm fails because the node cannot distinguish between a message coming from the cycle and a message coming from outside the cycle, and wrong messages are circulated within the cycle. Figure (b) shows the message passing of a 2-bit decoder. By the incorporation of an extra bit, node is able to distinguish between messages coming from the cycle and messages coming from outside the cycle, and the decoder can successfully correct the error pattern with an appropriately chosen update rule.
In this project, we focus on developing this new type of message passing decoders which we refer to as finite alphabet iterative decoders (FAIDs) for LDPC codes. Unlike traditional BP based iterative decoders which propagate probabilities or log-likelihoods, these new decoders propagate messages, which are levels belonging to a finite alphabet, that require only a finite number of bits for their representation. The update function used at the variable nodes during decoding are maps derived using knowledge of trapping sets and are chosen to increase the guaranteed error correction capability of the code. Hence, these decoders are not only different from quantized BP decoders but also have the potential to surpass floating-point BP in the error floor region in spite of their significantly reduced complexity.
An example of a particularly good map defined for a FAID that is used for updating messages at a variable node in column-weight three codes is shown below in the form of a look-up table when the received value from the BSC is 1. The messages are represented as levels belonging to a finite alphabet of size 7. They can also be represented as 3-bit binary vectors as shown in the previous example.
Our results have shown that FAIDs requiring only 3 bits of precision for the representation of the messages can surpass floating-point BP in the error floor region for several column-weight three codes including structured high-rate codes that were designed for the best known BP performance at the given rate and length. We are currently working on designing decoders for much higher guaranteed error correction capability as well as extending this work to non-binary channels and higher column-weight codes. We are also investigating techniques to analyze the decoders in order to derive explicit conditions on the graph that guarantees performance in terms of error correction capability.
Project Members
- Prof. Bane Vasic
- Prof. David Declercq
- Shiva Kumar Planjery
- Ludovic Danjean
Sponsor
- NSF Grant CCF-0963726
Project Publications
Patents
BibTeX | S. K. Planjery, S. K. Chilappagari, B. Vasić, and D. Declercq, "Low Complexity finite precision decoders and apparatus for LDPC codes," Jun. 2013. |
BibTeX | B. Vasić and D. Declercq, "A methodology for selecting multiple decoders for decoder diversity that improves the guaranteed error correction capability of low-density parity check codes," Feb. 2012. |
BibTeX | D. V. Nguyen and B. Vasić, "Structured LDPC codes from permutation matrices," Mar. 2011. |
BibTeX | D. V. Nguyen and B. Vasić, "Multibit bit flipping decoding of LDPC codes," Feb. 2011. |
Book or Monographs
BibTeX | I. Djordjevic, W. E. Ryan, and B. Vasić, "Coding for optical channels," 2010. |