Còdic prefixe

Un còdic prefixe és un còdic, generalment un còdic de llongitut variable, en la "propietat de prefix": cap paraula de còdic és prefix de qualsevol atra paraula de còdic del conjunt. Un còdic en les paraules de còdic {0, 10, 11} té la propietat de prefix; un còdic {0, 1, 10, 11} no la té, perque "1" és prefix de tant "10" com "11".

Als còdics prefixe també se'ls coneix com a còdics sense prefix i còdics instantàneus. Encara que la codificació Huffman és només un dels molts algoritmes per a obtindre còdics prefixe, als còdics prefixe també se'ls crida còdics Huffman, inclús quan el còdic no es va generar en un algoritme Huffman.

Usant còdics prefixe, un mensage pot transmetre's com una seqüència de paraules de còdic concatenades, sense cap senyal fòra de banda per a distinguir les paraules del mensage. El receptor pot descodificar el mensage sense ambigüitat, trobant i llevant repetidament els prefixos que formen una paraula de còdic vàlida. Açò no és possible en còdics que no tenen la propietat de prefix, com en l'eixemple de {0, 1, 10, 11}: un receptor que llegira un "1" al principi d'una paraula de còdic no sabria si este és la paraula de còdic completa "1" o si és simplement el prefix de la paraula de còdic "10" o "11".

Els còdics Huffman de llongitut variable, els prefixos telefònics internacionals, les parts del país i l'editorial del ISBN i els còdics de sincronisació secundària usats en l'estàndart inalàmbric 3G UMTS W-CDMA són còdics prefixe. Els còdics prefixe també són una forma de codificació d'entropía usats en compressió de senyes sense pèrdues.

Els còdics prefixe no són còdics correctors d'error. En la pràctica, un mensage pot estar comprimit primer en un còdic prefixe, i despuix codificar-se de nou (en un còdic de correcció d'errors) abans de la transmissió.

Tècniques

Les tècniques per a construir un còdic prefixe poden ser simples, o prou complicades.

Si cada paraula en el còdic té la mateixa llongitut, el còdic es diu còdic de llongitut fixa. Per eixemple, les lletres del ISO 8859-15 són sempre de 8 bits de llongitut. Les lletres del UTF-32/UCS-4 són sempre de 32 bits de llongitut. Els paquets ATM són sempre de 424 bits de llongitut. Els prefixos no poden existir en un còdic de llongitut fixa. Desafortunadament, la codificació de llongitut fixa és ineficiente en situacions a on algunes paraules són molt més provables de ser transmeses que unes atres.

Alguns còdics de llongitut variable senyalen el final d'una paraula de còdic en un símbol especial. Est és d'alguna manera anàlec al punt del final d'una frase; marca a on acaba una frase i comença la següent. Si cada paraula de còdic acaba en un símbol especial, i el símbol especial no apareix en la paraula de còdic, és un còdic sense prefix. No obstant, els sistemes de comunicació moderns envien tot com a seqüències de "0" i "1" – afegir un tercer símbol seria car, i usar-ho només al final de les paraules seria ineficiente. El còdic Morse és un eixemple quotidià d'un còdic de llongitut variable en un símbol especial. Les pauses llargues entre lletres, i les pauses encara més llargues entre paraules, ajuden a la gent a reconéixer a on una lletra (o paraula) acaba, i a on comença la següent.

La codificació Huffman és una tècnica més sofisticada per a construir còdics prefixe de llongitut variable. L'algoritme de codificació Huffman pren com a entrada les freqüències que les paraules de còdic derían tindre, i construïx un còdic prefixe que minimisa la mija ponderada de la llongitut de les paraules de còdic.

La desigualtat de Kraft caracterisa els conjunts de llongituts de paraules de còdic que són possibles en un còdic prefixe.

Còdics prefixe en us hui en dia

El sistema UTF-8 per a codificar caràcters Unicode usant entre un i quatre bytes per caràcter pot vore's com una forma de codificació prefixe, com també els còdics VCR Plus+ i el sistema de còdics telefònics dels països per a la telefonia internacional.

Entre les tècniques comunament usades per a construir còdics prefixe es troben la codificació Shannon-Fano, la codificació Huffman, i els còdics universals en la codificació delta d'Elias, la codificació gamma d'Elias, la codificació omega d'Elias, la codificació Fibonacci, i la codificació Levenshtein.

Referències

• P. Elias, Universal codeword sets and representations of integers, IEEE Trans. Inform. Theory 21 (2) (1975) 194-203.
• D.A. Huffman, "A method for the construction of minimum-redundancy codes" (PDF), Proceedings of the I.R.E., Sept. 1952, pp. 1098-1102 (artícul original de Huffman)
• Profile: David A. Huffman, Scientific American, Sept. 1991, pp. 54-58 (Història dels antecedents)
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 16.3, pp.385–392.