Redes - Aula 3

Prévia do material em texto

Prof. Claudio P. Fernandes
euclaudio@redes.ufsm.br
Fundamentos de Redes
Prof. Claudio P. Fernandes
euclaudio@redes.ufsm.br
Detecção e Controle de Erros
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Detecção de Erros 
 Em meios físicos de transmissão, erros de
transmissão podem ocorrer. As probabilidades de
erro são diferentes para cada meio.
 Erros são causados por atenuação de sinal e por
ruído.
O que ocorre quando o receptor 
detecta presença de erro 
?
Prof. Claudio P. Fernandes
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Detecção de Erros 
 O receptor sinaliza ao remetente para
retransmissão, ou simplesmente descarta o quadro
em erro.
 Métodos de detecção de erro:
 Bits de Paridade
Teste de redundância cíclica (Cyclic redundancy check,
CRC)
 Soma de verificação (Checksum)
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Paridade 
 Talvez a maneira mais simples de detectar erros
seja utilizar um único bit de paridade.
0 1 1 1 0 0 0 1 1 0 1 0 1 0 1 1 1
Bits de Dados Bit de 
Paridade
Paridade par com um bit de paridade
Prof. Claudio P. Fernandes
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Paridade 
 Em um esquema de paridade par, o remetente
simplesmente inclui um bit adicional e escolhe o
valor desse bit de modo que o número total de
“1” nos bits d + 1 (a informação original mais um bit
de paridade) seja par.
 Em esquemas de paridade ímpar, o valor do bit de
paridade é escolhido de modo que haja um
número ímpar de “1”.
Prof. Claudio P. Fernandes
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Paridade 
 Consiste basicamente no ato do transmissor
adicionar um bit de redundância após um
determinado número de bits (normalmente um
byte):
 nº par de 1’s  paridade par
 nº impar de 1’s paridade impar
 000, 011, 101, 110  são mensagens transmitidas
sem erro, tendo em conta que o último bit é o de
paridade
Prof. Claudio P. Fernandes
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Paridade 
Exemplo1:
 O caracter A no código ASCII é representado por
1000001
 O bit P de paridade é calculado e transmitido:
1000001Pnº par de 1’s / P =0 (paridade par),
logo transmite-se 10000010
 O receptor calcula a paridade da mensagem e
compara-a com o bit P recebido: P = paridade
transmissão correta.
Prof. Claudio P. Fernandes
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Paridade 
 A operação do receptor também é simples com
um único bit de paridade. O receptor precisa
apenas contar quantos “1” há nos d + 1 bits
recebidos.
 Se, utilizando um esquema de paridade par, for
encontrado um número ímpar de bits de valor 1, o
receptor saberá que ocorreu pelo menos um erro
de bit
Prof. Claudio P. Fernandes
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Exercicios Paridade 
 Verifique se ocorreu erro e, neste caso, se e possível
corrigir o erro. Se for possível corrigir o erro, faca a
correção.
Prof. Claudio P. Fernandes
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Paridade 
Mas o que acontecerá se ocorrer 
um número par de erros de 
bits?
Isso resultaria em um erro não detectado
Prof. Claudio P. Fernandes
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Paridade Bidirecional 
 Os d bits de D são divididos em i filas e j colunas. Um
valor de paridade é calculado para cada fila e para
cada coluna.
 Os i + j + 1 bits de paridade resultantes
compreendem os bits de detecção de erros do quadro
da camada de enlace.
Prof. Claudio P. Fernandes
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Paridade Bidirecional 
Paridade Par Bidimensional
Prof. Claudio P. Fernandes
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Exercicios Paridade Bidirecional 
Prof. Claudio P. Fernandes
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Exercicios Paridade Bidirecional 
Prof. Claudio P. Fernandes
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Exercicios Paridade Bidirecional 
Prof. Claudio P. Fernandes
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Exercícios Paridade Bidirecional
A sequência de bits a seguir foi recebida por um 
destinatário. Sabendo que o N-ésimo bit foi invertido no 
envio e que essa sequência possui bits de paridade 
bidimensional par,onde a quantidade de colunas é igual 
à de linhas, qual a linha e coluna desse bit?
100111001100101011111101010100101101 
Prof. Claudio P. Fernandes
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Exercícios Paridade Bidirecional
A seqüência de bits a seguir foi recebida por um
destinatário. Sabendo que vários bits foram invertidos no
envio e que essa seqüência inclui bits de paridade
bidimensional ímpar,onde a quantidade de colunas é
igual à de linhas, quais as linhas e colunas desses bits?
000111101101101010110101010100001101 
Prof. Claudio P. Fernandes
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Soma de Verificação CheckSum
 Consiste na transmissão de todas as palavras
juntamente com o resultado da sua soma
binária.
Inclui o bit de transporte.
Inversão do valor dos bits do checksum.
Prof. Claudio P. Fernandes
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Soma de Verificação CheckSum
Exemplo:
Checksum de 2 palavras de 8 bits
 Dados iniciais: 00111101 00001101
Checksum é:
01001010
Checksum invertido:
10110101.
Prof. Claudio P. Fernandes
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Soma de Verificação CheckSum
 Dados enviados:
 00111101
 00001101
10110101 (checksum –invertido)
 No receptor, as palavras são novamente somadas
e comparadas com o checksum enviado:
 Se qualquer um dos dados transmitidos, incluindo
o checksum, sofrerem algum erro então, a soma
do novo checksum com o checksum enviado, será
diferente de 1.
Prof. Claudio P. Fernandes
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Soma de Verificação CheckSum
0 1 0 0 1 0 1 0  novo checksum (das palavras
iniciais recebidas)
1 0 1 1 0 1 0 1 Checksum enviado
1 1 1 1 1 1 1 1  Sem erro
Prof. Claudio P. Fernandes
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Soma de Verificação CheckSum
Exemplo com erro:
0 0 1 1 0 0 0 1
0 0 0 0 1 1 0 1
0 0 1 1 0 1 1 0  Novo checksum
1 0 1 1 0 1 0 1  Checksum enviado
1 1 1 0 1 0 1 1 ≠ 1 1 1 1 1 1 1 1 
Prof. Claudio P. Fernandes
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Exercícios CheckSum
Calcule o “checksum” (8 bits) das mensagens abaixo:
0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 Forneça um exemplo onde dois bits são invertidos e,
mesmo assim, o “checksum” não é alterado
Prof. Claudio P. Fernandes
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Exercícios CheckSum
 Calcule o checksum para uma transmissão com os seguintes
bytes: 10100011, 11110000, 01011100,
10101010.
Prof. Claudio P. Fernandes
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Exercícios CheckSum
 Calcule o checksum para uma transmissão com os seguintes
bytes: 10100011,11110000, 01011100,
10101010.
1 0 1 0 0 0 1 1
1 1 1 1 0 0 0 0
1 0 0 1 0 0 1 1
0 1 0 1 1 1 0 0
1 1 1 0 1 1 1 1
1 0 1 0 1 0 1 0
1 0 0 1 1 0 0 1
CheckSum Inv
0 1 1 0 0 1 1 0
Prof. Claudio P. Fernandes
CheckSum 
1 0 0 1 1 0 0 1
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Exercícios CheckSum 3
 Calcule o checksum para uma transmissão com os seguintes
bytes:
11011010 10101111 01011110, 
10101010 11101110
Prof. Claudio P. Fernandes
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Resposta Exercícios CheckSum 3
 1 1 0 1 1 0 1 0
1 0 1 0 1 1 1 1
1 0 0 0 1 0 0 1
0 1 0 1 1 1 1 0
1 1 1 0 0 1 1 1
1 0 1 0 1 0 1 0
1 0 0 1 0 0 0 1
1 1 1 0 1 1 1 0
0 1 1 1 1 1 1 1 CheckSum
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Exercícios CheckSum 4
 Calcule o checksum para o receptor com os seguintes bytes
trocados e verifique se este detectou o erro
11011010 00101111 01011110, 
10101010 11101111
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Exercícios CheckSum Trocado 4
 1 1 0 1 1 0 1 0
0 0 1 0 1 1 1 1
0 0 0 0 1 0 0 1
0 1 0 1 1 1 1 0
0 1 1 0 0 1 1 1
1 0 1 0 1 0 1 0
0 0 0 1 0 0 0 1
1 1 1 0 1 1 1 1
0 0 0 0 0 0 0 0 CheckSum
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
CRC 
 Introdução
 Cálculo de CRC
 Exemplo:Antes do envio de dados
 Exemplo:Teste do receptor
 Considerações
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
INTRODUÇÃO 
 A verificação de redundância cíclica (CRC) é
uma técnica de detecção de erros muito usada
em redes de computadores.
 Os códigos de CRC são conhecidos como
códigos polinomiais.
B(x)= x
5 + x3 + x2 + x0 = (101101)2
 Uma mensagem deve ser enviada com o código
de CRC calculado para que possa ser verificada
no receptor.
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Cálculo de CRC 
 O cálculo de CRC é realizado através de uma
operação de divisão aplicada a números
binários.
 Há uma diferença na divisão: as operações de
subtração são substituídas por operações
lógicas de ou exclusivo (XOR – eXclusive OR).
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Cálculo de CRC 
 Um emissor deseja enviar D com d bits de dados.
 Um código de CRC R com r bits de comprimento dever
ser gerado e anexado aos dados antes do envio.
D: d bits de dados R: r bits de CRC
 O receptor e o emissor conhecem um padrão de bits
denominado G, de gerador.
 Esse gerador tem (r + 1) bits de comprimentos
 O bit mais significativo do gerador (mais à esquerda
dever ser 1).
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Cálculo de CRC 
 A base para o cálculo de R (código de CRC) é a formula:
R = resto ------------
 D * 2 é o deslocamento dos bits de dados a esquerda r
casas.
◦ Isto é a adição de r bits 0 no final dos bits de dados. Por
exemplo:
D*2
r
G
D= (100101) e r=3 D * 2 (100101000)
2
r
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Exemplo: Antes do envio de dados
 O emissor deseja enviar os bits de dados 111100101
 O gerador são os bits 101101.
 Como calcular o CRC antes de enviar os dados???
2
Emissor Receptor
CRC???
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Exemplo: Antes do envio de dados
11110010100000
Dados = (111100101)
Gerador = (101101 ou
G(x) = x5+x3+x2+x0
101101
1101101
XOR
010001 1
1
101101
XOR
001110 0
0
1
1
101101XOR
010100 0
1
101101XOR
000101 0
0
0
0
0
1
101101XOR
000101 0
0
Bits que são 
adicionados aos dados 
antes do envio
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Exemplo: Envio dos dados
 Após calcular o CRC cujos bits são 01010, o emissor
envia os bits de dados mais os bits de CRC.
 O receptor utiliza os bits enviados e divide pelo gerador
para verificar se os bits estão corretos.
2
Emissor Receptor
1 1 1 10010101010
1 1 1 10010101010
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Exemplo: Teste no Receptor
11110010101010
Dados = (111100101)
Gerador = (101101 ou
G(x) = x5+x3+x2+x0
101101
1101101
XOR
010001 1
1
101101
XOR
001110 0
0
1
1
101101XOR
010100 0
1
101101XOR
000101 1
0
0
0
1
1
101101XOR
000000 0
0
Resto zero: Os dados 
recebidos estão corretos
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Considerações
 Existem alguns polinômios geradores padronizados
para serem usados no cálculo de CRC
32 Bits
CRC32(x) x
32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8
+ x7 + x5 + x4 + x2 + x1 + x0
100000100110000010001110110110111
16 Bits
CRC16(x) x
16 + x15 + x2 + x0 
11000000000000101
2
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Considerações
12 Bits
CRC12(x) = x
12 + x3 + x1 + x0
1000000001011
8 Bits
CRC8(x) = x
8 + x2 + x1 + x0
100000111 
2
F
U
N
D
A
M
E
N
T
O
S 
D
E
 R
E
D
E
S
Prof. Claudio P. Fernandes
Exercícios
 Calcule o CRC para a sequência de bits
“1 0 0 1 1 1 1 0 1 1 1 0 0 1” e
para os seguintes polinômios geradores:
A) G(x)= X
5+X2+x0
B) G(x) = X
6 + X4 + X1 + X0
2