Hamming, 1950: três bits de verificação para corrigir um erro

Artigo redigido e traduzido por um sistema de IA a partir das fontes citadas, com verificações automatizadas segundo o método editorial News.

Manutenção — 7 de outubro de 2026. A capa foi substituída porque seu arquivo original e comprovante de geração não puderam ser recuperados nos acessos disponíveis. A nova imagem foi recebida da ferramenta nativa e inspecionada visualmente; arquivo, instruções e referências são preservados no registro editorial privado. A capa anterior e sua procedência não verificada permanecem no histórico. Trata-se de uma ilustração, não de evidência experimental; o resultado científico central é mantido.

Ilustração conceitual gerada por IA do código de Hamming (7,4): quatro bits de dados, três bits de verificação e correção de uma inversão por bloco. Peças simbólicas, não um circuito.

Antes das equações

Um bit é um valor, 0 ou 1. Uma inversão troca um pelo outro. A paridade indica se um grupo contém um número par ou ímpar de uns. Por exemplo, 101 contém dois uns: sua paridade é par. Redundância significa transmitir informações adicionais que permitam conferir os dados. Aqui, três verificações sobrepostas localizam um bit invertido, desde que haja no máximo um em um bloco de sete bits.

Para compreender a ideia, acompanhe o exemplo da seção 3 e depois volte às equações da seção 2. Para verificar, use o programa completo abaixo. Pergunte-se: uma verificação bem-sucedida prova que nenhum bit mudou? A seção 5 explica por que a resposta depende do modelo de erro.

1. Confiabilidade com redundância estruturada

Em abril de 1950, Richard W. Hamming publicou “Error Detecting and Error Correcting Codes” no Bell System Technical Journal. O problema era prático: detectar uma falha em um cálculo sem supervisão podia interromper o trabalho; localizá-la e corrigi-la podia permitir continuar. O artigo apresenta construções binárias explícitas, não a promessa de reparar qualquer dano. [1,2]

O avanço consiste em tornar a redundância informativa. Repetir cada um de quatro bits três vezes exige doze bits transmitidos. Um código de Hamming utiliza sete para proteger os mesmos quatro bits contra qualquer inversão única no bloco. São formas diferentes de organizar a redundância, não uma prova de superioridade para todos os canais. A compressão remove redundância; a correção de erros adiciona uma forma controlada dela.

2. Sete posições, três perguntas

Numere as posições de 1 a 7. As posições 1, 2 e 4 contêm verificações; 3, 5, 6 e 7 contêm os dados d₁, d₂, d₃ e d₄. ⊕ significa OU exclusivo, a soma módulo 2: 1 ⊕ 1 = 0. As equações impõem paridade par. Os índices de p indicam posições, não a ordem das verificações. [1, §3]

$p_1=d_1\oplus d_2\oplus d_4$p1​=d1​⊕d2​⊕d4​

$p_2=d_1\oplus d_3\oplus d_4$p2​=d1​⊕d3​⊕d4​

$p_4=d_2\oplus d_3\oplus d_4$p4​=d2​⊕d3​⊕d4​

O receptor verifica {1,3,5,7}, {2,3,6,7} e {4,5,6,7}. Uma verificação que falha gera um bit de síndrome 1; uma satisfeita gera 0. Chamemos esses bits de s₁, s₂ e s₄. Supondo no máximo uma inversão, sua posição j é:

$j=s_1+2s_2+4s_4$j=s1​+2s2​+4s4​

Síndrome zero indica ausência de erro apenas nessa hipótese; não é um certificado universal de integridade.

3. Uma correção reproduzível

Considere os dados 1010. As equações dão p₁ = 1, p₂ = 0 e p₄ = 1. A palavra transmitida, lida da esquerda para a direita na ordem das posições, é 1011010. Se o bit 6 inverter, chega 1011000. A primeira verificação é par; a segunda e a terceira são ímpares. Logo, (s₁,s₂,s₄) = (0,1,1) e j = 0 + 2 + 4 = 6. Inverta novamente o bit 6 e leia 3,5,6,7: os dados recuperados são 1010.

Esquema científico produzido por código; sequências exatas, não dados experimentais.

É um cálculo editorial, não uma medição experimental. O procedimento também corrige um bit de verificação invertido. Ele pressupõe limites de bloco e posições conhecidos; bits inseridos ou removidos pertencem a outro modelo de erro.

4. Por que a construção funciona

Três verificações binárias têm oito resultados possíveis: exatamente o necessário para distinguir sete posições de erro único e a ausência de erro. Em geral, um código binário com r verificações e n bits precisa de pelo menos n + 1 síndromes distintos para corrigir uma inversão:

$2^r\ge n+1$2r≥n+1

A construção atinge essa contagem com n = 2ʳ − 1 e k = n − r bits de dados. Para r = 3, n = 7 e k = 4. Sua distância mínima de Hamming — o menor número de posições diferentes entre palavras válidas — é 3. Uma palavra recebida não pode estar a uma inversão de duas palavras válidas distintas, pois estas teriam distância de no máximo 2.

Há 16 palavras válidas, cada uma com sete vizinhas de uma inversão. Incluindo a própria palavra, esses conjuntos disjuntos cobrem as 128 possibilidades: 16 × 8 = 128. “Perfeito” descreve esse empacotamento, não funcionamento infalível com qualquer ruído. [1, §§5,7]

5. A armadilha dos dois erros

Duas inversões sempre produzem síndrome não nula: um detector que apenas sinalize palavras inválidas consegue detectá-las. Porém, interpretar toda síndrome não nula como erro único pode causar uma correção errada. Inverter as posições 2 e 5 gera a mesma síndrome que inverter a 7. Corrigir o bit 7 deixa três bits errados e outra palavra válida.

Um oitavo bit que torne par a paridade total eleva a distância mínima a 4. O código estendido permite corrigir um erro e detectar dois: SECDED. As decisões abaixo supõem no máximo duas inversões. q é a paridade dos oito bits recebidos. [1, §4]

Três ou mais erros estão fora da garantia. Um decodificador SECDED pode corrigir alguns deles incorretamente; detectar dois erros não significa diagnosticar qualquer falha maior.

6. Um benefício numérico, com hipóteses explícitas

Suponha inversões independentes com probabilidade p = 0,01, igual para 0 e 1, codificação e decodificação perfeitas e limites de bloco conhecidos. Com o código de sete bits e este decodificador, a mensagem recuperada está errada exatamente quando há pelo menos duas inversões:

$\begin{aligned} P_{\rm fail}&=1-(1-p)^7\\ &\quad-7p(1-p)^6. \end{aligned}$Pfail​​=1−(1−p)7−7p(1−p)6.​

O resultado é aproximadamente 0,002031, ou 0,2031% dos blocos. Para os quatro dados sem codificação, 1 − (1 − p)⁴ = 0,039404: 3,9404% das mensagens contêm erro. São probabilidades de erro de mensagem, não taxas residuais por bit nem desempenho medido de um dispositivo.

O custo é de três bits adicionais para quatro dados: 75% mais bits transmitidos e taxa de código 4/7 ≈ 0,5714 bit de dados por bit transmitido. A comparação mantém p fixo, não simultaneamente largura de banda, tempo de transmissão e energia por mensagem.

7. O que o resultado promete — e o que não promete

A contribuição duradoura liga álgebra e confiabilidade de modo construtivo: separar palavras válidas, calcular verificações compactas e localizar uma falha limitada. O caso de sete bits pode ser verificado exaustivamente. Para este artigo, foram testadas as 16 mensagens e seus 128 casos sem erro ou com um erro, além dos 448 casos de dois erros do código estendido.

Isso não corrige rajadas arbitrárias, software corrompido, alterações maliciosas ou perda de sincronização. Sistemas reais precisam ajustar o código ao modelo de falhas e proteger codificador, decodificador e lógica ao redor. Hamming não apresenta medições de hardware moderno; nosso exemplo numérico é separado dessas alegações. O tema complementa os limites de comunicação de Shannon com uma construção finita explícita, não uma solução universal que alcance a capacidade.

8. Reproduzir o cálculo finito

Protocolo HAMMING-REPRO-1. Copie o bloco Python completo para reproduce_hamming.py e execute python3 reproduce_hamming.py. Ele usa apenas a biblioteca padrão do Python, sem rede, download de dados ou semente aleatória. Foi executado com CPython 3.12.14 nesta revisão editorial. As posições começam em 1; o oitavo bit estabelece paridade total par. O programa enumera as 16 mensagens, constrói separadamente as palavras válidas de sete bits pelas restrições de paridade e as compara com o codificador.

Saída esperada: status PASS, codewords 16, minimum_distances [3, 4]. Os contadores são 128 recuperações corretas com zero ou um erro em sete bits; 144 em oito bits; 448 erros duplos detectados pelo código estendido; 336 erros duplos corrigidos incorretamente pelo decodificador de sete bits; e 896 erros triplos corrigidos incorretamente pelo decodificador de oito bits descrito. Os dois últimos são controles negativos: mostram limites, não correções bem-sucedidas. Para p = 0,01, coded_message_error é aproximadamente 0,00203104163494 e uncoded_message_error 0,03940399. Essas probabilidades pressupõem inversões independentes com p fixo, não energia ou largura de banda iguais.

"""News HAMMING-REPRO-1: finite mathematical check, not hardware validation."""
from itertools import combinations, product
import json
import platform


def encode(data):
    a, b, c, d = data
    return (a ^ b ^ d, a ^ c ^ d, a, b ^ c ^ d, b, c, d)


def syndrome(word):
    a, b, c, d, e, f, g = word[:7]
    return (a ^ c ^ e ^ g) + 2 * (b ^ c ^ f ^ g) + 4 * (d ^ e ^ f ^ g)


def flip(word, positions):
    result = list(word)
    for position in positions:
        result[position - 1] ^= 1
    return tuple(result)


def decode7(word):
    position = syndrome(word)
    return flip(word, (position,)) if position else word


def decode8(word):
    position, parity = syndrome(word), sum(word) % 2
    if parity:
        return flip(word, (position or 8,))
    return None if position else word


def distance(a, b):
    return sum(x != y for x, y in zip(a, b))


def require(condition, label):
    if not condition:
        raise RuntimeError(label)


messages = list(product((0, 1), repeat=4))
code7 = [encode(data) for data in messages]
code8 = [word + (sum(word) % 2,) for word in code7]
# Independent enumeration uses parity sums rather than the encoder equations.
groups = ((1, 3, 5, 7), (2, 3, 6, 7), (4, 5, 6, 7))
oracle = {
    word for word in product((0, 1), repeat=7)
    if all(sum(word[p - 1] for p in group) % 2 == 0 for group in groups)
}
require(len(set(code7)) == 16 and set(code7) == oracle, "codebook")
min7 = min(distance(a, b) for a, b in combinations(code7, 2))
min8 = min(distance(a, b) for a, b in combinations(code8, 2))
require((min7, min8) == (3, 4), "minimum distances")
counts = {"seven_zero_or_one": 0, "eight_zero_or_one": 0,
          "eight_double_detected": 0, "seven_double_miscorrected": 0,
          "eight_triple_miscorrected": 0}
for word in code7:
    for positions in [()] + [(i,) for i in range(1, 8)]:
        require(decode7(flip(word, positions)) == word, "seven-bit recovery")
        counts["seven_zero_or_one"] += 1
    for positions in combinations(range(1, 8), 2):
        received = flip(word, positions)
        require(syndrome(received) != 0, "double error detectable")
        require(decode7(received) != word, "double error outside correction guarantee")
        counts["seven_double_miscorrected"] += 1
for word in code8:
    for positions in [()] + [(i,) for i in range(1, 9)]:
        require(decode8(flip(word, positions)) == word, "eight-bit recovery")
        counts["eight_zero_or_one"] += 1
    for positions in combinations(range(1, 9), 2):
        require(decode8(flip(word, positions)) is None, "double error must be flagged")
        counts["eight_double_detected"] += 1
    for positions in combinations(range(1, 9), 3):
        result = decode8(flip(word, positions))
        require(result is not None and result != word and result in code8,
                "triple error counterexample")
        counts["eight_triple_miscorrected"] += 1
require(list(counts.values()) == [128, 144, 448, 336, 896], "case counts")
require(encode((1, 0, 1, 0)) == (1, 0, 1, 1, 0, 1, 0), "worked example")
require(syndrome((1, 0, 1, 1, 0, 0, 0)) == 6, "worked syndrome")
p = 0.01
failure = 1 - (1-p)**7 - 7*p*(1-p)**6
uncoded = 1 - (1-p)**4
require(abs(failure - 0.00203104163494) < 1e-12, "probability")
print(json.dumps({"protocol": "HAMMING-REPRO-1", "python": platform.python_version(),
                  "codewords": len(code7), "minimum_distances": [min7, min8],
                  "counts": counts, "p": p, "coded_message_error": failure,
                  "uncoded_message_error": uncoded, "status": "PASS"}, indent=2))

PASS significa que essas verificações matemáticas finitas passaram. Não demonstra desempenho de hardware, robustez a outros modelos de erro ou replicação independente. O campo python registra a versão do seu interpretador e pode variar. Se ocorrer RuntimeError, preserve o script e a saída completa e examine a verificação indicada; uma execução parcial não equivale a validação.

Método News deste artigo

2026-10-03 — A revisão HAMMING-EN-2 acrescenta a introdução progressiva e o protocolo completo. O corpo científico e o esquema programado são preservados de HAMMING-EN-1. Nesta atualização, a construção e seus limites foram conferidos novamente no artigo de 1950 e nas seções 5.6–5.7 do MIT; o programa finito foi executado. Redação e traduções são de IA, sem revisão especializada independente ou validação humana.

Fontes

[1] R. W. Hamming — Error Detecting and Error Correcting Codes — DOI: 10.1002/j.1538-7305.1950.tb00463.x.

[2] Nokia Bell Labs — Error Detecting and Error Correcting Codes.

[3] MIT 6.02 — Coping with Bit Errors using Error Correction Codes.