Verificação de Redundância Cíclica Através de um Exemplo
Prof. Othon Batista
A verificação de redundância cíclica (CRC – Cyclic Redundancy Check) é realizada através de um cálculo bastante simples. O objetivo é
enviar a mensagem anexada a alguns bits que possibilitem a verificação por parte do receptor sem o conhecimento da mensagem
original. A divisão da mensagem com a informação anexada pelo gerador deve ser zero no receptor para que o resultado esteja correto.
Por exemplo, para a mensagem M e o gerador G dados, quantos e quais bits devem ser anexados à mensagem para que o CRC seja
calculado?
Mensagem M: 101101
Gerador G: 1101 com 4 bits. R deve ter 3 bits
1 o Passo - Deslocar a mensagem à esquerda 3 bits. Isso é o mesmo que M*2 R.
Mensagem deslocada: 101101000
R
2 o Passo - Dividir a mensagem deslocada pelo gerador. Isso é o mesmo que
M∗2
G
. As subtrações não levam em conta o fato de
um número ser maior que o outro, desde que tenham a mesma quantidade de bits iniciando com 1, e são efetuadas como a operação
lógica XOR, ou seja: 1 - 1 = 0; 0 - 0 = 0; 1 - 0 = 1 e 0 - 1 = 1. Não há operações de vai um ou empresta um.
Passo 1 da divisão:
101101000 / 1101
1101
1
---0110
1011 < 1101, mas tudo bem, pois
apenas interessa a quantidade de bits.
1011 XOR 1101 = 0110
Passo 2 da divisão:
101101000 / 1101
1101|
11
----|
01100
1101
---0001
O próximo dígito, que é 0, “desce”.
1100 < 1101, mas tudo bem, pois
apenas interessa a quantidade de bits.
1100 XOR 1101 = 0001
Passo 3 da divisão:
101101000 / 1101
1101 |||
11001
---- |||
01100|||
1101|||
----|||
0001100
1101
---0001
O próximo dígito, que é 1, “desce”.
O número 11 tem apenas dois bits.
a. Acrescenta-se 0 no quociente;
b. “desce” o próximo dígito, que é 0.
O número 110 tem apenas três bits.
Repetem-se os passos a. e b.
1100 < 1101, mas tudo bem, pois
apenas interessa a quantidade de bits.
1100 XOR 1101 = 0001
Passo 4 da divisão:
101101000 / 1101
1101
|
110010
---|
01100
|
1101
|
---|
0001100|
1101|
----|
00010
O próximo dígito, que é 0, “desce”.
O número 10 tem apenas dois bits.
Não tem mais o que “descer”
Acrescenta-se 0 ao quociente e, acabou.
1100 XOR 1101 = 0001
O resto é 10.
3 o Passo - Utilizar o resto da divisão efetuada no passo 2, preencher com 1 zero à esquerda para completar 3 bits, e anexar à direita da
mensagem M.
M + R = 101101 010
4 o Passo - Verificar que a divisão
MR
=0
G
, usando as mesmas regras de divisão aplicadas no passo 2.
A página em inglês http://www.macs.hw.ac.uk/~pjbk/nets/crc/ contém um applet Java que realiza o cálculo de CRC para qualquer valor
informado pelo usuário.