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

Which codes have cycle-free Tanner graphs?

Tuvi Etzion, Ari Trachtenberg, Alexander Vardy

Published Sep 1, 1999• 158 citations
Publisher

Abstract

If a linear block code C of length n has a Tanner graph without cycles, then maximum-likelihood soft-decision decoding of C can be achieved in time O(n/sup 2/). However, we show that cycle-free Tanner graphs cannot support good codes. Specifically, let C be an (n,k,d) linear code of rate R=k/n that can be represented by a Tanner graph without cycles. We prove that if R/spl ges/0.5 then d/spl les/2, while if R<0.5 then C is obtained from a code of rate /spl ges/0.5 and distance /spl les/2 by simply repeating certain symbols. In the latter case, we prove that d/spl les/[n/k+1]+[n+1/k+1]<2/R. Furthermore, we show by means of an explicit construction that this bound is tight for all values of n and k. We also prove that binary codes which have cycle-free Tanner graphs belong to the class of graph-theoretic codes, known as cut-set codes of a graph. Finally, we discuss the asymptotics for Tanner graphs with cycles, and present a number of open problems for future research.

DOI
10.1109/18.782170

Related papers

Which codes have cycle-free Tanner graphs?

T. Etzion, Ari Trachtenberg, Alexander Vardy

If a linear (n,k,d) code C has a Tanner graph without cycles, then maximum-likelihood soft-decision decoding of C can be achieved in time O(n/sup 2/). However, we show that cycle-free Tanner graphs cannot support good codes: we prove that d/spl les/max{2,2/R} for any linear code of rate R that can be represented by a cycle-free Tanner graph. Moreover, we explicitly construct codes that meet this bound with equality. We also show that all binary codes that have cycle-free Tanner graphs belong to the class of graph-theoretic cut-set codes. We conclude that the number of cycles in a Tanner graph must increase exponentially with the length n for asymptotically good codes.

IEEE International Symposium on Information Theory (ISIT)•Nov 27, 2002•10 citations

Which Codes Have 4-Cycle-Free Tanner Graphs?

Thomas R. Halford, K.M. Chugg, Alex J. Grant

Let C be an [n, k, d] binary linear code with rate R = k/n and dual Cperp. In this correspondence, it is shown that C can be represented by a 4-cycle-free Tanner graph only if: pdperples lfloorradicnp(p-1)+n2/4+n/2rfloor where p = n - k and dperpis the minimum distance of Cperp. By applying this result, it is shown that 4-cycle-free Tanner graphs do not exist for many classical binary linear block codes

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•8 citations

Codes that have tanner graphs with non-overlapping cycles

S. Srimathy, Andrew Thangaraj

The Sum-Product Algorithm (SPA) for the decoding of Low Density Parity Check (LDPC) codes produces exact posterior probabilities when the underlying Tanner graph is cycle-free. However, it has been shown that cycle-free Tanner graphs cannot support good codes as they have poor minimum distance properties. When a Tanner graph has cycles that do not overlap (no two cycles have any node in common), the corresponding code has managable minimal tree complexity so that optimal decoding can be achieved. In this paper, we consider codes whose Tanner graphs contain non-overlapping cycles. We derive upper bounds on the minimum distance for such codes, and show that the upper bound can be at most one more than that of a tree code for any given block length and rate. Our results imply that Tanner graphs of good codes will contain several cycles that overlap.

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

Which Codes Have444-Cycle-Free Tanner Graphs?

Thomas R. Halford, Alex J. Grant, K.M. Chugg

Let C be an [n,k,d] binary linear code with rate R=k/n and dual Cperp. In this correspondence, it is shown that C can be represented by a 4-cycle-free Tanner graph only if: pdperples lfloorradicnp(p-1)+n2/4+n/2 rfloorwhere p=n-k and dperpis the minimum distance of Cperp. By applying this result, it is shown that 4-cycle- free Tanner graphs do not exist for many classical binary linear block codes

IEEE Transactions on Information Theory•Aug 29, 2006•28 citations

The Complexity Limits of Graphical Models for Linear Codes

Thomas R. Halford, K.M. Chugg

Since the discovery of turbo codes in the 1990s, much of the work concerning graphical models for codes has focused on constructing models in order to define a new code. This work focuses on the theoretical foundations of the inverse problem to code construction -extracting a graphical model for a given (fixed) code. Specifically, limits on the space of graphical models for a given code are examined. A number of results concerning these limits (e.g., the cut-set bound, the square-root bound) are first reviewed. Following this review, recent results concerning these limits are presented. It is first shown that the Tanner graphs of many classical block codes necessarily contain many short cycles. It is then shown that cycle-free binary graphical models do not support good codes thus generalizing Trachtenberg's work concerning the existence of cycle-free Tanner graphs. Finally, and most significantly, the tree-inducing cut-set bound (TI-CSB) is derived and discussed. The TI-CSB provides a characterization of the tradeoff between complexity and density in the family of graphical models for a given code. For example, the TI-CSB can be used to show that anrth-root complexity reduction (with respect to the least-complex cycle-free model) requires the introduction of at leastr(r- 1)/2 cycles thus generalizing the square-root bound to graphical models with arbitrary cyclic topologies.

IEEE Information Theory Workshop (ITW)•Sep 1, 2007•1 citation

Pseudocodeword-Free Criterion for Codes with Cycle-Free Tanner Graph

Wittawat Kositwattanarerk

Iterative decoding and linear programming decoding are guaranteed to converge to the maximum-likelihood codeword when the underlying Tanner graph is cycle-free. Therefore, cycles are usually seen as the culprit of low-density parity-check (LDPC) codes. In this paper, we argue in the context of graph cover pseudocodeword that, for a code that permits a cycle-free Tanner graph, cycles have no effect on error performance as long as they are a part of redundant rows. Specifically, we characterize all parity-check matrices that are pseudocodeword-free for such class of codes.

arXiv:1706.06648•Jun 20, 2017•0 citations
If a linear block code C of length n has a Tanner graph without cycles, then maximum-likelihood soft-decision decoding of C can be achieved in time O(n/sup 2/). However, we show that cycle-free Tanner graphs cannot support good codes. Specifically, let C be an (n,k,d) linear code of rate R=k/n that can be represented by a Tanner graph without cycles. We prove that if R/spl ges/0.5 then d/spl les/2, while if R<0.5 then C is obtained from a code of rate /spl ges/0.5 and distance /spl les/2 by simply repeating certain symbols. In the latter case, we prove that d/spl les/[n/k+1]+[n+1/k+1]<2/R. Furthermore, we show by means of an explicit construction that this bound is tight for all values of n and k. We also prove that binary codes which have cycle-free Tanner graphs belong to the class of graph-theoretic codes, known as cut-set codes of a graph. Finally, we discuss the asymptotics for Tanner graphs with cycles, and present a number of open problems for future research.
If a linear (n,k,d) code C has a Tanner graph without cycles, then maximum-likelihood soft-decision decoding of C can be achieved in time O(n/sup 2/). However, we show that cycle-free Tanner graphs cannot support good codes: we prove that d/spl les/max{2,2/R} for any linear code of rate R that can be represented by a cycle-free Tanner graph. Moreover, we explicitly construct codes that meet this bound with equality. We also show that all binary codes that have cycle-free Tanner graphs belong to the class of graph-theoretic cut-set codes. We conclude that the number of cycles in a Tanner graph must increase exponentially with the length n for asymptotically good codes.
The Sum-Product Algorithm (SPA) for the decoding of Low Density Parity Check (LDPC) codes produces exact posterior probabilities when the underlying Tanner graph is cycle-free. However, it has been shown that cycle-free Tanner graphs cannot support good codes as they have poor minimum distance properties. When a Tanner graph has cycles that do not overlap (no two cycles have any node in common), the corresponding code has managable minimal tree complexity so that optimal decoding can be achieved. In this paper, we consider codes whose Tanner graphs contain non-overlapping cycles. We derive upper bounds on the minimum distance for such codes, and show that the upper bound can be at most one more than that of a tree code for any given block length and rate. Our results imply that Tanner graphs of good codes will contain several cycles that overlap.
Since the discovery of turbo codes in the 1990s, much of the work concerning graphical models for codes has focused on constructing models in order to define a new code. This work focuses on the theoretical foundations of the inverse problem to code construction -extracting a graphical model for a given (fixed) code. Specifically, limits on the space of graphical models for a given code are examined. A number of results concerning these limits (e.g., the cut-set bound, the square-root bound) are first reviewed. Following this review, recent results concerning these limits are presented. It is first shown that the Tanner graphs of many classical block codes necessarily contain many short cycles. It is then shown that cycle-free binary graphical models do not support good codes thus generalizing Trachtenberg's work concerning the existence of cycle-free Tanner graphs. Finally, and most significantly, the tree-inducing cut-set bound (TI-CSB) is derived and discussed. The TI-CSB provides a characterization of the tradeoff between complexity and density in the family of graphical models for a given code. For example, the TI-CSB can be used to show that anrth-root complexity reduction (with respect to the least-complex cycle-free model) requires the introduction of at leastr(r- 1)/2 cycles thus generalizing the square-root bound to graphical models with arbitrary cyclic topologies.
Iterative decoding and linear programming decoding are guaranteed to converge to the maximum-likelihood codeword when the underlying Tanner graph is cycle-free. Therefore, cycles are usually seen as the culprit of low-density parity-check (LDPC) codes. In this paper, we argue in the context of graph cover pseudocodeword that, for a code that permits a cycle-free Tanner graph, cycles have no effect on error performance as long as they are a part of redundant rows. Specifically, we characterize all parity-check matrices that are pseudocodeword-free for such class of codes.