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
- 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.
- 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.
- 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