Código de prefijo - Prefix code

Un código de prefijo es un tipo de sistema de código que se distingue por poseer la "propiedad de prefijo", que requiere que no haya una palabra de código completa en el sistema que sea un prefijo (segmento inicial) de cualquier otra palabra de código en el sistema. Es trivialmente cierto para el código de longitud fija, por lo que solo es un punto a tener en cuenta en el código de longitud variable .

Por ejemplo, un código con palabras de código {9, 55} tiene la propiedad de prefijo; un código que consta de {9, 5, 59, 55} no lo hace, 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 palabras. Sin embargo, existen códigos decodificables unívocamente que no son códigos de prefijo; por ejemplo, el reverso de un código de prefijo todavía es decodificable de forma única (es un código de sufijo), pero no es necesariamente un código de prefijo.

Los códigos prefijo también se conocen como códigos libres de prefijo , los 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 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 prefijos, pero en la mayoría de los libros y artículos matemáticos (p. Ej.) Un código sin comas se usa para referirse a un código de sincronización automática , una subclase de códigos de prefijo.

Usando códigos de prefijo, un mensaje se puede transmitir como una secuencia de palabras de código concatenadas, sin marcadores fuera de banda o (alternativamente) marcadores especiales entre palabras para enmarcar las palabras en el mensaje. El destinatario puede decodificar el mensaje sin ambigüedades, encontrando y eliminando repetidamente secuencias que forman palabras de código válidas. Por lo general, esto no es 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 es la palabra de código completa " 1 ", o simplemente el prefijo de la palabra de código" 10 "u" 11 "; por lo que la cadena "10" podría interpretarse como una sola palabra de código o como la concatenación de las palabras "1" y luego "0".

Los códigos de Huffman de longitud variable , los códigos de llamadas de países , el país y las partes del editor de los ISBN , los códigos de sincronización secundarios 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 informáticas 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 la codificación de canal (incluida la corrección de errores) antes de la 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. 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 .

Técnicas

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 canales ). 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 células 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 fuente. ${\ Displaystyle 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 los símbolos fijos en los prefijos más cortos para cumplir con la longitud de los prefijos más largos. Alternativamente, tales 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 ineficaces 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 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 deben 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érdidas basada en la codificación de la entropía .

Algunos códigos marcan el final de una palabra de código con un símbolo especial de "coma", diferente de los datos normales. 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 ninguna otra parte de una palabra de código, el código es automáticamente libre de prefijos. Sin embargo, los sistemas de comunicación modernos envían todo como secuencias de "1" y "0"; agregar un tercer símbolo sería costoso y usarlo solo al final de las palabras sería ineficaz. 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 sincronización automática son códigos de prefijo que permiten la sincronización de cuadros .

Conceptos relacionados

Un código de sufijo es un conjunto de palabras, ninguna de las cuales es un sufijo de ninguna otra; de manera equivalente, 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 tanto un prefijo como un código de sufijo. Un código de prefijo óptimo es un código de prefijo con una longitud media mínima. Es decir, asumir 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 . ${\ 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})} \!}$

Códigos de prefijo en uso hoy

Ejemplos de códigos de prefijo incluyen:

• códigos Huffman de longitud variable
• códigos de llamadas de países
• Codificación Chen – Ho
• el país y las partes del editor de los ISBN
• los códigos de sincronización secundarios 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 tanto un código sin prefijo como un código de sincronización automática
• cantidad de longitud variable

Técnicas

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

• Codificación delta de Elias
• Codificación gamma de Elias
• Codificación omega de Elías
• Codificación de Fibonacci
• Codificación de Levenshtein
• Codificación unaria
• Código de Golomb Rice
• Tablero de ajedrez a horcajadas (técnica de criptografía simple que produce códigos de prefijo)
• Codificación binaria

Notas

Referencias

• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Códigos y autómatas . Enciclopedia de Matemáticas y sus Aplicaciones. 129 . Cambridge: Cambridge University Press . ISBN   978-0-521-88831-8 . Zbl   1187.94001 .
• Elías, Peter (1975). "Conjuntos de palabras de código universales y representaciones de los números enteros". IEEE Trans. Inf. Teoría . 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", Proceedings of the 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 del documento de la Administración de Servicios Generales : "Norma Federal 1037C" .

enlaces externos

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