1. Introduction : Deux miracles quotidiens de résurrection de l’information

Aux confins de l’espace interstellaire comme au creux de votre main, l’ingénierie numérique accomplit chaque jour ce qui semble défier l’intuition physique : reconstruire à 100 %, au bit près, une information numérique dont le support ou le signal a été gravement mutilé par le bruit thermique ou la destruction matérielle.

Miracle 1 : Voyager 1 et 2 communiquant à 24 milliards de kilomètres avec $10^{-16}\text{ watts}$

Lancées en 1977, les sondes Voyager 1 et Voyager 2 ont photographié Jupiter, Saturne, Uranus et Neptune avant de pénétrer dans l’espace interstellaire à plus de 24 milliards de kilomètres de la Terre. L’émetteur radio de Voyager ne développe que $23\text{ watts}$ — moins que l’ampoule d’un réfrigérateur. Lorsque cette onde atteint les antennes de 70 mètres du Deep Space Network (DSN) de la NASA sur Terre, la puissance reçue est tombée à environ $10^{-16}\text{ watts}$ ($0,1\text{ attowatt}$), totalement noyée dans le bruit thermique (bruit de Johnson-Nyquist). Pourtant, Voyager a transmis des portraits en couleur d’une netteté remarquable avec zéro erreur binaire résiduelle.

Miracle 2 : Un code QR recouvert à $30\,\%$ par une tache de café ou un logo

Considérez maintenant un code QR sur une table de café dont un coin est taché, ou dont $30\,\%$ de la surface centrale est délibérément masquée par le logo d’une entreprise. En moins de $10\text{ millisecondes}$, la caméra de votre smartphone restitue l’URL exacte avec zéro bit d’erreur.

  flowchart TD
    subgraph Voyager["Télémesure spatiale lointaine (Voyager 1 & 2)"]
        V1["Image planétaire (k bits)"] --> V2["Codage concaténé (RS externe + Convolutif/LDPC interne)"]
        V2 --> V3["Émetteur 23 W sur des milliards de km (10⁻¹⁶ W reçus)"]
        V3 --> V4["Bruit blanc gaussien (AWGN) & inversions de bits"]
        V4 --> V5["Viterbi pondéré / Propagation de croyance + Décodage RS"]
        V5 --> V6["Portrait planétaire parfait (Zéro bit d'erreur)"]
    end
    subgraph QR["Lecture quotidienne d'un Code QR"]
        Q1["URL / Données utiles (k octets)"] --> Q2["Codage de Reed-Solomon sur GF(2⁸) (n octets)"]
        Q2 --> Q3["Tache de café ou logo détruisant 30 % des modules"]
        Q3 --> Q4["Calcul des syndromes + Algorithme de Berlekamp-Massey"]
        Q4 --> Q5["Recherche de Chien + Formule de Forney (10 ms)"]
        Q5 --> Q6["Reconstruction exacte à 100 %"]
    end

Comment est-ce mathématiquement possible ? Grâce à la théorie de l’information de Claude Shannon (1948) et à la science des codes correcteurs d’erreurs (ECC).

2. La révolution de Claude Shannon (1948) et le théorème du codage de canal

2.1 L’impasse du codage par répétition naïf ($0 \to 00000$)

Lorsque $n \to \infty$, on a bien $P_e^{(n)} \to 0$, mais le rendement du code s’effondre simultanément : $R = k/n = 1/n \to 0$.

2.2 Le théorème de Shannon et la limite ultime de Shannon ($-1,59\,\text{dB}$)

En 1948, Claude E. Shannon démontra dans “A Mathematical Theory of Communication” son célèbre théorème du codage de canal bruyant :

Théorème (Codage de canal de Shannon, 1948) : Tout canal sans mémoire possède une capacité de canal $C > 0$ intrinsèque :

• Pour le canal binaire symétrique (BSC) avec entropie binaire $H_2(p) = -p\log_2 p - (1-p)\log_2(1-p)$ : $$C_{\text{BSC}}(p) = 1 - H_2(p) = 1 + p\log_2 p + (1-p)\log_2(1-p) \quad [\text{bits / utilisation}]$$
• Pour le canal AWGN de bande passante $B$, puissance signal $S$ et bruit $N = N_0 B$ (théorème de Shannon-Hartley) : $$C_{\text{AWGN}} = B \log_2\!\left(1 + \frac{S}{N}\right) = B \log_2\!\left(1 + \frac{S}{N_0 B}\right) \quad [\text{bits / s}]$$

Pour tout débit $R < C$, il existe des codes en blocs de longueur $n \to \infty$ permettant une probabilité d’erreur arbitrairement faible ($P_e \to 0$) !

3. La percée géométrique de Richard Hamming (1950) : distance de Hamming et code parfait $[7, 4, 3]$

3.1 Distance de Hamming $d_H(\mathbf{u}, \mathbf{v})$ et borne d’empilement de sphères

Pour un code $\mathcal{C} \subset \mathbb{F}_q^n$ de distance minimale $d_{\min} = \min_{\mathbf{u}\neq\mathbf{v}} d_H(\mathbf{u},\mathbf{v})$, la disjonction des sphères de Hamming de rayon $t$ prouve que le code peut :

• Détecter $d_{\min} - 1$ erreurs ;
• Corriger $e = d_{\min} - 1$ effacements (positions connues) ;
• Corriger $t = \lfloor(d_{\min} - 1)/2\rfloor$ erreurs arbitraires (positions inconnues) : $$\mathbf{d_{\min} \ge 2t + e + 1}, \qquad |\mathcal{C}| \cdot \sum_{i=0}^{t} \binom{n}{i} (q-1)^i \le q^n \quad \text{(Borne de Hamming)}$$

3.2 Le code parfait de Hamming $(7,4)$ et le décodage par syndrome

Le syndrome à 3 bits $\mathbf{s} = \mathbf{H}\mathbf{y}^T = \mathbf{H}(\mathbf{c} + \mathbf{e})^T = \mathbf{H}\mathbf{e}^T \pmod 2$ extrait directement la colonne de $\mathbf{H}$ correspondant au bit inversé : si les colonnes sont ordonnées de $1$ à $7$ en binaire, $\mathbf{s}$ donne directement l’indice binaire $(1 \dots 7)$ du bit erroné ! Ce circuit équipe toutes les mémoires serveur ECC DRAM (SECDED).

4. Le chef-d’œuvre de Reed et Solomon (1960) : codes de Reed-Solomon sur les corps de Galois $\mathbb{F}_{2^m}$

4.1 Corps de Galois $\text{GF}(2^8)$ et immunité aux erreurs en rafale (Burst Errors)

Pour vaincre les erreurs en rafale (rayures, taches sur un code QR), Irving Reed et Gustave Solomon (1960) ont regroupé chaque octet ($m=8$ bits) en un symbole unique du corps fini $\text{GF}(2^8) = \mathbb{F}_2[x]/(x^8 + x^4 + x^3 + x^2 + 1)$. Même si les 8 bits d’un octet sont détruits, cela ne représente qu’une seule erreur de symbole dans $\text{GF}(2^8)$ !

4.2 Interpolation polynomiale et borne de Singleton MDS $d_{\min} = n - k + 1$

Cela permet de corriger $e = n - k$ effacements (RAID-6, stockage cloud) ou $t = \lfloor(n-k)/2\rfloor$ erreurs de position inconnue (codes QR jusqu’à 30 % au niveau H, sonde Voyager $[255, 223]$) via le polynôme générateur cyclique $g(x) = \prod_{i=1}^{2t}(x - \alpha^i)$, l’algorithme de Berlekamp-Massey / Euclide résolvant $\Lambda(x)S(x) \equiv \Omega(x) \pmod{x^{2t}}$, la recherche de Chien et la formule de Forney.

5. Atteindre la limite de Shannon : codes LDPC (1962), Turbo (1993) et Polaires (2009)

1. Codes LDPC de Robert Gallager (1962) : définis par une matrice de parité creuse $\mathbf{H}$ et un graphe bipartite de Tanner. Le décodage itératif par propagation de croyance (Belief Propagation / Sum-Product) échangeant des rapports de vraisemblance logarithmiques souples $L(c_i) = \ln\frac{P(c_i=0|y_i)}{P(c_i=1|y_i)}$ s’approche à $0,0045\,\text{dB}$ de la limite de Shannon (canaux de données 5G NR, Wi-Fi 6/7, SSD 3D NAND).
2. Codes Polaires d’Erdal Arıkan (2009) : par application récursive du noyau de Kronecker $\mathbf{G}_N = \mathbf{B}_N \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}^{\otimes m}$, la polarisation de canal fait converger une fraction $C = I(W)$ des sous-canaux synthétiques vers une capacité $1$ (sans bruit, bits d’information) et une fraction $1 - C$ vers une capacité $0$ (bits gelés / Frozen Bits $= 0$), atteignant pour la première fois de manière mathématiquement prouvable la capacité de Shannon en $O(N \log N)$ (canaux de contrôle 5G NR).

  flowchart TD
    subgraph Cap["Codes modernes atteignant la capacité de Shannon"]
        L1["Codes LDPC (Graphe bipartite creux de Tanner)"] --> L2["Échange itératif de messages LLR souples"]
        L2 --> L3["Propagation de croyance Sum-Product (à 0,0045 dB de la limite de Shannon)"]
        P1["Codes Polaires (Transformation de Kronecker G_N = B_N F^{⊗m})"] --> P2["Polarisation en sous-canaux W⁻ (dégradés) et W⁺ (améliorés)"]
        P2 --> P3["Fraction C → Capacité 1 (Bits utiles), Fraction 1-C → Capacité 0 (Bits gelés)"]
    end

Tableau comparatif des grandes familles de codes correcteurs

6. Implémentation Python complète : Hamming $(7,4)$ et Reed-Solomon sur $\text{GF}(2^8)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

from typing import List

def hamming74_demo() -> None:
    G = [[1,0,0,0,1,1,0], [0,1,0,0,1,0,1], [0,0,1,0,0,1,1], [0,0,0,1,1,1,1]]
    H = [[1,1,0,1,1,0,0], [1,0,1,1,0,1,0], [0,1,1,1,0,0,1]]
    msg = [1, 0, 1, 1]
    c = [sum(msg[i] * G[i][j] for i in range(4)) % 2 for j in range(7)]
    y = c.copy()
    y[2] ^= 1
    s = [sum(H[r][col] * y[col] for col in range(7)) % 2 for r in range(3)]
    err_idx = next(col for col in range(7) if [H[r][col] for r in range(3)] == s)
    y[err_idx] ^= 1
    print(f"[Hamming (7,4)] Syndrome={s} -> Flipped idx={err_idx}, Recovered={y[:4] == msg}")

class GF256:
    def __init__(self, poly: int = 0x11D) -> None:
        self.exp, self.log = [0] * 512, [0] * 256
        v = 1
        for i in range(255):
            self.exp[i] = self.exp[i + 255] = v
            self.log[v] = i
            v <<= 1
            if v & 0x100:
                v ^= poly

    def mul(self, a: int, b: int) -> int:
        return 0 if (a == 0 or b == 0) else self.exp[self.log[a] + self.log[b]]

    def inv(self, a: int) -> int:
        return self.exp[255 - self.log[a]]

    def power(self, a: int, p: int) -> int:
        return 1 if p == 0 else (0 if a == 0 else self.exp[(self.log[a] * p) % 255])

    def eval_poly(self, coeffs: List[int], x: int) -> int:
        res = 0
        for c in reversed(coeffs):
            res = self.mul(res, x) ^ c
        return res

    def solve(self, A: List[List[int]], b: List[int]) -> List[int]:
        n = len(b)
        M = [row[:] + [b[i]] for i, row in enumerate(A)]
        for col in range(n):
            piv = next(r for r in range(col, n) if M[r][col] != 0)
            M[col], M[piv] = M[piv], M[col]
            inv_p = self.inv(M[col][col])
            for j in range(col, n + 1):
                M[col][j] = self.mul(M[col][j], inv_p)
            for r in range(n):
                if r != col and M[r][col] != 0:
                    f = M[r][col]
                    for j in range(col, n + 1):
                        M[r][j] ^= self.mul(f, M[col][j])
        return [M[i][n] for i in range(n)]

def rs_demo() -> None:
    gf = GF256()
    text = "VOYAGER-1"
    k, t = len(text), 3
    n = k + 2 * t
    pts = [gf.exp[i] for i in range(n)]
    cw = [gf.eval_poly([ord(c) for c in text], x) for x in pts]
    rx = cw.copy()
    rx[1] ^= 0xFF; rx[6] ^= 0xA5; rx[13] ^= 0x3C
    A = [[gf.power(pts[i], d) for d in range(k + t)] + [gf.mul(rx[i], gf.power(pts[i], d)) for d in range(t)] for i in range(n)]
    b = [gf.mul(rx[i], gf.power(pts[i], t)) for i in range(n)]
    sol = gf.solve(A, b)
    E = sol[k + t:] + [1]
    err_pos = [i for i, x in enumerate(pts) if gf.eval_poly(E, x) == 0]
    valid = [(pts[i], rx[i]) for i in range(n) if i not in err_pos][:k]
    rec = gf.solve([[gf.power(x, d) for d in range(k)] for x, _ in valid], [y for _, y in valid])
    print(f"[RS(15,9) over GF(2^8)] Located Errors={err_pos}, Recovered='{''.join(chr(c) for c in rec)}'")

if __name__ == "__main__":
    hamming74_demo()
    rs_demo()

7. Conclusion

De la limite de Shannon $-1,59\,\text{dB}$ (1948) à la géométrie de Hamming (1950), à l’interpolation polynomiale de Reed-Solomon sur $\mathbb{F}_{2^m}$ (1960), jusqu’aux graphes de Tanner LDPC et à la polarisation de canal d’Arıkan, la théorie des codes correcteurs illustre comment l’algèbre abstraite permet de vaincre l’entropie physique.