Bits invertidos
Síndrome
Recebido
Bits de dados por bit enviado

Mais sobre códigos corretores de erros

Simulador de códigos corretores de erros

Todas as mensagens que viajam por um fio, pelo ar ou num disco riscado apanham erros: os bits passam de 0 para 1 e vice-versa. Um código corretor de erros acrescenta alguns bits extra escolhidos com cuidado para que o recetor possa encontrar e reparar o dano sem voltar a pedir. Introduza quatro bits de dados, veja o código de Richard Hamming transformá-los em sete, inverta o bit que quiser e veja três círculos sobrepostos apontarem diretamente para o erro. Depois envie uma mensagem inteira por um canal ruidoso e compare o que chega com e sem o código. Introduza quatro bits de dados, por exemplo 1011, e a aplicação acrescenta três bits de paridade para formar uma palavra de código de Hamming de 7 bits. Clique em qualquer bit, nos círculos ou na linha, para o inverter como faria o ruído; clique de novo para o repor. Cada círculo tem de conter um número par de uns: os círculos que falham apontam para o bit errado, e o descodificador repõe-no. Ative o bit de paridade extra para ver dois erros detetados em vez de mal corrigidos. Mais abaixo, envie um texto por um canal ruidoso com e sem o código.

Como funciona

  1. Introduza quatro bits de dados e veja a palavra de código de sete bits com os seus três bits de paridade, em círculos e numa linha.
  2. Clique nos bits para os inverter e veja que círculos falham, para onde aponta a síndrome e se o descodificador repara a palavra.
  3. Ative o bit de paridade extra, depois envie uma mensagem pelo canal ruidoso e compare os resultados com e sem o código.

Como o código de Hamming encontra um erro

Os sete bits são numerados de 1 a 7. Os bits 1, 2 e 4 são bits de paridade, e os quatro bits de dados ficam nas posições 3, 5, 6 e 7. O bit de paridade 1 torna par o número de uns entre as posições 1, 3, 5 e 7, aquelas cujo número em binário termina em 1; o bit 2 faz o mesmo para 2, 3, 6 e 7, e o bit 4 para 4, 5, 6 e 7. Desenhando as verificações como três círculos sobrepostos, cada bit fica exatamente nos círculos que o verificam. Quando um bit se inverte, os círculos que o contêm tornam-se ímpares. Leia as verificações que falham como um número binário, a síndrome, e obtém a posição do bit errado.

O que um bit a mais permite

Com dois bits invertidos, a síndrome aponta para um terceiro bit inocente, e o descodificador piora as coisas. Acrescentar um oitavo bit que torna par a palavra inteira resolve isso: um erro altera a paridade global, dois erros deixam-na par enquanto alguns círculos falham. O código estendido, conhecido como SECDED (single error correction, double error detection: correção de um erro, deteção de dois), corrige um erro e deteta dois de forma fiável, para que o recetor possa pedir esse bloco de novo. É o código usado na memória ECC dos servidores. Num canal ruidoso, o código transforma muitos erros dispersos em poucos, desde que raramente caiam duas inversões no mesmo bloco.

Perguntas frequentes

Porque estão os bits de paridade nas posições 1, 2 e 4?

Porque são as potências de dois, e cada uma tem um único 1 em binário. O bit de paridade 2ᵏ verifica todas as posições cujo número binário tem um 1 na casa k. Um bit invertido na posição 6 = 110 em binário quebra as verificações de 2 e 4 e deixa a de 1 intacta, e as verificações que falham formam 110, a própria posição.

Quanto custa a proteção?

O código (7,4) envia 7 bits por cada 4 bits de dados, uma taxa de 4/7: 75 % a mais. O código estendido envia 8 por 4, o dobro. Códigos de Hamming mais longos são mais baratos: 15 bits transportam 11 bits de dados, 31 transportam 26. Códigos modernos como os códigos LDPC e os códigos polares, usados no Wi-Fi e no 5G, aproximam-se muito da melhor taxa que Claude Shannon provou ser possível em 1948.

O que acontece com três erros?

O código de Hamming simples pode ser completamente enganado: quaisquer duas palavras de código diferem em pelo menos três bits, por isso três inversões podem transformar uma palavra de código válida noutra, e nenhuma verificação falha. A aplicação indica isto como erro não detetado. Os sistemas reais mantêm estes casos raros escolhendo um código suficientemente forte para o nível de ruído.

Onde são usados os códigos corretores de erros?

Quase em todo o lado onde dados digitais circulam ou são guardados: memória ECC de computadores, discos rígidos e SSD, CD, DVD e discos Blu-ray, códigos QR, que continuam legíveis mesmo com um pedaço arrancado, telemóveis e Wi-Fi, televisão digital e mensagens de sondas espaciais como as Voyager, que ainda enviam dados de além do Sistema Solar.

A minha mensagem é enviada para algum lado?

Não. O canal ruidoso é simulado no seu navegador, e a sua mensagem e definições ficam no armazenamento local deste navegador.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Ir para o editor