Teorema da codificação da fonte

O Código produzido por uma fonte discreta sem memória deve ser representado de forma eficiente, o que é um problema importante nas comunicações. Para que isso aconteça, existem palavras-código, que representam esses códigos-fonte.

Por exemplo, na telegrafia, usamos o código Morse, em que os alfabetos são denotados por Marks e Spaces. Se a cartaE é considerado, que é mais usado, é denotado por “.” Considerando que a carta Q que raramente é usado, é denotado por “--.-”

Vamos dar uma olhada no diagrama de blocos.

Onde S_k é a saída da fonte discreta sem memória e b_k é a saída do codificador de origem, representada por 0s e 1s.

A sequência codificada é tal que é convenientemente decodificada no receptor.

Vamos supor que a fonte tenha um alfabeto com k símbolos diferentes e que o k^th símbolo S_k ocorre com a probabilidade P_k, Onde k = 0, 1…k-1.

Deixe a palavra do código binário atribuída ao símbolo S_k, pelo codificador ter comprimento l_k, medido em bits.

Portanto, definimos o comprimento médio da palavra de código L do codificador de origem como

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

L representa o número médio de bits por símbolo de fonte

Se $ L_ {min} = \: mínimo \: possível \: valor \: de \: \ overline {L} $

Então coding efficiency pode ser definido como

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

Com $ \ overline {L} \ geq L_ {min} $ teremos $ \ eta \ leq 1 $

No entanto, o codificador de origem é considerado eficiente quando $ \ eta = 1 $

Para isso, o valor $ L_ {min} $ deve ser determinado.

Vamos nos referir à definição, “Dada uma fonte discreta sem memória de entropia $ H (\ delta) $, o comprimento médio da palavra-códigoL para qualquer fonte, a codificação é limitada como $ \ overline {L} \ geq H (\ delta) $. "

Em palavras mais simples, a palavra de código (exemplo: código Morse para a palavra QUEUE é -.- ..-. ..-.) É sempre maior ou igual ao código-fonte (QUEUE no exemplo). O que significa que os símbolos na palavra de código são maiores ou iguais aos alfabetos no código-fonte.

Portanto, com $ L_ {min} = H (\ delta) $, a eficiência do codificador de origem em termos de Entropia $ H (\ delta) $ pode ser escrita como

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

Este teorema de codificação de fonte é chamado de noiseless coding theoremuma vez que estabelece uma codificação sem erros. Também é chamado deShannon’s first theorem.