O controle de erros

Novembro 2017

O controle de erros

A codificação binária é de grande utilidade em dispositivos eletrônicos como computadores, onde a informação pode ser codificada graças à presença, ou não, de um sinal elétrico.

Contudo, o sinal elétrico pode sofrer alterações (distorção ou ruídos), especialmente quando os dados são transportados por longas distâncias. Por este motivo, o controle da validade dos dados é imprescindível para certos objetivos (profissionais, bancários, industriais, confidenciais, relativos à segurança etc.).

É por isso que existem mecanismos que permitem garantir um certo nível de integridade dos dados, ou seja, que o destinatário obtenha uma confirmação de que os dados recebidos são, na realidade, similares aos dados transmitidos. Existem duas maneiras de proteger a transferência de dados para evitar erros: instalando um meio de transmissão mais seguro, isto é, uma camada de proteção física, ou instalando mecanismos lógicos de detecção e correção de erros.


A maioria dos sistemas de controle lógico de erros se baseia na soma de informação (isto se chama redundância) para verificar a validade dos dados. Esta informação adicional é chamada de soma de controle (checksum).

Como é feita a correção de erros

É assim que os sistemas de detecção de erros mais sofisticados foram criados, estes códigos são chamados de códigos autocorretor e códigos diversificadores.

O controle de paridade

O controle de paridade (VRC - Vertical Redundancy Checking) é um dos sistemas de controle mais simples. Ele consiste em acrescentar um bit adicional (chamado bit de paridade) a um certo número de bits de dados chamado palavra de código (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 seja par. Para ser mais explícito, consiste em acrescentar um 1 se o número de bits da palavra de código for ímpar e 0 no caso contrário.

Vejamos o seguinte exemplo:


Neste exemplo, o número de bits de dados a 1 é par, por conseguinte, o bit de paridade é posicionado em 0. Porém, no exemplo seguinte, os bits de dados sendo em número ímpar, o bit de paridade é de 1:


Agora, imaginemos que depois da transmissão o bit de peso fraco (o bit situado à direita) do byte precedente seja vítima de uma interferência:


O bit de paridade não corresponde mais então à paridade do byte: um erro foi detectado. Contudo, se dois bits (ou um número par de bits) mudam, simultaneamente, durante o transporte de dados, então nenhum erro seria detectado:


Já que o sistema de controle de paridade pode detectar um número ímpar de erros, ele só pode detectar 50% dos erros. Este sistema de detecção de erros também tem a grande desvantagem de não poder corrigir os erros encontrados (a único forma de corrigi-lo é solicitar a retransmissão do byte errado).

O controle de paridade cruzado

O controle de paridade cruzado (também chamado controle de redundância longitudinal) não consiste em controlar a integridade dos dados através da representação de um caractere, mas sim na verificação da integridade do bit de paridade de um conjunto de caracteres.

Digamos que 'HELLO' é a mensagem a ser transmitida, utilizando o código ASCII padrão. Veja os dados tal como foram transmitidos com os códigos de controle de paridade cruzado:

LetraCódigo ASCII (7 bits)Bit de paridade (LRC)
H10010000
E10001011
L10011001
L10011001
010011111
VRC10000100

O controle cíclico de redundância

O controle cíclico de redundância (CRC - Cyclic Redundancy Check) é um meio de controle de integridade de dados muito fácil de aplicar. Ele representa o principal método de detecção de erros utilizado nas telecomunicações.

Princípio

O controle cíclico de redundância consiste em proteger blocos de dados, chamados frames (tramas). A cada trama é associado um bloco de dados, chamado código de controle (CRC). O código CRC contém dados redundantes no que diz respeito à trama, permitindo, não só detectar os erros, como também repará-los:

Controle de redundância cíclica (CRC)

O princípio do CRC consiste em tratar as sequências binárias como polinômios binários, polinômios cujos coeficientes correspondem à sequência binária. Por exemplo, a sequência binária 0110101001 pode ser representada como um polinômio, como mostrado abaixo:

0*X9 + 1*X8 + 1*X7 + 0*X6 + 1*X5 + 0*X4 + 1*X3 + 0*X2 + 0*X1 + 1*X0
ou seja:
X8 + X7 + X5 + X3 + X0
ou então:
X8 + X7 + X5 + X3 + 1

Desta maneira, a sequência de bits com menos peso (o bit mais à direita) representa o grau 0 do polinômio (X0 = 1), o 4º bit partindo da direita representa o grau 3 do polinômio (X3), e assim, sucessivamente. Logo, uma sequência de n- bits constitui um polinômio de grau máximo n-1. Todas as expressões polinomiais são manipuladas posteriormente utilizando um módulo 2.

Neste processo de detecção de erros, um polinômio predeterminado (chamado polinômio gerador e abreviado G (X)) é conhecido tanto pelo emissor quanto pelo receptor. O remetente, para iniciar o mecanismo de detecção de erros, executa um algoritmo nos bits da trama, de forma a gerar um CRC, e transmitir estes dois elementos ao destinatário. Para isso, então, basta que o destinatário efetue o mesmo cálculo para verificar a validade do CRC.

Aplicação prática

Digamos que M é a mensagem que corresponde aos bits da trama a ser enviada e M(X) é o polinômio associado. Suponhamos que M’ é a mensagem transmitida, por exemplo, a mensagem inicial à qual se concatena um CRC de n bits. O CRC é o seguinte: M’(X)/G(X)=0. Assim, o código CRC é igual ao resto da divisão polinomial de M(X) (X) (ao qual se anexou os n bits nulos que correspondem ao comprimento do CRC) entre G(X).

Por exemplo, tomemos a mensagem M com os seguintes 16 bits: 1011 0001 0010 1010 (chamado B1 em hexadecimal). Tomemos G(X) = X3 + 1 (representado no sistema binário por 1001). Sendo que G(X) é de grau 3, o resultado é adicionar a M 4 bits nulos: 10110001001010100000. O CRC é igual ao resto de M dividido por G:

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..
----..
1100.
1001.
----.
1010
1001
----
0011

Para criar M’ basta concatenar o CRC assim obtido com os bits da trama que vai ser transmitida:

M' = 1011000100101010 + 0011  
M' = 10110001001010100011

Assim, se o destinatário da mensagem dividir M’ por G, obterá um resto nulo se a transmissão ocorreu sem erros:

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

Polinômios geradores

Os polinômios geradores mais comuns são:


CRC-12: X12 + X11 + X3 + X2 + X + 1;
CRC-16: X16 + X15 + X2 + 1;
CRC CCITT V41: X16 + X12 + X5 + 1 (código utilizado principalmente no procedimento HDLC);
CRC-32 (Ethernet): = X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X + 1;
CRC ARPA: X24 + X23+ X17 + X16 + X15 + X13 + X11 + X10 + X9 + X8 + X5 + X3 + 1.

Error checking
Error checking
Verificación de errores
Verificación de errores
Die Fehlerkontrolle
Die Fehlerkontrolle
Contrôle d'erreur (CRC)
Contrôle d'erreur (CRC)
Il controllo degli errori
Il controllo degli errori
Última modificação: 6 de outubro de 2017 às 11:53 por Pedro.CCM.
Este documento, intitulado 'O controle de erros', está disponível sob a licença Creative Commons. Você pode copiar e/ou modificar o conteúdo desta página com base nas condições estipuladas pela licença. Não se esqueça de creditar o CCM (br.ccm.net) ao utilizar este artigo.