Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Conference on Decision and Control (CDC)

Root Locus Plots and Iterative Decoding

Christopher M. Kellett

Published Jan 1, 2006• 0 citations
Publisher

Abstract

A well known class of error correction codes called low-density parity-check (LDPC) codes have been the subject of a great deal of recent study in the coding community as a result of their ability to approach Shannon's fundamental capacity limit. Crucial to the performance of these codes is the use of an iterative decoder. We describe LDPC codes and the decoding algorithm and make a connection between the fixed points of the decoding algorithm and the well-known root locus plot. Via two example LDPC codes, we describe the insights afforded by the root locus plot

DOI
10.1109/cdc.2006.376931

Related papers

Bifurcations in iterative decoding and root locus plots

Christopher M. Kellett, Steven R. Weller

A class of error correction codes called ‘low-density parity-check (LDPC)’ codes have been the subject of a great deal of recent study in the coding community as a result of their ability to approach Shannon's fundamental capacity limit. Crucial to the performance of these codes is the use of an ‘iterative’ decoder. These iterative decoders are effectively high-dimensional, nonlinear dynamical systems and, consequently, control-theoretic tools are useful in analysing such decoders. The authors describe LDPC codes and the decoding algorithm and make a connection between the fixed points of the decoding algorithm and the well-known root locus plot. Through two examples of LDPC codes, the authors show that the root locus plot visually captures the bifurcation behaviour of iterative decoding that occurs at the signal-to-noise ratio predicted by Shannon's noisy channel coding theorem.

IET Control Theory and Applications•Dec 6, 2008•2 citations

Low-density parity-check codes

Sarah J. Johnson

Introduction In this chapter we introduce low-density parity-check (LDPC) codes, a class of error correction codes proposed by Gallager in his 1962 PhD thesis 12 years after error correction codes were first introduced by Hamming (published in 1950). Both Hamming codes and LDPC codes are block codes: the messages are broken up into blocks to be encoded at the transmitter and similarly decoded as separate blocks at the receiver. While Hamming codes are short and very structured with a known, fixed, error correction ability, LDPC codes are the opposite, usually long and often constructed pseudo-randomly with only a probabilistic notion of their expected error correction performance. The chapter begins by presenting parity bits as a means to detect and, when more than one is employed, to correct errors in digital data. Block error correction codes are described as a linear combination of parity-check equations and thus defined by their parity-check matrix representation. The graphical representation of codes by Tanner graphs is presented and the necessary graph theoretic concepts introduced. In Section 2.4 iterative decoding algorithms are introduced using a hard decision algorithm (bit flipping), so that the topic is developed first without reference to probability theory. Subsequently the sum–product decoding algorithm is presented. This chapter serves as a self-contained introduction to LDPC codes and their decoding. It is intended that the material presented here will enable the reader to implement LDPC encoders and iterative decoders.

Cambridge University Press eBooks•Nov 19, 2009•6 citations

Controlling the Error Floors of the Low-Density Parity-Check Codes

Shuai Zhang

The goal of error control coding is to encode information in such a way, that in the event that errors occur during transmission over a noisy communication channel or during storage in an unreliable memory, the receiver can correct the errors and recover the original transmitted information. Low-density parity-check (LDPC) codes are a kind of high performance linear block code, which are already used in many recent communication systems. Information rates guaranteed by these codes approach the theoretical Shannon capacity limit. In addition, LDPC codes are now widely used in practice and included in many communication standards. Therefore study of these codes is very important and practical approaches to their design and decoding techniques are of great interest. There exist very good decoding algorithms for LDPC codes with respect to different channel models. However, LDPC codes suffer from the infamous error floor problem at high signal-to-noise ratios. This problem is attributed to the trapping sets by Richardson. It is shown that the dominant trapping sets of regular LDPC codes, so called absorption sets, undergo a two-phase dynamic behavior in the iterative message-passing decoding algorithm. We present a linear dynamic model for the iteration behavior of these sets. It can be seen that they undergo an initial geometric growth phase which stabilizes in a final bit-flipping behavior where the algorithm reaches a fixed point. Our analysis is shown to lead to very accurate numerical calculations of the error floor bit error rates down to error rates that are inaccessible by simulation. The topologies of the dominant absorption sets of two example codes, the IEEE 802.3an [2048,1723] regular (6,32) LDPC code and the Tanner [155,64,20] regular (3,5) LDPC code, are identified and tabulated by using topological features in combination with search algorithms, respectively. To make our analysis more complete, we provide more solid evidence showing that trapping sets are equivalent to absorption sets. In other words, we argue that absorption sets characterize all failure mechanisms. Some insights from our linear analysis can be borrowed to approach this problem. Another insight that this formula provides to us is the means to reduce the error floor, which is another important part of what we hoped to achieve by developing the formula in the first place. By allowing the log-likelihood ratios (LLRs) utilized by the message-passing decoding to grow bigger in precision length, the absorption sets as a trouble-causing structure will be successfully corrected. Therefore, the absorption sets, generically born with the code design, will no longer threaten the error correcting performance as long as the messages have enough room and time to grow. This translates to greater LLR clipping thresholds and more iterations, both of which are preset at the decoder. However, the actual settings are dependent on how much the subgraph of the dominant absorption set resembles that of a non-zero minimum-weight codeword, therefore the settings are empirical. In general more likeness in their topologies, the more effort it costs to correct the absorption set.

•Jan 1, 2013•0 citations

Low‐Density Parity‐Check Codes

Christian B. Schlegel, Lance C. Pérez

Low-density parity-check (LDPC) codes can rightfully take their stand next to turbo codes as the most powerful and most popular error control codes known. They offer a performance spectacularly close to theoretical limits when decoded using iterative soft decision algorithms. This chapter explores the properties and structure of low-density parity-check codes. It begins with the fundamental construction of regular LDPC codes and their representation as bipartite graphs. The graphical representation of LDPC codes then leads to the notion of irregular LDPC codes, which have been used to improve performance, and to the density evolution analysis technique, which predicts the performance of these codes.

Wiley eBooks•Aug 29, 2015•6 citations

Finite precision implementation of LDPC decoders

Guido Masera, Federico Quaglio, F. Vacca

Low-density parity-check (LDPC) codes are among the most powerful known error correcting codes and they have been shown to achieve performance very close to the Shannon bound. In practical hardware implementations of LDPC decoders, bit error rate performances are affected strongly by fixed-point representation of processed data and, although many papers have been published in recent years on the subject of LDPC codes, only a few of them report results on the effects of finite precision. In the paper two novel arithmetic approximations for the basic processing operations of the decoding algorithm are presented. The two proposed solutions are analysed in terms of bit error rate performance for different finite precison representations of both external and internal data; the estimated performance loss is comparable to that reported by previous works and limited to approximately 0.1 dB for cases of interests. However the proposed solutions support a reduced complexity formulation of the decoding algorithm, so enabling the implementation of flexible decoders that can be adapted to different LDPC codes, block sizes and code rates.

IEE Proceedings - Communications•Jan 1, 2005•33 citations

Iterative Decoding of Low-Density Parity Check Codes

Venkatesan Guruswami

Much progress has been made on decoding algorithms for error-correcting codes in the last decade. In this article, we give an introduction to some fundamental results on iterative, message-passing algorithms for low-density parity check codes. For certain important stochastic channels, this line of work has enabled getting very close to Shannon capacity with algorithms that are extremely ecient (both in theory and practice).

Bulletin of the European Association for Theoretical Computer Science•Jan 1, 2006•12 citations
A well known class of error correction codes called low-density parity-check (LDPC) codes have been the subject of a great deal of recent study in the coding community as a result of their ability to approach Shannon's fundamental capacity limit. Crucial to the performance of these codes is the use of an iterative decoder. We describe LDPC codes and the decoding algorithm and make a connection between the fixed points of the decoding algorithm and the well-known root locus plot. Via two example LDPC codes, we describe the insights afforded by the root locus plot
A class of error correction codes called ‘low-density parity-check (LDPC)’ codes have been the subject of a great deal of recent study in the coding community as a result of their ability to approach Shannon's fundamental capacity limit. Crucial to the performance of these codes is the use of an ‘iterative’ decoder. These iterative decoders are effectively high-dimensional, nonlinear dynamical systems and, consequently, control-theoretic tools are useful in analysing such decoders. The authors describe LDPC codes and the decoding algorithm and make a connection between the fixed points of the decoding algorithm and the well-known root locus plot. Through two examples of LDPC codes, the authors show that the root locus plot visually captures the bifurcation behaviour of iterative decoding that occurs at the signal-to-noise ratio predicted by Shannon's noisy channel coding theorem.
Introduction In this chapter we introduce low-density parity-check (LDPC) codes, a class of error correction codes proposed by Gallager in his 1962 PhD thesis 12 years after error correction codes were first introduced by Hamming (published in 1950). Both Hamming codes and LDPC codes are block codes: the messages are broken up into blocks to be encoded at the transmitter and similarly decoded as separate blocks at the receiver. While Hamming codes are short and very structured with a known, fixed, error correction ability, LDPC codes are the opposite, usually long and often constructed pseudo-randomly with only a probabilistic notion of their expected error correction performance. The chapter begins by presenting parity bits as a means to detect and, when more than one is employed, to correct errors in digital data. Block error correction codes are described as a linear combination of parity-check equations and thus defined by their parity-check matrix representation. The graphical representation of codes by Tanner graphs is presented and the necessary graph theoretic concepts introduced. In Section 2.4 iterative decoding algorithms are introduced using a hard decision algorithm (bit flipping), so that the topic is developed first without reference to probability theory. Subsequently the sum–product decoding algorithm is presented. This chapter serves as a self-contained introduction to LDPC codes and their decoding. It is intended that the material presented here will enable the reader to implement LDPC encoders and iterative decoders.
The goal of error control coding is to encode information in such a way, that in the event that errors occur during transmission over a noisy communication channel or during storage in an unreliable memory, the receiver can correct the errors and recover the original transmitted information. Low-density parity-check (LDPC) codes are a kind of high performance linear block code, which are already used in many recent communication systems. Information rates guaranteed by these codes approach the theoretical Shannon capacity limit. In addition, LDPC codes are now widely used in practice and included in many communication standards. Therefore study of these codes is very important and practical approaches to their design and decoding techniques are of great interest. There exist very good decoding algorithms for LDPC codes with respect to different channel models. However, LDPC codes suffer from the infamous error floor problem at high signal-to-noise ratios. This problem is attributed to the trapping sets by Richardson. It is shown that the dominant trapping sets of regular LDPC codes, so called absorption sets, undergo a two-phase dynamic behavior in the iterative message-passing decoding algorithm. We present a linear dynamic model for the iteration behavior of these sets. It can be seen that they undergo an initial geometric growth phase which stabilizes in a final bit-flipping behavior where the algorithm reaches a fixed point. Our analysis is shown to lead to very accurate numerical calculations of the error floor bit error rates down to error rates that are inaccessible by simulation. The topologies of the dominant absorption sets of two example codes, the IEEE 802.3an [2048,1723] regular (6,32) LDPC code and the Tanner [155,64,20] regular (3,5) LDPC code, are identified and tabulated by using topological features in combination with search algorithms, respectively. To make our analysis more complete, we provide more solid evidence showing that trapping sets are equivalent to absorption sets. In other words, we argue that absorption sets characterize all failure mechanisms. Some insights from our linear analysis can be borrowed to approach this problem. Another insight that this formula provides to us is the means to reduce the error floor, which is another important part of what we hoped to achieve by developing the formula in the first place. By allowing the log-likelihood ratios (LLRs) utilized by the message-passing decoding to grow bigger in precision length, the absorption sets as a trouble-causing structure will be successfully corrected. Therefore, the absorption sets, generically born with the code design, will no longer threaten the error correcting performance as long as the messages have enough room and time to grow. This translates to greater LLR clipping thresholds and more iterations, both of which are preset at the decoder. However, the actual settings are dependent on how much the subgraph of the dominant absorption set resembles that of a non-zero minimum-weight codeword, therefore the settings are empirical. In general more likeness in their topologies, the more effort it costs to correct the absorption set.
Low-density parity-check (LDPC) codes can rightfully take their stand next to turbo codes as the most powerful and most popular error control codes known. They offer a performance spectacularly close to theoretical limits when decoded using iterative soft decision algorithms. This chapter explores the properties and structure of low-density parity-check codes. It begins with the fundamental construction of regular LDPC codes and their representation as bipartite graphs. The graphical representation of LDPC codes then leads to the notion of irregular LDPC codes, which have been used to improve performance, and to the density evolution analysis technique, which predicts the performance of these codes.
Low-density parity-check (LDPC) codes are among the most powerful known error correcting codes and they have been shown to achieve performance very close to the Shannon bound. In practical hardware implementations of LDPC decoders, bit error rate performances are affected strongly by fixed-point representation of processed data and, although many papers have been published in recent years on the subject of LDPC codes, only a few of them report results on the effects of finite precision. In the paper two novel arithmetic approximations for the basic processing operations of the decoding algorithm are presented. The two proposed solutions are analysed in terms of bit error rate performance for different finite precison representations of both external and internal data; the estimated performance loss is comparable to that reported by previous works and limited to approximately 0.1 dB for cases of interests. However the proposed solutions support a reduced complexity formulation of the decoding algorithm, so enabling the implementation of flexible decoders that can be adapted to different LDPC codes, block sizes and code rates.