Cálculo de Cyclic Redundancy Check – CRC

Prévia do material em texto

othonb@yahoo.com 2009 ©
Cálculo de 
Cyclic Redundancy Check – CRC
Prof. Othon M. N. Batista
Mestre em Informática
Redes de Computadores e Sistemas Distribuídos
othonb@yahoo.com
othonb@yahoo.com 2009 ©
Roteiro
● Introdução
● Cálculo de CRC
● Exemplo – Antes do Envio de Dados
● Exemplo – Envio de Dados
● Exemplo – Teste no Receptor
● Considerações
othonb@yahoo.com 2009 ©
Introdução
● 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.
B(x) = x5 + x3 + x2 + x0 = (101101)2
● Uma mensagem deve ser enviada com o código de 
CRC calculado para que possa ser verificada no 
receptor.
othonb@yahoo.com 2009 ©
Introdução
● 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).
● Relembrando a tabela da operação XOR:
AA BB A XOR BA XOR B
0 0 0
0 1 1
1 0 1
1 1 0
othonb@yahoo.com 2009 ©
● 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.
● 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.
Cálculo de CRC
R: r bits de CRCD: d bits de dados
othonb@yahoo.com 2009 ©
Cálculo de CRC
● A base para o cálculo de R (código de CRC) é a 
fórmula:
● D * 2r é o deslocamento dos bits de dados à esquerda 
r casas.
– Isso é a adição de r bits 0 no final dos bits de dados. Por 
exemplo:
D = (100101)2 e r = 3 ⟹ D * 2r = (100101000)2
R=resto D∗2
r
G
othonb@yahoo.com 2009 ©
Exemplo – Antes do Envio de Dados
Emissor Receptor
111100101
● 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???
CRC???
othonb@yahoo.com 2009 ©
11110010100000
1101101
101101
XOR
0100011
1
101101XOR
0011100
0
1
1
101101XOR
0101000
1
101101
XOR
0001010
0
0
0
0
1
101101XOR
0001010
Bits que são adicionados aos 
dados antes do envio.
Dados = (111100101)
2
Gerador = (101101)
2
 ou
G(X) = x5 + x3 + x2 + x0
Exemplo – Antes do Envio de Dados
othonb@yahoo.com 2009 ©
Exemplo – Envio dos Dados
Emissor Receptor
11110010101010
● 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 verifica se os bits estão corretos.
othonb@yahoo.com 2009 ©
Exemplo – Teste no Receptor
11110010101010
1101101
101101XOR
0100011
1
101101XOR
0011100
0
1
1
101101XOR
0101000
1
101101
XOR
0001011
0
0
0
1
1
101101
XOR
0000000
Resto zero: os dados 
recebidos estão corretos.
Dados = (111100101)
2
CRC = (01010)2
Gerador = (101101)
2
 ou
G(X) = x5 + x3 + x2 + x0
othonb@yahoo.com 2009 ©
Considerações
● Padrões para CRC com 8, 12, 16 ou 32 bits:
CRC-32
G(x) = x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x1 + x0 = 
(100000100110000010001110110110111)2
CRC-16
G(x) = x16 + x15 + x2 + x0 = (11000000000000101)2
CRC-12
G(x) = x12 + x3 + x1 + x0 = (1000000001011)2
CRC-8
G(x) = x8 + x2 + x1 + 1 = (100000111)2
othonb@yahoo.com 2009 ©
Considerações
● Cada padrão de CRC detecta erros em rajadas 
menores que (r + 1) bits.
● Mesmo um erro em rajadas iguais ou superiores a (r 
+ 1) bits é detectada com probabilidade (1 – 0,5r).
● 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.
othonb@yahoo.com 2009 ©
Referências
[1] KUROSE, J. F. e ROSS, K. W. Redes de 
Computadores e a Internet – Uma Abordagem Top-
Down. 3a edição. Pearson Addison Wesley. 2006.
[2] TANENBAUM, A. S. Redes de Computadores. 4a 
edição. 2003.
[3] SCHWARTZ, M. Information, Transmission, 
Modulation and Noise. McGraw Hill. 1980.
othonb@yahoo.com 2009 ©
Fim
MUITO OBRIGADO!!!
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14