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), p. P11007. 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), p. P05003. 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-279. 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-2181. 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-1296.  Google Scholar

[7]

F. Harary, "Graph Theory,'' Addison-Wesley Publishers, 1969.  Google Scholar

[8]

N. Kashyap, Code decomposition: theory and applications, in "IEEE International Symposium on Information Theory,'' (2007), 481-485. 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-3058. doi: 10.1109/TIT.2008.924700.  Google Scholar

[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.  Google Scholar

[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. 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-1460. 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-124. 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), p. P11007. 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), p. P05003. 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-279. 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-2181. 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-1296.  Google Scholar

[7]

F. Harary, "Graph Theory,'' Addison-Wesley Publishers, 1969.  Google Scholar

[8]

N. Kashyap, Code decomposition: theory and applications, in "IEEE International Symposium on Information Theory,'' (2007), 481-485. 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-3058. doi: 10.1109/TIT.2008.924700.  Google Scholar

[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.  Google Scholar

[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. 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-1460. 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-124. 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]

Joaquim Borges, Josep Rifà, Victor A. Zinoviev. Families of nested completely regular codes and distance-regular graphs. Advances in Mathematics of Communications, 2015, 9 (2) : 233-246. doi: 10.3934/amc.2015.9.233
[3]

John Sheekey. A new family of linear maximum rank distance codes. Advances in Mathematics of Communications, 2016, 10 (3) : 475-488. doi: 10.3934/amc.2016019
[4]

Jean Creignou, Hervé Diet. Linear programming bounds for unitary codes. Advances in Mathematics of Communications, 2010, 4 (3) : 323-344. doi: 10.3934/amc.2010.4.323
[5]

Emmanuel Charbit, Irène Charon, Gérard Cohen, Olivier Hudry, Antoine Lobstein. Discriminating codes in bipartite graphs: bounds, extremal cardinalities, complexity. Advances in Mathematics of Communications, 2008, 2 (4) : 403-420. doi: 10.3934/amc.2008.2.403
[6]

Ali Tebbi, Terence Chan, Chi Wan Sung. Linear programming bounds for distributed storage codes. Advances in Mathematics of Communications, 2020, 14 (2) : 333-357. doi: 10.3934/amc.2020024
[7]

Idan Goldenberg, David Burshtein. Error bounds for repeat-accumulate codes decoded via linear programming. Advances in Mathematics of Communications, 2011, 5 (4) : 555-570. doi: 10.3934/amc.2011.5.555
[8]

Beniamin Mounits, Tuvi Etzion, Simon Litsyn. New upper bounds on codes via association schemes and linear programming. Advances in Mathematics of Communications, 2007, 1 (2) : 173-195. doi: 10.3934/amc.2007.1.173
[9]

Kamil Otal, Ferruh Özbudak. Explicit constructions of some non-Gabidulin linear maximum rank distance codes. Advances in Mathematics of Communications, 2016, 10 (3) : 589-600. doi: 10.3934/amc.2016028
[10]

Ferruh Özbudak, Patrick Solé. Gilbert-Varshamov type bounds for linear codes over finite chain rings. Advances in Mathematics of Communications, 2007, 1 (1) : 99-109. doi: 10.3934/amc.2007.1.99
[11]

Yujuan Li, Guizhen Zhu. On the error distance of extended Reed-Solomon codes. Advances in Mathematics of Communications, 2016, 10 (2) : 413-427. doi: 10.3934/amc.2016015
[12]

Carlos Munuera, Morgan Barbier. Wet paper codes and the dual distance in steganography. Advances in Mathematics of Communications, 2012, 6 (3) : 273-285. doi: 10.3934/amc.2012.6.273
[13]

Jinmei Fan, Yanhai Zhang. Optimal quinary negacyclic codes with minimum distance four. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021043
[14]

Dina Ghinelli, Jennifer D. Key. Codes from incidence matrices and line graphs of Paley graphs. Advances in Mathematics of Communications, 2011, 5 (1) : 93-108. doi: 10.3934/amc.2011.5.93
[15]

Carlos Munuera, Fernando Torres. A note on the order bound on the minimum distance of AG codes and acute semigroups. Advances in Mathematics of Communications, 2008, 2 (2) : 175-181. doi: 10.3934/amc.2008.2.175
[16]

Andries E. Brouwer, Tuvi Etzion. Some new distance-4 constant weight codes. Advances in Mathematics of Communications, 2011, 5 (3) : 417-424. doi: 10.3934/amc.2011.5.417
[17]

Diego Napp, Roxana Smarandache. Constructing strongly-MDS convolutional codes with maximum distance profile. Advances in Mathematics of Communications, 2016, 10 (2) : 275-290. doi: 10.3934/amc.2016005
[18]

Bram van Asch, Frans Martens. A note on the minimum Lee distance of certain self-dual modular codes. Advances in Mathematics of Communications, 2012, 6 (1) : 65-68. doi: 10.3934/amc.2012.6.65
[19]

José Joaquín Bernal, Diana H. Bueno-Carreño, Juan Jacobo Simón. Cyclic and BCH codes whose minimum distance equals their maximum BCH bound. Advances in Mathematics of Communications, 2016, 10 (2) : 459-474. doi: 10.3934/amc.2016018
[20]

Jong Yoon Hyun, Yoonjin Lee, Yansheng Wu. Connection of $ p $-ary $ t $-weight linear codes to Ramanujan Cayley graphs with $ t+1 $ eigenvalues. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020133

2020 Impact Factor: 0.935

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences