Teoria da informação

O panorama: bits, redundância e ruído

Imagine uma brincadeira de adivinhação: eu penso num número de 1 a 8 e você faz perguntas de sim ou não. Você sempre precisa de exatamente 3 perguntas: "é maior que 4?", "está na metade de cima do que sobrou?", e assim por diante. Cada resposta sim/não vale 1 bit. Então escolher uma coisa entre 8 possibilidades iguais carrega 3 bits.

Duas ideias explicam o assunto inteiro. A primeira é a redundância. Se eu escrevo "Obrigaaaaado", os a extras não contam nada. A redundância pode ser removida para a mensagem ficar menor (compressão), ou adicionada de propósito para proteger a mensagem (correção de erros).

A segunda ideia é o ruído. Um caminho ruidoso inverte alguns bits. Não dá para impedir, mas dá para montar a mensagem de um jeito que o estrago apareça.

origem --> comprimir --> proteger --> CAMINHO RUIDOSO
(foto,     (tirar o     (bits extras          (bits podem
 texto)     desperdício)  inteligentes)         inverter)
                                                |
usuário <-- descomprimir <-- conferir <---+

Informação e entropia de Shannon

Se eu digo "o sol nasceu hoje", você não aprende nada: já sabia. Se eu digo "nevou no deserto hoje", você aprende muito, porque era muito improvável. Quanto mais rara a notícia, mais informação ela carrega.

Shannon transformou isso em número. Um evento com probabilidade p carrega I = −log2(p) bits, chamada de autoinformação. O log2 só pergunta: "quantas vezes preciso dividir as possibilidades ao meio para chegar a este evento?"

Entropia: a surpresa média

Uma fonte (uma moeda, um texto, um arquivo) produz muitos símbolos. A entropia é a autoinformação média, ponderada por quanto cada símbolo aparece:

H = soma de  p * log2(1 / p)   sobre todos os símbolos

moeda justa:   1/2*1 + 1/2*1             = 1 bit
1/2, 1/4, 1/4:  0,5*1 + 0,25*2 + 0,25*2  = 1,5 bits
1/2,1/4,1/8,1/8: 0,5 + 0,5 + 0,375 + 0,375 = 1,75 bits

A entropia é medida em bits por símbolo. É um limite inferior: nenhum código sem perdas que olha um símbolo por vez consegue, em média, usar menos bits por símbolo. Usar o logaritmo natural (base e) só muda a unidade para nats; a base 10 dá hartleys. O resultado é a mesma quantidade multiplicada por uma constante.

Quando a entropia é grande ou pequena?

• Uma fonte com um único símbolo possível tem H = 0. Não há surpresa, então um arquivo de 5.000 bytes iguais pode ser descrito em poucas palavras.
• Com n símbolos igualmente prováveis, H = log2(n). Esse é o máximo: uma moeda justa tem 1 bit, um dado justo de 4 faces tem 2 bits, 256 valores de byte igualmente frequentes têm 8 bits.
• Qualquer desequilíbrio reduz H. Uma moeda que dá cara 90% das vezes tem só cerca de 0,47 bit por jogada.

A fórmula para dois resultados é a entropia binária: H(p) = −p·log2(p) − (1−p)·log2(1−p). Ela é simétrica: H(0,1) = H(0,9).

Duas variáveis juntas

• A entropia conjunta H(X, Y) é a incerteza do par. Ela é no máximo H(X) + H(Y), e é igual exatamente quando X e Y são independentes. Uma moeda justa e uma escolha entre 4 opções, independentes, dão 1 + 2 = 3 bits (8 pares iguais).
• A informação mútua I(X; Y) diz quanto saber Y reduz sua dúvida sobre X. Vale 0 para variáveis independentes. Se Y sempre determina X, chega a H(X). Não importa se Y é "igual" ou "o oposto" de X: um fio que inverte todo bit ainda conta tudo.

Codificação de fonte e códigos de prefixo

Um código é uma tabela: o símbolo de um lado, os bits do outro. Escolher bem a tabela se chama codificação de fonte. A tabela mais simples dá a todos os símbolos o mesmo número de bits (um código de comprimento fixo). Para guardar 26 letras você precisa de ⌈log2(26)⌉ = 5 bits por letra, porque 4 bits só fazem 16 padrões. Isso desperdiça 6 dos 32 padrões.

O comprimento médio de um código é L = soma de p × comprimento. Exemplo: A, B, C, D com probabilidades 0,5, 0,25, 0,125, 0,125 e códigos 0, 10, 110, 111. Então L = 0,5 + 0,5 + 0,375 + 0,375 = 1,75 bits, contra 2 bits de um código fixo, uma economia de 12,5%.

O problema de saber onde a palavra termina

Com comprimentos variáveis, como o leitor sabe onde uma palavra-código termina? Um código de prefixo resolve isso. Compare os códigos 0, 10, 110, 111 (código de prefixo) e 0, 01, 10 (não é: 0 é o começo de 01).

          (raiz)
         0/    \1
         A     (*)
             0/   \1
             B    (*)
                0/   \1
                C     D

A = 0   B = 10   C = 110   D = 111

Para decodificar 0101100111, leia bit a bit e pare na primeira palavra-código que reconhecer: 0 = A, 10 = B, 110 = C, 0 = A, 111 = D. Como nenhuma palavra começa outra, o primeiro acerto está sempre certo. Isso se chama decodificação instantânea.

Três famílias de códigos

• Códigos de prefixo (instantâneos): decodificam enquanto você lê, sem esperar.
• Códigos unicamente decodificáveis: só há uma maneira de dividir qualquer mensagem, mas pode ser preciso esperar. O código 0, 01, 011, 0111 não é de prefixo, mas todo 0 começa uma palavra nova, então é unicamente decodificável. Depois de ler 01 você precisa ver o próximo bit para saber se é B ou o começo de C.
• Códigos não singulares: símbolos diferentes têm palavras diferentes, nada mais. Os códigos de prefixo estão dentro dos unicamente decodificáveis, que estão dentro dos não singulares.

A desigualdade de Kraft

Quais comprimentos são possíveis? Uma palavra-código de comprimento l gasta uma fração 2^(−l) da árvore. Um código de prefixo binário com comprimentos l1, ..., ln existe se e somente se soma de 2^(−li) ≤ 1. Para comprimentos 1, 2, 3, 3: 1/2 + 1/4 + 1/8 + 1/8 = 1 (árvore cheia). Para comprimentos 1, 1, 2, 2: 1/2 + 1/2 + 1/4 + 1/4 = 1,5 > 1, então é impossível.

O teorema da codificação de fonte

Para uma fonte com entropia H, o melhor código de prefixo que codifica um símbolo por vez tem comprimento médio L com H ≤ L < H + 1. O limite inferior nunca pode ser vencido. O superior é alcançado dando a cada símbolo o comprimento ⌈log2(1/p)⌉; a parte extra (menos de 1 bit) vem do arredondamento para bits inteiros. Codificar grupos de símbolos dilui esse desperdício.

Codificação de Huffman

David Huffman achou uma receita simples para construir o melhor código de prefixo possível, símbolo a símbolo. É um algoritmo guloso: a cada passo faz a melhor coisa local, e isso acaba sendo o melhor global.

1. Crie uma folha para cada símbolo, com sua frequência.
2. Pegue os dois nós de menor frequência e dê a eles um novo pai, cuja frequência é a soma.
3. Repita até sobrar um nó: a raiz.
4. Marque as arestas da esquerda com 0 e as da direita com 1. O código de um símbolo é o caminho da raiz até ele.

1. C(1) + D(1)    -> nó 2
2. B(2) + nó 2     -> nó 4
3. A(5) + nó 4     -> raiz 9

        (9)
       /   \
      A    (4)        A = 0    (1 bit)
          /   \       B = 10   (2 bits)
         B    (2)     C = 110  (3 bits)
             /   \    D = 111  (3 bits)
            C     D

5*1 + 2*2 + 1*3 + 1*3 = 15 bits (bytes normais: 9*8 = 72)

Uma conferência rápida: o custo total também é igual à soma dos pesos de todos os nós internos, 2 + 4 + 9 = 15. Com probabilidades 0,40, 0,30, 0,15, 0,10 e 0,05, o mesmo método dá comprimentos 1, 2, 3, 4, 4 e média de 2,05 bits, enquanto a entropia é cerca de 2,01 bits.

Fatos sobre a árvore e seu custo

• Todo nó interno tem exatamente dois filhos (uma árvore binária cheia). Com n símbolos distintos há n folhas, n − 1 nós internos e 2n − 1 nós no total. Seis símbolos dão 5 nós internos.
• O passo "os dois menores, de novo e de novo" é feito com um min-heap. O heap entrega o mínimo em O(log n). São n − 1 junções, então construir a árvore custa O(n log n).
• Na prática n é pequeno (no máximo 256 valores de byte), então o tempo é dominado pela leitura do arquivo.

O que vai no arquivo comprimido

O leitor precisa da mesma árvore. Por isso o arquivo guarda um cabeçalho com a tabela de frequências, a árvore, ou só os comprimentos dos códigos (o truque do Huffman canônico). O cabeçalho é um custo fixo, então arquivos muito pequenos podem ficar maiores depois de comprimidos.

Quão perto da entropia?

• Sempre H ≤ L < H + 1.
• L é igual a H exatamente quando todas as probabilidades são potências de 1/2 (1/2, 1/4, 1/8, ...). Aí os comprimentos ideais são inteiros. O exemplo de 800 bytes com probabilidades 1/4, 1/4, 1/4, 1/8, 1/8 tem H = 2,25 bits e o Huffman chega exatamente a 1.800 bits = 225 bytes.
• O Huffman nunca usa menos de 1 bit por símbolo. Para uma moeda com 99% de cara a entropia é 0,08 bit, mas o Huffman ainda paga 1 bit, ou seja, é 12 vezes pior que o limite. As curas são codificar blocos de símbolos ou usar a codificação aritmética.

Codificação aritmética e a família LZ

O Huffman só olha o quanto cada símbolo é comum. Duas outras ideias vão além. A codificação aritmética resolve o problema do "número inteiro de bits". A família LZ aproveita partes da mensagem que voltam a aparecer.

Codificação aritmética: um número numa régua

Pegue a régua de 0 a 1. Para cada símbolo, fique só com a fatia da régua que corresponde à probabilidade dele e dê zoom nela para o próximo símbolo. No fim, a mensagem inteira é um intervalo pequeno, e você anota qualquer número dentro dele.

0                                1
|--------A--------|-----B------|   passo 1: A = [0, 0,6)
0                0,6
|----A----|----B----|             passo 2, dentro de A:
0        0,36     0,6            B = [0,36, 0,60)

A regra para cada símbolo: novo low = low + largura × (probabilidade antes do símbolo) e nova largura = largura × P(símbolo). Para AB: largura 0,6 × 0,4 = 0,24, intervalo [0,36, 0,60). A largura final é a probabilidade da mensagem inteira. Um intervalo largo precisa de poucos bits para apontar dentro dele, um estreito precisa de mais, então o custo é cerca de −log2(probabilidade da mensagem), muito perto da entropia.

A grande diferença para o Huffman: o custo de cada símbolo é uma fração de bit. Com um símbolo de probabilidade 0,95, o Huffman desperdiça muito (pelo menos 1 bit a cada vez), enquanto a codificação aritmética fica a cerca de 2 bits da entropia da mensagem inteira.

LZ77: aponte para o que você já escreveu

O LZ77 mantém uma janela deslizante dos últimos bytes que viu. Quando o texto à frente já apareceu na janela, ele escreve uma referência curta: (distância, comprimento), que significa "volte distância, copie comprimento símbolos". O LZ77 clássico escreve triplas (offset, comprimento, símbolo): copie comprimento símbolos de offset atrás e depois acrescente um símbolo literal. Quando nada se repete, escreve (0, 0, símbolo). Assim a tripla (5, 3, 'x') acrescenta 4 símbolos: três copiados mais o x.

saída até agora:  a b
tripla (2, 4, 'c'):  copie um símbolo por vez, 2 atrás
  a b -> a b a -> a b a b -> a b a b a -> a b a b a b
  depois o literal c   => ababab c

Repare que a cópia pode ser maior que o offset, porque o decodificador lê símbolos que acabou de escrever. É assim que uma sequência da mesma letra vira um token minúsculo (offset 1). O decodificador não precisa de arquivo de dicionário: ele reconstrói a janela enquanto escreve.

O tamanho da janela é um compromisso. Uma janela de 2^k bytes precisa de k bits por offset. Uma janela maior encontra mais repetições, mas cada referência custa mais e a busca é mais lenta. O DEFLATE usa 32 KiB.

LZ78 e LZW: um dicionário explícito

O LZ78 e o LZW mantêm uma tabela numerada de frases que cresce enquanto leem. O LZ77 tem um dicionário implícito (a janela) e esquece os dados antigos. A tabela do LZW lembra frases de qualquer ponto do passado. Exemplo com A = 1, B = 2 e entrada ABABAB:

1. Frase A, lê B: AB é novo. Saída 1, adiciona AB = 3.
2. Frase B, lê A: BA é novo. Saída 2, adiciona BA = 4.
3. Frase A, lê B: AB existe, a frase vira AB. Lê A: ABA é novo. Saída 3, adiciona ABA = 5.
4. Frase A, lê B: AB existe. A entrada acaba: saída 3.
5. Resultado: 1 2 3 3.

DEFLATE: dois passos em ordem fixa

gzip, zip e PNG usam o DEFLATE: primeiro LZ77, depois Huffman. O LZ77 remove trechos repetidos, que um código de símbolos não enxerga. O que ele produz (literais, comprimentos, distâncias) ainda tem frequências desiguais, então o Huffman aperta isso. A ordem importa: a saída do Huffman parece aleatória, então nada poderia ser feito depois dela.

O LZ77 mais Huffman fica abaixo do limite de ordem 0, porque palavras repetidas são uma redundância que a ordem 0 não mede.

Limites da compressão

Existem dois grandes tipos de compressão. A sem perdas devolve exatamente os mesmos bytes (Huffman, LZ77, DEFLATE). É obrigatória para texto, programas e dados. A com perdas joga fora detalhes que as pessoas mal percebem (JPEG, MP3, vídeo), então o que sai é só parecido com o que entrou. O limite da entropia fala da sem perdas.

Comprimir duas vezes não ajuda

Espremer um arquivo de 1 MB até 300 kB e comprimir o resultado de novo quase não muda nada. Comprimir é remover redundância. Depois de um bom trabalho, os bytes parecem quase aleatórios: perto de 8 bits de entropia por byte, sem repetições para achar. A segunda passada não tem o que remover, e os cabeçalhos ainda podem deixar o arquivo um pouco maior. Se repetir sempre encolhesse um arquivo, todo arquivo acabaria com 1 bit, o que é absurdo.

Nenhum compressor encolhe tudo

Um compressor sem perdas precisa dar saídas diferentes para entradas diferentes, senão a decodificação seria ambígua. Existem 2^n arquivos de n bits, mas só 2^0 + 2^1 + ... + 2^(n−1) = 2^n − 1 sequências de bits menores. Não há saídas curtas para todo mundo. Então se um compressor encurta alguns arquivos, ele precisa alongar outros.

Outro exemplo: a codificação por sequências (RLE) escreve cada sequência como um par (contagem, valor), 1 byte cada. É ótima para 50 bytes iguais (2 bytes), mas para 100 bytes em que nenhum byte é igual ao vizinho a saída tem 200 bytes. Formatos reais se protegem guardando um bloco "sem comprimir" quando a compressão não compensa.

A entropia não é o limite final

Os primeiros um milhão de dígitos de π parecem aleatórios para a estatística: os dígitos são quase uniformes, e os compressores comuns quase nada fazem. Mas existe um programa minúsculo que os imprime. O tamanho do menor programa que produz uma sequência é a sua complexidade de Kolmogorov, o limite absoluto da compressão. Ela não pode ser calculada, então nenhum compressor a alcança em geral. A maioria das sequências é quase incompressível; os arquivos que as pessoas usam são um cantinho minúsculo e muito regular de todos os possíveis.

Capacidade de canal e ruído

Um canal é a estrada que a mensagem percorre: um cabo de cobre, ondas de rádio, uma fibra, um disco. Duas coisas limitam a velocidade de envio de bits: quão larga é a estrada (a largura de banda) e quão ruidosa ela é.

Nyquist: o limite de velocidade de um canal limpo

Um sinal limitado a B hertz é completamente descrito por 2B amostras por segundo. Amostrar mais rápido não acrescenta nada. Se cada amostra pode ter V níveis diferentes, ela carrega log2(V) bits. Então a taxa máxima de um canal sem ruído é 2B · log2(V) bits por segundo.

B = 4.000 Hz, V = 8 níveis
2B = 8.000 amostras por segundo
log2(8) = 3 bits por amostra
taxa = 8.000 * 3 = 24.000 bps

Num canal real o ruído impede o uso de muitos níveis, porque você não conseguiria distingui-los. É aí que entra Shannon.

Shannon-Hartley: o limite de um canal ruidoso

A capacidade é C = B · log2(1 + S/N) bits por segundo, onde S/N é a relação sinal-ruído. Nenhuma técnica envia mais rápido que C com taxa de erro minúscula. A capacidade cresce linearmente com a largura de banda, mas só logaritmicamente com S/N: dobrar a potência não dobra a velocidade.

B = 4.000 Hz, S/N = 255 (razão simples)
1 + 255 = 256 = 2^8  ->  log2 = 8
C = 4.000 * 8 = 32.000 bps

A S/N costuma vir em decibéis (dB), uma escala logarítmica: dB = 10 · log10(S/N). Então 10 dB é uma razão de 10, 20 dB é 100 e 30 dB é 1.000. A fórmula pede a razão simples, então converta primeiro.

O canal binário simétrico

O modelo de ruído mais simples é o canal binário simétrico (BSC): cada bit é invertido com probabilidade p, independentemente de todos os outros. O número p é a taxa de erro de bit (BER). Sua capacidade é C = 1 − H(p) bits por uso.

• Com p = 0,5 o bit que chega é um cara ou coroa, então nada sobrevive: capacidade 0.
• A curva é simétrica: p = 0,1 e p = 0,9 têm a mesma capacidade (0,531). O que destrói informação é a imprevisibilidade do ruído. Um canal que sempre inverte (p = 1) é tão bom quanto um perfeito: basta inverter de volta.

Um erro pequeno por bit machuca quadros grandes

Se os bits são danificados de forma independente, um quadro de n bits chega perfeito com probabilidade (1 − p)^n. Para n = 1.000 e p = 0,001 isso dá cerca de 0,368: quase dois terços dos quadros chegam danificados, mesmo com só 1 bit em 1.000 errado. O que importa para um protocolo é a taxa de erro de quadro, não a taxa de erro de bit.

O segundo teorema de Shannon

O teorema da codificação de canal ruidoso diz: se você envia a uma taxa R abaixo da capacidade C, existem códigos (com blocos longos o bastante) que deixam a probabilidade de erro tão pequena quanto você quiser, sem a taxa cair a zero. Acima de C é impossível. O teorema só diz que esses códigos existem; achá-los levou décadas (códigos turbo, LDPC e polares chegam perto do limite).

Detecção de erros: paridade, checksum, CRC

O ruído inverte bits e não dá para impedir. Para perceber o estrago, o remetente acrescenta alguns bits de verificação calculados a partir dos dados. O receptor recalcula: se não batem, algo mudou. Quando o dano é só detectado, a reação habitual é pedir os dados de novo (retransmissão). Em enlaces confiáveis como a fibra isso é mais barato que corrigir.

O bit de paridade

Um bit extra escolhido para que o total de bits 1 seja par (paridade par). Ele é igual ao XOR de todos os bits de dados. Para 1011001 há quatro bits 1, então o bit de paridade é 0. O receptor conta os bits 1 nos 8 bits e reclama se a contagem for ímpar.

A paridade bidimensional organiza os dados numa matriz com um bit de paridade por linha e por coluna. Um único bit errado faz falhar exatamente uma linha e uma coluna, e o cruzamento delas é o culpado: dá para corrigir um erro.

O checksum

Um checksum soma os bytes. Exemplo com soma módulo 256: os bytes 0xA0, 0x70, 0x15 são 160 + 112 + 21 = 293, e 293 mod 256 = 37 = 0x25. É barato, mas só enxerga o total. Trocar dois bytes de lugar, ou subir um byte em k e descer outro em k, mantém a soma, então o erro não é detectado.

CRC: divisão sem vai-um

Um CRC trata a mensagem como um polinômio cujos coeficientes são 0 e 1. Na aritmética módulo 2, somar e subtrair são a mesma coisa: XOR. Os passos: acrescente r zeros (r é o grau do gerador G), divida por G e acrescente o resto (r bits) à mensagem. O quadro completo agora é divisível por G, e é isso que o receptor confere.

1101000
1011
----
 1100
 1011
 ----
  1110
  1011
  ----
   1010
   1011
   ----
    001   <- resto

quadro enviado: 1101 001

• O tamanho do CRC é o grau do gerador: o CRC-16 acrescenta 16 bits, o CRC-32 acrescenta 32 bits, qualquer que seja o tamanho do quadro. Num quadro de 12.000 bits, 32 bits são menos de 0,3%.
• Teste padrão: o CRC-32 do texto 123456789 é 0xCBF43926.
• Se o quadro T(x) é múltiplo de G(x) e o quadro recebido é T(x) + E(x) (E é o padrão de erro), o erro passa despercebido exatamente quando E(x) é um múltiplo não nulo de G(x).
• Uma rajada de comprimento k é detectada com certeza quando k ≤ r, se G tem termo constante 1. Então o CRC-16 pega toda rajada de até 16 bits.
• Para dano aleatório longo, um CRC de r bits deixa passar um quadro ruim com probabilidade cerca de 2^(−r): no CRC-32, 1 em 4,3 bilhões.

Correção de erros: códigos de repetição e de Hamming

Detectar um erro é bom. Corrigi-lo sem pedir de novo é melhor quando não há volta (uma sonda espacial, um disco, a memória). Custa mais bits extras. A ideia-chave é a distância.

Distância de Hamming

A distância de Hamming entre 10110 e 11100 é 2 (as posições 2 e 4 diferem), o número de bits 1 do XOR delas. Um código só usa algumas palavras como válidas. A menor distância entre duas palavras válidas é a distância mínima d.

As regras: para detectar d erros é preciso d_min ≥ d + 1. Para corrigir d erros é preciso d_min ≥ 2d + 1, para que a palavra danificada continue mais perto da palavra certa do que de qualquer outra. Detecção e correção competem: se a distância 3 é usada para corrigir 1 erro, você abre mão de detectar dois.

O código de repetição

A ideia mais simples: enviar cada bit três vezes e fazer votação por maioria. É o código (3,1): as palavras válidas são 000 e 111, a distância 3. Os blocos 011, 110, 010 dão os bits 1, 1, 0. Um erro por bloco é corrigido. Dois erros num bloco enganam o código.

Com taxa de erro de bit p = 0,1, um bit é entregue errado quando 2 ou 3 das cópias estão invertidas: 3 × 0,01 × 0,9 + 0,001 = 0,028. O erro cai de 10% para 2,8%, mas você envia 3 vezes mais bits. A taxa de um código (n, k) é k/n; aqui, 1/3.

Hamming(7,4)

O Hamming(7,4) pega 4 bits de dados e acrescenta 3 bits de paridade: 7 bits numa palavra, taxa 4/7 ≈ 0,57, ainda corrigindo um erro. Das 128 palavras possíveis de 7 bits, só 16 são válidas, e quaisquer duas diferem em pelo menos 3 posições. Os bits de paridade ficam nas posições 1, 2 e 4 (potências de dois).

posição    1   2   3   4   5   6   7
conteúdo   p1  p2  d1  p4  d2  d3  d4

p1 confere as posições 1, 3, 5, 7
p2 confere as posições 2, 3, 6, 7
p4 confere as posições 4, 5, 6, 7

Codificando os dados 1011 (d1=1, d2=0, d3=1, d4=1): p1 cobre d1, d2, d4 = 1, 0, 1, então p1 = 0. p2 cobre d1, d3, d4 = 1, 1, 1, então p2 = 1. p4 cobre d2, d3, d4 = 0, 1, 1, então p4 = 0. Palavra: 0110011.

Decodificando: recalcule cada grupo. Um grupo com número ímpar de bits 1 dá 1. Leia os três resultados como um número binário p4 p2 p1: a síndrome. Exemplo: recebido 0110001: o grupo de p1 é par (0), o de p2 é ímpar (1), o de p4 é ímpar (1). A síndrome é 110 = 6, então inverta a posição 6 e obtenha 0110011.

Por que funciona? A posição 6 pertence exatamente aos grupos de p2 e p4, e a posição de cada bit é a soma dos bits de paridade que o cobrem.

Quantos bits de paridade?

Com m bits de dados e r bits de paridade, a síndrome tem 2^r valores. Ela precisa dizer "sem erro" ou nomear uma das m + r posições, então m + r + 1 ≤ 2^r. Para m = 8: r = 3 dá 12 > 8, não; r = 4 dá 13 ≤ 16, sim: o código (12, 8). Para m = 4, r = 3 cabe exatamente (8 ≤ 8), por isso o Hamming(7,4) é chamado de código perfeito.

Dois erros é demais

Com dois bits invertidos, a síndrome é o XOR de duas posições, que aponta para um terceiro bit. O decodificador o inverte e passa a ter três bits errados, achando que está tudo bem. Exemplo: erros nas posições 1 e 2 dão síndrome 3 e uma inversão na posição 3.

O Hamming estendido (8,4) acrescenta um bit de paridade geral e eleva a distância para 4 (SECDED: correção de erro simples, detecção de erro duplo). Síndrome zero e paridade certa: sem erro. Síndrome diferente de zero e paridade errada: um erro, corrija. Síndrome diferente de zero e paridade certa: dois erros, só detectados. É o esquema da memória ECC.

Rajadas e intercalação

Erros reais muitas vezes vêm em rajadas. A intercalação escreve k palavras como linhas de uma matriz e a envia coluna por coluna. Vizinhos no canal viram palavras diferentes, então uma rajada de até k bits deixa no máximo um erro por palavra, que o Hamming conserta. Sem redundância extra, mas com atraso: a matriz inteira precisa chegar primeiro.

Codificações de texto e binário: ASCII, UTF-8, base64

Um computador só guarda números. Para guardar texto, todo mundo combina uma tabela: letra para número, e número para bytes. Essa tabela é uma codificação.

ASCII

O ASCII tem 128 posições (7 bits): 33 caracteres de controle e 95 imprimíveis. Um byte tem 8 bits, então sobrava um bit, e vários países o usaram de formas incompatíveis. O ASCII não tem letras acentuadas, e por isso foram criados o Unicode e o UTF-8.

UTF-8

O Unicode dá um número (um ponto de código) a cada caractere do mundo. O UTF-8 é um jeito de escrever esses números como 1 a 4 bytes. Os primeiros 128 caracteres ocupam 1 byte idêntico ao ASCII, então os programas antigos continuam funcionando.

• Um byte que começa com 0 é um caractere inteiro. 110, 1110, 11110 começam um caractere de 2, 3, 4 bytes. 10 marca um byte de continuação.
• Assim a palavra ação tem 4 caracteres mas 6 bytes: a, ç (2), ã (2), o. Bytes e caracteres são contagens diferentes.
• Para contar caracteres, conte os bytes que não são de continuação. Em 48 C3 A9 E2 82 AC 21 os bytes iniciais são 48, C3, E2 e 21, então há 4 caracteres (H, é, €, !).
• Como bytes iniciais e de continuação usam faixas separadas, o UTF-8 é autossincronizante: se você começa no meio, acha o próximo caractere em até 3 bytes, e um caractere nunca aparece dentro de outro.

base64

Alguns canais antigos, como o e-mail, só carregam texto seguro. O base64 reescreve quaisquer bytes usando 64 caracteres seguros: A-Z, a-z, 0-9, + e /. Ele pega 3 bytes (24 bits), divide em quatro grupos de 6 bits e escreve um caractere para cada. Se o final fica incompleto, o = completa o bloco de 4.

'Hi' = 0x48 0x69 = 01001000 01101001
grupos de 6: 010010 | 000110 | 100100 (completado)
valores:     18       6        36
letras:      S        G        k      depois '='
resultado: SGk=

• Cada caractere de saída carrega 6 bits mas ocupa um byte: eficiência de 75%, então a saída é 4/3 (cerca de 33% maior) que a entrada.
• Tamanho com preenchimento: 4 × teto(n / 3). Para 10 bytes: 4 × 4 = 16 caracteres (o último grupo tem 1 byte, escrito como 2 caracteres e ==).

Codificação, hash e criptografia comparados

Três palavras que as pessoas confundem o tempo todo. Todas transformam dados em algo que parece diferente, mas seus objetivos são muito diferentes.

Hashes criptográficos

Um hash como o SHA-256 transforma qualquer entrada numa saída de tamanho fixo. É determinístico (mesma entrada, mesma saída), unidirecional (achar uma entrada para uma saída dada é inviável, a chamada resistência à pré-imagem) e resistente a colisões (achar duas entradas com a mesma saída é inviável). Infinitas entradas compartilham cada saída, então não há nada para "desfazer".

Guardando senhas

O sistema não precisa saber sua senha, só conferir se você digitou a mesma. Então guarda o hash e compara com o hash do que você digita. Dois reforços: um sal faz senhas iguais terem hashes diferentes e acaba com tabelas prontas; e um hash deliberadamente lento limita os palpites por segundo.

CRC contra hash criptográfico

Um arquivo é entregue com seu CRC-32. Isso prova que ninguém o mudou de propósito? Não. Um acidente não escolhe quais bits mudar, e o CRC o pega. Um atacante escolhe: o CRC é público e linear, então ele muda o arquivo e conserta o CRC. Para resistir a um adversário use um hash criptográfico obtido por um canal confiável, um MAC (um hash com chave secreta) ou uma assinatura digital.

Comprimir primeiro, depois criptografar

A compressão precisa de redundância para remover. Uma boa cifra produz bytes que parecem aleatórios, sem redundância. Então comprima antes de criptografar; a outra ordem quase não encolhe nada. Uma observação de segurança: se um atacante controla parte do texto e vê o tamanho da saída, comprimir antes de criptografar pode vazar informação pelo comprimento (os ataques CRIME e BREACH ao HTTPS).

Como tudo se conecta

Olhe um arquivo viajando do seu computador até um amigo. Cada ideia desta página tem um lugar na estrada.

texto --UTF-8--> bytes --LZ77+Huffman--> menos bits
  --cifrar--> bytes aleatórios --CRC/Hamming--> quadro
  --CANAL RUIDOSO (limite: Shannon)--> quadro danificado
  --conferir/consertar--> bytes --decifrar--> descomprimir

Erros comuns

• Achar que base64 ou UTF-8 escondem dados (eles só codificam).
• Acreditar que um CRC ou um hash simples protege contra um inimigo.
• Usar o valor em dB direto na fórmula de Shannon.
• Esquecer que o Huffman paga pelo menos 1 bit por símbolo.
• Comprimir dados já comprimidos ou criptografados e esperar ganho.
• Confiar num decodificador Hamming quando dois bits podem estar errados.
• Misturar a entropia de ordem 0 com o limite real de um compressor que usa contexto.