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 ${\displaystyle R>H(S)}$, onde ${\displaystyle 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:

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

em que

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

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

Note que a igualdade ocorre se, e somente se, ${\displaystyle 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 ${\displaystyle U_{1},U_{2},U_{3},...,}$ onde cada mensagem ${\displaystyle U_{i}}$ pode assumir r valores com probabilidades ${\displaystyle p_{1},p_{2},...,p_{r}}$.

É mais eficiente combinar duas ou mais mensagens ${\displaystyle (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 ${\displaystyle 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 ${\displaystyle U_{l}}$ é r-ária, V terá ${\displaystyle r^{v}}$ possíveis símbolos. É possível expressar H(V) em termos de H(U). Considerando ${\displaystyle q_{j}}$ a probabilidade do j-ésimo símbolo de V, temos que as mensagens ${\displaystyle U_{l}}$ são mutuamente independentes, então:

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

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

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

${\displaystyle 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}})}$

${\displaystyle 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}})}$

${\displaystyle 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}}}$

${\displaystyle 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)}$

${\displaystyle 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)}$

${\displaystyle 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: ${\displaystyle H(V){\text{ bits}}\leq L_{av}<H(V)+1{\text{ bits}}}$, temos que um valor ν maior produzirá ${\displaystyle 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:

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

Sabendo que ${\displaystyle H(V)=vH(U)}$, temos:

${\displaystyle {\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:

${\displaystyle 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 ${\displaystyle L_{av}/v}$ de dígitos de código binário por símbolo da fonte satisfaz:

${\displaystyle {\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

${\displaystyle {\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.

Referências