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) bits \leq L_{a v} \leq H (U) + 1 bits$ ,

em que

$L_{a v} = \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.^[1]

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}} \dots 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} l o g_{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) = - (\sum_{i_{1} = 1}^{r} p_{i_{1}} \log_{2} p_{i_{1}}) . (\sum_{i_{2} = 1}^{r} p_{i_{2}}) . . . (\sum_{i_{v} = 1}^{r} p_{i_{v}}) - . . . - (\sum_{i_{1} = 1}^{r} p_{i_{1}}) . . . (\sum_{i_{v - 1} = 1}^{r} p_{i_{v - 1}}) . (\sum_{i_{v} = 1}^{r} p_{i_{v}} \log_{2} p_{i_{v}})$

$H (V) = - (\sum_{i_{l} = 1}^{r} p_{i_{l}} \log_{2} p_{i_{l}}) - . . . - (\sum_{i_{v} = 1}^{r} p_{i_{v}} \log_{2} p_{i_{v}})$

$H (V) = H (U_{l}) + . . . + H (U_{v}) = v H (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) bits \leq L_{a v} < H (V) + 1 bits$ , temos que um valor ν maior produzirá $L_{a v}$ 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_{a v}}{v} < \frac{H (V)}{v} + \frac{1}{v}$ bits

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

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

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

$H (U) \leq \frac{L_{a v}}{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_{a v} / v$ de dígitos de código binário por símbolo da fonte satisfaz:

$\frac{L_{a v}}{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_{a v}}{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

↑ Moser,Stefan M. Chen,Po-Ning. A Student's Guide to Coding and Information Theory. National Chiao Tung University (NCTU), Hsinchu, Taiwan.

[1] Moser,Stefan M. Chen,Po-Ning. A Student's Guide to Coding and Information Theory. National Chiao Tung University (NCTU), Hsinchu, Taiwan.

[1]

Teorema de codificação da fonte

Índice

Codificação de Fonte