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

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.