Codificação de Hamming - Organização de Computadores

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Codificação de hamming
Distância de Hamming
Ao estudar os erros existentes na transmissão de sinais digitais, o pesquisador Richard W. Hamming introduziu o conceito de “distância” entre 2 valores binários (distância de Hamming).
Distância de Hamming: numero de bits em um dos valores binários que devem ser modificados para que ele se transforme no outro valor. 
Forma de avaliação: fazer um “ou exclusivo” bit a bit entre os dois valores, e somar os bits 1 obtidos.
Distância de Hamming
Exemplos:
1001 e 1010 : distância 2
0010 e 0011 : distância 1
10011010 e 10101011 : distância 3
1110 e 0001: distância 4
Quanto maior a distância entre 2 valores, menor a chance do primeiro valor se transformar no outro, por conta de erros de transmissão.
Códigos de Hamming
A codificação de Hamming introduz vários bits de paridade no código binário original.
Cada bit é responsável pela paridade de um grupo de bits dentro do código. 
O numero de bits de paridade será proporcional ao numero de bits do dado.
Para 4 bits usa-se 3 de paridade, de 5 a 11 usa-se 4, de 12 a 26 usa-se 5, etc...
Códigos de Hamming
Ideia básica: se for trabalhar com dados de n bits, e sendo acrescentados m bits de paridade:
Serão 2n+m valores possíveis.
Destes apenas 2n serão valores válidos.
A distância de Hamming entre 2 valores inválidos será sempre maior que 1.
A codificação de Hamming permite não só detectar a existência de erro, mas também identificar onde está o erro (e portanto corrigir).
Códigos de Hamming
Para detectar e erros, distância de Hamming entre dois valores deve ser de e + 1.
Para se corrigir e erros, a distância de Hamming deverá ser 2e + 1
Exemplo gráfico
Valor a ser guardado/transmitido: 1101.
1
Exemplo gráfico
Valor a ser guardado/transmitido: 1101.
1
1
Exemplo gráfico
Valor a ser guardado/transmitido: 1101.
1
1
0
Exemplo gráfico
Valor a ser guardado/transmitido: 1101.
1
1
0
1
Exemplo gráfico
Valor a ser guardado/transmitido: 1101.
Supondo paridade par.
1
1
0
1
0
1\
0
Exemplo gráfico
Supondo que um dos bits seja trocado
Paridade de A: ok; de B e C incorretas.
1
0
0
1
0
1\
0
Erro está na interseção do círculo B com o círculo C.
Obtenção dos códigos Hamming
Numera-se os bits da esquerda para a direita, começando com 1.
Nessa contagem, os bits que coincidirem em posição com uma potência de 2 serão bits de paridade.
Para 8 bits, os bits de paridade estarão nas posições 1, 2, 4 e 8. 12 bits totais.
Para 16 bits, paridade nas posições 1,2,4, 8 e 16. 21 bits no total.
Cada bit de paridade é responsável por um conjunto específico de bits.
Obtenção dos códigos Hamming: tabela auxiliar
Pode ser feita a tabela a seguir para se saber os bits de dados que cada bit de paridade verifica. 
Nas linhas tem-se a relação de bits de 1 ao máx, e nas colunas os múltiplos de 2.
Marca-se as células cuja soma dos múltiplos de 2 corresponde ao valor da linha.
Cada coluna irá mostrar quais bits cada bit de paridade verifica. 
1
2
4
8
16
3
x
x
5
x
x
6
x
x
7
x
x
x
9
x
x
10
x
x
11
x
x
x
12
x
x
13
x
x
x
14
x
x
x
15
x
x
x
x
17
x
x
Exemplo de cálculo
Valor de exemplo (8 bits): 11010001
Paridade: ímpar.
Serão acrescentados 4 bits de paridade, nas posições 1, 2, 4 e 8.
1
2
3
4
5
6
7
8
9
10
11
12
1
1
0
1
0
0
0
1
Exemplo de cálculo
Valor de exemplo (8 bits): 11010001
Paridade: ímpar.
1
1
0
1
0
0
0
1
1
2
3
4
5
6
7
8
9
10
11
12
Bit 1 verifica bits 3, 5, 7, 9, 11
Valor do bit 1: 0 
0
Exemplo de cálculo
Valor de exemplo (8 bits): 11010001
Paridade: ímpar.
0
1
1
0
1
0
0
0
1
1
2
3
4
5
6
7
8
9
10
11
12
Bit 2 verifica bits 3, 6, 7, 10, 11
Valor do bit 2: 1 
1
Exemplo de cálculo
Valor de exemplo (8 bits): 11010001
Paridade: ímpar.
0
1
1
1
0
1
0
0
0
1
1
2
3
4
5
6
7
8
9
10
11
12
Bit 4 verifica bits 5, 6, 7, 12
Valor do bit 4: 0 
0
Exemplo de cálculo
Valor de exemplo (8 bits): 11010001
Paridade: ímpar.
0
1
1
0
1
0
1
0
0
0
1
1
2
3
4
5
6
7
8
9
10
11
12
Bit 8 verifica bits 9 e acima
Valor do bit 8: 0 
Portanto: 11010001 ⇨ 011010100001
0
Exercício
Dados os valores a seguir em 8 bits
10110101 e 10100101.
Obter a distância de Hamming entre esses valores.
Obter a palavra de código, considerando a paridade par, para o primeiro valor: 10110101.
Exercício
Dados os valores a seguir em 8 bits
10110101 e 10100101.
Obter a distância de Hamming entre esses valores.
Obter a palavra de código, considerando a paridade par, para o primeiro valor: 10110101.
Soluções:
 Distância de Hamming = 1
Palavra em Hamming = 001101100101
Cálculo do Exercício
Valor de exercício (8 bits): 10110101
Paridade: par.
1
0
1
1
0
1
0
1
1
2
3
4
5
6
7
8
9
10
11
12
Bit 1 verifica bits 3, 5, 7, 9, 11
Valor do bit 1: 0 
0
Cálculo do Exercício
Valor de exercício (8 bits): 10110101
Paridade: par.
0
0
1
0
1
1
0
1
0
1
1
2
3
4
5
6
7
8
9
10
11
12
Bit 2 verifica bits 3, 6, 7, 10, 11
Valor do bit 2: 0 
Cálculo do Exercício
Valor de exercício (8 bits): 10110101
Paridade: par.
0
0
1
0
1
1
0
1
0
1
1
2
3
4
5
6
7
8
9
10
11
12
Bit 4 verifica bits 5, 6, 7, 12
Valor do bit 4: 1 
1
Cálculo do Exercício
Valor de exercício (8 bits): 10110101
Paridade: par.
0
0
1
1
0
1
1
0
1
0
1
1
2
3
4
5
6
7
8
9
10
11
12
Bit 8 verifica bits 9 e acima
Valor do bit 8: 0 
Portanto: 10110101 ⇨ 001101100101
0
Verificação de erros
Faz-se o cálculo das paridades novamente. 
O bit com erro será o bit em comum dos bits de paridade que estiverem com erro.
Exemplo:
Supondo paridade ímpar e código recebido foi 001011110100.
Calculando paridades:
Verificação de erros
Faz-se o cálculo das paridades novamente. 
O bit com erro será o bit em comum dos bits de paridade que estiverem com erro.
Exemplo:
Supondo paridade ímpar e código recebido foi 001011110100.
Calculando paridades: 
bit 1 ok
Verificação de erros
Faz-se o cálculo das paridades novamente. 
O bit com erro será o bit em comum dos bits de paridade que estiverem com erro.
Exemplo:
Supondo paridade ímpar e código recebido foi 001011110100.
Calculando paridades: 
bit 1 ok, bit 2 com erro
Verificação de erros
Faz-se o cálculo das paridades novamente. 
O bit com erro será o bit em comum dos bits de paridade que estiverem com erro.
Exemplo:
Supondo paridade ímpar e código recebido foi 001011110100.
Calculando paridades: 
bit 1 ok, bit 2 com erro, bit 4 ok
Verificação de erros
Faz-se o cálculo das paridades novamente. 
O bit com erro será o bit em comum dos bits de paridade que estiverem com erro.
Exemplo:
Supondo paridade ímpar e código recebido foi 001011110100.
Calculando paridades: 
bit 1 ok, bit 2 com erro, bit 4 ok, bit 8 com erro.
O bit em comum das paridades com erro é o bit 10 (2 + 8).
invertendo esse bit, o código correto é: 001011110000.
Exemplo de Verificação de Erro
Valor transmitido:
0
1
1
0
1
0
1
0
0
0
0
1
1
2
3
4
5
6
7
8
9
10
11
12
Valor recebido:
0
1
1
0
1
0
0
0
0
0
0
1
1
2
3
4
5
6
7
8
9
10
11
12
Exemplo de Verificação de Erro
Valor recebido:
0
1
1
0
1
0
0
0
0
0
0
1
1
2
3
4
5
6
7
8
9
10
11
12
Bit de paridade 1: paridade par. 
Bit de paridade 2: paridade par. 
Bit de paridade 4: paridade par. 
Bit de paridade 8: paridade ímpar. 
1
2
4
8
16
3
x
x
5
x
x
6
x
x
7
x
x
x
9
x
x
10
x
x
11
x
x
x
12
x
x
13
x
x
x
14
x
x
x
15
x
x
x
x
17
x
x
Exemplo de Verificação de Erro
Valor recebido:
0
1
1
0
1
0
0
0
0
0
0
1
1
2
3
4
5
6
7
8
9
10
11
12
Os bits de paridade 1, 2 e 4 acusaram problemas: encontraram paridade par em seus grupos, sendo que a combinada antes do envio era impar. 
Some as posições dos bits de paridade com problema: 1 + 2 + 4 = 7. 
Portanto, o erro está no bit
7.
1
2
4
8
16
3
x
x
5
x
x
6
x
x
7
x
x
x
9
x
x
10
x
x
11
x
x
x
12
x
x
13
x
x
x
14
x
x
x
15
x
x
x
x
17
x
x