Redes de Computadores I

Aula: 23/04/2012
Professor: Daniel Biasoli
Detecção de Erros

Redes de Computadores (AULA 06) 2

Quando é mais eficiente detectar erros e
retransmitir dados, para lidar com erros
ocasionais?

Redes de Computadores (AULA 06) 3

 Códigos de Detecção de Erros

• Em fios de cobre ou fibra óptica a taxa de

erros é menor em relação a enlaces sem fios.

Redes de Computadores (AULA 06) 4

 Detecção de Erros
• A detecção de erros não é 100% perfeita
• Protocolo pode não identificar alguns erros,
mas é raro
• Maior campo de bits de detecção e correção
de erros permite melhorar detecção e
correção

Redes de Computadores (AULA 06) 5

 Códigos de Detecção de Erros
– CRC ou código de Redundância Cíclica (ou ainda,
código polinomial)
– Cyclic Redundancy Check - CRC

Redes de Computadores (AULA 06) 6

CRC ou Código de Redundância Cíclica
(Cyclic Redundancy Check)

• Cálculo de CRC
• Exemplo – Antes do Envio de Dados
• Exemplo – Envio de dados
• Exemplo – Teste no Receptor
• Considerações

Redes de Computadores (AULA 06) 7

CRC ou Código de Redundância Cíclica
• A verificação de redundância cíclica (Cyclic
Redundancy Check – 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

Redes de Computadores (AULA 06) 8

B(x) =  +  +  +  = (   )

Redes de Computadores (AULA 06) 9

CRC ou Código de Redundância Cíclica
• Uma mensagem deve ser enviada com o
código de CRC calculado para que possa ser
verificada no receptor.
• 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óticas de ou exclusivo (XOR – eXclusive OR).

Redes de Computadores (AULA 06) 10

CRC ou Código de Redundância Cíclica
• Relembrando a tabela da operação XOR:
A B A XOR B
0 0 0
0 1 1
1 0 1
1 1 0

Redes de Computadores (AULA 06) 11

CRC ou Código de Redundância Cíclica
• Cálculo de CRC – Premissas:
– Um emissor deseja enviar D com d bits de dados.
– Um código de CRC R com r bits de comprimento
deve ser gerado e anexado aos dados antes do
envio.
• D: d bits de dados
• R: r bits de CRC

Redes de Computadores (AULA 06) 12

CRC ou Código de Redundância Cíclica
• O receptor e o emissor conhecem um padrão
de bits denominado G, de gerador.
• Este gerador tem (r + 1) bits de comprimento.
• O bit mais significativo do gerador (mais à
esquerda) deve ser 1.

Redes de Computadores (AULA 06) 13

CRC ou Código de Redundância Cíclica
• A base para o cálculo de R (código de CRC) é a
fórmula):

∗
– R = 

–  ∗  é o deslocamento dos bits de dados à
esquerda r casas.
– G é o gerador
– Isso é a adição de r bits 0 no final dos bits de dados.
– Por exemplo:
D = (   ) e r = 3
D* (100101000)

Redes de Computadores (AULA 06) 14

CRC ou Código de Redundância Cíclica
Exemplo antes do envio de dados:

−      !"  :

111100101.
− $ % ã  !" 101101.

COMO CALCULAR O CRC ANTES DE ENVIAR OS

DADOS?

Redes de Computadores (AULA 06) 15

CRC ou Código de Redundância Cíclica

Emissor Receptor

111100101
CRC?????

Redes de Computadores (AULA 06) 16

Exemplo – Antes do Envio de Dados

Redes de Computadores (AULA 06) 17

 Exemplo – Antes do Envio de Dados
11110010100000

Grau do Gerador = 5

Redes de Computadores (AULA 06) 18

 Exemplo – Antes do Envio de Dados
11110010100000 101101

Grau do Gerador = 5

Redes de Computadores (AULA 06) 19

 Exemplo – Antes do Envio de Dados
11110010100000 101101

Redes de Computadores (AULA 06) 20

 Exemplo – Antes do Envio de Dados
Gerador
11110010100000 101101

Redes de Computadores (AULA 06) 21

 Exemplo – Antes do Envio de Dados
11110010100000 101101

Redes de Computadores (AULA 06) 22

 Exemplo – Antes do Envio de Dados
11110010100000 101101
1

Redes de Computadores (AULA 06) 23

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 xor 1

Redes de Computadores (AULA 06) 24

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 1

Redes de Computadores (AULA 06) 25

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 1
010001

Redes de Computadores (AULA 06) 26

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 1
010001

Redes de Computadores (AULA 06) 27

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 1
0100011

Redes de Computadores (AULA 06) 28

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 11
0100011

Redes de Computadores (AULA 06) 29

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 11
0100011
101101

Redes de Computadores (AULA 06) 30

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 11
0100011 xor
101101

Redes de Computadores (AULA 06) 31

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 11
0100011 xor
101101

Redes de Computadores (AULA 06) 32

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 11
0100011 xor
101101
001110

Redes de Computadores (AULA 06) 33

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 11
0100011
101101
0011100

Redes de Computadores (AULA 06) 34

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 110
0100011
101101
0011100

Redes de Computadores (AULA 06) 35

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 110
0100011
101101
00111001

Redes de Computadores (AULA 06) 36

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 1101
0100011
101101
00111001

Redes de Computadores (AULA 06) 37

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 1101
0100011
101101
00111001
101101

Redes de Computadores (AULA 06) 38

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 1101
0100011
101101
00111001 xor
101101

Redes de Computadores (AULA 06) 39

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 1101
0100011
101101
00111001 xor
101101

Redes de Computadores (AULA 06) 40

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 1101
0100011
101101
00111001 xor
101101
010100

Redes de Computadores (AULA 06) 41

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 1101
0100011
101101
00111001
101101
010100

Redes de Computadores (AULA 06) 42

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 1101
0100011
101101
00111001
101101
0101000

Redes de Computadores (AULA 06) 43

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 11011
0100011
101101
00111001
101101
0101000

Redes de Computadores (AULA 06) 44

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 11011
0100011
101101
00111001
101101
0101000
101101

Redes de Computadores (AULA 06) 45

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 11011
0100011
101101
00111001
101101
0101000 xor
101101

Redes de Computadores (AULA 06) 46

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 11011
0100011
101101
00111001
101101
0101000 xor
101101
000101

Redes de Computadores (AULA 06) 47

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 11011
0100011
101101
00111001
101101
0101000
101101
000101

Redes de Computadores (AULA 06) 48

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 11011
0100011
101101
00111001
101101
0101000
101101
0001010

Redes de Computadores (AULA 06) 49

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 110110
0100011
101101
00111001
101101
0101000
101101
0001010

Redes de Computadores (AULA 06) 50

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 110110
0100011
101101
00111001
101101
0101000
101101
00010100

Redes de Computadores (AULA 06) 51

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 1101100
0100011
101101
00111001
101101
0101000
101101
00010100

Redes de Computadores (AULA 06) 52

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 1101100
0100011
101101
00111001
101101
0101000
101101
000101000

Redes de Computadores (AULA 06) 53

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 1101100
0100011
101101
00111001
101101
0101000
101101
000101000

Redes de Computadores (AULA 06) 54

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 11011001
0100011
101101
00111001
101101
0101000
101101
000101000

Redes de Computadores (AULA 06) 55

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 11011001
0100011
101101
00111001
101101
0101000
101101
000101000 xor
101101

Redes de Computadores (AULA 06) 56

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 11011001
0100011
101101
00111001
101101
0101000
101101
000101000 xor
101101
000101

Redes de Computadores (AULA 06) 57

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 11011001
0100011
101101
00111001
101101
0101000
101101
000101000
101101
000101

Redes de Computadores (AULA 06) 58

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 11011001
0100011
101101
00111001
101101
0101000
101101
000101000
101101
0001010

Redes de Computadores (AULA 06) 59

 Exemplo – Antes do Envio de Dados
11110010100000 101101
101101 110110010
0100011
101101
00111001
101101
0101000
101101
000101000
101101
0001010

Redes de Computadores (AULA 06) 60

 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.

Redes de Computadores (AULA 06) 61

CRC ou Código de Redundância Cíclica

Emissor Receptor

11110010101010

Redes de Computadores (AULA 06) 62

 Exemplo – Teste no Receptor
11110010101010

Redes de Computadores (AULA 06) 63

 Exemplo – Teste no Receptor
11110010101010 101101

Redes de Computadores (AULA 06) 64

 Exemplo – Teste no Receptor
11110010101010 101101
1

Redes de Computadores (AULA 06) 65

 Exemplo – Teste no Receptor
11110010101010 101101
101101 1

Redes de Computadores (AULA 06) 66

 Exemplo – Teste no Receptor
11110010101010 101101
101101 xor 1

Redes de Computadores (AULA 06) 67

 Exemplo – Teste no Receptor
11110010101010 101101
101101 xor 1
010001

Redes de Computadores (AULA 06) 68

 Exemplo – Teste no Receptor
11110010101010 101101
101101 1
0100011

Redes de Computadores (AULA 06) 69

 Exemplo – Teste no Receptor
11110010101010 101101
101101 11
0100011

Redes de Computadores (AULA 06) 70

 Exemplo – Teste no Receptor
11110010101010 101101
101101 11
0100011
101101

Redes de Computadores (AULA 06) 71

 Exemplo – Teste no Receptor
11110010101010 101101
101101 11
0100011
101101

Redes de Computadores (AULA 06) 72

 Exemplo – Teste no Receptor
11110010101010 101101
101101 11
0100011
101101 xor
001110

Redes de Computadores (AULA 06) 73

 Exemplo – Teste no Receptor
11110010101010 101101
101101 11
0100011
101101
001110

Redes de Computadores (AULA 06) 74

 Exemplo – Teste no Receptor
11110010101010 101101
101101 11
0100011
101101
0011100

Redes de Computadores (AULA 06) 75

 Exemplo – Teste no Receptor
11110010101010 101101
101101 110
0100011
101101
0011100

Redes de Computadores (AULA 06) 76

 Exemplo – Teste no Receptor
11110010101010 101101
101101 110
0100011
101101
00111001

Redes de Computadores (AULA 06) 77

 Exemplo – Teste no Receptor
11110010101010 101101
101101 1101
0100011
101101
00111001
101101

Redes de Computadores (AULA 06) 78

 Exemplo – Teste no Receptor
11110010101010 101101
101101 1101
0100011
101101
00111001
101101
010100

Redes de Computadores (AULA 06) 79

 Exemplo – Teste no Receptor
11110010101010 101101
101101 1101
0100011
101101
00111001
101101
0101000

Redes de Computadores (AULA 06) 80

 Exemplo – Teste no Receptor
11110010101010 101101
101101 11011
0100011
101101
00111001
101101
0101000
101101

Redes de Computadores (AULA 06) 81

 Exemplo – Teste no Receptor
11110010101010 101101
101101 11011
0100011
101101
00111001
101101
0101000
101101
000101

Redes de Computadores (AULA 06) 82

 Exemplo – Teste no Receptor
11110010101010 101101
101101 11011
0100011
101101
00111001
101101
0101000
101101
0001011

Redes de Computadores (AULA 06) 83

 Exemplo – Teste no Receptor
11110010101010 101101
101101 110110
0100011
101101
00111001
101101
0101000
101101
0001011

Redes de Computadores (AULA 06) 84

 Exemplo – Teste no Receptor
11110010101010 101101
101101 110110
0100011
101101
00111001
101101
0101000
101101
00010110

Redes de Computadores (AULA 06) 85

 Exemplo – Teste no Receptor
11110010101010 101101
101101 1101100
0100011
101101
00111001
101101
0101000
101101
00010110

Redes de Computadores (AULA 06) 86

 Exemplo – Teste no Receptor
11110010101010 101101
101101 1101100
0100011
101101
00111001
101101
0101000
101101
000101101

Redes de Computadores (AULA 06) 87

 Exemplo – Teste no Receptor
11110010101010 101101
101101 11011001
0100011
101101
00111001
101101
0101000
101101
000101101

Redes de Computadores (AULA 06) 88

 Exemplo – Teste no Receptor
11110010101010 101101
101101 11011001
0100011
101101
00111001
101101
0101000
101101
000101101
101101

Redes de Computadores (AULA 06) 89

 Exemplo – Teste no Receptor
11110010101010 101101
101101 11011001
0100011
101101
00111001
101101
0101000
101101
000101101
101101
000000

Redes de Computadores (AULA 06) 90

 Exemplo – Teste no Receptor
11110010101010 101101
101101 11011001
0100011
101101
00111001
101101
0101000
101101
000101101
101101
0000000

Redes de Computadores (AULA 06) 91

 Exemplo – Teste no Receptor
11110010101010 101101
101101 110110010
0100011
101101
00111001
101101
0101000
101101
000101101
101101
0000000

Redes de Computadores (AULA 06) 92

 Exemplo – Teste no Receptor
11110010101010 101101
101101 110110010
0100011
101101
00111001
101101
0101000
101101
000101101
101101
0000000

Redes de Computadores (AULA 06) 93

 Exemplo – Teste no Receptor
11110010101010 101101
101101 110110010
0100011
101101
00111001
101101
0101000
101101 Resto zero: os
dados recebidos
000101101 estão corretos
101101
0000000

Redes de Computadores (AULA 06) 94

 Considerações
• Padrões para CRC com 8, 12, 16 ou 32 bits:
– CRC-32

– CRC-16

– CRC-12

Redes de Computadores (AULA 06) 95

 Considerações
• Cada padrão de CRC detecta erros em rajadas
menores que (r+1) bits.
• Os padrões também detectam qualquer
quantidade ímpar de erros de bits.
• ATM utiliza CRC-8 no cabeçalho das células.
• CRC-32 é utilizado pelos protocolos da camada
de enlace padronizados pelo IEEE.

Redes de Computadores (AULA 06) 96

Lista de Exercícios

Redes de Computadores (AULA 06) 97