Blog

ERROS CÓDIGOS DE DETECÇÃO UNIVERSIDADE FEDERAL DO ABC 1 . Resumo… Santo André Novembro/2011 Sumário páginas Introdução……… Blnários e Erros……… 3 4. Método da Parid Erro.. 1 orlo to view nut*ge ão de Dados 4 5. O código de correção de erro 6 5. 1 . Detecção e Correção de Erro com o Código de .. 7 6. Exercicios resolvidos 9 7. Considerações 10 8. Referências Bibliográficas…. [2] 1 . Resumo Este trabalho, em formato livro-texto, tem por objetivo apresentar de forma direta e esclarecida a problemática dos dos erros incidentes nos sistemas digitais na transferência de informações.

Será sintetizado em modelo explicativo, alguns dos métodos mais importantes, e também simples, acerca das estratégias para detecção e correção de erros. 2. Introdução Em informática, telecomunicações e afins, mais concretamente em uma transmissão de dados entre sistemas digitais, um erro é um “defeito” na mensagem/informação a ser transmitida, fazendo com que esta seja modificada para um valor que não corresponde ao da original, o que é extremamente inconveniente. A detecção e correção de erros em uma comunicação de dados é crucial para que esta seja feita de uma forma correta e imune a falhas. Movimentação de Dados Binários e Erros A movimentação de dados binários e de códigos de um lugar para outro é a operação mais frequentemente realizada em sistemas digitais. Aqui estão alguns exemplos: – A transmissão de voz digitalizada através de um enlace de microondas. – A gravação e recuperação de dados de dispositivos de memória externa como fitas e discos magnéticos. – A transmissão de informação de um computador para um terminal de um usuário remoto ou para outro computador através das linhas telefônicas (usando um modem). por que ocorrem os erros?

Sempre que uma nformação é transmitida de um dispositivo (o transmissor) para outro dispositivo (o receptor), existe a possibilidade de que erros ocorram de modo que o receptor não receba a informação idêntica àquela que foi enviada pelo transmissor. – Um link de comunicaçã 10 receba a informação idêntica àquela que foi enviada pelo transmissor. – Um link de comunicação pode romper; – O sinal se atenua ao longo de grandes distâncias; – Uma linha telefônica pode ter multo ruído; [3] • Uma posição de memória (uma célula) pode falhar; – etc…

A causa principal de erros de transmissão, por exemplo, são ruídos létricos que consistem em flutuações de tensão ou corrente que estão presentes em diferentes graus em todos os sistemas eletrônicos. A figura 1 é uma ilustração simples de um tipo de erro de transmissão. Figura 1 . Exemplo de ruído causando um erro na transmissão de dados digitais O transmissor envia uma linha de sinal digital serial relativamente livre de ru[dos através de uma linha de sinal para o receptor. Entretanto, quando o sinal atinge o receptor, ele contém certo nivel de ruido sobreposto ao sinal original.

A maioria dos equipamentos digitais modernos é projetada para ser elatlvamente livre de erros e a probabilidade de que eles ocorram como mostrado na figura 1 é muito baixa. Entretanto, devemos compreender que sistemas digitais frequentemente transmitem milhares, ou mesmo milhões, de bits por segundo, e assim mesmo uma taxa de ocorrência de erros muito baixa pode produzir um erro ocasional que pode ser incômodo, ou mesmo um desastre. Por essa razão, muitos sistemas digitais empregam algum método para detecção (e algumas vezes correção) de erros. . Método da Paridade para Detecção de Erro Muitos sistemas usam um bit de paridade como um meio de det Método da Paridade para Detecção de Erro Muitos sistemas usam um bit de paridade como um meio de detecção de erro de bit. Qualquer grupo de bits possui um número de 1 ‘s no grupo sempre par ou sempre (mpar. um bit de pandade é acrescentado a um grupo de bits para tornar o número de 1 ‘s par e um bit de paridade impar torna ímpar o total de bits. um dado sistema pode operar com paridade par ou ímpar, porém não ambas.

Por exemplo, se um sistema opera com paridade par, é feita uma verificação em cada grupo de bits recebido para certificar-se de que o número total de 1 ‘s no grupo seja par. Caso exista um número ímpar de 1 ‘s, ocorreu um erro. Como uma ilustração da forma com que os bits de paridade são acrescentados a um código, a Tabela 1 apresenta uma lista dos bits de paridade para cada número BCD, tanto para a paridade par quanto para a ímpar. O bit de paridade para cada número BCD está na coluna P. Tabela 1.

O código BCD com bits de paridade O blt de paridade pode ser acrescentado ao inicio ou final do código, dependendo do projeto do sistema. Observe que o número total de 1 ‘s, incluindo o bit de paridade, é sempre par para a paridade par e sempre ímpar para a paridade ímpar. Detecção de um erro – Um bit de paridade provê a detecção de erro em um único bit (ou qualquer número ímpar de erros, que é bem pouco provável) mas não pode verificar dois erros em um grupo. Por exemplo, vamos supor que desejamos transmitir o código BCD 0101. A paridade pode ser usada com qualquer número de bits: desejamos transmitir o código BCD 0101. (A paridade pode ser usada com qualquer número de bits: estamos usando quatro bits como ilustração. ) O código total transmitido, incluindo o bit de paridade par, é: Agora vamos admitir que ocorra um erro no terceiro bit a partir da esquerda (0 1 vira O). Quando esse código é recebido, o circuito de verificação de paridade determina a existência de apenas um único 1 (paridade impar), quando deveria haver um número par de 1 • s.

Devido ao número par de 1 ‘s não aparecer no código recebido, é indicado um erro. Um bit de paridade impar também provê uma forma de detecção de erro em um único bit, em um dado grupo de bits. 5. O código de Correção de Erro Hamming Conforme estudado, um unico bit de paridade permite a detecção de erro em um único bit em uma palavra de código. Um único bit de paridade pode indicar que existe um erro em um certo grupo de bits. Para orrigir um erro detectado, mais Informação é necessária porque a posição do bit errado tem que ser identificada antes que ele posa ser corrigido.

Mais do que um bit de paridade tem que ser incluído no grupo de bits para tornar possível a correção do erro detectado. Em um código de 7 bits, existem sete possibilidade de erro em um único bit. Nesse caso, três bits de paridade podem não apenas detectar um erro, mas podem especificar a posição do bit errado. O código Hamming provê a correção de um único erro. A abordagem a seguir ilustra a construção de um código Hammlng de 7 bits para a correção de um Hammng de 7 bits para a correção de um único erro.

Número de Bits de Paridade – Se o número de bits de dados projetados for d, então o número de bits de pandade, p, é determinado pela seguinte relação: (l) Por exemplo, se temos quatro bits de dados, então p é determinado por tentativa e erro por meio da Equação anterior. Façamos p=2. Então: Como 2Ap tem que ser igual ou maior a d+p+l, a relação na equação (l) não é satisfeita. Temos que tentar novamente. Façamos p=3. Então: Esse valor de p satisfaz a equação (l), assim são necessários três bits de paridade para proporcionar a correção de um único rro para quatro bits de dados.

Deve-se notar que a detecção e correção são proporcionadas por todos os bits, de paridade de dados, no grupo de código; ou seja, os bits de paridade também são verificados. Inserção de Bits de Paridade no Código – Agora que sabemos determinar o número de bits de paridade necessários no nosso exemplo particular, temos que arranjar os bits adequadamente no código. Devemos saber que nesse exemplo o código é composto de quatro bits de dados e três bits de paridade.

O bit mais à esquerda é designado como bit 1 , o próximo bit é 0 2 e assim por diante, conforme a seguir: bi l, bit 2, bit 3, bit 4, bit 5, bit 6, bit 7 Os bits de paridade estão localizados nas posições que são numeradas em correspondência às potencias de dois ascendentes (1, 2, 4, 8, conforme indicado: P 1, P2, Dl, P3, D2, 03, D4 0 PAGF 10 potencias de dois ascendentes (1, 2, 4, 8, conforme indicado: RI, P2, Dl, P3, 02, 03, 04 0 símbolo pn designa um bit de paridade em particular e Dn designa um bit de dado em particular. 5. 1.

Detecção e Correção de Erro com o Código de Hamming Cada bit de paridade, ao longo dos seus grupos de bits correspondentes, tem que ser verificado para a paridade adequada. Caso existam três bits de paridade na palavra de código, são geradas três verificações. Caso existam quatro bits de paridade, são geradas quatro verificações, e assim por diante. Cada verificação de paridade apresenta um resultado bom ou rum. O resultado total de todas as verificações de paridade indica o bit, se houver algum, que está errado, como a seguir: passo 1 – Comece com o grupo verificado por Pl . asso 2 Verifique o grupo quanto à paridade correta. Um O representa uma verificação de paridade correta e um 1 representa uma verificação incorreta. Passo 3 – Repita o passo 2 para cada grupo e paridade. Passo 4 – O número binário formado pelo resultado de todas as verificações de paridade determina a posição do bit do código que está errado. Esse é o código de posição de erro. A primelra verificação de paridade gera o bit menos significativo (LSB). Se todas as verificações forem corretas, não há erro.

Exemplo: Considere que a palavra de código 0011001 seja transmitida e que 0010001 seja recebida. O receptor não “sabe” o que foi transmitido e tem que testar as paridade para determinar se o código está correto. Determine transmitido e tem que testar as paridade para determinar se código está correto. Determine qualquer erro que tenha ocorrido na transmissão se a paridade usada foi a par. Solução – primeiramente, faça uma tabela de poslção de bit, conforme indicado na Tabela 2: Tabela 2.

Designação dos BITS Posição dos BITS Número da posição em Binário Código recebido Primeira verificação de paridade: Pl 1 001 0 P2 2 0100 Dl 30111 P341000 D25 1010 D361100 O bit Pl verifica as posições 1, 3, 5 e 7; existem dois 1 ‘s nesse grupo; a verificação de paridade é correta C] 0 (LSB) Segunda verificação de paridade: O bit P2 verifica as posições 2, 4, 6 e 7; xistem dois 1 ‘s nesse grupo; a verificação de paridade é correta Cl O Terceira verificação de paridade: O bit P3 verifica as posições 4, 5, 6 e 7; existe um 1 nesse grupo; a verificação de paridade é incorreta 1 (MSB) Resultado: O código de posição de erro é 100 (binário quatro). Isso diz que o bit na posição 4 está errado. Ele é o O e deveria ser 1. O códi o corri ido é 0011001, que está de acordo com o código tran relação acima, m 8 16 32 64 128 256 512 r 45678910 rn+r 1221 38 71 136 265 522 Overhead (h) 50 31 19 11 642 2- Associe o bit de paridade apropriado para os seguintes ódigos: G) 1010 (b)1 11000 (b) (C)1 01101 (d)100011100100 Solução: Faça o bit de paridade O ou 1 conforme o necessário para tornar o número total de 1 ‘s par.

O bit de paridade será o bit mais à esquerda (colorido) (a)01 OIO (b)11 11000 (c)01011 OI 00011100100 3- Um sistema de paridade ímpar recebe os seguintes grupos de código: 10110, 11010, 110011, 110101110100 e 1100010101010. Determine quais grupos, se houver algum, estão com erro. Solução: Como é informado que a paridade é ímpar, qualquer grupo com um número par de l’s está incorreto. Os seguintes grupos estão com erro: 110011 e 1100010101010. – Determine o código de Hamming para o número BCD 1001 (bits de dados), usando paridade par. Solução: Passo 1: determine o número de bits de paridade necessários. Façamos p: 3, então: 2p= 22= 8 4+ 3* 8 Três bits de paridade são suficientes.

Total de bits de código: 4+ 7 Passo 2: construa uma tabela Desi na bits NO da posição em bin ão dos bits Posição dos dos Bits de paridade Pl 1 que o número de l’s (2) seja par nesse grupo. O bit P2 verifica os bits das posições 2,3,6 e 7 e tem que ser O para que o número de 1 ‘s (2) seja par nesse grupo. O bit P3 verifica os bits das posições 7 e tem que ser 1 para que o número de l’s (2) seja par nesse grupo. Passo 4: Esses bits de paridade são inseridos na tabela 2-12 e o código combinado resultante é 0011001 Observação: Para visualizar como ocorre a detecção e correção de erros, acesse um simulador virtual do código de Hamming em http://candle. ctit. utwente. nl/wp5/tel-sys/exercises/datalinkp2p lhamming74demo 7.

Considerações Finais Através dos tópicos abordados neste livro-texto, espera-se que o conteúdo explanado possa servir de auxílio aos futuros estudantes da disciplina Natureza da Informação (em complemento às aulas), de modo que estes ossam ter um [10] material adicional de apoio, e desta forma, conduzi-los à plena compreensão do assunto. 8. Referências Bibliográficas [1] Thomas FIOYd, 2007. SISTEMAS DIGITAIS – FUNDAMENTOS APLICAÇOES. gookman, ga ed. p. 1 11. [2] Ronald J. TOCCi, Neal S. Widmer, 1998. DIGITAL SYSTEMS: PRINCIPLES AND APPLICATIONS. Prentice-HaIl, Inca a Simon & Schuster company. [3] Equipe de professors de Natureza da Informação, 2011. NOTAS DE AULA – BC-0504, Natureza da Informação. Aula 3. [4] http://wvm. ele. puc-rio. br ,’-mcr0/SLlDES/COdigos. Pdf 25/11/2011 – 16h30) cacessad0 [1 11