5.7: Detalle- Código Fuente Eficiente
- Page ID
- 82140
En ocasiones, la codificación fuente y la compresión para sistemas de comunicación del tipo que se muestra en la Figura 5.1 se realizan juntas (es una cuestión abierta si hay beneficios prácticos al combinar la codificación fuente y canal). Para fuentes con un número finito de símbolos, pero con probabilidades desiguales de aparecer en el flujo de entrada, existe una técnica elegante y sencilla para la codificación de fuentes con redundancia mínima.
Ejemplo de una Fuente Finita
Considere una fuente que genere símbolos que son grados de letras MIT, con posibles valores A, B, C, D y F. Se le pide que diseñe un sistema que pueda transmitir un flujo de dichos grados, producido a la velocidad de un símbolo por segundo, a través de un canal de comunicaciones que solo puede llevar dos dígitos booleanos, cada uno 0 o 1, por segundo. \(^3\)
Primero, no asumamos nada sobre la distribución de calificaciones. Para transmitir cada símbolo por separado, debe codificar cada uno como una secuencia de bits (dígitos booleanos). Usar código ASCII de 7 bits es derrochador; solo tenemos cinco símbolos y ASCII puede manejar 128. Dado que solo hay cinco valores posibles, las calificaciones se pueden codificar en tres bits por símbolo. Pero el canal sólo puede procesar dos bits por segundo.
Sin embargo, tres bits es más de lo necesario. La entropía, asumiendo que no hay información sobre las probabilidades, es como mucho\(\log_2(5)\) = 2.32 bits. \(\sum_{i} p(A_i) \log_2(1/p(A_i))\)Aquí también es donde hay cinco de esos\(p_i\), cada uno igual a 1/5. ¿Por qué necesitábamos tres bits en el primer caso? Porque no teníamos forma de transmitir un bit parcial. Para hacerlo mejor, podemos usar “codificación de bloques”. Agrupamos los símbolos en bloques de, digamos, tres. La información en cada bloque es tres veces la información por símbolo, o 6.97 bits. Así, un bloque se puede transmitir usando 7 bits booleanos (hay 125 secuencias distintas de tres grados y 128 posibles patrones disponibles en 7 bits). Por supuesto que también necesitamos una manera de significar el fin, y una manera de decir que la palabra final transmitida tiene sólo una calificación válida (o dos), no tres.
Pero esto sigue siendo demasiados bits por segundo para que el canal los maneje. Entonces veamos la distribución de probabilidad de los símbolos. En un curso típico de MIT “centrado en B” con buenos estudiantes, la distribución de calificaciones podría ser la que se muestra en la Tabla 5.3. Asumiendo esto como una distribución de probabilidad, ¿cuál es la información por símbolo y cuál es la información promedio por símbolo? Este cálculo se muestra en la Tabla 5.4. La información por símbolo es de 1.840 bits. Dado que esto es menos de dos bits quizás los símbolos se puedan codificar para usar este canal.
| A | B | C | D | F |
| 25% | 50% | 12.5% | 10% | 2.5% |
\ [\ nonumber\ begin {array} {cccc}
\ text {Símbolo} &\ text {Probabilidad} &\ text {Información} &\ begin {array} {c}
\ text {Contribución}\
\\ text {a la media}
\ end {array}\\
& p &\ log\ left (\ frac {1} {p}\ right) & p\ log\ left (\ frac {1} {p}\ derecha)\
\ mathrm {A} & 0.25 & 2\ mathrm {\, bits} & 0.5\ mathrm {\, bits}\
\ mathrm {B} & 0.50 & 1\ mathrm {\, bit} & 0.5\ mathrm {\, bits}\\ mathrm {\, bits}
\\ mathrm {C} & 0.125 y 3\ mathrm rm {\, bits} & 0.375\ mathrm {\, bits}\\
\ mathrm {D} & 0.10 & 3.32\ mathrm {\, bits} & 0.332\ mathrm {\, bits}
\\ mathrm {F} & 0.025 & 5.32\ mathrm {\, bits} & 0.133\ mathrm {\, bits}\\ [-20pt]
&\ overline {\ qquad\ qquad} &\ overline {\ qquad}\\ [-10pt]
\ text {Total} & 1.00 & & 1.840\ mathrm {\, bits}
\ end {array}\ nonumber\]
Cuadro 5.4: Distribución de la información para las calificaciones en una distribución promedio del MIT
Código Huffman
David A. Huffman (9 de agosto de 1925 - 6 de octubre de 1999) fue un estudiante de posgrado en el MIT. Para resolver una tarea de tarea para un curso que estaba tomando del profesor Robert M. Fano, ideó una forma de codificar símbolos con diferentes probabilidades, con redundancia mínima y sin marcos de símbolos especiales, y por lo tanto de manera más compacta. Lo describió en Actas del IRE, septiembre de 1962. Su algoritmo es muy sencillo. El objetivo es llegar a un “libro de códigos” (una cadena de bits para cada símbolo) para que se minimice la longitud promedio del código. Presumiblemente, los símbolos poco frecuentes obtendrían códigos largos, y símbolos comunes códigos cortos, al igual que en el código Morse. El algoritmo es el siguiente (puede seguirlo haciendo referencia a la Tabla 5.5):
- Inicializar: Deje que el código parcial para cada símbolo sea inicialmente la cadena de bits vacía. Definir correspondiente a cada símbolo un “conjunto de símbolos”, con solo ese símbolo en él, y una probabilidad igual a la probabilidad de ese símbolo.
- Prueba de bucle: Si hay exactamente un conjunto de símbolos (su probabilidad debe ser 1) ya terminaste. El libro de códigos consiste en los códigos asociados a cada uno de los símbolos en ese conjunto de símbolos.
- Loop-action: Si hay dos o más conjuntos de símbolos, tome los dos con las probabilidades más bajas (en caso de empate, elija dos cualquiera). Anexen los códigos para aquellos en un conjunto de símbolos con 0 y el otro con 1. Definir un nuevo conjunto de símbolos que es la unión de los dos conjuntos de símbolos que se acaban de procesar, con probabilidad igual a la suma de las dos probabilidades. Reemplace los dos conjuntos de símbolos por uno nuevo. De este modo, el número de conjuntos de símbolos se reduce en uno. Repita este bucle, incluida la prueba de bucle, hasta que solo quede un conjunto de símbolos.
Tenga en cuenta que este procedimiento generalmente produce un código de longitud variable. Si hay símbolos\(n\) distintos, al menos dos de ellos tienen códigos con la longitud máxima.
Para nuestro ejemplo, comenzamos con cinco conjuntos de símbolos, y reducimos el número de conjuntos de símbolos en uno cada paso, hasta que nos quedemos con solo uno. Los pasos se muestran en la Tabla 5.5, y el libro de códigos final en la Tabla 5.6.
| Inicio: | (A='-' p=0.25) (B='-' p=0.5) (C='-' p=0.125) (D='-' p=0.1) (F='-' p=0.025) |
| Siguiente: | (A='-' p=0.25) (B='-' p=0.5) (C='-' p=0.125) (D='1' F='0' p=0.125) |
| Siguiente: | (A='-' p=0.25) (B='-' p=0.5) (C='1' D='01' F='00' p=0.25) |
| Siguiente: | (B='-' p=0.5) (A='1' C='01' D='001' F='000' p=0.5) |
| Final: | (B='1' A='01' C='001' D='0001' F'0000' p=1.0) |
| Símbolo | Código |
| A | 0 1 |
| B | 1 |
| C | 0 0 1 |
| D | 0 0 0 1 |
| F | 0 0 0 |
¿Este código es realmente compacto? Al símbolo más frecuente (B) se le da el código más corto y a los símbolos menos frecuentes (D y F) los códigos más largos, por lo que en promedio el número de bits necesarios para un flujo de entrada que obedece a la distribución de probabilidad asumida es efectivamente corto, como se muestra en la Tabla 5.7.
Compare esta tabla con la tabla anterior de contenido de información, Tabla 5.4. Tenga en cuenta que la longitud codificada promedio por símbolo, 1.875 bits, es mayor que la información por símbolo, que es 1.840 bits. Esto se debe a que los símbolos D y F no pueden codificarse en bits fraccionarios. Si se consideró un bloque de varios símbolos
\ [\ nonumber\ begin {array} {cllll}
\ text {Símbolo} &\ text {Código} &\ text {Probabilidad} &\ begin {array} {c}
\ text {Código}\\
\ text {length}
\ end {array} &\ begin {array} {c}
\ text {Contribución}\\
\ texto {a la media}
\ end {array}\
\\ texto {A} & 01 & 0.25 & 2 & 0.5\
\\ texto {B} & 1 & 0.50 & 1 & 0.5
\\ texto {C} & 001 & 0.125 & 3 & 0.375\
\ texto {D} & 0001 & 0.1 y 3.32 & amp; 0.4\\
\ text {F} & 0000 & 0.025 & 5.32 & 0.1\\ [-30pt]
& &\ overline {\ qquad\ qquad\ quad} & &\ overline {\ qquad\ qquad\ quad}\ [-30pt]
\ text {Total} & & 1.00 & & 1.875\ texto {bits}
\ end {array}\ nonumber\]
Tabla 5.7: Codificación de Huffman de la distribución típica de grados MIT
juntos, la longitud promedio del código Huffman podría estar más cerca de la información real por símbolo, pero no por debajo de ella.
El canal puede manejar dos bits por segundo. Al usar este código, puedes transmitir por el canal un poco más de un símbolo por segundo en promedio. Puedes lograr tu objetivo de diseño. Hay al menos seis cosas prácticas a considerar sobre los códigos de Huffman:
- Podría ocurrir una explosión de grados D o F. Es necesario que el codificador almacene estos bits hasta que el canal pueda ponerse al día. ¿Qué tan grande se necesita un búfer para el almacenamiento? ¿Qué pasará si el búfer se desborda?
- La salida puede retrasarse debido a una copia de seguridad de búfer. El tiempo entre una entrada y la salida asociada se llama “latencia”. Para los sistemas interactivos se quiere mantener baja la latencia. El número de bits procesados por segundo, el “rendimiento”, es más importante en otras aplicaciones que no son interactivas.
- La salida no ocurrirá a intervalos regularmente espaciados, debido a los retrasos causados por las ráfagas. En algunas aplicaciones en tiempo real como el audio, esto puede ser importante.
- ¿Y si nos equivocamos en nuestras presuntas distribuciones de probabilidad? Un curso grande podría dar menos calificaciones A y B y más C y D. Nuestra codificación sería ineficiente y podría haber desbordamiento de búfer.
- El decodificador necesita saber cómo romper el flujo de bits en códigos individuales. La regla en este caso es, romper después de '1' o después de '0000', lo que ocurra primero. Sin embargo, hay muchos códigos posibles de Huffman, correspondientes a diferentes elecciones para 0 y 1 precediendo en el paso 3 del algoritmo anterior. La mayoría no tiene reglas tan simples. Puede ser difícil (aunque siempre es posible) saber dónde se deben poner los saltos entre símbolos.
- El libro de códigos en sí debe entregarse, de antemano, tanto al codificador como al decodificador. Esto podría hacerse transmitiendo el libro de códigos sobre el canal una vez.
Otro Ejemplo
Los estudiantes de primer año del MIT están en un sistema de “pasa/sin registro” durante su primer semestre en el campus. Los grados A, B y C se reportan en las transcripciones como P (pase), y no se reportan D y F (para nuestros propósitos designaremos esto como sin registro, N). Diseñemos un sistema para enviar estos símbolos P y N a una impresora a la tasa promedio más rápida. Sin considerar probabilidades, se necesita 1 bit por símbolo. Pero las probabilidades (asumiendo la distribución típica de calificaciones del MIT en el Cuadro 5.3) son\(p(P) = p(A) + p(B) + p(C) = 0.875\), y\(p(N) = p(D) + p(F) = 0.125\). Por lo tanto, la información por símbolo no es de 1 bit sino de solo 0.875 ×\(\log_2(1/0.875)\) + 0.125 ×\(\log_2(1/0.125)\) = 0.544 bits. La codificación de Huffman en símbolos individuales no ayuda. Tenemos que tomar grupos de pedacitos juntos. Por ejemplo once grados como bloque tendrían 5.98 bits de información y podrían en principio codificarse para requerir solo 6 bits para ser enviados a la impresora.
\(^3\)Boolean digits, or binary digits, are usually called “bits.” The word “bit” also refers to a unit of information. When a boolean digit carries exactly one bit of information there may be no confusion. But inefficient codes or redundant codes may have boolean digit sequences that are longer than the minimum and therefore carry less than one bit of information per bit. This same confusion attends other units of measure, for example meter, second, etc.