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 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. 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 palabras clave {9, 55} tiene la propiedad de prefijo; un código que consta de {9, 5, 59, 55} no lo es, porque "5" es un prefijo de "59" y también de "55". Un código de prefijo es un código únicamente decodificable : dada una secuencia completa y precisa, un receptor puede identificar cada palabra sin necesidad de un marcador especial entre las palabras. Sin embargo, existen códigos únicamente decodificables 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 sólo 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 prefijos [1] [2] pero en la mayoría de los libros y artículos de matemáticas (por ejemplo, [3] [4] ) un código sin comas se utiliza para significar 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 del mensaje. El destinatario puede decodificar el mensaje sin ambigüedades, buscando y eliminando repetidamente secuencias que formen palabras clave válidas. Generalmente, 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 clave "10" u "11"; por lo que la cadena "10" podría interpretarse como una sola palabra en clave o como la concatenación de las palabras "1" y luego "0".
Los códigos Huffman de longitud variable , los códigos de llamadas de países , las partes de país y 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 podría 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 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. [5] La desigualdad de Kraft caracteriza los conjuntos de longitudes de palabras de código que son posibles en un código únicamente decodificable . [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 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 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 fuente.
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 símbolos fijos con los prefijos más cortos para cumplir 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 ineficaces en situaciones en las que es mucho más probable que algunas palabras se transmitan 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 minimizar la entropía). Esta es una forma de compresión de datos sin pérdidas basada en codificación de entropía .
Algunos códigos marcan el final de una palabra de código con un símbolo de "coma" especial (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 ninguna otra parte de una palabra de código, el código queda automáticamente libre de prefijos. Sin embargo, reservar un símbolo completo solo para usarlo como coma puede resultar ineficiente, especialmente para idiomas con una pequeña cantidad de símbolos. El código Morse es un ejemplo cotidiano de 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 utiliza 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, ninguna de las cuales es sufijo de 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 dichas palabras es única. Un código bifijo es un conjunto de palabras que es a la vez un código de prefijo y sufijo. [8] Un código de prefijo óptimo es un código de prefijo con una longitud promedio 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 en código de C' , entonces . [9]
Ejemplos de códigos de prefijo incluyen:
Las técnicas comúnmente utilizadas para construir códigos de prefijo incluyen códigos de Huffman y los códigos de Shannon-Fano anteriores , y códigos universales como:
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.
