Teorema de codificação da fonte

Codificação de Fonte

Codificar uma fonte de informação envolve representá-la, para fins de transmissão e armazenamento, de tal forma a usar a menor quantidade de símbolos médios possível, pois a eficiência do codificador está ligada à quantidade de dígitos que foram utilizados para essa nova representação. Temos então que, quanto menor for a quantidade de dígitos empregado, mais eficiente será esse codificador. Pode-se dizer então que o processo de codificação de fonte eficiente tem como objetivo retirar redundâncias que estão presentes naquela fonte. Nesse, sentido Shannon provou que a informação emitida por uma fonte discreta sem memória pode ser comprimida a uma taxa de codificação $R>H(S)$, onde $H(S)$ é a entropia associada à fonte. Essa idéia é parte do conceito do conhecido Teorema de codificação da fonte, a ser discutido a seguir.

Teorema de Codificação da Fonte para uma Mensagem Aleatória

O teorema enuncia que existe um código binário livre de prefixo ótimo, por exemplo, um código de Huffman, de uma mensagem aleatória U com r possíveis valores, onde o comprimento médio das palavras-código obedece satisfaz:

$H(U){\text{ bits}}\leq L_{av}\leq H(U)+1{\text{ bits}}$,

em que

$L_{av}=\sum _{i=1}^{r}p_{i}l_{i}$

é o comprimento médio associado à mensagem U, $p_{i}$ é a probabilidade associada ao i-ésimo possível valor, de comprimento $l_{i}$ dígitos binários.

Note que a igualdade ocorre se, e somente se, $p_{i}$é uma potência negativa inteira de 2 para todo i. Vale ressaltar que, embora não seja um código ótimo, o teorema também é válido para o código de Fano.

Codificando uma Fonte de Informação

Considere agora que há um fluxo de mensagens, a ser continuamente codificadas. Para essa situação vamos considerar que cada símbolo emitido pela fonte seja independente dos anteriormente enviados, ou seja, temos uma fonte discreta e sem memória (DMS, Discrete Memoryless Source), gerando uma sequência de mensagens aleatórias independentes $U_{1},U_{2},U_{3},...,$ onde cada mensagem $U_{i}$ pode assumir r valores com probabilidades $p_{1},p_{2},...,p_{r}$.

É mais eficiente combinar duas ou mais mensagens $(U_{l},U_{l+1},...,U_{l+v})$ para a construção de um código, e assim podemos chamá-la de mensagem vetorial aleatória. Matematicamente, uma mensagem vetorial aleatória $V=(U_{1},U_{2},...,U_{v})$ não é diferente de uma mensagem aleatória convencional, pois ela pode assumir um número limitado de valores com probabilidades associadas. Então, se $U_{l}$ é r-ária, V terá $r^{v}$ possíveis símbolos. É possível expressar H(V) em termos de H(U). Considerando $q_{j}$ a probabilidade do j-ésimo símbolo de V, temos que as mensagens $U_{l}$ são mutuamente independentes, então:

$q_{j}=p_{i_{1}}\cdot p_{i_{2}}\cdots p_{i_{v}}$

Onde $p_{i_{l}}$ indica a probabilidade do $i_{l}$ -ésimo símbolo de $U_{i}$. Logo:

$H(V)=-\sum _{j=1}^{r^{v}}q_{j}log_{2}q_{j}$

$H(V)=-\sum _{i_{l}=1}^{r}...\sum _{i_{v}=1}^{r}(p_{i_{1}}.p_{i_{2}}...p_{i_{v}})\log _{2}(p_{i_{1}}.p_{i_{2}}...p_{i_{v}})$

$H(V)=-\sum _{i_{l}=1}^{r}...\sum _{i_{v}=1}^{r}(p_{i_{1}}.p_{i_{2}}...p_{i_{v}})(\log _{2}p_{i_{l}}+...+\log _{2}p_{i_{v}})$

$H(V)=-\sum _{i_{l}=1}^{r}...\sum _{i_{v}=1}^{r}p_{i_{1}}.p_{i_{2}}...p_{i_{v}}.\log _{2}p_{i_{l}}-...-\sum _{i_{1}=1}^{r}...\sum _{i_{v}=1}^{r}p_{i_{1}}.p_{i_{2}}...p_{i_{v}}.\log _{2}p_{i_{v}}$

$H(V)=-\left(\sum _{i_{1}=1}^{r}p_{i_{1}}\log _{2}p_{i_{1}}\right).\left(\sum _{i_{2}=1}^{r}p_{i_{2}}\right)...\left(\sum _{i_{v}=1}^{r}p_{i_{v}}\right)-...-\left(\sum _{i_{1}=1}^{r}p_{i_{1}}\right)...\left(\sum _{i_{v-1}=1}^{r}p_{i_{v-1}}\right).\left(\sum _{i_{v}=1}^{r}p_{i_{v}}\log _{2}p_{i_{v}}\right)$

$H(V)=-\left(\sum _{i_{l}=1}^{r}p_{i_{l}}\log _{2}p_{i_{l}}\right)-...-\left(\sum _{i_{v}=1}^{r}p_{i_{v}}\log _{2}p_{i_{v}}\right)$

$H(V)=H(U_{l})+...+H(U_{v})=vH(U)$

Isso quer dizer que se V consiste de ν mensagens aleatórias independentes, sua incerteza é ν vezes a incerteza média de U. Se usarmos um código ótimo, como o de Huffman, e sabendo do Teorema de Codificação para uma Mensagem Aleatória: $H(V){\text{ bits}}\leq L_{av}<H(V)+1{\text{ bits}}$, temos que um valor ν maior produzirá $L_{av}$ também maior, o que impede comparações justas entre sistemas de compressão distintos. Por isso, devemos computar o comprimento médio necessário para descrever um símbolo da fonte por vez, ou seja:

${\frac {H(V)}{v}}\leq {\frac {L_{av}}{v}}<{\frac {H(V)}{v}}+{\frac {1}{v}}$ bits

Sabendo que $H(V)=vH(U)$, temos:

${\frac {vH(U)}{v}}\leq {\frac {L_{av}}{v}}<{\frac {vH(U)}{v}}+{\frac {1}{v}}$ bits

E por fim chegamos ao Teorema de Codificação de Fonte de Shannon:

$H(U)\leq {\frac {L_{av}}{v}}<H(U)+{\frac {1}{v}}$ bits

Teorema de Codificação de Fonte de Shannon

Existe um código binário livre de prefixo para mensagens em blocos de ν dígitos, de uma fonte discreta sem-memória, tal que o número médio $L_{av}/v$ de dígitos de código binário por símbolo da fonte satisfaz:

${\frac {L_{av}}{v}}<H(U)+{\frac {1}{v}}$ bits

Onde H (U) é a entropia do símbolo medida em bits. De forma contrária, para todo código binário de mensagens em blocos de ν dígitos

${\frac {L_{av}}{v}}\geq H(U)$ bits

Consequentemente, o teorema mostra que é possível, com um código adequado, atingir um grau de compressão tão próximo à quantidade de informação emitida pela fonte.