Code d'expansion

théorie du codage , les codes expanseurs forment une classe de codes correcteurs d'erreurs construits à partir de graphes expanseurs bipartis . Avec les codes de Justesen , les codes expanseurs présentent un intérêt particulier car ils possèdent un taux positif constant , une distance relative positive constante et une taille d'alphabet constante . En effet, l'alphabet ne contient que deux éléments ; les codes expanseurs appartiennent donc à la classe des codes binaires . De plus, le codage et le décodage des codes expanseurs s'effectuent en un temps proportionnel à la longueur des blocs du code.

théorie du codage , un code expanseur est un code linéaire par blocs dont la matrice de contrôle de parité est la matrice d'adjacence d'un graphe expanseur biparti . Ces codes présentent une bonne distance relative , où et sont des propriétés du graphe expanseur définies ultérieurement, un taux et une décodabilité élevée (des algorithmes de temps d'exécution existent).

Définition

Soit un graphe birégulier entre un ensemble de nœuds , appelés variables , et un ensemble de nœuds , appelés contraintes .

Soit une fonction conçue de sorte que, pour chaque contrainte , les variables voisines soient .

Soit un code correcteur d'erreurs de longueur de bloc . Le code expanseur est le code de longueur de bloc dont les mots de code sont les mots tels que, pour , est un mot de code de .

Il a été démontré que des graphes expanseurs sans perte non triviaux existent. De plus, nous pouvons les construire explicitement.

Taux

Le taux de est égal à sa dimension divisée par la longueur de son bloc. Dans ce cas, la matrice de contrôle de parité a une taille , et donc un taux d'au moins .

Distance

Supposons que . Alors la distance d'un code d'expansion est au moins .

Preuve

Notons que l'on peut considérer chaque mot de code de comme un sous-ensemble de sommets , en définissant le sommet si et seulement si l' indice i du mot de code est égal à 1. est alors un mot de code si chaque sommet est adjacent à un nombre pair de sommets de . (Pour qu'un sommet soit un mot de code, il faut que , où est la matrice de parité. Chaque sommet de correspond alors à chaque colonne de . La multiplication matricielle sur donne le résultat souhaité.) Ainsi, si un sommet est adjacent à un seul sommet de , on sait immédiatement qu'il ne s'agit pas d'un mot de code. Soit l'ensemble des voisins de dans , et soit l'ensemble des voisins uniques de , c'est-à-dire adjacents à un seul sommet de .

Lemme 1

Pour chaque taille , .

Preuve

De façon triviale, , puisque implique . Il en découle que le degré de chaque sommet de est . Par la propriété d'expansion du graphe, il existe nécessairement un ensemble d' arêtes menant à des sommets distincts. Les arêtes restantes rendent au plus voisins non uniques, donc .

Corollaire

Tout objet suffisamment petit possède un voisin unique. Ceci découle du fait que …

Lemme 2

Chaque sous-ensemble possède un voisin unique.

Preuve

Le lemme 1 démontre le cas , donc supposons . Soit tel que . D'après le lemme 1, on sait que . Alors un sommet appartient à si , et on sait que , donc d'après la première partie du lemme 1, on sait que . Puisque , , et donc n'est pas vide. $|T|>\gamma n\, 2 (1 - ε) γ n > | T | > γ n$

Corollaire

Notez que si a possède au moins un voisin unique, c'est-à-dire , alors le mot correspondant à ne peut pas être un mot de code, car le produit de la matrice de parité ne donnera pas un vecteur nul. D'après le raisonnement précédent, . Puisque est linéaire, nous concluons que a une distance d'au moins . $0\, | U (T) | > 0$

Codage

Le temps d'encodage d'un code expanseur est majoré par celui d'un code linéaire général , par multiplication matricielle. Un résultat de Spielman montre que l'encodage est possible en un temps O(n).

Décodage

Le décodage des codes expanseurs est possible dans le temps en utilisant l'algorithme suivant.

Soit le sommet de qui correspond à l' indice dans les mots de code de . Soit un mot reçu, et . Soit , et soit . Considérons alors l' algorithme glouton :

Entrée : mot reçu .

Initialiser y' à y alors qu'il existe un av dans R adjacent à un nombre impair de sommets dans V(y') s'il existe un i tel que o(i) > e(i) entrée flip i dans y' autre échouer

Résultat : échec ou mot de code modifié .

Preuve

Nous démontrons d'abord la validité de l'algorithme, puis nous examinons son temps d'exécution.

Exactitude

Nous devons démontrer que l'algorithme se termine avec le mot de code correct lorsque le mot de code reçu se situe à moins de la moitié de la distance de code du mot de code original. Soit l'ensemble des variables corrompues , et l'ensemble des sommets non satisfaits (adjacents à un nombre impair de sommets) de . Le lemme suivant s'avérera utile.

Lemme 3

Si , alors il existe un avec . $e(i)\, o (i) > e (i)$

Preuve

D'après le lemme 1, on sait que . Donc, un sommet moyen possède au moins voisins uniques (rappelons que les voisins uniques sont insatisfaits et contribuent donc à ), puisque , et il existe donc un sommet avec . $d/2\, d (1 - 2 ε) > d / 2$

Donc, si nous n'avons pas encore atteint un mot de code, il y aura toujours un sommet à inverser. Ensuite, nous montrons que le nombre d'erreurs ne peut jamais dépasser une certaine valeur .

Lemme 4

Si nous commençons par , alors nous n'atteignons jamais à aucun point de l'algorithme.

Preuve

Lorsqu'on inverse un sommet , et que et sont intervertis, et puisque nous avions , cela signifie que le nombre de sommets non satisfaits à droite diminue d'au moins une unité après chaque inversion. Puisque , le nombre initial de sommets non satisfaits est au plus , d'après la -régularité du graphe . Si nous atteignions une chaîne avec des erreurs, alors, d'après le lemme 1, il y aurait au moins voisins uniques, ce qui signifie qu'il y aurait au moins sommets non satisfaits, une contradiction. $e(i)\, o (i) > e (i)$

Les lemmes 3 et 4 montrent que si l'on part d' une distance égale à la moitié de celle de l' algorithme, on trouvera toujours un sommet à inverser. Chaque inversion réduit d'au moins 1 le nombre de sommets non satisfaits dans l'algorithme, et par conséquent, ce dernier se termine en au plus n étapes, et il se termine sur un mot de code, d'après le lemme 3. (S'il ne s'arrêtait pas à un mot de code, il y aurait toujours un sommet à inverser). Le lemme 4 montre que l'on ne peut jamais être à plus de n du mot de code correct. Puisque le code a une distance n ≥ n (car n ≥ n ), le mot de code sur lequel il se termine est nécessairement le mot de code correct, puisque le nombre d'inversions de bits est inférieur à la moitié de la distance (on n'aurait donc pas pu aller assez loin pour atteindre un autre mot de code). $\gamma n\, 2 (1 - ε) γ n > γ n$

Complexité

Nous démontrons maintenant que l'algorithme permet un décodage en temps linéaire. Soit une constante, et soit le degré maximal de tout sommet de . Notons que est également constant pour les constructions connues.

Prétraitement : Il faut du temps pour calculer si chaque sommet a un nombre impair ou pair de voisins.
Prétraitement 2 : Nous prenons le temps de calculer une liste de sommets dans lesquels ont . $e(i)\, o (i) > e (i)$
À chaque itération : on supprime simplement le premier élément de la liste. Pour mettre à jour la liste des sommets pairs/impairs , il suffit de modifier les entrées, en insérant ou en supprimant les éléments nécessaires. On met ensuite à jour les entrées de la liste des sommets ayant plus de voisins impairs que pairs, en insérant ou en supprimant les éléments nécessaires. Chaque itération a donc une durée O(n).
Comme indiqué ci-dessus, le nombre total d'itérations est au plus de .

Cela donne un temps d'exécution total de temps, où et sont des constantes.