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

Gallager Codes – Recent Results

David Mackay

Published Jan 1, 2006• 10 citations
OpenAlex

Abstract

In 1948, Claude Shannon posed and solved one of the fundamental problems of information theory. The question was whether it is possible to communicate reliably over noisy channels, and, if so, at what rate. He defined a theoretical limit, now known as the Shannon limit, up to which communication is possible, and beyond which communication is not possible. Since 1948, coding theorists have attempted to design error-correcting codes capable of getting close to the Shannon limit. In the last decade remarkable progress has been made using codes that are defined in terms of sparse random graphs, and which are decoded by a simple probability-based message-passing algorithm. This paper reviews low-density parity-check codes (Gallager codes), repeat-accumulate codes, and turbo codes, emphasising recent advances. Some previously unpublished results are then presented, describing (a) experiments on Gallager codes with small blocklengths; (b) a stopping rule for decoding of repeat-accumulate codes, which saves computer time and allows block decoding errors to be detected and flagged; and (c) the empirical power-laws obeyed by decoding times of sparse graph codes. 1

Related papers

Turbo-Gallager Codes: The Emergence of an Intelligent Coding Scheme

PC Catherine, K. S. Soyjaudah

In 1948, C. Shannon developed fundamental limits on the efficiency of communication over noisy channels. However it is only in 1993 (about half a century later) that Berrou, Glavieux and Thitimajshima developed turbo codes and demonstrated performance close to that limit. Overnight, much of the  algebraic coding techniques of the pre-turbo era were rendered obsolete. Turbo codes employ iterative algorithms and focus on exchange of soft (or probabilistic) information. Shortly after, it was recognised that another class of codes developed by Gallager in 1963 shared all the essential features of turbo codes, including sparse graph-based codes and iterative message-passing decoders. Today, both turbo codes and low-density parity-check codes are largely superior to other code families and are being used in an increasing number of modern communication systems including 3G standards, satellite and deep space communications. However, the two codes have certain distinctive characteristics that differentiate them. This work proposes a blend of the two technologies, yielding a code that we nicknamed Turbo-Gallager or TG Code. The code has additional “intelligence” compared to its parents. It detects and corrects the so-called “undetected errors” and recovers from individual decoder failure by making use of a network of decoders. Keywords : TG codes, message-passing algorithms, low-density parity-check codes, turbo codes, bipartite graphs

University of Mauritius Research Journal•Jan 1, 2007•0 citations

Iterative Decoding of Low-Density Parity Check Codes (A Survey)

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 efficient (both in theory and practice).

arXiv:cs/0610022•Oct 5, 2006•11 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•11 citations

Good error-correcting codes based on very sparse matrices

David Mackay

We report theoretical and empirical properties of Gallager's (1963) low density parity check codes on Gaussian channels. It can be proved that, given an optimal decoder, these codes asymptotically approach the Shannon limit. With a practical 'belief propagation' decoder, performance substantially better than that of standard convolutional and concatenated codes can be achieved; indeed the performance is almost as close to the Shannon limit as that of turbo codes.

IEEE International Symposium on Information Theory (ISIT)•Nov 22, 2002•175 citations

A Universal Theory of Decoding and Pseudocodewords

Nathan Axvig, Deanna Dreher, Katherine Morrison +3 more

The discovery of turbo codes [5] and the subsequent rediscovery of low-density parity-check (LDPC) codes [9, 18] represent a major milestone in the field of coding theory. These two classes of codes can achieve realistic bit error rates, between 10−5 and 10−12, with signalto- noise ratios that are only slightly above the minimum possible for a given channel and code rate established by Shannon’s original capacity theorems. In this sense, these codes are said to be near-capacity-achieving codes and are sometimes considered to have solved (in the engineering sense, at least) the coding problem for the additive white Gaussian noise (AWGN) channel and its derivative channels. Perhaps the most important commonality between turbo and low-density parity-check codes is that they both utilize iterative message-passing decoding algorithms. For turbo codes, one uses the so-called turbo decoding algorithm, and for LDPC codes, both the sumproduct (SP) and the min-sum (MS) algorithms are used. The success of the various iterative message-passing algorithms is sometimes said to have ushered in a new era of “modern” coding theory in which the design emphasis has shifted from optimizing some code property, such as minimum distance, to optimizing the corresponding decoding structure of the code, such as the degree profile [24, 25], with respect to the behavior of a message-passing decoder. As successful as these codes and decoders have been in terms of application, there are several major questions that must be answered before a complete understanding of them can be achieved. The theoretical research in the area of capacity-achieving codes is focused on two main themes. The first theme is whether different types of capacity-achieving codes have common encoder and structural properties. In [17], it was claimed that turbo codes could be viewed as LDPC codes, but the relationship was not made explicit. More recently, P´erez, his student Jiang, and others [11, 16] developed a construction for the parity-check matrices of arbitrary turbo codes that clearly connects the components of the turbo encoder to the resulting structure of the parity-check matrix. From a more abstract perspective, turbo codes and low-density parity-check codes are examples of codes with long block lengths that exhibit the random structure inherent in Shannon’s original theorems. The second and more active research theme is the determination of the behavior of iterative message-passing decoding and the relationships between the various decoding algorithms. The dominant problem in this area is to understand the non-codeword decoder errors that occur in computer simulations of LDPC codes with iterative message-passing decoders. Motivated by empirical observations of the non-codeword outputs of LDPC decoders, the notion of stopping sets was first introduced by Forney, et al. [8] in 2001. Two years later, a formal definition of stopping sets was given by Changyan, et al. [6]. They demonstrated that the bit and block error probabilities of iteratively decoded LDPC codes on the binary erasure channel (BEC) can be determined exactly from the stopping sets of the parity-check matrix. (Here, a stopping set S is a subset of the set of variable nodes such that all neighboring check nodes of S are connected to S at least twice.)

•Jan 1, 2008•2 citations

Good error-correcting codes based on very sparse matrices

David Mackay

We study two families of error-correcting codes defined in terms of very sparse matrices. "MN" (MacKay-Neal (1995)) codes are recently invented, and "Gallager codes" were first investigated in 1962, but appear to have been largely forgotten, in spite of their excellent properties. The decoding of both codes can be tackled with a practical sum-product algorithm. We prove that these codes are "very good", in that sequences of codes exist which, when optimally decoded, achieve information rates up to the Shannon limit. This result holds not only for the binary-symmetric channel but also for any channel with symmetric stationary ergodic noise. We give experimental results for binary-symmetric channels and Gaussian channels demonstrating that practical performance substantially better than that of standard convolutional and concatenated codes can be achieved; indeed, the performance of Gallager codes is almost as close to the Shannon limit as that of turbo codes.

IEEE Transactions on Information Theory•Mar 1, 1999•3,685 citations
In 1948, Claude Shannon posed and solved one of the fundamental problems of information theory. The question was whether it is possible to communicate reliably over noisy channels, and, if so, at what rate. He defined a theoretical limit, now known as the Shannon limit, up to which communication is possible, and beyond which communication is not possible. Since 1948, coding theorists have attempted to design error-correcting codes capable of getting close to the Shannon limit. In the last decade remarkable progress has been made using codes that are defined in terms of sparse random graphs, and which are decoded by a simple probability-based message-passing algorithm. This paper reviews low-density parity-check codes (Gallager codes), repeat-accumulate codes, and turbo codes, emphasising recent advances. Some previously unpublished results are then presented, describing (a) experiments on Gallager codes with small blocklengths; (b) a stopping rule for decoding of repeat-accumulate codes, which saves computer time and allows block decoding errors to be detected and flagged; and (c) the empirical power-laws obeyed by decoding times of sparse graph codes. 1
In 1948, C. Shannon developed fundamental limits on the efficiency of communication over noisy channels. However it is only in 1993 (about half a century later) that Berrou, Glavieux and Thitimajshima developed turbo codes and demonstrated performance close to that limit. Overnight, much of the  algebraic coding techniques of the pre-turbo era were rendered obsolete. Turbo codes employ iterative algorithms and focus on exchange of soft (or probabilistic) information. Shortly after, it was recognised that another class of codes developed by Gallager in 1963 shared all the essential features of turbo codes, including sparse graph-based codes and iterative message-passing decoders. Today, both turbo codes and low-density parity-check codes are largely superior to other code families and are being used in an increasing number of modern communication systems including 3G standards, satellite and deep space communications. However, the two codes have certain distinctive characteristics that differentiate them. This work proposes a blend of the two technologies, yielding a code that we nicknamed Turbo-Gallager or TG Code. The code has additional “intelligence” compared to its parents. It detects and corrects the so-called “undetected errors” and recovers from individual decoder failure by making use of a network of decoders. Keywords : TG codes, message-passing algorithms, low-density parity-check codes, turbo codes, bipartite graphs
The discovery of turbo codes [5] and the subsequent rediscovery of low-density parity-check (LDPC) codes [9, 18] represent a major milestone in the field of coding theory. These two classes of codes can achieve realistic bit error rates, between 10−5 and 10−12, with signalto- noise ratios that are only slightly above the minimum possible for a given channel and code rate established by Shannon’s original capacity theorems. In this sense, these codes are said to be near-capacity-achieving codes and are sometimes considered to have solved (in the engineering sense, at least) the coding problem for the additive white Gaussian noise (AWGN) channel and its derivative channels. Perhaps the most important commonality between turbo and low-density parity-check codes is that they both utilize iterative message-passing decoding algorithms. For turbo codes, one uses the so-called turbo decoding algorithm, and for LDPC codes, both the sumproduct (SP) and the min-sum (MS) algorithms are used. The success of the various iterative message-passing algorithms is sometimes said to have ushered in a new era of “modern” coding theory in which the design emphasis has shifted from optimizing some code property, such as minimum distance, to optimizing the corresponding decoding structure of the code, such as the degree profile [24, 25], with respect to the behavior of a message-passing decoder. As successful as these codes and decoders have been in terms of application, there are several major questions that must be answered before a complete understanding of them can be achieved. The theoretical research in the area of capacity-achieving codes is focused on two main themes. The first theme is whether different types of capacity-achieving codes have common encoder and structural properties. In [17], it was claimed that turbo codes could be viewed as LDPC codes, but the relationship was not made explicit. More recently, P´erez, his student Jiang, and others [11, 16] developed a construction for the parity-check matrices of arbitrary turbo codes that clearly connects the components of the turbo encoder to the resulting structure of the parity-check matrix. From a more abstract perspective, turbo codes and low-density parity-check codes are examples of codes with long block lengths that exhibit the random structure inherent in Shannon’s original theorems. The second and more active research theme is the determination of the behavior of iterative message-passing decoding and the relationships between the various decoding algorithms. The dominant problem in this area is to understand the non-codeword decoder errors that occur in computer simulations of LDPC codes with iterative message-passing decoders. Motivated by empirical observations of the non-codeword outputs of LDPC decoders, the notion of stopping sets was first introduced by Forney, et al. [8] in 2001. Two years later, a formal definition of stopping sets was given by Changyan, et al. [6]. They demonstrated that the bit and block error probabilities of iteratively decoded LDPC codes on the binary erasure channel (BEC) can be determined exactly from the stopping sets of the parity-check matrix. (Here, a stopping set S is a subset of the set of variable nodes such that all neighboring check nodes of S are connected to S at least twice.)
We study two families of error-correcting codes defined in terms of very sparse matrices. "MN" (MacKay-Neal (1995)) codes are recently invented, and "Gallager codes" were first investigated in 1962, but appear to have been largely forgotten, in spite of their excellent properties. The decoding of both codes can be tackled with a practical sum-product algorithm. We prove that these codes are "very good", in that sequences of codes exist which, when optimally decoded, achieve information rates up to the Shannon limit. This result holds not only for the binary-symmetric channel but also for any channel with symmetric stationary ergodic noise. We give experimental results for binary-symmetric channels and Gaussian channels demonstrating that practical performance substantially better than that of standard convolutional and concatenated codes can be achieved; indeed, the performance of Gallager codes is almost as close to the Shannon limit as that of turbo codes.