Quantum Computation and Information Seminar 

02/03/2012, 15:00 — 16:00 — Room P4.35, Mathematics Building
Francisco Monteiro, IT & ISCTE-IUL

The closest vector problem in multi-dimensional wireless channels

This talk provides an overview of one of the central problems in communication engineering in the last 10 years, whose solution allows us now to reach the 1 Gbps frontier in wireless systems such as LTE Advanced and WiMax. The capacity limits set by Shannon in 1948 for digital transmission were reached in 1993 and 1995 after the discovery of turbo-codes and low-density parity-check codes. While this put an end to an era in coding theory, a new door was opened in the late 90s for wireless channels: multiple-input multiple output (MIMO). It was soon mathematically proved that increasing the number of antennas both at the transmitter and at the receiver would increase the capacity of the radio link. However, this gain comes at the expense of a much higher algorithmic complexity at the receiver side. The mathematical underlying detection problem is the closest vector problem (CVP) in a lattice. The problem had been mostly investigated in algorithmic number theory and much of the progress made in signal processing in communications came in fact from the re-discovery of algorithms known in the communities of algorithmic number theory and cryptography. The talk will describe several approximate and exact solutions to CVP, emphasising the geometric manipulation of lattices that is carried out by the most relevant algorithms: maximum likelihood detection, zero-forcing, minimum mean square error, successive detection, sphere decoding and lattice reduction. A novel approach to the problem will also be presented, which maps the problem onto a graph-based path minimisation problem.