Code préfixe

Un code préfixe est un type de système de codage caractérisé par la propriété de préfixe , qui exige qu'aucun mot de code entier du système ne soit le préfixe (segment initial) d'un autre mot de code. Cette propriété est triviale pour les codes de longueur fixe ; elle ne concerne donc que les codes de longueur variable .

Par exemple, un code avec du code ${\displaystyle \{{ exttt {a}},{ exttt {bb}}\ <semantics><mrow><mstyle><mo>{</mo><mrow><mrow><mtext>un</mtext></mrow></mrow><mo>,</mo><mrow><mrow><mtext>bb</mtext></mrow></mrow><mo>}</mo></mstyle></mrow><annotation>{\displaystyle \{{ exttt {a}},{ exttt {bb}}\}}</annotation></semantics></math><img src=$ ${\displaystyle \{{ exttt {a}},{ exttt {b}},{ exttt {ab}},{ exttt {aa}}\ <semantics><mrow><mstyle><mo>{</mo><mrow><mrow><mtext>un</mtext></mrow></mrow><mo>,</mo><mrow><mrow><mtext>b</mtext></mrow></mrow><mo>,</mo><mrow><mrow><mtext>ab</mtext></mrow></mrow><mo>,</mo><mrow><mrow><mtext>aa</mtext></mrow></mrow><mo>}</mo></mstyle></mrow><annotation>{\displaystyle \{{ exttt {a}},{ exttt {b}},{ exttt {ab}},{ exttt {aa}}\}}</annotation></semantics></math><img src=$ « a » est un préfixe de « ab » et de « aa » . Un code préfixe est un code décodable de manière unique : étant donné une séquence complète et exacte, un récepteur peut identifier chaque mot sans avoir besoin d’un marqueur spécial entre les mots. Cependant, il existe des codes décodables de manière unique qui ne sont pas des codes préfixes ; par exemple, l’inverse d’un code préfixe est toujours décodable de manière unique (c’est un code suffixe), mais ce n’est pas nécessairement un code préfixe.

Les codes préfixes sont également appelés codes sans préfixe , codes à condition préfixe ou codes instantanés . Bien que le codage de Huffman ne soit qu'un algorithme parmi d'autres pour dériver des codes préfixes, ces derniers sont souvent désignés par l'expression « codes de Huffman », même lorsqu'ils n'ont pas été produits par un algorithme de Huffman. Le terme « code sans virgule » est parfois employé comme synonyme de « code sans préfixe » , mais dans la plupart des ouvrages et articles mathématiques (par exemple ), un code sans virgule désigne un code auto-synchronisant , une sous-classe des codes préfixes.

Grâce aux codes préfixes, un message peut être transmis sous forme de séquence de mots codés concaténés, sans marqueurs hors bande ni marqueurs spéciaux entre les mots pour les encadrer . Le destinataire peut décoder le message sans ambiguïté en identifiant et en supprimant successivement les séquences qui forment des mots codés valides. Ceci est généralement impossible avec les codes dépourvus de préfixe. ${\displaystyle \{{ exttt {0}},{ exttt {1}},{ exttt {10}},{ exttt {11}}\ <semantics><mrow><mstyle><mo>{</mo><mrow><mrow><mtext>0</mtext></mrow></mrow><mo>,</mo><mrow><mrow><mtext>1</mtext></mrow></mrow><mo>,</mo><mrow><mrow><mtext>10</mtext></mrow></mrow><mo>,</mo><mrow><mrow><mtext>11</mtext></mrow></mrow><mo>}</mo></mstyle></mrow><annotation>{\displaystyle \{{ exttt {0}},{ exttt {1}},{ exttt {10}},{ exttt {11}}\}}</annotation></semantics></math><img src=$ 1 au début d'un mot de code ne saurait pas s'il s'agit du mot de code complet 1 , ou simplement du préfixe du mot de code 10 ou 11 ; la chaîne 10 pourrait donc être interprétée soit comme un seul mot de code, soit comme la concaténation des mots 1 puis 0 .

Les codes Huffman de longueur variable , les indicatifs téléphoniques de pays , les parties pays et éditeur des ISBN , les codes de synchronisation secondaire 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 correcteurs d'erreurs . En pratique, un message peut d'abord être compressé avec un code de préfixe, puis réencodé avec un codage de canal (incluant la correction d'erreurs) avant transmission.

À chaque code décodable de manière unique correspond un code préfixe dont les longueurs de mots de code sont identiques. L'inégalité de Kraft caractérise les ensembles de longueurs de mots de code possibles dans un code décodable de manière unique.

Techniques

Si tous les mots d'un code ont la même longueur, on parle de code à longueur fixe ou de code par blocs (bien que le terme « code par blocs » soit également utilisé pour les codes correcteurs d'erreurs de taille fixe dans le codage de canal ). Par exemple, les caractères ISO 8859-15 font toujours 8 bits. Les caractères UTF-32/UCS-4 font toujours 32 bits. Les cellules ATM font toujours 424 bits (53 octets). Un code à longueur fixe de longueur fixe ${\displaystyle k <semantics><mrow><mstyle><mi>k</mi></mstyle></mrow><annotation>{\displaystyle k}</annotation></semantics></math><img src=$ ${\displaystyle 2^{k <semantics><mrow><mstyle><msup><mn>2</mn><mrow><mi>k</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle 2^{k}}</annotation></semantics></math><img src=$

Un code à longueur fixe est nécessairement un code préfixe. Il est possible de transformer n'importe quel code en un code à longueur fixe en ajoutant des symboles fixes aux préfixes les plus courts afin d'atteindre la longueur des préfixes les plus longs. Ces codes de remplissage peuvent également servir à introduire une redondance permettant l'autocorrection et/ou la synchronisation. Cependant, les codages à longueur fixe sont inefficaces lorsque 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 permettant de traiter les cas où le nombre de symboles n n'est pas une puissance de deux. Les symboles sources se voient attribuer des mots de code de longueur n. ${\displaystyle k <semantics><mrow><mstyle><mi>k</mi></mstyle></mrow><annotation>{\displaystyle k}</annotation></semantics></math><img src=$ ${\displaystyle k+1 <semantics><mrow><mstyle><mi>k</mi><mo>+</mo><mn>1</mn></mstyle></mrow><annotation>{\displaystyle k+1}</annotation></semantics></math><img src=$ ${\displaystyle k <semantics><mrow><mstyle><mi>k</mi></mstyle></mrow><annotation>{\displaystyle k}</annotation></semantics></math><img src=$ ${\displaystyle 2^{k}<n\leq 2^{k+1 <semantics><mrow><mstyle><msup><mn>2</mn><mrow><mi>k</mi></mrow></msup><mo><</mo><mi>n</mi><mo>≤</mo><msup><mn>2</mn><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msup></mstyle></mrow><annotation>{\displaystyle 2^{k}<n\leq 2^{k+1}}</annotation></semantics></math><img src=$

Le codage de Huffman est une technique plus sophistiquée pour construire des codes préfixes de longueur variable. L'algorithme de codage de Huffman prend en entrée les fréquences que doivent avoir les mots de code et construit un code préfixe qui minimise la moyenne pondérée des longueurs des mots de code (ce qui 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 entropique .

Certains codes marquent la fin d'un mot codé par un symbole spécial, la virgule (également appelée valeur sentinelle ), différent des données normales. Ceci est comparable aux espaces entre les mots dans une phrase ; ils indiquent où un mot se termine et où le suivant commence. Si chaque mot codé se termine par une virgule, et que la virgule n'apparaît pas ailleurs dans le mot codé, le code est automatiquement sans préfixe. Cependant, réserver un symbole entier uniquement pour la virgule peut s'avérer inefficace, notamment pour les langues ayant un nombre réduit de symboles. Le code Morse est un exemple courant de code à longueur variable avec virgule. Les longues pauses entre les lettres, et les pauses encore plus longues entre les mots, permettent de reconnaître où une lettre (ou un mot) se termine et où le suivant commence. De même, le codage de Fibonacci utilise le chiffre 11 pour marquer la fin de chaque mot codé.

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

Concepts connexes

Un code suffixe est un ensemble de mots dont aucun n'est le suffixe d'un autre ; de manière équivalente, un ensemble de mots qui est l'inverse d'un code préfixe. Comme pour un code préfixe, la représentation d'une chaîne comme concaténation de tels mots est unique. Un code bifixe est un ensemble de mots qui est à la fois un code préfixe et un code suffixe. Un code préfixe optimal est un code préfixe de longueur moyenne minimale. Autrement dit, considérons un alphabet de ${\displaystyle p(A_{i}) <mrow><mstyle><msubsup><mi>λ</mi><mrow><mi>je</mi></mrow><mo>′</mo></msubsup></mstyle></mrow><annotation>{\displaystyle \lambda '_{i}}</annotation></semantics></math><img src=$ ${\displaystyle \sum _{i=1}^{n}{\lambda _{i}p(A_{i})}\leq \sum _{i=1}^{n}{\lambda '_{i}p(A_{i})}\! </span referrerpolicy=$ .

Codes préfixes utilisés aujourd'hui

Exemples de codes préfixes :

codes de Huffman à longueur variable
indicatifs téléphoniques de pays
Codage de 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 l'encodage des caractères Unicode , qui est à la fois un code sans préfixe et un code auto-synchronisant
Préfixes d'opcode utilisés dans les jeux d'instructions informatiques
quantité de longueur variable

Techniques

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

Codage delta d'Elias
Codage gamma d'Elias
Codage oméga d'Elias
Codage de Fibonacci
Codage de Levenshtein
Codage unaire
Code Golomb Rice
Damier à cheval (technique de cryptographie simple qui produit des codes préfixes)
codage binaire