On cycle-free lattices with high rate label codes

Amin Sakzad; Mohammad-Reza Sadeghi

doi:10.3934/amc.2010.4.441

Article Contents

2010, Volume 4, Issue 4: 441-452. Doi: 10.3934/amc.2010.4.441

This issue Previous Article Next Article On the generic construction of identity-based signatures with additional properties

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

Received: October 2009

Revised: June 2010

Published: November 2010

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 11H31, 94B75; Secondary: 11H71.

Citation:

Related Papers

Cited by

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.
[2]	R. de Buda, Some optimal codes have structre, IEEE Trans. Information Theory, 7 (1989), 893-899.
[3]	Y.-S. Choi, I.-J. Baik and S.-Y. Chung, Iterative decoding for low-density parity-check lattices, ICACT, (2008), 358-361.
[4]	J. H. Conway and N. J. A. Sloane, "Sphere Packing, Lattices and Groups," 3^rd edition, Springer-Verlag, New York, 1998.
[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.
[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.
[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.
[8]	R. G. Gallager, Low-density parity-check codes, Ire Trans. Information Theory, IT-8 (1962), 21-28.doi: 10.1109/TIT.1962.1057683.
[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.
[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.
[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.
[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.
[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.
[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.
[15]	N. Wiberg, "Codes and Decoding on General Graphs," Ph.D thesis, Univ. Linköping, Linköping, Sweden, 1996.