Codificação de fonte

RKA4JL - Começamos com um problema. Alice e Bob moram em fortalezas de árvores que estão distantes, sem linha de visão entre eles, e eles precisam se comunicar. Então, eles decidem correr um fio entre as duas casas. Eles puxam um fio apertado e prendem uma lata em cada extremidade, permitindo que eles enviassem suas vozes levemente ao longo do fio. Entretanto, há um problema: o ruído. Sempre que há vento alto, torna-se impossível ouvir o sinal sobre o ruído. Eles precisam de uma maneira para aumentar o nível de energia do sinal para separá-lo do barulho. Isso dá a Bob uma ideia. Eles podem simplesmente dar arranques no arame, que é muito mais fácil de detectar sobre o ruído. Mas isso leva a um novo problema: como eles devem codificar suas mensagens com arranques? Bem, se que eles quiserem jogar jogos de tabuleiro em uma distância, eles abordam as mensagens mais comuns primeiro, como o resultado de duas rodadas de dados. Neste caso, as mensagens que estão enviando podem ser pensadas como uma seleção de um número finito de símbolos. Neste caso, onze números possíveis que chamamos de fonte discreta. A primeira vez que eles decidem usar o método mais simples, eles enviam o resultado com o número de arranques. Então, para enviar um 3, eles enviam três arranques. 9 são nove arranques e 12 são doze arranques. E logo eles percebem que leva muito mais tempo e descobrem, na prática, que a velocidade máxima de arranques são poucas por segundo. Quanto mais rápidos, mais eles podem ficar confusos. Assim, pode-se pensar que dois arranques por segundo são a taxa ou a capacidade de enviar a informação. E acontece que a rodada mais comum é o número 7. Demora-se 3,5 segundos para enviar o número 7. Alice, então, percebe que eles podem fazer de uma forma melhor. Mudam de estratégia de codificação. Ela percebe que as probabilidades de cada número ser enviado seguem um padrão simples: há uma maneira de rolar um 2, duas maneiras rolar um 3, três maneiras rolar um 4, quatro maneiras rolar um 5, cinco maneiras de rolar um 6 e seis maneiras de rolar um 7, o mais comum. Há cinco maneiras rolar um 8, quatro maneiras de rolar um 9 e assim por diante. Uma maneira para rolar um 12. E este é o gráfico que mostra o número de maneiras que cada resultado pode ocorrer. O padrão é óbvio. Agora, vamos mudar o gráfico para o número de arranques em relação a cada símbolo. Alice prossegue mapeando o número mais comum, o 7, para o sinal mais curto de um arranque. Então, ela passa para o próximo número mais provável. E se houver um empate, ela escolhe um ao acaso. Nesse caso, ela seleciona 6 para ser dois arranques e depois 8 para ser três arranques, e, depois, de volta ao 5 para ser quatro arranques e 9 como cinco arranques, para a frente e para trás até chegar a 12, que é atribuído a onze arranques. Agora, o número mais comum, 7, pode ser enviado em menos de um segundo. Dessa forma, a melhoria é enorme. Essa mudança de símbolo permite que eles enviem mais informações na mesma quantidade média de tempo. Na verdade, essa estratégia de codificação é ideal para este exemplo simples, que é impossível para você chegar a um método mais curto de enviar duas rodadas de dados usando arranques idênticos. Mas depois de brincar com fio por algum tempo, Bob teve uma nova ideia.