Codes on planar Tanner graphs

Srimathy Srinivasan; Andrew Thangaraj

doi:10.3934/amc.2012.6.131

Article Contents

2012, Volume 6, Issue 2: 131-163. Doi: 10.3934/amc.2012.6.131

This issue Previous Article On the symmetry group of extended perfect binary codes of length $n+1$ and rank $n-\log(n+1)+2$ Next Article Combinatorial batch codes: A lower bound and optimal constructions

Codes on planar Tanner graphs

Srimathy Srinivasan^1, and
Andrew Thangaraj^1,

1.
Department of Electrical Engineering, Indian Institute of Technology Madras, Chennai 600036

Received: January 31, 2011

Revised: October 31, 2011

Published: April 2012

Abstract Related Papers Cited by

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.

Keywords:

Mathematics Subject Classification: Primary: 94B05, 05C10; Secondary: 94B65.

Citation:

Related Papers

Cited by

References

[1]	J. A. Bondy and U. S. R. Murty, "Graph Theory with Applications,'' North-Holland, 1976.
[2]	V. Y. Chernyak and M. Chertkov, Planar graphical models which are easy, J. Statist. Mechan. Theory Exper., 2010 (2010), p. P11007.doi: 10.1088/1742-5468/2010/11/P11007.
[3]	M. Chertkov, V. Y. Chernyak and R. Teodorescu, Belief propagation and loop series on planar graphs, J. Statist. Mechan. Theory Exper., 2008 (2008), p. P05003.doi: 10.1088/1742-5468/2008/05/P05003.
[4]	K. Diks, H. N. Djidjev, O. Sykora and I. Vrto, Edge separators of planar and outerplanar graphs with applications, J. Algorithms, 14 (1993), 258-279.doi: 10.1006/jagm.1993.1013.
[5]	T. Etzion, A. Trachtenberg and A. Vardy, Which codes have cycle-free Tanner graphs?, IEEE Trans. Inform. Theory, 45 (1999), 2173-2181.doi: 10.1109/18.782170.
[6]	V. Gómez, H. J. Kappen and M. Chertkov, Approximate inference on planar graphs using loop calculus and belief propagation, J. Mach. Learn. Res., 99 (2010), 1273-1296.
[7]	F. Harary, "Graph Theory,'' Addison-Wesley Publishers, 1969.
[8]	N. Kashyap, Code decomposition: theory and applications, in "IEEE International Symposium on Information Theory,'' (2007), 481-485.doi: 10.1109/ISIT.2007.4557271.
[9]	N. Kashyap, A decomposition theory for binary linear codes, IEEE Trans. Inform. Theory, 54 (2008), 3035-3058.doi: 10.1109/TIT.2008.924700.
[10]	R. J. Lipton and R. E. Tarjan, Applications of a planar separator theorem, in "18th Annual Symposium on Foundations of Computer Science,'' (1977), 162-170.doi: 10.1109/SFCS.1977.6.
[11]	S. Srinivasan and A. Thangaraj, Codes that have Tanner graphs with non-overlapping cycles, in "5th International Symposium on Turbo Codes and Related Topics,'' (2008), 299-304.
[12]	B. Xiang, R. Shen, A. Pan, D. Bao and X. Zeng, An area-efficient and low-power multirate decoder for quasi-cyclic low-density parity-check codes, IEEE Trans. Very Large Scale Integr. Systems, 18 (2010), 1447-1460.doi: 10.1109/TVLSI.2009.2025169.
[13]	C. Zhang, Z. Wang, J. Sha, L. Li and J. Lin, Flexible LDPC decoder design for multigigabit-per-second applications, IEEE Trans. Circ. Systems I, 57 (2010), 116-124.doi: 10.1109/TCSI.2009.2018915.