Código de prefijo

Un código de prefijo es un tipo de sistema de códigos que se distingue por poseer la "propiedad de prefijo", que requiere que no exista ninguna palabra de código completa en el sistema que sea un prefijo (segmento inicial) de cualquier otra palabra de código en el sistema. Esto es trivialmente cierto para los códigos de longitud fija, por lo que solo es un punto a considerar para los códigos de longitud variable .

Por ejemplo, un código con código {9, 55} tiene la propiedad de prefijo; un código que consiste en {9, 5, 59, 55} no la tiene, porque "5" es un prefijo de "59" y también de "55". Un código de prefijo es un código decodificable de forma única : dada una secuencia completa y precisa, un receptor puede identificar cada palabra sin necesidad de un marcador especial entre las palabras. Sin embargo, hay códigos decodificables de forma única que no son códigos de prefijo; por ejemplo, el reverso de un código de prefijo sigue siendo decodificable de forma única (es un código de sufijo), pero no es necesariamente un código de prefijo.

Los códigos de prefijo también se conocen como códigos sin prefijo , códigos de condición de prefijo y códigos instantáneos . Aunque la codificación de Huffman es solo uno de los muchos algoritmos para derivar códigos de prefijo, los códigos de prefijo también se conocen ampliamente como "códigos de Huffman", incluso cuando el código no fue producido por un algoritmo de Huffman. El término código sin comas a veces también se aplica como sinónimo de códigos sin prefijo ^{[1] [2]} pero en la mayoría de los libros y artículos matemáticos (por ejemplo, ^{[3] [4]} ) un código sin comas se usa para significar un código autosincronizado , una subclase de códigos de prefijo.

Mediante códigos de prefijo, un mensaje puede transmitirse como una secuencia de palabras de código concatenadas, sin ningún marcador fuera de banda o (alternativamente) marcadores especiales entre palabras para enmarcar las palabras en el mensaje. El receptor puede decodificar el mensaje sin ambigüedades, al buscar y eliminar repetidamente secuencias que formen palabras de código válidas. Esto no es generalmente posible con códigos que carecen de la propiedad de prefijo, por ejemplo {0, 1, 10, 11}: un receptor que lea un "1" al comienzo de una palabra de código no sabría si esa era la palabra de código completa "1", o simplemente el prefijo de la palabra de código "10" o "11"; por lo tanto, la cadena "10" podría interpretarse como una sola palabra de código o como la concatenación de las palabras "1" y "0".

Los códigos Huffman de longitud variable , los códigos de llamada de país , las partes de país y editor de los ISBN , los códigos de sincronización secundaria utilizados en el estándar inalámbrico UMTS W-CDMA 3G y los conjuntos de instrucciones (lenguaje de máquina) de la mayoría de las microarquitecturas de computadora son códigos de prefijo.

Los códigos de prefijo no son códigos de corrección de errores . En la práctica, un mensaje puede comprimirse primero con un código de prefijo y luego codificarse nuevamente con codificación de canal (incluida la corrección de errores) antes de su transmisión.

Para cualquier código decodificable de forma única existe un código de prefijo que tiene la misma longitud de palabra de código. ^[5] La desigualdad de Kraft caracteriza los conjuntos de longitudes de palabras de código que son posibles en un código decodificable de forma única . ^[6]

Si cada palabra del código tiene la misma longitud, el código se denomina código de longitud fija o código de bloque (aunque el término código de bloque también se utiliza para códigos de corrección de errores de tamaño fijo en la codificación de canal ). Por ejemplo, las letras ISO 8859-15 siempre tienen una longitud de 8 bits. Las letras UTF-32/UCS-4 siempre tienen una longitud de 32 bits. Las celdas ATM siempre tienen una longitud de 424 bits (53 bytes). Un código de longitud fija de k bits de longitud fija puede codificar hasta símbolos de origen.${\estilo de visualización 2^{k}}$

Un código de longitud fija es necesariamente un código de prefijo. Es posible convertir cualquier código en un código de longitud fija rellenando con símbolos fijos los prefijos más cortos para que coincidan con la longitud de los prefijos más largos. Alternativamente, dichos códigos de relleno pueden emplearse para introducir redundancia que permita la autocorrección y/o sincronización. Sin embargo, las codificaciones de longitud fija son ineficientes en situaciones en las que es mucho más probable que se transmitan algunas palabras que otras.

La codificación binaria truncada es una generalización sencilla de los códigos de longitud fija para tratar casos en los que el número de símbolos n no es una potencia de dos. A los símbolos fuente se les asignan palabras de código de longitud k y k +1, donde k se elige de modo que 2 ^k < n ≤ 2 ^k+1 .

La codificación de Huffman es una técnica más sofisticada para construir códigos de prefijo de longitud variable. El algoritmo de codificación de Huffman toma como entrada las frecuencias que deberían tener las palabras de código y construye un código de prefijo que minimiza el promedio ponderado de las longitudes de las palabras de código. (Esto está estrechamente relacionado con la minimización de la entropía). Esta es una forma de compresión de datos sin pérdida basada en la codificación de entropía .

Algunos códigos marcan el final de una palabra de código con un símbolo especial de "coma" (también llamado valor Sentinel ), diferente de los datos normales. ^[7] Esto es algo análogo a los espacios entre palabras en una oración; marcan dónde termina una palabra y comienza otra. Si cada palabra de código termina en una coma, y ​​la coma no aparece en otra parte de una palabra de código, el código está automáticamente libre de prefijo. Sin embargo, reservar un símbolo completo solo para usarlo como coma puede ser ineficiente, especialmente para idiomas con un pequeño número de símbolos. El código Morse es un ejemplo cotidiano de un código de longitud variable con una coma. Las pausas largas entre letras, y las pausas aún más largas entre palabras, ayudan a las personas a reconocer dónde termina una letra (o palabra) y comienza la siguiente. De manera similar, la codificación de Fibonacci usa un "11" para marcar el final de cada palabra de código.

Los códigos de autosincronización son códigos de prefijo que permiten la sincronización de cuadros .

Un código de sufijo es un conjunto de palabras que no son sufijos de ninguna otra; equivalentemente, un conjunto de palabras que son el reverso de un código de prefijo. Al igual que con un código de prefijo, la representación de una cadena como una concatenación de tales palabras es única. Un código bifijo es un conjunto de palabras que es a la vez un código de prefijo y de sufijo. ^[8] Un código de prefijo óptimo es un código de prefijo con una longitud media mínima. Es decir, supongamos un alfabeto de n símbolos con probabilidades para un código de prefijo C . Si C' es otro código de prefijo y son las longitudes de las palabras de código de C' , entonces . ^[9]${\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})}\!}$

Algunos ejemplos de códigos de prefijo incluyen:

• códigos de Huffman de longitud variable
• códigos de llamadas de países
• Codificación Chen-Ho
• Las partes del ISBN que corresponden al país y al editor
• Los códigos de sincronización secundaria utilizados en el estándar inalámbrico UMTS W-CDMA 3G
• Códigos VCR Plus+
• Formato de transformación Unicode , en particular el sistema UTF-8 para codificar caracteres Unicode , que es a la vez un código sin prefijo y un código autosincronizado ^[10]
• cantidad de longitud variable

Las técnicas comúnmente utilizadas para construir códigos de prefijo incluyen los códigos de Huffman y los códigos de Shannon-Fano anteriores , y códigos universales como:

• Codificación delta de Elias
• Codificación gamma de Elias
• Codificación omega de Elias
• Codificación de Fibonacci
• Codificación de Levenshtein
• Codificación unaria
• Código del arroz Golomb
• Tablero de ajedrez a horcajadas (técnica criptográfica simple que produce códigos de prefijo)
• codificación binaria ^[11]

• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Códigos y autómatas. Enciclopedia de matemáticas y sus aplicaciones. Vol. 129. Cambridge: Cambridge University Press . ISBN 978-0-521-88831-8.Zbl 1187.94001  .
• Elias, Peter (1975). "Conjuntos de palabras de código universales y representaciones de los números enteros". IEEE Trans. Inf. Theory . 21 (2): 194–203. doi :10.1109/tit.1975.1055349. ISSN  0018-9448. Zbl  0298.94011.
• DA Huffman, "Un método para la construcción de códigos de redundancia mínima", Actas del IRE, septiembre de 1952, págs. 1098-1102 (artículo original de Huffman)
• Perfil: David A. Huffman, Scientific American , septiembre de 1991, págs. 54-58 (Historia de fondo)
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7 . Sección 16.3, págs. 385–392. 
•  Este artículo incorpora material de dominio público de la Norma Federal 1037C. Administración de Servicios Generales . Archivado desde el original el 22 de enero de 2022.

• Códigos, árboles y la propiedad del prefijo por Kona Macphee