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/0607064

How to Find Good Finite-Length Codes: From Art Towards Science

Amraoui, Abdelaziz, Andrea Montanari A, Rudiger L. Urbanke

Published Jul 13, 2006• 11 citations
arXivHTMLPDF

Abstract

We explain how to optimize finite-length LDPC codes for transmission over the binary erasure channel. Our approach relies on an analytic approximation of the erasure probability. This is in turn based on a finite-length scaling result to model large scale erasures and a union bound involving minimal stopping sets to take into account small error events. We show that the performances of optimized ensembles as observed in simulations are well described by our approximation. Although we only address the case of transmission over the binary erasure channel, our method should be applicable to a more general setting.

DOI
10.48550/arxiv.cs/0607064

Related papers

How to find good finite‐length codes: from art towards science

Abdelaziz Amraoui, Andrea Montanari A, Rudiger L. Urbanke

Abstract We explain how to optimise finite‐length LDPC codes for transmission over the binary erasure channel. Our approach relies on an analytic approximation of the erasure probability. This is in turn based on a finite‐length scaling result to model large scale erasures and a union bound involving minimal stopping sets to take into account small error events. We show that the performance of optimised ensembles as observed in simulations is well described by our approximation. Although we only address the case of transmission over the binary erasure channel, our method should be applicable to a more general setting. Copyright © 2007 John Wiley & Sons, Ltd.

European Transactions on Telecommunications•Apr 23, 2007•60 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, 2005•19 citations

A Scaling Law to Predict the Finite-Length Performance of Spatially-Coupled LDPC Codes

Pablo M. Olmos, Rudiger L. Urbanke

Spatially-coupled low-density parity-check (SC-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 code 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 SC-LDPC codes under practical constraints.

arXiv:1404.5719•IEEE Transactions on Information Theory•Apr 14, 2015•58 citations

Finite-length and asymptotic analysis and design of LDPC codes for binary erasure and fading channels.

Kaiann Fu

Low-density parity-check (LDPC) codes in conjunction with iterative decoding based on message-passing algorithms have been shown to achieve excellent performance over a variety of communication channels. In this dissertation, we investigate LDPC codes under two scenarios which present different challenges for providing robust communications. First, LDPC codes are analyzed and designed for time-selective, frequency-nonselective complex-fading channels where both the amplitude and the phase of the transmitted signal are altered by the channel. To combat the fading, we use a pilot symbol-assisted scheme where known pilot symbols are added to the LDPC code and used to help estimate the channel at the receiver. Using asymptotic, infinite-length analysis, we investigate several iterative, message-passing, joint-estimation-and-decoding strategies; optimal energy distribution between pilot and data symbols; and LDPC code design. Several interesting results are obtained regarding unification of analysis and code design. Next, we address the issue of achieving very low error rates with practical, finite-length LDPC codes for binary erasure channels. Finite-length LDPC codes suffer from error floors which limit the achievable error rate, and this error-floor performance is determined by stopping sets. Asymptotic analysis of weight and stopping-set enumerators, for codewords and stopping sets which grow linearly with codelength, has aided in designing codes with lower error floors but does not reflect the behavior of sublinearly-sized stopping sets, which can dominate the iterative-decoding, error-floor performance. Thus, we provide a perspective on protograph-based and standard LDPC ensemble enumerators, based on analysis of stopping sets with sublinear growth, which brings new insight into sublinear stopping-set behavior, advantages of protograph structure, and effects of precoding. We show for stopping sets that grow at most logarithmically with codelength, the enumerators follow a polynomial relationship with codelength, unlike the exponential relationship for linearly-growing stopping sets, and this polynomial relationship can be approximately captured by a single parameter. Further, we begin to address the question, Given finite stopping-set sizes and finite codelengths, do the stopping sets follow the behavior predicted by linear or sublinear analysis?

•Jan 1, 2007•1 citation

Upper Bounding the Performance of Arbitrary Finite LDPC Codes on Binary Erasure Channels

Chih-chun Wang, Sanjeev R. Kulkarni, H. Vincent Poor

Assuming iterative decoding for binary erasure channels (BECs), a novel tree-based technique for upper bounding the bit error rates (BERs) of arbitrary, finite low-density parity-check (LDPC) codes is provided and the resulting bound can be evaluated for all operating erasure probabilities, including both the waterfall and the error floor regions. This upper bound can also be viewed as a narrowing search of stopping sets, which is an approach different from the stopping set enumeration used for lower bounding the error floor. When combined with optimal leaf-finding modules, this upper bound is guaranteed to be tight in terms of the asymptotic order. The Boolean framework proposed herein further admits a composite search for even tighter results. For comparison, a refinement of the algorithm is capable of exhausting all stopping sets of size les 13 for irregular LDPC codes of length n ap 500, which requires (13500) ap 1.67 times 1025trials if a brute force approach is taken. These experiments indicate that this upper bound can be used both as an analytical tool and as a deterministic worst-performance (error floor) guarantee, the latter of which is crucial to optimizing LDPC codes for extremely low BER applications, e.g., optical/satellite communications

arXiv:cs/0605086•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•9 citations

Asymptotic and finite-length analysis of low-density parity-check codes

Di, Changyan

This thesis addresses the topic of Low-Density Parity-Check (LDPC) code analysis, both asymptotically and for finite block lengths. Since in general it is a difficult problem to analyze individual code instances, ensemble averages are studied by following Gallager's original idea and results of Luby et al. Often, one can relate the insights gained by studying ensemble averages to statements regarding individual codes by proving that most elements in the ensemble behave "close" to the average. One important such average is the average weight distribution, another is the average pseudo-codeword distribution, where pseudo-codewords play the same role under iterative decoding as codewords do for maximum likelihood decoding. One of the main contributions of this thesis is the calculation of such averages for fully irregular LDPC code ensembles. Much of classical coding theory is aimed at the construction of codes with large minimum distance. This is so since away from capacity accurate bounds on the performance of a code can be given in terms of its minimum distance (or more generally, in terms of its weight distribution). Therefore, it is of interest to investigate what role the minimum distance plays for iteratively decoded LDPC code ensembles. In particular, sequences of capacity-achieving LDPC code ensembles of increasing length when transmission takes place over the Binary Erasure Channel (BEC) are investigated. It is shown that, under certain technical conditions, the minimum distance of such ensembles grows sub-linearly in the block length, a result which is somewhat surprising from a classical point of view. Specific attention is also given to the design of LDPC code ensembles, where an inherent trade-off is observed between achieving large minimum distance (which is relevant for the so called error-floor regime) and achieving a large threshold (which in the limit of long block lengths determines the worst channel on which transmission can be accomplished reliably). Most results on iterative coding systems to date address their asymptotic performance, i.e., their performance when the block length tends to infinity. For small and moderate block lengths the behavior of a code can deviate significantly from its asymptotic limit. It is therefore of high practical value to be able to analyze the finite-length performance of LDPC code ensembles. In this thesis, an exact such analysis is presented for iteratively decoded LDPC code ensembles over the BEC. In particular, expressions for the exact average bit and block erasure probabilities are computed by solving a set of recursions. Such an analysis is the starting point for a finite-length optimization, a topic which is slated for future work. The methods used in this thesis include a combinatorial approach (familiar to the coding society) as well as the powerful techniques developed in the statistical physics community, for example, the replica method or the mean-field approximation. Although the statistical physics techniques are ideally suited for the analysis of iterative coding systems, they are to date only accessible to a relatively small community. Therefore, an overview of these techniques is first presented using a language familiar to the coding theory community. Next, in order to highlight the differences and common points between the combinatorial and the statistical physics approaches, both techniques are applied to the weight distribution problem. It turns out that for regular ensembles, both methods yield the same result, while for irregular ensembles, they do differ in general.

•Jan 1, 2004•13 citations
We explain how to optimize finite-length LDPC codes for transmission over the binary erasure channel. Our approach relies on an analytic approximation of the erasure probability. This is in turn based on a finite-length scaling result to model large scale erasures and a union bound involving minimal stopping sets to take into account small error events. We show that the performances of optimized ensembles as observed in simulations are well described by our approximation. Although we only address the case of transmission over the binary erasure channel, our method should be applicable to a more general setting.
Abstract We explain how to optimise finite‐length LDPC codes for transmission over the binary erasure channel. Our approach relies on an analytic approximation of the erasure probability. This is in turn based on a finite‐length scaling result to model large scale erasures and a union bound involving minimal stopping sets to take into account small error events. We show that the performance of optimised ensembles as observed in simulations is well described by our approximation. Although we only address the case of transmission over the binary erasure channel, our method should be applicable to a more general setting. Copyright © 2007 John Wiley & Sons, Ltd.
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.
Spatially-coupled low-density parity-check (SC-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 code 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 SC-LDPC codes under practical constraints.
Low-density parity-check (LDPC) codes in conjunction with iterative decoding based on message-passing algorithms have been shown to achieve excellent performance over a variety of communication channels. In this dissertation, we investigate LDPC codes under two scenarios which present different challenges for providing robust communications. First, LDPC codes are analyzed and designed for time-selective, frequency-nonselective complex-fading channels where both the amplitude and the phase of the transmitted signal are altered by the channel. To combat the fading, we use a pilot symbol-assisted scheme where known pilot symbols are added to the LDPC code and used to help estimate the channel at the receiver. Using asymptotic, infinite-length analysis, we investigate several iterative, message-passing, joint-estimation-and-decoding strategies; optimal energy distribution between pilot and data symbols; and LDPC code design. Several interesting results are obtained regarding unification of analysis and code design. Next, we address the issue of achieving very low error rates with practical, finite-length LDPC codes for binary erasure channels. Finite-length LDPC codes suffer from error floors which limit the achievable error rate, and this error-floor performance is determined by stopping sets. Asymptotic analysis of weight and stopping-set enumerators, for codewords and stopping sets which grow linearly with codelength, has aided in designing codes with lower error floors but does not reflect the behavior of sublinearly-sized stopping sets, which can dominate the iterative-decoding, error-floor performance. Thus, we provide a perspective on protograph-based and standard LDPC ensemble enumerators, based on analysis of stopping sets with sublinear growth, which brings new insight into sublinear stopping-set behavior, advantages of protograph structure, and effects of precoding. We show for stopping sets that grow at most logarithmically with codelength, the enumerators follow a polynomial relationship with codelength, unlike the exponential relationship for linearly-growing stopping sets, and this polynomial relationship can be approximately captured by a single parameter. Further, we begin to address the question, Given finite stopping-set sizes and finite codelengths, do the stopping sets follow the behavior predicted by linear or sublinear analysis?
Assuming iterative decoding for binary erasure channels (BECs), a novel tree-based technique for upper bounding the bit error rates (BERs) of arbitrary, finite low-density parity-check (LDPC) codes is provided and the resulting bound can be evaluated for all operating erasure probabilities, including both the waterfall and the error floor regions. This upper bound can also be viewed as a narrowing search of stopping sets, which is an approach different from the stopping set enumeration used for lower bounding the error floor. When combined with optimal leaf-finding modules, this upper bound is guaranteed to be tight in terms of the asymptotic order. The Boolean framework proposed herein further admits a composite search for even tighter results. For comparison, a refinement of the algorithm is capable of exhausting all stopping sets of size les 13 for irregular LDPC codes of length n ap 500, which requires (13500) ap 1.67 times 1025trials if a brute force approach is taken. These experiments indicate that this upper bound can be used both as an analytical tool and as a deterministic worst-performance (error floor) guarantee, the latter of which is crucial to optimizing LDPC codes for extremely low BER applications, e.g., optical/satellite communications
This thesis addresses the topic of Low-Density Parity-Check (LDPC) code analysis, both asymptotically and for finite block lengths. Since in general it is a difficult problem to analyze individual code instances, ensemble averages are studied by following Gallager's original idea and results of Luby et al. Often, one can relate the insights gained by studying ensemble averages to statements regarding individual codes by proving that most elements in the ensemble behave "close" to the average. One important such average is the average weight distribution, another is the average pseudo-codeword distribution, where pseudo-codewords play the same role under iterative decoding as codewords do for maximum likelihood decoding. One of the main contributions of this thesis is the calculation of such averages for fully irregular LDPC code ensembles. Much of classical coding theory is aimed at the construction of codes with large minimum distance. This is so since away from capacity accurate bounds on the performance of a code can be given in terms of its minimum distance (or more generally, in terms of its weight distribution). Therefore, it is of interest to investigate what role the minimum distance plays for iteratively decoded LDPC code ensembles. In particular, sequences of capacity-achieving LDPC code ensembles of increasing length when transmission takes place over the Binary Erasure Channel (BEC) are investigated. It is shown that, under certain technical conditions, the minimum distance of such ensembles grows sub-linearly in the block length, a result which is somewhat surprising from a classical point of view. Specific attention is also given to the design of LDPC code ensembles, where an inherent trade-off is observed between achieving large minimum distance (which is relevant for the so called error-floor regime) and achieving a large threshold (which in the limit of long block lengths determines the worst channel on which transmission can be accomplished reliably). Most results on iterative coding systems to date address their asymptotic performance, i.e., their performance when the block length tends to infinity. For small and moderate block lengths the behavior of a code can deviate significantly from its asymptotic limit. It is therefore of high practical value to be able to analyze the finite-length performance of LDPC code ensembles. In this thesis, an exact such analysis is presented for iteratively decoded LDPC code ensembles over the BEC. In particular, expressions for the exact average bit and block erasure probabilities are computed by solving a set of recursions. Such an analysis is the starting point for a finite-length optimization, a topic which is slated for future work. The methods used in this thesis include a combinatorial approach (familiar to the coding society) as well as the powerful techniques developed in the statistical physics community, for example, the replica method or the mean-field approximation. Although the statistical physics techniques are ideally suited for the analysis of iterative coding systems, they are to date only accessible to a relatively small community. Therefore, an overview of these techniques is first presented using a language familiar to the coding theory community. Next, in order to highlight the differences and common points between the combinatorial and the statistical physics approaches, both techniques are applied to the weight distribution problem. It turns out that for regular ensembles, both methods yield the same result, while for irregular ensembles, they do differ in general.