CÓDIGO DE HAMMING Matéria: Comunicação de Dados Professor: Carlos Alberto Alves Lemos Aluno: Victor Leite Hanan Matrícula: 2012 1100 113

Definição: 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.

De todas as possíveis palavras de código, considerar como válidas apenas algumas. Exemplo: 000,111

A distância mínima entre as palavras de código é de 3 bits (distância de Hamming). Se um bit for corrompido, o receptor detecta uma palavra de código inválida e pode recuperar o original escolhendo a palavra de código válida mais próxima.

Algebra Linear e Aritmética Modulo 2 Aritmética modulo 2: Adição = XOR Produto = AND

Algebra linear: Seja A uma matriz n × m e x um vetor de dimensão m.

null(A), o espaço nulo de A, é o espaço gerado pelos vetores x que verificam Ax = 0. rank(A) é o número de linhas/colunas linearmente independentes. Temos que rank(null(A)) + rank(A) = m. Exemplo:

rank(H) = 2; null(H) = 000,111, rank(null(H)) = 1; rank(H) + rank(null(H)) = 2 + 1 = 3.

O Código de Hamming Um código de Hamming (c,d) é formado da seguinte maneira: Constroi-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

, espaço nulo de H é composto pelos vetores [000] e [111]

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 r pertence ao espaço nulo!

Se Hr = 0, então r pertence ao espaço nulo → OK!

Se Hr 6= 0, então r não pertence a null(H) → ERRO!

Exemplo:

Se c = 000 e r = 000, Hr = [00]′ → sem erros

Se c = 000 e r = 001, Hr = [11]′ → erros detectados

Se c = 000 e r = 101, Hr = [10]′ → erros detectados

Se c = 000 e r = 111, Hr = [00]′ → sem erros

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

Detecta-se um erro quando Hr 6= 0. Como se pode saber qual o erro que ocorreu?

Suponhamos que ocorreu um erro na posição i. Usando um vector ei = [0 . . . 010 . . . 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, obtemos a posição i onde ocorreu o erro. Para o corrigir, basta invertê-lo.

Como escolher 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 vector 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:

Desempenho dos códigos de Hamming

Taxa de transmissão é: R =

Aumentando o tamanho das palavras de código, é possível fazer R → 1.

No entanto, a probabilidade de erro na decodificação também converge para 1: A probabilidade de a decodificação ser correta corresponde a haver até um erro numa palavra de comprimento c. Num canal binário simétrico com probabilidade de erro pe a probabilidade de decodificação correta de um código (c, d), é dada por:

(1 − pe)c + cpe(1 − pe)c−1, cujo limite é zero quando c → ∞.

Distância mínima de um código de Hamming: Pode ser determinado através da matriz H ou com uma analise das palavras código.

Calculando a distância minima através da matriz H: A distância mínima do código será determinada pelo numero mínimo de colunas da matriz H que devem ser somadas para se obter o vetor nulo. Exemplo:

A distancia mínima para o código cuja matriz H foi dada acima é 3, porque são necessaria a soma de no mínimo 3 colunas para obtermos o vetor nulo.

Calculando a distância minima através das palavras código: A distancia mínima do código será determinado pela mesma distância entre duas palavras código lembrando que o vetor nulo sempre corresponde a uma palavra código.

Se calcularmos as distâncias entre todas as palavras código o menor valor obtido corresponde a distância mínima para o código. Nesse exemplo igual a 3.

Capacidade de detecção: o número de erros que podem ser detectados utilizando um código de Hamming dependerá da distancia minima (dMIN) do código utilizado. e o número máximo de erros detectados será dado por:

Capacidade de correção: O número de erros que podem ser corrigidos utilizando um código de Hamming também dependerá da distancia minima (dMIN) do código utilizado. e o número máximo de erros corrigidos será dado por: