Computing the Voronoi Cell of a Lattice: The Diamond-Cutting Algorithm

Emanuele Viterbo, Ezio Biglieri

Research output: Contribution to journalArticleResearchpeer-review

32 Citations (Scopus)

Abstract

Numerical evaluation of some typical lattice parameters such as density, thickness, dimensionless second moment (quantizing constant), etc., are considered. Computational complexity grows exponentially with the dimension of the lattices and all known results rely on the very regular structure of some of these. In this paper we present a general algorithm which enables computation of all the common parameters for any given lattice by means of a complete description of its Voronoi cell. Using this algorithm, we have computed previously unknown values of the quantizing constants of some particularly interesting lattices. These results can be used to evaluate the performance of lattice quantizers and lattice signal constellations for the Gaussian channel. As an application we evaluate a tight upper hound for the error probability of a lattice constellation used for transmission over the additive white Gaussian noise channel.

Original languageEnglish
Pages (from-to)161-171
Number of pages11
JournalIEEE Transactions on Information Theory
Volume42
Issue number1
DOIs
Publication statusPublished - 1 Dec 1996
Externally publishedYes

Keywords

  • Computational geometry
  • Covering
  • Error probability
  • Lattice
  • Lattice constellation
  • Packing
  • Quantization
  • Quantizing constant
  • Voronoi region

Cite this