Fuente → Canal: Codificación de Dos Etapas
El Capítulo 10 de Hamming abre con el modelo de comunicación de Shannon, que se aplica a cada sistema que mueve información: llamadas telefónicas, radio, discos duros, replicación de ADN, memoria de computadora.
La Arquitectura de Dos Etapas
Etapa 1: Codificación de fuente (compresión). Convertir el mensaje de fuente a una representación compacta. Objetivo: eliminar redundancia nativa de la fuente. El código Morse hace esto: las letras comunes obtienen códigos cortos, las letras raras obtienen códigos largos.
Etapa 2: Codificación de canal (protección de errores). Agregar redundancia controlada adaptada a las características de ruido del canal. Una línea telefónica ruidosa necesita más redundancia que un cable de fibra óptica. Las dos etapas se desacoplan: optimizar cada una de forma independiente para su propia tarea.
La interfaz común entre las dos etapas — un flujo de bits estandarizado — significa que cualquier fuente puede emparejarse con cualquier canal. Esta modularidad es la perspectiva arquitectónica clave de Shannon.
Almacenamiento como comunicación. Hamming señala que enviar un mensaje a través del espacio (transmisión) y enviarlo a través del tiempo (almacenamiento) usan el mismo modelo. Una unidad de copia de seguridad es un canal ruidoso en el tiempo.
El Papel del Ruido
El modelo de Shannon hace una suposición radical: el ruido es inevitable. Cada canal, cada medio de almacenamiento, cada circuito de conmutación introduce alguna probabilidad de error. La pregunta no es 'cómo eliminamos el ruido?' sino 'cómo recuperamos el mensaje original a pesar del ruido?'
Esto contrasta con la física clásica, donde el ruido entra como una idea de último momento (el principio de incertidumbre). Shannon trata el ruido como la condición fundamental — toda la teoría se construye a partir de esto.
Por ahora, el Capítulo 10 se enfoca en el caso sin ruido: codificación de fuente sin errores. El problema de codificación de canal (corrección de errores) espera para capítulos posteriores.
¿Cuándo Puedes Decodificar de Forma Única?
Para que un código de longitud variable sea útil, el receptor debe decodificar un flujo de bits de forma inequívoca. Hamming ilustra con un código de 4 símbolos que falla en esta prueba, luego introduce la solución: códigos sin prefijo.
Condición sin Prefijo
Un código es sin prefijo (o instantáneo) si ninguna palabra clave es un prefijo de ninguna otra palabra clave. Dado un flujo de bits recibido, sabes que un símbolo ha terminado en el momento en que alcanzas una hoja en el árbol de decodificación — sin necesidad de mirar hacia adelante.
Ejemplo de código sin prefijo para {s1, s2, s3, s4}: s1 = 0, s2 = 10, s3 = 110, s4 = 111.
Verifica: 0 no es un prefijo de 10, 110, o 111. 10 no es un prefijo de 110 o 111 (10 seguido de más bits da 100... o 101..., ninguno de los cuales comienza con 110 o 111). El código califica.
El procedimiento de decodificación: sigue el árbol, bifúrcate en cada bit entrante, emite el símbolo cuando alcanzas una hoja, regresa a la raíz.
La Desigualdad de Kraft
Para cualquier código binario sin prefijo con longitudes de palabras clave l_1, l_2, ..., l_n:
Σ 2^(−l_i) ≤ 1
La igualdad se cumple cuando el código es completo (las hojas cubre el árbol binario completo sin espacios). Esta es una condición necesaria: ningún código sin prefijo puede violarla. Inversamente, para cualquier conjunto de longitudes que satisfaga la desigualdad de Kraft, existe un código sin prefijo.
Aplicando la Desigualdad de Kraft
Dadas longitudes de palabras clave, verifica Kraft: Σ 2^(−l_i) ≤ 1.
Para {s1=0, s2=10, s3=110, s4=111}: las longitudes son 1, 2, 3, 3.
Σ = 2^(−1) + 2^(−2) + 2^(−3) + 2^(−3) = 1/2 + 1/4 + 1/8 + 1/8 = 1. ✓
Entropía de Shannon
La longitud promedio de palabra clave de un código de longitud variable: L = Σ p_i · l_i, donde p_i es la probabilidad del símbolo s_i y l_i es la longitud de su palabra clave.
¿Qué tan corta puede ser L? La respuesta de Shannon: no por debajo de la entropía de la fuente.
Entropía de Shannon: H = −Σ p_i · log₂(p_i) (unidades: bits/símbolo)
La entropía mide la información promedio por símbolo. Alta entropía significa que los símbolos son aproximadamente equiprobables (imprevisibilidad máxima). Baja entropía significa que algunos símbolos dominan (alta previsibilidad, más comprimible).
Teorema de Codificación sin Ruido
Para cualquier código sin prefijo, H(fuente) ≤ L ≤ H(fuente) + 1.
Ningún código puede vencer la entropía. La codificación de Huffman (próximo capítulo) alcanza el límite superior: L < H + 1. Para códigos de bloque sobre n símbolos, el límite se estrecha: H ≤ L/n < H + 1/n.
La entropía también es el límite de compresión teórico: no puedes comprimir una fuente por debajo de H bits por símbolo sin perder información.
Calculando la Entropía
Ejemplo: 4 símbolos con probabilidades p = [1/2, 1/4, 1/8, 1/8].
H = −(1/2)·log₂(1/2) − (1/4)·log₂(1/4) − (1/8)·log₂(1/8) − (1/8)·log₂(1/8)
= (1/2)·1 + (1/4)·2 + (1/8)·3 + (1/8)·3
= 0.5 + 0.5 + 0.375 + 0.375 = 1.75 bits/símbolo
Y la codificación de Huffman {0, 10, 110, 111} logra L = 1.75 = H exactamente.
¿Por Qué la Entropía es un Límite Inferior?
El límite inferior del teorema de codificación sin ruido no es solo una fórmula — refleja algo profundo sobre la información: no puedes comprimir lo que ya es máximamente impredecible.
Cuando todos los símbolos son igualmente probables (distribución uniforme), la entropía H = log₂(n) para n símbolos. Un código de bloque de longitud log₂(n) bits logra exactamente H. Ningún código puede hacerlo mejor.
Cuando un símbolo domina (digamos, p(A) = 0.99, p(B) = 0.01), H es pequeño — cerca de 0. Un código de longitud variable puede asignar a A un código muy corto, codificando el flujo de forma muy eficiente.
El resultado práctico: las ganancias de compresión grandes solo existen cuando las probabilidades de símbolos difieren sustancialmente. Si la fuente ya es 'uniforme' (parece aleatoria), la codificación de Huffman no gana nada.