CÓDIGOS DEHAMMING

UFSM-CTISM

Comunicação de DadosAula-17

CÓDIGOS DE HAMMING

Professor:Andrei Piccinini Legg

Santa Maria, 2012

CÓDIGOS DEHAMMING

CÓDIGOS DE HAMMING

Definição:

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

c – no bits transmitidos

d – no bits de dados

p – no bits de paridade

palavra código

dados paridade

A implementação do codificador e do decodificador é muitosimples, como se vai ver em seguida.

CÓDIGOS DEHAMMING

Ideia

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

PSfr

000 010

110100

001011

111101

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 decódigo inválida e pode recuperar o original escolhendo apalavra de código válida mais próxima.

CÓDIGOS DEHAMMING

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 vector de dimensão m.null(A), o espaço nulo de A, é o espaço gerado pelosvectores x que verificam Ax = 0.rank(A) é o no de linhas/colunas linearmenteindependentes. Temos que rank(null(A)) + rank(A) = m.

Exemplo:

H =

[

0 1 11 0 1

]

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

CÓDIGOS DEHAMMING

Código de Hamming

Um código de Hamming (c,d ) é formado da seguintemaneira:Constroi-se uma matriz H cujas colunas são formadas portodos os vetores não nulos de dimensão p = c − d .O código de Hamming consiste no espaço nulo da matrizH, 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 11 0 1

]

O espaço nulo de H é composto pelos vetores [000] e [111](Verifique!)

CÓDIGOS DEHAMMING

Detecção de erros

Como as palavras de código pertencem ao espaço nulo deH, é muito simples verificar se houve erro de transmissão:Basta verificar se a palavra recebida r pertence ao espaçonulo!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 errosSe c = 000 e r = 001, Hr = [11]′ → erros detectadosSe c = 000 e r = 101, Hr = [10]′ → erros detectadosSe c = 000 e r = 111, Hr = [00]′ → sem errosNote que se existirem 3 erros é recebida uma palavra válidae não são detectados erros (não há milagres!)

CÓDIGOS DEHAMMING

Correção de erros

Detecta-se um erro quando Hr 6= 0. Como se pode saberqual o erro que ocorreu?Suponhamos que ocorreu um erro na posição i.Usando um vector ei = [0 . . . 010 . . .0] para representar aposiçã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 aposição i onde ocorreu o erro. Para o corrigir, bastainvertê-lo.

CÓDIGOS DEHAMMING

Como escolher o número de bits de paridade?

O número de colunas de H é igual a 2p − 1, que deve sercompatível com a dimensão do vector r . Entãod + p = 2p − 1

Regra de Hamming

d + p + 1 ≤ 2p

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

Exemplos:

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

CÓDIGOS DEHAMMING

Exemplo: Código de Hamming (7,4)

Palavras de código:0000 000 0100 101 1000 011 1100 1100001 111 0101 010 1001 100 1101 0010010 110 0110 011 1010 101 1110 0000011 001 0111 100 1011 010 1111 111

Codificação:

Pesquisar na tabela a palavra de código cujos 4 primeirosbits são os dos dados que se pretendem codificar.Adicionar a paridade correspondente.

Fonte Cod. Canal Decod.1011 1011010 1010010 1011

Hr = [100]′

CÓDIGOS DEHAMMING

Exemplo: Código de Hamming (7,4)

Palavras de código:0000 000 0100 101 1000 011 1100 1100001 111 0101 010 1001 100 1101 0010010 110 0110 011 1010 101 1110 0000011 001 0111 100 1011 010 1111 111

Codificação:

Pesquisar na tabela a palavra de código cujos 4 primeirosbits são os dos dados que se pretendem codificar.Adicionar a paridade correspondente.

H =

0 0 0 1 1 1 10 1 1 0 0 1 11 0 1 0 1 0 1

CÓDIGOS DEHAMMING

Desempenho dos códigos de Hamming

O Taxa de transmissão é: R =dc=

2p − p − 12p − 1

Aumentando o tamanho das palavras de código, é possívelfazer R → 1.No entanto, a probabilidade de erro na decodificaçãotambém converge para 1:A probabilidade de a decodificação ser correta corresponde ahaver até um erro numa palavra de comprimento c. Num canalbinário simétrico com probabilidade de erro pe a probabilidade dedecodificação correta de um código (c, d), é dada por:

(1 − pe)c + cpe(1 − pe)

c−1

cujo limite é zero quando c → ∞.

CÓDIGOS DEHAMMING

Desempenho dos códigos de Hamming

Distância minima de uma código de Hamming

pode ser determinado através da matriz H ou com umaanalise das palavras código.

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

H =

0 0 0 1 1 1 10 1 1 0 0 1 11 0 1 0 1 0 1

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 paraobtermos o vetor nulo.

CÓDIGOS DEHAMMING

Desempenho dos códigos de Hamming

Distância minima de uma código de Hamming

pode ser determinado através da matriz H ou com umaanalise das palavras código.

Calculando a distância minima através das palavras código:

A distancia mínima do código será determinada pela menosdistancia entre duas palavras código lembrando que o vetor nulosempre corresponde a uma palavra código.

Exemplo:

0000000 0100101 1000011 11001100001111 0101010 1001100 11010010010110 0110011 1010101 11100000011001 0111100 1011010 1111111

Se calcularmos as distâncias entre todas as palavras código omenor valor obtido corresponde a distância minima para ocódigo. Nesse exemplo igual a 3.

CÓDIGOS DEHAMMING

Desempenho dos códigos de Hamming

capacidade de detecção

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

dMIN = ed + 1 ⇒ ed = dMIN − 1

capacidade de correção

o número de erros que podem ser corrigidos utilizando umcódigo de Hamming também dependerá da distanciaminima (dMIN) do código utilizado. e o número máximo deerros corrigidos será dado por:

dMIN = 2ec + 1 ⇒ ec =dMIN − 1

2