O controle de erros

Julho 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 barulhos), 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: seja instalando um meio de transmissão mais seguro, isto é, uma camada de proteção física. Geralmente, uma conexão tradicional tem uma taxa de erro entre 10/05 e 10/07. Seja 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 adicionar (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á sistema 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 de controle de redundância longitudinal ou Longitudinal Redundancy Check, - LRC) 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 de redundância cíclico

O controle de redundância cíclico (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 de redundância cíclico consiste em proteger blocos de dados, chamados frames (tramas). A cada trama é associado um bloco de dados, chamado código de controle (CRC ou FCS - Frame Check Sequence, no caso de um código de 32 bits). 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
(Este 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

Veja também


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: 3 de julho de 2017 às 13: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.