Capacité d’un canal : combien d’information transmettre malgré le bruit

Supposons qu’une ligne transmette un bit à la fois, avec une probabilité de 10 % de l’inverser. Sans codage, le récepteur lit en moyenne un bit erroné sur dix. Répéter chaque bit trois fois réduit les erreurs, mais occupe la ligne trois fois plus longtemps pour le même message. La capacité répond à une question : si l’on peut choisir le code, combien d’information chaque utilisation du canal permet-elle de transmettre avec une probabilité d’erreur arbitrairement faible ?

La note Théorie de l’information et entropie présente l’entropie conditionnelle, l’information mutuelle et la compression. Ces notions servent ici à décrire la communication : la compression réduit le nombre de bits nécessaires pour représenter une source, tandis que le codage de canal organise la redondance pour retrouver un message malgré le bruit. Tous les logarithmes sont en base 2 ; la capacité d’un canal discret s’exprime en bits par utilisation du canal.

Décrire le canal par une distribution conditionnelle

Au chapitre 9 d’Information Theory, Inference, and Learning Algorithms, de MacKay, la section Noisy channels définit un canal discret sans mémoire par ses alphabets d’entrée et de sortie et ses probabilités conditionnelles. Notons $X$ le symbole envoyé, $Y$ le symbole reçu, et

$$W(y\mid x)=P(Y=y\mid X=x),\qquad \sum_y W(y\mid x)=1.$$

À chaque entrée $x$ correspond une distribution des sorties possibles. Lorsque l’émetteur choisit la distribution d’entrée $P_X$, les distributions conjointe et de sortie sont déterminées :

$$P_{X,Y}(x,y)=P_X(x)W(y\mid x),\qquad P_Y(y)=\sum_x P_X(x)W(y\mid x).$$

Considérons d’abord des alphabets finis, une loi du canal constante dans le temps, aucune rétroaction et un canal sans mémoire. L’absence de mémoire signifie que les sorties sont conditionnellement indépendantes une fois toute la séquence d’entrée fixée :

$$P(y_1,\ldots,y_n\mid x_1,\ldots,x_n) =\prod_{i=1}^n W(y_i\mid x_i).$$

Les symboles d’entrée produits par un code peuvent néanmoins être corrélés. L’absence de mémoire concerne le mécanisme de bruit du canal. Un bruit en rafales ou un canal dont la loi évolue demande un autre modèle.

Maximiser l’information mutuelle sur la distribution d’entrée

Pour une distribution $P_X$ donnée, l’information mutuelle mesure combien d’information une sortie apporte en moyenne sur l’entrée. La section Maximizing the mutual information du chapitre 9 de MacKay définit la capacité par

$$C=\max_{P_X} I(X;Y) =\max_{P_X}\bigl[H(Y)-H(Y\mid X)\bigr].$$

La loi $W$ reste fixe : on choisit la fréquence d’utilisation de chaque symbole d’entrée, sans modifier les probabilités du bruit. Envoyer toujours le même symbole ne permet de distinguer aucun message ; l’information mutuelle est donc nulle, même si le récepteur reconnaît ce symbole. Une entrée uniforme atteint souvent la capacité d’un canal symétrique, mais ce résultat ne vaut pas pour tous les canaux.

Canal binaire symétrique : déduire et calculer la capacité

Le canal binaire symétrique (BSC), l’un des modèles du chapitre 9 de MacKay, inverse chaque bit avec probabilité $p$ et le conserve avec probabilité $1-p$. Les inversions sont indépendantes d’une utilisation à l’autre. Les entrées figurent ici en lignes et les sorties en colonnes :

Entrée	$Y=0$	$Y=1$
$X=0$	$1-p$	$p$
$X=1$	$p$	$1-p$

Définissons l’entropie binaire par

$$H_2(t)=-t\log_2 t-(1-t)\log_2(1-t),\qquad 0\log_2 0:=0.$$

Soit $q=P(X=1)$. Chaque entrée subit la même probabilité d’inversion, d’où $H(Y\mid X)=H_2(p)$. Par ailleurs,

$$P(Y=1)=p(1-q)+(1-p)q=p+(1-2p)q,$$

et donc

$$I(X;Y)=H_2\bigl(p+(1-2p)q\bigr)-H_2(p).$$

L’entropie d’une sortie binaire ne dépasse pas 1. Le choix $q=1/2$ rend la sortie uniforme et atteint cette borne. On obtient

$$C_{\mathrm{BSC}}=1-H_2(p).$$

Avec $p=0.1$, comme dans l’exemple initial :

$$\begin{aligned} H_2(0.1)&=-0.1\log_2 0.1-0.9\log_2 0.9 \approx 0.468996,\\ C_{\mathrm{BSC}}&\approx 0.531004\ \text{bits/use}. \end{aligned}$$

La capacité diffère de la proportion $0.9$ de bits reçus correctement. La sortie n’indique pas quels bits ont été inversés : le code doit fournir assez de structure pour lever cette ambiguïté. La formule vaut pour tout $0\le p\le1$ connu : la capacité est 1 pour $p=0$, nulle pour $p=1/2$ puisque l’entrée et la sortie sont indépendantes, et de nouveau 1 pour $p=1$, car il suffit au récepteur d’inverser chaque bit.

Canal binaire à effacement : les positions manquantes sont connues

Le chapitre 9 de MacKay définit aussi le canal binaire à effacement (BEC). La sortie reproduit l’entrée avec probabilité $1-\varepsilon$ et devient un symbole spécial ? avec probabilité $\varepsilon$. La probabilité d’effacement ne dépend pas de la valeur d’entrée, et les utilisations sont indépendantes. Un 0 n’est jamais annoncé à tort comme un 1.

Gardons $q=P(X=1)$. Recevoir 0 ou 1 détermine exactement l’entrée ; recevoir ? laisse sa distribution initiale inchangée. Ainsi,

$$H(X\mid Y)=\varepsilon H_2(q),\qquad I(X;Y)=(1-\varepsilon)H_2(q).$$

Une entrée uniforme donne $H_2(q)=1$, donc

$$C_{\mathrm{BEC}}=1-\varepsilon.$$

Pour $\varepsilon=0.1$, la capacité vaut $0.9$ bit par utilisation. À probabilité de dommage identique, soit 10 %, les effacements permettent de transmettre davantage d’information que les inversions du BSC, dont la capacité est $0.531004$. Le récepteur connaît les positions manquantes et peut faire confiance aux bits restants ; avec les inversions, il doit aussi repérer les positions erronées. Cette comparaison tient aux informations que chaque modèle fournit au récepteur : le seul chiffre « 10 % » ne rend pas ces canaux équivalents.

Ce que garantit le théorème de codage pour un canal bruité

Les sections 13–14 de l’article de Shannon de 1948 établissent le théorème de codage pour un canal bruité et sa formulation pour les longs messages. Pour le modèle discret fini sans mémoire décrit plus haut, les chapitres 9–10 de MacKay donnent la forme suivante.

Un encodeur associe à chacun des $M$ messages possibles un mot de code d’entrée de longueur $n$ ; un décodeur estime le message à partir de la sortie. Le débit du code est

$$R_n=\frac{\log_2 M}{n}\ \text{bits/use}.$$

Pour $k$ bits de message, $M=2^k$ et le débit vaut $k/n$. Il y a erreur de bloc lorsque le message entier n’est pas correctement retrouvé, ce qui diffère de la corruption d’un symbole transmis.

Pour tout débit cible fixe $0<R<C$ et toute probabilité d’erreur de bloc tolérée $\delta>0$, une longueur de bloc suffisamment grande permet l’existence d’un code de débit au moins $R$ et d’un décodeur dont la probabilité d’erreur, même pour le message le plus défavorable, est inférieure à $\delta$. La probabilité d’erreur de bloc peut donc tendre vers zéro tout en maintenant un débit positif inférieur à la capacité. À l’inverse, un débit fixe supérieur à $C$ ne permet pas de faire tendre cette probabilité vers zéro.

Il s’agit d’un résultat d’existence. Il ne rend pas tous les codes efficaces, ne précise ni la longueur nécessaire ni un décodeur rapide, et ne garantit pas zéro erreur pour un bloc fini. L’énoncé d’atteignabilité exige strictement $R<C$ ; il n’apporte pas cette garantie à $R=C$. Pour le BSC avec $p=0.1$, le débit cible $R=0.5$ est inférieur à $0.531004$ et satisfait cette condition ; $R=0.6$ dépasse la capacité.

Code de répétition : erreur résiduelle et coût en débit

Le chapitre 1 de MacKay commence par la répétition triple : coder 0 en 000, coder 1 en 111, puis décoder par vote majoritaire. Si l’on a envoyé 000, la réception de 010 donne encore 0, tandis que 011 est décodé à tort comme 1.

Chaque mot de code porte un seul bit de message et utilise trois fois le canal : $R=1/3$. Avec des inversions indépendantes de probabilité $p=0.1$, une erreur demande au moins deux inversions :

$$\begin{aligned} P_{\mathrm{err}}&=\binom32 p^2(1-p)+p^3\\ &=3(0.1)^2(0.9)+(0.1)^3\\ &=0.027+0.001=0.028. \end{aligned}$$

Le bloc de message ne contient ici qu’un bit : les probabilités d’erreur de bit décodé et d’erreur de bloc coïncident. L’erreur passe de 10 % à 2,8 %, mais le débit tombe à environ $0.333333$ bit par utilisation.

Pour un nombre impair $n$ de répétitions, la loi binomiale donne la probabilité d’une majorité d’inversions :

$$R=\frac1n,\qquad P_{\mathrm{err}}=\sum_{j=(n+1)/2}^{n}\binom nj p^j(1-p)^{n-j}.$$

Répétitions $n$	Débit (bits par utilisation)	Probabilité d’erreur après décodage, $p=0.1$
1 (sans codage)	1.000000	0.10000000
3	0.333333	0.02800000
5	0.200000	0.00856000
9	0.111111	0.00089092

Pour $0<p<1/2$, augmenter indéfiniment le nombre de répétitions fait tendre l’erreur du vote majoritaire vers zéro, mais aussi le débit $1/n$ vers zéro, loin de la capacité positive fixée. Les codes proches de la capacité doivent porter un nombre croissant de bits de message à mesure que leur longueur augmente.

Assembler des mots de répétition triple pour former un message plus long ne réalise pas non plus le codage en longs blocs du théorème. Pour $m$ bits de message codés indépendamment, la probabilité d’au moins une erreur vaut $1-(1-0.028)^m$ et tend vers 1 quand $m$ augmente. Avec $m=100$, elle vaut $1-0.972^{100}\approx0.941571$, soit environ 94,16 %. La répétition montre que la redondance peut corriger des erreurs ; sa répartition compte également.

Canal gaussien : préciser la puissance et les unités

Une distribution conditionnelle peut aussi décrire des entrées continues. Dans le modèle gaussien du chapitre 11 de MacKay, $Y=X+Z$, où $Z\sim\mathcal N(0,\sigma^2)$ est indépendant de l’entrée ; les échantillons de bruit sont indépendants et identiquement distribués d’une utilisation à l’autre. Si la puissance moyenne d’entrée satisfait $E[X^2]\le P$ et que les entrées réelles sont autorisées, la capacité par utilisation d’une dimension réelle vaut

$$C_{\mathrm{real}}=\frac12\log_2\left(1+\frac{P}{\sigma^2}\right) \ \text{bits/use}.$$

Une entrée gaussienne de moyenne nulle et de variance $P$ maximise l’information mutuelle. La contrainte de puissance est essentielle : sans elle, augmenter l’amplitude rend la capacité non bornée. Limiter l’entrée à deux niveaux change également le problème ; cette formule autorise toutes les valeurs réelles.

Le théorème 17, dans la section 25 de l’article de Shannon, donne la formule du canal à bande limitée avec bruit blanc gaussien additif. Pour une bande passante $B$ en Hz, une puissance moyenne du signal au plus égale à $S$ et une puissance totale du bruit $N$ dans cette bande,

$$C_{\mathrm{band}}=B\log_2\left(1+\frac SN\right) \ \text{bits/s}.$$

Les unités diffèrent : la première formule compte des dimensions réelles, la seconde des secondes. Au chapitre 11, MacKay représente le modèle idéal à bande limitée par $2B$ dimensions réelles par seconde. Répartir les puissances du signal et du bruit entre ces dimensions conserve leur rapport ; multiplier par $2B$ annule donc le facteur $1/2$ de la première formule. Pour un rapport signal sur bruit linéaire de 9, la première donne $\tfrac12\log_2 10\approx1.660964$ bit par utilisation. Avec $B=10^6$ Hz, la seconde donne $10^6\log_2 10\approx3321928.094887$ bits/s, soit environ $3.321928$ Mbit/s.

La capacité est une limite asymptotique propre au modèle du canal. Avec des blocs courts, il faut déterminer séparément la probabilité d’erreur au débit et à la longueur choisis. Une faible latence ou des moyens de calcul limités imposent aussi de comparer le temps d’exécution et la mémoire des encodeurs et décodeurs réels. Shannon observe dans la section 14 que la méthode de la preuve pour approcher le codage idéal est généralement peu praticable. La formule de capacité ne suffit donc pas à calculer le débit qu’un appareil peut atteindre.

Recalculer avec Python

Cet exemple nécessite Python 3.8 ou une version ultérieure, car il utilise math.comb. Il évalue les capacités et les sommes binomiales en virgule flottante avec la seule bibliothèque standard. Ce sont des probabilités du modèle, sans échantillonnage aléatoire.

from math import comb, log2


def h2(t):
    if not 0 <= t <= 1:
        raise ValueError("Probability must be between 0 and 1")
    if t in (0, 1):
        return 0.0
    return -t * log2(t) - (1 - t) * log2(1 - t)


p = 0.1
epsilon = 0.1
print(f"H2({p}) = {h2(p):.6f}")
print(f"BSC capacity = {1 - h2(p):.6f} bits/use")
print(f"BEC capacity = {1 - epsilon:.6f} bits/use")
for n in (1, 3, 5, 9):
    error = sum(comb(n, j) * p**j * (1 - p)**(n - j)
                for j in range((n + 1) // 2, n + 1))
    print(f"n={n}: rate={1/n:.6f}, error={error:.8f}")
threefold_error = 3 * p**2 * (1 - p) + p**3
print(f"100-bit message error = {1 - (1 - threefold_error)**100:.6f}")
snr = 9.0
bandwidth = 1_000_000
print(f"Real Gaussian capacity = {0.5 * log2(1 + snr):.6f} bits/use")
print(f"Bandlimited capacity = {bandwidth * log2(1 + snr):.6f} bits/s")

Sortie :

H2(0.1) = 0.468996
BSC capacity = 0.531004 bits/use
BEC capacity = 0.900000 bits/use
n=1: rate=1.000000, error=0.10000000
n=3: rate=0.333333, error=0.02800000
n=5: rate=0.200000, error=0.00856000
n=9: rate=0.111111, error=0.00089092
100-bit message error = 0.941571
Real Gaussian capacity = 1.660964 bits/use
Bandlimited capacity = 3321928.094887 bits/s

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.