Code préfixe - Prefix code

Un code de préfixe est un type de système de code qui se distingue par sa possession de la "propriété de préfixe", qui exige qu'il n'y ait pas de mot de code entier dans le système qui soit un préfixe (segment initial) d'un autre mot de code dans le système. C'est trivialement vrai pour le code de longueur fixe, donc seulement un point de considération dans le code de longueur variable .

Par exemple, un code avec les mots de code {9, 55} a la propriété prefix; un code composé de {9, 5, 59, 55} ne le fait pas, car "5" est un préfixe de "59" et également de "55". Un code préfixe est un code décodable de manière unique : étant donné une séquence complète et précise, un récepteur peut identifier chaque mot sans avoir besoin d'un marqueur spécial entre les mots. Cependant, il existe des codes uniquement décodables qui ne sont pas des codes de préfixe; par exemple, l'inverse d'un code de préfixe est toujours décodable de manière unique (c'est un code de suffixe), mais ce n'est pas nécessairement un code de préfixe.

Codes préfixes sont également connus comme les codes sans préfixe , codes de condition de préfixe et codes instantanés . Bien que le codage de Huffman ne soit que l'un des nombreux algorithmes pour dériver des codes de préfixe, les codes de préfixe sont également largement appelés «codes de Huffman», même lorsque le code n'a pas été produit par un algorithme de Huffman. Le terme code sans virgule est parfois également utilisé comme synonyme de codes sans préfixe, mais dans la plupart des livres et articles mathématiques (par exemple), un code sans virgule est utilisé pour désigner un code auto-synchronisant , une sous-classe de codes préfixes.

En utilisant des codes de préfixe, un message peut être transmis sous la forme d'une séquence de mots de code concaténés, sans aucun marqueur hors bande ou (en variante) marqueur spécial entre les mots pour encadrer les mots dans le message. Le destinataire peut décoder le message sans ambiguïté, en recherchant et en supprimant à plusieurs reprises des séquences qui forment des mots de code valides. Cela n'est généralement pas possible avec des codes qui ne possèdent pas la propriété de préfixe, par exemple {0, 1, 10, 11}: un récepteur lisant un "1" au début d'un mot de code ne saurait pas s'il s'agit du mot de code complet " 1 ", ou simplement le préfixe du mot de code" 10 "ou" 11 "; ainsi la chaîne "10" pourrait être interprétée soit comme un mot de code unique, soit comme la concaténation des mots "1" puis "0".

Les codes Huffman de longueur variable , les codes d' appel de pays , les parties pays et éditeur des ISBN , les codes de synchronisation secondaires utilisés dans la norme sans fil UMTS W-CDMA 3G et les jeux d'instructions (langage machine) de la plupart des microarchitectures informatiques sont des codes de préfixe.

Les codes de préfixe ne sont pas des codes de correction d'erreur . En pratique, un message peut d'abord être compressé avec un code de préfixe, puis à nouveau codé avec un codage de canal (y compris une correction d'erreur) avant la transmission.

Pour tout code décodable de manière unique, il existe un code de préfixe qui a les mêmes longueurs de mot de code. L'inégalité de Kraft caractérise les ensembles de longueurs de mot de code qui sont possibles dans un code décodable de manière unique .

Techniques

Si chaque mot du code a la même longueur, le code est appelé un code de longueur fixe ou un code de bloc (bien que le terme code de bloc soit également utilisé pour les codes de correction d'erreur de taille fixe dans le codage de canal ). Par exemple, les lettres ISO 8859-15 ont toujours une longueur de 8 bits. Les lettres UTF-32 / UCS-4 ont toujours une longueur de 32 bits. Les cellules ATM ont toujours une longueur de 424 bits (53 octets). Un code de longueur fixe de k bits de longueur fixe peut coder jusqu'à des symboles source. ${\ displaystyle 2 ^ {k}}$

Un code de longueur fixe est nécessairement un code préfixe. Il est possible de transformer n'importe quel code en code de longueur fixe en complétant les symboles fixes avec les préfixes les plus courts afin de respecter la longueur des préfixes les plus longs. En variante, de tels codes de remplissage peuvent être utilisés pour introduire une redondance qui permet une autocorrection et / ou une synchronisation. Cependant, les codages de longueur fixe sont inefficaces dans les situations où certains mots sont beaucoup plus susceptibles d'être transmis que d'autres.

Le codage binaire tronqué est une généralisation simple des codes de longueur fixe pour traiter les cas où le nombre de symboles n n'est pas une puissance de deux. Les symboles source se voient attribuer des mots de code de longueur k et k +1, où k est choisi de telle sorte que 2 ^k <n ≤ 2 ^{k + 1} .

Le codage de Huffman est une technique plus sophistiquée pour construire des codes de préfixe de longueur variable. L'algorithme de codage de Huffman prend en entrée les fréquences que les mots de code devraient avoir et construit un code de préfixe qui minimise la moyenne pondérée des longueurs de mot de code. (Ceci est étroitement lié à la minimisation de l'entropie.) Il s'agit d'une forme de compression de données sans perte basée sur le codage d'entropie .

Certains codes marquent la fin d'un mot de code avec un symbole spécial "virgule", différent des données normales. Ceci est quelque peu analogue aux espaces entre les mots dans une phrase; ils marquent la fin d'un mot et le début d'un autre. Si chaque mot de code se termine par une virgule et que la virgule n'apparaît pas ailleurs dans un mot de code, le code est automatiquement sans préfixe. Cependant, les systèmes de communication modernes envoient tout sous forme de séquences de «1» et «0» - ajouter un troisième symbole serait coûteux, et l'utiliser uniquement à la fin des mots serait inefficace. Le code Morse est un exemple quotidien de code de longueur variable avec une virgule. Les longues pauses entre les lettres et les pauses encore plus longues entre les mots aident les gens à reconnaître où se termine une lettre (ou un mot) et où commence la suivante. De même, le codage de Fibonacci utilise un «11» pour marquer la fin de chaque mot de code.

Les codes d'auto-synchronisation sont des codes préfixes qui permettent la synchronisation des trames .

Concepts associés

Un code de suffixe est un ensemble de mots dont aucun n'est un suffixe d'un autre; de manière équivalente, un ensemble de mots qui sont l'inverse d'un code de préfixe. Comme avec un code de préfixe, la représentation d'une chaîne comme une concaténation de tels mots est unique. Un code bifix est un ensemble de mots qui est à la fois un préfixe et un code suffixe. Un code de préfixe optimal est un code de préfixe avec une longueur moyenne minimale. C'est, supposons un alphabet de n symboles avec des probabilités pour un code de préfixe C . Si C ' est un autre code de préfixe et sont les longueurs des mots de code de C' , alors . ${\ displaystyle p (A_ {i})}$${\ displaystyle \ lambda '_ {i}}$${\ displaystyle \ sum _ {i = 1} ^ {n} {\ lambda _ {i} p (A_ {i})} \ leq \ sum _ {i = 1} ^ {n} {\ lambda '_ { i} p (A_ {i})} \!}$

Codes de préfixe utilisés aujourd'hui

Exemples de codes de préfixe:

• codes Huffman de longueur variable
• indicatifs de pays
• Encodage Chen – Ho
• les parties pays et éditeur des ISBN
• les codes de synchronisation secondaires utilisés dans la norme sans fil UMTS W-CDMA 3G
• Codes VCR Plus +
• Format de transformation Unicode , en particulier le système UTF-8 pour le codage des caractères Unicode , qui est à la fois un code sans préfixe et un code auto-synchronisant
• quantité de longueur variable

Techniques

Les techniques couramment utilisées pour construire des codes de préfixe comprennent les codes de Huffman et les anciens codes Shannon – Fano , ainsi que des codes universels tels que:

• Codage Elias delta
• Codage gamma Elias
• Codage Elias Omega
• Codage de Fibonacci
• Codage Levenshtein
• Codage unaire
• Code du riz Golomb
• Damier chevauchant (technique de cryptographie simple qui produit des codes préfixes)
• Codage binaire

Remarques

Les références

• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Codes et automates . Encyclopédie des mathématiques et ses applications. 129 . Cambridge: Cambridge University Press . ISBN   978-0-521-88831-8 . Zbl   1187.94001 .
• Elias, Peter (1975). "Ensembles universels de mots de code et représentations des entiers". IEEE Trans. Inf. Théorie . 21 (2): 194–203. doi : 10.1109 / tit.1975.1055349 . ISSN   0018-9448 . Zbl   0298.94011 .
• DA Huffman, "A method for the construction of minimum-redundancy codes", Proceedings of the IRE, septembre 1952, pp. 1098-1102 (article original de Huffman)
• Profil: David A. Huffman , Scientific American , septembre 1991, pp. 54-58 (Contexte)
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest et Clifford Stein . Introduction aux algorithmes , deuxième édition. MIT Press et McGraw-Hill, 2001. ISBN   0-262-03293-7 . Section 16.3, pp. 385–392.
•  Cet article incorpore  du matériel du domaine public du document General Services Administration : «Federal Standard 1037C» .

Liens externes

• Codes, arbres et propriété de préfixe par Kona Macphee