Deteccao de Erros

Prévia do material em texto

Detecção de Erros 1
Detecção de Erros
• Todos os métodos para detecção de erros são baseados
na inserção de bits extras na informação transmitida
– O transmissor, através de algum algoritmo (que tem como
entrada os bits originais a serem transmitidos),computa
os bits extras (redundantes).
• Os bits redundantes são acrescentados nas informações
originais.
– O receptor (conhecendo o algoritmo utilizado pelo
transmissor) ao obter o quadro:
• recalcula os bits de redundância
• compara-os com os respectivos bits recebidos
• se eles forem distintos  foram alterados  existência de
erros.
• Três técnicas de detecção de erros:
– Verificação de paridade
– Soma de verificação (mais empregado na camada de
transporte)
– Redundância cíclica (empregada normalmente na camada de
enlace).
Detecção de Erros 2
Detecção de Erros
EDC = Bits de Detecção e Correção de Erros (redundância)
D = Dados protegidos pela verificação de erros, pode incluir os 
campos de cabeçalho 
• A detecção de erros não é 100% confiável!
• protocolos podem deixar passar alguns erros, mas é raro.
• Quanto maior o campo EDC melhor é a capacidade de detecção e 
correção de erros 
Datagrama
D EDC
D bits de dados
Enlace sujeito a erros
D‟ EDC‟
Todos 
os bits 
em D‟ 
estão 
OK?
Datagrama
V
F
Erro detectado
Detecção de Erros 3
Verificação de Paridade
• Maneira mais simples de detectar erros  usar um
único bit de paridade.
1
bit de
paridaded bits de dados
• Paridade Par  o valor do
bit de paridade é escolhido
de modo que haja um número
par de „1s‟ (d bits de
dados + bit de paridade).
• Paridade Ímpar  o valor do bit de paridade é
escolhido de modo que haja um número ímpar de „1s‟ (d
bits de dados + bit de paridade).
• Problema: O que acontecerá se ocorrer um número par
de erros de bits?
- Erro não Detectado!
- Se a probabilidade de erros de bits for pequena 
OK!
- Porém, medições demonstram o contrário.
- Necessidade de esquemas mais robustos como CRC.
Detecção de Erros 4
Verificação de Paridade
– Os d bits de D são 
divididos em i linhas e 
j colunas.
– Um valor de paridade é 
calculado para cada 
linha e para cada 
coluna.
• Se houver erro em um 
bit, o receptor pode 
detectar e corrigir 
aquele erro.
sem erros erro de
paridade
erro de 1 bit
corrigível
erro de
paridade
00
• Generalização Bidimensional do esquema de paridade 
de bit único.
Detecção de Erros 5
Soma de Verificação
• Os d bits de dados são tratados como uma seqüência de
números inteiros de k bits.
– Somar os inteiros de k bits e usar o total resultante
como bits de detecção de erros.
• A soma de verificação da Internet é baseada nessa abordagem.
• Soma de Verificação da Internet
– Determinar se os bits dentro do segmento foram alterados
(por exemplo, por ruído nos enlaces ou enquanto
armazenados em um roteador) durante o percurso da fonte
ao destino.
– Unidades de dados são tratadas como inteiros de 16 bits e
somadas.
– O complemento de 1 dessa soma forma a soma de verificação
da Internet e é adicionada ao cabeçalho do segmento.
Detecção de Erros 6
Soma de Verificação da Internet
• Processo:
– O remetente realiza o complemento de 1 da soma de
todas as palavras de 16 bits, levando em conta o
“vai um” em toda a soma.
– O resultado é adicionado no campo de soma de
verificação no segmento.
• Exemplo:
– suponha que tenhamos três palavras de 16 bits
0110011001100000
0101010101010101
1000111100001100
A soma das duas primeiras palavras de 16 bits é:
0110011001100000
0101010101010101
1011101110110101
11 1
Detecção de Erros 7
Soma de Verificação da Internet
Adicionando a terceira palavra à soma, temos:
1011101110110101
1000111100001100
0100101011000001
Como teve o “vai um” no bit mais significativo, então é 
feita a soma ao bit menos significativo: 
vai 1
1111111111
1
0100011011000001
0100101011000010
1 vai 1 do bit + 
significativo
O complemento de 1 é obtido pela conversão de todos os 
0‟s em 1‟s e de todos os 1‟s em 0‟s.
0100101011000010 1011010100111101
Soma de Verificação
Detecção de Erros 8
Soma de Verificação da Internet
• No destinatário:
– Todas as quatro palavras de 16 bits são somadas,
inclusive a Soma de Verificação.
Se um dos bits for 0 significa que houve erro.
0110011001100000
0101010101010101
1000111100001100
1011010100111101
– A soma de verificação do destinatário deve dar:
1111111111111111
Detecção de Erros 9
Verificação de Redundância Cíclica (CRC)
• CRC = Cyclic Redundancy Check.
• Técnica largamente utilizada na prática.
• Considera os bits de dados, D, como um polinômio. Por
isso, códigos de CRC são conhecidos como Códigos
Polinomiais.
• Funcionamento:
– Considere a parcela de d bits de dados, D, que o nó
remetente deseja enviar ao receptor
– Primeiro, o remetente e o receptor devem concordar com um
padrão de r+1 bits, conhecido como gerador, G.
D:bits de dados a enviar R: bits de CRC
d bits r bits
D * 2r XOR R Fórmula Matemática
Padrão de bit
Detecção de Erros 10
Verificação de Redundância Cíclica (CRC)
• Exigência: o bit mais significativo (da extrema
esquerda) de G deve ser 1.
• Para uma parcela de dados, D, o remetente escolherá r
bits adicionais, R, anexando-os a D.
– d + r bits resultantes devem ser divisíveis por G, usando
aritmética de módulo 2.
– A aritmética de módulo 2 (sem “vai um” nas adições e nem
“empresta um” nas subtrações) é equivalente à operação ou
exclusivo (XOR).
– o receptor divide os d + r bits recebidos. 
– Resto  0  Ocorreu um erro!
1011 XOR 0101 = 1110
1001 XOR 1101 = 0100
Detecção de Erros 11
Verificação de Redundância Cíclica
• Algoritmo para calcular a verificação:
– Defina r como grau de G(x). Acrescente r bits zero
à extremidade de baixa ordem do quadro, de modo que
ele passe a conter m+r bits e corresponda ao
polinômio xrM(x);
– Subtraia a seqüência de bits correspondente a
xrM(x) pelo G(x) utilizando a subtração de módulo
2. O resultado é o valor do resto que será
adicionado no pacote a ser transmitido.
Detecção de Erros 12
Verificação de Redundância Cíclica
• Quadro:
• Quadro após acréscimo 
de 4 zeros: 
• Quadro a ser 
transmitido:
10011
10011
10011
000010110
10011
010100
10011
01110
Resto
10011 11010110110000
Gerador(G): x4 + x1 + x0: 10011
1101011011
11010110110000
11010110111110
Detecção de Erros 13
Verificação de Redundância Cíclica
• Os seguintes polinômios tornaram-se padrões
internacionais:
– CRC-12 = x12 + x11 + x3 + x2 + x + 1
– CRC-16 = x16 + x15 + x2 + 1
– CRC-32 = x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 +
+ x8 + x7 + x5 + x4 + x2 + x + 1
• Os dois últimos detectam todos os erros simples e
duplos, todos os erros com um número ímpar de
bits, todos os erros em rajadas que tiverem um
tamanho de no máximo 16 bits, 99,997% das rajadas
de erros de 17 bits e 99,998 % das rajadas de 18
bits no mínimo.