Cálculo de CRC - Sobre o Prof. Othon

Cálculo de
Cyclic Redundancy Check – CRC
Prof. Othon M. N. Batista
Mestre em Informática
Redes de Computadores e Sistemas Distribuídos
[email protected]
[email protected]
2009 ©
Roteiro
●
Introdução
●
Cálculo de CRC
●
Exemplo – Antes do Envio de Dados
●
Exemplo – Envio de Dados
●
Exemplo – Teste no Receptor
●
Considerações
[email protected]
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.
[email protected]
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:
[email protected]
A
0
B
0
A XOR B
0
0
1
1
1
0
1
1
1
0
2009 ©
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
deve 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.
Este gerador tem (r + 1) bits de comprimento.
O bit mais significativo do gerador (mais à esquerda)
deve ser 1.
[email protected]
2009 ©
Cálculo de CRC
●
A base para o cálculo de R (código de CRC) é a
fórmula:
r
●
D∗2
R=resto
G
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
[email protected]
2009 ©
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???
Emissor
Receptor
111100101
CRC???
[email protected]
2009 ©
Exemplo – Antes do Envio de Dados
101101
11110010100000
XOR
11 0 11 0 0 1
101101
0100011
XOR
101101
Dados = (111100101)2
Gerador = (101101)2 ou
001110 01
XOR
G(X) = x5 + x3 + x2 + x0
101101
0101000
XOR
101101
0001010 0 0
XOR
Bits que são adicionados aos
101101
dados antes do envio.
0001010
[email protected]
2009 ©
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 verifica se os bits estão corretos.
Emissor
Receptor
11110010101010
[email protected]
2009 ©
Exemplo – Teste no Receptor
11110010101010 101101
101101
1 1 0 11 0 01
0100011
XOR
Dados = (111100101)2
101101
CRC = (01010)2
00111001
XOR
Gerador = (101101)2 ou
101101
G(X) = x5 + x3 + x2 + x0
0101000
XOR
101101
00010110 1
XOR
Resto zero: os dados
101101
recebidos estão corretos.
0000000
XOR
[email protected]
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
[email protected]
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.
[email protected]
2009 ©
Referências
[1] KUROSE, J. F. e ROSS, K. W. Redes de
Computadores e a Internet – Uma Abordagem TopDown. 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.
[email protected]
2009 ©
Fim
MUITO OBRIGADO!!!
[email protected]
2009 ©