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

arXiv:cs/0611089 · IEEE Transactions on Information Theory

The Extraction and Complexity Limits of Graphical Models for Linear Codes

Thomas R. Halford, K.M. Chugg

Published Aug 27, 2008• 17 citations
arXivHTMLPDF

Abstract

Two broad classes of graphical modeling problems for codes can be identified in the literature: constructive and extractive problems. The former class of problems concern the construction of a graphical model in order to define a new code. The latter class of problems concern the extraction of a graphical model for a (fixed) given code. The design of a new low-density parity-check code for some given criteria (e.g., target block length and code rate) is an example of a constructive problem. The determination of a graphical model for a classical linear block code that implies a decoding algorithm with desired performance and complexity characteristics is an example of an extractive problem. This work focuses on extractive graphical model problems and aims to lay out some of the foundations of the theory of such problems for linear codes. The primary focus of this work is a study of the space of all graphical models for a (fixed) given code. The tradeoff between cyclic topology and complexity in this space is characterized via the introduction of a new bound: the forest-inducing cut-set bound (FI-CSB). The proposed bound provides a more precise characterization of this tradeoff than that which can be obtained using existing tools (e.g., the CSB) and can be viewed as a generalization of the square-root bound for tail-biting trellises to graphical models with arbitrary cyclic topologies. Searching the space of graphical models for a given code is then enabled by introducing a set of basic graphical model transformation operations that are shown to span this space. Finally, heuristics for extracting novel graphical models for linear block codes using these transformations are investigated.

DOI
10.1109/tit.2008.928271

Related papers

The Complexity Limits of Graphical Models for Linear Codes

Thomas R. Halford, K.M. Chugg

Since the discovery of turbo codes in the 1990s, much of the work concerning graphical models for codes has focused on constructing models in order to define a new code. This work focuses on the theoretical foundations of the inverse problem to code construction -extracting a graphical model for a given (fixed) code. Specifically, limits on the space of graphical models for a given code are examined. A number of results concerning these limits (e.g., the cut-set bound, the square-root bound) are first reviewed. Following this review, recent results concerning these limits are presented. It is first shown that the Tanner graphs of many classical block codes necessarily contain many short cycles. It is then shown that cycle-free binary graphical models do not support good codes thus generalizing Trachtenberg's work concerning the existence of cycle-free Tanner graphs. Finally, and most significantly, the tree-inducing cut-set bound (TI-CSB) is derived and discussed. The TI-CSB provides a characterization of the tradeoff between complexity and density in the family of graphical models for a given code. For example, the TI-CSB can be used to show that anrth-root complexity reduction (with respect to the least-complex cycle-free model) requires the introduction of at leastr(r- 1)/2 cycles thus generalizing the square-root bound to graphical models with arbitrary cyclic topologies.

IEEE Information Theory Workshop (ITW)•Sep 1, 2007•1 citation

Iterative decoding and graphical code representations

Meina Xu

Since the invention of turbo codes, there has been an explosion of interest in iterative decoding and graphical representation of codes. This thesis examines the iterative decoding of codes defined on graphs with cycles, which appears to be an efficient means of achieving the Shannon limit. Much of this analysis is on the iterative min-sum decoding of tail-biting codes and cycle codes. We have identified the pseudocodeword as the cause of the suboptimal performance of the iterative decoder, and we have obtained a union bound for the performance of the iterative decoder on both AWGN and BSC channels. Using the union bound argument, for cycle codes, we have shown that the performance of the iterative decoder is asymptotically as good as that of the ML decoder. As for tail-biting codes, the same thing is true if the lowest weight pseudocodeword is at least the minimum weight of the code. Unfortunately, the analysis of tail-biting codes and cycle codes does not extend to turbo codes and low density parity check codes in general. Our next approach is to determine the average behavior of message passing algorithms by studying the evolution of their "message" densities. For the class of "repeat and accumulate" serially concatenated turbo-like codes, we have devised an algorithm for determining their "threshold" values. When the signal-to-noise ratio is larger than the threshold value, the error probabilities of message passing algorithms approach zero, whereas if the signal-to-noise ratio is less than the threshold value, the error probability stays bounded away from zero. Some message passing algorithms and graphical representation of codes are efficient means of devising ML or MAP decoding algorithms. We have proposed a junction tree representation for linear block codes, and we have shown that the minimum junction tree can be less complex than the minimal trellis.

•Mar 11, 2008•1 citation

Error Floors of LDPC Codes and Related Topics

Brian K. Butler

Since their rediscovery in the late 1990s, low-density parity-check (LDPC) codes have rapidly become one the most important classes of error correcting codes. LDPC codes have a graphical description and are generally decoded iteratively. The graph of an iteratively decoded code's error rate performance versus the channel quality is typically divided into two regions. The error floor region appears at higher channel quality and is characterized by a more gradual decrease in error rate as channel quality improves. For iterative decoders the error floor is apparently determined by small structures within the code that are specific to the selected graphical description of the code and subtle details of the decoding algorithm. This thesis addresses several issues of LDPC error floors in the additive white Gaussian noise channel. First, we find the source of several well publicized error floors to be numerical issues within the message-passing decoder. We propose numerical improvements to several decoding formulations which substantially lower error floors. Next, we examine and refine error-floor prediction models. A time-variant linear state-space model is presented and analyzed. Graph theory is applied to analyze the small error-prone structures within the code. While we find our techniques encounter considerable problems in determining the error floors for iterative decoders with unrestricted dynamic range, their predictions are quite accurate when significant range restrictions are present. The final issue of LDPC error floors which we address relates to the minimum distance of quasi-cyclic (QC) LDPC codes. We derive improved minimum distance upper bounds for codes which are punctured and codes which contain a significant number of zeros in their protomatrices. These bound are then applied to a family of protograph-based LDPC codes standardized for use in deep-space communications. In the case of the rate-1/2 code, our upper bounds demonstrate that the previously promulgated ensemble lower bounds do not apply to QC constructions at block lengths beyond 4400 bits. The last part of this dissertation is a fairly separate piece of work on bounding the spectral radius of a large class of nonnegative matrices. We apply these bounds to digraphs and derive several associated equality conditions.</

•Jan 1, 2013•1 citation

Error Floors of LDPC Codes and Related Topics - eScholarship

Brian K. Butler

Since their rediscovery in the late 1990s, low-density parity-check (LDPC) codes have rapidly become one the most important classes of error correcting codes. LDPC codes have a graphical description and are generally decoded iteratively. The graph of an iteratively decoded code's error rate performance versus the channel quality is typically divided into two regions. The error floor region appears at higher channel quality and is characterized by a more gradual decrease in error rate as channel quality improves. For iterative decoders the error floor is apparently determined by small structures within the code that are specific to the selected graphical description of the code and subtle details of the decoding algorithm. This thesis addresses several issues of LDPC error floors in the additive white Gaussian noise channel. First, we find the source of several well publicized error floors to be numerical issues within the message-passing decoder. We propose numerical improvements to several decoding formulations which substantially lower error floors. Next, we examine and refine error-floor prediction models. A time-variant linear state-space model is presented and analyzed. Graph theory is applied to analyze the small error-prone structures within the code. While we find our techniques encounter considerable problems in determining the error floors for iterative decoders with unrestricted dynamic range, their predictions are quite accurate when significant range restrictions are present. The final issue of LDPC error floors which we address relates to the minimum distance of quasi-cyclic (QC) LDPC codes. We derive improved minimum distance upper bounds for codes which are punctured and codes which contain a significant number of zeros in their protomatrices. These bound are then applied to a family of protograph-based LDPC codes standardized for use in deep-space communications. In the case of the rate-1/2 code, our upper bounds demonstrate that the previously promulgated ensemble lower bounds do not apply to QC constructions at block lengths beyond 4400 bits. The last part of this dissertation is a fairly separate piece of work on bounding the spectral radius of a large class of nonnegative matrices. We apply these bounds to digraphs and derive several associated equality conditions.</

•Sep 11, 2013•0 citations

Low-delay low-complexity error-correcting codes on sparse graphs

Hu, Xiao-Yu

This dissertation presents a systematic exposition on finite-block-length coding theory and practice. We begin with the task of identifying the maximum achievable rates over noisy, finite-block-length constrained channels, referred to as (ε, n)-capacity Cεn, with ε denoting target block-error probability and n the block length. We characterize how the optimum codes look like over finite-block-length constrained channels. Constructing good, short-block-length error-correcting codes defined on sparse graphs is the focus of the thesis. We propose a new, general method for constructing Tanner graphs having a large girth by progressively establishing edges or connections between symbol and check nodes in an edge-by-edge manner, called progressive edge-growth (PEG) construction. Lower bounds on the girth of PEG Tanner graphs and on the minimum distance of the resulting low-density parity-check (LDPC) codes are derived in terms of parameters of the graphs. The PEG construction attains essentially the same girth as Gallager's explicit construction for regular graphs, both of which meet or exceed an extension of the Erdös-Sachs bound. The PEG construction proves to be powerful for generating good, short-block-length binary LDPC codes. Furthermore, we show that the binary interpretation of GF(2b) codes on the cycle Tanner graph TG(2, dc), if b grows sufficiently large, can be used over the binary-input additive white Gaussian noise (AWGN) channel as "good code for optimum decoding" and "good code for iterative decoding". Codes on sparse graphs are often decoded iteratively by a sum-product algorithm (SPA) with low complexity. We investigate efficient digital implementations of the SPA for decoding binary LDPC codes from both the architectural and algorithmic point of view, and describe new reduced-complexity derivatives thereof. The unified treatment of decoding techniques for LDPC codes provides flexibility in selecting the appropriate design point in high-speed applications from a performance, latency, and computational complexity perspective.

•Jan 1, 2003•26 citations

A graphical model and search algorithm based Quasi-Cyclic Low-Density Parity-Check codes scheme

Jun Lin, Peng Jia Shi, Yan Ge +2 more

A constant challenge in Quasi-Cyclic Low-Density Parity-Check (QC-LDP-C) codes lies on flexible code lengths and rates, conditioned by good error performance. This paper presents an optimal construction method of QC-LDPC codes on the basis of graphical model and search algorithm. Utilizing the proposed scheme, we can construct adaptable QC-LDPC codes whose girths are no less than 12, and column weights are 3. Comparing with any other QC-LDPC code construction approach, this method is much more flexible in block length and block rate. Furthermore, when construction parameters are selected, regular QC-LDPC codes can be constructed easily. Simulation results indicate that LDPC codes proposed in the method perform similarly to the classic Progressive Edge-Growth (PEG) based LDPC codes but outweigh in convenience of implementation and applications. © 2013 ICIC International.

•Jan 1, 2013•0 citations
Two broad classes of graphical modeling problems for codes can be identified in the literature: constructive and extractive problems. The former class of problems concern the construction of a graphical model in order to define a new code. The latter class of problems concern the extraction of a graphical model for a (fixed) given code. The design of a new low-density parity-check code for some given criteria (e.g., target block length and code rate) is an example of a constructive problem. The determination of a graphical model for a classical linear block code that implies a decoding algorithm with desired performance and complexity characteristics is an example of an extractive problem. This work focuses on extractive graphical model problems and aims to lay out some of the foundations of the theory of such problems for linear codes. The primary focus of this work is a study of the space of all graphical models for a (fixed) given code. The tradeoff between cyclic topology and complexity in this space is characterized via the introduction of a new bound: the forest-inducing cut-set bound (FI-CSB). The proposed bound provides a more precise characterization of this tradeoff than that which can be obtained using existing tools (e.g., the CSB) and can be viewed as a generalization of the square-root bound for tail-biting trellises to graphical models with arbitrary cyclic topologies. Searching the space of graphical models for a given code is then enabled by introducing a set of basic graphical model transformation operations that are shown to span this space. Finally, heuristics for extracting novel graphical models for linear block codes using these transformations are investigated.
Since the discovery of turbo codes in the 1990s, much of the work concerning graphical models for codes has focused on constructing models in order to define a new code. This work focuses on the theoretical foundations of the inverse problem to code construction -extracting a graphical model for a given (fixed) code. Specifically, limits on the space of graphical models for a given code are examined. A number of results concerning these limits (e.g., the cut-set bound, the square-root bound) are first reviewed. Following this review, recent results concerning these limits are presented. It is first shown that the Tanner graphs of many classical block codes necessarily contain many short cycles. It is then shown that cycle-free binary graphical models do not support good codes thus generalizing Trachtenberg's work concerning the existence of cycle-free Tanner graphs. Finally, and most significantly, the tree-inducing cut-set bound (TI-CSB) is derived and discussed. The TI-CSB provides a characterization of the tradeoff between complexity and density in the family of graphical models for a given code. For example, the TI-CSB can be used to show that anrth-root complexity reduction (with respect to the least-complex cycle-free model) requires the introduction of at leastr(r- 1)/2 cycles thus generalizing the square-root bound to graphical models with arbitrary cyclic topologies.
Since the invention of turbo codes, there has been an explosion of interest in iterative decoding and graphical representation of codes. This thesis examines the iterative decoding of codes defined on graphs with cycles, which appears to be an efficient means of achieving the Shannon limit. Much of this analysis is on the iterative min-sum decoding of tail-biting codes and cycle codes. We have identified the pseudocodeword as the cause of the suboptimal performance of the iterative decoder, and we have obtained a union bound for the performance of the iterative decoder on both AWGN and BSC channels. Using the union bound argument, for cycle codes, we have shown that the performance of the iterative decoder is asymptotically as good as that of the ML decoder. As for tail-biting codes, the same thing is true if the lowest weight pseudocodeword is at least the minimum weight of the code. Unfortunately, the analysis of tail-biting codes and cycle codes does not extend to turbo codes and low density parity check codes in general. Our next approach is to determine the average behavior of message passing algorithms by studying the evolution of their "message" densities. For the class of "repeat and accumulate" serially concatenated turbo-like codes, we have devised an algorithm for determining their "threshold" values. When the signal-to-noise ratio is larger than the threshold value, the error probabilities of message passing algorithms approach zero, whereas if the signal-to-noise ratio is less than the threshold value, the error probability stays bounded away from zero. Some message passing algorithms and graphical representation of codes are efficient means of devising ML or MAP decoding algorithms. We have proposed a junction tree representation for linear block codes, and we have shown that the minimum junction tree can be less complex than the minimal trellis.
Since their rediscovery in the late 1990s, low-density parity-check (LDPC) codes have rapidly become one the most important classes of error correcting codes. LDPC codes have a graphical description and are generally decoded iteratively. The graph of an iteratively decoded code's error rate performance versus the channel quality is typically divided into two regions. The error floor region appears at higher channel quality and is characterized by a more gradual decrease in error rate as channel quality improves. For iterative decoders the error floor is apparently determined by small structures within the code that are specific to the selected graphical description of the code and subtle details of the decoding algorithm. This thesis addresses several issues of LDPC error floors in the additive white Gaussian noise channel. First, we find the source of several well publicized error floors to be numerical issues within the message-passing decoder. We propose numerical improvements to several decoding formulations which substantially lower error floors. Next, we examine and refine error-floor prediction models. A time-variant linear state-space model is presented and analyzed. Graph theory is applied to analyze the small error-prone structures within the code. While we find our techniques encounter considerable problems in determining the error floors for iterative decoders with unrestricted dynamic range, their predictions are quite accurate when significant range restrictions are present. The final issue of LDPC error floors which we address relates to the minimum distance of quasi-cyclic (QC) LDPC codes. We derive improved minimum distance upper bounds for codes which are punctured and codes which contain a significant number of zeros in their protomatrices. These bound are then applied to a family of protograph-based LDPC codes standardized for use in deep-space communications. In the case of the rate-1/2 code, our upper bounds demonstrate that the previously promulgated ensemble lower bounds do not apply to QC constructions at block lengths beyond 4400 bits. The last part of this dissertation is a fairly separate piece of work on bounding the spectral radius of a large class of nonnegative matrices. We apply these bounds to digraphs and derive several associated equality conditions.</
Since their rediscovery in the late 1990s, low-density parity-check (LDPC) codes have rapidly become one the most important classes of error correcting codes. LDPC codes have a graphical description and are generally decoded iteratively. The graph of an iteratively decoded code's error rate performance versus the channel quality is typically divided into two regions. The error floor region appears at higher channel quality and is characterized by a more gradual decrease in error rate as channel quality improves. For iterative decoders the error floor is apparently determined by small structures within the code that are specific to the selected graphical description of the code and subtle details of the decoding algorithm. This thesis addresses several issues of LDPC error floors in the additive white Gaussian noise channel. First, we find the source of several well publicized error floors to be numerical issues within the message-passing decoder. We propose numerical improvements to several decoding formulations which substantially lower error floors. Next, we examine and refine error-floor prediction models. A time-variant linear state-space model is presented and analyzed. Graph theory is applied to analyze the small error-prone structures within the code. While we find our techniques encounter considerable problems in determining the error floors for iterative decoders with unrestricted dynamic range, their predictions are quite accurate when significant range restrictions are present. The final issue of LDPC error floors which we address relates to the minimum distance of quasi-cyclic (QC) LDPC codes. We derive improved minimum distance upper bounds for codes which are punctured and codes which contain a significant number of zeros in their protomatrices. These bound are then applied to a family of protograph-based LDPC codes standardized for use in deep-space communications. In the case of the rate-1/2 code, our upper bounds demonstrate that the previously promulgated ensemble lower bounds do not apply to QC constructions at block lengths beyond 4400 bits. The last part of this dissertation is a fairly separate piece of work on bounding the spectral radius of a large class of nonnegative matrices. We apply these bounds to digraphs and derive several associated equality conditions.</
This dissertation presents a systematic exposition on finite-block-length coding theory and practice. We begin with the task of identifying the maximum achievable rates over noisy, finite-block-length constrained channels, referred to as (ε, n)-capacity Cεn, with ε denoting target block-error probability and n the block length. We characterize how the optimum codes look like over finite-block-length constrained channels. Constructing good, short-block-length error-correcting codes defined on sparse graphs is the focus of the thesis. We propose a new, general method for constructing Tanner graphs having a large girth by progressively establishing edges or connections between symbol and check nodes in an edge-by-edge manner, called progressive edge-growth (PEG) construction. Lower bounds on the girth of PEG Tanner graphs and on the minimum distance of the resulting low-density parity-check (LDPC) codes are derived in terms of parameters of the graphs. The PEG construction attains essentially the same girth as Gallager's explicit construction for regular graphs, both of which meet or exceed an extension of the Erdös-Sachs bound. The PEG construction proves to be powerful for generating good, short-block-length binary LDPC codes. Furthermore, we show that the binary interpretation of GF(2b) codes on the cycle Tanner graph TG(2, dc), if b grows sufficiently large, can be used over the binary-input additive white Gaussian noise (AWGN) channel as "good code for optimum decoding" and "good code for iterative decoding". Codes on sparse graphs are often decoded iteratively by a sum-product algorithm (SPA) with low complexity. We investigate efficient digital implementations of the SPA for decoding binary LDPC codes from both the architectural and algorithmic point of view, and describe new reduced-complexity derivatives thereof. The unified treatment of decoding techniques for LDPC codes provides flexibility in selecting the appropriate design point in high-speed applications from a performance, latency, and computational complexity perspective.
A constant challenge in Quasi-Cyclic Low-Density Parity-Check (QC-LDP-C) codes lies on flexible code lengths and rates, conditioned by good error performance. This paper presents an optimal construction method of QC-LDPC codes on the basis of graphical model and search algorithm. Utilizing the proposed scheme, we can construct adaptable QC-LDPC codes whose girths are no less than 12, and column weights are 3. Comparing with any other QC-LDPC code construction approach, this method is much more flexible in block length and block rate. Furthermore, when construction parameters are selected, regular QC-LDPC codes can be constructed easily. Simulation results indicate that LDPC codes proposed in the method perform similarly to the classic Progressive Edge-Growth (PEG) based LDPC codes but outweigh in convenience of implementation and applications. © 2013 ICIC International.