Códigos de Hamming

Códigos de Hamming

Um código de Hamming adiciona um bloco de paridade a um bloco de dados, de forma a que, caso ocorram erros de transmissão, seja possível detectar ou corrigir erros do bloco transmitido.

É formado da seguinte maneira, constrói-se uma matriz H cujas colunas são formadas por todos os vetores não nulos de dimensão p = c – d. O código de Hamming consiste no espaço nulo da matriz H, i.e., as palavras de código verificam Hc=0.

Exemplo:
Código (3,1) -> 1 bit dados + 2 bits redundância

H=[0 1 1 1 0 1]

O espaço nulo de H é composto pelos vetores [0 0 0] e [1 1 1].

Detecção de erros

Como as palavras de código pertencem ao espaço nulo de H, é muito simples verificar se houve erro de transmissão: Basta verificar se a palavra recebida pertence ao espaço nulo:

Se Hr = 0, então r pertence ao espaço nulo --> OK!
Se Hr ≠ 0, então r não pertence a null(H) --> ERRO!

Exemplo:
Se c=000 e r=000, Hr = [0 0]' --> sem erros
Se c=000 e r=001, Hr = [1 1]' --> erros detectados
Se c=000 e r=101, Hr = [1 0]' --> erros detectados
Se c=000 e r=111, Hr = [0 0]' --> sem erros

Note que se existirem 3 erros é recebida uma palavra válida e não são detectados erros.

Escolhendo o número de bits de paridade:

O número de colunas de H é igual a 2p-1, que deve ser compatível com a dimensão do vetor r. Então d+p = 2p-1

Regra de Hamming: d - p -1 ≤2p

Se a igualdade se verificar, diz-se que é um código perfeito. Os códigos de Hamming designam-se pelo par (c,d)

Exemplos:

p d c código
3 4 7 (7,4)
4 11 15 (15,11)
5 26 31 (31,26)