Controlo de Erros (CRC)

, Author

h2>Nosso Vídeo

Loading Your Video
“FAQ: Controlo de Erros (CRC)”

Controlo de Erros

Codificação binária é muito conveniente para utilização em dispositivos electrónicos como um computador, em que a informação pode ser codificada pela presença ou ausência de um sinal eléctrico.

No entanto, o sinal eléctrico pode estar sujeito a perturbações (distorção, presença de ruído), especialmente quando se transporta dados a uma longa distância. Assim, o controlo da validade dos dados
é necessário para certas aplicações (profissionais, bancárias, industriais, confidenciais, relacionadas com a segurança, …).

É por isso que existem mecanismos para garantir um certo nível de integridade dos dados, ou seja, para dar ao destinatário a garantia de que os dados recebidos são de facto semelhantes aos dados transmitidos. A protecção contra erros pode ser alcançada de duas maneiras:

  • ou tornando o meio de transmissão fiável, ou seja, confiando na protecção física. Uma ligação convencional tem geralmente uma taxa de erro entre 10-5 e 10-7,
  • ou implementando mecanismos de detecção e correcção de erros lógicos.

p>Os sistemas de controlo de erros ao nível lógico baseiam-se na adição de informação (a isto chama-se “redundância”) para verificar a validade dos dados. Esta informação adicional chama-se soma de controlo.

Correcção de erros

Assim, foram desenvolvidos sistemas de detecção de erros mais sofisticados, estes códigos são chamados :

  • Códigos de autocorrecção
  • Códigos de auto-verificação

h2>Verificação de paridade

Verificação de paridade (por vezes chamada VRC, para Vertical Redundancy Checking ou Vertical Redundancy Checking) é um dos sistemas de verificação mais simples.
Consiste em adicionar um bit extra (chamado bit de paridade) a um número de bits de dados chamado codeword
(geralmente 7 bits, para formar um byte com o bit de paridade) cujo valor (0 ou 1) é tal que o número total de bits a 1 é igual. Para ser mais explícito, consiste em adicionar 1 se o número de bits na palavra de código for estranho, 0 caso contrário.

Vejamos o seguinte exemplo:


Neste exemplo, o número de bits de dados de 1 bit é igual, pelo que o bit de paridade está definido para 0. No exemplo seguinte, contudo, os bits de dados são um número ímpar, pelo que o bit de paridade está definido para 1 :

Agora imaginemos que após a transmissão o bit menos significativo (o bit da direita) do byte anterior sofre interferência:

Então o bit da paridade já não corresponde à paridade do byte: é detectado um erro.

No entanto, se dois bits (ou um número par de bits) mudassem simultaneamente durante o transporte de dados, então nenhum erro seria detectado…

Desde que o sistema de verificação da paridade apenas detecta erros com um número ímpar de bits, apenas detecta 50% dos erros.
Este sistema de detecção de erros também tem a grande desvantagem de não permitir a correcção dos erros detectados (a única forma é exigir a retransmissão do byte errado..).

Verificação da paridade cruzada

Verificação da paridade cruzada (também conhecida como Verificação de Redundância Longitudinal ou LRC) não é uma verificação da integridade dos dados de um carácter, mas uma verificação da integridade dos bits de paridade de um bloco de caracteres.

Então “HELLO” a mensagem a ser transmitida, utilizando o código ASCII padrão. Aqui estão os dados, uma vez que serão transmitidos com os códigos de verificação da paridade cruzada:

>br>>/p>

0

Letter código ASCII
(7 bits)
Parity bit
(LRC)
H 1001000 0
E 1000101 1
L 1001100 1
L 1001100 1
1001111 1
VRC 1000010 0

h2>Cyclic Redundancy Check

Cyclic Redundancy Check (denoted CRC, ou Cyclic Redundancy Check) é um meio poderoso e fácil de implementar de verificação da integridade dos dados. É o principal método de detecção de erros utilizado em telecomunicações.

Princípio

Verificação da redundância cíclica consiste em proteger blocos de dados, chamados frames
(frames em inglês). Cada frame está associado a um bloco de dados, chamado código de verificação
(por vezes CRC por abuso de linguagem ou FCS para Sequência de Verificação de Frame no caso de um código de 32 bits). O código CRC contém elementos que são redundantes em relação à moldura, tornando possível a detecção de erros, mas também a sua reparação.

Cyclic Redundancy Check (CRC)

O princípio de CRC é tratar as sequências binárias como polinómios binários, ou seja, polinómios cujos coeficientes coincidem com a sequência binária. Assim, a sequência binária 0110101001 pode ser representada
na seguinte forma polinomial:

0*X9 + 1*X8 + 1*X7 + 0*X6 + 1*X5 + 0*X4 + 1*X3 + 0*X2 + 0*X1 + 1*X0
soit
X8 + X7 + X5 + X3 + X0
ou encore
X8 + X7 + X5 + X3 + 1

p> Desta forma, o bit menos significativo da sequência (o bit mais à direita) representa o grau 0 do polinómio (X0 = 1), o 4º bit da direita representa o grau
3 do polinómio (X3)… Uma sequência de n bits constitui assim um polinómio de grau máximo n-1. Todas as expressões polinomiais são posteriormente tratadas com aritmética do módulo 2.

Neste mecanismo de detecção de erros,
um polinómio pré-definido (chamado polinómio gerador e denotado G(X)) é conhecido tanto pelo emissor como pelo receptor. A detecção de erros consiste em o transmissor executar um algoritmo nos bits da moldura para gerar um CRC, e transmitir estes dois elementos
para o receptor. O receptor só precisa então de efectuar o mesmo cálculo para verificar se o CRC é válido.

Aplicação prática

Deixe M ser a mensagem correspondente aos bits da moldura a enviar e M(X) o polinómio associado. Chamemos M’ a mensagem transmitida, ou seja, a mensagem inicial à qual a CRC de n bits terá sido concatenada. O CRC é tal que M'(X)/G(X)=0. O código CRC é assim igual ao resto da divisão polinomial de M(X) (à qual concatenámos anteriormente n n n n nulos bits correspondentes ao comprimento do CRC) por G(X).

É ainda mais simples tomar um exemplo: tomemos a seguinte mensagem de 16 bits M: 1011 0001 0010 1010 (denota B1 em hexadecimal). Tomemos
G(X) = X3 + 1 (representado em binário como 1001).
Desde que G(X) é de grau 3, é uma questão de adicionar 4 bits nulos a M:
br>>br> O CRC é igual ao resto da divisão de M por G:
/p>

10110001001010100000
1001...,..,.,.,.....
----...,..,.,.,.....
0100..,..,.,.,.....
0000..,..,.,.,.....
----..,..,.,.,.....
1000.,..,.,.,.....
0000.,..,.,.,.....
----.,..,.,.,.....
1000.,..,.,.,.....
1001,..,.,.,.....
----,..,.,.,.....
1111..,.,.,.....
1001..,.,.,.....
----..,.,.,.....
1100.,.,.,.....
1001.,.,.,.....
----.,.,.,.....
1101,.,.,.....
1001,.,.,.....
----,.,.,.....
1000.,.,.....
0000.,.,.....
----.,.,.....
10001,.....
1001,.,.....
----,.,.....
10000.,.....
1001.,.....
----
1111,.....
1001,.....
----,.....
1100.....
1001.....
----.....
1100....
1001....
----....
1010...
1001...
----...
0110..
0000..
----..


----.
1010
1001
----
0011

p> Para criar M’ é suficiente concatenar o CRC assim obtido aos bits da moldura a ser transmitida:

M' = 1011000100101010 + 0011
M' = 10110001001010100011

Assim, se o receptor da mensagem efectuar a divisão de M’ por G, obterá um remanescente de zero se a transmissão tiver sido concluída sem erro:

10110001001010100011
1001...,..,.,.,...,,
----...,..,.,.,...,,
0100..,..,.,.,...,,
0000..,..,.,.,...,,
----..,..,.,.,...,,
1000.,..,.,.,.....
1001.,..,.,.,.....
----.,..,.,.,.....
0010,..,.,.,.....
0000,..,.,.,.....
----,..,.,.,.....
0101..,.,.,.....
0000..,.,.,.....
----..,.,.,.....
1010.,.,.,.....
1001.,.,.,.....
----.,.,.,.....
0110,.,.,.....
0000,.,.,.....
----,.,.,.....
1101.,.,.....
1001.,.,.....
----.,.,.....
1010,.,.....
1001,.,.....
----,.,.....
0111.,.....
0000.,.....
----
1110,.....
1001,.....
----,.....
1111.....
1001.....
----.....
1100....
1001....
----....
1010...
1001...
----...
0110..
0000..
----,,
1101,
1001,
----,
1001
1001
----
0

h2>Geração de polinómios

Os polinómios geradores mais utilizados são:

  • CRC-12 : X12 + X11 + X3 + X2 + X + X + 1
  • CRC-16 : X16 + X15 + X2 + 1
  • CRC CCITT V41 : X16 + X12 + X5 + 1

(Este código é utilizado em particular no procedimento HDLC.)

    CRC-32 (Ethernet) : = X32 + X26 + X23 + X22 + X16 + X12 +
    X11 + X10 + X8 + X7 + X5 + X4 + X2 + X + X + 1

    • CRC ARPA : X24 + X23+ X17 + X16 + X15 + X15 +

Deixe uma resposta

O seu endereço de email não será publicado. Campos obrigatórios marcados com *