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

Advances in Mathematics of Communications

Codes on planar Tanner graphs

Srimathy Srinivasan, Andrew Thangaraj

Published Jan 1, 2012• 0 citations
Publisher

Abstract

Codes defined on graphs and their properties have been subjects of intense recent research. In this work, we are concerned with codes that have planar Tanner graphs. When the Tanner graph is planar, message-passing decoders can be efficiently implemented on chips without any issues of wiring. Also, recent work has shown the existence of optimal decoders for certain planar graphical models. The main contribution of this paper is an explicit upper bound on minimum distance $d$ of codes that have planar Tanner graphs as a function of the code rate $R$ for $R \geq 5/8$. The bound is given by\begin{equation*}d\le \left\lceil \frac{7-8R}{2(2R-1)} \right\rceil + 3\le 7.\end{equation*}As a result, high-rate codes with planar Tanner graphs will result in poor block-error rate performance, because of the constant upper bound on minimum distance.

DOI
10.3934/amc.2012.6.131

Related papers

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 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

Lower Bounds on Stopping Distance of Linear Codes and Their Applications

Mingrui Zhu, K.M. Chugg

One of the most important open problems in the communication society is to determine the performance of iterative message passing algorithms over loopy graphs.Some recent work addresses this problem for loopy Tanner graphs by introducing the concepts of stopping distance and stopping redundancy.By analyzing the eigenvalues and eigenvectors of the normalized incidence matrix representing a Tanner graph, we derive lower bounds on its stopping distance.Using these lower bounds, an upper bound on stopping redundancy of the difference-set codes is derived as well.

•Sep 28, 2005•0 citations

Permutation-block LDPC codes: influence of Tanner-graph structure on minimum hamming distance

Benjamin Michael Thorn

Only since the mid-1990s, with the increase in computational power, has the\nimportance been realized regarding low-density parity-check (LDPC) codes as leading error\ncorrecting codes. The work in this thesis primarily studies LDPC codes that are de???ned by a\nparity-check matrix comprised of r _ r permutation matrix blocks, that is, permutation-block\nLDPC codes. More specifically, we study their minimum Hamming distance, as this is a\nparameter that affects the performance of linear codes, and thus LDPC codes.\nIt has been proven that there are upper bounds on the minimum Hamming distance of\nquasi-cyclic codes, de???ned by a parity-check matrix comprised of r _ r circulant matrix\nblocks, regardless of how large we allow r. However, we show that if general permutation\nmatrices are used instead of circulant matrices, we are able to exceed the bounds allowed by\nquasi-cyclic codes. Graphical representations of the codes, called Tanner-graphs, are used in\nproving many useful results regarding permutation-block LDPC codes and their minimum\nHamming distance. We show a characterization of the minimum Hamming distance of these\ncodes and we produce an algorithm for constructing permutation-block LDPC codes with\nlarge minimum Hamming distance.

•Jun 28, 2011•0 citations

Bounds on the Expansion Properties of Tanner Graphs

Mingrui Zhu, K.M. Chugg

This work focuses on the expansion properties of a Tanner Graph because they are known to be related to the performance of associated iterative message-passing algorithms over various channels. By analyzing the eigenvalues and corresponding eigenvectors of the normalized incidence matrix representing a Tanner Graph, lower bounds on these expansion properties are derived. Specifically, for the binary erasure channel, these results lead to two lower bounds on stopping distance for any given binary linear code and an upper bound on stopping redundancy for the family of difference-set codes (type-I 2-D projective geometry low-density parity-check (LDPC) codes).

IEEE Transactions on Information Theory•Dec 1, 2007•3 citations

Generalization of Tanner's minimum distance bounds for LDPC codes

Min-Ho Shin, Joon-Sung Kim, Hong‐Yeop Song

Tanner derived minimum distance bounds of regular codes in terms of the eigenvalues of the adjacency matrix by using some graphical analysis on the associated graph of the code. In this letter, we generalize Tanner's results by deriving a bit-oriented bound and a parity-oriented bound on the minimum distances of both regular and block-wise irregular LDPC codes.

IEEE Communications Letters•Mar 1, 2005•7 citations
Codes defined on graphs and their properties have been subjects of intense recent research. In this work, we are concerned with codes that have planar Tanner graphs. When the Tanner graph is planar, message-passing decoders can be efficiently implemented on chips without any issues of wiring. Also, recent work has shown the existence of optimal decoders for certain planar graphical models. The main contribution of this paper is an explicit upper bound on minimum distance ddd of codes that have planar Tanner graphs as a function of the code rate RRR for R≥5/8R \geq 5/8R≥5/8. The bound is given by\begin{equation*}d\le \left\lceil \frac{7-8R}{2(2R-1)} \right\rceil + 3\le 7.\end{equation*}As a result, high-rate codes with planar Tanner graphs will result in poor block-error rate performance, because of the constant upper bound on minimum distance.
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.
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.
One of the most important open problems in the communication society is to determine the performance of iterative message passing algorithms over loopy graphs.Some recent work addresses this problem for loopy Tanner graphs by introducing the concepts of stopping distance and stopping redundancy.By analyzing the eigenvalues and eigenvectors of the normalized incidence matrix representing a Tanner graph, we derive lower bounds on its stopping distance.Using these lower bounds, an upper bound on stopping redundancy of the difference-set codes is derived as well.
Only since the mid-1990s, with the increase in computational power, has the\nimportance been realized regarding low-density parity-check (LDPC) codes as leading error\ncorrecting codes. The work in this thesis primarily studies LDPC codes that are de???ned by a\nparity-check matrix comprised of r _ r permutation matrix blocks, that is, permutation-block\nLDPC codes. More specifically, we study their minimum Hamming distance, as this is a\nparameter that affects the performance of linear codes, and thus LDPC codes.\nIt has been proven that there are upper bounds on the minimum Hamming distance of\nquasi-cyclic codes, de???ned by a parity-check matrix comprised of r _ r circulant matrix\nblocks, regardless of how large we allow r. However, we show that if general permutation\nmatrices are used instead of circulant matrices, we are able to exceed the bounds allowed by\nquasi-cyclic codes. Graphical representations of the codes, called Tanner-graphs, are used in\nproving many useful results regarding permutation-block LDPC codes and their minimum\nHamming distance. We show a characterization of the minimum Hamming distance of these\ncodes and we produce an algorithm for constructing permutation-block LDPC codes with\nlarge minimum Hamming distance.
This work focuses on the expansion properties of a Tanner Graph because they are known to be related to the performance of associated iterative message-passing algorithms over various channels. By analyzing the eigenvalues and corresponding eigenvectors of the normalized incidence matrix representing a Tanner Graph, lower bounds on these expansion properties are derived. Specifically, for the binary erasure channel, these results lead to two lower bounds on stopping distance for any given binary linear code and an upper bound on stopping redundancy for the family of difference-set codes (type-I 2-D projective geometry low-density parity-check (LDPC) codes).