American Institute of Mathematical Sciences

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

Codes on planar Tanner graphs

Srimathy Srinivasan 1, and  Andrew Thangaraj 1,

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.
Keywords: planar Tanner graphs, Linear codes, distance bounds..
Mathematics Subject Classification: Primary: 94B05, 05C10; Secondary: 94B6.
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

[1]

San Ling, Buket Özkaya. New bounds on the minimum distance of cyclic codes. Advances in Mathematics of Communications, 2021, 15 (1) : 1-8. doi: 10.3934/amc.2020038
[2]

Vito Napolitano, Ferdinando Zullo. Codes with few weights arising from linear sets. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020129
[3]

Dandan Wang, Xiwang Cao, Gaojun Luo. A class of linear codes and their complete weight enumerators. Advances in Mathematics of Communications, 2021, 15 (1) : 73-97. doi: 10.3934/amc.2020044
[4]

Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045
[5]

Jong Yoon Hyun, Boran Kim, Minwon Na. Construction of minimal linear codes from multi-variable functions. Advances in Mathematics of Communications, 2021, 15 (2) : 227-240. doi: 10.3934/amc.2020055
[6]

Fengwei Li, Qin Yue, Xiaoming Sun. The values of two classes of Gaussian periods in index 2 case and weight distributions of linear codes. Advances in Mathematics of Communications, 2021, 15 (1) : 131-153. doi: 10.3934/amc.2020049
[7]

Hongming Ru, Chunming Tang, Yanfeng Qi, Yuxiao Deng. A construction of $ p $-ary linear codes with two or three weights. Advances in Mathematics of Communications, 2021, 15 (1) : 9-22. doi: 10.3934/amc.2020039
[8]

Darko Dimitrov, Hosam Abdo. Tight independent set neighborhood union condition for fractional critical deleted graphs and ID deleted graphs. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 711-721. doi: 10.3934/dcdss.2019045
[9]

Hua Shi, Xiang Zhang, Yuyan Zhang. Complex planar Hamiltonian systems: Linearization and dynamics. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020406
[10]

Soonki Hong, Seonhee Lim. Martin boundary of brownian motion on Gromov hyperbolic metric graphs. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021014
[11]

Alessandro Fonda, Rodica Toader. A dynamical approach to lower and upper solutions for planar systems "To the memory of Massimo Tarallo". Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021012
[12]

Zhiyan Ding, Qin Li, Jianfeng Lu. Ensemble Kalman Inversion for nonlinear problems: Weights, consistency, and variance bounds. Foundations of Data Science, 2020  doi: 10.3934/fods.2020018
[13]

Ching-Hui Wang, Sheng-Chen Fu. Traveling wave solutions to diffusive Holling-Tanner predator-prey models. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2021007
[14]

Claudio Arancibia-Ibarra, José Flores, Michael Bode, Graeme Pettet, Peter van Heijster. A modified May–Holling–Tanner predator-prey model with multiple Allee effects on the prey and an alternative food source for the predator. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 943-962. doi: 10.3934/dcdsb.2020148
[15]

Jianfeng Huang, Haihua Liang. Limit cycles of planar system defined by the sum of two quasi-homogeneous vector fields. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 861-873. doi: 10.3934/dcdsb.2020145
[16]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117
[17]

Shahede Omidi, Jafar Fathali. Inverse single facility location problem on a tree with balancing on the distance of server to clients. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021017
[18]

Klemens Fellner, Jeff Morgan, Bao Quoc Tang. Uniform-in-time bounds for quadratic reaction-diffusion systems with mass dissipation in higher dimensions. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 635-651. doi: 10.3934/dcdss.2020334
[19]

Xiangrui Meng, Jian Gao. Complete weight enumerator of torsion codes. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020124
[20]

Cheng Peng, Zhaohui Tang, Weihua Gui, Qing Chen, Jing He. A bidirectional weighted boundary distance algorithm for time series similarity computation based on optimized sliding window size. Journal of Industrial & Management Optimization, 2021, 17 (1) : 205-220. doi: 10.3934/jimo.2019107

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (63)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences