Detecção e Correção de Erros - UnB

13/07/16 Departamento de Ciência da Computação

Detecção e Correção de Erros

1

13/07/16 Departamento de Ciência da Computação Departamento de Ciência da Computação

Objetivo

• Entender como o computador pode detectar erros e corrigí-los

•Perceber a importância da detecção e correção de erros

• Saber onde estes algoritmos podem ser aplicados

2


Sumário• Introdução•Desenvolvimento•Considerações Finais

3


Computador não erra?

●Às vezes . . .

●Mas como o ser humano erra com uma frequência muito maior . . .

● É mais fácil um erro ser cometido pelo ser humano do que pelo computador


No entanto . . .● Erros acontecem . . .

●Na transmissão de dados entre computadores os erros são mais frequentes

●Podem gerar grandes prejuízos


Revisando a aula de números binários

●Computadores usam números binários porque:● É mais simples de implementar● É mais barato de produzir● É mais confiável

●Mas, mesmo assim, um bit pode mudar de 0 para 1 ou vice-versa!


Fatores espúrios● Eventos acidentais que podem causar uma mudança de valor em um ou mais bits● Pico de energia elétrica● Ruídos● Radiação cósmica● . . .


Exemplo●Transação Bancária

● Débito de 10 reais● Byte com o valor em binário

● 00001010● Devido a um fator espúrio . . .● Um bit é trocado● 10001010

● Débito de 138 reais!


Como melhorar ainda mais a confiabilidade?


Imagine várias cartas, branco de um lado e

vermelho do outro lado


Vamos virar as cartas aleatoriamente


Cartas viradas aleatoriamente


Agora vamos acrescentar mais uma linha e coluna.


Pronto! Olhem bem para esta imagem!

Copie, se quiser?


Suponha que ela foi transmitida pela Internet


Descubra se ela chegou sem erros ao destino?


1 erro?


E esta?


1 erro


Outra?


Fácil, 1 erro


Mais uma?


Detecto 2


Verifique esta também?


2 erros e não consigo corrigir (existem duas

possibilidades de correção)


Vamos tentar agora?


Tem 4 erros, mas não detecto


Desafio . . .


Corrijo 3, mas dá trabalho!


Paridade Pode ser par ou ímpar A quantidade de linhas e colunas precisa ser ambos pares ou ímpares Exemplo: 5x9 4x6 Mas não 3x4


ISBNEditora: LTC; Edição: 1 (1996)

Idioma: Português

ISBN-10: 852160372X

ISBN-13: 978-8521603726

Dimensões do produto: 22,9 x 15,7 x 1 cm

Peso do produto: 281 g


International Standard Book Number

● Usa a mesma técnica de verificação!● Livros possuem código de 10 dígitos, o ISBN-10

● O décimo dígito é o dígito verificador, tal qual o bit de paridade do exercício anterior

● Ou seja, se você pedir um livro pelo ISBN o livreiro pode verificar se você cometeu um erro. ● Basta testar a soma verificadora. Assim você não recebe o livro errado.


ISBN-10●Por exemplo: ISBN 0-13-911991-4

● 0x10+1x9+3x8+9x7+1x6+1x5+9x4+9x3+1x2=172● 172/11 = 15 resto 7

● Se o resto for igual a zero, então o dígito verificador é zero

● Caso contrário, subtraia 11 do resto para obter o dígito verificador● 11-7 = 4

● Se o dígito verificador for 10, para evitar mais de um dígito, utiliza-se a letra x


International Standard Book Number

● Usa a mesma técnica de verificação!● Livros possuem código de 10 dígitos, o ISBN-10

● O décimo dígito é o dígito verificador, tal qual o bit de paridade do exercício anterior

● Ou seja, se você pedir um livro pelo ISBN o livreiro pode verificar se você cometeu um erro. ● Basta testar a soma verificadora. Assim você não recebe o livro errado.


ISBN-13● Usa soma módulo 10● Em aritmética modular

● (x1+3x2+x3+3x4+x5+3x6+x7+3x8+x9+3x10+x11+3x12+x13) = 0 mod 10

● Exemplo: Calcular o dígito verificador no ISBN-13 978-0-306-40615-?● s = 9×1 + 7×3 + 8×1 + 0×3 + 3×1 + 0×3 + 6×1 + 4×3 + 0×1 + 6×3 + 1×1 + 5×3

● = 9 + 21 + 8 + 0 + 3 + 0 + 6 + 12 + 0 + 18 + 1 + 15

● = 93● 93 / 10 = 9 remainder 3● = 10 – 3 = 7


Código de Barras

Se o código de barras não for lido corretamente (dígito verificador errado)

a máquina emite um sinal sonoro de erro!


De que se trata tudo isso?Imagine depositar R$ 1000,00 e por uma interferência na linha o valor é alterado para R$ 10,00 . . .

Imagine uma sonda em Júpiter mandar dados errados e nãoser possível corrigí-los, demandando nova retransmissão.São mais de 30 minutos para o 1º bit chegar!!! Mais de uma semana para transmitir 1 imagem! Taxa de transmissão: 160 bps!!

Computadores usam sistemas de controle de erros mais complexoscapazes de detectar e corrigir erros múltiplos. Disco Rígido temgrande espaço alocado só para corrigir erros, de forma queseja mais confiável. Os esquemas utilizados são parecidos com ode paridade.


Dúvidas

38

?


Estudar em casa assunto da aula prática

Fonte: Google Educator


Estudar em casa assunto da aula prática

Estudar o conteúdoVer os vídeos e os outros linksResolver os exercíciosLevar as dúvidas para tirar com os tutores e monitoresAinda com dúvidas, consultar o plantão de dúvidasFazer os exercícios


Referências

http://csunplugged.org/

Documents

Detecção e Correção de Erros - UnB