Códigos corretores de erros explicados
Nenhum canal é perfeito. Os raios cósmicos invertem bits na memória, os riscos apagam partes de um disco e os sinais de rádio desvanecem. Em vez de esperar pelo melhor, os sistemas digitais acrescentam redundância de forma engenhosa, para que o recetor consiga descobrir o que foi enviado mesmo quando uma parte chega errada. A matemática destes códigos, iniciada no final da década de 1940, protege discretamente quase todos os bits que guardamos ou enviamos.
Detetar erros com a paridade
A proteção mais simples é um único bit de paridade: acrescenta-se um 1 ou um 0 para que o número total de uns seja par. Se um bit se inverter pelo caminho, a contagem fica ímpar e o recetor sabe que algo correu mal. A paridade não consegue dizer qual é o bit errado, e duas inversões anulam-se sem que se note, mas é barata e foi usada durante décadas em memórias e ligações série. No entanto, detetar um erro é só metade do trabalho: depois os dados têm de ser enviados de novo.
Corrigir por repetição
Para corrigir um erro sem voltar a pedir, o recetor precisa de redundância suficiente para o vencer por maioria. Enviar cada bit três vezes, 000 ou 111, permite ao recetor ficar com a maioria: uma inversão num trio é corrigida. O preço é alto: três bits por cada bit de dados, e duas inversões no mesmo trio continuam a ganhar. A pergunta que deu origem à teoria dos códigos foi se seria possível fazer melhor.
O código de Hamming
Em 1947, Richard Hamming trabalhava nos Bell Labs num computador de relés que lia programas de cartões perfurados. Quando a máquina encontrava um erro durante o fim de semana, simplesmente parava, e na segunda-feira Hamming voltava para encontrar cálculos desperdiçados. Se uma máquina consegue detetar um erro, perguntou ele, porque não consegue localizá-lo e corrigi-lo? A sua resposta, publicada em 1950, envia 4 bits de dados como 7. Três bits de paridade, nas posições 1, 2 e 4, verificam cada um um grupo diferente de posições sobrepostas, escolhido de modo que cada erro isolado quebre uma combinação única de verificações.
A síndrome
O recetor volta a calcular as três verificações. Se todas passarem, a palavra é aceite. Se algumas falharem, escrever as verificações que falham como dígitos binários, com a verificação 4 como dígito mais alto, dá um número de 1 a 7: a síndrome, que é exatamente a posição do bit invertido. Invertê-lo de novo restaura a palavra de código. O truque funciona porque as posições estão numeradas de modo que a representação binária de cada uma enumera as verificações a que pertence, e é por isso que o código parece tão arrumado quando desenhado como três círculos sobrepostos.
A distância de Hamming
A distância de Hamming entre duas palavras é o número de posições em que diferem. No código (7,4), quaisquer duas palavras de código estão a uma distância de pelo menos 3. Uma palavra com um erro continua a distância 1 da palavra de código enviada e a pelo menos 2 de todas as outras, por isso descodificá-la para a palavra de código mais próxima corrige-a. Em geral, um código cujas palavras de código distam pelo menos d deteta d − 1 erros e corrige (d − 1)/2 deles, arredondado por defeito. Acrescentar um bit de paridade global eleva a distância para 4, dando o código estendido que corrige um erro e deteta dois.
O limite de Shannon
Em 1948, dois anos antes do artigo de Hamming, Claude Shannon demonstrou um teorema surpreendente. Todo o canal ruidoso tem uma capacidade, e abaixo dela é possível enviar dados a qualquer ritmo com tão poucos erros quanto se queira, usando códigos suficientemente longos; acima dela, os erros não podem ser evitados. Shannon mostrou que esses códigos existem, mas não como construí-los. Encontrar códigos práticos que se aproximem do seu limite levou meio século, desde os códigos de Reed-Solomon em 1960 até aos turbocódigos em 1993 e à redescoberta dos códigos de verificação de paridade de baixa densidade (LDPC).
Códigos à nossa volta
Os códigos de Reed-Solomon permitem que os CD toquem apesar dos riscos e que os códigos QR sejam lidos com até 30 % do símbolo danificado. A memória dos servidores usa códigos de Hamming estendidos para corrigir bits isolados invertidos por raios cósmicos. As imagens dos planetas exteriores captadas pelas Voyager foram protegidas por códigos de Golay e, mais tarde, de Reed-Solomon, e os códigos LDPC e polares do 5G e do Wi-Fi aproveitam quase todos os bits que o canal permite. Até o código de barras de um livro e o último dígito de um número de conta bancária são códigos simples de deteção de erros.
Explore
Abra o simulador de códigos corretores de erros para codificar quaisquer quatro bits de dados com o código de Hamming (7,4), inverter bits clicando neles nos círculos ou na linha, e ver os círculos que falham e a síndrome apontarem para o erro antes de o descodificador o reparar. Ative o bit de paridade extra para ver erros duplos detetados, e envie uma mensagem por um canal ruidoso para comparar o que chega com e sem o código.
Perguntas frequentes
Qual é a diferença entre deteção e correção de erros?
A deteção apenas diz ao recetor que algo está errado, pelo que tem de voltar a pedir os dados; um bit de paridade ou uma soma de verificação fazem isto. A correção permite ao recetor reconstruir o original sem pedir, o que exige mais redundância. Os sistemas que não podem voltar a pedir, como uma sonda espacial a milhões de quilómetros ou um DVD, dependem da correção.
Porque não enviar simplesmente tudo duas vezes?
Duas cópias mostram que houve um erro, mas não qual das cópias está certa, e duplicam o custo. Três cópias permitem uma votação por maioria, mas triplicam-no. O código de Hamming corrige um erro isolado por bloco de sete com menos do dobro dos bits, e códigos mais longos fazem muito melhor.
Quem foi Richard Hamming?
Um matemático norte-americano, 1915–1998, que trabalhou no Projeto Manhattan e depois durante trinta anos nos Bell Labs. Além dos seus códigos, é conhecido pela janela de Hamming no processamento de sinal, pela distância de Hamming e pela sua palestra «You and Your Research». Recebeu o Prémio Turing em 1968.
Um código consegue corrigir qualquer número de erros?
Só com redundância suficiente. Um código pode corrigir até (d − 1)/2 erros por bloco, onde d é a distância mínima entre palavras de código, e códigos mais longos com mais bits de verificação atingem um d maior. O teorema de Shannon fixa o limite último: nenhum código pode ultrapassar a capacidade do canal.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Abrir o simulador de códigos corretores de erros