American Institute of Mathematical Sciences

Advanced
November  2010, 4(4): 441-452. doi: 10.3934/amc.2010.4.441

On cycle-free lattices with high rate label codes

Amin Sakzad 1, and  Mohammad-Reza Sadeghi 1,

1. 

Department of Mathematics and Computer Science, Amirkabir University of Technology, No. 424, Hafez Avenue, Tehran 15914, Iran, Iran

Received  October 2009 Revised  June 2010 Published  November 2010

Etzion et al. have shown that high rate codes based on cycle-free Tanner graphs have minimum distance at most $2$. This result was extended by Sadeghi et al. to a small class of lattices based on Construction $D'$ only. In this paper, we prove a key theorem which relates the minimum distance of every lattice to the minimum distance of its label code. Then, using this powerful tool along with some new bounds on minimum distance of cycle-free group codes, we generalize those results to a large class of lattices here called RPS and PFP lattices. More importantly, we show that this class of cycle-free lattices are not so good in the view of coding gain.
Keywords: group code, Tanner graph, label code., Lattice.
Mathematics Subject Classification: Primary: 11H31, 94B75; Secondary: 11H7.
Citation: Amin Sakzad, Mohammad-Reza Sadeghi. On cycle-free lattices with high rate label codes. Advances in Mathematics of Communications, 2010, 4 (4) : 441-452. doi: 10.3934/amc.2010.4.441
References:
[1]

A. H. Banihashemi and F. R. Kschischang, Tanner graphs for block codes and lattices: construction and complexity, IEEE Trans. Information Theory, 47 (2001), 822-834. doi: 10.1109/18.910592.  Google Scholar

[2]

R. de Buda, Some optimal codes have structre, IEEE Trans. Information Theory, 7 (1989), 893-899. Google Scholar

[3]

Y.-S. Choi, I.-J. Baik and S.-Y. Chung, Iterative decoding for low-density parity-check lattices, ICACT, (2008), 358-361. Google Scholar

[4]

J. H. Conway and N. J. A. Sloane, "Sphere Packing, Lattices and Groups," 3rd edition, Springer-Verlag, New York, 1998.  Google Scholar

[5]

T. Etzion, A. Trachtenberg and A. Vardy, Which codes have cycle-free Tanner graphs?, IEEE Trans. Information Theory, 45 (1999), 2173-2181. doi: 10.1109/18.782170.  Google Scholar

[6]

G. D. Forney, Jr., Density/length profiles and trellis complexity of lattices, IEEE Trans. Information Theory, 40 (1994), 1753-1774. doi: 10.1109/18.340453.  Google Scholar

[7]

G. D. Forney, Jr., M. D. Trott and S. Chung, Sphere-bound-achieving coset codes and multilevel coset codes, IEEE Trans. Information Theory, 46 (2000), 820-850. doi: 10.1109/18.841165.  Google Scholar

[8]

R. G. Gallager, Low-density parity-check codes, Ire Trans. Information Theory, IT-8 (1962), 21-28. doi: 10.1109/TIT.1962.1057683.  Google Scholar

[9]

X.-Y. Hu, E. Eleftherou and D. M. Arnold, Regular and irregular progressive edge-growth Tanner graphs, IEEE Trans. Information Theory, 51 (2005), 386-398. doi: 10.1109/TIT.2004.839541.  Google Scholar

[10]

F. R. Kschischang, B. J. Frey and H. Loeliger, Factor graphs and the sum-product algorithm, IEEE Trans. Information Theory, 47 (2001), 498-519. doi: 10.1109/18.910572.  Google Scholar

[11]

M. R. Sadeghi, A. H. Banihashemi and D. Panario, Low-density parity-check lattices: construction and decoding complexity, IEEE Trans. Information Theory, 52 (2006), 4481-4495. doi: 10.1109/TIT.2006.881720.  Google Scholar

[12]

M. R. Sadeghi and D. Panario, Low density parity check lattices based on construction $D'$ and cycle-free Tanner graphs, Algebraic Coding Theory and Information Theory, AMS DIMACS, 28 (2005), 85-95.  Google Scholar

[13]

N. Sommer, M. Feder and O. Shalvi, Low-density lattice codes, IEEE Trans. Information Theory, 54 (2008), 1561-1586. doi: 10.1109/TIT.2008.917684.  Google Scholar

[14]

R. M. Tanner, A recursive approach to low-complexity codes, IEEE Trans. Information Theory, 27 (1981), 533-547. doi: 10.1109/TIT.1981.1056404.  Google Scholar

[15]

N. Wiberg, "Codes and Decoding on General Graphs," Ph.D thesis, Univ. Linköping, Linköping, Sweden, 1996. Google Scholar

show all references

References:
[1]

A. H. Banihashemi and F. R. Kschischang, Tanner graphs for block codes and lattices: construction and complexity, IEEE Trans. Information Theory, 47 (2001), 822-834. doi: 10.1109/18.910592.  Google Scholar

[2]

R. de Buda, Some optimal codes have structre, IEEE Trans. Information Theory, 7 (1989), 893-899. Google Scholar

[3]

Y.-S. Choi, I.-J. Baik and S.-Y. Chung, Iterative decoding for low-density parity-check lattices, ICACT, (2008), 358-361. Google Scholar

[4]

J. H. Conway and N. J. A. Sloane, "Sphere Packing, Lattices and Groups," 3rd edition, Springer-Verlag, New York, 1998.  Google Scholar

[5]

T. Etzion, A. Trachtenberg and A. Vardy, Which codes have cycle-free Tanner graphs?, IEEE Trans. Information Theory, 45 (1999), 2173-2181. doi: 10.1109/18.782170.  Google Scholar

[6]

G. D. Forney, Jr., Density/length profiles and trellis complexity of lattices, IEEE Trans. Information Theory, 40 (1994), 1753-1774. doi: 10.1109/18.340453.  Google Scholar

[7]

G. D. Forney, Jr., M. D. Trott and S. Chung, Sphere-bound-achieving coset codes and multilevel coset codes, IEEE Trans. Information Theory, 46 (2000), 820-850. doi: 10.1109/18.841165.  Google Scholar

[8]

R. G. Gallager, Low-density parity-check codes, Ire Trans. Information Theory, IT-8 (1962), 21-28. doi: 10.1109/TIT.1962.1057683.  Google Scholar

[9]

X.-Y. Hu, E. Eleftherou and D. M. Arnold, Regular and irregular progressive edge-growth Tanner graphs, IEEE Trans. Information Theory, 51 (2005), 386-398. doi: 10.1109/TIT.2004.839541.  Google Scholar

[10]

F. R. Kschischang, B. J. Frey and H. Loeliger, Factor graphs and the sum-product algorithm, IEEE Trans. Information Theory, 47 (2001), 498-519. doi: 10.1109/18.910572.  Google Scholar

[11]

M. R. Sadeghi, A. H. Banihashemi and D. Panario, Low-density parity-check lattices: construction and decoding complexity, IEEE Trans. Information Theory, 52 (2006), 4481-4495. doi: 10.1109/TIT.2006.881720.  Google Scholar

[12]

M. R. Sadeghi and D. Panario, Low density parity check lattices based on construction $D'$ and cycle-free Tanner graphs, Algebraic Coding Theory and Information Theory, AMS DIMACS, 28 (2005), 85-95.  Google Scholar

[13]

N. Sommer, M. Feder and O. Shalvi, Low-density lattice codes, IEEE Trans. Information Theory, 54 (2008), 1561-1586. doi: 10.1109/TIT.2008.917684.  Google Scholar

[14]

R. M. Tanner, A recursive approach to low-complexity codes, IEEE Trans. Information Theory, 27 (1981), 533-547. doi: 10.1109/TIT.1981.1056404.  Google Scholar

[15]

N. Wiberg, "Codes and Decoding on General Graphs," Ph.D thesis, Univ. Linköping, Linköping, Sweden, 1996. Google Scholar

[1]

María Chara, Ricardo A. Podestá, Ricardo Toledano. The conorm code of an AG-code. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021018
[2]

Jorge P. Arpasi. On the non-Abelian group code capacity of memoryless channels. Advances in Mathematics of Communications, 2020, 14 (3) : 423-436. doi: 10.3934/amc.2020058
[3]

Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1
[4]

Irene Márquez-Corbella, Edgar Martínez-Moro, Emilio Suárez-Canedo. On the ideal associated to a linear code. Advances in Mathematics of Communications, 2016, 10 (2) : 229-254. doi: 10.3934/amc.2016003
[5]

Serhii Dyshko. On extendability of additive code isometries. Advances in Mathematics of Communications, 2016, 10 (1) : 45-52. doi: 10.3934/amc.2016.10.45
[6]

Olof Heden. The partial order of perfect codes associated to a perfect code. Advances in Mathematics of Communications, 2007, 1 (4) : 399-412. doi: 10.3934/amc.2007.1.399
[7]

Sascha Kurz. The $[46, 9, 20]_2$ code is unique. Advances in Mathematics of Communications, 2021, 15 (3) : 415-422. doi: 10.3934/amc.2020074
[8]

Selim Esedoḡlu, Fadil Santosa. Error estimates for a bar code reconstruction method. Discrete & Continuous Dynamical Systems - B, 2012, 17 (6) : 1889-1902. doi: 10.3934/dcdsb.2012.17.1889
[9]

Martino Borello, Francesca Dalla Volta, Gabriele Nebe. The automorphism group of a self-dual $[72,36,16]$ code does not contain $\mathcal S_3$, $\mathcal A_4$ or $D_8$. Advances in Mathematics of Communications, 2013, 7 (4) : 503-510. doi: 10.3934/amc.2013.7.503
[10]

M. Delgado Pineda, E. A. Galperin, P. Jiménez Guerra. MAPLE code of the cubic algorithm for multiobjective optimization with box constraints. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407
[11]

Andrew Klapper, Andrew Mertz. The two covering radius of the two error correcting BCH code. Advances in Mathematics of Communications, 2009, 3 (1) : 83-95. doi: 10.3934/amc.2009.3.83
[12]

Masaaki Harada, Takuji Nishimura. An extremal singly even self-dual code of length 88. Advances in Mathematics of Communications, 2007, 1 (2) : 261-267. doi: 10.3934/amc.2007.1.261
[13]

José Gómez-Torrecillas, F. J. Lobillo, Gabriel Navarro. Information--bit error rate and false positives in an MDS code. Advances in Mathematics of Communications, 2015, 9 (2) : 149-168. doi: 10.3934/amc.2015.9.149
[14]

M. De Boeck, P. Vandendriessche. On the dual code of points and generators on the Hermitian variety $\mathcal{H}(2n+1,q^{2})$. Advances in Mathematics of Communications, 2014, 8 (3) : 281-296. doi: 10.3934/amc.2014.8.281
[15]

Sihuang Hu, Gabriele Nebe. There is no $[24,12,9]$ doubly-even self-dual code over $\mathbb F_4$. Advances in Mathematics of Communications, 2016, 10 (3) : 583-588. doi: 10.3934/amc.2016027
[16]

Michael Kiermaier, Johannes Zwanzger. A $\mathbb Z$4-linear code of high minimum Lee distance derived from a hyperoval. Advances in Mathematics of Communications, 2011, 5 (2) : 275-286. doi: 10.3934/amc.2011.5.275
[17]

Anna-Lena Horlemann-Trautmann, Kyle Marshall. New criteria for MRD and Gabidulin codes and some Rank-Metric code constructions. Advances in Mathematics of Communications, 2017, 11 (3) : 533-548. doi: 10.3934/amc.2017042
[18]

Masaaki Harada, Ethan Novak, Vladimir D. Tonchev. The weight distribution of the self-dual $[128,64]$ polarity design code. Advances in Mathematics of Communications, 2016, 10 (3) : 643-648. doi: 10.3934/amc.2016032
[19]

Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2021, 15 (1) : 113-130. doi: 10.3934/amc.2020046
[20]

Terry Shue Chien Lau, Chik How Tan. Polynomial-time plaintext recovery attacks on the IKKR code-based cryptosystems. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020132

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (87)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences