Section 28

Codes linéaires et correction d'erreurs

> Application algébrique des espaces vectoriels et des corps finis. Cette section présente le noyau mathématique des codes linéaires sans transformer le cours en un cours complet de théorie des codes.

Code linéaire sur un corps fini

avancéviz

Un code linéaire $C$ de longueur $n$ sur $F_{q}$ est un sous-espace vectoriel

C \leq F_{q}^{n} .

Forme équivalente

dim (C) = k,

Un ensemble de mots de code fermés sous addition et multiplication par des scalaires du corps fini.

Voir le détail →

C'est ce qu'on appelle le code linéaire $[n, k]_{q}$ .

Génération de matrice

avancéviz

G \in F_{q}^{k \times n} .

Forme équivalente

c = m G .

Convertit un message de symboles $k$ en un mot de code de symboles $n$ .

Voir le détail →

Un message $m \in F_{q}^{k}$ est codé en utilisant

Matrice de contrôle de parité

avancéviz

Une matrice de contrôle $H$ satisfait, pour chaque mot de code $c$

H c^{T} = 0 .

Forme équivalente

H \in F_{q}^{(n - k) \times n} .

De plus, avec les conventions prises en charge pour $G$ et $H$

G H^{T} = 0.

Il définit des contraintes linéaires que chaque mot de code valide doit satisfaire.

Voir le détail →

Syndrome

avancéviz

s = H r^{T} .

Si $r$ est un mot de passe valide

s = 0 .

Forme équivalente

s = H e^{T} .

Résume les contraintes de parité violées par un mot reçu.

Voir le détail →

Si $r = c + e$ , alors

Distance de Hamming et poids

avancéviz

d_{H} (x, y) = ∣ {i : x_{i} \neq = y_{i}} ∣.

Forme équivalente

w_{H} (x) = d_{H} (x, 0) .

Comptez combien de positions diffèrent entre deux mots.

Voir le détail →

Le poids de Hamming est

Distance minimale, détection et correction

avancéviz

d_{m i n} = c_{1} \neq = c_{2} min d_{H} (c_{1}, c_{2}) .

Forme équivalente

d_{m i n} - 1

Forme équivalente

t = ⌊ \frac{d _{m i n} - 1}{2} ⌋

Pour un code linéaire

d_{m i n} = c \neq = 0 min w_{H} (c) .

La séparation entre les mots de code détermine la capacité théorique de détection et de correction.

Voir le détail →

Un code avec une distance minimale $d_{m i n}$ peut détecter jusqu'à

erreurs et corriger

erreurs dans le modèle d’erreur de symbole classique.

Taux d'un code linéaire

avancéviz

R = \frac{k}{n} .

Fraction de symboles dans le mot de code qui représentent des informations indépendantes.

Voir le détail →

Section 28

Codes linéaires et correction d'erreurs

Code linéaire sur un corps fini

avancéviz

Un code linéaire $C$ de longueur $n$ sur $F_{q}$ est un sous-espace vectoriel

C \leq F_{q}^{n} .

Forme équivalente

dim (C) = k,

Un ensemble de mots de code fermés sous addition et multiplication par des scalaires du corps fini.

Voir le détail →

C'est ce qu'on appelle le code linéaire $[n, k]_{q}$ .

Génération de matrice

avancéviz

G \in F_{q}^{k \times n} .

Forme équivalente

c = m G .

Convertit un message de symboles $k$ en un mot de code de symboles $n$ .

Voir le détail →

Un message $m \in F_{q}^{k}$ est codé en utilisant

Matrice de contrôle de parité

avancéviz

Une matrice de contrôle $H$ satisfait, pour chaque mot de code $c$

H c^{T} = 0 .

Forme équivalente

H \in F_{q}^{(n - k) \times n} .

De plus, avec les conventions prises en charge pour $G$ et $H$

G H^{T} = 0.

Il définit des contraintes linéaires que chaque mot de code valide doit satisfaire.

Voir le détail →

Syndrome

avancéviz

s = H r^{T} .

Si $r$ est un mot de passe valide

s = 0 .

Forme équivalente

s = H e^{T} .

Résume les contraintes de parité violées par un mot reçu.

Voir le détail →

Si $r = c + e$ , alors

Distance de Hamming et poids

avancéviz

d_{H} (x, y) = ∣ {i : x_{i} \neq = y_{i}} ∣.

Forme équivalente

w_{H} (x) = d_{H} (x, 0) .

Comptez combien de positions diffèrent entre deux mots.

Voir le détail →

Le poids de Hamming est

Distance minimale, détection et correction

avancéviz

d_{m i n} = c_{1} \neq = c_{2} min d_{H} (c_{1}, c_{2}) .

Forme équivalente

d_{m i n} - 1

Forme équivalente

t = ⌊ \frac{d _{m i n} - 1}{2} ⌋

Pour un code linéaire

d_{m i n} = c \neq = 0 min w_{H} (c) .

La séparation entre les mots de code détermine la capacité théorique de détection et de correction.

Voir le détail →

Un code avec une distance minimale $d_{m i n}$ peut détecter jusqu'à

erreurs et corriger

erreurs dans le modèle d’erreur de symbole classique.

Taux d'un code linéaire

avancéviz

R = \frac{k}{n} .

Fraction de symboles dans le mot de code qui représentent des informations indépendantes.

Voir le détail →