Allerton Conference on Communication, Control, and Computing

Finite-Length Scaling For Gallager A

Jeremie Ezri, Andrea Montanari A, Rudiger L. Urbanke

Published Jan 1, 2006• 3 citations

Abstract

We consider LDPC codes, transmission over the binary symmetric channel (BSC), and decoding using Gallager's algorithm A. For those ensembles whose threshold is determined by the behavior of the algorithm at the beginning of the decoding process we derive a scaling law. This scaling law has the same form as the scaling law which was established for the the case of transmission over the binary erasure channel (BEC). We show how the scaling parameters can be computed and point out some interesting open challenges.

Related papers

A Generalization of the Finite-Length Scaling Approach Beyond the BEC

Jeremie Ezri, Andrea Montanari A, Rudiger L. Urbanke

We want to extend the approximation of the error probability via a scaling approach from the BEC to general binary-input memoryless output-symmetric (BMS) channels. In particular, we consider such scaling laws for regular LDPC ensembles and message-passing (MP) decoders with a finite number of messages. We first show how to re-derive the scaling law for transmission over the BEC using an ";EXIT-like"; curve instead of the density evolution curve of the peeling decoder. The advantage of the new derivation is that the new expression of the scaling parameter a only contains quantities that can be meaningfully interpreted also for general message-passing algorithms. In particular, this expression only depends on the curvature of the EXIT-like curve as well as the variance of the messages, both taken at the critical channel parameter. We discuss how to compute these quantities for general MP algorithms and we evaluate the expressions for the specific cases of the Gallager algorithm A as well as the Decoder with Erasures and compare the resulting predictions on the error probability with simulation results.

IEEE International Symposium on Information Theory (ISIT)Jun 1, 200718 citations

A closed-form scaling law for convolutional LDPC codes over the BEC

Pablo M. Olmos, Rudiger L. Urbanke

We propose a scaling law for the error probability of convolutional LDPC ensembles when transmission takes place over the binary erasure channel. We discuss how the parameters of the scaling law are connected to fundamental quantities appearing in the asymptotic analysis of these ensembles and we verify that the predictions of the scaling law fit well with data derived from simulations over a wide range of parameters.

IEEE Information Theory Workshop (ITW)Sep 1, 20139 citations

Analyzing the finite-length performance of generalized LDPC codes

Pablo M. Olmos, David G. M. Mitchell, Daniel J. Costello

In this paper, we analyze the performance of finite-length generalized LDPC (GLDPC) block codes constructed from protographs when transmission takes place over the binary erasure channel (BEC). A generalized peeling decoder is proposed and we derive a system of differential equations that gives the expected evolution of the graph degree distribution during decoding. We then show that the finite-length performance of a GLDPC code can be estimated by means of a simple scaling law, where a single scaling parameter represents the finite-length properties of the code. We also show that, as we consider stronger component codes, both the asymptotic threshold and the finite-length scaling parameter are improved.

IEEE International Symposium on Information Theory (ISIT)Jun 1, 201510 citations

Finite-length scaling of irregular LDPC code ensembles

Ala Eddine Kaddour Amraoui, Rudiger L. Urbanke, Andrea Montanari A

We investigate the finite-length scaling methodology for irregular LDPC code ensembles when transmission takes place over the binary erasure channel (BEC). We first show how the necessary computations, namely the covariance evolution and the computation of the finite-length shift, can be accomplished in the irregular case. We then investigate how the obtained approximation can be used to predict the performance of irregular code ensembles and to optimize the degree distributions for finite-length codes.

IEEE Information Theory Workshop (ITW)Jan 1, 200522 citations

Finite-length scaling of non-binary (c, d) LDPC codes for the BEC

Iryna Andriyanova, Kenta Kasai

This paper provides a performance analysis of the regular (c, d) LDPC code ensemble of codelength n with parity-check matrices defined over the general linear group GL(2m). The transmission is assumed to take place over the binary erasure channel with erasure probability ε. In this work, the scaling approximation of the block erasure rate is generalized to the non-binary case, and the scaling parameter α of the approximation is derived. The proposed estimation is then compared with numerical results, showing that it predicts well the slope of the block erasure rate vs. channel erasure probability.

IEEE International Symposium on Information Theory (ISIT)Jun 1, 20104 citations

A scaling law to predict the finite-length performance of spatially-coupled LDPC codes

Pablo M. Olmos

Spatially-coupled LDPC codes are known to have excellent asymptotic properties. Much less is known regarding their finite-length performance. We propose a scaling law to predict the error probability of finite-length spatially-coupled ensembles when transmission takes place over the binary erasure channel. We discuss how the parameters of the scaling law are connected to fundamental quantities appearing in the asymptotic analysis of these ensembles and we verify that the predictions of the scaling law fit well to the data derived from simulations over a wide range of parameters. The ultimate goal of this line of research is to develop analytic tools for the design of spatially-coupled LDPC codes under practical constraints.

Jan 1, 201446 citations