SpringerLink
Log in

Some “goodness” properties of LDA lattices

  • Information Theory
  • Published:
Problems of Information Transmission Aims and scope Submit manuscript

Abstract

We study some structural properties of Construction-A lattices obtained from low density parity check codes over prime fields. Such lattices are called low density Construction-A (LDA) lattices, and permit low-complexity belief propagation decoding for transmission over Gaussian channels. It has been shown that LDA lattices achieve the capacity of the power constrained additive white Gaussian noise (AWGN) channel with closest lattice-point decoding, and simulations suggested that they perform well under belief propagation decoding. We continue this line of work and prove that these lattices are good for packing and mean squared error quantization and that their duals are good for packing. With this, we can conclude that codes constructed using nested LDA lattices can achieve the capacity of the power constrained AWGN channel, the capacity of the dirty paper channel, the rates guaranteed by the computeand-forward protocol, and the best known rates for bidirectional relaying with perfect secrecy.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Erez, U. and Zamir, R., Achieving 1/2 log(1+SNR) on the AWGN Channel with Lattice Encoding and Decoding, IEEE Trans. Inform. Theory, 2004, vol. 50, no. 10, pp. 2293–2314.

    Article  MathSciNet  MATH  Google Scholar 

  2. Erez, U., Shamai, S., and Zamir, R., Capacity and Lattice Strategies for Canceling Known Interference, IEEE Trans. Inform. Theory, 2005, vol. 51, no. 11, pp. 3820–3833.

    Article  MathSciNet  MATH  Google Scholar 

  3. Bresler, G., Parekh, A., and Tse, D.N.C., The Approximate Capacity of the Many-to-One and One-to-Many Gaussian Interference Channels, IEEE Trans. Inform. Theory, 2010, vol. 56, no. 9, pp. 4566–4592.

    Article  MathSciNet  Google Scholar 

  4. Jafar, S.A. and Vishwanath, S., Generalized Degrees of Freedom of the Symmetric Gaussian K User Interference Channel, IEEE Trans. Inform. Theory, 2010, vol. 56, no. 7, pp. 3297–3303.

    Article  MathSciNet  Google Scholar 

  5. Wilson, M.P., Narayanan, K., Pfister, H.D., and Sprintson, A., Joint Physical Layer Coding and Network Coding for Bidirectional Relaying, IEEE Trans. Inform. Theory, 2010, vol. 56, no. 11, pp. 5641–5654.

    Article  MathSciNet  Google Scholar 

  6. Nazer, B. and Gastpar, M., Compute-and-Forward: Harnessing Interference through Structured Codes, IEEE Trans. Inform. Theory, 2011, vol. 57, no. 10, pp. 6463–6486.

    Article  MathSciNet  Google Scholar 

  7. Baik, I.-J. and Chung, S.-Y., Network Coding for Two-Way Relay Channels Using Lattices, in Proc. IEEE Int. Conf. on Communications (ICC’08), Bei**g, China, May 19–23, 2008, pp. 3898–3902.

    Google Scholar 

  8. Belfiore, J.-C. and Oggier, F., Secrecy Gain: A Wiretap Lattice Code Design, in Proc. 2010 Int. Sympos. on Information Theory and Its Applications (ISITA’2010), Taichung, Taiwan, Oct. 17–20, 2010, pp. 174–178.

    Chapter  Google Scholar 

  9. Ling, C., Luzzi, L., Belfiore, J.-C., and Stehlé, D., Semantically Secure Lattice Codes for the Gaussian Wiretap Channel, IEEE Trans. Inform. Theory, 2014, vol. 60, no. 10, pp. 6399–6416.

    Article  MathSciNet  Google Scholar 

  10. He, X. and Yener, A., Strong Secrecy and Reliable Byzantine Detection in the Presence of an Untrusted Relay, IEEE Trans. Inform. Theory, 2013, vol. 59, no. 1, pp. 177–192.

    Article  MathSciNet  Google Scholar 

  11. Vatedka, S., Kashyap, N., and Thangaraj, A., Secure Compute-and-Forward in a Bidirectional Relay, IEEE Trans. Inform. Theory, 2015, vol. 61, no. 5, pp. 2531–2556.

    Article  MathSciNet  Google Scholar 

  12. Zamir, R., Lattice Coding for Signals and Networks: A Structured Coding Approach to Quantization, Modulation, and Multi-User Information Theory, Cambridge: Cambridge Univ. Press, 2014.

    Book  MATH  Google Scholar 

  13. Poltyrev, G., On Coding without Restrictions for the AWGN Channel, IEEE Trans. Inform. Theory, 1994, vol. 40, no. 2, pp. 409–417.

    Article  MathSciNet  MATH  Google Scholar 

  14. Conway, J.H. and Sloane, N.J.A., Sphere Packings, Lattices, and Groups, New York: Springer-Verlag, 1988.

    Book  MATH  Google Scholar 

  15. Erez, U., Litsyn, S., and Zamir, R., Lattices Which Are Good for (Almost) Everything, IEEE Trans. Inform. Theory, 2005, vol. 51, no. 10, pp. 3401–3416.

    Article  MathSciNet  MATH  Google Scholar 

  16. di Pietro, N., Boutros, J.J., Zémor, G., and Brunel, L., Integer Low-Density Lattices Based on Construction A, in Proc. 2012 IEEE Information Theory Workshop (ITW’2012), Lausanne, Switzerland, Sept. 3–7, 2012, pp. 422–426.

    Chapter  Google Scholar 

  17. di Pietro, N., On Infinite and Finite Lattice Constellations for the Additive White Gaussian Noise Channel, PhD Thesis, Inst. Math. Bordeaux, Univ. Bordeaux, Bordeaux, France, 2014. Available at https://tel.archives-ouvertes.fr/tel-01135575/document.

    Google Scholar 

  18. Tunali, N.E., Narayanan, K.R., and Pfister, H.D., Spatially-Coupled Low Density Lattices Based on Construction A with Applications to Compute-and-Forward, in Proc. 2013 IEEE Information Theory Workshop (ITW’2013), Sevilla, Spain, Sept. 9–13, 2013, pp. 1–5.

    Chapter  Google Scholar 

  19. di Pietro, N., Boutros, J.J., Zémor, G., and Brunel, L., New Results on Low-Density Integer Lattices, in Proc. 2013 Information Theory and Applications Workshop (ITA’2013), San Diego, CA, Feb. 10–15, 2013, pp. 39–44.

    Google Scholar 

  20. di Pietro, N., Zémor, G., and Boutros, J.J., LDA Lattices without Dithering Achieve Capacity on the Gaussian Channel, ar**v:1603.02863 [cs.IT], 2016.

    Google Scholar 

  21. Sommer, N., Feder, M., and Shalvi, O., Low-Density Lattice Codes, IEEE Trans. Inform. Theory, 2008, vol. 54, no. 4, pp. 1561–1585.

    Article  MathSciNet  MATH  Google Scholar 

  22. Yan, Y., Ling, C., and Wu, X., Polar Lattices: Where Arikan Meets Forney, in Proc. 2013 IEEE Int. Sympos. on Information Theory (ISIT’2013), Istanbul, Turkey, July 7–12, 2013, pp. 1292–1296.

    Chapter  Google Scholar 

  23. Minkowski, H., Gesammelte Abhandlungen, vol. 2, Leipzig: B.G. Teubner, 1911.

    MATH  Google Scholar 

  24. Hlawka, E., Zur Geometrie der Zahlen, Math. Z., 1943, vol. 49, pp. 285–312.

    Article  MathSciNet  MATH  Google Scholar 

  25. Rogers, C.A., Packing and Covering, Cambridge: Cambridge Univ. Press, 1964.

    MATH  Google Scholar 

  26. Ordentlich, O. and Erez, U., A Simple Proof for the Existence of “Good” Pairs of Nested Lattices, IEEE Trans. Inform. Theory, 2016, vol. 62, no. 8, pp. 4439–4453.

    Article  MathSciNet  Google Scholar 

  27. Richardson, T. and Urbanke, R., Modern Coding Theory, Cambridge: Cambridge Univ. Press, 2008.

    Book  MATH  Google Scholar 

  28. Bassalygo, L.A. and Pinsker, M.S., Complexity of an Optimum Nonblocking Switching Network without Reconnections, Probl. Peredachi Inf., 1973, vol. 9, no. 1, pp. 84–87 [Probl. Inf. Trans. (Engl. Transl.), 1973, vol. 9, no. 1, pp. 64–66].

    Google Scholar 

  29. Bassalygo, L.A., Asymptotically Optimal Switching Circuits, Probl. Peredachi Inf., 1981, vol. 17, no. 3, pp. 81–88 [Probl. Inf. Trans. (Engl. Transl.), 1981, vol. 17, no. 3, pp. 206–211].

    MathSciNet  MATH  Google Scholar 

  30. Sipser, M. and Spielman, D.A., Expander Codes, IEEE Trans. Inform. Theory, 1996, vol. 42, no. 6, part 1, pp. 1710–1722.

    Article  MathSciNet  MATH  Google Scholar 

  31. Hoory, S., Linial, N., and Wigderson, A., Expander Graphs and Their Applications, Bull. Amer. Math. Soc. (N.S.), 2006, vol. 43, no. 4, pp. 439–561.

    Article  MathSciNet  MATH  Google Scholar 

  32. di Pietro, N., Zémor, G., and Boutros, J.J., New Results on Construction A Lattices Based on Very Sparse Parity-Check Matrices, in Proc. 2013 IEEE Int. Sympos. on Information Theory (ISIT’2013), Istanbul, Turkey, July 7–12, 2013, pp. 1675–1679.

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Electrical Communication Engineering, Indian Institute of Science, Bengaluru, India

    S. Vatedka & N. Kashyap

Authors
  1. S. Vatedka
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. N. Kashyap
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to S. Vatedka.

Additional information

Original Russian Text © S. Vatedka, N. Kashyap, 2017, published in Problemy Peredachi Informatsii, 2017, Vol. 53, No. 1, pp. 3–33.

This work was presented in part at the 2015 IEEE Information Theory Workshop at Jerusalem, Israel.

Supported in part by the Tata Consultancy Services Research Scholarship Program.

Supported in part by a Swarnajayanti fellowship awarded by the Department of Science and Technology, India

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Vatedka, S., Kashyap, N. Some “goodness” properties of LDA lattices. Probl Inf Transm 53, 1–29 (2017). https://doi.org/10.1134/S003294601701001X

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1134/S003294601701001X

Search

Navigation