Detecção de erros

Quando estamos em ambientes ruidosos temos dificuldade em ouvir alguém que fale connosco, nas transmissões de dados, fenómenos como o ruído e as interferências também ocorrem, podendo deturpar a mensagem original. Devido a este problema são aplicados códigos de detecção e correcção de erros às transmições:

- Verificação de paridade

- Checksum

- CRC (Cyclic Redundancy Check)

Verificação de paridade

O bit de paridade indica o número de bits 1 presentes num carácter (byte). Assim diz-se que a paridade é par se tiver um número par de 1' se ímpar caso tenha número ímpar de 1's. Assim, este assume o bit 0 quando temos paridade par e 1 quando temos paridade ímpar. Vejamos os exemplos:

11001100 - A mensagem está correcta. O último bit é zero indicando que o número de 1's que o precede é par (4 uns).

10101011 - A mensagem está errada. O byte teria assim de ser retransmitido visto o bit de paridade dizer que o número de 1's é ímpar e no entanto é par (4 uns).

Exercício prático: Das sequências de bits que se seguem, assinale em qual/quais ocorreram erro, sabendo que o último bit é um bit de paridade.

a)11100111110101011 - sem erro

b)10101011110001001 - com erro

c)10101000000001001 - com erro

Checksum

São técnicas utilizadas para detectar erros principalmente na internet e denominam-se somas de verificação. Se a soma de checksums (normal e complemento para um) resultarem apenas 1's, podemos inferir que "não" houve erro na transmição, caso contrário, existiu erro na transmissão.

Exercício prático:

Indique qual o valor em binário a juntar a 2 byte (00111101 e 00001101) de informação para que estes sejam transmitidos com um código detector de erros do tipo checksum. Faça a verificação no recetor.

        00111101
+      00001101

        01001010

Como a soma tem de ser em complemento para um terá de inverter a sequência resultante da soma normal (zeros passam a uns e vice-versa).

Obtemos a seguinte sequência checksum: 10110101

Os dados enviados serão então: 001111010000110110110101, ou seja, os 2 bytes iniciais mais a sequência de checksum invertida.

Para verificar se ocorreram erros durante a transmissão, teremos de voltar a somar os dois byte de dados enviados e somar ao checksum invertido.

        10110101 -> Checksum invertido(da soma)

+      01001010 -> Resultado da soma

        11111111 -> Não há erros

Como todos os bites resultantes desta soma são 1, não existiu erro na transmição. No caso de algum desses bits ser diferente de 1, então nessa posição (de qualquer um dos bytes ou mesmo do código de checksum teria ocorrido um erro.)

CRC (Cyclic redundancy check)

Esta técnica é mais eficiente que as anteriores.

Muitas das vezes, também denominada por método de detecção polinomial. 

O método consiste em adicionar um conjunto de bits (FCS - Frame Check Sequence) à mensagem original a transmitir. Os bits FCS são calculados através da seguinte expressão:

FCS(x) é igual ao resto da divisão inteira entre duas funções polinomiais M(x) e G(x) onde M(x) é a nossa mensagem original sem código de erros e G(x) o polinómio gerado pré-definido.

Exercício Prático:

Seja  a mensagem a transmitir. Pretende-se calcular o FCS a adicionar a M(x) para que esta

M(x) = 1101011 

Vejamos:

Não nulas: Grau do expoente 6;5;3;1;0

Nulas: Grau do expoente 4;2

Assim, nas posições 6;5;3;1;0 , o valor é 1 e nas restantes posições é 0.

Para G(x) = 11001

Calcular o FCS - É o mesmo que realizar uma divisão aplicando uma divisão XOR

O resto não é mais do que FCS(x); isto é, a sequência de bits necessário a acrescentar a M(x).

M(x) + FCS = 1101011 1010