PTC29008: Projeto 1: Controle de erros

Próxima aula

• Implementação de Checksum
• Implementação de CRC em software
• CRC em hardware
• Implementação do CRC-16 para PPP (RFC 1662)
• A Painless Guide to CRC Error Detection Algorithms, 3rd Edition por Ross Williams
• Um pequeno resumo sobre CRC (obtido do livro Comunicação de Dados e Redes de Computadores, de William Stallings)
• Tabela de polinômios geradores para CRC

O controle de erros envolve:

1. Detecção de erros: cada mensagem recebida deve ter verificada a integridade de seu conteúdo. Mensagens corrompidas devem ser rejeitadas (descartadas)
2. Recuperação de erros: mensagens descartadas devido a erros podem ser recuperadas. Existem duas abordagens:
   • Correção de erros: mensagens incluem bits de redundância que possibilita, dentro de certos limites, corrigir bits corrompidos.
   • Retransmissão: mensagens descartadas são simplesmente retransmitidas

O protocolo de comunicação a ser desenvolvido no projeto 1 deve receber apenas mensagens corretas. Para isso, pelo menos deve ser implementada uma função de detecção de erros.

Detecção de erros

Durante uma transmissão. uma mensagem pode ser corrompida, pois bits podem ter seus valores invertidos ou serem mesmo suprimidos. Para ter uma ideia da chance disso ocorrer, deve-se tomar como base a taxa de erro de bit do canal de comunicação, apelidada de BER (Bit Error Rate). Assim, se BER é a probabilidade de um bit sofrer um erro, a probabilidade de um quadro de tamanho F bits não sofrer erros é:

$P_{F}=(1-BER)^{F}$

Por exemplo se BER for $10^{-6}$, e F for 1500 bytes, a probabilidade de um quadro não ter erros é:

$P_{F}=(1-10^{-6})^{12000}=0.9881$

... o que não é muito bom: entre 1 e 2% dos quadros em média terão erros, uma taxa razoavelmente alta. Porém se BER for $10^{-10}$:

$P_{F}=(1-10^{-10})^{12000}=0.9999988$

... o que é bem melhor.

Essa análise mostra que erros de transmissão são possíveis. O protocolo de enlace deve ser capaz de detectá-los, para evitar desencapsular o conteúdo de um quadro comrrompido. Assim, ele facilita o trabalho de protocolos de camadas superiores. A detecção de erros implica adiciona à mensagem transmitida uma certa quantidade de bits de redundância. Os valores desses bits são determinados com base no conteúdo da mensagem. Na recepção, calcula-se novamente o valor dos bits de redundância e compara-se com os bits de redundância incluídos na mensagem. Se forem iguais, presume-se que mensagem está correta.

Bits de redundância para detecção de erros

A detecção de erros envolve basicamente a escolha de uma dentre duas técnicas:

• Checksum (soma de verificação): os bits de redundância são calculados como uma soma de todos os octetos da mensagem.
• CRC (verificação de redundância cíclica): os bits de redundância são calculados usando uma forma de álgebra polinomial.

CRC

A detecção de erros com CRC envolve realizar uma divisão entre os bits da mensagem e um certo padrão de bits. Essa divisão é feita em módulo 2, com operações XOR para subtração durante a divisão. Para fins de demonstração da validade dessa técnica, define-se:

• M: mensagem com n bits
• F: k bits de redundância a serem anexados à mensagem
• T: quadro a ser transmitido, contendo n+k bits
• P: padrão com k+1 bits a serem usados na divisão

Para começar, deseja-se que, na recepção, T/P não tenha resto, sendo que T é definido por:

$T=2^{k}M+F$

Para testar essa condição, primeiro faz-se a divisão de $2^{k}M$ por P:

$2^{k}M/P=Q+R/P$

... sendo Q o quociente e R o resto da divisão. Sendo uma divisão binária, R tem no mínimo 1 bit a menos que P. Usa-se R como os bits de CRC:

$T=2^{k}M+R$

Agora deve-se testar se usar R como bits de CRC satisfaz a condição de T/P ter resto zero:

$T/P=(2^{k}M+R)/P=Q+R/P+R/P$

Como qualquer número somado a si próprio em aritmética de módulo 2 é zero, o resultado pode ser escrito assim:

$T/P=(2^{k}M+R)/P=Q+(R+R)/P=Q$

... e assim não há resto !

Atividade

1. Analise e escolha uma das técnicas para detecção de erros para seu protocolo.
2. Implemente a técnica escolhida.

Exemplo da classe Enquadramento com métodos para cálculo e verificação de CRC baseados no código de referência da RFC 1662 (protocolo PPP)

#ifndef FRAMING_H #define FRAMING_H #include <cstdint> #include "Serial.h" class Enquadramento { public: Enquadramento(Serial & dev, int bytes_min, int bytes_max); ~Enquadramento(); // envia o quadro apontado por buffer // o tamanho do quadro é dado por bytes void envia(char * buffer, int bytes); // espera e recebe um quadro, armazenando-o em buffer // retorna o tamanho do quadro recebido int recebe(char * buffer); private: int min_bytes, max_bytes; // tamanhos mínimo e máximo de quadro Serial & porta; char buffer[4096]; // quadros no maximo de 4 kB (hardcoded) enum Estados {Q0, Q1, Q2}; // bytes recebidos pela MEF até o momento int n_bytes; // estado atual da MEF int estado; // aqui se implementa a máquina de estados de recepção // retorna true se reconheceu um quadro completo bool handle(char byte); // verifica o CRC do conteúdo contido em "buffer". Os dois últimos // bytes desse buffer contém o valor de CRC bool check_crc(char * buffer, int len); // gera o valor de CRC dos bytes contidos em buffer. O valor de CRC // é escrito em buffer[len] e buffer[len+1] void gen_crc(char * buffer, int len); // calcula o valor de CRC dos bytes contidos em "cp". // "fcs" deve ter o valor PPPINITFCS16 // O resultado é o valor de CRC (16 bits) // OBS: adaptado da RFC 1662 (enquadramento no PPP) uint16_t pppfcs16(uint16_t fcs, char * cp, int len); }; #endif

DICA: CRC16 em Python

Existem módulos Python para cálculo de CRC, tais como PyCRC e crcmod. No entanto, é difícil acertar os parâmetros para que eles calculem os mesmos valores de CRC que a versão do algoritmo da RFC 1662 (CRC do PPP). Sendo assim, foi implementada uma classe para calcular CRC16 que segue fielmente o algoritmo dessa RFC. Essa classe está contida no módulo crc:

• Módulo crc para Python3

Abaixo segue a descrição dessa classe gerada com pydoc:

    class CRC16(builtins.object)
     |  Classe CRC16: calcula e verifica FCS cm base no algoritmo 
     |  de CRC descrito na RFC 1662 (PPP)
     |  
     |  Methods defined here:
     |  
     |  __convert__(self, data)
     |      Converte os dados para um objeto bytes
     |  
     |  __init__(self, data=b'')
     |      data: contém os dados para calcular o FCS. Armazena esses 
     |      dados em um bufer interno. Deve ser um objeto str, bytes ou 
     |      bytearray
     |  
     |  calculate(self)
     |      Calcula o valor do FCS (sem o complemento de 1 ao final)
     |  
     |  check_crc(self)
     |      Verifica o valor de FCS contido nos dados armazenados no buffer interno
     |  
     |  gen_crc(self)
     |      Gera o valor de FCS (com complemento de 1). Retorna um objeto 
     |      bytes com o os dados seguidos do valor de FCS (LSB e depois MSB)
     |  
     |  update(self, data)
     |      Acrescenta mais dados ao buffer interno
     |  
     |  clear(self)
     |      Limpa o buffer interno
     |

Um exemplo de uso dessa classe pode ser visto a seguir:

#!/usr/bin/python3

import crc

fcs = crc.CRC16('Mensagem Transmitida')
msg = fcs.gen_crc()
print('Mensagem com FCS:', msg)

fcs.clear()
fcs.update(msg)
print('Resultado da verificação da mensagem com FCS:', fcs.check_crc())

msg=msg[:-1]
fcs.clear()
fcs.update(msg)
print('Resultado da verificação da mensagem com FCS após modificá-la:', fcs.check_crc())