6.3: Teorema de Codificación Fuente

Ahora volviendo al modelo fuente, tenga en cuenta que las palabras clave tienen una longitud promedio, en bits por símbolo,

$L = \displaystyle \sum_{i} p(A_i)L_i \tag{6.11}$

Para la velocidad máxima se necesita la longitud promedio de palabra de código más baja posible. La asignación de símbolos de alta probabilidad a las palabras de código cortas puede ayudar a hacer$L$ pequeñas. Los códigos Huffman son códigos óptimos para este propósito. Sin embargo, hay un límite en cuanto a cuán corta puede ser la palabra de código promedio. Específicamente, el Teorema de Codificación Fuente establece que la información promedio por símbolo siempre es menor o igual a la longitud promedio de una palabra clave:

$H \leq L \tag{6.12}$

Esta desigualdad es fácil de probar utilizando las desigualdades de Gibbs y Kraft. Utilizar la desigualdad Gibbs con$p'(A_i) = 1/2^{L_i}$ (la desigualdad Kraft asegura que el$p'(A_i)$, además de ser positivo, suman no más de 1). Así

Figura 6.3: Canal binario

$$\begin{align*} H \quad &= \quad \displaystyle \sum_{i} p(A_i)\log_2\Big(\dfrac{1}{p(A_i)}\Big) \\ &\leq \quad\displaystyle \sum_{i} p(A_i)\log_2\Big(\dfrac{1}{p'(A_i)}\Big) \\ &= \quad \displaystyle \sum_{i} p(A_i)\log_2 2^{L_i} \\ &= \quad\sum_{i} p(A_i)L_i \\ &= \quad L \tag{6.13} \end{align*}$$

El Teorema de Codificación de Origen también se puede expresar en términos de velocidades de transmisión en bits por segundo multiplicando la Ecuación 6.12 por los símbolos por segundo$R$:

$H \ R \leq L \ R \tag{6.14}$