Embed Size (px)
Citation preview
ANDERSON ANTONIO DE REZENDE
CARACTERÍSTICAS E BASE ESTRUTURAL DOS MÉTODOS DE
CRC UTILIZADOS EM SISTEMAS DE COMUNICAÇÃO DIGITAL
PARA DETECÇÃO DE ERROS
PARACATU, 2015
FACULDADE DO NOROESTE DE MINAS – FINOM CENTRO BRASILEIRO DE EDUCAÇÃO E CULTURA – CENBEC
GRADUAÇÃO EM ENGENHARIA DE TELECOMUNICAÇÕES
ANDERSON ANTONIO DE REZENDE
CARACTERÍSTICAS E BASE ESTRUTURAL DOS MÉTODOS DE
CRC UTILIZADOS EM SISTEMAS DE COMUNICAÇÃO DIGITAL
PARA DETECÇÃO DE ERROS
Monografia apresentada como requisito parcial para obtenção de título de Bacharel em Engenharia de Telecomunicações da Faculdade do Noroeste de Minas - FINOM.
Orientador (a): Prof. Esp. Ledson Reis Branquinho
Co-orientadora: Profª. Msc. Rosa Jussara Bonfim Silva
PARACATU, 2015
FACULDADE DO NOROESTE DE MINAS – FINOM CENTRO BRASILEIRO DE EDUCAÇÃO E CULTURA – CENBEC
GRADUAÇÃO EM ENGENHARIA DE TELECOMUNICAÇÕES
Dedico este trabalho primeiramente a Deus, pelas oportunidades e objetivos que me permitiu alcançar, durante toda minha trajetória. Em especial à minha família, a minha esposa Daiana Cássia e ao meu filho Miguel Henrique, que nascerá ainda no final deste ano, nos dando uma nova razão para viver.
AGRADECIMENTOS
Agradeço primeiramente a Deus por ter nos presenteado com a graça de
estarmos vivos, além de ter iluminado meus passos e me dado condições de lutar e
alcançar mais uma conquista. Agradeço especialmente aos meus pais Manoel e
Isaura, as minhas irmãs Silvana e Simone e a minha esposa Daiana Cássia, por toda
paciência, compreensão, apoio e incentivos prestados, os quais foram de fundamental
importância para superação das barreiras e adversidades encontradas durante essa
caminhada.
Deixo ainda o meu muito obrigado aos amigos, colegas de turma, a todos os
professores e ex-professores pelos conhecimentos partilhados, dedicação,
persistência, convívio e apoio prestados antes e durante o desenvolvimento deste
curso. Agradeço, em especial, ao meu orientador Ledson Branquinho e co-orientadora
Rosa Jussara, pelo acompanhamento e ensinamentos transmitidos, essenciais para
edificação e concretização desta obra.
RESUMO:
Este trabalho abordou as Características e a Base Estrutural dos Métodos de CRC utilizados em Sistemas de Comunicação Digital para Detecção de Erros. Os códigos baseados em CRC, se utilizam de uma lógica matemática poderosa, o qual através de uma pequena quantidade de bits redundantes, possui a capacidade de detectar erros múltiplos e simples em mensagens com milhares de bytes de extensão. A metodologia presente na pesquisa pode ser classificada como qualitativa e experimental, pois objetivamente buscou explorar e demonstrar a importância da verificação da integridade dos pacotes de bits, através da implementação de códigos baseados em CRC, como método de controle de erro. Também foi elaborado um circuito eletrônico em interface gráfica de simulação ISIS do software Proteus 8, para exemplificação e análise da detecção de erro, através de programas baseados em CRC, desenvolvidos no compilador MikroC PRO for PIC. Mediante a realização deste trabalho pôde-se concluir que, devido ao alto grau de confiabilidade e eficiência, os métodos de CRC são amplamente utilizados em diversos padrões e protocolos de redes de computadores e que a capacidade de detecção de erros desses códigos, está estritamente ligada ao verificador, ou seja, ao polinômio gerador em que o sistema se baseou.
Palavras-chave: CRC. Verificação de Redundância Cíclica. Códigos cíclicos. Detecção de erro.
ABSTRACT:
This work addressed the feature and structural basis of CRC methods used in Digital Communication Systems Error Detection. The CRC codes based on use a powerful mathematical logic, which through a small number of redundant bits, has the ability to detect single and multiple errors in messages thousands bytes in length. This research methodology can be classified as qualitative and experimental, as objectively sought to explore and demonstrate the importance of bit frames of the health check through the implementation of CRC-based codes such as error control method. It was also designed an electronic circuit in graphic software Proteus ISIS simulation interface 8, for exemplification and analysis of error detection through programs based on CRC, developed in MikroC PRO compiler for PIC. Through this work it could be concluded that due to the high degree of reliability and efficiency, the CRC methods are widely used in several patterns and computer networking protocols and error detection capacity of these codes is closely linked the verifier, that is, the generator polynomial in which the system is based on.
Keywords: CRC. Cyclic Redundancy Check. Cyclic Codes. Error Detection.
LISTA DE TABELAS
TABELA 1 – Representação polinomial de strings binárias ............................. 28
TABELA 2 – Ou exclusivo. ............................................................................... 29
TABELA 3 – Polinômios de CRC comuns. ....................................................... 31
TABELA 4 – Tabela de estados dos registradores de deslocamento no processo
de divisão para obtenção do FCS no lado do transmissor. .............................. 37
LISTA DE FIGURAS
FIGURA 1 – Modelo do sistema de comunicação de dados de Shannon .... 16
FIGURA 2 – Paridade Par . ............................................................................. 21
FIGURA 3 – Matriz de paridade par bidimensional .......................................... 24
FIGURA 4 – Paridade par bidimensional ....................................................... 24
FIGURA 5 – Cálculo do total de verificação do código polinomial .................... 30
FIGURA 6 – Codificador e decodificador CRC ................................................. 34
FIGURA 7 – Divisão polinomial de um bloco de dados no transmissor e receptor
de um canal para detecção de erros baseado em CRC. ................................. 35
FIGURA 8 – LFSR ............................................................................................ 36
FIGURA 9 – Frame IEEE 802.3 ..................................................................... 40
FIGURA 10 – Tx e Rx CRC-5 em plataforma ISIS ........................................... 42
FIGURA 11 – Tx CRC-5 em plataforma ISIS ................................................... 43
FIGURA 12 – Sistema deturpador do Sinal ...................................................... 45
FIGURA 13 – Rx CRC-5 em plataforma ISIS ................................................... 46
FIGURA 12 – Algoritmo do Sistema Transmissor CRC-5 ................................ 48
FIGURA 13 – Algoritmo do Sistema Receptor CRC-5 ..................................... 49
LISTA DE ABREVIATURAS E SIGLAS
ARES - Advanced Routing and Editing Software
ARQ - Automatic-Repeat Request
ASCII - American Standard Code for Information Interchange
ATM - Asynchronous Transfer Mode
BSC - Binary Sinchronous Communication
CDMA - Code Division Multiple Access
CRC - Cyclic Redundancy Checking
DVB - Digital Video Broadcast
FCS - Frame Check Sequence
GPS - Global Positioning System
HDLC - High-level Data Link Control
IBM - International Business Machines
IEEE - Institute of Electrical and Electronics Engineers
ISIS – Intelligent Schematic Input System
ITU - International Telecommunication Union
LCD – Liquid Crystal Display
Led – Light Emitting Diode
LFSR - Linear Feedback Shift Register
LRC- Longitudinal redundancy check
MHz – Megahertz
PCB – Printed Circuit Board
PIC - Periferal Interface Controler
SCD - Sistemas de Comunicação de Dados
TDMA - Time Division Multiple Access
UDP - User Datagram Protocol
VRC - Vertical Redundancy Check
SUMÁRIO:
INTRODUÇÃO ............................................................................................... .11
1 COMUNICAÇÃO DIGITAL ........................................................................... 14 2 SISTEMA DE COMUNICAÇÃO DE SHANNON ........................................... 16 3 CÓDIGOS DE CONTROLE DE ERROS ....................................................... 19 3.1 Códigos Detectores de erros .................................................................. 20 3.1.1 Paridade Unidimensional......................................................................... 22 3.1.2 Paridade Bidimensional ........................................................................... 23 3.1.3 Soma de verificação ................................................................................ 25 4 MÉTODO CRC DE DETECÇÃO DE ERRO .................................................. 27 4.1 Fundamentos dos códigos CRC ............................................................. 27 4.1.1 Representação Polinomial ....................................................................... 27 4.1.2 Aritmética de módulo 2 ............................................................................ 28 4.1.3 Da divisão em módulo 2 .......................................................................... 29 4.1.4 Do Polinômio Divisor ............................................................................... 31 4.2 Lógica funcional do código CRC ............................................................ 32 4.2.1 Codificação e Decodificação CRC .......................................................... 32 4.2.2 Registradores de Deslocamento ............................................................. 36 4.3 Fatores limitantes e aplicações de métodos de CRC ........................... 38 4.3.1 Da Capacidade de Detecção CRC .......................................................... 38 4.3.2 Aplicações ............................................................................................... 39 5 PROJETO EXPERIMENTAL CRC-5 ............................................................ 41 5.1 Do Circuito de Simulação em Plataforma ISIS ....................................... 41 5.1.1 Estrutura do Transmissor ........................................................................ 42 5.1.2 Estrutura de deturpação do sinal ............................................................. 44 5.1.3 Estrutura do receptor ............................................................................... 45 5.2 Da elaboração dos códigos em MikroC .................................................. 46 CONSIDERAÇÕES FINAIS ............................................................................. 51 REFERÊNCIAS ................................................................................................ 52 APÊNDICE 1: Codificador CRC-5 .................................................................. 54 APÊNDICE 2: Decodificador CRC-5 .............................................................. 59
11
INTRODUÇÃO:
Os sistemas de comunicação são considerados um dos mais importantes
pilares na evolução da humanidade, refletindo na formação de um mundo cada vez
mais globalizado. A evolução desses sistemas fez com que desafios fossem
superados e distâncias encurtadas, resultando em eficientes meios de comunicação
e de acesso a informação.
Devido a facilidade e a eficiência que as tecnologias nos proporcionam, a
população mundial está cada vez mais dependente da utilização dos sistemas
modernos de comunicação para desempenhar os mais variados tipos de atividades,
tais como: a utilização dos aparelhos de GPS para se locomover, dos sistemas
Netbank para controle de finanças, da utilização rastreadores em automóveis, de
equipamentos automação e de segurança residencial, dentre outros (REBELLATO,
2010).
Grande parte das tecnologias utilizadas atualmente, se comunicam através de
sinais digitais, isto é, produzem informação em uma forma descontínua e que é melhor
descrita por números. Para a transferência de dados em um Sistema de Comunicação
Digital (SCD), os arquivos compostos por uma larga extensão bits, são particionados
em unidades menores denominadas pacotes de bits. Contudo, assim como ocorre nos
sistemas analógicos, os sistemas digitais apesar de maior imunidade, também estão
susceptíveis aos efeitos de ruídos e interferências de naturezas diversas. Estes efeitos
podem ocasionar erros e corromper os dados enviados em questão, causando mal
funcionamento ou invalidação total para utilização ou reprodução dos arquivos
estruturados.
Neste contexto, conforme Young (2006), a grande vantagem oferecida pelos
SCDs, é que estes permitem a implementação de mecanismos de controle de erros,
que de forma limitada, tem por finalidade superar esse tipo de problema.
Considerando a evolução dos SCD, cuja a tendência se volta para a transferência de
fluxo de bits em velocidades cada vez maiores, é indispensável a implementação dos
códigos de controle de erro, a fim de se garantir a eficiência destes sistemas.
Diante do exposto, faz-se necessário a realização de estudos científicos
aprofundados, em relação à aplicabilidade e funcionamento, de códigos de controle
de erro. Em meio a esse universo contextual, o objetivo central deste trabalho
científico consistiu em explorar analiticamente a importância da verificação da
12
integridade dos pacotes bits, através da implementação de códigos baseados em
CRC (Cyclic Redundancy Check), como métodos de detecção de erros utilizados em
sistemas de comunicação digital. Para esse propósito, de maneira específica, serão
analisadas as vantagens e desvantagens da utilização de códigos de detecção
aplicados ao controle de erro, assim como os pilares característicos e fatores
limitantes que regem os códigos de CRC.
O método científico pode ser resumido em um conjunto de técnicas e
procedimentos necessários para atingir um determinado fim ou resultado desejado.
Neste contexto, faz-se necessário a classificação específica do método de pesquisa
a ser utilizado, pois em âmbito geral as pesquisas podem estar relacionadas aos mais
diversos objetos, assim como, podem possuir diferentes objetivos (GIL, 2010;
LAKATOS; MARCONI, 2010).
Assim, quanto a ao objetivo e a abordagem, esta pesquisa classifica-se como
exploratória e qualitativa, respectivamente. Pois sua fundamentação teórica,
estruturou-se mediante uma revisão da literatura realizada por meio de um
levantamento bibliográfico através de pesquisas em capítulos de livros, sites e artigos
científicos publicados em português pertinentes ao assunto abordado. Nesse sentido,
este estudo buscou aprofundar de forma explícita, clara e descritiva, o processamento
lógico e a base estrutural de um código CRC.
Dessa forma, em relação à temática abordada, o primeiro capítulo descreve os
fundamentos da comunicação digital. Dentre eles, são apresentados os principais
fatores que fomentam a transição de sistemas de comunicação analógicos em direção
a digitalização e a crescente utilização de técnicas de comunicação digital na maioria
dos serviços de telecomunicações. No segundo capítulo é apresentado o sistema de
comunicação de Shannon, enfatizando as funções do bloco codificador e decodificar
de canal em meio aos demais blocos. Já o terceiro capítulo retrata importância da
aplicação de códigos de controle de erros em SCD, além de ser feita uma análise
sistémica relacionada à classe dos códigos detectores de erro. No quarto capítulo
apresenta-se as bases funcionais, peculiaridades e limitações dos métodos CRC de
detecção de erro, sendo esse o escopo principal do trabalho.
De acordo com Gil (2010, p. 32):
A pesquisa experimental constitui o delineamento mais prestigiado nos meios científicos. Consiste essencialmente em determinar um objeto de estudo,
13
selecionar as variáveis capazes de influenciá-lo e definir as formas de controle e de observação dos efeitos que a variável produz no objeto.
A pesquisa experimental permite um esboço mais conceituado dos meios
científicos de uma pesquisa, logo que possibilita a definição de um objeto de estudo,
e a seleção de incertezas que podem influenciá-los, assim como descreve as formas
de controle e de observação das consequências que as variáveis causam no objeto.
(GIL, 2010).
Neste contexto, quanto ao procedimento, este trabalho também pode ser
classificado como uma pesquisa experimental, pois no quinto capítulo será abordado
o projeto intitulado pelo autor de CRC-5, o qual teve seus códigos desenvolvidos
através do software MikroC PRO for PIC, para simulação e análise em um circuito
estruturado com microcontroladores em plataforma ISIS do software Proteus 8.
14
1 COMUNICAÇÃO DIGITAL
A Comunicação Digital é baseada na transmissão de informação através de
símbolos. Nos dias atuais existe uma infinidade de tecnologias que se comunicam
através de sinais digitais, isto é, produzem informação em uma forma descontínua e
que é melhor descrita por números (RUSCHEL, 1996).
Os dados neste contexto são essencialmente os dígitos binários, zero e um, e, portanto, podem ser considerados como uma forma de representação da informação. A informação é gerada a partir de uma fonte de informação, que gera um fluxo de símbolos de informação. Esses símbolos podem ser codificados segundo dígitos binários e a seguir associados a símbolos elétricos, podendo ser propagados através de um meio até um destinatário. O destinatário, ao receber os símbolos elétricos, associa dígitos binários aos mesmos com base no mesmo código do transmissor e, desta forma, recupera os símbolos de informação enviada pela fonte (ROCHOL, 2012. p.2).
Segundo RUSCHEL (1996), para o envio de informações através de um
sistema de transmissão digital é necessário que esta seja representada por sinais
elétricos, por exemplo, o valor lógico "1' representado por um pulso de tensão positivo
+V e o valor lógico “0" representado por um pulso de tensão negativo -V, ou seja,
símbolos que representam os dígitos zero e um e que podem ser substituídos ao longo
do sistema por outros símbolos, por exemplo um seno e um cosseno, sem que o
conteúdo da informação digital seja alterado.
A comunicação digital, não se restringe apenas à transmissão de informações
originadas em formato digital, pois sinais analógicos como voz, áudio e vídeo, podem
ser digitalizados, através da teoria da amostragem, de maneira em que se adequem
a um padrão de transmissão digital. A modernização e migração de tecnologias
baseadas em sistemas analógicos para sistemas digitais é um fator que cresce
exponencialmente, pois esta transição implica em uma comunicação de maior
qualidade e fluxo de transmissão de dados (JEZENSKY, 2004; RUSCHEL, 1996).
Na transmissão de qualquer sinal sempre existe a degradação oriunda de
interferências adversas. Dentre as muitas vantagens obtidas por sistemas de
comunicação digital podemos destacar maior imunidade ao ruído, pois em um
receptor de sinal digital, pelo fato de que o sinal a ser transmitido e o ruído serem de
naturezas diversas, permite que o receptor distinga o sinal de informação mesmo
quando este sofra uma distorção considerável. Já no receptor de sinal analógico, o
sinal enviado e o ruído presente no canal de transmissão podem se misturar a ponto
15
de serem tratados como um único sinal e devido ambos serem de mesma natureza,
não há meios do receptor distinguir um do outro (RUSCHEL, 1996).
De acordo com PIMENTEL (2007), a evolução dos sistemas analógicos em
direção à digitalização e a crescente utilização de técnicas de comunicação digital na
maioria dos serviços de telecomunicações, pode ser explicada por vários motivos,
dentre os quais se destacam:
Facilidade de regeneração do sinal digital. A utilização de repetidores
regeneradores permite a recuperação perfeita do sinal transmitido, exceto por
alguns erros que podem ser controlados no projeto do sistema;
Incorporação de técnicas de processamento digital de sinais, por exemplo a
aplicação de códigos corretores de erro na codificação do canal, que resultam
em uma maior imunidade ao ruído;
Possibilita a utilização de métodos criptográficos, a fim de preservar integridade
da informação;
Flexibilidade de alternância entre taxas de transmissão, que os diferentes tipos
de sinais digitais (voz, vídeo, dados) quando em natureza de símbolos binários,
podem ser tratados e manipulados;
Permite diferentes garantias de Grau de Serviço; em que pode-se especificar
prioridades;
Possibilidade de implementação de várias técnicas de multiplexação, tais como
TDMA e CDMA, visando a economicidade e eficiência do canal;
Implementação em Circuito Digital VLSI (baixo custo e ocupação de espaço);
Baixo consumo de potência.
Nos Sistemas Digitais, o fato da transmissão ser baseada em símbolos, ou seja,
em geral na base binária, permite o emprego de técnicas computacionais para a
recepção e o tratamento destes sinais. Genericamente denominadas de
Processamento Digital de Sinais, estas técnicas viabilizam a implementação de
filtragens, para o tratamento de interferências e ruídos, além da possibilidade de
inserção de sistemas detectores e corretores de erros. Devido ao avanço tecnológico,
cada vez mais estas técnicas têm sua complexidade desenvolvida com base em
softwares que operam em dispositivos compactos, como em microcontroladores,
tendência que reflete na eliminação de grandes estruturas de hardwares complexos e
que os tornam cada vez mais compactos (RUSCHEL, 1996).
16
2 SISTEMA DE COMUNICAÇÃO DE SHANNON
Os sistemas de comunicações digitais apresentam como característica
principal o fato de se limitarem a um conjunto finito de mensagens a serem
transmitidas através de um canal. Abaixo, a Figura 1 demonstra os principais blocos
funcionais que compõem um sistema de comunicação de informação. O modelo
adotado para nossa análise foi proposto pela primeira vez pelo matemático e
engenheiro eletrônico Claude Elwood Shannon no ano de 1948. Este modelo, ainda
nos tempos atuais, é tido como referência tanto para o desenvolvimento como para a
análise dos modernos sistemas de comunicação de dados (SCD) (ROCHOL, 2012).
Figura 1: Modelo do sistema de comunicação de dados de Shannon Fonte: (ROCHOL, 2012, p. 3)
Como podemos observar, no modelo do sistema de comunicação proposto por
Shannon, também conhecido como um sistema ponto-a-ponto de comunicação de
informação, os blocos superiores indicam o processamento da informação da fonte
até o modulador, enquanto os blocos inferiores indicam o processamento de sinais no
receptor até o destino. É importante ressaltar que outros blocos funcionais podem
existir em sistemas práticos e dependendo do tipo de aplicação e tecnologia, alguns
blocos são facultativos e suas sequências de operações podem ser trocadas
(PIMENTEL, 2007; ROCHOL, 2012).
De acordo com o SCD de Shannon, no sentido da transmissão, os blocos
constituintes se iniciam pela fonte de informação, cuja a função é descrita a seguir:
17
A fonte de informação emite símbolos discretos. Quando a fonte for de natureza analógica, como, por exemplo, sinais de voz, vídeo, assumiremos que os procedimentos de digitalização de sinais convertem a saída da fonte em uma sequência de símbolos discretos. Uma fonte discreta é caracterizada por um alfabeto, por uma taxa de informação (em símbolos por segundo) e por uma distribuição de probabilidade de emissão de sequências de símbolos (PIMENTEL, 2007, p.1).
No bloco seguinte a fim de reduzir a redundância contida na informação a ser
transmitida, entra em cena o codificador de fonte, que converte uma sequência de
símbolos de informação em uma sequência de símbolos codificados. Uma
transmissão eficiente consiste na representação de uma sequência de símbolos da
fonte em uma sequência binária usando o menor número de bits possível, que possa
atender a exploração de todas probabilidades necessárias. Ainda no codificador de
fonte, há a possibilidade de manipulação criptográfica que permite a transmissão de
informação de forma sigilosa e torna a informação incompreensível àqueles
destinatários não autorizados a recebê-la (PIMENTEL, 2007).
Já no codificador de canal a informação codificada anteriormente no codificador
de fonte é fracionada de acordo com o com o comprimento limitante do pacote de bits,
que varia de sistema para sistema, em seguida, através de códigos detectores ou
corretores de erros, é introduzida uma redundância de maneira controlada nesta
sequência de símbolos à sua saída, de tal forma que o decodificador de canal usará
esta redundância para controlar erros oriundos dos efeitos de ruídos e distorções
causados durante a passagem do sinal transmitido pelo canal de comunicações. O
objetivo principal do codificador do canal é garantir a integridade da mensagem e
aumentar confiabilidade da transmissão (JEZENSKY, 2004).
Após os dados serem processados pelo codificador de canal, são
encaminhados para a modulação. De acordo com Pimentel (2007, p. 2):
Como o canal de comunicação é de natureza analógica, o modulador mapeia uma sequência de símbolos na sua entrada em uma sequência de formas de onda (sinais) adequada para transmissão pelo canal. O projeto do modulador envolve a escolha de vários parâmetros, como, por exemplo, o formato e a duração das formas de onda e a potência média transmitida.
Os sinais emitidos pelo modulador propagam por um canal ruidoso, até serem
captados pelo sistema receptor, onde o demodulador efetuará o mapeamento inverso,
baseado no utilizado pelo modulador, para assim determinar a sequência de símbolos
discretos que serão encaminhados ao decodificador de canal. Cabe ressaltar que,
18
devido as distorções sofridas pelo sinal transmitido no canal ruidoso, é praticamente
impossível se obter no demodulador uma réplica exata do sinal transmitido. Estas
distorções são oriundas de sinais interferentes de naturezas diversas, conhecidas
genericamente como ruídos. Sendo assim, um sistema receptor de sinal digital não
tem como objetivo reproduzir a forma de onda transmitida com precisão, mas sim de
processar o sinal recebido baseado em uma caracterização estatística e decidir,
dentro de um conjunto finito, qual a sequência de formas de onda transmitida
(PIMENTEL, 2007).
No decodificador do canal, a sequência recebida é processada através de
algoritmos que se utilizam da redundância introduzida, com a finalidade de detectar
e/ou corrigir erros, buscando aferir a integridade dos dados transmitidos. A síntese
sequencial de bits resultante do processo anterior é enviada ao decodificador de fonte,
que reinsere a redundância originalmente removida pelo codificador de fonte, com a
finalidade de reproduzir os dados provenientes da fonte o mais fidedignamente
possível ao destinatário final (PIMENTEL, 2007).
19
3 CÓDIGOS DE CONTROLE DE ERROS
Todos os sistemas de comunicações em pequenas ou altas proporções, estão
sujeitos a perturbações causadas pela ação do ruído presente no canal. Este efeito
pode ocasionar a ocorrência de erros nas mensagens que são recebidas por um
sistema receptor. Genericamente são chamados de erros aleatórios, quando este tipo
de incidência ocorre de maneira esporádica e independente; já quando ocorrem em
surtos, ou seja, em sequência de vários erros consecutivos, são denominados erros
em rajadas (ALENCAR, 2007).
Como a previsão e eliminação total do ruído é algo praticamente impossível, os
sistemas de comunicação devem ser projetados com mecanismos que possibilitem a
recuperação de dados perdidos, durante o processo de transferência. Estes
mecanismos, são baseados primordialmente, na identificação de um quadro recebido
com erro, para que em seguida entre em execução as demais providências
necessárias, que variarão de acordo com as características e aplicações do sistema
em questão (SOARES; LEMOS; COLCHER, 1995).
Desta forma, visando atingir uma maior confiabilidade do sistema, utiliza-se o
bloco codificador do canal, cuja a principal função é a aplicação de códigos de controle
de erros, que são métodos que buscam superar os efeitos de ruídos e interferências,
presentes de forma degenerativa no canal de transmissão. Estes códigos se
originaram de técnicas baseadas na introdução de redundância a mensagem a ser
enviada, de forma que o receptor através de processamentos lógicos consiga
identificar e aplicar uma medida de tratamento, caso o sinal recebido estiver sido
corrompido (JESZENSKY, 2004; ROCHOL, 2012; YOUNG, 2006).
Quem primeiro se preocupou de forma sistemática com esse assunto foi Richard Wesley Hamming (1915-1998). Em 1950, ele publicou, no Bell System Technical Journal de abril, um trabalho com o título de: Error Detecting and Error Correcting Codes, que pode ser considerado a primeira sistematização teórica sobre detecção e correção de erros (ROCHOL, 2012, p. 249).
A partir da década de 60, devido ao crescimento acelerado dos Sistemas de
Comunicações Digitais (SCD), o desenvolvimento de técnicas e parâmetros para o
tratamento de erros tornou-se um fator emergente (ROCHOL, 2012).
20
As técnicas empregadas para o controle de erros podem ser classificadas em
dois grupos principais: detecção e correção. Nas técnicas de correção de erros, é
adicionado a mensagem original uma quantidade suficiente de redundância, para que
no receptor, o decodificador seja capaz de identificar se a mensagem recebida foi
corrompida a ponto de conter erros, e possa corrigir estes erros e recuperar a
mensagem original. Já os códigos baseados em técnicas de detecção de erros, o
codificador do canal adiciona redundância apenas para que o receptor deduza se
houve o erro, mas sem identificar qual, e em seguida, caso o sistema possua algum
mecanismo ARQ (Automatic-Repeat Request), solicite automaticamente uma
retransmissão (TENENBAUM, 2003; YOUNG, 2006).
Conforme Peterson e Davie (2004, p.70):
A princípio, parece que a correção é sempre melhor, pois com a detecção somos forçados a abandonar a mensagem e, em geral, pedir a transmissão e outra cópia. Isso utiliza largura de banda e pode introduzir latência enquanto se espera a retransmissão. Porém, existe uma desvantagem na correção: ela geralmente exige um número maior de bits redundantes para enviar um código de correção de erros tão forte (ou seja, capaz de lidar com o mesmo intervalo de erros) quanto um código que só detecta erros. Assim, embora a detecção de erro exija o envio de mais bits quando os erros são encontrados, a correção de erro exige o envio demais bits o tempo todo.
Nesse contexto, podemos perceber que a decisão de optar-se entre a
implementação de um método de detecção ou correção de erros, é algo a ser
analisado minunciosamente. Sendo assim, deve-se levar em consideração a
quantidade de bits redundantes, por bits de informação, que se pretende enviar por
quadro; além da probabilidade de erro que o sistema estará suscetível, de acordo com
suas características limitantes, dentre outros fatores.
3.1 Códigos Detectores de erros
Eventualmente, durante a transmissão de dados em um SCD, devido a ações
deturpadoras do sinal, tais como ruído térmico ou interferências elétricas, são
introduzidos erros nos quadros de bits. Sendo assim, por mais que em alguns
sistemas, como em enlaces ópticos, esta incidência seja consideravelmente baixa,
faz-se necessário a utilização de algum mecanismo detector de erros, que opere
juntamente com uma ação corretiva (PETERSON; DAVIE, 2004).
21
De acordo com Young (2006, p.379), “uma forma de superar os efeitos de ruído
e interferência no sistema de transmissão de dados, além de aumentar a potência
transmitida, é detectar a ocorrência de erros e obter uma retransmissão[...]”.
Nesse contexto, os métodos de detecção de erros utilizam-se do acréscimo de
bits redundantes, processados de forma lógica e incorporada a mensagem a ser
enviada, de forma que o sistema receptor ao receber a mensagem utilizará de um
algoritmo que através destes dados adicionais, poderá identificar se a mensagem foi
recebida integra ou corrompida (PETERSON; DAVIE, 2004).
Já a retransmissão se resume em enviar uma notificação ao sistema emissor,
identificando e solicitando que o quadro adulterado seja retransmitido. Sendo assim,
se o enlace em questão, tiver sido instalado e configurado respeitando as limitações
do sistema, e os erros de bits tiverem ocorrendo de forma esporádica, será alta a
probabilidade da cópia reenviada ser recebida livre de erros (PETERSON; DAVIE,
2004).
É o que ocorre em um SCD constituído apenas por um código detector de erros,
e que possua um mecanismo ARQ, ou seja, quando o receptor detecta algum erro em
um bloco de bits recebido, este devolve uma mensagem curta ao sistema emissor;
através de um percurso de retorno, ou seja, um canal de realimentação; solicitando
uma retransmissão do quadro de bits em questão (HAYKIN; MOHER, 2008; YOUNG,
2006).
De acordo com Tenenbaum (2003, p. 205-206):
Em canais altamente confiáveis, como os de fibra, é mais econômico utilizar um código de detecção de erros e simplesmente retransmitir o bloco defeituoso ocasional. Porém em canais com enlaces sem fio que geram muitos erros, é melhor adicionar a cada bloco redundância suficiente para que o receptor seja capaz de descobrir qual era o bloco original, em vez de confiar em uma retransmissão, que pode ela própria conter erros.
Dessa forma, podemos constatar que os códigos corretores de erros, são mais
indicados para sistemas de comunicação em que erros sejam muito prováveis, pois
apesar desses códigos necessitarem de maior quantidade de bits de redundância e
de processamento, se comparados aos códigos detectores, a necessidade de
retransmissão contínua poderia introduzir uma alta latência, a ponto de inviabilizar o
sistema. Já os códigos detectores de erro, juntamente com os mecanismos ARQ,
possuem melhor desempenho para enlaces cabeados, pois esses sistemas
apresentam baixas taxas de erro. Sendo assim, consequentemente, a necessidade
22
de retransmissão de uma mensagem corrompida seria eventualmente baixa
(PATERSON; DAVIE, 2004; TENENBAUM, 2003).
De acordo com Rochol (2012, p.254), “Existem duas grandes classes de
técnicas de detecção de erros: as técnicas baseadas em paridade e as técnicas
baseadas em códigos cíclicos”. Dentro deste contexto, nas subseções a seguir, serão
abordadas de forma breve as técnicas de paridade linear e bidimensional, que são
considerados métodos primitivos, porém pioneiros, que ainda em tempos atuais são
utilizados em alguns protocolos para a detecção de erros. Já no Capítulo 4, serão
explorados de forma aprofundada, os fundamentos e características funcionais dos
métodos de CRC, os quais são largamente empregados em protocolos de
comunicação de redes de computadores.
3.1.1 Paridade Unidimensional
De acordo com o contexto histórico, as técnicas de paridade foram as primeiras
técnicas a serem desenvolvidas e utilizadas em SCD. Sendo que devido sua
simplicidade, ainda são largamente utilizados em protocolos de comunicação
baseados em caracteres, tais como os protocolos BSC-1 e BSC-3 (Binary
Sinchronous Communication) da IBM (ROCHOL, 2012).
O método de paridade unidimensional, baseia-se em acrescentar um único bit
de redundância a um bloco composto por n bits. Sendo que este bit deve ser escolhido
e adicionado ao bloco, de forma a obter um resultado par da soma da quantidade de
caracteres 1 (caso o sistema opere em paridade par); ou resultado ímpar (caso o
sistema opere em paridade ímpar), como demonstra a Figura 2 (SOARES; LEMOS;
COLCHER, 1995).
Figura 2: Paridade Par Fonte: Elaborado pelo autor
23
Em SCD, pode-se entender como erro, quando o nível de consistência do
ruído/interferência presente no canal, se torna consideravelmente alto a ponto de
distorcer o sinal recebido, ocasionando a inversão de somente um ou vários bits.
Neste contexto, conforme Kurose e Ross (2006, p. 333):
A operação do receptor também é simples com único bit paridade. O receptor precisa apenas contar quantos '1' há nos d +1 bits recebidos. Se, utilizando o esquema de paridade par, for encontrado um número ímpar de bits e valor 1, o receptor saberá que ocorreu pelo menos um erro de bit. Mais precisamente, ele saberá que ocorreu algum número ímpar de erros de bit.
A paridade unidimensional é um método bastante simples, com a capacidade
de detectar todos os erros em um determinado bloco, caso ocorram em quantidades
ímpares. Porém, ao mesmo tempo, baseia-se em um código relativamente fraco, pois
caso ocorra algum erro, que inverta uma quantidade par de bits, o receptor não teria
a capacidade de detectá-lo. Sendo assim, em um sistema suscetível a erros em
rajadas, a probabilidade de detectar erros consistiria em apenas 0,5, proporção que
não é muito aceitável (TENENBAUM, 2003; YOUNG, 2006).
3.1.2 Paridade Bidimensional
A paridade bidimensional também se trata de um método simples, sendo esta,
uma técnica derivada da paridade de bloco único, contudo, possui melhor eficiência,
devido sua maior capacidade de detecção de erros.
A lógica estrutural aplicada neste método, pode ser melhor descrita por
Tenenbaum (2003, p. 209), quando nos fala que:
As disparidades poderão ser consideravelmente melhoradas se cada bloco for enviado como uma matriz retangular com n bits de largura e k bits de altura [...] Um bit de paridade é calculado separadamente para cada coluna e afixado à matriz como sua última linha. Em seguida a matriz é transmitida uma linha de cada vez.
A Figura 3, demostra de maneira simples, como pode ser interpretada a
matriz de paridade bidimensional, para o processamento dos bits de paridade,
referentes ao bloco de verificação, o qual é afixado como última linha da matriz. Do
ponto de vista prático, primeiramente deve ser processado o bit de paridade que será
adicionado ao final de cada pacote, gerando uma última coluna, denominada de
24
verificação de redundância vertical (VRC - Vertical redundancy check). Posteriormente
são processados são calculados os bits de paridade para cada coluna, incluindo os
da coluna VRC, que integrarão um último pacote de verificação, geralmente intitulado
de verificação de redundância longitudinal (LRC- Longitudinal redundancy check), ou
paridade horizontal. Após tais procedimentos, os dados já estarão codificados e
prontos para envio (YOUNG, 2006).
Figura 3: Matriz de paridade par bidimensional Fonte: Elaborado pelo autor.
Assim como todo código de tratamento de erros possui suas peculiaridades e
limitações, com método de paridade bidimensional não é diferente. E por mais que se
enquadre na classe de códigos detectores, este possui a capacidade de correção de
erro, caso a degradação atinja um único bit.
Figura 4: Paridade par bidimensional Fonte: KUROSE; ROSS, 2006, p.334.
25
Como pode ser observado na Figura 4, quando ocorre um erro que atinge
somente um dos bits do bloco, é possível mapeá-lo. Neste contexto, conforme Young
(2006, p.381), “a interseção da fila e da coluna com erro de paridade é a localização
do bit incorreto. Obtém se a correção simplesmente invertendo o bit com problemas”.
Em relação a adulteração de bits, devido a inserção de erros pelo ruído
presente no canal de transmissão, Kurose e Ross (2006, p. 333-334 grifos dos
autores), nos diz que: “[...] medições demonstraram que, em vez de acontecerem
independentemente, os erros frequentemente se aglomeram em 'rajadas' ”.
Sendo assim, se tratando das limitações, os códigos baseados em paridade
bidimensional ainda podem detectar mais não corrigir, qualquer combinação de erro
duplo em determinado pacote. Em relação a um bloco por inteiro e sendo n a
quantidade de bits em sentido horizontal deste bloco, ou seja, o tamanho do pacote
de bits, o método ainda possibilita a detecção de erros de uma única rajada de
tamanho n, pois desta forma, se interpretarmos a estrutura deste bloco recebido, no
sistema receptor, como uma matriz, verificaríamos que um surto dessa proporção
alteraria somente um bit por coluna. No entanto, uma rajada de tamanho maior que n,
comprometeria a capacidade de detecção do sistema, pois o bloco estaria suscetível
a erros duplos em linhas e colunas com a possibilidade de não serem detectados.
Assim a capacidade de identificação de um bloco corrompido consistiria em apenas
50% de probabilidade de detecção (TENENBAUM, 2003; YOUNG, 2006).
3.1.3 Soma de verificação
Uma das técnicas de bastante destaque utilizada em comunicação de dados,
também pertencentes a classe de detecção de erro, é o método de soma de
verificação, mais conhecido como Checksun. Conforme Kurose e Ross (2006), é o
método de codificação utilizado em protocolo UDP (User Datagram Protocol –
Protocolo de Datagrama de Usuário), sendo mais especificamente aplicado na
camada de transporte.
A soma de verificação também se trata um método simples, o qual devido não
ser o escopo deste trabalho não será aprofundada. De maneira resumida, a
codificação baseada em Checksun, consiste primeiramente em somar uma
determinada quantidade de palavras de código que se pretende transmitir, sendo que
26
em seguida são enviadas as palavras de código em questão juntamente com o
resultado dessa soma. Após os dados serem encaminhados ao sistema receptor, é
realizado o mesmo cálculo em cima dos pacotes recebidos, sendo em seguida o
resultado comparado com a soma de verificação recebida. Se caso algum dado tenha
sido adulterado, incluindo os da soma de verificação, os resultados não combinarão,
permitindo que o sistema identifique que ocorreu um erro e que a mensagem está
corrompida (PETERSON; DAVIE, 2004).
27
4 MÉTODO CRC DE DETECÇÃO DE ERRO
Atualmente, as utilizações de técnicas de controle de erro em sistemas de
comunicações digitais são praticamente indispensáveis, a fim de se garantir a
eficiência durante a troca de informação entre dispositivos. Neste contexto,
principalmente os projetos baseados em algoritmos de detecção de erro, tem como
objetivo maximizar a probabilidade de detectar quadros ou blocos de bits corrompidos,
utilizando uma quantidade mínima de bits redundantes (PATERSON; DAVIE, 2004).
Como vimos, as técnicas de paridade são bastante restritas e pouco eficientes,
principalmente relacionadas à necessidade de detecção de erros múltiplos. Assim,
dentre as várias técnicas utilizadas para a detecção de erro, iremos analisar os
métodos de verificação de redundância cíclica CRC (Cyclic Redundancy Checking),
que se destacam pela sua simplicidade e capacidade de detecção (ROCHOL, 2012;
SOARES; LEMOS; COLCHER, 1995).
Os códigos baseados em CRC, se utilizam de uma lógica matemática bastante
poderosa, o qual através de uma pequena quantidade de bits redundantes, possui a
capacidade de detectar erros múltiplos e simples em mensagens com milhares de
bytes de extensão. Por este motivo, são amplamente utilizados em diversos padrões
e protocolos de redes de computadores, juntamente com estratégias de solicitação de
repetição automática ARQ, consistindo em fortes e eficientes sistemas de controle de
erros (KUROSE; ROSS, 2006; HAYKIN, 2004).
4.1 Fundamentos dos códigos CRC
Os códigos CRC também são denominados de códigos polinomiais, uma vez
que é possível considerar um sequencial de bits, como um polinômio de coeficientes
0 e 1. Neste contexto, de acordo com Kurose e Ross (2006), as operações
matematicamente lógicas, empregadas neste método, são baseadas na aritmética
polinomial. Sendo seus fundamentos descritos nas subseções a seguir.
4.1.1 Representação Polinomial
De acordo com o que foi mencionado anteriormente, nas operações baseadas
em CRC, uma cadeia de bits pode ser melhor representada de forma polinomial.
28
Dessa forma, as palavras de código (sequências de bits), também podem ser
interpretadas e representadas por polinômios constituídos por potências de x e com
coeficientes 0 e 1, de acordo com a posição dos bits da cadeia em questão (ROCHOL,
2012).
Seguindo esta lógica, Tenenbaum (2003, p.209) nos diz que:
Os códigos polinomiais se baseiam no tratamento de strings de bits como representações de polinômios com coeficientes 0 e 1. Um quadro de k bits é considerado a lista de coeficientes para um polinômio com k termos, variando desde xk-1 até a x0. Dizemos que tal polinômio é de grau k-1. O bit de mais alta ordem (mais à esquerda) é o coeficiente xk-1; o bit seguinte é o coeficiente de xk-2 e assim por diante.
Assim, uma mensagem binária de n bits, pode ser convertida em um polinômio
de ordem n – 1, como pode ser observado no quadro de exemplos abaixo:
Tabela 1: Representação polinomial de strings binárias. Fonte: Elaborado pelo autor.
M(x) = 10101 = 1.x4 + 0.x3 + 1.x2 + 0.x1 + 1.x0 = x4 + x2 + 1
M(x) = 1100101 = 1.x6 + 1.x5 + 0.x4 + 0.x3 + 1.x2 + 0.x1 + 1.x0 = x6 + x5 + x2 + 1
M(x) = 1011100 = 1.x6 + 0.x5 + 1.x4 + 1.x3 + 1.x2 + 0.x1 + 0.x0 = x6+ x4 + x3 + x2
Diante ao exposto, do ponto de vista matemático, podemos então imaginar uma
transmissão de dados digitais, como sendo, uma troca de polinômios entre um
emissor e um receptor (PATERSON; DAVIE, 2004).
4.1.2 Aritmética de módulo 2
A aritmética polinomial empregada em códigos CRC, baseia-se na soma de
módulo 2. Sendo assim, durante o cálculo de processamento dos bits representados
de forma polinomial, não há transporte para adição e nem empréstimos para
subtração. As comparações bit a bit são equivalentes a operadores XOR (ou
exclusivo), derivados da álgebra booleana, conforme a tabela abaixo (KUROSE;
ROSS, 2006, p. 332; TENENBAUM, 2003).
29
Tabela 2: Ou exclusivo. Fonte: Elaborado pelo autor.
Tabela XOR (ou exclusivo)
A B A # B
0 0 0
1 0 1
0 1 1
1 1 0
Neste contexto, quando somamos duas palavras de código, utilizando
aritmética de módulo 2, praticamente estamos aplicando o operador lógico XOR de
forma concomitante, de acordo com cada nível das cadeias binárias em questão.
Consequentemente, as operações adição e subtração acabam se tornando idênticas,
ou seja, produzem o mesmo resultado (ROCHOL, 2012). Por exemplo:
101000011 101000011 + 101100111 − 101100111 000100100 000100100
4.1.3 Da divisão em módulo 2
A divisão de módulo 2, empregada na codificação CRC, segue princípios
diferentes aos da divisão binária simples, começando pelo fato, de que no
procedimento de subtração aplica-se a aritmética de módulo 2, sendo assim, não
existe elevação ou empréstimo, por parte do bit de grau ligeiramente superior ao bit
em questão. De acordo com Peterson e Davie (2004), a realização deste tipo de
divisão polinomial, pode ser efetuada respeitando as seguintes propriedades:
Qualquer polinômio B(x), pode ser dividido por um polinômio C(x), se B(x)
possuir grau maior, ou igual, ao polinômio divisor C(x);
Obedecendo a condição anterior, para efetuar a subtração do polinômio B(x)
por C(x), basta realizar a operação XOR para cada par de coeficientes de
acordo com o grau correspondente.
Por exemplo, vamos analisar, poderíamos dividir em módulo 2 o polinômio
M(x)= x4 + x2 + 1 (10101), pelo polinômio D(x) = x4 + x3 (11000)? E a resposta é sim,
ou seja, por mais que o polinômio D(x) esteja relacionado a um valor decimal maior
30
que o polinômio M(x), ambos são de mesmo grau obedecendo as premissas citadas
anteriormente. Assim, realizando a divisão, através da operação XOR bit a bit, entre
o dividendo M(x) e o divisor D(x), obteríamos como resto da divisão o polinômio x3 +
x2 +1 (1101), conforme esboço abaixo.
De acordo com Tenenbaum (2003, p.209-210), “a divisão longa é efetuada do
mesmo modo que em binário, exceto pelo fato de a subtração ser de módulo 2, [...]”.
Dessa forma, a divisão longa em módulo 2, consiste em emparelhar o divisor ao
dividendo, realizando as operações XOR e processando a “queda” dos bits de forma
sequencial, até que divisor apresente grau maior que o dividendo, fator que implicará
no termino da operação e na obtenção do resto da divisão, como pode ser observado
na Figura 5.
Figura 5: Cálculo do total de verificação do código polinomial Fonte: TENENBAUM, 2003, p. 211.
31
4.1.4 Do Polinômio Divisor
Em códigos de CRC, o polinômio divisor, também conhecido como polinômio
gerador, é um dos pilares mais importantes e intimamente ligado a eficiência e a
capacidade detecção de erros de um sistema. De acordo com Peterson e Davie
(2004), a escolha do polinômio divisor G(x) deve ser baseada em certos critérios, a
fim de minimizar a probabilidade de divisibilidade exata de mensagens passivas de
erros; buscando atingir a maximização da capacidade de detecção para os tipos mais
comuns de erros, de acordo com as condições do sistema.
Neste contexto, é possível detectar os seguintes tipos de erros, se G(x) tiver
sido selecionado obedecendo as respectivas características indicadas abaixo
(PATERSON; DAVIE, 2004; ROCHOL, 2012):
Todos os erros de um único bit, desde que os coeficientes do termo mais
significativo e o menos significativo de G(x) sejam diferentes de zero;
Todos os erros duplos de bit, desde que G(x) seja constituído por pelo menos
três termos de coeficientes iguais a 1;
Qualquer quantidade ímpar de erros, desde que G(x), tenha x+1 como fator;
Qualquer rajada de erro de tamanho menor que k bits, além da maioria das
rajadas de erros com mais de k bits (sendo o valor de k equivalente ao grau de
G(x)).
Se tratando de redes de computadores, seis versões de polinômios geradores
são mais difundidos entre padrões e protocolos. Como exemplo, podemos citar as
redes Ethernet que utilizam CRC-32 e as redes ATM (Asynchronous Transfer Mode),
que utilizam CRC-8, CRC-10 e CRC-32. A tabela abaixo, demonstra os termos que
compõem estes dentre outros polinômios divisores (PATERSON; DAVIE, 2004).
Tabela 3: Polinômios de CRC comuns. Fonte: PETERSON; DAVIE, 2004, p.70.
CRC G(x)
CRC-8 x8 + x2 + x + 1
CRC-10 x10+ x9 + x5 + x4 + x + 1
CRC-12 x12 + x11 + x3 + x2 + 1
CRC-16 x16 + x15 + x2 + 1
CRC-CCITT x16 + x12 + x5 + 1
CRC-32 x32+ x26 + x23 + x22 + x16+ x12 + x11 + x10 + x8+ x7 + x5 + x4 + x2+ x + 1
32
4.2 Lógica funcional de códigos CRC
O método CRC é uma das técnicas mais difundidas e largamente utilizadas em
SCD, não somente por consistir em um poderoso algoritmo para verificação da
integridade dos dados transmitidos, mas também pela sua simplicidade de
implementação tanto em hardware, quanto em software via programação. Sendo
assim, será abordada a seguir, as bases lógicas sequenciais que regem a codificação
e decodificação de códigos de CRC.
4.2.1 Codificação e Decodificação CRC
De acordo com o conteúdo apresentado na seção anterior, sabemos que as
cadeias de bits a serem processadas e transmitidas através de códigos cíclicos,
podem ser representadas de forma polinomial. E será no contexto polinomial e binário,
que analisaremos a lógica aplicada aos códigos de CRC.
Como fator primordial para a comunicação entre um sistema transmissor e um
sistema receptor implementados com um código de CRC, ambos devem concordar
com um mesmo polinômio gerador G(x), composto por r+1 bits e obviamente de ordem
r. Como regra, o bit de ordem superior e inferior deste polinômio gerador devem ser
iguais a 1, a fim de se garantir a detecção de todos os erros de um único bit
(TENENBAUM, 2003).
No transmissor consideremos uma cadeia de m bits, sendo o bloco de bits
M(x), a ser codificado e enviado; este bloco será de ordem polinomial m+1 bits e
obrigatoriamente deve ser maior que G(x). Para a codificação e cálculo dos bits de
verificação, o bloco M(x) deverá ser multiplicado por xr, processo que corresponde em
praticamente acrescentar r zeros a direita de M(x). Em seguida, o próximo passo
consiste em dividirmos M(x). xr pelo polinômio divisor G(x), através da divisão longa
em modulo 2. Sendo que, ao final da divisão, obteremos o resto, também denominado
de Frame Check Sequence (FCS) (ROCHOL, 2012).
De acordo Tenenbaum (2003, p.210):
Em qualquer problema de divisão, se você subtrair o resto do dividendo, o resultado será divisível pelo divisor. Por exemplo, na base 10, se você dividir 210.278 por 10.941, o resto será 2.399. Subtraindo-se 2.399 de 210.278, o resultado final (207.879) será divisível por 10.941.
33
À vista deste raciocínio, o passo seguinte consiste em subtrairmos (em módulo
2) do polinômio M(x). xr, o resto obtido no procedimento anterior. Fenômeno que
resultará em um polinômio T(x) = M(x).xr − FCS, exatamente divisível por G(x). Dessa
forma, a mensagem resultante T(x), estará codificada e pronta para ser enviada ao
sistema receptor (TENENBAUM, 2003).
Segundo Peterson e Davie (2004), ao subtrairmos o FCS de M(x).xr, estamos
apenas realizando a operação XOR entre o resto e os r bits zeros acrescentados à
direita de M(x), de acordo com o procedimento inicial. Outro fato relevante a ser
citado, se refere ao processo de codificação, pois devido a adição e a subtração em
módulo 2 possuir resultados idênticos, algumas literaturas nos dirá que devemos
somar o FCS ao polinômio M(x).xr, ao invés de subtraí-lo, para obtenção da
mensagem codificada T(x).
Após codificado, o bloco de dados T(x) (composto por bits de informação e por
bits de redundância), é enviado ao sistema receptor, através de um canal de
transmissão. Sendo que, ao receber o bloco dados T(x)’, inicia-se o processo de
decodificação por parte do receptor, o qual irá dividi-lo em módulo 2 por G(x), para
que assim possa se efetuar a verificação. Se o resultado obtido pela divisão der resto
nulo, o sistema poderá concluir, baseado em uma alta probabilidade, que a mensagem
chegou de forma integra; caso contrário, poderá constatar que a mensagem chegou
corrompida. Após a verificação e constatação da integridade bloco recebido, obtêm-
se a mensagem original, descartando os últimos r bits, que foram adicionados a M(x)
durante a codificação (ROCHOL, 2012).
Conforme pode ser observado no esquema da Figura 6, o método CRC é
estruturado com base em um polinômio divisor, o qual é empregado tanto no sistema
emissor, para geração dos bits redundantes, posteriormente anexado ao bloco;
quanto no sistema receptor para verificação da integridade dos blocos recebidos.
Assim, a ideia principal da codificação CRC, consiste em planejar que um polinômio
M(x), concatenado com r bits redundantes processados de maneira lógica, seja
exatamente divisível por G(x).
34
Figura 6: Codificador e decodificador CRC. Fonte: FOROUZAN; MOSHARRAF, 2013, p.384.
Seguindo o exemplo contido em Rochol (2012) e conforme fundamentos
teóricos de Tenenbaum (2003), é possível resumirmos de forma sequencial, as
principais etapas que regem um algoritmo CRC. A fim de fixarmos com clareza a lógica
aplicada à esses códigos, tomaremos como exemplo uma mensagem
M(x)=1010001101, a ser codificada no transmissor e verificada no receptor por um
polinômio gerador G(x)=110101. Sendo assim, após a definição do polinômio divisor,
as principais etapas consistem em:
1. Sendo r o grau de G(x), igual a 5 para o caso em questão; multiplica-se o
polinômio M(x) por xr, a fim de se obter M(x). xr, procedimento equivalente à
acrescentar r zeros a direita de M(x), com a finalidade de prepara-lo para
divisão e de dar espaço pra acrescentar os bits de verificação.
2. Aplica-se a divisão polinomial de módulo 2 de M(x). xr por G(x). Obtendo-se o
FCS, como podemos observar na figura abaixo.
35
Figura 7: Divisão polinomial de um bloco de dados no transmissor e receptor de um canal para detecção de erros baseado em CRC. Fonte: ROCHOL, 2012, p.256.
3. Subtraia (ou some), em módulo 2 o FCS de M(x).xr; procedimento que
consistirá na formação do quadro codificado T(x), divisível por G(x), a ser
transmitido pelo meio. De acordo com exemplo, obteríamos como resultado o
polinômio T(x)=101000110101110.
4. Após a transmissão do quadro codificado T(x)= M(x). xr + FCS, o receptor irá
dividi-lo em módulo 2 pelo mesmo divisor G(x). Se o resto da divisão for:
Igual a zero, o sistema entenderá que a mensagem terá chegado integra
ao receptor, sendo em seguida descartados os r bits referentes ao FCS,
para sintetização dos bits de informação;
Diferente de zero, o sistema constatará que a mensagem recebida está
corrompida, descartando-a por completa.
Vale lembrar que, caso haja a detecção de erro em um sistema que possua
algum mecanismo ARQ, será solicitada a retransmissão do respectivo quadro
corrompido, através de um canal de realimentação. Outro fato relevante a ser citado,
é que o quociente da divisão não possui utilidade em métodos CRC, sendo este termo
descartado, ou melhor, desconsiderado para este tipo de código (YOUNG, 2006).
36
4.2.2 Registradores de Deslocamento
Se tratando da implementação e execução de códigos de CRC, os processos
relacionados a divisão em módulo 2, para obtenção ou verificação do FCS, geralmente
são feitos em tempo real, através de técnicas baseadas em circuitos digitais
sequenciais simples. Essas técnicas têm seu desenvolvimento fundamentado em
blocos funcionais conhecidos como LFSR (Linear Feedback Shift Register), e também
são implementadas em embaralhadores de bits utilizados, por exemplo, em circuitos
de modems e DVBs (Digital Video Broadcast), para geração de sequências
pseudoaleatórias de bits (ROCHOL, 2012).
Segundo Young (2006), geradores do tipo LFSR, quase sempre são
implementados em hardwares e basicamente são constituídos por registradores de
deslocamento seriais encadeados com pontos de realimentação do tipo XOR (ou-
exclusivo), como mostra a Figura 8.
Figura 8: LFSR. Fonte: ROCHOL, 2012, p.257.
A arquitetura LFSR também pode ser representada por uma notação
polinomial, em que a quantidade total n de registradores deslocamento, equivale a
ordem do polinômio gerador em questão. Já os coeficientes desse polinômio,
respeitando o padrão binário, também assumirão valores zero ou um, sendo que por
via de regra, adota-se coeficiente um para o primeiro termo, ou seja, o menos
significativo que é tido como termo independente; para os termos relacionados as
posições dos registradores que antecedem as saídas interligadas aos pontos de
realimentação XOR e também para o ultimo termo (xn), relacionado a saída do
registrador de índice mais significativo, o qual irá convolucionar com os demais
37
operadores XOR, durante o ciclo de geração e deslocamento sequencial de bits,
conforme pode ser observado na Figura 8 (PETERSON; DAVIE, 2004; ROCHOL,
2012).
Em um código CRC composto por arquitetura LFSR, no transmissor, para o
processo de obtenção FCS, os registrados de deslocamento são inicializados em
zero. Em seguida, são deslocados, respeitando os pontos de realimentação XOR, os
bits de informação, seguidos de r bits zero, sendo r a ordem do polinômio divisor G(x)
empregado. Como pode ser observado Tabela 4, que exemplifica os valores que os
registradores (baseados no LFSR da Figura 8) assumirão, de acordo com o
processamento do deslocamento.
Tabela 4: Tabela de estados dos registradores de deslocamento no processo de divisão para obtenção do FCS no lado do transmissor. Fonte: ROCHOL, 2012, p.258
Dessa forma, só após o deslocamento de M(x). xr, será extraído o conteúdo
dos registradores o FCS a ser enviado ao final da mensagem. Sendo assim,
principalmente para operações em tempo real, as configurações de processamento
devem ser precisamente ajustadas, a fim de forma a transmitir um quadro contínuo de
bits de informação, juntamente com os bits de redundância.
O sistema receptor deverá concordar em uma arquitetura LFRS baseada no
mesmo polinômio divisor empregado ao transmissor, sendo que de forma análoga ao
38
processamento de codificação, ao receber a mensagem, composta por bits de
informação seguidos de bits de redundância, também os submeterão aos
registradores de deslocamento. Assim, se após o processamento, todos os
registradores apresentarem valores iguais a zero, o sistema entenderá que os dados
foram recebidos íntegros, caso contrário, se algum dos registradores apresentarem
valores diferentes de zero, o sistema detectará a mensagem como corrompida
(YOUNG, 2006).
4.3 Fatores limitantes e aplicações de métodos de CRC
Os métodos CRC são largamente utilizados em padrões de comunicação da
camada de enlace, devido sua alta capacidade de detecção de erro. Porém, conforme
já foi mencionado anteriormente, nenhum código tem o poder de detectar 100% das
combinações possíveis de erro, em um determinado sistema. Assim, por mais forte
que seja um código e por mais baixa que seja a probabilidade, existem combinações
de erros que passariam despercebidas por um sistema verificador, sendo este, um
fator denominado como taxa residual de erros (ROCHOL, 2012).
Nesse contexto, a subseção a seguir, tem por objetivo abordar os fatores
limitantes, relacionados a capacidade de detecção de erros, que regem os códigos de
CRC. Ainda nesta seção, serão abordados, de forma superficial, alguns padrões de
comunicação que utilizam códigos CRC, tendo em vista a alta confiabilidade e
eficiência na transferência de dados entre dispositivos.
4.3.1 Da Capacidade de Detecção CRC
A capacidade de detecção de erros através de algoritmos de CRC, é um fator
estreitamente relacionado com as características do polinômio gerador em questão.
Assim, de acordo com a subseção 4.1.3, que descreve as premissas que devem ser
obedecidas para a escolha ou criação do polinômio divisor G(x), os códigos CRC são
capazes de detectar (ROCHOL, 2012):
Todos os erros de um único bit;
Todos os erros duplos, desde que G(x) seja composto por no mínimo três
termos;
39
Todos os erros de bit, em quantidade ímpar, desde que G(x) tenha “x + 1” como
um de seus fatores;
Todos os erros em rajada, desde que o comprimento da rajada seja menor/igual
a ordem do polinômio G(x);
A maioria dos erros de rajada, maior do que a ordem de G(x).
Em relação ao último tópico supracitado e sendo r o grau do polinômio divisor
G(x), Tenenbaum (2003, p.212) nos diz que:
Se o tamanho da rajada for r + 1, o restante da divisão por G(x) será zero se e somente se a rajada for idêntica a G(x). Por definição de rajada, o primeiro e os últimos bits de uma rajada dever ser iguais a 1; assim, a correspondência entre os valores dependera dos r − 1 bits intermediários. Se todas as combinações forem consideradas igualmente prováveis, a probabilidade desse quadro incorreto ser aceito como válido será de ½ (r - 1) (TENEMBAUM, 2003, p. 212).
Ainda segundo Tenenbaum (2003), em um sistema onde todos os padrões de
bits sejam equiprováveis, caso ocorra em um quadro uma rajada de erro maior que r
+ 1 bits ou várias rajadas curtas de erro, a probabilidade desse quadro defeituoso ser
verificado e aceito sem ser percebido o erro, será igual a ½r. De fato, os códigos
baseados em CRC, possuem uma taxa residual de erros não detectados
extremamente baixa, principalmente para algoritmos baseados em polinômios
geradores compostos por 8 ou mais bits.
Assim, a escolha do polinômio divisor, a ser empregado em determinado
projeto, é um dos quesitos de impacto significativo, relacionados com os tipos de erros
que poderão ser alcançados de maneira confiável. Essa escolha, geralmente é feita
de acordo com o protocolo a ser desenvolvido, respeitando características físicas, o
comprimento dos quadros, a distância e as taxas de transmissão que se pretende
alcançar (PATERSON; DAVIE, 2004).
4.3.2 Aplicações
Devido sua alta eficiência, os códigos de CRC, têm sua empregabilidade mais
difundida entre padrões e protocolos da camada de enlace utilizados em redes de
computadores. Nesses protocolos, a definição do polinômio gerador G(x) foi
estabelecida de acordo com os organismos de padronização, relacionados às
40
telecomunicações, tais como a IEEE (Institute of Electrical and Electronics Engineers)
e ITU (International Telecommunication Union) (ROCHOL, 2012).
Geralmente, as versões dos códigos de CRC, são referenciadas pela
quantidade de bits redundantes, ou seja, o FCS que serão atribuídos a cada quadro.
Por equivalência, essas versões, também podem e são referenciadas com ao grau do
polinômio gerador G(x). De acordo com Kurose e Ross (2006), os padrões
internacionais estabeleceram geradores para processamento de FCS compostos por
8, 10, 12, 16 e 32 bits.
Nesse contexto, Peterson e Davie (2004, p.65), nos diz que “em uma Ethernet,
por exemplo, um quadro transportando até 12.000 bits (1.500 bytes) de dados exige
apenas um código de CRC de 32 bits, ou, como normalmente é expresso, utiliza CRC-
32”. Assim podemos observar na Figura 9, a partição FCS de 4 bytes, ou seja, 32 bits,
destinada a indexação dos bits de redundância ao quadro.
Figura 9: Frame IEEE 802.3 Fonte: Elaborado pelo autor.
Dentre os principais protocolos e arquiteturas de rede que empregam a
verificação de redundância cíclica, podemos destacar as redes ATM (Asynchronous
Transfer Mode), que trata-se de uma tecnologia de comunicação de dados de alta
velocidade, em que são aplicadas as versões CRC-8, CRC-10 e CRC-32. Já o
protocolo HDLC (High-level Data Link Control), utiliza o CRC-CCITT V41, baseado
em um polinômio gerador de ordem 16. A versão CRC-32, também é altamente
utilizada em protocolos Token Ring e por uma série de protocolos IEEE 802 dos
padrões de redes Ethernet (PETERSON; DAVIE, 2004; TENENBAUM, 2003).
41
5 PROJETO EXPERIMENTAL CRC-5
O projeto experimental consiste na elaboração e análise de um código de CRC,
o qual verificará a integridade dos dados transmitidos, em um sistema de comunicação
digital. Devido os algoritmos desenvolvidos, respectivamente para o circuito
transmissor e o circuito receptor, serem baseados em um polinômio divisor
G(x)=110101, de ordem 5, o projeto foi denominado de CRC-5.
Para tal finalidade, o projeto foi desenvolvido através de dois softwares:
Primeiramente foi elaborado um circuito eletrônico composto por microcontroladores,
para simulação em plataforma virtual ISIS do programa Proteus 8. Posteriormente
foram desenvolvidos dois códigos baseados em linguagem C, através do software de
compilação MikroC PRO for PIC, para implementação nos microcontroladores
estruturados no circuito da plataforma ISIS.
5.1 Do Circuito de Simulação em Plataforma ISIS
A edificação e teste do circuito eletrônico, foi feita através do Proteus 8, que se
trata de um software desenvolvido pela empresa Labcenter Eletronics, o qual possui
várias plataformas de aplicação. Dentre as mais utilizadas, se destacam a plataforma
ISIS que funciona como uma bancada eletrônica para edificação e simulação de
circuitos eletrônicos e a plataforma ARES que é utilizada para elaboração de
esquemas para confecção de placas de circuito impresso (PCB).
O circuito eletrônico elaborado para simulação do código intitulado pelo autor
de CRC-5, foi desenvolvido em plataforma ISIS, para fins de execução e análise.
Conforme a Figura 10, o circuito completo é composto pela junção de três sistemas,
denominados de transmissor, deturpador do sinal e receptor, os quais serão
abordados individualmente nas subseções seguir, para melhor interpretação.
42
Figura 10: Tx e Rx CRC-5 em plataforma ISIS. Fonte: Elaborado pelo autor.
Cabe ressaltar que, para implementação e execução do código desenvolvido
no MikroC, tanto a estrutura de transmissão, quanto a de recepção é composta por
um microcontrolador PIC (Periferal Interface Controler). Os microcontroladores PIC
são componentes desenvolvidos pela empresa Microchip Technology e basicamente
consistem em chips compostos de unidades de processamento, memórias e
periféricos de entrada/saída. Como são dispositivos programáveis, os
microcontroladores consistem praticamente em uma fusão entre hardware e software
e são largamente utilizados em circuitos eletrônicos relacionados à tecnologia das
mais diversas áreas e seguimentos, tais como as telecomunicações, setores de
automação, maquinários agrícolas, eletrodomésticos, dentre outras.
5.1.1 Estrutura do Transmissor
Assim como pode ser observado na Figura 11, o sistema transmissor é
composto basicamente por um microcontrolador PIC 16F877a, um LCD (liquid crystal
display) 2x20, por um teclado matricial 4x3 e por 4 resistores.
43
Figura 11: Tx CRC-5 em plataforma ISIS. Fonte: Elaborado pelo autor.
De acordo com o datasheet do microcontrolador PIC 16F877a empregado ao
circuito, podemos citar como principais características, o fato deste ser um dispositivo
composto por 40 pinos, dentre os quais 33 são configuráveis como portas de
entrada/saída; arquitetura de dados em 8 bits; memória RAM de 368 bytes; memória
EEPROM de 256 bytes; memória Flash de 14 kB (8 Kwords); operar em frequência
máxima de 20 MHz, dentre outras. A escolha deste dispositivo se deu principalmente
pela sua quantidade de portas, haja vista, a necessidade de interação com os demais
componentes.
Em relação ao display, foi utilizado um LCD 2x20, composto por 14 pinos, sendo
que os pinos 1, 2 e 3 são utilizados para alimentação e controle de brilho do visor. Já
os pinos referentes as entradas RS e E (utilizados como controle de escrita e leitura),
44
juntamente os pinos de D4 à D7 (utilizados como barramentos de dados), foram
interligados às portas RC do microcontrolador, para fins de comunicação entre os
dispositivos. Já o teclado matricial 4x3, é do tipo utilizado em telefones fixos
convencionais e possui 7 portas, as quais foram interligadas às portas RD do PIC
16F877a. Quanto aos barramentos que interligam saídas horizontais do teclado às
respectivas entradas no microcontrolador, foram conectados resistores em pull down,
a fim de manter essas entradas em nível logico baixo quando não tiverem sendo
acionadas, evitando mau funcionamento do sistema.
O canal de transmissão, refere-se a linha que simboliza o barramento que sai
da porta RB0 do transmissor, se conecta ao relé do sistema deturpador do sinal,
juntamente com o barramento que sai desse sistema e se conecta à porta RA0 do
sistema receptor. Um fato importante a ser considerado, é que microcontroladores do
modelo PIC 16F877a são alimentados através das portas 11, 12, 31, 32, porém a
alimentação de microcontroladores em plataforma de simulação ISIS, deve ser
intrinsicamente subentendida, uma vez que não é representada.
5.1.2 Estrutura de deturpação do sinal
Conforme foi abordado nos capítulos anteriores, os códigos de controle de erro
são utilizados como medidas de tratamento da descaracterização sofrida pelo sinal no
canal transmissão, devido aos efeitos de deterioração, oriundas de diversos fatores,
genericamente denominados de ruídos e interferências. Assim, como o objetivo do
projeto experimental, é ratificar didaticamente o poder de detecção de erros dos
códigos de CRC, em meio a um canal de transmissão sujeito a perturbações, foi
elaborado um pequeno circuito, denominado de deturpador do sinal, para inserção de
erros no canal.
45
Figura 12: Sistema deturpador do Sinal. Fonte: Elaborado pelo autor.
Como pode ser observado na Figura 12, o sistema deturpador intercepta o
canal de envio de dados e consiste em um circuito composto de um botão, sendo que
enquanto estiver acionado, acenderá o led (D2), simultaneamente ativando o relé que
está em paralelo, fazendo com que o sinal passe por uma segunda rota composta por
uma porta inversora. Dessa forma, o sinal será adulterado e injetado novamente no
nó ligado ao pino de entrada RA0 do PIC 16F628a, do sistema receptor.
5.1.3 Estrutura do receptor
O sistema receptor é formado por um LCD 2x20 e por um microcontrolador PIC
16F628a. De acordo com datasheet do fabricante, dentre as principais características
do PIC 16F628a, se destaca o fato deste ser um dispositivo composto por 18 pinos,
dentro os quais 16 podem são configuráveis como portas de entrada ou saída;
memória RAM de 224 bytes; memória EEPRON de 128 bytes; memória Flash de 3,5
kB (2 Kwords); oscilador interno de 4 MHz; além operar em uma frequência máxima
de 20 MHz.
46
Figura 13: Rx CRC-5 em plataforma ISIS. Fonte: Elaborado pelo autor.
Conforme a Figura 13, a comunicação entre o microcontrolador e o display no
receptor, ocorre de forma análoga ao sistema transmissor. Sendo assim, seguindo a
mesma lógica, os pinos do LCD referentes ao controle de escrita e leitura, além dos
pinos de barramentos de dados foram interligados às portas RBs do PIC 16F628a. O
encaminhamento e recepção dos dados de forma binária pelo microcontrolador é
obtido através do barramento conectado à porta RA0, configurada como entrada
através do programa do receptor desenvolvido no software MikroC.
5.2 Lógica e Programação aplicada ao CRC-5
A plataforma de simulação ISIS permite atribuir aos microcontroladores
firmwares de execução, através do acesso ao dispositivo pela interface gráfica e
direcionamento do local onde o arquivo desenvolvido por um software de compilação
se encontra armazenado. Assim, para a elaboração dos programas de execução do
CRC-5, utilizou-se o compilador MikroC PRO for PIC, sendo este um dos softwares
de destaque da MikroEletronika, empresa especializada no desenvolvimento e
47
produção de microcontroladores, placas, compiladores e livros. O MikroC consiste,
resumidamente, em um IDE (Integrated Development Environment) altamente
avançado, baseado em linguagem C e composto por uma vasta biblioteca de recursos
sofisticados, para o desenvolvimento de maneira rápida e eficiente de programas
utilizados em microcontroladores PIC.
Os códigos utilizados nos programas de codificação e decodificação CRC-5,
encontram-se disponíveis no Apêndice 1 e Apêndice 2, respectivamente. Como pode-
se observar nos Apêndices, foram inseridos comentários rente a codificação utilizada,
para melhor compreensão dos códigos em questão. Contudo, para maior clareza
quanto ao objetivo e execução do CRC-5, faz-se necessário a descrição das
características lógicas e funcionais, relacionadas à interação dinâmica entre os
programas de transmissão e recepção, assim como das estruturas abordadas na
seção anterior.
Conforme o algoritmo a descrito na Figura 14, quanto aos procedimentos de
funcionamento do transmissor em plataforma ISIS, será executado no
microcontrolador PIC 16F877a o programa de codificação (Apêndice 1: Codificador
CRC-5) desenvolvido em MikroC, que solicitará através do LCD a inserção de dois
valores, sendo que, deverá ser utilizado o teclado como periférico de entrada. Após
inseridos os valores, o operador deverá digitar # para o envio ou * para apagar os
valores e redigitar. Se pressionado #, baseado na codificação CRC, o programa
realizará o cálculo do FCS, apresentará os valores binários resultantes no LCD e os
encaminhará bit a bit ao receptor, através do barramento ligado a pino RB0 do
microcontrolador.
48
Figura 14: Algoritmo do Sistema Transmissor CRC-5. Fonte: Elaborado pelo autor.
Um dos pontos relevantes, relacionados ao desenvolvimento do projeto, refere-
se aos procedimentos para a geração e verificação do FCS, os quais foram
desenvolvidos baseados em um LFSR, com registradores e operadores XOR
empregados de acordo com o polinômio divisor G(x)=110101. Além da utilização de
variáveis como registradores e dos operadores XOR (representados no MikroC como
acento circunflexo), também foi necessário o emprego de técnicas de deslocamento
e acesso a bit a bit, assim como o uso de comandos de instrução for para a criação
de laços de repetição estruturados. Cabe ressaltar que, os valores referentes a
numeração do teclado, estão relacionados a tabela ASCII que utiliza 8 bits para
representação 128 caracteres. Porém no CRC-5, como os dois bits mais significativos
da representação numeral em ASCII são nulos, estes foram descartados e utilizou-se
somente seis bits de cada valor para concatenação e cálculo do FCS, consistindo na
codificação e envio de mensagens compostas de 12 bits de informação seguidas de
5 bits de redundância.
Já no sistema receptor será implementado e executado no microcontrolador
PIC 16F628a, o programa de decodificação (Apêndice B: Decodificador CRC-5), o
qual realizará a recepção dos dados, ou seja, dos pulsos elétricos, através do pino
RA0, procedimento que consistirá na realização de varredura cíclica e sincronizada
49
ao sistema transmissor. Dessa forma, a medida que os dados chegam ao receptor, os
valores dos seis primeiros bits são atribuídos a uma variável A e uma segunda variável
B atribui os valores do sétimo ao décimo segundo bit, sendo que simultaneamente, os
bits de informação juntamente com os bits de redundância vão sendo impressos no
LCD e submetidos a verificação em tempo real, através de codificação baseada em
registradores de deslocamento. Ao final da transmissão, o sistema verificará se todos
os registradores, se apresentarem resultados nulos, o receptor irá constatar que os
dados foram recebidos de forma integra e imprimirá os valores em formato decimal no
LCD; caso contrário, o sistema constatará a ocorrência de erro(s), imprimindo como
resultado “mensagem corrompida”. Assim, Figura 15, nos mostra o algoritmo
relacionado aos principais procedimentos realizados pelo sistema receptor.
Figura 15: Algoritmo do Sistema Receptor CRC-5. Fonte: Elaborado pelo autor.
50
Quanto ao procedimento de transmissão dos dados, antes de ser enviado o
primeiro bit da mensagem, o transmissor envia três pulsos elétricos seguidos de
delays de 50 ms, sendo um pulso baixo entre meio dois pulsos altos, como forma de
sincronismo, para que assim o receptor possa identificar o início da transmissão. Em
seguida a mensagem é transmitida bit a bit, através de pulsos elétricos temporizados
em 500 ms. No receptor, a varredura dos pulsos de sincronismo, assim como dos
pulsos referentes aos bits da mensagem, é feita através de comandos de condição if,
temporizadores e comandos de repetição for, logicamente estruturados.
Propositalmente o procedimento da transmissão bit a bit, foi configurado para
executar-se de forma extremamente lenta, para que assim fosse feita analise da
decodificação realizada no sistema receptor, diante da inserção de erros no canal.
Assim, em conformidade com a subseção 5.1.2, devido ao fato da simulação
em ISIS ser executada em condições ideais e a necessidade de avaliar a capacidade
de detecção de erros do sistema, foi elaborado e complementado ao circuito o Sistema
Deturpador do Sinal para inserção de erros. Dessa forma, se durante a transmissão o
botão do sistema deturpador for acionado, este ativará o relé que inverterá o sinal que
está sendo encaminhado ao receptor. Esta inversão implicará na adulteração do
pacote de bits, fenômeno que deve ser identificado e cientificado pelo sistema
receptor.
De acordo com fundamentação teórica relacionada ao CRC, assim como testes
realizados na plataforma de simulação, o Projeto CRC-5 é capaz de detectar todos os
erros de único bit, todos os erros duplos, além de todos os erros de rajada menor igual
a 5 bits.
51
CONSIDERAÇÕES FINAIS:
Devido à evolução dos sistemas de comunicação digital, cuja tendência se volta
para taxas de transferência de dados em velocidades cada vez maiores, é de
fundamental importância a implementação de códigos de controle de erro, a fim de se
garantir a confiabilidade e eficiência funcional dos sistemas em questão. Nesse
contexto, o trabalho abordou os principais fundamentos relacionados a códigos
detectores de erros, como forma de embasamento para exploração dos códigos CRC.
Assim de acordo com o levantamento literário realizado, os códigos detectores
em geral, necessitam de menor quantidade de bits de redundância e de
processamento, se comparados aos códigos corretores. Porém, sua implementação
é indicada para sistemas altamente confiáveis, como os enlaces cabeados, pois a
necessidade de retransmissão constante de pacotes que foram corrompidos, acabam
inserindo uma latência muito grande ao sistema, inviabilizando a comunicação.
Quanto ao objetivo principal da presente pesquisa, foi possível constatar que
os códigos de CRC empregados à transmissão de dados, se utilizam de um
processamento lógico simples e ao mesmo tempo poderoso, o qual através de
acréscimo de poucos bits de redundância permitem a detecção de erros em pacotes
de dados compostos por milhares de bytes. Dessa forma, devido sua alta capacidade
de detecção erros, esses códigos são amplamente utilizados em protocolos da
camada de enlace de redes de computadores, os quais os empregam juntamente com
mecanismos ARQ, consistindo em eficientes meios de comunicação. Vale lembrar
que, a realização do Projeto Experimental CRC-5, possibilitou uma exemplificação
simples e didática da empregabilidade funcional baseada nos fundamentos teóricos
dos métodos de CRC.
Apesar da grande importância dos códigos de controle de erro, a literatura
disponível ainda os abordam de forma sucinta, fato que dificultou a realização deste
trabalho. Dessa forma faz-se necessário a realização de mais estudos científicos para
melhor entendimento das estruturas lógicas e da aplicabilidade relacionada a esta
classe de códigos.
52
REFERÊNCIAS:
ALENCAR, Marcelo S. de. Televisão Digital. 1. ed. São Paulo: Érica, 2007.
FOROUZAN; Behrouz A.; MOSHARRAF; Firouz. Redes de Computadores: Uma Abordagem Top-Down. 3. ed. Porto Alegre: AMGH, 2013.
GIL, Antonio C. Como elaborar projetos de pesquisa. 5. ed. São Paulo: Atlas, 2010.
HAYKIN, Simon; MOHER, Michael. Sistemas modernos de comunicações wireless. 1. ed. Porto Alegre: Bookman, 2008.
JESZENSKY, Paul Jean E. Sistemas telefônicos. 1. ed. Barueri: Manole, 2004.
KUROSE, James F.; ROSS, Keith W. Redes de computadores e a internet: uma abordagem top-down. 3. ed. São Paulo: Pearson, 2006.
LAKATOS, Eva M.; MARCONI, Marina de A. Metodologia Científica. 5. Ed. São Paulo: Atlas, 2010.
PETERSON, Larry L.; DAVIE, Bruce S. Redes de computadores: uma abordagem de sistemas. 1. ed. Rio de Janeiro: Elsevier, 2004.
PIMENTEL, Cecílio José L. Comunicação Digital. 1. ed. Rio de Janeiro: Brasport, 2007.
REBELLATO, João Luiz. Codificação de rede baseada em códigos corretores de erros clássicos. 2010. 119 f. Tese (Doutorado em Engenharia Elética) -Departamento de Engenharia Elétrica, Universidade Federal de Santa Catarina, Florianópolis, 2010.
ROCHOL, Juergen. Comunicação de dados. 1. ed. Porto alegre: Bookman, 2012.
RUSCHEL, Orlando T. Princípios da comunicação digital. 1. ed. Porto Alegre: EDIPUCRS, 1996.
SOARES, Luiz Fernando G.; LEMOS, Guido; COLCHER, Sérgio. Redes de computadores: das LANs, MANs e WANs às Redes ATM. 2. ed. Rio de Janeiro: Campus, 1995. TANENBAUM, Andrew S. Redes de computadores. 1. ed. Rio de Janeiro: Elsevier, 2003.
53
YOUNG, Paul H. Técnicas de comunicação eletrônica. 5. ed. São Paulo: Pearson, 2006.
54
APÊNDICE 1: Codificador CRC-5
55
56
57
58
59
APÊNDICE 2: Decodificador CRC-5
60
61
![Apostila Cursos CRC - Administração de Departamento Pessoal CRC[1]](https://img.document.onl/doc/110x75/5571f85049795991698d254a/apostila-cursos-crc-administracao-de-departamento-pessoal-crc1.jpg)
