A highly-performing code called turbo-Gallager code (TG code) is introduced, which outperforms the normal Gallager code of same rate. The decoding of the TG code is based on the construction of the contradiction matrix and is capable of correcting errors left over by normal Gallager code decoders.
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
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.
The theoretical performance of binary codes for the additive white Gaussian noise (AWGN) channel is discussed. In particular, Gallager’s coding theorem for binary codes is treated extensively. By assuming a binomial weight distribution for linear codes, it is shown that the decoder error probability performance of some of the best, known linear, binary codes is the same as the average performance of the ensemble of all randomly chosen, binary nonlinear codes having the same length and dimension. Assuming a binomial weight distribution, an upper bound is determined for the erasure performance of any code, and it is shown that this can be translated into an upper bound for code performance in the AWGN channel. Finally, theoretical bounds on the construction of error-correction codes are discussed. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
We construct new families of error-correcting codes based on Gallager's (1973) low-density parity-check codes. We improve on Gallager's results by introducing irregular parity-check matrices and a new rigorous analysis of hard-decision decoding of these codes. We also provide efficient methods for finding good irregular structures for such decoding algorithms. Our rigorous analysis based on martingales, our methodology for constructing good irregular codes, and the demonstration that irregular structure improves performance constitute key points of our contribution. We also consider irregular codes under belief propagation. We report the results of experiments testing the efficacy of irregular codes on both binary-symmetric and Gaussian channels. For example, using belief propagation, for rate 1/4 codes on 16000 bits over a binary-symmetric channel, previous low-density parity-check codes can correct up to approximately 16% errors, while our codes correct over 17%. In some cases our results come very close to reported results for turbo codes, suggesting that variations of irregular low density parity-check codes may be able to match or beat turbo code performance.
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