Error Correction
Transcrição
Error Correction
Códigos de detecção e correção de erro Raul Queiroz Feitosa Conteúdo Motivação Idéia Básica Definições Deteção de Erro Correção de Erros Código de Hamming Exercícios 23/08/2013 Códigos 2 1 Motivação Erros ocorrem: 0’s se transformam em 1’s devido a causas espúrias em dispositivos de memória, em sistemas de comunicação, etc. Objetivo: Procurar mecanismos que sejam capazes de detectar ou, melhor ainda, corrigir este erros. 23/08/2013 Códigos 3 Idéia Básica Para representar 2m palavras utilizam-se n=r+m bits (r bits além do necessário!) Entre as 2m+r palavras possíveis são válidas e m r 2 (2 -1) são inválidas. 2m palavras O sistema só gera palavras válidas. Logo, se surgir alguma palavra inválida, trata-se de um erro! 23/08/2013 Códigos 4 2 Definições Código é o conjunto de palavras válidas. Erro simples é a alteração de uma palavra válida numa única posição (bit). 5 Códigos 23/08/2013 Definições Distância de Hamming entre palavras é o número de posições (bits) em que as palavras diferem. Exemplo: p1 = 1 0 0 0 1 0 0 1 p2 = 1 0 1 1 0 0 0 1 h(p1,p2)=3 xor(p1,p2) = 0 0 1 1 1 0 0 0 23/08/2013 Códigos 6 3 Definições Distância de Hamming de um código é a menor distância de Hamming entre 2 palavras do código. Exemplo: H=2 4 10110001 3 2 10111110 7 00000001 4 5 11110011 23/08/2013 Códigos 7 Detecção de erro Para que uma palavra (válida) de um código com H=d se transforme numa outra palavra (válida) do mesmo código, deverão ocorrer pelo menos d erros simples. Logo, um código capaz de detectar d erros simples deve ter H ≥ d+1 23/08/2013 Códigos 8 4 Detecção de erro Exemplo: bit de paridade 0000 0011 0101 0110 1001 1010 1100 1111 23/08/2013 H=1 2 Códigos 9 Correção de erro Idéia básica: Qualquer palavra inválida é substituída pela válida mais próxima (em termos de distância de Hamming) logo, um código será capaz de corrigir até c erros simples, se e somente se H ≥ 2c+1 23/08/2013 Códigos 10 5 Correção de erro Problema: Suponha que se deseja construir um código contendo 2m palavras válidas, capaz de corrigir até 1 erro simples. Quantos bits extra serão necessários (r=?) 23/08/2013 Códigos 11 Correção de erro Solução: 2m+r → total m 2 → válidas (m+r)2m → inválidas a uma distância 1 de uma válida Portanto, m+r+1 ≤ 2r 23/08/2013 Códigos 12 6 Correção de erro Pela relação anterior m r m+r overhead (%) 8 4 12 50 16 5 21 31 32 6 38 19 64 7 71 11 128 8 136 6 256 9 265 4 512 10 522 2 23/08/2013 Códigos 13 Código de Hamming Construindo um código de correção de 1 erro simples para 2m palavras Acrescentam-se r bits de paridade (vide slide anterior): total de m+r bits por palavra Bits são numerados de 1 a m+r Posições potência inteira de 2 têm os bits de paridade, cf. próximo slide 23/08/2013 Códigos 14 7 Código de Hamming Construindo um código de correção de 1 erro simples para 2m palavras 10100111 1 1 1 1 0 1 0 0 0 1 1 1 1 2 3 4 5 6 7 9 10 11 12 Bit 1 → 1 , 3 , 5 , 7 , 9 , 11 Bit 2 → 2 , 3 , 6 , 7 , 10 ,11 Bit 4 → 4 , 5 , 6 , 7 , 12 Bit 8 → 8 , 9 , 10 ,11 ,12 Geralmente um bit b é verificado por todos os bits de paridade em que b = b1 + b2 + ... + bj 23/08/2013 8 Códigos 15 Exercícios 1. Deseja-se construir um código composto de 3 palavras código de 8 bits cada uma. As palavras código devem ser escolhidas de modo a maximizar o número de erros simples que se poderá detectar. Pergunta-se quantos erros simples se poderá corrigir com tal código? 23/08/2013 Códigos 16 8 Exercícios 2. Derive uma relação que forneça um limite inferior para o número de bits de verificação (r) necessários para se montar um código de correção de até 2 erros simples para 2m palavras válidas distintas. Códigos 23/08/2013 17 Exercícios 3. Seja o código formado pelas palavras código abaixo: 10100110 - 11111111 - 01011001 - 10000101 Qual é a distância de Hamming do Código? Qual é o número máximo de erros simples que se pode detectar neste código? Qual é o número máximo de erros simples que se pode corrigir neste código? 23/08/2013 Códigos 18 9 Exercícios 4. 5. Qual é o código completo contendo 12 bits produzido pelo código de Hamming derivado palavra de 8 bits abaixo? 10100101 Altere aleatoriamente um dos bits do resultado à questão anterior e verifique se você consegue identificar o bit alterado, e portanto, corrigi-lo. 23/08/2013 Códigos 19 FIM 23/08/2013 Códigos 20 10
Documentos relacionados
Detecção de Erros – Paridade
– Foram descobertos por R.W. Hamming e constituem um código perfeito (para correção de um único erro) – Os códigos de Hamming apresentam m ≥ 2 e apresentam:
Leia mais