A Matriz de Verificação de Paridade
Todo código linear sobre GF(2) — o corpo com apenas 0 e 1, aritmética módulo 2 — possui uma matriz de verificação de paridade H. Para o código Hamming (7,4), H é uma matriz 3×7 cujas colunas são as representações binárias de 1 a 7:
``
H = [ 0 0 0 1 1 1 1 ] ← bit 2 da representação da posição
[ 0 1 1 0 0 1 1 ] ← bit 1 da representação da posição
[ 1 0 1 0 1 0 1 ] ← bit 0 da representação da posição
``
A coluna j de H é a representação binária de j. É por isso que a síndrome s = Hr nomeia diretamente a posição do erro.
O mapa H: GF(2)^7 → GF(2)^3 é um mapa linear (multiplicação de matrizes mod 2). Seu núcleo ker(H) = { r : Hr = 0 } é exatamente o conjunto de palavras-código válidas.
Contagem de dimensão: dim(ker H) = 7 − rank(H) = 7 − 3 = 4. Portanto, existem 2^4 = 16 palavras-código. Isso confirma 4 bits de mensagem.
O Código como um Núcleo
Uma palavra c ∈ {0,1}^7 é uma palavra-código válida se e somente se Hc = 0 (mod 2). Esta é a equação definidora de um código linear.
Exemplo: c = 0011001. Verifique Hc mod 2:
``
Linha 1: 0·0+0·0+0·1+1·1+1·0+1·0+1·1 = 0+0+0+1+0+0+1 = 2 ≡ 0
Linha 2: 0·0+1·0+1·1+0·1+0·0+1·0+1·1 = 0+0+1+0+0+0+1 = 2 ≡ 0
Linha 3: 1·0+0·0+1·1+0·1+1·0+0·0+1·1 = 0+0+1+0+0+0+1 = 2 ≡ 0
``
Hc = 000. Portanto, 0011001 é uma palavra-código válida.
Classes Laterais do Código
As palavras-código C = ker(H) formam um subgrupo de GF(2)^7. Todas as outras palavras em GF(2)^7 pertencem a exatamente uma classe lateral de C.
Definição de classe lateral: para qualquer palavra e, a classe lateral C + e = { c + e : c ∈ C }.
Duas palavras pertencem à mesma classe lateral se e somente se sua diferença é uma palavra-código — equivalentemente, se têm a mesma síndrome: H(r₁) = H(r₂) se e somente se H(r₁ − r₂) = 0 se e somente se r₁ − r₂ ∈ C.
O mapa de síndrome H induz um isomorfismo GF(2)^7 / C ≅ GF(2)^3. Com |C| = 16 e |GF(2)^7| = 128: existem exatamente 128/16 = 8 classes laterais, uma para cada valor de síndrome em GF(2)^3.
Matriz padrão: liste um líder de classe lateral por classe lateral — a palavra de peso de Hamming mínimo naquela classe lateral. Para correção de erro único, cada síndrome não-zero corresponde uniquamente a um padrão de erro de peso-1 (um único 1 em uma das 7 posições). É por isso que 7 padrões de erro + 1 sem-erro = 8 classes laterais = 2^3.
Decodificação via Líderes de Classe Lateral
Algoritmo de decodificação: receba r → compute s = Hr → procure o líder de classe lateral e_s (o padrão de erro canônico para síndrome s) → produza r − e_s = r + e_s (igual em GF(2)).
Para o código (7,4), os 8 líderes de classe lateral são: 0000000 (síndrome 000), 1000000 (síndrome 001), 0100000 (síndrome 010), 0010000 (síndrome 011), 0001000 (síndrome 100), 0000100 (síndrome 101), 0000010 (síndrome 110), 0000001 (síndrome 111).
Por que (7,4) é Perfeito
Um código C ⊆ GF(2)^n com distância mínima 3 corrige todos os erros únicos. Cada palavra-código c tem uma esfera de Hamming de raio 1: o centro c e seus n vizinhos imediatos (padrões de erro de peso-1). Volume da esfera = 1 + n.
Para n = 7: volume da esfera = 8. Com 16 palavras-código: 16 × 8 = 128 = 2^7. As esferas ladrilham GF(2)^7 perfeitamente — nenhum ponto deixado descoberto, nenhum ponto coberto duas vezes.
Esta é a definição de um código perfeito: M · Vol(n, t) = 2^n. Códigos perfeitos corretores de erro único binários (t=1) existem apenas para parâmetros específicos: (7,4), (15,11), (23,12) (o código de Golay binário), e trivialmente n = 2^r − 1, k = n − r para qualquer r ≥ 2.
A geometria: GF(2)^7 se decompõe em exatamente 8 órbitas sob a ação do código como uma partição de classe lateral. Cada órbita é uma classe lateral; cada classe lateral tem uma síndrome única. O mapa de síndrome H é uma bijeção de classes laterais para GF(2)^3.
O Argumento de Contagem
Para um código perfeito corretor de erro único em n = 2^r − 1 bits com r bits de verificação de paridade:
- Número de palavras-código: M = 2^k = 2^(n−r)
- Volume da esfera: Vol(n, 1) = 1 + n = 1 + 2^r − 1 = 2^r
- Total coberto: M × Vol = 2^(n−r) × 2^r = 2^n ✓
O fato de Vol(n,1) = 2^r quando n = 2^r − 1 é o que torna códigos perfeitos possíveis nestes comprimentos. Em outros comprimentos, 1 + n não é uma potência de 2, e códigos binários perfeitos corretores de erro único não podem existir.
Matriz Geradora & Dualidade
A matriz de verificação de paridade H define o código via o núcleo. Seu dual: uma matriz geradora G cujas linhas formam uma base para ker(H).
Para o código (7,4): G é uma matriz 4×7. Qualquer palavra-código c = mG para algum vetor de mensagem m ∈ GF(2)^4. As linhas de G abrangem o código; as linhas de H abrangem o espaço nulo do código.
Relação-chave: HG^T = 0 (mod 2). Cada linha de G está em ker(H); cada linha de H anula cada linha de G.
Código dual: C⊥ = ker(G^T) = image(H^T). Para o código (7,4), o dual é um código (7,3) — um código [7,3,4] com distância mínima 4.
A geometria da dualidade: C e C⊥ são subespaços ortogonais de GF(2)^7. Todo o espaço se decompõe no código, suas classes laterais, e a estrutura dual que o mapa de síndrome codifica.