Skip to article frontmatterSkip to article content

Exemples Intéractifs: Contrôle des erreurs

Introduction\textbf{Introduction}

Dans les systèmes de communication et de stockage, les erreurs de transmission ou de lecture sont fréquentes. Les codes correcteurs d’erreurs permettent de garantir l’intégrité des données en ajoutant des bits redondants à un message initial. Ces bits supplémentaires aident à détecter et corriger les erreurs éventuelles.

Codage de blocs\textbf{Codage de blocs}

Veˊrification de la pariteˊ\textbf{Vérification de la parité}

Le code de parité transversale est un exemple de code correcteur d’erreurs simple. Ce code transforme un mot d’information de 3 bits (d1,d2,d3d_1, d_2, d_3) en un mot de code de 4 bits (c1,c2,c3,c4c_1, c_2, c_3, c_4). Le 4e bit est un bit de parité qui garantit que la somme des bits est toujours paire.

Ce type de code permet de :

  • Détecter 1 erreur : si un seul bit est erroné, la parité ne sera pas respectée.
  • Ne pas détecter 2 erreurs : deux bits erronés peuvent “annuler” la violation de parité.

Matrice de Génération G

La génération des mots de code repose sur la matrice G suivante :

G=[100101010011]G = \begin{bmatrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{bmatrix}
(1)

Chaque ligne de G encode les bits d1,d2,d3d_1, d_2, d_3, et le dernier bit est la parité transversale :

c4=d1⊕d2⊕d3c_4 = d_1 \oplus d_2 \oplus d_3
(2)

Encodage

Pour encoder un mot d’information d=[d1,d2,d3]d = [d_1, d_2, d_3], on multiplie dd par GG modulo 2 :

c=d⋅Gmod  2c = d \cdot G \mod 2
(3)

Exemple :
Si d=[1,1,0]d = [1, 1, 0], le mot de code généré sera c=[1,1,0,0]c = [1, 1, 0, 0].

Détection d’Erreurs

Lorsqu’un mot de code r=[r1,r2,r3,r4]r = [r_1, r_2, r_3, r_4] est reçu, on vérifie si la parité est respectée :

  • Si la somme modulo 2 de tous les bits est 0, le mot est valide.
  • Sinon, une erreur est détectée.

Limites du Code

  • dmin⁡=2d_{\min} = 2 : La distance minimale entre deux mots de code est de 2.
  • Le code peut détecter 1 erreur (1 bit incorrect).
  • Il ne peut pas détecter 2 erreurs, car elles peuvent “annuler” la violation de parité.
Source
import numpy as np
from ipywidgets import interact, Text

# ================================
# Matrice de génération G (Code 4,3)
# ================================
G = np.array([
    [1, 0, 0, 1],
    [0, 1, 0, 1],
    [0, 0, 1, 1]
], dtype=int)

# ================================
# Fonction d'encodage
# ================================
def encode_parity(d_bits):
    """Encode le mot d'information en mot de code avec parité."""
    d_bits = np.array(d_bits, dtype=int)
    return (d_bits @ G) % 2  # Multiplication matrice mod 2

# ================================
# Fonction de vérification de parité
# ================================
def check_parity(r_bits):
    """Vérifie si le mot reçu respecte la parité."""
    r_bits = np.array(r_bits, dtype=int)
    parity = np.sum(r_bits) % 2  # Somme modulo 2
    return parity == 0

# ================================
# Interface interactive : Encodage
# ================================
def interactive_encode(d_str):
    """
    Fonction interactive pour encoder un mot d'information d (3 bits).
    """
    d_digits = [int(ch) for ch in d_str if ch in ('0', '1')]
    if len(d_digits) != 3:
        print("[ERREUR] Le mot d'information doit contenir exactement 3 bits.")
        return
    d_bits = np.array(d_digits, dtype=int)
    c = encode_parity(d_bits)
    print(f"Mot d'information (d) : {d_bits.tolist()}")
    print(f"Mot de code généré (c) : {c.tolist()}")
    print("\nFormule utilisée : c = d × G (mod 2)")
    print("Matrice G :")
    print(G)

# ================================
# Interface interactive : Vérification
# ================================
def interactive_check(r_str):
    """
    Fonction interactive pour vérifier la parité d'un mot reçu r (4 bits).
    """
    r_digits = [int(ch) for ch in r_str if ch in ('0', '1')]
    if len(r_digits) != 4:
        print("[ERREUR] Le mot reçu doit contenir exactement 4 bits.")
        return
    r_bits = np.array(r_digits, dtype=int)
    is_valid = check_parity(r_bits)
    result = "Valide (parité vérifiée)" if is_valid else "Erreur détectée (parité non vérifiée)"
    print(f"Mot reçu (r) : {r_bits.tolist()}")
    print(f"Résultat : {result}")
    print("\nFormule utilisée : Parité = somme(r) % 2")

# ================================
# Widgets interactifs
# ================================
print("### Encodage ###")
interact(
    interactive_encode,
    d_str=Text(
        value="110",
        description="d (3 bits) :"
    )
)

print("\n### Vérification ###")
interact(
    interactive_check,
    r_str=Text(
        value="1100",
        description="r (4 bits) :"
    )
)
Loading...

Codage de Hamming(7,4)\textbf{Codage de Hamming(7,4)}

Le code Hamming(7,4) est un code linéaire simple qui transforme un mot de 4 bits d’information (dd) en un mot de code de 7 bits (cc). Ce code permet de :

  • Corriger 1 erreur survenue pendant la transmission.
  • Détecter jusqu’à 2 erreurs, sans les corriger.

Principe du code Hamming(7,4)

Le code Hamming(7,4) est défini par deux matrices :

  • Matrice de génération GG : utilisée pour encoder les données.
  • Matrice de contrôle HH : utilisée pour détecter et corriger les erreurs.

Encodage

Le mot de code cc est obtenu en multipliant le mot d’information dd par la matrice GG (modulo 2) :

c=d⋅Gmod  2c = d \cdot G \mod 2

Détection et correction d’erreurs

Lorsqu’un mot rr est reçu (avec ou sans erreur), on calcule le syndrome ss en multipliant rr par la transposée de la matrice HH :

s=r⋅HTmod  2s = r \cdot H^T \mod 2

  • Si s=0s = 0, aucune erreur n’est détectée.
  • Si s≠0s \neq 0, le syndrome indique la position de l’erreur (dans les limites du code).

Le code Hamming(7,4) est dit SECDED (Single Error Correction, Double Error Detection).

Étapes de la démonstration

Cette démonstration suit les étapes suivantes :

  1. Déterminer la distance minimale dmin⁡d_{\min} et les pouvoirs détecteur/correcteur du code.
  2. Encodage : Transformez un mot d’information dd (4 bits) en un mot de code cc (7 bits).
  3. Détection d’erreurs : Comparez un mot reçu rr avec le mot de code cc pour détecter et localiser les erreurs.
  4. Correction : Corrigez le mot reçu rr pour retrouver le mot de code attendu c^c_{\hat{}} et en déduire le mot d’information corrigé d^\hat{d}.

Matrices utilisées

Matrice de génération GG

$G =

[1000110010010100100110001111]\begin{bmatrix} 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 \end{bmatrix}
(4)

Matrice de contrôle HH

$H =

[110110010110100111001]\begin{bmatrix} 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{bmatrix}
(5)

Autres codages possibles

En plus du code Hamming(7,4), il existe d’autres codes correcteurs d’erreurs avec des propriétés différentes, tels que :

  • Code Parité(4,3) : un code simple qui ajoute un seul bit de parité pour détecter 1 erreur.
  • Code Hamming étendu(8,4) : basé sur le Hamming(7,4) mais ajoute un bit supplémentaire pour détecter 2 erreurs et corriger 1 erreur.
  • Code BCH : codes plus puissants capables de corriger plusieurs erreurs simultanées.
Source
import numpy as np
from ipywidgets import interact, Text

# ===============================
# Matrices pour Hamming(7,4)
# ===============================
G = np.array([
    [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]
], dtype=int)

H = np.array([
    [1, 1, 0, 1, 1, 0, 0],
    [1, 0, 1, 1, 0, 1, 0],
    [0, 1, 1, 1, 0, 0, 1]
], dtype=int)

# Nombre de bits d'information et de bits totaux
k, n = 4, 7

# =============================
# Fonctions utilitaires
# =============================
def encode(d_bits):
    """ c = d * G (mod 2). """
    d_bits = np.array(d_bits, dtype=int)
    return (d_bits @ G) % 2

def syndrome(r_bits):
    """ s = r * H^T (mod 2). """
    r_bits = np.array(r_bits, dtype=int)
    return (r_bits @ H.T) % 2

def correct_error(r_bits):
    """ Tente de corriger r_bits en détectant 1 erreur max. """
    s = syndrome(r_bits)
    pos_err = 0
    Ht = H.T
    for i_col in range(n):
        if np.all(Ht[i_col] == s):
            pos_err = i_col + 1
            break
    r_corr = r_bits.copy()
    if pos_err > 0:
        r_corr[pos_err - 1] ^= 1  # Flip le bit détecté
    return r_corr, s, pos_err

def syndrome_table(H):
    """
    Génère le tableau des syndromes pour toutes les erreurs possibles.
    """
    n = H.shape[1]
    table = {}
    for pos in range(n):
        e = np.zeros(n, dtype=int)
        e[pos] = 1  # Injecter une erreur à une position donnée
        s = (e @ H.T) % 2  # Syndrome
        table[tuple(s)] = e
    return table

# Variable pour stocker les valeurs calculées de c
c_global = None

# ============================
# Étape 1 : Calcul d_min et t
# ============================
def step1_dmin():
    d_min = 3  # d_min est fixé pour le code Hamming(7,4)
    t_detect = d_min - 1
    t_correct = (d_min // 2) if (d_min % 2 == 0) else ((d_min - 1) // 2)
    print("=== Étape 1 : Hamming(7,4) ===")
    print("### Matrice de génération G ###")
    print(G)
    print("\n### Matrice de contrôle H ###")
    print(H)
    print("\n### Distance minimale d_min ###")
    print("d_min = 3")
    print("\n### Pouvoirs du code ###")
    print(f"Détection d'erreurs : jusqu'à {t_detect} erreurs")
    print(f"Correction d'erreurs : jusqu'à {t_correct} erreur(s)")

    # Afficher le tableau des syndromes
    table = syndrome_table(H)
    print("\n### Tableau des syndromes (1 erreur max) ###")
    print("Syndrome (s)   → Erreur (e)")
    for s, e in table.items():
        print(f"{list(s)} → {e.tolist()}")

# ============================
# Étape 2 : Encodage
# ============================
def step2_encode(d_str):
    global c_global  # On sauvegarde c pour l'utiliser dans l'étape suivante
    d_digits = [int(ch) for ch in d_str if ch in ('0', '1')]
    if len(d_digits) != k:
        print(f"[ERREUR] Le Hamming(7,4) attend {k} bits pour d.")
        print(f"        Vous avez saisi : {d_str}")
        return
    d_bits = np.array(d_digits, dtype=int)
    c_global = encode(d_bits)
    print("\n### Étape 2 : Encodage ###")
    print(f"Bits d'information (d) : {d_bits.tolist()}")
    print(f"Mot de code généré (c) : {c_global.tolist()}")
    print("\n### Formule utilisée ###")
    print("c = d × G (mod 2)")

# ============================
# Étape 3 : Calcul de s, e, et correction
# ============================
def step3_process_r(r_str):
    global c_global  # Utilise le c calculé dans l'étape 2
    if c_global is None:
        print("[ERREUR] Vous devez d'abord calculer c à l'étape 2.")
        return

    # Lire et valider r
    r_digits = [int(ch) for ch in r_str if ch in ('0', '1')]
    if len(r_digits) != n:
        print(f"[ERREUR] Le Hamming(7,4) attend {n} bits pour r.")
        print(f"        Vous avez saisi : {r_str}")
        return
    r_bits = np.array(r_digits, dtype=int)

    # Calculer e = r ⊕ c et syndrome s
    e = (r_bits ^ c_global) % 2
    s = syndrome(r_bits)

    # Corriger l'erreur
    r_corr, s, pos_err = correct_error(r_bits)
    d_hat = r_corr[:k]

    print("\n### Étape 3 : Calcul et Correction ###")
    print(f"Mot de code attendu (c) : {c_global.tolist()}")
    print(f"Mot reçu (r) : {r_bits.tolist()}")
    print(f"Erreur détectée (e = r ⊕ c) : {e.tolist()}")
    print(f"Syndrome calculé (s = r × H^T) : {s.tolist()}")
    print("\n### Correction ###")
    if np.all(s == 0):
        print("Aucune erreur détectée (s = 0).")
    else:
        print("Erreur détectée (s ≠ 0).")
        if pos_err == 0:
            print("Aucune correspondance trouvée pour le syndrome : Erreur non corrigeable.")
        else:
            print(f"Bit erroné détecté : position {pos_err} (1-indexé)")
            print(f"Mot corrigé (ĉ) : {r_corr.tolist()}")
    print("\n### Bits corrigés ###")
    print(f"d̂ = {d_hat.tolist()} (bits d'information corrigés)")

# ============================
# Interfaces interactives
# ============================

# Étape 1 : Afficher d_min et t
print("=== Étape 1 : Calcul de d_min et t ===")
step1_dmin()

# Étape 2 : Entrer d et obtenir c
print("\n=== Étape 2 : Encodage d → c ===")
interact(
    step2_encode,
    d_str=Text(
        value="1011",
        description="d (4 bits) :"
    )
);

# Étape 3 : Entrer r, calculer s, e, et corriger
print("\n=== Étape 3 : Processus avec r ===")
interact(
    step3_process_r,
    r_str=Text(
        value="1110010",
        description="r (mot reçu) :"
    )
);
Loading...
Introduction
Section 6 - Contrôle des erreurs
Introduction
Section 7 - Codage de source