Codificação de Fonte (Linguagem das Moedas 4/9)

Introdução à Teoria da Codificação (codificação de fonte pelo comprimento da variável), em um problema de compressão sem perdas. Este problema simplificado lida apenas com o envio de símbolos unários ("plucs") para envio de símbolos singulares. A Codificação de Fonte se destina a comprimir os dados da fonte de maneira a transmití-los com maior eficiência.

Vamos começar com um problema ...

[VENTO SOPRANDO]

Alice e Bob vivem em casas nas árvores,

muito longe um do outro,

fora da linha de visão.

Eles precisam se comunicar.

Portanto, decidiram colocar um arame

entre as duas casas.

[ruído do vento, barulho, perturbação] Eles esticaram o fio firmemente

e juntaram uma lata a cada uma das extremidades,

lhes permitindo enviar a voz

fracamente através do fio.

[Bob - Você pode ouvir um "Olá" muito vago]

[Alice]: Eu não consigo ouvir.

[Bob]: Eu ouço, mas mal

[Alice]: 1, 2, 3, 4, 5

No entanto, há um problema.

Ruído.

Sempre que há um vento forte,

torna-se impossível ouvir

o sinal sobre o ruído.

Assim, eles precisam de uma maneira de aumentar

o nível de energia do sinal

para separá-lo do ruído.

Isso dá a Bob uma idéia.

Eles podem simplesmente dar puxões no fio,

o que pode ser mais fácil de detectar no meio do ruído.

Mas isso leva a outro problema:

como codificar a mensagem como "plucs"?

Bem, já que eles querem jogar

jogos de tabuleiro à distância,

eles lidam com as mensagens mais comuns primeiro.

O resultado do lançamento de dois dados.

Neste caso, as mensagens podem ser enviadas

podem ser pensadas como uma seleção

de um número finito de símbolos.

Neste caso, os 11 números possíveis,

o que chamamos de uma fonte "discreta".

Inicialmente, decidiram usar o método mais simples.

Enviar o resultado como o número de "plucs".

Então, para enviar três, três "plucs".

9 tem 9 "plucs",

12 tem 12 "plucs"

No entanto, eles logo perceberam que isso leva

muito mais tempo do precisa.

Na prática, eles descobriram que a velocidade máxima é de

2 "plucs" por segundo.

Mais rápido, confunde.

Assim, dois "plucs" por segundo pode ser considerado como a velocidade

ou a capacidade de transferir informação desta forma.

[SONS DE PLUCS]

Acontece que o

resultado mais comum é sete.

O número 7 leva 3,5 segundos para ser enviado.

[SOM DE 7 PLUCS]

Alice, então, vê que você pode fazer muito melhor

se eles mudaram a estratégia de codificação.

Ele reconhece que as chances de enviar cada número

seguem um padrão simples.

Há uma maneira de tirar o dois;

duas maneiras de tirar o 3;

três de tirar o 4;

quatro para tirar o 5;

cinco para tirar o 6;

e seis maneiras de tirar o 7,

o resultado mais comum;

cinco para para tirar o 8;

quatro maneiras de jogar o 9,

e assim por diante até uma maneira de jogar do 12.

Esse é um gráfico que mostra

o número de possibilidades para que cada resultado ocorra,

O padrão é óbvio.

Então agora vamos mudar o gráfico para

o número de "plucs" atribuído a cada símbolo.

Ela seguiu relacionando

o número mais comum no mapa,

7, ao sinal mais curto, um "pluc"

[SOM DE UM PLUC]

Ela, então, prosseguiu para o próximo desfecho mais provável seguinte,

e se havia um empate, escolhia um aleatoriamente.

Neste caso, ela selecionou 6 para dois "plucs" ,

8 para três "plucs",

e, em seguida, de volta para 5 para quatro "plucs",

e 9 são quatro "plucs"

e assim por diante, até chegarmos a 12,

que é associado aos onze "plucs".

Agora, o número 7, mais comum,

pode ser enviado em menos de um segundo,

um enorme aperfeiçoamento.

Essa simples mudança permite que eles enviem

mais informação na mesma média de tempo.

Neste caso simples, essa estratégia de codificação é ótima,

para este exemplo singelo,

uma vez que não é possível

chegar a uma método mais curto

para enviar o resultado do lançamento de dois dados com os mesmos "plucs".

No entanto, depois de brincar com o arame por um tempo,

Bob tem uma nova idéia

[PLUCS TOCADOS AO FUNDO]

[PLUCS TOCADOS EM VELOCIDADE REDUZIDA - SEM SOM]