Introduction aux codes correcteurs d’erreurs

Travaux Dirigés 1

Exercice 3

L'énoncé de cet exercice est manquant dans le document source. Le cours (section 3.1) mentionne uniquement qu'il s'agit d'un exemple de code non linéaire. Les données d'entrée et les questions exactes étant absentes du texte fourni, il est impossible de formuler une résolution.

Exercice 4

Le document source est endommagé ou incomplet concernant cet exercice. Seule la matrice génératrice (une matrice contenant 6 lignes et 3 colonnes) est donnée à titre d'illustration dans le cours (section 3.1). Aucune question n'étant posée sur cette matrice, il est impossible d'y répondre.

Travaux Dirigés 7

Algorithme de décodage

La section 5.3 fait référence à un algorithme de décodage pour les codes cycliques qui serait détaillé dans le TD 7. Le sujet et l'énoncé de ce TD n'ont pas été inclus dans le document fourni. Il est par conséquent impossible de résoudre cet exercice sans les données.

Contenu du document

Sujet d'examen

Le document fourni ("Introduction aux codes correcteurs d'erreurs" par Pierre Abbrugiati) s'avère être un support de cours théorique et non un sujet d'examen. Il ne pose aucune question ou problème non résolu au lecteur. Toutes les étapes de calcul présentées, telles que la factorisation des classes cyclotomiques ou le décodage du code de Hamming (4, 7) à l'aide de l'algorithme de Peterson-Gorenstein-Zierler (section 6.3), sont des exemples d'illustration dont la solution complète fait déjà partie intégrante du texte.

Méthode

Pour aborder un examen portant sur cette matière (les codes correcteurs d'erreurs en blocs, linéaires, cycliques et BCH), voici les étapes et réflexes fondamentaux à acquérir :

1. Identifier les paramètres du code (k, n, d) :

• n : la longueur du code (taille finale des blocs transmis).
• k : la dimension du code (taille des blocs de données source). Le nombre total de mots de code est 2ᵏ.
• d : la distance minimale. Elle définit les limites physiques du code.
• Capacité de détection : ed = d - 1.
• Capacité de correction : ec = ⌊(d - 1) ÷ 2⌋ (partie entière inférieure). Note : dans les documents altérés par l'extraction, cette formule apparaît souvent sous la forme typographique erronée "b d-1 / 2 c" au lieu des crochets de partie entière.

Manipuler les codes linéaires :

• La matrice génératrice G (de taille n lignes par k colonnes) permet le codage matriciel : Y = G × X.
• Un code est systématique si la matrice identité Ik apparaît clairement dans G (généralement sur les k premières lignes).
• La matrice de contrôle H permet de vérifier si un mot Z reçu appartient au code. Z est valide si et seulement si H × Z = 0 (vecteur nul).
• La distance minimale d correspond au nombre minimal de colonnes de H qui sont linéairement dépendantes.

Décodage par syndrome (algorithme de base) :

• Calculez le syndrome S = H × Z.
• Si S = 0, il n'y a pas d'erreur (ou le nombre d'erreurs dépasse la capacité de détection et forme un autre mot de code valide).
• Si S ≠ 0, cherchez la combinaison linéaire contenant le moins de colonnes de H dont la somme donne S. Les indices de ces colonnes vous indiquent la position exacte des erreurs.
• Attention aux calculs dans F2 : L'addition est un "OU exclusif" (XOR). 1 + 1 = 0, et la soustraction est strictement identique à l'addition.

Codes cycliques et polynômes :

• Un mot est représenté par un polynôme : P(X) = a0 + a1X + a2X² + ... + a(n-1)Xⁿ⁻¹.
• Un code cyclique est entièrement défini par son polynôme générateur g(X), qui doit obligatoirement être un diviseur exact de Xⁿ + 1 dans F2.
• Un mot reçu est valide si le reste de la division euclidienne de son polynôme par g(X) est nul.

Utilisation des tables (Codes BCH) :

• Pour l'algorithme de décodage des codes BCH (comme Peterson-Gorenstein-Zierler), utilisez systématiquement la table d'addition du corps fini F2(α) fournie dans le sujet. Ne tentez jamais de deviner les sommes de puissances de α (ex: α³ + α² = α⁵) sans vous référer au tableau d'équivalences de l'énoncé.

Outil de vérification informatique : Lors de vos révisions, si vous souhaitez vérifier vos calculs d'addition polynomiale dans le corps F2, vous pouvez utiliser ce petit script :

def add_poly_f2(p1, p2):
    """
    Additionne deux polynômes dans F2.
    Les polynômes sont représentés par des listes de coefficients [a0, a1, a2...].
    """
    max_len = max(len(p1), len(p2))
    # Copie et remplissage avec des zéros pour égaliser les degrés
    p1_padded = p1 + [0] * (max_len - len(p1))
    p2_padded = p2 + [0] * (max_len - len(p2))
    
    # Addition modulo 2 (équivalent au XOR)
    return [(c1 + c2) % 2 for c1, c2 in zip(p1_padded, p2_padded)]

# Exemple pour (1 + X) + (1 + X²) = X + X²
# Représenté par : p1 = [1, 1], p2 = [1, 0, 1]
print(add_poly_f2([1, 1], [1, 0, 1])) 
# Affiche : [0, 1, 1] (soit 0 + 1*X + 1*X²)