Atividade 4: A Mágica de virar as cartas—Detecção e Correção de Erros

Apresentação

Quando os dados são armazenados num disco ou transmitidos de um computador para outro, costumamos supor que estes não tenham sofrido alterações no processo. Mas, às vezes, problemas acontecem e os dados são alterados acidentalmente. Esta atividade utiliza um truque de mágica para mostrar como detectar quando os dados foram corrompidos e como podemos corrigi-los.

Disciplinas e conteúdos relacionados

Habilidades

Nível de Ensino

Material

Cada dupla de crianças precisará de:

O “Truque de Mágica”

Demonstração

Esta é a sua chance de se tornar um mágico!

Você precisará de um conjunto de cartas iguais de duas faces. (Para fazer suas próprias cartas, corte uma folha grande e colorida apenas de um lado). Para a demonstração, é mais fácil usar cartas magnéticas e planas com uma cor diferente em cada lado—ímãs de geladeira são ideais.

  1. Escolha uma criança para dispor as cartas aleatoriamente em um quadrado de dimensões 5 × 5.

Casualmente adicione outra linha e coluna, “apenas para dificultar o truque”.

Essas cartas são a chave para o truque. Você deve escolher as cartas adicionais para assegurar que haja um número par de cartas coloridas em cada linha e coluna.

  1. Peça a uma criança para virar apenas uma carta enquanto você cobre seus olhos. A linha e coluna que contém a carta modificada agora terão um número ímpar de cartas coloridas, e isto identificará a carta modificada.

As crianças conseguem adivinhar como o truque é feito ?

Ensine o truque para as crianças:

  1. Trabalhando em pares, as crianças distribuem suas cartas em um quadrado 5 × 5.

  2. Quantas cartas coloridas estão em cada linha e coluna ? Trata-se de um número par ou ímpar ? Lembre-se, 0 é um número par.

  3. Agora, adicione uma sexta carta a cada linha, certificando-se de que o número de cartas coloridas seja sempre ímpar. Esta carta extra é chamada de carta de “paridade”.

  4. Adicione uma sexta linha de cartas na parte de baixo, fazendo com que o número de cartas em cada coluna seja um número par.

  5. Agora, vire uma carta. O que você nota sobre a linha e coluna dessa carta ? (Elas terão um número ímpar de cartas coloridas.) Cartas de paridade são usadas para lhe mostrar a ocorrência de um erro.

  6. Agora, faça revezamentos para realizar o “truque”.

Atividades de Extensão:

  1. Tente usar outros objetos. Tudo o que tem dois “estados” é apropriado. Por exemplo, você poderia utilizar cartas de baralho, moedas (cara ou coroa) ou cartões impressos com 0 ou 1 (para referir-se ao sistema binário).

  2. O que acontece quando duas ou mais cartas são viradas ? (Nem sempre é possível saber exatamente quais duas cartas foram viradas, embora seja possível dizer que alguma coisa foi modificada. Normalmente, é possível restringir a um dos dois pares de cartas. Após 4 viradas, é possível que todos os bits de paridade estejam corretos e, por isso, o erro poderia passar despercebido.)

  3. Outro exercício interessante é considerar a carta do lado inferior direito. Se você a escolhe como correta para a coluna logo acima, então ela estará correta para a fila à sua esquerda? (A resposta é sim, sempre.)

  4. Neste exercício de cartas empregamos a paridade par—usando um número par de cartas coloridas. Podemos fazê-lo com paridade ímpar ? (Isso é possível, porém a carta do lado direito somente funciona para a sua linha e coluna se os números de linhas e colunas são ambos pares ou ímpares. Por exemplo, isso funciona bem para um quadrado 5 × 9 ou 4 × 6, mas não para um quadrado 3 × 4.)

Um exemplo prático desafiador

Esta mesma técnica de verificação é utilizada em códigos de livro. Livros publicados possuem um código de dez dígitos normalmente encontrados na contracapa. O décimo dígito é um dígito verificador, tal qual os bits de paridade do exercício.

Isto significa que se você encomendar um livro usando o seu ISBN (International Standard Book Number – Padrão Internacional de Número de Livro), o editor pode verificar se você cometeu um erro. Eles simplesmente testam a soma verificadora. Assim, você não acaba esperando o livro errado !

Veja como calcular a soma verificadora: multiplique por dez o primeiro dígito, o segundo por nove, o terceiro por oito, e assim por diante, até o nono dígito multiplicado por dois. Some esses valores.

Por exemplo, o ISBN 0-13-911991-4 fornece o seguinte valor

\[ (0 × 10) + (1 × 9) + (3 × 8) + (9 × 7) + (1 × 6) + (1 × 5) + (9 × 4) + (9 × 3) + (1 × 2) = 172 \]

Em seguida, divida o resultado por onze. Qual é o resto?

\[ 172 ÷ 11 = 15 \] resto \(7\)

Se o resto for igual a zero, então a soma verificadora é zero. Caso contrário, subtraia 11 do resto para obter a soma verificadora.

\[ 11 – 7 = 4 \]

Olhe novamente. Este é o último dígito do ISBN acima ? Sim ! Se o último dígito do ISBN não fosse quatro, então saberíamos que houve um erro.

Também é possível obter uma soma verificadora de valor 10, o que demandaria mais de um dígito. Quando isso acontece, utilizamos a letra X.

Outro exemplo de uso do dígito verificador são os códigos de barra de produtos, os quais usam uma fórmula diferente. Se o código de barras não é lido corretamente, então o dígito final será diferente do valor calculado. Quando isso acontece, o equipamento de leitura emite um sinal sonoro para que o operador do equipamento refaça a leitura do código de barras.

As somas verificadoras estão corretas ?

Às vezes, cometemos erros. Alguns exemplos de erros comuns são:

Você pode encontrar um código ISBN de livro com a letra X para uma soma verificadora de valor 10 ? Não deverá ser difícil encontrá-lo — um dentre 11 livros devem ter esta soma.

Quais tipos de erros aconteceriam e não seriam detectados ? Você pode alterar um dígito e ainda obter a soma verificadora correta ? E se dois dígitos forem trocados (um erro de digitação comum) ?

De que se trata tudo isso ?

Imagine que você está depositando R$ 10,00 em dinheiro na sua conta bancária. O caixa digita o valor do depósito e o envia para um computador central. Contudo, suponha que alguma interferência ocorre na linha enquanto o montante está sendo enviado e o código de R$ 10,00 é alterado para R$ 1.000,00. Não há problema se você for o cliente, mas, obviamente, há claramente um problema para o banco!

É importante detectar erros nos dados transmitidos. Portanto, um computador precisa verificar que os dados recebidos não foram corrompidos por algum tipo de interferência elétrica na linha de transmissão. Às vezes, os dados originais podem ser reenviados se um erro foi transmitido, mas existem situações nas quais isso é inviável, por exemplo, caso um disco ou fita seja corrompido pela exposição a radiações magnéticas ou elétricas, pelo calor ou por danos físicos. Se os dados fossem recebidos de uma sonda espacial profunda, seria muito tedioso esperar pela retransmissão em caso de erro ! (Demora pouco mais de meia hora para conseguir um sinal de rádio para Júpiter quando este se encontra na sua posição mais próxima à Terra!)

Precisamos ser capazes de reconhecer quando os dados foram corrompidos (detecção de erro) e de reconstruir os dados originais (correção de erro).

A mesma técnica que foi utilizada no jogo de “virar as cartas” é usada em computadores. Colocando bits em linhas e colunas imaginárias, e acrescentando bits de paridade para cada linha e coluna, podemos não somente detectar se ocorreu um erro, mas quando este erro aconteceu. O valor do bit incorreto é modificado e, com isso, realizamos sua correção.

Obviamente, os computadores usam frequentemente sistemas de controle de erros mais complexos capazes de detectar e corrigir erros múltiplos. O disco rígido em um computador tem uma grande quantidade de espaço alocado para corrigir erros para que este funcione de forma confiável ainda que partes do disco falhem. Os sistemas utilizados para esse fim são bastante próximos ao esquema de paridade.

Para saber mais

O texto A matemática dos códigos de barra - Detectando erros discute algumas propriedades do ISBN e do código de barras usado para identificar produtos à venda e pode ser uma boa leitura para complementar a discussão iniciada com essa atividade.

Se você deseja aprofundar ainda mais seus conhecimentos sobre códigos corretores de erros, sugerimos os vídeos do canal 3blue1Brown no Youtube sobre códigos de Hamming. Esse tipo de código corretor de erro é um aprimoramento do que foi apresentado nesta atividade e abre portas para outras técnicas usadas nessa área da matemática.

Soluções e dicas

Erros que não seriam detectados são aqueles nos quais um dígito é incrementado e outro é decrementado. Neste caso, o valor da soma permanece inalterada.