Codigo de Hamming

...

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

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

[pic 3]

2.1 Determinação da posição do bit errado

Para a determinar a posição do bit errado, aplica-se a expressão abaixo:

[pic 4]

Assim sendo, a combinação binaria C3 C2 C1 indicara a posição do bit errado. Sendo C3 o bit mais significativo (Msb).

Quando os valores das funções C3, C2 e C1 são zero, isto é:

C3 C2 C1 = 0 0 0 não há erro. Caso contrário, C3 C2 C1 = 1 0 0 = 4, indica que a posição do bit errado é onde se localiza o b4.

3. Detecção e correção de erros Hamming

3.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: verifica- se a palavra recebida r 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

3.2 Correcção de erros

Detecta-se um erro quando Hr diferente de 0. Usando um vector ei = [0 ... 0 1 0 ... 0] para representar a posição onde ocorre o erro, temos que r = c + ei. Então, Hr = H(c+ei) = Hc + Hei = Hei. Mas Hei corresponde à i-ésima coluna de H. Portanto, calculando Hr e procurando em H, obtêm-se a posição i onde ocorreu o erro. Para o corrigir, basta invertê-lo.

4. Códigos de Hamming -Codificação

1.Os bits da palavra de código são numerados a partir da esquerda, começando por 1;

2.É acrescentada informação redundante em posições pré-definidas, ou seja, os bits que são potência de 2 vão ser bits de controlo (2n);

3.Os restantes são preenchidos com k bits de dados conhecidos, isto é, com a mensagem a transmitir;

[pic 5]4. Cálculo dos bits de controlo, isto é, conversão para binário das posições ≠2n e valor=1. 3-001, 7-111;

5. Aplicação do OR Exculsivo (XOR -⊕) aos valores obtido no ponto anterior

0 1 1

1 1 1

1 0 0

3ª2ª1ª

6.Inserção dos valores obtidos nas respectivas posições dos bits de paridade (ponto 2.)

[pic 6]

7. Mensagem a transmitir: 00110011

5. Códigos de Hamming -Descodificação

1. Conversão para binário das posições=1;

2. Aplicação do OR Exclusivo (XOR -⊕) aos valores obtido no ponto anterior:

- Se o resultado for = 0, não houve erros na transmissão;

- Se for ≠0, o resultado obtido convertido para decimal é igual à posição do erro.

Sem erro: 0 0 1 1 0 0 1 0 1 1

3ª 4ª 7ª 1 0 0[pic 7]

3- 0 1 1 1 1 1

4-1 0 0 1 1 1[pic 8]

7-1 1 1 0 0 0

Com erro: 0 0 0 1 0 0 1

4ª 7ª 10 0

4-100 1 1 1

7-111 0 1 1 → erro na posição 3

Código correcto: 0 0 1 1 0 0 1

6. Distância de Hamming e distância mínima

Seja um vector de código representado por X= (x1 x2...xn).

Um código é linear quando:

- inclui o vector nulo

- a soma de dois vectores do código é ainda um vector do código.

Soma de vectores: XY= (x1 y1 x2y2 ...xn=yn) xi,yi= 0,1[pic 9][pic 10][pic 11]

Peso do vector X, w(X): Número de elementos não nulos do vector.

Ex: Se X= (101101) w (X) = 4[pic 12]

Distância de Hamming, d (X, Y), entre quaisquer dois vectores do código: número de elementos diferentes.

Exemplo: [pic 13]

Z=X= (0 1 1 1 0 0 0); w (Z) =w= 3=(X, Y)[pic 14][pic 15]

Distância mínima de um código, dmin é a menor distância de Hamming entre dois vectores válidos do código.

A distância de Hamming de entre X e Y é igual ao peso de um vector do código, [pic 16]

Logo a menor distância de Hamming é igual ao menor peso.

dmin=[w(X)]min X≠ ( 0 0 ...0)

7. Código de Hamming (7,4)

Palavras de código:

0000 000 0100 101 1000 011 1100 110

0001 111 0101 010 1001 100 1101 001

0010