Codes on planar Tanner graphs

DOI10.3934/AMC.2012.6.131zbMATH Open1278.94075DBLPjournals/amco/SrinivasanT12arXiv0904.0768OpenAlexW2079829049WikidataQ58606553 ScholiaQ58606553MaRDI QIDQ444514FDOQ444514

Authors: Srimathy Srinivasan, Andrew Thangaraj 

Publication date: 14 August 2012

Published in: Advances in Mathematics of Communications (Search for Journal in Brave)

Abstract: Codes defined on graphs and their properties have been subjects of intense recent research. On the practical side, constructions for capacity-approaching codes are graphical. On the theoretical side, codes on graphs provide several intriguing problems in the intersection of coding theory and graph theory. In this paper, we study codes defined by planar Tanner graphs. We derive an upper bound on minimum distance $d$ of such codes as a function of the code rate $R$ for $Rge5/8$. The bound is given by ${\displaystyle }$dle lceil frac{7-8R}{2(2R-1)} ceil + 3le 7.${\displaystyle }$ Among the interesting conclusions of this result are the following: (1) planar graphs do not support asymptotically good codes, and (2) finite-length, high-rate codes on graphs with high minimum distance will necessarily be non-planar.

Full work available at URL: https://arxiv.org/abs/0904.0768

Recommendations

• On Tanner codes: Minimum distance and decoding
• Which codes have cycle-free Tanner graphs?
• On cycle-free lattices
• The minimum distance of graph codes
• Which Codes Have$4$-Cycle-Free Tanner Graphs?

zbMATH Keywords

linear codesdistance boundsplanar Tanner graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Linear codes (general theory) (94B05) Bounds on codes (94B65)

Cited In (6)

• Planar Convex Codes are Decidable
• On Tanner codes: Minimum distance and decoding
• On a code problem concerning planar acyclic graphs
• Links and Planar Diagram Codes
• Discriminating codes in (bipartite) planar graphs
• Codes with girth 8 Tanner graph representation

This page was built for publication: Codes on planar Tanner graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q444514)