Error Correction

Códigos de
detecção e correção
de erro
Raul Queiroz Feitosa
Conteúdo







Motivação
Idéia Básica
Definições
Deteção de Erro
Correção de Erros
Código de Hamming
Exercícios
23/08/2013
Códigos
2
1
Motivação

Erros ocorrem:
0’s se transformam em 1’s devido a causas
espúrias em dispositivos de memória, em
sistemas de comunicação, etc.

Objetivo:
Procurar mecanismos que sejam capazes de
detectar ou, melhor ainda, corrigir este erros.
23/08/2013
Códigos
3
Idéia Básica


Para representar 2m palavras utilizam-se
n=r+m bits (r bits além do necessário!)
Entre as
 2m+r
palavras possíveis
são válidas e
m
r
 2 (2 -1) são inválidas.
 2m palavras


O sistema só gera palavras válidas.
Logo, se surgir alguma palavra inválida,
trata-se de um erro!
23/08/2013
Códigos
4
2
Definições

Código
é o conjunto de palavras válidas.

Erro simples
é a alteração de uma palavra válida numa
única posição (bit).
5
Códigos
23/08/2013
Definições

Distância de Hamming entre palavras
é o número de posições (bits) em que as
palavras diferem.
Exemplo:
p1 = 1 0 0 0 1 0 0 1
p2 = 1 0 1 1 0 0 0 1
h(p1,p2)=3
xor(p1,p2) = 0 0 1 1 1 0 0 0
23/08/2013
Códigos
6
3
Definições

Distância de Hamming de um código
é a menor distância de Hamming entre 2
palavras do código.
Exemplo:
H=2
4
10110001
3
2
10111110
7
00000001
4
5
11110011
23/08/2013
Códigos
7
Detecção de erro

Para que uma palavra (válida) de um código
com
H=d
se transforme numa outra palavra (válida) do
mesmo código, deverão ocorrer pelo menos d
erros simples.

Logo, um código capaz de detectar d erros
simples deve ter
H ≥ d+1
23/08/2013
Códigos
8
4
Detecção de erro

Exemplo: bit de paridade
0000
0011
0101
0110
1001
1010
1100
1111
23/08/2013
H=1
2
Códigos
9
Correção de erro

Idéia básica:
Qualquer palavra inválida é substituída pela
válida mais próxima (em termos de distância
de Hamming)
logo, um código será capaz de corrigir até c
erros simples, se e somente se
H ≥ 2c+1
23/08/2013
Códigos
10
5
Correção de erro

Problema:
Suponha que se deseja construir um código
contendo 2m palavras válidas, capaz de
corrigir até 1 erro simples.
Quantos bits extra serão necessários (r=?)
23/08/2013
Códigos
11
Correção de erro

Solução:
2m+r
→ total
m
2
→ válidas
(m+r)2m → inválidas a uma distância 1 de uma válida
Portanto,
m+r+1 ≤ 2r
23/08/2013
Códigos
12
6
Correção de erro

Pela relação anterior
m
r
m+r
overhead (%)
8
4
12
50
16
5
21
31
32
6
38
19
64
7
71
11
128
8
136
6
256
9
265
4
512
10
522
2
23/08/2013
Códigos
13
Código de Hamming

Construindo um código de correção de
1 erro simples para 2m palavras
 Acrescentam-se
r bits de paridade (vide slide
anterior): total de m+r bits por palavra
 Bits são numerados de 1 a m+r
 Posições potência inteira de 2 têm os bits de
paridade, cf. próximo slide
23/08/2013
Códigos
14
7
Código de Hamming

Construindo um código de correção de
1 erro simples para 2m palavras
10100111
1 1 1 1 0 1 0 0 0 1 1 1
1
2
3
4
5
6
7
9
10
11
12
Bit 1 → 1 , 3 , 5 , 7 , 9 , 11
Bit 2 → 2 , 3 , 6 , 7 , 10 ,11
Bit 4 → 4 , 5 , 6 , 7 , 12
Bit 8 → 8 , 9 , 10 ,11 ,12
Geralmente um bit b é verificado por
todos os bits de paridade em que
b = b1 + b2 + ... + bj
23/08/2013
8
Códigos
15
Exercícios
1.
Deseja-se construir um código composto de 3
palavras código de 8 bits cada uma. As
palavras código devem ser escolhidas de
modo a maximizar o número de erros simples
que se poderá detectar. Pergunta-se quantos
erros simples se poderá corrigir com tal
código?
23/08/2013
Códigos
16
8
Exercícios
2.
Derive uma relação que forneça um limite
inferior para o número de bits de verificação
(r) necessários para se montar um código de
correção de até 2 erros simples para 2m
palavras válidas distintas.
Códigos
23/08/2013
17
Exercícios
3.
Seja o código formado pelas palavras código
abaixo:
10100110 - 11111111 - 01011001 - 10000101
Qual é a distância de Hamming do Código?
Qual é o número máximo de erros simples que
se pode detectar neste código? Qual é o
número máximo de erros simples que se pode
corrigir neste código?
23/08/2013
Códigos
18
9
Exercícios
4.
5.
Qual é o código completo contendo 12 bits
produzido pelo código de Hamming derivado
palavra de 8 bits abaixo?
10100101
Altere aleatoriamente um dos bits do resultado
à questão anterior e verifique se você
consegue identificar o bit alterado, e portanto,
corrigi-lo.
23/08/2013
Códigos
19
FIM
23/08/2013
Códigos
20
10