Código de longitud variable

Código que asigna información a un número variable de bits

En teoría de codificación , un código de longitud variable es un código que asigna símbolos de origen a una cantidad variable de bits . El concepto equivalente en informática es cadena de bits .

Los códigos de longitud variable permiten comprimir y descomprimir fuentes con cero errores ( compresión de datos sin pérdida ) y, aun así, leerlas símbolo por símbolo. Con la estrategia de codificación adecuada, una fuente independiente e idénticamente distribuida puede comprimirse casi arbitrariamente cerca de su entropía . Esto contrasta con los métodos de codificación de longitud fija, para los cuales la compresión de datos solo es posible para grandes bloques de datos, y cualquier compresión más allá del logaritmo del número total de posibilidades conlleva una probabilidad finita (aunque quizás arbitrariamente pequeña) de falla.

Algunos ejemplos de estrategias de codificación de longitud variable bien conocidas son la codificación de Huffman , la codificación de Lempel-Ziv , la codificación aritmética y la codificación de longitud variable adaptativa al contexto .

Códigos y sus extensiones

La extensión de un código es el mapeo de secuencias fuente de longitud finita a cadenas de bits de longitud finita, que se obtiene concatenando para cada símbolo de la secuencia fuente la palabra de código correspondiente producida por el código original.

Utilizando términos de la teoría del lenguaje formal , la definición matemática precisa es la siguiente: Sean y dos conjuntos finitos, llamados alfabetos de origen y destino , respectivamente. Un código es una función total ^[1] que asigna cada símbolo de a una secuencia de símbolos sobre , y la extensión de a un homomorfismo de en , que asigna naturalmente cada secuencia de símbolos de origen a una secuencia de símbolos de destino, se conoce como su extensión . ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle C:S\to T^{*}}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle C}$ ${\displaystyle S^{*}}$ ${\displaystyle T^{*}}$

Clases de códigos de longitud variable

Los códigos de longitud variable se pueden anidar estrictamente en orden decreciente de generalidad como códigos no singulares, códigos decodificables de forma única y códigos de prefijo. Los códigos de prefijo siempre son decodificables de forma única y estos, a su vez, siempre son no singulares:

Códigos no singulares

Un código no es singular si cada símbolo de origen se asigna a una cadena de bits no vacía diferente, es decir, la asignación de los símbolos de origen a las cadenas de bits es inyectiva .

• Por ejemplo, la asignación no es no singular porque tanto "a" como "b" se asignan a la misma cadena de bits "0"; cualquier extensión de esta asignación generará una codificación con pérdida (no sin pérdida). Esta codificación singular puede ser útil cuando se acepta cierta pérdida de información (por ejemplo, cuando dicho código se utiliza en la compresión de audio o video, donde una codificación con pérdida se vuelve equivalente a la cuantificación de la fuente ). ${\displaystyle M_{1}=\{\,a\mapsto 0,b\mapsto 0,c\mapsto 1\,\}}$
• Sin embargo, el mapeo no es singular; su extensión generará una codificación sin pérdidas, que será útil para la transmisión de datos generales (pero esta característica no siempre es necesaria). Nótese que no es necesario que el código no singular sea más compacto que la fuente (y en muchas aplicaciones, un código más grande es útil, por ejemplo, como una forma de detectar y/o recuperarse de errores de codificación o transmisión, o en aplicaciones de seguridad para proteger una fuente de una manipulación indetectable). ${\displaystyle M_{2}=\{\,a\mapsto 1,b\mapsto 011,c\mapsto 01110,d\mapsto 1110,e\mapsto 10011,f\mapsto 0\}}$

Códigos decodificables de forma única

Un código es decodificable de forma única si su extensión es § no singular. Se puede decidir si un código dado es decodificable de forma única con el algoritmo de Sardinas–Patterson .

• El mapeo es decodificable de manera única (esto se puede demostrar mirando el conjunto de seguimiento después de cada cadena de bits de destino en el mapa, porque cada cadena de bits finaliza tan pronto como vemos un bit 0 que no puede seguir ningún código existente para crear un código válido más largo en el mapa, sino que inicia de manera inequívoca un nuevo código). ${\displaystyle M_{3}=\{\,a\mapsto 0,b\mapsto 01,c\mapsto 011\,\}}$
• Consideremos nuevamente el código de la sección anterior. ^[1] Este código no es decodificable de manera única, ya que la cadena 011101110011 puede interpretarse como la secuencia de palabras de código 01110 – 1110 – 011 , pero también como la secuencia de palabras de código 011 – 1 – 011 – 10011 . Por lo tanto, cdb y babe proporcionan dos posibles decodificaciones de esta cadena codificada . Sin embargo, un código de este tipo es útil cuando el conjunto de todos los símbolos fuente posibles es completamente conocido y finito, o cuando existen restricciones (por ejemplo, una sintaxis formal) que determinan si los elementos fuente de esta extensión son aceptables. Dichas restricciones permiten la decodificación del mensaje original al verificar cuáles de los posibles símbolos fuente asignados al mismo símbolo son válidos bajo esas restricciones. ${\displaystyle M_{2}}$

Códigos de prefijo

Un código es un código de prefijo si ninguna cadena de bits de destino en la asignación es un prefijo de la cadena de bits de destino de un símbolo de origen diferente en la misma asignación. Esto significa que los símbolos se pueden decodificar instantáneamente después de recibir su palabra de código completa. Otros nombres que se usan comúnmente para este concepto son código sin prefijo , código instantáneo o código sin contexto .

• El ejemplo de mapeo en el párrafo anterior no es un código de prefijo porque no sabemos después de leer la cadena de bits "0" si codifica un símbolo fuente "a", o si es el prefijo de las codificaciones de los símbolos "b" o "c". ${\displaystyle M_{3}}$
• A continuación se muestra un ejemplo de código de prefijo.

Ejemplo de codificación y decodificación:

aabacdab → 00100110111010 → |0|0|10|0|110|111|0|10| → aabacdab

Un caso especial de códigos de prefijo son los códigos de bloque . En estos casos, todas las palabras de código deben tener la misma longitud. Estos últimos no son muy útiles en el contexto de la codificación de fuente , pero a menudo sirven como corrección de errores hacia adelante en el contexto de la codificación de canal .

Otro caso especial de códigos de prefijo son los códigos LEB128 y de cantidad de longitud variable (VLQ), que codifican números enteros arbitrariamente grandes como una secuencia de octetos, es decir, cada palabra de código es un múltiplo de 8 bits.

Ventajas

La ventaja de un código de longitud variable es que a los símbolos de origen improbables se les pueden asignar palabras de código más largas y a los símbolos de origen probables se les pueden asignar palabras de código más cortas, lo que da como resultado una longitud de palabra de código esperada baja . Para el ejemplo anterior, si las probabilidades de (a, b, c, d) fueran , la cantidad esperada de bits utilizados para representar un símbolo de origen utilizando el código anterior sería: ${\displaystyle \textstyle \left({\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{8}}\right)}$

${\displaystyle 1\times {\frac {1}{2}}+2\times {\frac {1}{4}}+3\times {\frac {1}{8}}+3\times {\frac {1}{8}}={\frac {7}{4}}}$.

Como la entropía de esta fuente es de 1,75 bits por símbolo, este código comprime la fuente tanto como sea posible para que pueda recuperarse con cero errores.

Véase también

• Código Golomb
• Conteo de Kruskal
• Conjuntos de instrucciones de longitud variable en informática

Referencias

1. Este código se basa en un ejemplo encontrado en Berstel et al. (2009), Ejemplo 2.3.1, pág. 63.

Lectura adicional

• Salomon, David (septiembre de 2007). Códigos de longitud variable para compresión de datos (1.ª edición). Springer Verlag . ISBN 978-1-84628-958-3.(xii+191 páginas) Fe de erratas 1 Fe de erratas 2
• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Códigos y autómatas . Enciclopedia de matemáticas y sus aplicaciones. Vol. 129. Cambridge, Reino Unido: Cambridge University Press . ISBN. 978-0-521-88831-8.Zbl 1187.94001  .Borrador disponible en línea