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

IEEE Transactions on Information Theory

Bounds on the Number of Iterations for Turbo-Like Ensembles Over the Binary Erasure Channel

Igal Sason, Gil Wiechman

Published May 19, 2009• 16 citations
Publisher

Abstract

This paper provides simple lower bounds on the number of iterations which is required for successful message-passing decoding of some important families of graph-based code ensembles (including low-density parity-check codes and variations of repeat-accumulate codes). The transmission of the code ensembles is assumed to take place over a binary erasure channel, and the bounds refer to the asymptotic case where we let the block length tend to infinity. The simplicity of the bounds derived in this paper stems from the fact that they are easily evaluated and are expressed in terms of some basic parameters of the ensemble which include the fraction of degree-2 variable nodes, the target bit erasure probability and the gap between the channel capacity and the design rate of the ensemble. This paper demonstrates that the number of iterations which is required for successful message-passing decoding scales at least like the inverse of the gap (in rate) to capacity, provided that the fraction of degree-2 variable nodes of these turbo-like ensembles does not vanish (hence, the number of iterations becomes unbounded as the gap to capacity vanishes).

DOI
10.1109/tit.2009.2018342

Related papers

Bounds on the Number of Iterations for Turbo-Like Ensembles over the Binary Erasure Channe

Igal Sason, Gil Wiechman

This paper provides simple lower bounds on the number of iterations which is required for successful message-passing decoding of some important families of graph-based code ensembles (including low-density parity-check codes and variations of repeat-accumulate codes). The transmission of the code ensembles is assumed to take place over a binary erasure channel, and the bounds refer to the asymptotic case where we let the block length tend to infinity. The simplicity of the bounds derived in this paper stems from the fact that they are easily evaluated and are expressed in terms of some basic parameters of the ensemble which include the fraction of degree-2 variable nodes, the target bit erasure probability and the gap between the channel capacity and the design rate of the ensemble. This paper demonstrates that the number of iterations which is required for successful message-passing decoding scales at least like the inverse of the gap (in rate) to capacity, provided that the fraction of degree-2 variable nodes of these turbo-like ensembles does not vanish (hence, the number of iterations becomes unbounded as the gap to capacity vanishes).

arXiv:0711.1056•Nov 7, 2007•1 citation

Bounds on the convergence speed of iterative message-passing decoders over the binary erasure channel

Igal Sason, Gil Wiechman

Simple lower bounds on the number of iterations, required for successful message-passing decoding of some important families of graph-based code ensembles, are derived. The transmission is assumed to take place over a binary erasure channel, and the bounds refer to the asymptotic case where we let the block length tend to infinity. It is demonstrated that the number of iterations required for successful decoding scales at least like the inverse of the gap (in rate) to capacity, provided that the fraction of degree-2 variable nodes of these turbo-like ensembles does not vanish.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 1, 2008•2 citations

Bounds on the number of iterations for turbo-like code ensembles over the binary erasure channel

Igal Sason, Gil Wiechman

We derive simple lower bounds on the number of iterations which are required to communicate over the binary erasure channel when graph-based code ensembles are used in conjunction with an iterative message-passing decoder. These bounds refer to the asymptotic case where we let the block length tend to infinity, and the bounds apply to general ensembles of low- density parity-check (LDPC) codes, irregular repeat-accumulate (IRA) and accumulate-repeat-accumulate (ARA) codes. It is demonstrated that, under a mild condition, the number of iterations required for successful decoding scales at least like the inverse of the gap (in rate) to capacity.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2008•3 citations

Information-theoretic lower bounds on the bit error probability of codes on graphs

Igal Sason, Rudiger L. Urbanke

We present lower bounds on the bit error probability of binary linear block codes, and on the gap between the channel capacity and the rate of these codes for which reliable communica- tion is achievable. The results are valid for memo- ryless binary-input output-symmetric (MBIOS) chan- nels. The lower bounds provide a quantitative mea- sure for the number of cycles of bipartite graphs which represent good error-correcting codes. The tightness of the lower bounds is especially pronounced for the binary erasure channel (BEC); to this end, we analyze a sequence of ensembles of low-density parity-check (LDPC) codes which closely approach these bounds. I. Introduction If a linear block code can be represented by a cycle-free fac- tor graph which only includes variable nodes and parity-check nodes, then maximum-likelihood soft decision decoding can be performed with low complexity (1). Theorem 5 in (1) indicates that these graphs represent codes with very poor minimum distance. The bounds in (1) only refer to the minimum dis- tance of cycle-free codes, and in this work we derive lower bounds on the bit error probability and the gap to capacity for codes on graphs which are represented by bipartite graphs (with or without cycles). We derive in this work information- theoretic lower bounds on the bit error probability of a binary linear code used over MBIOS channels. The bounds are ex- pressed in terms of the density of an arbitrary parity-check matrix which represents the binary linear code (i.e., the num- ber of ones in the matrix normalized per information bit), and they are valid for codes whose bipartite graphs are with or without cycles. We introduce a quantitative measure for the cycles in a bipartite graph which represents a binary lin- ear code (where the graph only includes variable nodes and parity-check nodes). The bounds provide an interpretation for the tradeofi which exists between the bit error proba- bility and gap to capacity of an arbitrary LDPC code (i.e., its performance limitations), and the density of an arbitrary parity-check matrix which represents the code (where the lat- ter afiects the decoding complexity per information bit and per iteration, under a message-passing iterative decoding al- gorithm). We present in this work quantitative results which indicate that in order to approach the channel capacity with vanishing bit error probability, LDPC codes should not have too sparse parity-check matrices, as otherwise their inherent gap to capacity becomes large. In fact, we show that the density of any parity-check matrix and the fundamental num- ber of cycles of the graph which represents the code should increase at least like log 1 where designates the gap to ca- pacity under iterative message-passing decoding (see (2), (3)). The tightness of the lower bounds which are derived in this work (and whose validity is for any sequence of codes with 1 1.5 2 2.5 3 3.5 4 4.5

IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2003•4 citations

Asymptotic bit error probability of LDPC codes for the binary erasure channel with finite number of iterations

Ryuhei Mori, Kenta Kasai, Tomoharu Shibuya +1 more

We consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) code and belief propagation (BP) decoding. Furthermore, a gap between the bit error probability after finite number of iterations for finite block length n and that for infinite block length is asymptotically α/n, where α denotes a speci..c constant determined by a degree distribution, a number of iterations and erasure probability. Our main result is to derive an ef..cient algorithm for calculating α for regular ensembles.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2008•4 citations

Finite-length analysis of various low-density parity-check ensembles for the binary erasure channel

T. Richrdson, Amin Shokrollahi, Rudiger L. Urbanke

We investigate the average erasure probability of the belief propagation algorithm over the binary erasure channel (BEC) for various finite-length low-density parity-check (LDPC) ensembles. In particular, we give tight upper bounds on the "error floor", i.e., on the contribution to the erasure probability stemming from relatively small deficiencies in the graph. We also define and analyse "expurgated" ensembles and give upper bounds on the error floor of "typical" codes. Finally, we show that typical codes of properly chosen ensembles have an erasure correcting radius which grows linearly in the block length. The presented method provides valuable insight into how finite-length codes should be designed. Although the standard ensemble can achieve capacity on the BEC, the construction of good finite-length codes requires careful control of the structure of the degree two variable nodes. In this paper, we investigate the standard ensemble, the Poisson ensemble, an ensemble in which degree two nodes are added in a cycle, and an ensemble in which different degree two variable nodes have distinct neighboring check nodes.

IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2003•50 citations
This paper provides simple lower bounds on the number of iterations which is required for successful message-passing decoding of some important families of graph-based code ensembles (including low-density parity-check codes and variations of repeat-accumulate codes). The transmission of the code ensembles is assumed to take place over a binary erasure channel, and the bounds refer to the asymptotic case where we let the block length tend to infinity. The simplicity of the bounds derived in this paper stems from the fact that they are easily evaluated and are expressed in terms of some basic parameters of the ensemble which include the fraction of degree-2 variable nodes, the target bit erasure probability and the gap between the channel capacity and the design rate of the ensemble. This paper demonstrates that the number of iterations which is required for successful message-passing decoding scales at least like the inverse of the gap (in rate) to capacity, provided that the fraction of degree-2 variable nodes of these turbo-like ensembles does not vanish (hence, the number of iterations becomes unbounded as the gap to capacity vanishes).
This paper provides simple lower bounds on the number of iterations which is required for successful message-passing decoding of some important families of graph-based code ensembles (including low-density parity-check codes and variations of repeat-accumulate codes). The transmission of the code ensembles is assumed to take place over a binary erasure channel, and the bounds refer to the asymptotic case where we let the block length tend to infinity. The simplicity of the bounds derived in this paper stems from the fact that they are easily evaluated and are expressed in terms of some basic parameters of the ensemble which include the fraction of degree-2 variable nodes, the target bit erasure probability and the gap between the channel capacity and the design rate of the ensemble. This paper demonstrates that the number of iterations which is required for successful message-passing decoding scales at least like the inverse of the gap (in rate) to capacity, provided that the fraction of degree-2 variable nodes of these turbo-like ensembles does not vanish (hence, the number of iterations becomes unbounded as the gap to capacity vanishes).
Simple lower bounds on the number of iterations, required for successful message-passing decoding of some important families of graph-based code ensembles, are derived. The transmission is assumed to take place over a binary erasure channel, and the bounds refer to the asymptotic case where we let the block length tend to infinity. It is demonstrated that the number of iterations required for successful decoding scales at least like the inverse of the gap (in rate) to capacity, provided that the fraction of degree-2 variable nodes of these turbo-like ensembles does not vanish.
We derive simple lower bounds on the number of iterations which are required to communicate over the binary erasure channel when graph-based code ensembles are used in conjunction with an iterative message-passing decoder. These bounds refer to the asymptotic case where we let the block length tend to infinity, and the bounds apply to general ensembles of low- density parity-check (LDPC) codes, irregular repeat-accumulate (IRA) and accumulate-repeat-accumulate (ARA) codes. It is demonstrated that, under a mild condition, the number of iterations required for successful decoding scales at least like the inverse of the gap (in rate) to capacity.
We present lower bounds on the bit error probability of binary linear block codes, and on the gap between the channel capacity and the rate of these codes for which reliable communica- tion is achievable. The results are valid for memo- ryless binary-input output-symmetric (MBIOS) chan- nels. The lower bounds provide a quantitative mea- sure for the number of cycles of bipartite graphs which represent good error-correcting codes. The tightness of the lower bounds is especially pronounced for the binary erasure channel (BEC); to this end, we analyze a sequence of ensembles of low-density parity-check (LDPC) codes which closely approach these bounds. I. Introduction If a linear block code can be represented by a cycle-free fac- tor graph which only includes variable nodes and parity-check nodes, then maximum-likelihood soft decision decoding can be performed with low complexity (1). Theorem 5 in (1) indicates that these graphs represent codes with very poor minimum distance. The bounds in (1) only refer to the minimum dis- tance of cycle-free codes, and in this work we derive lower bounds on the bit error probability and the gap to capacity for codes on graphs which are represented by bipartite graphs (with or without cycles). We derive in this work information- theoretic lower bounds on the bit error probability of a binary linear code used over MBIOS channels. The bounds are ex- pressed in terms of the density of an arbitrary parity-check matrix which represents the binary linear code (i.e., the num- ber of ones in the matrix normalized per information bit), and they are valid for codes whose bipartite graphs are with or without cycles. We introduce a quantitative measure for the cycles in a bipartite graph which represents a binary lin- ear code (where the graph only includes variable nodes and parity-check nodes). The bounds provide an interpretation for the tradeofi which exists between the bit error proba- bility and gap to capacity of an arbitrary LDPC code (i.e., its performance limitations), and the density of an arbitrary parity-check matrix which represents the code (where the lat- ter afiects the decoding complexity per information bit and per iteration, under a message-passing iterative decoding al- gorithm). We present in this work quantitative results which indicate that in order to approach the channel capacity with vanishing bit error probability, LDPC codes should not have too sparse parity-check matrices, as otherwise their inherent gap to capacity becomes large. In fact, we show that the density of any parity-check matrix and the fundamental num- ber of cycles of the graph which represents the code should increase at least like log 1 where designates the gap to ca- pacity under iterative message-passing decoding (see (2), (3)). The tightness of the lower bounds which are derived in this work (and whose validity is for any sequence of codes with 1 1.5 2 2.5 3 3.5 4 4.5
We consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) code and belief propagation (BP) decoding. Furthermore, a gap between the bit error probability after finite number of iterations for finite block length n and that for infinite block length is asymptotically α/n, where α denotes a speci..c constant determined by a degree distribution, a number of iterations and erasure probability. Our main result is to derive an ef..cient algorithm for calculating α for regular ensembles.
We investigate the average erasure probability of the belief propagation algorithm over the binary erasure channel (BEC) for various finite-length low-density parity-check (LDPC) ensembles. In particular, we give tight upper bounds on the "error floor", i.e., on the contribution to the erasure probability stemming from relatively small deficiencies in the graph. We also define and analyse "expurgated" ensembles and give upper bounds on the error floor of "typical" codes. Finally, we show that typical codes of properly chosen ensembles have an erasure correcting radius which grows linearly in the block length. The presented method provides valuable insight into how finite-length codes should be designed. Although the standard ensemble can achieve capacity on the BEC, the construction of good finite-length codes requires careful control of the structure of the degree two variable nodes. In this paper, we investigate the standard ensemble, the Poisson ensemble, an ensemble in which degree two nodes are added in a cycle, and an ensemble in which different degree two variable nodes have distinct neighboring check nodes.