Códigos Corretores de Erros

Prévia do material em texto

Códigos Corretores de Erros
TT 108 - 1º 2013
26, setembro, 2011 Concurso FT Limeira
1
ISBN – International Standard Book Number
• 0 - 20 -136186- 8 
• País – Editora - Livro – Verificação
•Verificação: a segunda soma deve ser múltiplo de 11
222
000
somasomadígito
2
86276
59218
38131
25126
1363
731
420
222
Canal que introduz erros 
Sequência na entrada: 0 0 1 0 1 1 0 0 1 0
Sequência na saída: 0 0 0 0 1 1 1 0 1 0
O canal troca zero por um (ou um por zero) em média 
pppp % das vezes 
3
Se observamos zero (ou um) na saída do canal, qual será 
a nossa decisão ?
Verificação de paridade 
Sequências de tamanho 4
na entrada do canal: 
1110
0110
1010
0010
1100
0100
1000
0000
I1 I2 I3 I4 I1 I2 I3 I4 I1 I2 I3 I4 I1 I2 I3 I4 
41111
0111
1011
0011
1101
0101
1001
0001
1110
00110
01010
10010
01100
10100
11000
00000
Verificação de paridade 
Sequências de tamanho 5
na entrada do canal: 
I1 I2 I3 I4 P1I1 I2 I3 I4 P1I1 I2 I3 I4 P1I1 I2 I3 I4 P1
01111
10111
11011
00011
11101
00101
01001
10001
11110
5
Canal que introduz erros 
Sequência na entrada: 0 0 0 0 0
Sequência na saída: 0 0 0 0 1 
O que podemos concluir ?
Sequência na entrada: 0 0 0 0 0
6
Sequência na entrada: 0 0 0 0 0
Sequência na saída: 0 0 0 1 1
O que podemos concluir ? 
Verificação de paridade em duas dimensões
000
000
000
110
110
000
011
011
000
243
121
PII
PII
7
Código: 16 matrizes distintas (16 sequências distintas) 
Podemos corrigir um único erro introduzido pelo canal em 
qualquer um dos 09 bits ?
345
243
PPP
PII
Eficiência do código 
Usamos sequências de comprimento 09 para enviar 04 bits 
de informação. Ou seja, foram introduzidos 05 bits de 
paridade. 
O código mostrado tem capacidade de corrigir 01 erro em 
qualquer posição da sequência.
8
Podemos construir um código com sequências de comprimento 
menor e que corriga 01 erro ? Ou seja, introduzindo menos 
bits de paridade ?
Se existir, este seria um código mais “eficiente”.
Código de comprimento 07 
P1
P2
I1
I3
I2
I4
9
P3
I3
1
1
0
0
1
0
0
Código de tamanho 07 I1 I2 I3 I4 P1 P2 P3
0110
1010
0010
1100
1100100
1111000
0000000
10
1111
0111
1011
0011
1101
0101
1001
0001
1110
Código de comprimento 07 
R5
R6
R1
R3R2
R4
11
R7
R3
1
0
0
0
1
0
0
Código de comprimento 07 
R5
R6
R1
R3R2
R4
12
R7
R3
1
0
0
0
1
0
0
Código de comprimento 07 
R5
R6
R1
R3R2
R4
13
R7
R3
1
1
0
1
1
0
0
Código de comprimento 07 
R5
R6
R1
R3R2
R4
14
R7
R3
1
1
0
0
1
1
0
Simulação do código de Hamming 
Gerar sequência de 04 bits: I1 I2 I3 I4.
Gerar 03 bits de paridade: P1 P2 P3.
Enviar sequência de 07 bits pelo canal que introduz apenas 
um erro.
15
Corrigir o erro na sequência recebida: 
R1 R2 R3 R4 R5 R6 R7.
Recuperar os 04 bits de informação. 
http://www.ecs.umass.edu/ece/koren/FaultTolerantSystems/simulator/Hamming/HammingCodes.html
Correção de Erros num CD 
Até aproximadamente 4000 bits consecutivos numa mesma 
trilha ou aproximadamente 2,5 mm.
Se não forem consecutivos: aproximadamente 7,7 mm.
Vamos testar ? 
16
Gravem num CD-R (é mais barato!) uma música e tragam 
para a FT. No laboratório fazemos um furo de até 2,5 mm.
E em casa vocês voltam a tocar a música.
Canal Multiplicativo: dois usuários
1X
2X
X1=0, Y1=Y2=0 independente de X2
X2=0, Y1=Y2=0 independente de X1
X1=1 e X2=1, Y1=Y2=1 
17
X
1Y 2Y
2121 XXYY == { }1,0∈iX
Código para o canal multiplicativo
00011001
00100110
01010100
2121 YXXmm
rrr
Transmissão sem erros !!!
18
11111
00011001
Informação na Wikipédia
Códigos de Hamming
http://pt.wikipedia.org/wiki/C%C3%B3digo_de_Hamming
Claude Shannon: pai da Teoria da Informação e Codificação
19
http://pt.wikipedia.org/wiki/Claude_Shannon