Théorème du codage de source

Le théorème du codage de source (ou premier théorème de Shannon, ou encore théorème de codage sans bruit) est un théorème en théorie de l'information, énoncé par Claude Shannon en 1948, qui énonce la limite théorique pour la compression d'une source. Le théorème montre que l'on ne peut pas compresser une chaine de variables aléatoires i.i.d, quand la longueur de celle-ci tend vers l'infini, de telle sorte à ce que la longueur moyenne des codes des variables soit inférieure à l'entropie de la variable source. Cependant, on peut avoir une compression avec une longueur moyenne de code arbitrairement proche de l'entropie lorsque la longueur de la chaîne tend vers l'infini. Soit une variable aléatoire , posons la suite de variables aléatoires i.i.d de loi et en notant la longueur minimale d'un code pour à erreur de probabilité au plus . Le théorème énonce que , c'est-à-dire, lorsque tend vers l'infini, que ne peut être compressée en moins de bits sans perte d'information presque certaine. On peut en revanche trouver un code à probabilité d'erreur négligeable approchant cette borne d'arbitrairement près. On considère une suite de symboles provenant d'une source -aire stationnaire (suite de variables i.i.d), le théorème se simplifie en: avec la longueur d'un code optimal pour . Soit donc une variable aléatoire, notons la suite de réalisations différentes de ( suivent la même loi que et sont indépendantes). Le théorème affirme que , encadrons donc cette limite par deux inégalités. Pour et , on définit un ensemble de réalisations typiques de ainsi : . On a alors, avec et l'entropie : Puisque , la loi faible des grands nombres nous assure . Pour assez grand, et comme on peut coder cet ensemble avec moins de bits. Ainsi pour tout et correspondant assez grand, donc . Pour , soit tel que , posons et tels que de cette façon : Maintenant, Le premier terme tendant vers 0, et par la loi faible des grands nombres le second aussi, on a donc donc la probabilité de pouvoir encoder avec caractères ou moins tend vers 0.

Performance of Polar Codes for Channel and Source Coding

Rüdiger Urbanke, Satish Babu Korada, Nadine Hussami

Polar codes, introduced recently by Arikan, are the first family of codes known to achieve capacity of symmetric channels using a low complexity successive cancellation decoder. Although these codes, combined with successive cancellation, are optimal in this respect, their finite-length performance is not record breaking. We discuss several techniques through which their finite-length performance can be improved. We also study the performance of these codes in the context of source coding, both lossless and lossy, in the single-user context as well as for distributed applications.

2009

Delay and coding in multiple-user communications

Stéphane Musy

In multiple-user communications, the bursty nature of the packet arrival times cannot be divorced from the analysis of the transmission process. However, in traditional information theory the random arrival times are smoothed out by appropriated source coding and no consideration is made for the end-to-end delay. In this thesis, using tools from network theory, we investigate simple models that consider the end-to-end delay and/or the variability of the packet arrivals as important parameters, while staying in a information theoretic framework. First, we simplify the problem and focus on the transmission of a bursty source over a single-user channel. We introduce a new measure of channel features that enable us to incorporate the possibility to code among several packets in a scheduling problem. In this setup, we look for policies that minimize the average packet delay. Assuming that the packets are independent and sufficiently large to perform capacity achieving coding, we then consider the problem of allocating rates among a finite number of users communicating through a multiple-user channel. Following the previous work in the context of multiple-access channel, we formulate a scheduling problem in which the rate of each user is chosen from the capacity region of the multiple-user channel. Here, the goal is to find a scheduling policy that minimizes the sum of the transmitter queue lengths, such a policy is called delay optimal. In particular settings, for the additive Gaussian multiple-access channel we show the delay optimality of the Longer Queue Higher Rate policy introduced by Yeh. And, when the users communicate through a symmetric broadcast channel, we propose and show the delay optimality of a Best User Highest Possible Rate policy, among a large class of admissible policies. Finally, in the last part of this thesis, we look at the multiple-user channel coding problem from the perspective of the receivers. By measuring the transmission rates at the receivers, we are able to define variable length codes and to characterize the region of achievable rates when the receivers can decode their intended messages at different instants of time. For the two-user degraded broadcast channel and for the two-user multiple-access channel, we show that the gain in using variable length codes essentially comes from the possibility for the receivers to decode the transmitted messages in non-overlapping periods of time.

EPFL2007

Delay and coding in multiple-user communications

Stéphane Musy

EPFL2007