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

International Symposium on Turbo Codes and Iterative Information Processing

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

Igal Sason, Gil Wiechman

Published Sep 1, 2008• 2 citations
Publisher

Abstract

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.

DOI
10.1109/turbocoding.2008.4658690

Related papers

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

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•IEEE Transactions on Information Theory•May 19, 2009•17 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

Tradeoff between decoding complexity and rate for codes on graphs

Pulkit Grover

We consider transmission over a general memoryless channel, with bounded decoding complexity per bit under message passing decoding. We show that the achievable rate is bounded below capacity if there is a finite success in the decoding in a specified number of operations per bit at the decoder for some codes on graphs. These codes include LDPC and LDGM codes. Good performance with low decoding complexity suggests strong local structures in the graphs of these codes, which are detrimental to the code rate asymptotically. The proof method leads to an interesting necessary condition on the code structures which could achieve capacity with bounded decoding complexity. We also show that if a code sequence achieves a rate epsilon close to the channel capacity, the decoding complexity scales at least as O(log(1/epsilon).

arXiv:cs/0702073•Feb 13, 2007•0 citations

Asymptotic gaps between BP decoding and local-MAP decoding for low-density parity-check codes

Ryuhei Mori, Kenta Kasai, Tomoharu Shibuya +1 more

In this paper, we consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) codes. We consider MAP decoding not using a whole Tanner graph but only a neighborhood graph of fixed depth referred to as local-MAP decoding for deriving lower bounds of the error probability under message-passing decoding and bit-flipping decoding. The main result of this paper is to derive an asymptotic performance for regular ensembles under local-MAP decoding and to derive an asymptotic gap of the bit error probability between belief propagation (BP) and local-MAP decoding for irregular ensembles. Finally, we show the limit of the scaling parameter of these decodings when number of iterations tends to infinity.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 1, 2008•3 citations
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.
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).
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 consider transmission over a general memoryless channel, with bounded decoding complexity per bit under message passing decoding. We show that the achievable rate is bounded below capacity if there is a finite success in the decoding in a specified number of operations per bit at the decoder for some codes on graphs. These codes include LDPC and LDGM codes. Good performance with low decoding complexity suggests strong local structures in the graphs of these codes, which are detrimental to the code rate asymptotically. The proof method leads to an interesting necessary condition on the code structures which could achieve capacity with bounded decoding complexity. We also show that if a code sequence achieves a rate epsilon close to the channel capacity, the decoding complexity scales at least as O(log(1/epsilon).
In this paper, we consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) codes. We consider MAP decoding not using a whole Tanner graph but only a neighborhood graph of fixed depth referred to as local-MAP decoding for deriving lower bounds of the error probability under message-passing decoding and bit-flipping decoding. The main result of this paper is to derive an asymptotic performance for regular ensembles under local-MAP decoding and to derive an asymptotic gap of the bit error probability between belief propagation (BP) and local-MAP decoding for irregular ensembles. Finally, we show the limit of the scaling parameter of these decodings when number of iterations tends to infinity.