Code de Golay

Code de Golay
Page d'aide sur l'homonymie Pour les articles homonymes, voir Golay.

En théorie des codes, un code de Golay est un code correcteur d'erreurs pouvant être binaire ou tertiaire, nommé en l'honneur de son inventeur, Marcel Golay. Il y a deux types de code de Golay binaire. Le code binaire étendu de Golay encode 12 bits de données dans un mot de code de 24 bits de long de telle manière que n'importe quelle erreur sur trois bits puisse être corrigée et n'importe quelle erreur sur quatre bits puisse être détectée. L'autre, le code binaire parfait de Golay, a des mots de code de 23 bits de long et est obtenu à partir du code binaire prolongé de Golay en supprimant une position dans les coordonnées (réciproquement, le code binaire étendu de Golay est obtenu à partir du code binaire parfait de Golay en ajoutant un bit de parité).

Sommaire

Code de Golay binaire

Définition mathématique

Article détaillé : Code correcteur.

En termes mathématiques, le code binaire étendu de Golay se compose d'un sous-espace vectoriel à 12 dimensions W de l'espace V=F224 des mots de 24 bits tels que deux éléments distincts de W diffèrent dans au moins huit coordonnées ou, d'une manière équivalente, telles que n'importe quel élément de W différent de zéro possède au moins huit coordonnées différentes de zéro.

  • Les ensembles possibles de coordonnées différentes de zéro, sous-ensembles de W, se disent mots du code. Dans le code binaire étendu de Golay, tous les mots de code ont un poids de Hamming de 0, 8, 12, 16 ou 24.
  • Jusqu'au réétiquetage des coordonnées, W est unique.

Le code binaire de Golay est un code parfait. Autrement dit, les boules fermées de rayon trois autour des mots du code forment une partition de l'espace vectoriel.

Constructions

  1. Code lexicographique : Classer les vecteurs dans V par ordre lexicographique. En commençant par w1 = 0, définir w2, w3, ..., w12 par la règle que wn est le plus petit nombre entier qui diffère de toutes les combinaisons linéaires des éléments précédents dans au moins huit coordonnées. Alors W peut être défini comme l'ensemble généré par w1, ..., w12.
  2. Code de résidu quadratique : Considérer l'ensemble N des non-résidus quadratiques (mod 23). C'est un sous-ensemble de 11 éléments du groupe cyclique Z/23Z. Considérer les translations t+N de ce sous-ensemble. Augmenter chaque translation à un ensemble St de 12 éléments en ajoutant un élément ∞. Étiqueter les éléments de la base de V par 0, 1, 2..., 22 ∞, W peut être défini l'ensemble généré par les mots St ainsi que le mot se composant de tous les vecteurs de base. (Le code parfait est obtenu en omettant ∞.)
  3. Comme code cyclique : Le code parfait de G23 peut être construit par l'intermédiaire de la factorisation de x23 − 1 . C'est le code produit par x11 + x10 + x6 + x5 + x4 + x2 + 1 / x23 − 1
  4. Le générateur "Miracle Octad Generator" de R. T. Curtis : Ceci emploie des cellules carrés 4×6 pour décrire les 759 mots de code qui ont un poids de Hamming de 8, ou des "octads," du code binaire étendu de Golay. Les mots de code restants sont obtenus par l'intermédiaire des différences symétriques des sous-ensembles des 24 cellules -- c.-à-d., par addition binaire. Pour des détails, voir la géométrie de la place 4×4.

Code de Golay ternaire

Il y a deux codes correcteurs d'erreurs étroitement liés connus sous le nom de codes ternaires de Golay. Le code plus connu en tant que code ternaire de Golay est un code linéaire ternaire parfait (11, 6, 5) ; le code ternaire étendu de Golay est un code linéaire (12, 6, 6) obtenu en ajoutant un chiffre-clé de somme zéro au code (11, 6, 5).

L'énumérateur complet de poids du code ternaire étendu de Golay est

x12 + y12 + z12 + 22(x6y6 + y6z6 + z6x6) + 220(x6y3z3 + y6z3x3 + z6x3y3).

Le code ternaire parfait de Golay peut être construit comme le code de résidu quadratique de longueur 11 sur le corps fini F3.

Le groupe d'automorphisme du code ternaire étendu de Golay est 2.M12, où M12 est un groupe de Mathieu.

Considérer tous les codewords du code étendu qui ont seulement six chiffres non nuls. Les ensembles de positions auxquelles ces chiffres non nuls se trouvent forment le système de Steiner S(5, 6, 12).

Référence

  • J. H. Conway and N. J. A. Sloane. Sphere Packings, Lattices and Groups, Springer-Verlag, New York, Berlin, Heidelberg, 1988.

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Code de Golay de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Code De Golay — En théorie des codes, un code de Golay est un code correcteur d erreurs pouvant être binaire ou tertiaire, nommé en l honneur de son inventeur, Marcel J. E. Golay. Il y a deux types de code de Golay binaire. Le code binaire étendu de Golay encode …   Wikipédia en Français

  • Code de golay — En théorie des codes, un code de Golay est un code correcteur d erreurs pouvant être binaire ou tertiaire, nommé en l honneur de son inventeur, Marcel J. E. Golay. Il y a deux types de code de Golay binaire. Le code binaire étendu de Golay encode …   Wikipédia en Français

  • Code MDS — Code parfait et code MDS Un code parfait (ou code MDS, pour maximum distance séparable) est un concept de la théorie des codes et qui traite plus spécifiquement des codes correcteurs. Un code correcteur est un code permettant au récepteur de… …   Wikipédia en Français

  • Code Parfait Et Code MDS — Un code parfait (ou code MDS, pour maximum distance séparable) est un concept de la théorie des codes et qui traite plus spécifiquement des codes correcteurs. Un code correcteur est un code permettant au récepteur de détecter ou de corriger des… …   Wikipédia en Français

  • Code parfait — et code MDS Un code parfait (ou code MDS, pour maximum distance séparable) est un concept de la théorie des codes et qui traite plus spécifiquement des codes correcteurs. Un code correcteur est un code permettant au récepteur de détecter ou de… …   Wikipédia en Français

  • Code parfait et code mds — Un code parfait (ou code MDS, pour maximum distance séparable) est un concept de la théorie des codes et qui traite plus spécifiquement des codes correcteurs. Un code correcteur est un code permettant au récepteur de détecter ou de corriger des… …   Wikipédia en Français

  • Golay code — may refer to:* Binary Golay code * Ternary Golay code …   Wikipedia

  • Code parfait et code MDS — Un code parfait (ou code MDS, pour maximum distance séparable) est un concept de la théorie des codes et qui traite plus spécifiquement des codes correcteurs. Un code correcteur est un code permettant au récepteur de détecter ou de corriger des… …   Wikipédia en Français

  • Golay — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Code de Golay, un code correcteur Cellule de Golay  (en), un détecteur en spectroscopie infrarouge Filtre électronique de Stavitzky Golay  …   Wikipédia en Français

  • Code Correcteur — Un code correcteur est une technique de codage basée sur la redondance. Elle est destinée à corriger les erreurs de transmission d une information (plus souvent appelée message) sur une voie de communication peu fiable. La théorie des codes… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”