Teorema de codificação da fonte de Shannon - Shannon's source coding theorem

Na teoria da informação , o teorema da codificação da fonte de Shannon (ou teorema da codificação silenciosa ) estabelece os limites para possível compressão de dados e o significado operacional da entropia de Shannon .

Nomeado após Claude Shannon , o teorema da codificação de origem mostra que (no limite, como o comprimento de um fluxo de dados de variáveis aleatórias independentes e distribuídas de forma idêntica (iid) tende ao infinito), é impossível compactar os dados de tal forma que a taxa de código (número médio de bits por símbolo) é menor que a entropia de Shannon da fonte, sem ser virtualmente certo que a informação será perdida. No entanto, é possível obter a taxa de código arbitrariamente próxima da entropia de Shannon, com probabilidade de perda desprezível.

O teorema de codificação de fonte para códigos de símbolo coloca um limite superior e um limite inferior no comprimento mínimo esperado possível de palavras de código como uma função da entropia da palavra de entrada (que é vista como uma variável aleatória ) e do tamanho do alfabeto alvo.

Declarações

A codificação de origem é um mapeamento de (uma sequência de) símbolos de uma fonte de informação para uma sequência de símbolos do alfabeto (geralmente bits) de modo que os símbolos de origem possam ser recuperados exatamente dos bits binários (codificação de origem sem perdas) ou recuperados dentro de alguma distorção ( codificação de fonte com perdas). Este é o conceito por trás da compactação de dados .

Teorema de codificação de fonte

Na teoria da informação, o teorema da codificação da fonte (Shannon 1948) afirma informalmente que (MacKay 2003, pg. 81, Capa 2006, Capítulo 5):

$N$ i.id variáveis aleatórias, cada uma com entropia $H (X),$ podem ser compactadas em mais de $N H (X)$ bits com risco desprezível de perda de informação, pois $N \to \infty$ ; mas, inversamente, se eles forem compactados em menos de $N H (X)$ bits, é praticamente certo que as informações serão perdidas.

Teorema de codificação de fonte para códigos de símbolo

Seja $Σ 1, Σ 2$ denotar dois alfabetos finitos e seja $Σ * 1$ e $Σ * 2$ denotam o conjunto de todas as palavras finitas desses alfabetos (respectivamente).

Suponha que $X$ seja uma variável aleatória assumindo valores em $Σ 1$ e seja $f$ um código decodificável exclusivamente de $Σ$ $* 1$ para $Σ * 2$ onde $| Σ 2 | = a$ . Deixe $S$ denotar a variável aleatória dada pelo comprimento da palavra-código $f$ $($ $X$ $)$ .

Se $f$ for ótimo no sentido de que tem o comprimento de palavra mínimo esperado para $X$ , então (Shannon 1948):

{\ displaystyle {\ frac {H (X)} {\ log _ {2} a}} \ leq \ mathbb {E} [S] <{\ frac {H (X)} {\ log _ {2} a }} + 1}

Onde denota o operador de valor esperado . ${\ displaystyle \ mathbb {E}}$

Prova: Teorema da codificação da fonte

Dado que $X$ é uma fonte iid , sua série temporal $X 1, ..., X n$ é iid com entropia $H (X)$ no caso de valor discreto e entropia diferencial no caso de valor contínuo. O teorema de codificação da fonte afirma que para qualquer $ε > 0$ , ou seja, para qualquer taxa $H (X) + ε$ maior do que a entropia da fonte, existe $n$ grande o suficiente e um codificador que leva $n$ iid repetição da fonte, $X 1: n$ , e mapeia para $n (H (X) + ε)$ bits binários de modo que os símbolos de origem $X 1: n$ são recuperáveis dos bits binários com probabilidade de pelo menos $1 - ε$ .

Prova de realizabilidade. Corrija algum $ε > 0$ , e deixe

{\ displaystyle p (x_ {1}, \ ldots, x_ {n}) = \ Pr \ left [X_ {1} = x_ {1}, \ cdots, X_ {n} = x_ {n} \ right]. }

O conjunto típico, $A ε n$ , é definido da seguinte forma:

{\ displaystyle A_ {n} ^ {\ varepsilon} = \ left \ {(x_ {1}, \ cdots, x_ {n}) \: \ \ left | - {\ frac {1} {n}} \ log p (x_ {1}, \ cdots, x_ {n}) - H_ {n} (X) \ right | <\ varepsilon \ right \}.}

A propriedade de equipartição assintótica (AEP) mostra que para $n$ grande o suficiente , a probabilidade de que uma sequência gerada pela fonte esteja no conjunto típico, $A ε n$ , conforme definido se aproxima um. Em particular, para $n$ suficientemente grande , pode ser arbitrariamente próximo a 1 e, especificamente, maior que (consulte AEP para obter uma prova). ${\ displaystyle P ((X_ {1}, X_ {2}, \ cdots, X_ {n}) \ in A_ {n} ^ {\ varepsilon})}$ ${\ displaystyle 1- \ varepsilon}$

A definição de conjuntos típicos implica que as sequências que se encontram no conjunto típico satisfaçam:

{\ displaystyle 2 ^ {- n (H (X) + \ varepsilon)} \ leq p \ left (x_ {1}, \ cdots, x_ {n} \ right) \ leq 2 ^ {- n (H (X ) - \ varepsilon)}}

Observe que:

A probabilidade de uma sequência ser retirada de $A$ ${\ displaystyle (X_ {1}, X_ {2}, \ cdots X_ {n})}$ $ε n$ é maior que $1 - ε$ .
${\ displaystyle \ left | A_ {n} ^ {\ varepsilon} \ right | \ leq 2 ^ {n (H (X) + \ varepsilon)}}$ , que segue do lado esquerdo (limite inferior) para . ${\ displaystyle p (x_ {1}, x_ {2}, \ cdots x_ {n})}$
${\ displaystyle \ left | A_ {n} ^ {\ varepsilon} \ right | \ geq (1- \ varejpsilon) 2 ^ {n (H (X) - \ varepsilon)}}$ , que segue do limite superior e do limite inferior da probabilidade total de todo o conjunto $A$ ${\ displaystyle p (x_ {1}, x_ {2}, \ cdots x_ {n})}$ $ε n$ .

Uma vez que os bits são suficientes para apontar para qualquer string neste conjunto. ${\ displaystyle \ left | A_ {n} ^ {\ varepsilon} \ right | \ leq 2 ^ {n (H (X) + \ varepsilon)}, n (H (X) + \ varejpsilon)}$

O algoritmo de codificação: O codificador verifica se a sequência de entrada está dentro do conjunto típico; se sim, ele produz o índice da sequência de entrada dentro do conjunto típico; caso contrário, o codificador emite um número arbitrário de $n (H (X) + ε)$ dígitos. Desde que a sequência de entrada esteja dentro do conjunto típico (com probabilidade de pelo menos $1 - ε$ ), o codificador não comete nenhum erro. Portanto, a probabilidade de erro do codificador é limitada acima por $ε$ .

Prova de Converse. O inverso é provado mostrando que qualquer conjunto de tamanho menor que $A ε n$ (no sentido de expoente) cobriria um conjunto de probabilidades limitado a $1$ .

Prova: Teorema de codificação de fonte para códigos de símbolo

Para $1 \leq i \leq n,$ deixe $s i$ denotar o comprimento da palavra de cada $x i$ possível . Defina , onde $C$ é escolhido de forma que $q$ $1$ $+ ... +$ $q$ $n$ $= 1$ . Então ${\ displaystyle q_ {i} = a ^ {- s_ {i}} / C}$

{\ displaystyle {\ begin {alinhados} H (X) & = - \ sum _ {i = 1} ^ {n} p_ {i} \ log _ {2} p_ {i} \\ & \ leq - \ sum _ {i = 1} ^ {n} p_ {i} \ log _ {2} q_ {i} \\ & = - \ sum _ {i = 1} ^ {n} p_ {i} \ log _ {2 } a ^ {- s_ {i}} + \ sum _ {i = 1} ^ {n} p_ {i} \ log _ {2} C \\ & = - \ sum _ {i = 1} ^ {n } p_ {i} \ log _ {2} a ^ {- s_ {i}} + \ log _ {2} C \\ & \ leq - \ sum _ {i = 1} ^ {n} -s_ {i } p_ {i} \ log _ {2} a \\ & \ leq \ mathbb {E} S \ log _ {2} a \\\ end {alinhado}}}

onde a segunda linha segue da desigualdade de Gibbs e a quinta linha segue da desigualdade de Kraft :

{\ displaystyle C = \ sum _ {i = 1} ^ {n} a ^ {- s_ {i}} \ leq 1}

então $log C \leq 0$ .

Para a segunda desigualdade, podemos definir

{\ displaystyle s_ {i} = \ lceil - \ log _ {a} p_ {i} \ rceil}

de modo a

{\ displaystyle - \ log _ {a} p_ {i} \ leq s_ {i} <- \ log _ {a} p_ {i} +1}

e entao

{\ displaystyle a ^ {- s_ {i}} \ leq p_ {i}}

e

{\ displaystyle \ sum a ^ {- s_ {i}} \ leq \ sum p_ {i} = 1}

e assim, pela desigualdade de Kraft, existe um código sem prefixo com esses comprimentos de palavra. Assim, o $S$ mínimo satisfaz

{\ displaystyle {\ begin {alinhados} \ mathbb {E} S & = \ sum p_ {i} s_ {i} \\ & <\ sum p_ {i} \ left (- \ log _ {a} p_ {i} +1 \ direita) \\ & = \ sum -p_ {i} {\ frac {\ log _ {2} p_ {i}} {\ log _ {2} a}} + 1 \\ & = {\ frac {H (X)} {\ log _ {2} a}} + 1 \\\ end {alinhado}}}

Extensão para fontes independentes não estacionárias

Codificação de fonte sem perdas de taxa fixa para fontes independentes não estacionárias de tempo discreto

Defina o conjunto típico $A ε n$ Como:

{\ displaystyle A_ {n} ^ {\ varepsilon} = \ left \ {x_ {1} ^ {n} \: \ \ left | - {\ frac {1} {n}} \ log p \ left (X_ { 1}, \ cdots, X_ {n} \ right) - {\ overline {H_ {n}}} (X) \ right | <\ varepsilon \ right \}.}

Então, para dado $δ > 0$ , para $n$ grande o suficiente, $Pr (A ε n)> 1 - δ$ . Agora, apenas codificamos as sequências no conjunto típico, e os métodos usuais na codificação de origem mostram que a cardinalidade desse conjunto é menor que . Assim, em média, $H$ $n$ $($ $X$ $) +$ $ε$ bits são suficientes para codificar com probabilidade maior que $1 -$ $δ$ , onde $ε$ e $δ$ podem ser arbitrariamente pequenos, tornando $n$ maior. ${\ displaystyle 2 ^ {n ({\ overline {H_ {n}}} (X) + \ varepsilon)}}$

Languages

In other projects