Erros e Códigos de Detecção na Comunicação de Dados

Natureza da Informação Erros e Códigos de Detecção Até agora trabalhamos com informações e representações e códigos Informações são armazenadas eou transmitidas e portanto Como garantimos que não ocorrem erros no armazenamento ou na transmissão das informações Comunicação Comunicação Quando transmitimos informações como temos certeza que o lado receptor recebeu corretamente a informação SE erros e perdas ocorrem porque isso acontece A perda de informação pode ocorrer em todos os processo de comunicação mas é possível convivermos com ela Depende Existem situações nas quais que é possível convivermos com perdas de informações e outras situações isso não é possível Comunicação Exemplo transmissão de imagem por uma rede de computadores Quando transmitimos um vídeo pelo YouTube ou quando baixamos uma música pela Internet se alguma mensagem é perdida não existe problema pois o volume de informações de uma mensagem é tão pequeno que a falta de informação de um frame quadro não fará diferença Alem disso mesmo se fizer a conseqüência não é nem significativa e nem relevante Comunicação Quando transmitimos uma imagem médica por exemplo uma ressonância magnética através de uma rede de computadores a perda de um único quadro pode representar a detecção de um tumor Portanto existem situações e aplicações nas quais os erros nos processo de comunicação são tolerados e outras não E como detectar esses erros Comunicação Imagine o seguinte esquema de um sistema de comunicação Surgem as seguintes questões Saída Entrada Se sim tudo bem Senão Porque elas são diferentes Quais erros ocorreram Quão diferentes elas podem ser isto é existe uma taxa de perda tolerável para essa aplicaçãocomunicação Qual é essa taxa Comunicação Codificador Entrada Símbolos Cadeia de bits Canal de transmissão Cadeia de bits Decodificador Símbolos Saída A r Fibra ÓticaCabo Satélite Telefone Porque ocorrem os erros Como vimos temos diversos canais de comunicação que são fisicamente diferentes e conseqüentemente diferentes tipos de erro podem ocorrer Um link de comunicação pode romper Uma linha telefônica pode ter muito ruído Uma posição de memória uma célula pode falhar Etc No nosso estudo iremos considerar que independentemente da causa física um erro é uma mudança de um bit de um estado para outro estado 0 para 1 ou 1 para 0 Comunicação Existem 2 formas de tratarmos um erro 1 detectar e notificar o erro e o receptor tratará o erro 2 recuperar o erro Em ambos os casos informações adicionais bits adicionais são acrescentadas para informar o receptor como obter a informação original Existem formas de informar se 2 conjuntos de bits são iguais ou não Erros e Códigos de Detecção Uma definição muito usual é a Distancia de Hamming que aponta quantos bits 1 de um conjunto de bits é diferente do outro Ex a seqüência 0110 e a seqüência 1110 estão separados pela distancia 1 de Hamming Consequentemente 2 conjuntos que estão separados pela distância de Hamming igual a zero são iguais em distância Para essa medida fazer sentido os conjuntos comparados têm que ter o mesmo número de bits Erros e Códigos de Detecção Bit de Paridade Qualquer conjunto de bits possui um número par ou impar de 1s Paridade par quando o número de 1s de uma seqüência de bits é par Paridade impar quando o número de 1s de uma seqüência de bits é impar Para a detecção de erros é adicionado um bit a uma determinada seqüência de bits o bit de paridade Um sistema de comunicação só pode operar com um tipo de paridade Erros e Códigos de Detecção Exemplo de bit de paridade para sequencias de 4 bits Erros e Códigos de Detecção PARIDADE PAR P BCD PARIDADE IMPAR P BCD 0 0000 1 0000 1 0001 0 0001 1 0010 0 0010 0 0011 1 0011 1 0100 0 0100 0 0101 1 0101 0 0110 1 0110 1 0111 0 0111 1 1000 0 1000 0 1001 1 1001 O bit de paridade pode ser adicionado no início ou no fim da seqüência de bits e isso depende somente do projeto do sistema Um bit de paridade só consegue detectar um número impar de erros isto é 1 erro3 erros numa seqüência mas não consegue detectar 2 erros Imagine um sistema com paridade par e transmitindo a seqüência 0101 Com o bit de paridade focaria 00101 Supondo que ocorra um erro no terceiro bit o receptor receberá 00001 e apontará um erro pois perceberá um número im par de 1s numa paridade par Agora se ocorrerem 2 erros ao receptor receber 01010 O receptor não perceberá o erro pois o numero de 1s será par Erros e Códigos de Detecção Exercícios 1 Determine o bit de paridade par aos seguintes grupos de códigos 1010 111000 101101 1000111001001 101101011111 2 Um sistema de paridade impar recebe os seguintes grupos de códigos 101101101011001111011110100 e 1100010101010 Estão todos corretos Erros e Códigos de Detecção Vimos que com o codigo de detecção de paridade é possível detectar o erro mas não corrigilo O código de Hamming permite que alem da detecção de um erro seja possível especificar qual foi o bit no qual o erro ocorreu e corrigir o erro Erros e Códigos de Detecção 1 Se o número de bits de dados projetados for d então o número de bit de paridade p minimo é dado pela equação 2P dp1 onde d é o numero de bits a serem enviados e p é p número de bits de paridade necessários obtido por sucessivas tentativas até a equação ser verdadeira Ex Se tivermos 4 bits podemos determinamos p por tentativa e erro se p 2 temos 22 4 e dp1 7 e portanto a equação não se satisfaz se p 3 temos 23 8 e satisfaz a equação 1 portanto são necessários 3 bits de paridade para proporcionar a correção de um erro em uma seqüência de 4 bits Erros e Códigos de Detecção 2 Inserção dos bits de paridade no código No nosso exemplo temos 4 bits de informação e 3 de paridade O bit mais a esquerda é o bit1 o próximo é o bit 2 bit1 bit2 bit3 bit4 bit5 bit6 bit7 bit8 Os bits de paridade estão colocados nas posições correspondentes as potencias 1248 P1 P2 D1 P3 D2 D3 D4 Erros e Códigos de Detecção Para determinar o valor dos bits de paridade é necessário determinar a quais bits o bit de paridade está associado Para isso montamos a seguinte tabela Erros e Códigos de Detecção Designação dos Bits Posição do bits Numero da posição em binário P1 1 001 P2 2 010 D1 3 011 P3 4 100 D2 5 101 D3 6 110 D4 7 111 Bits de dados dn Bits de Paridade Pn Tabela de posicionamento de bits para um código de correção de erro de 7 bits O numero da posição do bit de paridade P2 tem 1 bit no meio Devemos verificar todas as posições que têm 1 no meio inclusive P2 Portanto P2 verifica os bits das posições 236 e 7 O bit de paridade identifica a quantidade de 1s edependendo se foi definido paridade par ou impar ele é preenchido de forma a tornar a quantidade de 1s compatível com a paridade especificada Erros e Códigos de Detecção Exemplo Determinar o código de Hamming para o número 1001 usando paridade par Passo1 determinar p número de bits de paridade necessários 2P 23 8 dp1 431 8 Passo 2 Construir a tabela com os bits de paridade posicionados Erros e Códigos de Detecção Atende a equação portanto 3 bits de paridade são suficientes Designação dos Bits Posição do bits P1 1 P2 2 D1 3 P3 4 D2 5 D3 6 D4 7 Bits de dados dn Bits de Paridade Pn Números binários não inteiros Passo 3 Determine os bits de paridade bit P1 verifica os bits das posições 135 e 7 e tem que ser 0 para que o numero de 1s seja par nesse grupo bit P2 verifica os bits das posições 236 e 7 e tem que ser 0 para que o numero de 1s seja par nesse grupo bit P3 verifica os bits das posições 456 e 7 e tem que ser 1 para que o numero de 1s seja par nesse grupo Passo 4 inserir os bits de paridade na tabela e obtenha o código que será enviado 0011001 Erros e Códigos de Detecção Designação dos Bits Posição do bits P1 1 P2 2 D1 3 P3 4 D2 5 D3 6 D4 7 Bits de dados dn 1 0 0 1 Bits de Paridade Pn 0 0 1 Para a detecção do código de Hamming temos o seguinte procedimento Devem ser geradas tantas verificações quantos forem os bits de paridade Se forem 3 bits de paridades serão geradas 3 verificações e assim sucessivamente Passo 1 inicie começando por P1 e verifique o grupo quanto a paridade correta Se for correta coloque 0 e se for incorreta coloque 1 Passo 2 Repita o passo 1 para grupo de paridade Passo 3 O número obtido pelo resultado de todas as verificações determina a posição do bit errado Esse é o código de posição de erro e se todas as verificações forem corretas não há erro A primeira verificação gera o bit menos significativo Números binários não inteiros Detecção e correção de erro com o Código de Hamming Exemplo Imagine que a palavra 0011001 seja transmitida mas o receptor receba 0010001 Como o receptor não sabe que ocorreu um erro ele deve verificar se ocorreu ou não passo 1 desenhar a tabela de posição de bit 1º verificação o bit P1 verifica as posições 135 e 7 e existem 2 bits 1s nesse grupo então a paridade é correta 0 2º verificação o bit P2 verifica as posições 236 e 7 e existem 2 bits 1s nesse grupo então a paridade é correta 0 3º verificação o bit P3 verifica as posições 456 e 7 e existe um 1 nesse grupo então a paridade é incorreta 1 Resultado o código de posição de erro é 100 e está na posição 4 da palavra Ele é 0 e deveria ser 1 e o código corrigido é 0011001 Detecção e correção de erro com o Código de Hamming Designação dos Bits Posição do bits P1 1 P2 2 D1 3 P3 4 D2 5 D3 6 D4 7 Bits de dados dn 1 0 0 1 Bits de Paridade Pn 0 0 O 1 Códigos de erros Ø Como vimos a detecção de erros implica em um aumento de numero de bits a serem transmitidos Ø Implica em um aumento de processamento na comunicação Ø Em algumas situações não é viável a verificação de erros em todas as transmissões Exemplo Ø As mensagens transmitidas na Internet pelo protocolo IP têm no cabeçalho da sua mensagem um campo para verificação de erro o campo checksum As estações e os roteadores da rede só verificam erro nos cabeçalhos dessas mensagens e deixam para as aplicações verificarem os errosquando isso for necessário Ex transmissão de um programa FTP Ø E se os erros ocorrem no próprio campo de checksum Referências GMIT COURSE6050JSpring 2008OcwWebElectrical Science6050JSpring2008 capitulo 4 Sistemas Digitais Fundamentos e Aplicações de Thomas L Floyd capitulo 2