# American Institute of Mathematical Sciences

May  2012, 6(2): 131-163. doi: 10.3934/amc.2012.6.131

## Codes on planar Tanner graphs

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

Received  February 2011 Revised  November 2011 Published  April 2012

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.
Citation: Srimathy Srinivasan, Andrew Thangaraj. Codes on planar Tanner graphs. Advances in Mathematics of Communications, 2012, 6 (2) : 131-163. doi: 10.3934/amc.2012.6.131
##### References:
 [1] J. A. Bondy and U. S. R. Murty, "Graph Theory with Applications,'', North-Holland, (1976). Google Scholar [2] V. Y. Chernyak and M. Chertkov, Planar graphical models which are easy,, J. Statist. Mechan. Theory Exper., 2010 (2010). doi: 10.1088/1742-5468/2010/11/P11007. Google Scholar [3] M. Chertkov, V. Y. Chernyak and R. Teodorescu, Belief propagation and loop series on planar graphs,, J. Statist. Mechan. Theory Exper., 2008 (2008). doi: 10.1088/1742-5468/2008/05/P05003. Google Scholar [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. doi: 10.1006/jagm.1993.1013. Google Scholar [5] T. Etzion, A. Trachtenberg and A. Vardy, Which codes have cycle-free Tanner graphs?,, IEEE Trans. Inform. Theory, 45 (1999), 2173. doi: 10.1109/18.782170. Google Scholar [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. Google Scholar [7] F. Harary, "Graph Theory,'', Addison-Wesley Publishers, (1969). Google Scholar [8] N. Kashyap, Code decomposition: theory and applications,, in, (2007), 481. doi: 10.1109/ISIT.2007.4557271. Google Scholar [9] N. Kashyap, A decomposition theory for binary linear codes,, IEEE Trans. Inform. Theory, 54 (2008), 3035. doi: 10.1109/TIT.2008.924700. Google Scholar [10] R. J. Lipton and R. E. Tarjan, Applications of a planar separator theorem,, in, (1977), 162. doi: 10.1109/SFCS.1977.6. Google Scholar [11] S. Srinivasan and A. Thangaraj, Codes that have Tanner graphs with non-overlapping cycles,, in, (2008), 299. Google Scholar [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. doi: 10.1109/TVLSI.2009.2025169. Google Scholar [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. doi: 10.1109/TCSI.2009.2018915. Google Scholar

show all references

##### References:
 [1] J. A. Bondy and U. S. R. Murty, "Graph Theory with Applications,'', North-Holland, (1976). Google Scholar [2] V. Y. Chernyak and M. Chertkov, Planar graphical models which are easy,, J. Statist. Mechan. Theory Exper., 2010 (2010). doi: 10.1088/1742-5468/2010/11/P11007. Google Scholar [3] M. Chertkov, V. Y. Chernyak and R. Teodorescu, Belief propagation and loop series on planar graphs,, J. Statist. Mechan. Theory Exper., 2008 (2008). doi: 10.1088/1742-5468/2008/05/P05003. Google Scholar [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. doi: 10.1006/jagm.1993.1013. Google Scholar [5] T. Etzion, A. Trachtenberg and A. Vardy, Which codes have cycle-free Tanner graphs?,, IEEE Trans. Inform. Theory, 45 (1999), 2173. doi: 10.1109/18.782170. Google Scholar [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. Google Scholar [7] F. Harary, "Graph Theory,'', Addison-Wesley Publishers, (1969). Google Scholar [8] N. Kashyap, Code decomposition: theory and applications,, in, (2007), 481. doi: 10.1109/ISIT.2007.4557271. Google Scholar [9] N. Kashyap, A decomposition theory for binary linear codes,, IEEE Trans. Inform. Theory, 54 (2008), 3035. doi: 10.1109/TIT.2008.924700. Google Scholar [10] R. J. Lipton and R. E. Tarjan, Applications of a planar separator theorem,, in, (1977), 162. doi: 10.1109/SFCS.1977.6. Google Scholar [11] S. Srinivasan and A. Thangaraj, Codes that have Tanner graphs with non-overlapping cycles,, in, (2008), 299. Google Scholar [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. doi: 10.1109/TVLSI.2009.2025169. Google Scholar [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. doi: 10.1109/TCSI.2009.2018915. Google Scholar

2018 Impact Factor: 0.879