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

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

Amir H. Banihashemi, Frank R. Kschischang

Published Jan 1, 2001• 24 citations
Publisher

Abstract

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.

DOI
10.1109/18.910592

Related papers

On Tanner graphs of lattices and codes

Amir H. Banihashemi, Frank R. Kschischang, P. Glenn Gulak

The problem of finding a low-complexity Tanner graph for a general lattice /spl Lambda/ is studied. The problem is divided into two subproblems: (1) Finding an orthogonal sublattice /spl Lambda/' of /spl Lambda/ which minimizes the complexity of the label code of the quotient group /spl Lambda///spl Lambda/'. (2) Constructing a simple Tanner graph for the label code obtained in part 1. The proposed approach for solving subproblem 2 can also be applied to any abelian group block code with arbitrary finite alphabets at different coordinates. The results of this work are useful in finding low-complexity graph representation of lattices and codes, which consequently results in efficient graph-based decoding algorithms.

IEEE International Symposium on Information Theory (ISIT)•Nov 27, 2002•2 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

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

Construction of Cycle-free LDPC Codes

Fengfan Yang

The linear block code is called a binary Low-Density Parity-Check code if whose parity-check matrix is a sparse matrix. For the features of parity-check matrix, a LDPC code can be illustrated by a Tanner graph. Cycles, especially short cycles in the Tanner graph, lead to inefficient decoding and prevent the decoding algorithm from converging to the optimal decoding result. In this paper, a simple algorithm of constructing four-cycle-free regular A(n,d_v,d_c)LDPC codes, d_v3, is introduced. And we analyse the relationship between the performance and the cycle.

Journal of Yunnan University for Nationalites•Jan 1, 2005•0 citations

Low-delay low-complexity error-correcting codes on sparse graphs

Hu, Xiao-Yu

This dissertation presents a systematic exposition on finite-block-length coding theory and practice. We begin with the task of identifying the maximum achievable rates over noisy, finite-block-length constrained channels, referred to as (ε, n)-capacity Cεn, with ε denoting target block-error probability and n the block length. We characterize how the optimum codes look like over finite-block-length constrained channels. Constructing good, short-block-length error-correcting codes defined on sparse graphs is the focus of the thesis. We propose a new, general method for constructing Tanner graphs having a large girth by progressively establishing edges or connections between symbol and check nodes in an edge-by-edge manner, called progressive edge-growth (PEG) construction. Lower bounds on the girth of PEG Tanner graphs and on the minimum distance of the resulting low-density parity-check (LDPC) codes are derived in terms of parameters of the graphs. The PEG construction attains essentially the same girth as Gallager's explicit construction for regular graphs, both of which meet or exceed an extension of the Erdös-Sachs bound. The PEG construction proves to be powerful for generating good, short-block-length binary LDPC codes. Furthermore, we show that the binary interpretation of GF(2b) codes on the cycle Tanner graph TG(2, dc), if b grows sufficiently large, can be used over the binary-input additive white Gaussian noise (AWGN) channel as "good code for optimum decoding" and "good code for iterative decoding". Codes on sparse graphs are often decoded iteratively by a sum-product algorithm (SPA) with low complexity. We investigate efficient digital implementations of the SPA for decoding binary LDPC codes from both the architectural and algorithmic point of view, and describe new reduced-complexity derivatives thereof. The unified treatment of decoding techniques for LDPC codes provides flexibility in selecting the appropriate design point in high-speed applications from a performance, latency, and computational complexity perspective.

•Jan 1, 2003•26 citations

Regular and irregular progressive edge-growth tanner graphs

Xiao-Yu Hu, Evangelos S. Eleftheriou, Donald M. Arnold

We propose a general method for constructing Tanner graphs having a large girth by establishing edges or connections between symbol and check nodes in an edge-by-edge manner, called progressive edge-growth (PEG) algorithm. Lower bounds on the girth of PEG Tanner graphs and on the minimum distance of the resulting low-density parity-check (LDPC) codes are derived in terms of parameters of the graphs. Simple variations of the PEG algorithm can also be applied to generate linear-time encodeable LDPC codes. Regular and irregular LDPC codes using PEG Tanner graphs and allowing symbol nodes to take values over GF(q) (q>2) are investigated. Simulation results show that the PEG algorithm is a powerful algorithm to generate good short-block-length LDPC codes.

IEEE Transactions on Information Theory•Jan 1, 2005•1,489 citations
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.
The problem of finding a low-complexity Tanner graph for a general lattice /spl Lambda/ is studied. The problem is divided into two subproblems: (1) Finding an orthogonal sublattice /spl Lambda/' of /spl Lambda/ which minimizes the complexity of the label code of the quotient group /spl Lambda///spl Lambda/'. (2) Constructing a simple Tanner graph for the label code obtained in part 1. The proposed approach for solving subproblem 2 can also be applied to any abelian group block code with arbitrary finite alphabets at different coordinates. The results of this work are useful in finding low-complexity graph representation of lattices and codes, which consequently results in efficient graph-based decoding algorithms.
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.
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.
The linear block code is called a binary Low-Density Parity-Check code if whose parity-check matrix is a sparse matrix. For the features of parity-check matrix, a LDPC code can be illustrated by a Tanner graph. Cycles, especially short cycles in the Tanner graph, lead to inefficient decoding and prevent the decoding algorithm from converging to the optimal decoding result. In this paper, a simple algorithm of constructing four-cycle-free regular A(n,d_v,d_c)LDPC codes, d_v3, is introduced. And we analyse the relationship between the performance and the cycle.
This dissertation presents a systematic exposition on finite-block-length coding theory and practice. We begin with the task of identifying the maximum achievable rates over noisy, finite-block-length constrained channels, referred to as (ε, n)-capacity Cεn, with ε denoting target block-error probability and n the block length. We characterize how the optimum codes look like over finite-block-length constrained channels. Constructing good, short-block-length error-correcting codes defined on sparse graphs is the focus of the thesis. We propose a new, general method for constructing Tanner graphs having a large girth by progressively establishing edges or connections between symbol and check nodes in an edge-by-edge manner, called progressive edge-growth (PEG) construction. Lower bounds on the girth of PEG Tanner graphs and on the minimum distance of the resulting low-density parity-check (LDPC) codes are derived in terms of parameters of the graphs. The PEG construction attains essentially the same girth as Gallager's explicit construction for regular graphs, both of which meet or exceed an extension of the Erdös-Sachs bound. The PEG construction proves to be powerful for generating good, short-block-length binary LDPC codes. Furthermore, we show that the binary interpretation of GF(2b) codes on the cycle Tanner graph TG(2, dc), if b grows sufficiently large, can be used over the binary-input additive white Gaussian noise (AWGN) channel as "good code for optimum decoding" and "good code for iterative decoding". Codes on sparse graphs are often decoded iteratively by a sum-product algorithm (SPA) with low complexity. We investigate efficient digital implementations of the SPA for decoding binary LDPC codes from both the architectural and algorithmic point of view, and describe new reduced-complexity derivatives thereof. The unified treatment of decoding techniques for LDPC codes provides flexibility in selecting the appropriate design point in high-speed applications from a performance, latency, and computational complexity perspective.
We propose a general method for constructing Tanner graphs having a large girth by establishing edges or connections between symbol and check nodes in an edge-by-edge manner, called progressive edge-growth (PEG) algorithm. Lower bounds on the girth of PEG Tanner graphs and on the minimum distance of the resulting low-density parity-check (LDPC) codes are derived in terms of parameters of the graphs. Simple variations of the PEG algorithm can also be applied to generate linear-time encodeable LDPC codes. Regular and irregular LDPC codes using PEG Tanner graphs and allowing symbol nodes to take values over GF(q) (q>2) are investigated. Simulation results show that the PEG algorithm is a powerful algorithm to generate good short-block-length LDPC codes.