Teorema de codificación de fuentes

El Código producido por una fuente discreta sin memoria tiene que ser representado de manera eficiente, lo cual es un problema importante en las comunicaciones. Para que esto suceda, existen palabras de código, que representan estos códigos fuente.

Por ejemplo, en telegrafía, usamos código Morse, en el que los alfabetos se denotan por Marks y Spaces. Si la cartaE se considera, que se usa principalmente, se denota por “.” Mientras que la carta Q que se usa raramente, se denota por “--.-”

Echemos un vistazo al diagrama de bloques.

Dónde S_k es la salida de la fuente discreta sin memoria y b_k es la salida del codificador de origen que está representado por 0s y 1s.

La secuencia codificada es tal que se decodifica convenientemente en el receptor.

Supongamos que la fuente tiene un alfabeto con k diferentes símbolos y que el k^th símbolo S_k ocurre con la probabilidad P_k, dónde k = 0, 1…k-1.

Deje que la palabra de código binario asignada al símbolo S_k, por el codificador que tiene longitud l_k, medido en bits.

Por lo tanto, definimos la longitud media de la palabra de código L del codificador de origen como

$$ \ overline {L} = \ displaystyle \ sum \ limits_ {k = 0} ^ {k-1} p_kl_k $$

L representa el número medio de bits por símbolo fuente

Si $ L_ {min} = \: mínimo \: posible \: valor \: de \: \ overline {L} $

Luego coding efficiency Puede ser definido como

$$ \ eta = \ frac {L {min}} {\ overline {L}} $$

Con $ \ overline {L} \ geq L_ {min} $ tendremos $ \ eta \ leq 1 $

Sin embargo, el codificador de origen se considera eficiente cuando $ \ eta = 1 $

Para ello, se debe determinar el valor $ L_ {min} $.

Vamos a referirnos a la definición, "Dada una fuente de entropía discreta sin memoria $ H (\ delta) $, la longitud promedio de la palabra de códigoL porque cualquier codificación de origen se limita a $ \ overline {L} \ geq H (\ delta) $. "

En palabras más simples, la palabra de código (ejemplo: el código Morse para la palabra QUEUE es -.- ..-. ..-.) Es siempre mayor o igual que el código fuente (QUEUE en el ejemplo). Lo que significa que los símbolos de la palabra de código son mayores o iguales que los alfabetos del código fuente.

Por tanto, con $ L_ {min} = H (\ delta) $, la eficiencia del codificador de origen en términos de Entropía $ H (\ delta) $ puede escribirse como

$$ \ eta = \ frac {H (\ delta)} {\ overline {L}} $$

Este teorema de codificación de fuente se llama noiseless coding theoremya que establece una codificación libre de errores. También se llama comoShannon’s first theorem.