 |
|
|
||
 |
||||
|
|
|
||
|
|
||||
C. Polcino Milies
Introdução Num artigo anterior [1] descrevemos a forma em que são codificados os códigos de barras que encontramos frequentemente em artigos nas prateleiras de supermercados, em livros e revistas, etc. Nesse trabalho nos colocávamos duas perguntas interessantes a respeito desses códigos: • O desenho das barras é totalmente simétrico do ponto de vista da máquina leitora, que o lê usando um feixe de luz transversal. Ao passá-lo "de ponta-cabeça", como muitas vezes acontece no caixa do supermercado, ela não deveria ler o número na ordem contrária? Como é que a máquina reconhece a ordem certa de leitura? • Quando a máquina leitora não consegue "ver" o código, o operador do caixa digita esse número rapidamente. Ele não poderia cometer um erro e nós acabarmos pagando por um produto diferente daquele que estamos comprando? Como é que a máquina consegue reconhecer quando um erro foi cometido? Respondemos à primeira dessas perguntas naquele primeiro artigo. O objetivo desta continuação é responder à segunda pergunta. Como veremos, isso é conseguido através do uso engenhoso de algumas ideias de matemática elementar. Lembramos ao leitor que há dois códigos em uso para identificar artigos à venda. O mais antigo deles, o código UPC, usado inicialmente apenas na América do Norte, utiliza doze dígitos, escritos na forma de barras, para que possam ser lidos por uma máquina utilizando luz refletida (e também escritos, logo abaixo das barras, na nossa numeração, para que possam ser lidos por um operador humano, quando necessário). Com a ampla difusão do uso desse tipo de código, passou-se a usar um novo sistema, chamado EAN-13, que utiliza treze dígitos, para permitir também distinguir o país de origem do produto.
A detecção de erros Para compreender como funciona o processo de detecção de erros, precisamos entender, inicialmente, como se atribui a cada produto um dígito que permite essa detecção. Suponhamos que um determinado produto está identificado, no sistema EAN-13, por uma dada sequência de dígitos a1a2...a12a13. Os primeiros doze dígitos identificam o país de origem, o fabricante e o produto específico, e são determinados naturalmente, por um método padrão, a cargo de uma autoridade classificadora em cada país. O décimo terceiro dígito, chamado dígito de verificação, é justamente o dado utilizado para a detecção de erros, e o denotaremos por x. Para facilitar nossa exposição, vamos escrever essa sequência como um vetor O sistema EAN-13 se utiliza de um vetor fixo, que chamaremos vetor de pesos: Calcula-se, então, o produto escalar de ambos os vetores multiplicando cada dígito do vetor de informação pelo número que ocupa a mesma posição no vetor de pesos: α • w = (a1, ..., a12, x) • (1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1) Agora, o dígito de verificação x se escolhe de forma tal que a soma acima seja múltiplo de 10. O número 3 foi escolhido por ser o menor número diferente de 1 tal que mdc(3, 10) = 1. Por exemplo, no caso do código da figura abaixo, os números que indicam o país de origem, o fabricante e o produto são 789500026624. Vamos ver como foi determinado o dígito de verificação. Chamando esse dígito de x e fazendo o "produto escalar" com o vetor de pesos, temos:
7 + (3 × 8) + 9 + (3 × 5) + 0 + (3 × 0) + 0 + (3 × 2) + 6 Consequentemente, deve-se tomar x = 1. Vejamos agora um exemplo de como funciona a detecção de erros. Um livro do autor deste artigo recebeu o código de barras 9781402002380. Suponhamos que, por um erro de digitação no quarto dígito, esse número é lido como α = 9782402002380. Ao fazer a verificação de leitura, o computador que recebeu a informação faz a operação α • w e obtém: 9 + (3 × 7) + 8 + (3 × 2) + 4 + (3 × 0) + 2 + (3 × 0) + 0 Como o resultado não é um múltiplo de 10, o computador avisa que foi cometido algum erro. O código UPC é muito semelhante. Como utiliza apenas 12 dígitos (pois usa apenas um para identificar o país de origem do artigo, enquanto o EAN utiliza-se de dois), e o vetor de pesos utilizado pelo UPC também tem um dígito a menos, ele é: w = (3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1). Deixamos para o leitor verificar que, se o digitador comete apenas UM erro de digitação, trocando um dos dígitos ai, por um outro valor, então necessariamente o produto α • w não será um múltiplo de 10 e assim será possível detectar que o erro foi cometido. Se mais de um erro for cometido na digitação, o fato provavelmente ainda será detectado, mas já não podemos ter certeza, pois eles poderiam se "compensar" mutuamente e a soma poderia ainda continuar sendo um múltiplo de 10. O leitor pode se perguntar qual é a função do vetor de pesos w. De fato, se a escolha do dígito de verificação x fosse feita simplesmente de modo que a1 + a2 + ... + a12 + x seja múltiplo de 10, o que equivale a considerar o vetor de pesos (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1), ainda assim um erro de digitação seria detectado. Acontece que há um outro tipo de erro de digitação muito comum, que consiste em digitar todos os números corretamente, mas trocar a ordem de dois dígitos consecutivos. Nesse caso, o vetor (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1) não detecta o erro. Suponha que, ao digitar o número 9 788531 404580, se tenha cometido esse tipo de erro, e que o número de fato digitado fosse 9 788351 404580. Ao efetuar a verificação, ter-se-ia (9, 7, 8, 8, 3, 5, 1, 4, 0, 4, 5, 8, 0) • (1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1) = 134, que não é múltiplo de 10. Dessa forma, o erro seria detectado. Suponha agora que, ao digitar o número 9 781402 002380, código do livro, se tenha cometido um erro desse mesmo tipo, e que o número de fato digitado fosse 9 781402 002830. Ao efetuar a verificação, terse- ia (9, 7, 8, 1, 4, 0, 2, 0, 0, 2, 8, 3, 0) • (1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1) Esse exemplo mostra que o sistema de detecção adotado acima não tem a capacidade de detectar todo erro de transposição cometido. A transposição de dois dígitos consecutivos ai e ai + 1 não é detectada, nesse sistema de codificação, se e somente se | ai − ai + 1| = 5, pois, nesse caso, devemos ter (supondo i par) a1 + ... + 3ai + ai + 1 + ... + x e a1 + ... + 3ai + 1 + ai + ... + x, ambos múltiplos de 10 e, subtraindo as duas expressões, 2ai − 2ai + 1 é múltiplo de 10, o que implica ai − ai+ 1 = 5 (se ai é ímpar, tem-se a diferença com o sinal trocado). Um outro exemplo interessante é o sistema universalmente adotado para a classificação de livros, o ISBN (International Standard Book Number). Esse sistema utiliza códigos com dez dígitos, de 0 a 9, vetor de pesos w = (10, 9, 8, 7, 6, 5, 4, 3, 2, 1) e escolhe-se o dígito de verificação de modo que o produto escalar seja múltiplo de 11. Por exemplo, o livro do autor, já mencionado anteriormente, tem o número ISBN igual a 1-4020-0238-6. O dígito final, de verificação, é o 6, pois (1, 4, 0, 2, 0, 0, 2, 3, 8, 6) • (10, 9, 8, 7, 6, 5, 4, 3, 2, 1) = Esse sistema tem um inconveniente ilustrado no exemplo: um conhecido livro de Álgebra tem código ISBN igual a 0-387-96035. Vamos tentar determinar qual seria seu dígito de verificação, que deve ser um número a tal que (0, 3, 8, 7, 9, 6, 0, 3, 5, a) • (10, 9, 8, 7, 6, 5, 4, 3, 2, 1) = 243 + a seja um múltiplo de 11. Como 253 é múltiplo de 11, temos a = 10. Porém, no conjunto dos dígitos de 0 a 9, não temos nenhum que represente o número 10. Desse modo, devemos introduzir mais um símbolo para representar esse número. A convenção usual é utilizar o símbolo X e, assim, o código ISBN que aparece no livro é 0-387-96035-X. Autores como D. F. Beckley [2] e J. Verhoeff [3] investigaram sistematicamente os erros cometidos por operadores humanos. Os números abaixo mostram que os erros num único dígito e as transposições são, de longe, os mais frequentes. Assim, os erros que consideramos neste texto cobrem mais de 80% dos erros possivelmente cometidos.
Referências bibliográficas [1] POLCINO MILIES, C. A Matemática dos códigos de barras, RPM 65. Páginas na Internet com informações sobre o assunto: |
