Iterative decoding beyond belief propagation

Home Publications Projects Tools Links
  • Contact
    • +1-520-626-5550
    • vasic@ece.arizona.edu

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

google ukash ukash bozdur

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.

Book Chapters


BibTeX B. Vasić, D.V. Nguyen, and S. K. Chilappagari, "Chapter 6 - Failures and Error Floors of Iterative Decoders ," Academic Press Library in Mobile and Wireless Communications , 2014, pp. 299 - 341.

Journal Papers


BibTeX F. Cai, X. Zhang, D. Declercq, B. Vasić, and S. K. Planjery, "Finite Alphabet Iterative Decoders for LDPC Codes: Optimization, Architecture and Analysis," IEEE Transactions on Circuits and Systems - Part I: Regular Papers, vol. 61, no. 5, pp. 1366-1375, May 2014.
BibTeX D. V. Nguyen and B. Vasić, "Two-Bit Bit Flipping Algorithms for LDPC Codes and Collective Error Correction," IEEE Trans. Comm., vol. 62, no. 4, pp. 1153-1163, April 2014.
BibTeX B. Vasić and B. Vasić, "Simplification Resilient LDPC-Coded Sparse-QIM Watermarking for 3D-Meshes," IEEE Trans. Multimedia, vol. 15, no. 7, pp. 1532-1542 , Nov. 2013.
BibTeX S. K. Planjery, D. Declercq, L. Danjean, and B. Vasić, "Finite Alphabet Iterative Decoders, Part I: Decoding Beyond Belief Propagation on the Binary Symmetric Channel," IEEE Trans. Commun., vol. 61, no. 10, pp. 4033 - 4045, Nov. 2013.
BibTeX D. Declercq, B. Vasić, S. K. Planjery, and E. Li, "Finite Alphabet Iterative Decoders, Part II: Improved Guaranteed Error Correction of LDPC Codes via Iterative Decoder Diversity," IEEE Trans. Commun., vol. 61, no. 10, pp. 4046 - 4057, Nov. 2013.
BibTeX L Danjean, B. Vasić, M. K. Marcellin, and D. Declercq, "Interval-Passing Algorithm for Chemical Mixture Estimation," IEEE Signal Process. Lett., vol. 20, pp. 849 - 852, Sept. 2013.
BibTeX I. B. Djordjevic, J. Anguita, and B. Vasić, "Error-Correction Coded Orbital-Angular-Momentum Modulation for FSO Channels Affected by Turbulence," IEEE/OSA J. Lightw. Technol., vol. 30, no. 17, pp. 2846 - 2852, Sep. 2012.
BibTeX D. V. Nguyen, S. K. Chilappagari, B. Vasić, and M. W. Marcellin, "On the construction of structured LDPC codes free of small trapping sets," IEEE Trans. Inf. Theory, vol. 58, no. 4, pp. 2280 - 2302, Apr. 2012.
BibTeX S. K. Planjery, D. Declercq, L. Danjean, and B. Vasić, "Finite alphabet iterative decoders for LDPC codes surpassing floating-point iterative decoders," Electron. Lett., vol. 47, no. 16, pp. 919 - 921, Aug. 2011.
BibTeX S. K. Chilappagari, M. Chertkov, and B. Vasić, "An Efficient Instanton Search Algorithm for LP Decoding of LDPC Codes Over the BSC," IEEE Trans. Inf. Theory, vol. 57, no. 7, pp. 4417 - 4426, Jul. 2011.
BibTeX B. V. Vasić and H. Dyball, "Interview," Electron. Lett., vol. 47, no. 4, pp. 226, Feb. 2011.
BibTeX S. K. Chilappagari, D. V. Nguyen, B. Vasić, and M. W. Marcellin, "Error correction capability of column-weight-three LDPC codes under the Gallager A algorithm - PART II," IEEE Trans. Inf. Theory, vol. 56, no. 6, pp. 2626 - 2639, Jun. 2010.
BibTeX S. K. Chilappagari, D. V. Nguyen, B. Vasić, and M. W. Marcellin, "On Trapping Sets and Guaranteed Error Correction Capability of LDPC codes and GLDPC Codes," IEEE Trans. Inf. Theory, vol. 56, no. 4, pp. 1600 - 1611, Apr. 2010.
BibTeX J. A. Anguita, M. A. Neifeld, B. Hildner, and B. Vasić, "Rateless coding on experimental temporally correlated FSO channels," J. Lightw. Technol., vol. 28, no. 7, pp. 990 - 1002, Apr. 2010.

Conference Papers


BibTeX S. Brkic, P. Ivanis, G. Djordjevic, and B. Vasić, "Symbolic Analysis of Faulty Logic Circuits in the Presence of Correlated Gate Failures," Telecommunication Forum (TELFOR 2014), Nov 2013, pp. 369 - 372.
BibTeX O-A Rasheed, S. Brkic, P. Ivanis, and B. Vasić, "Performance Analysis of Faulty Gallager-B Decoding of QC-LDPC Codes," 2013 21st Telecommunications Forum Telfor (TELFOR), Nov. 2013, pp. 323 - 326.
BibTeX M. Khatami and B. Vasić, "Combined modulation and error correction decoder using generalized belief propagation," Proc. 49th Int. Telemetering Conf., Oct. 21 - 24 2013.
BibTeX L. Danjean, B. Vasić, M. K. Marcellin, and D. Declercq, "Low-Complexity Iterative Reconstruction Algorithms in Compressed Sensing," Proc. 49th Int. Telemetering Conf., Oct. 21 - 24 2013.
BibTeX B. Vasić and B. Vasić, "Blind QIM-LDPC Watermarking of 3D-Meshes," Proc. IEEE Int. Conf. on Commun., Workshop on Information Security over Noisy and Lossy Communication Systems, Jun. 9 - 13 2013, pp. 702 - 706.
BibTeX F. Cai, X. Zhang, D. Declercq, B. Vasić, D. V. Nguyen, and S. K. Planjery, "Low-Complexity Finite Alphabet Iterative Decoders for LDPC Codes," Proc. IEEE Int. Symp. on Circuits and Systems, May 19 - 23 2013, pp. 1332 - 1335.
BibTeX S. M. Khatami, L. Danjean, D. V. Nguyen, and B. Vasić, "An Efficient Exhaustive Low-Weight Codeword Search for Structured LDPC Codes," Proc. Inform. Theory and Applications Workshop, Feb. 10 - 15 2013.
BibTeX B. Vasić and B. Vasić, "A runlength coded LDPC scheme for insertion/deletion correction in multimedia watermarking," Proc. 48th Int. Telemetering Conf., vol. XLVIII, Oct. 22 - 25 2012, pp. 867-876.
BibTeX D. Declercq, E. Li, B. Vasić, and S.K. Planjery, "Approaching maximum likelihood decoding of finite length LDPC codes via FAID diversity," IEEE Inform. Theory Workshop, Sep. 3 - 7 2012, pp. 487-491.
BibTeX D. V. Nguyen, B. Vasić, and M. W. Marcellin, "Selecting two-bit bit flipping algorithms for collective error correction," Proc. IEEE Int. Symp. Theory, Jul. 1 - 6 2012, pp. 2881 - 2885.
BibTeX S. K. Planjery, B. Vasić, and D. Declercq, "Enhancing the error correction of finite alphabet iterative decoders via adaptive decimation," Proc. IEEE Int. Symp. Theory, Jul. 1 - 6 2012, pp. 2876 - 2880.
BibTeX D. Declercq, B. Vasić, S. K. Planjery, and E. Li, "Finite alphabet iterative decoders approaching maximum likelihood performance on the Binary Symmetric Channel," Proc. Inform. Theory and Applications Workshop, Feb. 5 - 10 2012, pp. 23 - 32.
BibTeX L. Danjean, D. Declercq, S. K. Planjery, and B. Vasić, "On the Selection of Finite Alphabet Iterative Decoders for LDPC codes on the BSC," Proc. IEEE Inform. Theory Workshop, Oct. 16 - 20 2011, pp. 345-349.
BibTeX D. V. Nguyen, B. Vasić, and M. W. Marcellin, "Methods of searching for trapping sets of quasi-cylic LDPC codes and their applications in code construction," Proc. 47th Int. Telemetering Conf., Oct. 24 - 27 2011, pp. 1 - 10.
BibTeX L. Danjean, D. Declercq, S. Planjery, and B. Vasić, "Trapping Sets bruites pour la selection des decodeurs multi-niveaux des codes LDPC," Proc. XXXIIIe Colloque GRETSI, Sep. 5 - 8 2011.
BibTeX I. B. Djordjevic, J. Anguita, and B. Vasić, "On the LDPC-coded OAM modulation for communication over atmospheric turbulence channels," Proc. SPIE Free-Space and Atmospheric Laser Commun. XI, Aug. 24 - 25 2011.
BibTeX S. K. Planjery, B. Vasić, and D. Declercq, "Decimation-enhanced finite alphabet iterative decoders for LDPC codes on the BSC," Proc. IEEE Int. Symp. on Inform. Theory, Jul. 31 - Aug. 5 2011, pp. 2383 - 2387.
BibTeX D. V. Nguyen, M. W. Marcellin, and B. Vasić, "Two-bit bit flipping decoding of LDPC codes," Proc. IEEE Int. Symp. on Inform. Theory, Jul. 31 - Aug. 5 2011, pp. 1995 - 1999.
BibTeX L. Danjean, D. Declercq, S. K. Planjery, and B. Vasić, "Decodeurs multi-niveaux pour le decodage quasi-optimal des codes LDPC," Proc. Manifestation des JEunes Chercheurs en Sci. et Technologies de l'Inform. et de la Commun., Oct. 13 - 15 2010, pp. 1 - 4.
BibTeX S. K. Planjery, B. Vasić, D. Declercq, and M. W. Marcellin, "Low-complexity finite precision decoders for low-density parity-check codes," Proc. 46th Int. Telemetering Conf., Oct. 2010.
BibTeX D. Declercq, L. Danjean, E. Li, S. K. Planjery, and B. Vasić, "Finite Alphabet Iterative Decoding (FAID) of the (155,64,20) Tanner Code," Proc. 6th Int. Symp. on Turbo-Codes and Iterative Inform. Process., Sep. 6 - 10 2010, pp. 11 - 15.
BibTeX D. V. Nguyen, M. Leslie, and B. Vasić, "Short column-weight-three LDPC codes without small trapping sets," Proc. 48th Allerton Conf. on Commun., Control, and Computing, Sep. 29 - Oct. 1 2010, pp. 172 - 179.
BibTeX B. Vasić, A. R. Krishnan, D. V. Nguyen, S. K. Planjery, and D. Declercq, "Iterative decoding beyond belief propagation and LDPC codes with guaranteed low error floors," Proc. The 21st Magnetic Recording Conf., Aug. 16 - 18 2010, pp. 47 - 48.
BibTeX D. V. Nguyen, B. Vasić, M. W. Marcellin, and S. K. Chilappagari, "Structured LDPC codes from permutation matrices free of small trapping sets," Proc. IEEE Inform. Theory Workshop, Aug. 30 - Sep. 3 2010, pp. 1 - 5.
BibTeX S. K. Planjery, D. Declercq, S. K. Chilappagari, and B. Vasić, "Multilevel decoders surpassing belief propagation on the binary symmetric channel," Proc. IEEE Int. Symp. on Inform. Theory, Jun. 13 - 18 2010, pp. 769 - 773.