Codi prefix

Un codi prefix és un tipus de sistema de codi que es distingeix per la seva possessió de la propietat prefix, que requereix que no hi hagi cap paraula de codi sencera al sistema que sigui un prefix (segment inicial) de cap altra paraula de codi del sistema. És trivialment cert per a codis de longitud fixa, per tant només és un punt a considerar per a codis de longitud variable.^[1]

Per exemple, un codi amb codi ${\displaystyle \{{\texttt {9}},{\texttt {55}}\}}$ té la propietat de prefix; un codi que consisteix en ${\displaystyle \{{\texttt {9}},{\texttt {5}},{\texttt {59}},{\texttt {55}}\}}$ no ho fa, perquè 5 és un prefix de 59 i també de 55. Un codi de prefix és un codi descodificable de manera única: donada una seqüència completa i precisa, un receptor pot identificar cada paraula sense necessitat d'un marcador especial entre les paraules. Tanmateix, hi ha codis descodificables de manera única que no són codis de prefix; per exemple, el revers d'un codi de prefix encara és descodificable de manera única (és un codi de sufix), però no és necessàriament un codi de prefix.

Els codis de prefix també es coneixen com a codis sense prefix, codis de condició de prefix i codis instantanis . Tot i que la codificació de Huffman és només un dels molts algorismes per derivar codis de prefix, els codis de prefix també es coneixen àmpliament com a "codis de Huffman", fins i tot quan el codi no va ser produït per un algorisme de Huffman. El terme codi sense comes de vegades també s'aplica com a sinònim de codis sense prefix,^[2][3] però a la majoria de llibres i articles matemàtics (per exemple,)^[4] un codi sense comes s'utilitza per referir-se a un codi autosincronitzant, una subclasse de codis de prefix.

Mitjançant codis de prefix, un missatge es pot transmetre com una seqüència de paraules de codi concatenades, sense marcadors fora de banda ni (alternativament) marcadors especials entre paraules per emmarcar-les en el missatge. El destinatari pot descodificar el missatge sense ambigüitats, trobant i eliminant repetidament seqüències que formen paraules de codi vàlides. Això generalment no és possible amb codis que no tenen la propietat de prefix, per exemple. ${\displaystyle \{{\texttt {0}},{\texttt {1}},{\texttt {10}},{\texttt {11}}\}}$ un receptor que llegeix un 1 al principi d'una paraula de codi no sabria si aquesta era la paraula de codi completa , 1 o simplement el prefix de la paraula clau 10 o 11; de manera que la cadena es podria interpretar com una sola paraula clau o com la concatenació de les paraules 1 llavors 0.

Els codis Huffman de longitud variable, els codis de trucades de país, les parts de país i editor dels ISBN, els codis de sincronització secundària utilitzats en l'estàndard sense fil UMTS W-CDMA 3G i els conjunts d'instruccions (llenguatge màquina) de la majoria de microarquitectures informàtiques són codis de prefix.

Els codis de prefix no són codis correctors d'errors. A la pràctica, un missatge es pot comprimir primer amb un codi de prefix i després codificar-se de nou amb codificació de canal (inclosa la correcció d'errors) abans de la transmissió.

Per a cada codi descodificable de manera única hi ha un codi prefix que té les mateixes longituds de paraula de codi.^[5] La desigualtat de Kraft caracteritza els conjunts de longituds de paraules de codi que són possibles en un codi descodificable de manera única.

Si totes les paraules del codi tenen la mateixa longitud, el codi s'anomena codi de longitud fixa o codi de bloc (tot i que el terme codi de bloc també s'utilitza per a codis correctors d'errors de mida fixa en la codificació de canals). Per exemple, les lletres ISO 8859-15 sempre tenen una longitud de 8 bits. Les lletres UTF-32/UCS-4 sempre tenen una longitud de 32 bits. Les cel·les ATM sempre tenen una longitud de 424 bits (53 bytes). Un codi de longitud fixa de longitud fixa ${\displaystyle k}$ els bits poden codificar fins a ${\displaystyle 2^{k}}$ símbols de font.

Un codi de longitud fixa és necessàriament un codi de prefix. És possible convertir qualsevol codi en un codi de longitud fixa omplint símbols fixos als prefixos més curts per tal de complir amb la longitud dels prefixos més llargs. Alternativament, aquests codis d'ompliment es poden utilitzar per introduir redundància que permeti l'autocorrecció i/o la sincronització. Tanmateix, les codificacions de longitud fixa són ineficients en situacions en què algunes paraules tenen moltes més probabilitats de ser transmeses que d'altres.

La codificació binària truncada és una generalització senzilla dels codis de longitud fixa per tractar casos on el nombre de símbols n no és una potència de dos. Als símbols font se'ls assignen paraules de codi de longitud ${\displaystyle k}$ i ${\displaystyle k+1}$, on ${\displaystyle k}$ s'escull de manera que ${\displaystyle 2^{k}<n\leq 2^{k+1}}$ .

La codificació de Huffman és una tècnica més sofisticada per construir codis de prefix de longitud variable. L'algorisme de codificació de Huffman pren com a entrada les freqüències que haurien de tenir les paraules de codi i construeix un codi de prefix que minimitza la mitjana ponderada de les longituds de les paraules de codi. (Això està estretament relacionat amb la minimització de l'entropia.) Aquesta és una forma de compressió de dades sense pèrdues basada en la codificació d'entropia.

Alguns codis marquen el final d'una paraula de codi amb un símbol especial de "coma" (també anomenat valor Sentinel), diferent de les dades normals.^[6] Això és una mica anàleg als espais entre paraules d'una frase; marquen on acaba una paraula i comença una altra. Si cada paraula de codi acaba en coma, i la coma no apareix en cap altre lloc d'una paraula de codi, el codi automàticament no té prefixos. Tanmateix, reservar un símbol sencer només per al seu ús com a coma pot ser ineficient, especialment per a idiomes amb un nombre reduït de símbols. El codi Morse és un exemple quotidià d'un codi de longitud variable amb coma. Les pauses llargues entre lletres, i les pauses encara més llargues entre paraules, ajuden a la gent a reconèixer on acaba una lletra (o paraula) i comença la següent. De la mateixa manera, la codificació de Fibonacci utilitza un per marcar el final de cada paraula de codi.

Els codis autosincronitzants són codis de prefix que permeten la sincronització de trames.