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 Information Theory Workshop (ITW)

The Complexity Limits of Graphical Models for Linear Codes

Thomas R. Halford, K.M. Chugg

Published Sep 1, 2007• 1 citation
Publisher

Abstract

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.

DOI
10.1109/itw.2007.4313064

Related papers

The Extraction and Complexity Limits of Graphical Models for Linear Codes

Thomas R. Halford, K.M. Chugg

Two broad classes of graphical modeling problems for codes can be identified in the literature: constructive and extractive problems. The former class of problems concern the construction of a graphical model in order to define a new code. The latter class of problems concern the extraction of a graphical model for a (fixed) given code. The design of a new low-density parity-check code for some given criteria (e.g., target block length and code rate) is an example of a constructive problem. The determination of a graphical model for a classical linear block code that implies a decoding algorithm with desired performance and complexity characteristics is an example of an extractive problem. This work focuses on extractive graphical model problems and aims to lay out some of the foundations of the theory of such problems for linear codes. The primary focus of this work is a study of the space of all graphical models for a (fixed) given code. The tradeoff between cyclic topology and complexity in this space is characterized via the introduction of a new bound: the forest-inducing cut-set bound (FI-CSB). The proposed bound provides a more precise characterization of this tradeoff than that which can be obtained using existing tools (e.g., the CSB) and can be viewed as a generalization of the square-root bound for tail-biting trellises to graphical models with arbitrary cyclic topologies. Searching the space of graphical models for a given code is then enabled by introducing a set of basic graphical model transformation operations that are shown to span this space. Finally, heuristics for extracting novel graphical models for linear block codes using these transformations are investigated.

IEEE Transactions on Information Theory•Aug 27, 2008•19 citations

The Extraction and Complexity Limits of Graphical Models for Linear Codes

Thomas R. Halford, K.M. Chugg

Two broad classes of graphical modeling problems for codes can be identified in the literature: constructive and extractive problems. The former class of problems concern the construction of a graphical model in order to define a new code. The latter class of problems concern the extraction of a graphical model for a (fixed) given code. The design of a new low-density parity-check code for some given criteria (e.g. target block length and code rate) is an example of a constructive problem. The determination of a graphical model for a classical linear block code which implies a decoding algorithm with desired performance and complexity characteristics is an example of an extractive problem. This work focuses on extractive graphical model problems and aims to lay out some of the foundations of the theory of such problems for linear codes. The primary focus of this work is a study of the space of all graphical models for a (fixed) given code. The tradeoff between cyclic topology and complexity in this space is characterized via the introduction of a new bound: the tree-inducing cut-set bound. The proposed bound provides a more precise characterization of this tradeoff than that which can be obtained using existing tools (e.g. the Cut-Set Bound) and can be viewed as a generalization of the square-root bound for tail-biting trellises to graphical models with arbitrary cyclic topologies. Searching the space of graphical models for a given code is then enabled by introducing a set of basic graphical model transformation operations which are shown to span this space. Finally, heuristics for extracting novel graphical models for linear block codes using these transformations are investigated.

arXiv:cs/0611089•Nov 18, 2006•0 citations

The Tradeoff Between Cyclic Topology and Complexity in Graphical Models of Linear Codes

Thomas R. Halford, K.M. Chugg

It is now well-known that together with a suitable message passing schedule, a graphical model for a code implies a soft-in soft-out (SISO) decoding algorithm which is optimal for cycle-free models and suboptimal, yet often substantially less complex, for cyclic models.The Cut-Set Bound (CSB) indicates that the introduction of cycles to graphical models can lead to dramatic reductions in complexity and in the case of tailbiting trellises (i.e.single-cycle models), the CSB can be used to establish the square-root bound, thus quantifying this potential reduction precisely.The aim of this work is to provide such a precise characterization of the tradeoff between cyclic topology and complexity (i.e.maximum hidden variable size and local constraint complexity) in graphical models with more than one cycle.To this end, a new bound is introduced -the tree-inducing cut-set bound -which can be viewed as a generalization of the square-root bound to graphical models with arbitrary cyclic topologies.

•Sep 27, 2006•0 citations

Which codes have cycle-free Tanner graphs?

Tuvi Etzion, Ari Trachtenberg, Alexander Vardy

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.

IEEE Transactions on Information Theory•Sep 1, 1999•158 citations

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

Tanner graphs for group block codes and lattices: construction and complexity

Amir H. Banihashemi, Frank R. Kschischang

We develop a Tanner graph (TG) construction for an Abelian group block code L with arbitrary alphabets at different coordinates, an important application of which is the representation of the label code of a lattice. The construction is based on the modular linear constraints imposed on the code symbols by a set of generators for the dual code L*. As a necessary step toward the construction of a TG for L we devise an efficient algorithm for finding a generating set for L*. In the process, we develop a construction for lattices based on an arbitrary Abelian group block code, called generalized Construction A (GCA), and explore relationships among a group code, its GCA lattice, and their duals. We also study the problem of finding low-complexity TGs for Abelian group block codes and lattices; and derive tight lower bounds on the label-code complexity of lattices. It is shown that for many important lattices, the minimal label codes which achieve the lower bounds cannot be supported by cycle-free Tanner graphs.

IEEE Transactions on Information Theory•Jan 1, 2001•24 citations
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.
Two broad classes of graphical modeling problems for codes can be identified in the literature: constructive and extractive problems. The former class of problems concern the construction of a graphical model in order to define a new code. The latter class of problems concern the extraction of a graphical model for a (fixed) given code. The design of a new low-density parity-check code for some given criteria (e.g., target block length and code rate) is an example of a constructive problem. The determination of a graphical model for a classical linear block code that implies a decoding algorithm with desired performance and complexity characteristics is an example of an extractive problem. This work focuses on extractive graphical model problems and aims to lay out some of the foundations of the theory of such problems for linear codes. The primary focus of this work is a study of the space of all graphical models for a (fixed) given code. The tradeoff between cyclic topology and complexity in this space is characterized via the introduction of a new bound: the forest-inducing cut-set bound (FI-CSB). The proposed bound provides a more precise characterization of this tradeoff than that which can be obtained using existing tools (e.g., the CSB) and can be viewed as a generalization of the square-root bound for tail-biting trellises to graphical models with arbitrary cyclic topologies. Searching the space of graphical models for a given code is then enabled by introducing a set of basic graphical model transformation operations that are shown to span this space. Finally, heuristics for extracting novel graphical models for linear block codes using these transformations are investigated.
Two broad classes of graphical modeling problems for codes can be identified in the literature: constructive and extractive problems. The former class of problems concern the construction of a graphical model in order to define a new code. The latter class of problems concern the extraction of a graphical model for a (fixed) given code. The design of a new low-density parity-check code for some given criteria (e.g. target block length and code rate) is an example of a constructive problem. The determination of a graphical model for a classical linear block code which implies a decoding algorithm with desired performance and complexity characteristics is an example of an extractive problem. This work focuses on extractive graphical model problems and aims to lay out some of the foundations of the theory of such problems for linear codes. The primary focus of this work is a study of the space of all graphical models for a (fixed) given code. The tradeoff between cyclic topology and complexity in this space is characterized via the introduction of a new bound: the tree-inducing cut-set bound. The proposed bound provides a more precise characterization of this tradeoff than that which can be obtained using existing tools (e.g. the Cut-Set Bound) and can be viewed as a generalization of the square-root bound for tail-biting trellises to graphical models with arbitrary cyclic topologies. Searching the space of graphical models for a given code is then enabled by introducing a set of basic graphical model transformation operations which are shown to span this space. Finally, heuristics for extracting novel graphical models for linear block codes using these transformations are investigated.
It is now well-known that together with a suitable message passing schedule, a graphical model for a code implies a soft-in soft-out (SISO) decoding algorithm which is optimal for cycle-free models and suboptimal, yet often substantially less complex, for cyclic models.The Cut-Set Bound (CSB) indicates that the introduction of cycles to graphical models can lead to dramatic reductions in complexity and in the case of tailbiting trellises (i.e.single-cycle models), the CSB can be used to establish the square-root bound, thus quantifying this potential reduction precisely.The aim of this work is to provide such a precise characterization of the tradeoff between cyclic topology and complexity (i.e.maximum hidden variable size and local constraint complexity) in graphical models with more than one cycle.To this end, a new bound is introduced -the tree-inducing cut-set bound -which can be viewed as a generalization of the square-root bound to graphical models with arbitrary cyclic topologies.
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.
We develop a Tanner graph (TG) construction for an Abelian group block code L with arbitrary alphabets at different coordinates, an important application of which is the representation of the label code of a lattice. The construction is based on the modular linear constraints imposed on the code symbols by a set of generators for the dual code L*. As a necessary step toward the construction of a TG for L we devise an efficient algorithm for finding a generating set for L*. In the process, we develop a construction for lattices based on an arbitrary Abelian group block code, called generalized Construction A (GCA), and explore relationships among a group code, its GCA lattice, and their duals. We also study the problem of finding low-complexity TGs for Abelian group block codes and lattices; and derive tight lower bounds on the label-code complexity of lattices. It is shown that for many important lattices, the minimal label codes which achieve the lower bounds cannot be supported by cycle-free Tanner graphs.