Paridade, código de Hamming, distância de Hamming, somas de verificação e CRC
Escreva os bits de dados e calculam-se os de paridade. Depois clique em qualquer bit da palavra para o mudar como se fosse um erro de transmissão, e veja o que faz o recetor: o síndrome indica a posição do bit errado. Experimente com um e com dois erros, com e sem o bit de paridade global.
paridade · dados · paridade global · bit mudado.
Escreva a trama em bytes hexadecimais (com ou sem espaços) ou como texto. A coluna «na trama» dá os bytes pela ordem em que se enviam.
Nenhum canal é perfeito: uma trama RS-485 que passa junto a um variador, um bit de memória atingido por uma partícula ou um risco num disco podem mudar um 0 para 1. Para dar por isso, o emissor junta aos dados alguns bits de redundância calculados a partir deles, e o recetor repete o cálculo. Se não coincidir, há duas estratégias:
A distância de Hamming entre duas palavras do mesmo tamanho é o número de bits em que diferem: entre 1011101 e 1001001 há 2. A distância mínima \(d\) de um código é a menor entre duas palavras válidas quaisquer, e fixa o que ele pode fazer:
| Código | Distância mínima | Deteta | Corrige |
|---|---|---|---|
| Dados sem redundância | 1 | nada | nada |
| Bit de paridade, 2 de 5 | 2 | 1 erro | nada |
| Hamming | 3 | 2 erros | 1 erro |
| Hamming com paridade global (SECDED) | 4 | 3 erros | 1 erro e deteta 2 |
| Repetir cada bit 3 vezes | 3 | 2 erros | 1 erro (por maioria) |
A ideia é geométrica: se as palavras válidas estão pelo menos a distância 3, uma palavra com um erro continua mais perto da original do que de qualquer outra.
É o código mais simples: junta-se um bit para que o número total de uns seja par (paridade par) ou ímpar (paridade ímpar). Deteta qualquer número ímpar de erros, mas não dois bits mudados ao mesmo tempo. É a paridade das portas série (8E1 são 8 bits de dados, paridade par e 1 bit de paragem; o Modbus RTU usa paridade par por omissão) e de algumas memórias antigas. Num circuito calcula-se com uma cadeia de portas XOR.
Com a paridade bidimensional, os dados colocam-se numa tabela e junta-se a paridade de cada linha e de cada coluna. Um erro muda a paridade de uma linha e de uma coluna, e o seu cruzamento indica o bit a corrigir.
Richard Hamming idealizou-o em 1950, farto de que as falhas das máquinas de relés lhe arruinassem os cálculos do fim de semana. As posições da palavra numeram-se a partir de 1; as que são potências de 2 (1, 2, 4, 8…) levam bits de paridade e as restantes os dados. Cada bit de paridade \(p_k\) cobre as posições cujo número em binário tem a 1 o bit de peso \(k\): \(p_1\) cobre 1, 3, 5, 7…; \(p_2\) cobre 2, 3, 6, 7…; \(p_4\) cobre 4–7, 12–15… Com \(r\) bits de paridade protegem-se \(m\) bits de dados se:
Os dados vão nas posições 3, 5, 6 e 7. \(p_1 = d_1 \oplus d_2 \oplus d_4 = 1 \oplus 0 \oplus 1 = 0\), \(p_2 = d_1 \oplus d_3 \oplus d_4 = 1\) e \(p_4 = d_2 \oplus d_3 \oplus d_4 = 0\). A palavra enviada é \(0110011\). Se chegar \(0110111\) (falha a posição 5), o recetor recalcula as três paridades sobre o que recebeu: \(s_1 = 1\), \(s_2 = 0\), \(s_4 = 1\). O síndrome \(s_4 s_2 s_1 = 101_2 = 5\) é exatamente a posição do erro, e basta inverter esse bit.
| Código | Bits de dados | Bits de paridade | Rendimento |
|---|---|---|---|
| Hamming (7, 4) | 4 | 3 | 57 % |
| Hamming (15, 11) | 11 | 4 | 73 % |
| Hamming (31, 26) | 26 | 5 | 84 % |
| Hamming (63, 57) | 57 | 6 | 90 % |
| SECDED (72, 64), memória ECC | 64 | 8 | 89 % |
Com dois erros, o Hamming simples dá um síndrome diferente de zero e «corrige» um bit que estava bem, piorando a palavra. Para o evitar junta-se um bit de paridade global P sobre toda a palavra (single error correction, double error detection):
É o esquema da memória ECC dos servidores e de muitos microcontroladores para automóvel e segurança: 8 bits de controlo por cada 64 de dados.
São rápidas e fáceis de programar, mas detetam bastante pior do que um CRC do mesmo tamanho.
O CRC trata a mensagem como um polinómio de coeficientes 0 e 1 (\(1011 = x^3 + x + 1\)) e divide-a por um polinómio gerador de grau \(r\). Nesta aritmética (módulo 2), somar e subtrair são o mesmo que o OU exclusivo e não há transportes. O emissor junta \(r\) zeros à mensagem, divide e envia o resto no seu lugar; o recetor divide a trama inteira e, se não houver erros, o resto é 0.
Juntam-se 3 zeros e divide-se subtraindo (XOR) o gerador sob cada 1 que resta à esquerda. O resto é 100, por isso envia-se 11010011101100100. É o exemplo que vem carregado na calculadora acima.
Com um bom polinómio de grau \(r\), o CRC deteta:
Além do polinómio, cada CRC define o valor inicial do registo, se os bits de cada byte entram refletidos (começando pelo de menor peso, como saem de uma UART), se o resultado é refletido e com que valor se faz o OU exclusivo final. Por isso CRC-16/MODBUS, CRC-16/ARC e CRC-16/CCITT dão resultados diferentes com os mesmos dados. Para saber qual usa um equipamento, calcula-se o da cadeia de texto 123456789 e compara-se com o seu valor de verificação: 4B37 para Modbus, 29B1 para CCITT-FALSE, CBF43926 para CRC-32.
Relacionado: conversor binário e hexadecimal, código 2 de 5 e simulador de portas lógicas (a XOR).