Asea Brown Boveri Ltd. Award (ABB) 2010 - Korada Satish Babu

"Pour sa contribution dans le domaine des algorithmes à faible complexité appliqués aux problèmes de transmission et de compression de données."

Polar codes for channel and source coding.

Coding is an indispensable part of modern day digital technology.
Applications include mobile communication, MP3 players, CDs, and the Internet. The two most important applications of coding are:
(i) protect data from errors (communication), (ii) compress data (compression). Shannon, in his seminal work, formalized both these problems and determined their fundamental limits. Since then a driving force has been to realize these fundamental limits under complexity constraints. This is also the main focus of this thesis.

In particular I consider the lossy data compression problem. Here, the task is to compress data while minimizing the created distortion.
Dating back to the work of Shannon, it is known that for a given distortion requirement there is a limit on the maximum compression that can be achieved. This is known as the rate-distortion tradeoff.
Achieving this trade-off with "low complexity" schemes has been a long-standing open problem. We solve this problem for a large class of data sources using the concept of "polar codes", recently introduced by Arikan. Other scenarios considered in the thesis include the Wyner-Ziv problem (which one can think of a simple model of compression of video) and the Gelfand-Pinsker problem (similar to watermarking). For each of these problems, our constructions are the first low-complexity schemes that approach the optimal performance.