En la teoría de la codificación, un código de longitud variable es un código que asigna símbolos fuente a un número variable de bits.
Los códigos de longitud variable pueden permitir que las fuentes se compriman y descompriman sin error ( compresión de datos sin pérdidas ) y aún así se puedan leer símbolo por símbolo. Con la estrategia de codificación correcta, 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 tiene una probabilidad de falla finita (aunque quizás arbitrariamente pequeña).
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: y ser dos conjuntos finitos, denominados alfabetos de origen y de destino , respectivamente. Un codigo es una función total [1] mapeando cada símbolo dea una secuencia de símbolos sobre, y la extensión de a un homomorfismo de dentro , que asigna naturalmente cada secuencia de símbolos de origen a una secuencia de símbolos de destino, se conoce como su extensión .
Clases de códigos de longitud variable
Los códigos de longitud variable se pueden anidar estrictamente en orden de generalidad decreciente como códigos no singulares, códigos decodificables unívocamente y códigos de prefijo. Los códigos de prefijo siempre se pueden decodificar de forma única y, a su vez, estos siempre no son singulares:
Códigos no singulares
Un código no es singular si cada símbolo fuente se asigna a una cadena de bits no vacía diferente, es decir, la asignación de los símbolos fuente a las cadenas de bits es inyectiva .
- Por ejemplo, el mapeo no es no singular porque tanto "a" como "b" se asignan a la misma cadena de bits "0"; cualquier extensión de este mapeo generará una codificación con pérdida (no sin pérdida). Tal codificación singular aún puede ser útil cuando es aceptable alguna pérdida de información (por ejemplo, cuando dicho código se usa 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 ).
- 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 en general (pero esta característica no siempre es necesaria). Tenga en cuenta 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 manipulaciones indetectables).
Códigos decodificables de forma única
Un código es decodificable de forma única si su extensión no es singular (ver arriba). Con el algoritmo de Sardinas-Patterson se puede decidir si un código determinado es decodificable de forma única .
- El mapeo es decodificable de forma ú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 se termina 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, pero sin ambigüedades inicia un nuevo código).
- Considere nuevamente el código de la sección anterior. [1] Este código no se puede decodificar de forma única, ya que la cadena 011101110011 se puede interpretar 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 tanto, cdb y babe dan dos posibles decodificaciones de esta cadena codificada . Sin embargo, dicho código es útil cuando el conjunto de todos los posibles símbolos fuente 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. Tales restricciones permiten la decodificación del mensaje original comprobando cuáles de los posibles símbolos fuente asignados al mismo símbolo son válidos bajo esas restricciones.
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 comúnmente utilizados para este concepto son código sin prefijo , código instantáneo o código sin contexto .
- El mapeo de ejemplo en el párrafo anterior no es un código de prefijo porque después de leer la cadena de bits "0" no sabemos si codifica un símbolo fuente "a", o si es el prefijo de las codificaciones de la "b" o la "c" "símbolos.
- A continuación se muestra un ejemplo de un código de prefijo.
Símbolo | Palabra clave |
---|---|
a | 0 |
B | 10 |
C | 110 |
D | 111 |
- Ejemplo de codificación y decodificación:
- aabacdab → 00100110111010 → | 0 | 0 | 10 | 0 | 110 | 111 | 0 | 10 | → aabacdab
- Ejemplo de codificación y decodificación:
Un caso especial de códigos de prefijo son los códigos de bloque . Aquí 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 códigos de corrección de errores en el contexto de la codificación de canales .
Otro caso especial de códigos de prefijo son los códigos de cantidad de longitud variable , que codifican 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 fuente poco probables se les pueden asignar palabras de código más largas y a los símbolos fuente probables se les pueden asignar palabras de código más cortas, dando así una longitud de palabra de código baja esperada . Para el ejemplo anterior, si las probabilidades de (a, b, c, d) fueran, el número esperado de bits usados para representar un símbolo fuente usando el código anterior sería:
- .
Como la entropía de esta fuente es de 1.7500 bits por símbolo, este código comprime la fuente tanto como sea posible para que la fuente se pueda recuperar sin errores.
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 . Borrador disponible en línea