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.