Théorème du codage de canal

En théorie de l'information, le théorème du codage de canal aussi appelé deuxième théorème de Shannon montre qu'il est possible de transmettre des données numériques sur un canal bruité avec un taux d'erreur arbitrairement faible si le débit est inférieur à une certaine limite propre au canal. Ce résultat publié par Claude Shannon en 1948 est fondé sur des travaux antérieurs de Harry Nyquist et Ralph Hartley. La première preuve rigoureuse fut établie par Amiel Feinstein en 1954. D'une importance fondamentale en théorie de l'information, il possède de larges applications dans les domaines des télécommunications et du stockage d'information.

Introduction

L'un des principaux avantages de la représentation numérique des données est de permettre la transmission d'information sans perte. Néanmoins, les données transitent la plupart du temps sur des canaux bruités non fiables subissant diverses interférences. Comment peut-on alors éliminer les erreurs de transmission ? Une solution générale consiste à introduire de la redondance dans le message émis par la source afin de pouvoir corriger les erreurs a posteriori. On parle d'encodage de voie par un code correcteur.

Le théorème montre que pour des sources dont le débit est plus faible qu'une certaine capacité liée au canal de transmission, il existe des codes tels que, au décodage, le taux d'erreur soit aussi faible que voulu.

Souvent, les symboles étant émis sur une durée fixe, on substitue l'entropie d'une source à son débit en bit/s. Il en est de même pour la capacité d'un canal qui peut-être un débit ou une information mutuelle (d'où une certaine confusion). Cette dernière est déterminée par les caractéristiques physiques du canal. Le théorème de Shannon-Hartley donne par exemple la capacité d'un canal à bande passante limitée subissant un bruit Gaussien (voir signal sur bruit).

Il est à noter que pour annuler le taux d'erreur, les diverses preuves font tendre la longueur des mots de code vers l'infini. Ainsi si le théorème permet de trouver de tels codes, il ne fournit pas d'algorithmes de décodage de complexité algorithmique satisfaisante. Aujourd'hui, les turbo codes convolutifs, les codes LDPC (Low-density parity-check) ou encore les codes polaires permettent de transmettre des signaux dont l'entropie approche la capacité du canal tout en restant décodables en temps réel^[1].

Théorème

En notant $p_{x}$ et $p_{y}$ les distributions marginales d'une distribution jointe $p$ , on note l'information mutuelle de $p$ ,

C_{p}=H(p_{x})+H(p_{y})-H(p)

où $H$ correspond a l'entropie.

Si on note $X^{n}$ et $Y^{n}$ des suites de $n$ variables aléatoires appariées issues de la distribution $p$ , alors étant données deux suites de fonctions $(e_{n})$ et $(d_{n})$ telles que,

\lim _{n\to \infty }P(e_{n}(X^{n})=d_{n}(Y^{n}))=1

en notant,

{\begin{aligned}H_{e,d}(p)&=\lim _{n\to \infty }{\frac {1}{n}}H(e_{n}(X^{n}))\\&=\lim _{n\to \infty }{\frac {1}{n}}H(d_{n}(Y^{n}))\end{aligned}}

on a l'égalité :

C_{p}=\max _{e,d}H_{e,d}(p)

Précisions

Ici la distribution jointe $p$ modélise le canal, $X$ représente ce que l'on cherche a transmettre et $Y$ ce qui est effectivement reçu en sortie du canal de communication. En général, on préfère modéliser le canal par la distribution conditionnelle $p_{y|x}$ de sorte que la capacité du canal s'exprime comme :

C(p_{y|x})=\max _{p_{x}}C_{p}

Enfin, pour des blocs de données $X^{n}$ (resp. $Y^{n}$ ) de longueur $n$ les fonctions $e_{n}$ (resp. $d_{n}$ ) constituent des encodeurs (resp. décodeurs) des messages transmis (resp. reçus).

Preuve

Notations utilisées

Soient $X$ et $Y$ deux variables aléatoires, suivant les probabilités conditionnelles, on a,

P(X,Y)=P(X)P(Y|X)

donc,

\log _{2}P(X,Y)=\log _{2}P(X)+\log _{2}P(Y|X)

et l’espérance étant linéaire,

\mathbb {E} \left[\log _{2}P(X,Y)\right]=\mathbb {E} \left[\log _{2}P(X)\right]+\mathbb {E} \left[\log _{2}P(Y|X)\right]

on notera,

H(XY)=H(X)+H(\pi _{X}(Y))

où $\pi _{X}(Y)$ peut être vue comme une variable aléatoire fonction de $Y$ dont la fonction dépend de la réalisation préalable de $X$ .

On remarque que $H(X)+H(Y)-H(XY)=D_{KL}(P(X,Y)\Vert P(X)\otimes P(Y))\geq 0$ , où $D_{KL}$ désigne la divergence de Kullback-Leibler et $\otimes$ le produit tensoriel.

Cette quantité s'annule seulement si $X$ et $Y$ sont indépendants, ainsi,

H(XY)\geq H(X\pi _{X}(Y))\leq H(X)+H(\pi _{X}(Y))=H(XY)

et l'égalité ci-dessus démontre l’indépendance de $X$ et $\pi _{X}(Y)$ .

Capacité du canal comme borne inférieure

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Capacité du canal comme borne supérieure

Par contradiction, avec la notation de Landau $\Omega (n)$ et en notant $I$ l'information mutuelle, supposons qu'il existe $d_{n}$ tel que,

I(d_{n}(Y^{n}),X^{n})-nC_{p}=|\Omega (n)|

comme $\pi _{X^{n}}(Y^{n})$ est indépendant de $X^{n}$ , on aurait,

I(\pi _{\pi _{X^{n}}(Y^{n})}(d_{n}(Y^{n})),X^{n})-nC_{p}=|\Omega (n)|

mais comme :

{\begin{aligned}H(Y^{n})&\geq H(\pi _{\pi _{X^{n}}(Y^{n})}(d_{n}(Y^{n}))\pi _{X^{n}}(Y^{n}))\\H(Y^{n})&\geq H(\pi _{\pi _{X^{n}}(Y^{n})}(d_{n}(Y^{n})))+H(\pi _{X^{n}}(Y^{n}))\\nC_{p}&\geq H(\pi _{\pi _{X^{n}}(Y^{n})}(d_{n}(Y^{n})))\end{aligned}}

Contradiction.

Articles connexes

Notes et références

↑ (en) Sae-Young Chung, G. David Forney, Jr. (en), Thomas J. Richardson et Rüdiger Urbanke, « On the Design of Low-Density Parity-Check Codes within 0.0045 dB of the Shannon Limit », IEEE Communication Letters, vol. 5,‎ février 2001, p. 58-60 (ISSN 1089-7798, lire en ligne)

[1] (en) Sae-Young Chung, G. David Forney, Jr. (en), Thomas J. Richardson et Rüdiger Urbanke, « On the Design of Low-Density Parity-Check Codes within 0.0045 dB of the Shannon Limit », IEEE Communication Letters, vol. 5,‎ février 2001, p. 58-60 (ISSN 1089-7798, lire en ligne)

[1]