FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO

Detecção de erros de

comunicação de dados

CRC

Rui Barbosa

12/04/2011

2

ÍNDICE

1. Introdução .............................................................................................................................................. 4

2. Cyclic Redundancy Check ................................................................................................................ 5

2.1. Fundamentos Teóricos .................................................................................................................. 5

2.2. Utilização prática ........................................................................................................................... 8

2.2.1. CRC - 12 .................................................................................................................................... 8

2.2.2. CRC - 16 .................................................................................................................................... 9

2.2.3. CRC - CCITT .............................................................................................................................. 9

2.2.4. CRC - 32 .................................................................................................................................. 10

2.3. Hardware ....................................................................................................................................... 10

3. Conclusão ............................................................................................................................................ 13

4. Anexos ................................................................................................................................................... 14

I. Exemplo de Código de Implementação do CRC-32 ............................................................. 15

3

ÍNDICE DE FIGURAS

Figura 1- Diagrama de blocos do CRC-12 .......................................................................................... 8

Figura 2 - DIAGRAMA DE BLOCOS DO CRC-16 .................................................................................. 9

Figura 3 - DIAGRAMA DE BLOCOS DO CRC-CCITT ............................................................................ 9

Figura 4 - DIAGRAMA DE BLOCOS DO CRC-32 ................................................................................ 10

Figura 5 - Portas lógica XOR (à esquerda) e Shift Register (à Direita) ......................................... 11

Figura 6- Algoritmo Básico do CRC-32 ............................................................................................... 15

ÍNDICE DE TABELAS

Tabela 1 - Polinómios Geradores de alguns CRC Standard ........................................................... 8

Tabela 2 - Funções Lógicas do XOR e do shift register ................................................................... 11

4

1. INTRODUÇÃO

O objectivo da codificação de dados é a eficiência do transporte dos mesmos através

de um meio específico. Esse meio pode ser um cabo de cobre de par entrelaçado, cabo

coaxial de cobre, cabo óptico ou ar. Cada tipo de meio de comunicação tem uma série

de incapacidades que se traduzem em erros na transmissão de dados. Estes erros podem

incluir a reflexão do sinal, a atenuação do sinal, distorção harmónica, distorção de fase,

eco, interferência, ruído gaussiano e de mudança de frequência. Todas estas deficiências

afectam a capacidade de transporte de dados. Em alguns casos, esses factores podem

causar um número excessivo de erros. Assim sendo é necessário implementar algoritmos

de verificação de erros nos dados transmitidos.

É possível a utilização de métodos ad-hoc para gerar checksums de verificação de

dados, mas usa-se, normalmente, sistemas padrão com propriedades bem

compreendidas como é o caso do CRC.

Este documento tem como finalidade explicar e descrever o funcionamento do CRC.

5

2. CYCLIC REDUNDANCY CHECK

O CRC (Cyclic Redundancy Check) é uma técnica usada para detecção de erros na

transmissão de dados digitais No método CRC são adicionados check bits normalmente

chamados de checksum. Estes são anexados à mensagem que irá ser transmitida. O

receptor pode assim determinar se os check bits estão de acordo com os dados

transmitidos e determinar com um certo grau de certezas se ocorreram erros na

transmissão ou não. Se ocorrer um erro o receptor envia um “negative

acknowledgement” (NAK) de volta ao emissor, pedindo para que a mensagem seja

retransmitida.

2.1. FUNDAMENTOS TEÓRICOS

O CRC é baseado em aritmética polinomial, em particular, sobre a computação do

resto da divisão de um polinómio em GF(2) - Galois field with two elements - por outro.

Um polinómio em GF (2) é um polinómio com uma única variável x cujos coeficientes

são 0 ou 1. A adição e subtracção são feitas em módulo para 2. A aritmética módulo 2

pode ser facilmente calculada através de uma operação de ou-exclusivo realizada bit a

bit entre os coeficientes do polinómio, ou seja, dos dígitos binários. Podemos notar que as

duas operações tem sempre o mesmo resultado equivalente ao da operação lógica de

ou exclusivo (ou XOR, da sigla em inglês exclusive OR).

Como exemplo podemos somar o polinómio e . O primeiro passo é a

transformação do polinómio em um número binário:

e

Procedemos então ao ou-exclusivo bit-a-bit (designada também por "soma polinomial

em módulo 2"):

6

Ou ainda:

Estes polinómios normalmente não são escritos com sinal negativa embora o possam

ser mas, o coeficiente -1 é equivalente a um coeficiente 1.

A multiplicação destes polinómios é simples. O produto de um coeficiente por outro

dado pela lógica do operador AND, e os produtos parciais são somados utilizando o

operador OU EXCLUSIVO. A multiplicação não é necessária para calcular o checksum

CRC.

No que diz respeito à divisão, existem diversas formas de realizar a divisão de módulo 2

entre dois números binários. A melhor maneira é fazer a representação polinomial do

Dividendo D e do Divisor d, e subtrair consequentemente os monómios do polinómio D. Ao

Dividendo polinomial D inicial, é concatenado á sua direita tantos monómios quanto o

grau do polinómio d.

Para que se entenda melhor é apresentado de seguida um exemplo:

Exemplo 1: Dividir 101011 por 11001.

11001 corresponde ao Divisor d(o qual também é designado por polinómio

"gerador"), e é representado pelo polinómio de grau 4,

;

101011 corresponde ao dividendo inicial D;

1010110000 corresponde ao dividendo inicial D concatenado com tantos bits

nulos quanto o grau do polinómio d (Neste caso o grau polinomial é de 4);

Assim sendo, 1010110000 o qual corresponde ao Dividendo final, será expresso

pelo polinómio

Procedendo agora à divisão:

7

Resto: , em binário 1001

Quociente: , em binário: 110001

No CRC o são adicionados à trama bits checksum para que garantir que a trama final

é divisível por um polinómio g(x) denominado por polinómio gerador. Assim sendo,

podemos transformar uma trama F(x) numa trama T(x) que é divisível por g(x). Se houver

erros em T(x), estes assumem a forma de uma string diferente E(x) e, no final, os bits

recebidos são T(x)+E(x).

Quando o receptor recebe uma trama correcta, ela é dividida pelo polinómio g(x) e o

resto da divisão obtida é nula. A questão que se coloca é quando é que a trama

recebida T(x)+E(x) quando dividida pelo g(x) retorna um resto de divisão nulo?

Erro num único bit? Um erro num único bit significa que E(x) vai apenas ter um

único termo. Se g(x) for de grau n a divisão nunca vai ser nula;

Erro em múltiplos bits? Diferentes polinómios geradores são usados com

propriedades diferentes. Deve haver um factor no polinómio que

assegura a detecção de erros em todos os bits impares (1,3,5,…)

Alguns polinómios geradores comummente utilizados são:

CRC 12 bits:

CRC 16 bits:

CRC 32 bits:

CRC CCITT:

Pegando no Exemplo 1, anteriormente descrito, onde o nosso (11001)

e considerando o nosso . Assim, se dividirmos o F(x) por g(x) e o resto for

anexado ao F(x) obtém-se o T(x). Segundo os cálculos anteriores, T(x)= 1010111001.

Quando estes dados forem recebidos são divididos e, se a recepção dos dados for

correcta, o resto da divisão será nula.

8

2.2. UTILIZAÇÃO PRÁTICA

A Tabela 1 mostra os polinómios gerados mais usados para alguns CRC standards.

NOME GERADOR

POLINÓMIO HEX

CRC - 12 80F

CRC - 16 8005

CRC - 32

1021

CRC CCITT 04C11DB7

TABELA 1 - POLINÓMIOS GERADORES DE ALGUNS CRC STANDARD

2.2.1. CRC - 12

O CRC-12 é usado para transmissões de conjuntos de caracteres de 6bits, é usado

ainda em conjuntos de caracteres de 8 bits ou ainda em dados arbitrários de 8 bits.

O diagrama de blocos é apresentado de seguida. Os dados são deslocados para a

linha de entrada de dados. Após todos os dados serem deslocados, o resto será

guardado nos registos de 0 a 11.

FIGURA 1- DIAGRAMA DE BLOCOS DO CRC-12

9

2.2.2. CRC - 16

O CRC-16 é utilizado no protocolo de comunicações BISYNCH da IBM.

O diagrama de blocos é apresentado de seguida. Os dados são deslocados para a

linha de entrada de dados. Após todos os dados serem deslocados, o resto será

guardado nos registos de 0 a 15.

FIGURA 2 - DIAGRAMA DE BLOCOS DO CRC-16

2.2.3. CRC - CCITT

O CRC-CCITT, também conhecido como ITU-TSS, é usado em vários protocolos de

comunicações como é o caso do XMODEM, X.25, IBM’s SDLC e ISO’s HDLC.

O diagrama de blocos é apresentado de seguida. Os dados são deslocados para a

linha de entrada de dados. Após todos os dados serem deslocados, o resto será

guardado nos registos de 0 a 15.

FIGURA 3 - DIAGRAMA DE BLOCOS DO CRC-CCITT

10

2.2.4. CRC - 32

CRC – 32 é também conhecido como AUTODIN-II e ITU-TSS (ITU-TSS definiu tanto

polinómios de 16 e 32 bits). É usado em PKZip, Ethernet, AAL5, (ATM Adaptation Layer 5),

FDDI (Fiber Distributed Data Interface), o protocol IEEE-802 LAN/MAN e em algumas

aplicações DOD.

O diagrama de blocos é apresentado de seguida. Os dados são deslocados para a linha

de entrada de dados. Após todos os dados serem deslocados, o resto será guardado nos

registos de 0 a 31.

FIGURA 4 - DIAGRAMA DE BLOCOS DO CRC-32

2.3. HARDWARE

Como foi possível verificar anteriormente, a divisão de polinómios seria mais fácil se

todos os coeficientes forem 1. Isto porque existe um circuito que pode realizar os cálculos

de uma trama de forma continua. O circuito é construído através de portas lógicas XOR

(ou-exlusivo) e shift registers.

11

FIGURA 5 - PORTAS LÓGICA XOR (À ESQUERDA) E SHIFT REGISTER (À DIREITA)

A tabela seguinte mostra as funções lógicas destas duas portas lógicas.

A B A XOR B

0 0 0

0 1 1

1 0 1

1 1 0

TABELA 2 - FUNÇÕES LÓGICAS DO XOR E DO SHIFT REGISTER

A saída do XOR dá a função de ou-exclusivo de dois sinais de entrada enquanto que a

saída do shift register Q muda o valor de entrada quando se dá um rising do clock.

Circuitos simples podem ser contruidos através desta lógica para realizar a divisão de

polinómios.

O circuito mostrado em baixo tem 5 shift registers o que corresponde a uma sequência

de 5 bits de checksum (grau 5 do polinómio gerador) e um polinómio gerador de

comprimento de 6 bits. Neste exemplo, o polinómio gerador é 100101 (o shift register mais

à esquerda corresponde ao bit menos significativo do polinómio gerador).

Se houver apenas 0s no sistema e colocarmos à entrada os dados 101101011, obtém-se

os seguintes estados:

D C Q

0 0

1 1

0 D

1 D

12

Dados de

entrada D4 D3 D2 D1 D0 Observações

… 0 0 0 0 0 Estado inicial

1 0 0 0 0 1 1º Bit

0 0 0 0 1 0 2º Bit

1 0 0 1 0 1 3º Bit

1 0 1 0 1 1

0 1 0 1 1 0

1 0 1 0 0 0

0 1 0 0 0 0

1 0 0 1 0 0

1 0 1 0 0 1

0 1 0 0 1 0

0 0 0 0 0 1

0 0 0 0 1 0

0 0 0 1 0 0

0 0 1 0 0 0

E assim resulta T(x) = 101101011 01000

13

3. CONCLUSÃO

Este documento analisou e explicou o funcionamento do código de verificação de

erros CRC.

Quando a linha de transmissão é longa e é afectada por ruídos, técnicas mais

avançadas de verificação de erros são implementadas. A redundância pode ser

acrescentada ao código para garantir um melhor desempenho do sistema. Quando os

sistemas são mais avançados devem ser usados códigos de controlo de erros mais

complexos como é o caso de verificação de paridade, checksums, CRCs.

Em todos os casos, a redundância resultante da utilização destes códigos permite ao

sistema tolerar uma relação sinal/ruído menos para uma taxa de transmissão de dados

fixa e, consequentemente, permite reduzir o número de erros na transmissão de dados.

14

4. ANEXOS

15

I . EXEMPLO DE CÓDIGO DE IMPLEMENTAÇÃO DO CRC-

32

FIGURA 6- ALGORITMO BÁSICO DO CRC-32