UNIDADE III
Aula 6 – Cálculo do CRC
Fonte: Othon M. N. Batista
Relembrando a aula passada
passada…
` A verificação de redundância cíclica (CRC –
Cyclic Redundancy Check) consiste na técnica de
detecção de erros muito usada em redes de
computadores
` Os códigos CRC utilizam-se de códigos
polinomiais expresso na fórmula:
polinomiais,
B( x) = x + x + x + x (101101) 2
5
`
3
2
0
Uma mensagem deve ser enviada com o
código
ódi
de
d CRC calculado
l l d 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
binários, porém essa divisão é chamada de
divisão exclusiva, pois as operações de subtração são substituídas
por operações lógicas de ou exclusivo (XOR – eXclusive OR).
O XOR diferencia-se do OR (OU simples) pois, para cada comparação
de termos, a expressão só será verdadeira se os pares da
comparação
p
ç forem antagônicos
g
((um verdadeiro e o outro falso,, ou
vice-versa)
Relembrando a tabela da operação XOR:
`
`
`
`
A base para o cálculo de R (código de CRC) baseia-se na fórmula:
Onde R = Valor do CRC; D = bits de dados a serem enviados; r =
deslocamento do bit de dados à esquerda r casas e; G = gerador (padrão
de bits que emissor e receptor conhecem). O bit mais significativo (mais à
esquerda)
q
) do Gerador deve ser sempre
p 1.
Observe a divisão binária a ser realizada é exclusiva (através do XOR) e
que, o que importará, no final, será obter o resto desta divisão.
Ex: Suponha que um transmissor deseje enviar uma mensagem cujos bits
são 111100101. O gerador desta mensagem é 101101. Encontre o
polinômio do Gerador e realize o cálculo do CRC. Resposta no próximo
Slide.
Slid
`
Resposta:
◦ 1º passo
passo: encontrar o polinômio do Gerador
Gerador: sabemos q
que
e o Gerador é ig
igual
al a
101101. Assim, o polinômio gerador será feito através da fórmula:
G ( x) = 15 + 0 4 + 13 + 12 + 01 + 10
Donde, eliminando os termos cujo bit seja 0, temos o polinômio Gerador como:
G ( x) = 15 + 13 + 12 + 1
Desta forma, notamos que o grau deste polinômio é 5 (r=5), o que implica dizer que
deveremos
de
e e os ad
adicionar
c o a 5 zeros
e os à d
direita
e ta dos b
bits
ts da mensagem
e sage a se
ser ttransmitida
a s t da ((D);
);
◦ 2º passo: Multiplicar a mensagem (D) por 2r . Então D * 25 = 11110010100000
(note que adicionamos os 5 zeros à direita de D).
◦ 3º passo: Realizar a divisão binária exclusiva (XOR) com o Gerador e obter o resto
desta divisão, que será o nosso CRC:
11110010100000
R = resto(
) => resto(11011001) => R = 00001010
101101
`
Resposta:
◦ 4º passo
passo: De posse do resto da di
divisão,
isão contamos os bits da direita para a esq
esquerda
erda
até a ordem do polinômio do Gerador que, no nosso caso é igual a 5 (r=5) e
desprezamos os bits mais a esquerda restantes. Assim, como R = 00001010,
temos R = 00001010 . Então R = 01010,, q
que é o nosso CRC ((transmissão).
)
◦ 5º passo: 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 (divisão
binária exclusiva) pelo gerador para verificar se os bits estão corretos. Assim,
como D = 111100101 e R = 01010 => D
D+R
R = 11110010101010:
11110010101010
`
Resposta:
◦ 6º passo
passo: Divisão
Di isão da mensagem acrescida do CRC a ser transmitida pelo polinômio
gerador. Se a mensagem recebida tiver o resto = 0, significa dizer que a
mensagem foi recebida corretamente. Então:
11110010101010
R = resto(
) => resto(11011001) => R = 0000000
101101
`
Para detalhes acerca deste exemplo, com o passo-a-passo da divisão
binária, ver os seguintes vídeos:
http://www youtube com/watch?v=XWcJcybL3JQ (parte 1) e
http://www.youtube.com/watch?v=XWcJcybL3JQ
http://www.youtube.com/watch?v=wyUNSzDbFjg&feature=related
(parte 2). O slide completo destes vídeos pode ser obtido em:
htt //
http://www.othonbatista.com/arquivos/redes/aulas/redes-othonth b ti t
/
i
/ d / l / d
th
crc.pdf .
`
Existem alguns polinômios geradores padronizados para serem
usados no cálculo de CRC que foram testados para garantir as
propriedades listadas acima. Os mais comuns são:
`
`
`
Existem alguns modelos computacionais (algoritmos) que
permitem
it
calcular
l l o CRC
CRC. Vamos
V
utilizar
tili
como exemplo
l
dois programas, um deles feito em Matlab R2010b
(arquivos calc_crc.m
calc crc m e calc_crc.fig),
calc crc fig) cujo objetivo é
realizar o cálculo do CRC à partir de uma mensagem
binária e o segundo, feito em C ANSI
(teste_arquivo_crc.exe, cujo código-fonte é o
teste_arquivo_crc.cpp), que simula o envio de um texto
como se fosse um arquivo e a sua posterior checagem
checagem,
através do CRC convertido para binário.
Para utilizar os exemplos
exemplos, descompacte o aquivo
calc_crc_ex.zip em alguma pasta de sua preferência.
Serão criadas as p
pastas CRC_Matlab e CRC_C.
À seguir exemplos demonstrativos de cada um destes
programas...
1.
2.
3
3.
Execute o Matlab R2010b e abra a pasta onde os
arquivos
i
fforam compactados
d como a sua pasta padrão;
d ã
Do lado direito da janela do Matlab, procure o arquivo
calc crc m e,
calc_crc.m
e com o botão direito em cima dele
dele, clique
em Run;
A seguinte janela será exibida:
4.
5.
O programa é aberto tendo como exemplo uma mensagem de formato
binário 1010011 (pode ser digitadas mensagens entre 6 e 9 bits) e como
Gerador 110010 (deve ser obrigatoriamente de 6 bits). Se desejar gerar
aleatoriamente novas mensagens, basta clicar no botão Gerar mensagem
randômica;
Após definida mensagem e gerador, clicar no botão Calcula CRC (realiza o
cálculo do CRC do transmissor). Note que é calculado automaticamente o
resto da divisão (o CRC) e a mensagem enviada é acrescida deste resto
resto,
conforme visto no exemplo teórico anterior:
6.
Para checar o CRC do lado do transmissor, basta clicar no botão Verifica
CRC Note que o resto da divisão zero
CRC.
zero, indicando que a mensagem foi
recebida com sucesso.
OBSERVAÇÕES IMPORTANTES:
`
O algoritmo que foi utilizado para gerar este código diverge do cálculo manual do
CRC, visto no exemplo didático do Professor Othon Batista, o que não inviabiliza sua
aplicação. Então, se tentarmos reproduzir a mesma mensagem e gerador utilizado
no exemplo de Othon, obteremos um resto (CRC) do transmissor diferente do
obtido pela divisão binária exclusiva manualmente feita. Abaixo é mostrado o
resultado gerado pelo programa, ao qual se observa que o resto da divisão do
receptor será zero, comprovando a eficácia deste algoritmo computacional.
Detalhes do algoritmo pode ser visto no próprio arquivo calc_crc.m
calc crc m ou através do
arquivo descritivo Pseudo Code for CRC calculator and Verifier.mht que encontra-se
na mesma pasta onde o programa calc_crc.m se encontra e deve ser aberto pelo seu
navegador de Internet
OBSERVAÇÕES IMPORTANTES:
`
Se desejar simular um erro na recepção,
recepção basta substituir qualquer bit (ou
mais de um) da mensagem enviada e mandar verificar novamente o CRC
(botão Verifica CRC). A mensagem recebida será diferente e,
consequentemente o resto do receptor (CRC do receptor) não será zero
consequentemente,
zero,
comprovando que a mensagem enviada difere da mensagem recebida.
1.
2.
3.
4
4.
Execute o arquivo teste_arquivo_crc.exe (programa feito em C
ANSI) à partir da pasta CRC
ANSI),
CRC_C;
C;
Na janela que se abre, digite a mensagem a ser enviada (“texto
original”);
Após, digite a mensagem a ser checada (“texto a ser verificado”).
Isto irá simular as mensagens enviadas e recebidas;
Se o texto enviado for o mesmo do recebido
recebido, o programa resultará
na compatibilidade do CRC. Esse programa utiliza algoritmo
semelhante ao implementado no programa do Matlab.
`
`
Digitando uma mensagem diferente da enviada, o teste de CRC
falhará simulando o que ocorreria no recebimento errado de uma
falhará,
mensagem enviada pelo transmissor ao receptor
Note que um único
ú
caractere diferente
df
(o
( “T”
“ ” da
d palavra
l
Teste foi
f
recebida como sendo um “t” minúsculo) acarreta um erro de CRC
no recebimento.