Trabalho de pesquisa 2

Deteção e correção de erros em transmissões digitais

Tipos de erros

• Todas as vezes que uma cadeia de bits flui de um ponto a outro de uma rede de computadores, eles ficam sujeitos a alterações imprevisíveis por causa das interferências;
• Essas interferências podem modificar as características do sinal;
• Em um erro de bit, um 0 passa a ser 1 e um 1 passa a ser 0;
• Por exemplo, uma rajada de 1/100s de ruídos impulsivos em uma transmissão com taxa de dados de 1.200bps poderia alterar todos os 12 bits de informação ou parte deles.

Erro de bit (Single Bit Error)

• O termo erro de bit significa dizer que apenas 1 bit de determinada unidade de dados (por exemplo, um byte, caractere ou pacote) foi alterado de 1 para 0 ou de 0 para 1;
• A próxima figura mostra o efeito do erro de bit sobre uma unidade de dados, para compreender o impacto desse problema, imagina que cada grupo de 8 bits seja caractere ASCII com um bit 0 adicionado à esquerda;
• Na imagem que se segue o caractere 00000010 (ASCII STX) foi enviado, significando o início do texto, mas foi recebido 00001010 (ASCII LF), que significa o avanço de linha:

• Os erros de bit são do tipo de erro de menos probabilidade de ocorrência em uma transmissão de dados serial, imagine que os dados são enviados a 1Mbps. Isso significa que a duração de cada bit é de apenas 1/100000s, ou seja, 1µs, o que é muito raro na prática. Normalmente os ruídos duram muito mais que isso.

Erros em rajada (Burst Error)

• O termo, erro em rajada, significa dizer eu 2 ou mais bits foram corrompidos na unidade de dados;
• A imagem seguinte ilustra o efeito do erro em rajada sobre uma unidade de dados, observe que um erro em rajada não significa que os erros ocorram em bits consecutivos. O comprimento da rajada é medido do primeiro bit corrompido até ao último, pode ser que alguns bits entre eles não tenham sido corrompidos:

Redundância

• O conceito mais importante na deteção e correção de erros é a redundância:
• Para sermos capazes de detetar ou corrigir erros precisamos que sejam enviados alguns bits extras redundantes junto com os dados:
• Esses bits redundantes são acrescentados pelo emissor e posteriormente retirados pelo receptor:
• A sua presença possibilita que o recetor detete ou corrija bits corrompidos.

Redundância cíclica (CRC)

• Caracterizado por ser de boa eficiência, que funciona basicamente em cima de uma concordância polinomial gerador “G(x)”, que quanto maior o grau deste G, maior a eficiência desse método para detectar um erro. Deixamos claro que neste polinômio, o bit de maior e menor ordem devem obrigatoriamente ser iguais a 1.
• Seguindo o exemplo: 
• Palavra inicial: 10110001, o polinômio p(x) é igual aos bits da palavra inicial somada com bits de paridade, além disso, deve ser divisível pelo polinômio gerador G(x), ou seja, deve dar resto “0”, caso não dê indica que houve erro.
• Quando ocorre um erro, para detetar, este método faz com que o receptor receba T(x)+E(x) em vez de receber o polinômio T(x) apenas, destacando que cada bit “1” em E(x) corresponde um bit inverso e,pegando T(x) e dividir por G(x) o resultado será sempre “0”.
• Observando o exemplo: tendo a mensagem com bits 10111011, é calculado o polinômio do gerador, utilizando a fórmula: G(x) = x4 + x + 1 resultando em 10011, conforme a mensagem já citada e, para enviar ao receptor é adicionado nessa mensagem ainda a quantidade de zeros determinado pela equivalência do grau do gerador G(x), ficando como: 10111011 0000. Logo em seguida é feita a divisão da mensagem original sem os zeros do gerador com o polinômio gerador utilizando a operação XOR, ou seja: 101110110000 / 10011
• No fim desta divisão sobra resto 01111, que é adicionado à mensagem original ficando: 101110111111, e é aqui, com este código a mais, que se detecta se houver erro, pois no receptor é novamente calculado este mesmo resto e caso não de o mesmo resultado é detetado e avisado o erro.

Método de paridade

• O método de paridade também é considerado ineficiente, porém é o mais utilizado na detecção de erros.
• Este método não tem segredo algum, é fácil de entender. Ele consiste em ser adicionado, pelo transmissor, um bit de redundância (bit de paridade) após ou antes da seqüência de bits que pertence à mensagem. Esse bit adicionado segue a seguinte regra:
• caso apareça o bit “1” número impar de vezes é adicionado 1, exemplo: 0100101 paridade = 1;
• caso apareça o bit “1” número par de vezes é adicionado 0, exemplo: 01001010010100, paridade =0 
• Por exemplo a letra H na mensagem “Hello world” é dado, em bits, por: 100001. Em seguida, o bit de paridade é calculado e depois enviado: 100001x, ou seja, existem dois bit “1” então o seu bit de paridade é par, adicionando bit de paridade “0”, sendo enviado: 10000010. No receptor, esse calcula a paridade da mensagem enviada com o bit de paridade x adicionado, observa que x = paridade então determina mensagem correta.
• Em caso de erro, vamos citar um exemplo. Há o envio do bit “00101”, sendo o primeiro “0” como o bit de paridade, porém o receptor recebe o seguinte código: “00001”, ou seja, o circuito de verificação de paridade percebe que há apenas um único “1”, isto é impar, então é detetado o erro.

Checksum

• Este método é muito simples e fácil de compreender, consiste em transmitir todas as palavras junto com o resultado da soma dos bits delas. Vamos trabalhar em cima de um exemplo para compreender:
• Dado os dados iniciais de duas palavras de 8 bits: 00111101 00001101, estes valores são somados dando resultado ao checksum: 01001010. 00111101+00001101 = 01001010 -> Checksum 10110101 -> Checksum invertido
• O emissor envia o checksum invertido ao receptor. De seguida, como o próprio nome desse método já diz, no receptor as palavras são novamente somadas e comparadas com checksum que foi enviado, ou seja, verificar a soma.
• Para a detecção de algum erro, se em qualquer dos dados transmitidos terem algum erro irá ser descoberto, pois no receptor é recalculado e ocorre a soma do novo checksum com o checksum enviado que terá um resultado diferente de “1”.
• Exemplo de uma transmissão sem algum erro: 01001010 MAIS 10110101 = 11111111 Onde 01001010 representa novo Checksum, que representa as palavras recebidas, 10110101 representa checksum enviado(Invertido) e 11111111 indica que não ocorreu erro.

Códigos de hamming

• Nesse método basicamente funciona com o envio de uma mensagem em códigos de 7 posições de bits que são numerados da esquerda para a direita e começando com “1”. Porém tem suas regras e especificações como, os bits que são potência de 2 vão ser bits 2n, já os outros é preenchido com bits com a mensagem que será transmitida.
• É feita a conversão das posições que são diferentes de 2n e valor igual a “1”, ficando na posição 3 e 7 respectivamente, 011 e 111. Pegando estes valores e aplicando OR exclusivo ou conhecido também como XOR, dá origem às 3 primeiras posições da mensagem: “0 0 1”.
• Em seguida é inserido os valores obtidos nas posições do bit de paridade, por fim sendo enviada a mensagem: “0011001”.
• Para detectar se há erro ou não, é aplicado novamente o XOR aos valores obtidos e se o resultado for igual a 0 é que não houve erro na transmissão, mas se for diferente indica que há erro, e para descobrir a posição onde está o erro é converter o resultado obtido para decimal.
• Exemplo sem erro: 0011001
• Posição: 3- 011; 4-100, 7-111. 011 XOR 100 = 111 111 XOR 111 = 000
• Exemplo com erro: 0001001
• Posição: 4-100; 7-111 100 XOR 111 = 011-> indica erro na posição 3

Correção de erros

• Os métodos descritos acima são suficientes para determinar se houve ou não um erro na transmissão de uma mensagem. Mas nas maiorias das vezes isto não é suficiente. As mensagem têm que ser recebidas sem erros e o mero conhecimento de que existiu um erro não chega. É preciso determinar exatamente qual foi o erro e depois corrigi-lo. Veja o exemplo:
• "Se faltarm algmas letrs consguims entndr a mensgm".
• Apesar de alterada, é possível entender o que a mensagem está dizendo. Obviamente, se a alteração for maior, não iremos entendê-la. Por exemplo:
• "S as rs sg tn mns".

Pedido automático de repetição 

(ARQ - Automatic repeat request)

• Utiliza a repetição como método de correcção de erros em tramas. O receptor informa o emissor de que não ocorreram erros na transmissão no trama, enviando um aviso de recepção (ACK). Se depois de um tempo o emissor não tiver recebido essa ACK, significa que o bloco possuía erros. Então o bloco é enviado de novo até que exceda um certo número de repetições de envio, ou até que a ACK seja recebida.

Auto-correctores (ECC - error-correcting code)

• É um código no qual cada sinal de dados está em conformidade com regras específicas de construção. Os desvios dessas regras podem ser detectados e corrigidos. Esta técnica é normalmente usada em armazenamento de dados no computador (por exemplo: memória flash) e em transmissões de dados.
• Ele faz uso de um aumento significativo da informação de controle para corrigir o erro. Por isso eles são usados somente em situações específicas em que não haja outra alternativa, por exemplo numa transmissão "Simplex" (unidirecional). Se houver erro este mecanismo irá recorrer a um ou mais esquemas de detecção referidos anteriormente para saber exatamente em que bit (que varia entre 1 ou 0) está o erro para inverter esse bit.
• Alguns códigos podem detectar e corrigir um certo número de bits de erros. Se apenas corrigirem um erro, são chamados códigos de correcção de erro único, ou SEC - single error correcting, e os que conseguem detectar dois erros são chamados de detecção de erro duplo, ou DED - double error detecting.