Emanuele Viterbo: Computational methods for analysis and design of lattice constellations
Ph. D. thesis, Department of Electrical Engineering, Politecnico of Torino, Torino, Italy, 1995. Advisor: Ezio Biglieri

viterbo@polito.it

Submission: 2000, Mar. 08

The interest for multidimensional lattice constellations for transmission over the Gaussian channel dates back to the beginning of the Eighties, although lattice theory is part of some classical branches of mathematics such as geometry of numbers and algebraic number theory. In this thesis we have explored some of these domains with the aim of finding some new computational techniques for decoding, analysis and design of lattice constellations for both the Gaussian and Rayleigh fading channel. The main results of this work may be summarized as follows.

a) Decoding a $d$-dimensional lattice consists of finding the lattice point closest to any given vector ${\bf z}$ in the Euclidean space ${\bf R}^d$. Decoding algorithms find applications in vector quantization and in demodulation of multidimensional signal constellations. We describe an algorithm that solves the decoding problem for any lattice, irrespective of its particular algebraic structure. This algorithm is also modified to enable maximum-likelihood decoding of lattice codes when used for transmission over a fading channel.

b) Numerical evaluation of some typical lattice parameters such as density, thickness, dimensionless second moment (quantizing constant) etc., is 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. A general algorithm has been developed 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 bound for the error probability of a lattice constellation used for transmission over the additive white Gaussian noise channel.

c) Recent work on lattices matched to the Rayleigh fading channel has shown the way to construct good signal constellations with high spectral efficiency. We present a new family of lattice constellations, based on complex algebraic number fields, which have good performance on Rayleigh fading channels. Some of these lattices also exhibit a reasonable packing density and thus may be used at the same time over a Gaussian channel. Conversely, we show that particular versions of the best lattice packings ($D_4,E_6,E_8,K_{12},\Lambda_{16},\Lambda_{24}$), constructed from totally complex algebraic cyclotomic fields, exhibit better performance over the Rayleigh fading channel. The practical interest in such signal contellations rises from the need to transmit information at high rates over both terrestrial and satellite links.

Parts of the thesis resulted in the following publications: - J. Boutros, E. Viterbo, C. Rastello, and J.C. Belfiore: "Good Lattice Constellations for both Rayleigh Fading and Gaussian Channels", IEEE Transactions on Information Theory, vol. 42, n. 2, pp. 502-518, Mar. 1996. - E. Viterbo and E. Biglieri: "Computing the Voronoi cell of a lattice: The diamond-cutting algorithm", IEEE Transactions on Information Theory, vol. 42, n. 1, pp. 161-171, Jan. 1996. For more information please contact the author at Dipartimento di Elettronica, Politecnico di Torino, C. Duca degli Abruzzi 24, I-10129 Torino, Italy.

Keywords and Phrases: broad: digital transmission, coding and modulation, fading channel, lattices specific: diversity, number fields, QAM modulation, Rayleigh fading, field embeddings, product distance

Full text: Abstract 4 k, ps.gz 792 k, pdf.gz 984 k, pdf 3395 k