Código de Hamming: corrigir um bit identificando a sua posição

Carregue em Uma inversão. O bit 5 é invertido no canal; os círculos 1 e 4 passam a conter um número ímpar de uns, enquanto o círculo 2 continua par: 1 + 4 = 5. Esta coincidência não foi preparada pelo exemplo. O círculo k verifica exatamente as posições cuja representação binária contém k; assim, um bit errado na posição i altera precisamente os círculos cuja soma é i. A posição de cada bit no diagrama é o seu endereço. Foi isto que Hamming procurou em 1950: um «número de verificação» que indicasse a posição de qualquer erro isolado, reservando o zero para a ausência de erros. Três verificações permitem oito respostas, exatamente as necessárias para a palavra de sete bits: sete posições e «sem erro». Não sobra nenhuma. Das 128 palavras de sete bits, 16 são palavras de código; as outras 112 resultam de uma única inversão e estão todas a uma inversão de exatamente uma palavra de código. A tabela sob o gráfico descodifica corretamente as 112. A razão para os bits de paridade ocuparem as posições 1, 2 e 4 é mais simples do que parece. Essas posições têm um único 1 na representação binária, pelo que cada bit de paridade pertence apenas a um círculo e pode ser definido pela sua própria verificação, precisamente a justificação apresentada por Hamming.

Carregue em Duas inversões. Os bits 3 e 5 ficam errados. O círculo 1 contém ambos, sofre duas alterações e continua par; os círculos 2 e 4 tornam-se ímpares e a síndrome indica 6, uma posição perfeitamente válida. O descodificador inverte o bit 6, que estava certo. À chegada havia dois bits de dados errados; depois da correção há três. A grelha mostra o mesmo resultado para todos os pares: os 21, portanto todas as 336 inversões duplas nas 16 palavras de dados, entregam dados errados sem sinalização. Carregue em Só bits de paridade: as posições 1 e 2 não transportam dados, portanto estes chegam intactos, mas a síndrome 3 manda o descodificador estragar d₁. Agora carregue em Estendido, duas. O oitavo bit torna par o conjunto dos oito; uma inversão deixa sempre a verificação global ímpar, enquanto duas a deixam par. Perante uma verificação global par e uma síndrome diferente de zero, o descodificador sinaliza a palavra sem lhe tocar, em todas as 448 inversões duplas. Não consegue corrigi-las: 3 e 5 produzem a síndrome 6, tal como 1 e 7. Hamming começou precisamente pela necessidade de sinalizar. O seu artigo de 1950 abre com os dois computadores de relés construídos pelos Bell Labs para o Aberdeen Proving Ground. Nenhuma falha de relé passava despercebida; no período inicial ocorriam cerca de duas ou três por dia entre 8 900 relés e, quando as máquinas funcionavam sem supervisão durante as noites e os fins de semana, paravam com frequência.

Repetir cada bit duas vezes e usar o código estendido consome, em ambos os casos, oito bits para transmitir quatro. Quando as duas cópias divergem, sabe-se que houve um erro, mas não qual delas está certa; o recetor só pode sinalizar o bloco. Para p = 0,01, isso acontece em 7,69×10⁻² dos blocos, enquanto 3,77×10⁻⁴ passam errados quando ambas as cópias de um bit se invertem. O código de Hamming estendido corrige todas as inversões isoladas, sinaliza 2,64×10⁻³ e deixa passar 5,34×10⁻⁵: com o mesmo número de bits, produz 29 vezes menos sinalizações e 7 vezes menos blocos errados. As linhas tracejadas e contínuas mostram a sua vantagem nas duas medidas até p ultrapassar 0,066, valor correspondente a um canal que inverte um bit em cada quinze. Repetir cada bit três vezes supera o código de sete bits por bloco em todos os valores de p disponíveis no seletor, 1,19×10⁻³ contra 2,03×10⁻³ neste ponto. Contudo, usa 12 bits em vez de 7; por isso, a comparação justa é a que usa oito.