Código de prefijo

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 clave en el sistema. Es trivialmente cierto para el código de longitud fija, por lo que solo es un punto a considerar 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, porque "5" es un prefijo de "59" y también de "55". Un código de prefijo es un código decodificable de manera única: dada una secuencia completa y precisa, un receptor puede identificar cada palabra sin necesidad de un marcador especial entre palabras. Sin embargo, hay códigos decodificables únicos 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 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 denominan "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 ningún marcador 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 lee 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 que la cadena "10" podría interpretarse como una sola palabra clave o como la concatenación de las palabras "1" luego "0".

Los códigos Huffman de longitud variable, los códigos de llamadas de países, las partes de países y editores 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 volver a codificarse con codificación de canal (incluida la corrección de errores) antes de la transmisión.

Para cualquier código decodificable de forma única, hay 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 en el código tiene la misma longitud, el código se llama a código de longitud fija, o un código bloque (aunque el código de bloqueo de término también se utiliza para códigos de corrección de errores de tamaño fijo en codificación de canales). Por ejemplo, las letras ISO 8859-15 siempre tienen 8 bits de largo. Las letras UTF-32/UCS-4 siempre tienen 32 bits de largo. Las células ATM siempre tienen 424 bits (53 bytes) de largo. Un código de longitud fija de longitud fija k bits pueden codificar hasta ${displaystyle 2^{k}$ 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 agregando símbolos fijos a 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 se transmitan algunas palabras que otras.

La codificación binaria truncada es una generalización directa 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 de origen se les asignan palabras clave de longitud k y k+1, donde k se elige para que 2^{k < n ≤ 2k+1}.

La codificación 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 del código y construye un código de prefijo que minimiza el promedio ponderado de las longitudes de las palabras del 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 entropía.

Algunos códigos marcan el final de una palabra clave con una "coma" símbolo, diferente de los datos normales. Esto es algo análogo a los espacios entre palabras en una oración; marcan donde 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 automáticamente no tiene prefijo. 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 ineficiente. El código Morse es un ejemplo cotidiano de un código de longitud variable con una coma. Las largas pausas entre las letras, y las pausas aún más largas entre las 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 clave.

Los códigos de sincronización automática son códigos de prefijo que permiten la sincronización de fotogramas.

Conceptos relacionados

A Código de sufijo es un conjunto de palabras ninguna de las cuales es un sufijo de ninguna otra; equivalentemente, un conjunto de palabras que son el reverso de un código prefijo. Como con un código prefijo, la representación de una cadena como concatenación de tales palabras es única. A código bifix es un conjunto de palabras que es tanto un prefijo como un código sufijo. An código prefijo óptimo es un código prefijo con una longitud media mínima. Es decir, asumir un alfabeto n símbolos con probabilidades ${displaystyle p(A_{i})}$ para un código prefijo C. Si C ' es otro código prefijo y ${displaystyle lambda '$ son las longitudes de las palabras clave de C ', entonces ${displaystyle sum _{i=1}{n}{lambda _{i}p(A_{i}}leq sum ##{i=1} {n}{n}{lambda ¡Oh!$.

Códigos de prefijo en uso hoy

Los ejemplos de códigos de prefijo incluyen:

• códigos Huffman de longitud variable
• country calling codes
• Chen-Ho codificando
• el país y las partes editoras de ISBNs
• la sincronización secundaria Códigos utilizados en el estándar inalámbrico UMTS W-CDMA 3G
• VCR Códigos más+
• Transformación Unicode Formato, en particular el sistema UTF-8 para la codificación de caracteres Unicode, que es un código libre de prefijo y un código autosincronizador
• cantidad de longitud variable

Técnicas

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

• Codificación de Elias delta
• Codificación de Elias Gamma
• Codificación de Elias omega
• Codificación de Fibonacci
• Codificación de levenshtein
• Codificación no religiosa
• Golomb Rice code
• Panel de control (técnica de criptografía simple que produce códigos prefijos)
• codificación binaria