← Matemática

Dígitos de Controlo: Luhn, Códigos de Barras, ISBN e os Erros que Deixam Passar

Introduza um número de cartão, um IMEI, um código de barras ou um ISBN e escolha o sistema que o verifica. A página mostra a contribuição de cada algarismo e se o número é válido. Em seguida, testa todos os erros a um passo de distância e lista aqueles que o dígito de controlo não notaria.

A carregar a simulação interativa...

Lição

A teoria — Dígitos de Controlo: Luhn, Códigos de Barras, ISBN e os Erros que Deixam Passar

Um dígito de controlo é um algarismo extra escolhido para que o número completo cumpra uma regra: neste caso, que os algarismos, cada um multiplicado ou transformado consoante a sua posição, somem um múltiplo do módulo, 10 ou 11. Um erro que quebre a regra é detetado. Um erro que a respeite não é notado. Por isso, um dígito de controlo pode provar que um número está errado, mas nunca pode provar que está correto.

O que significa cada símbolo

dᵢ
o algarismo a i posições da direita; o dígito de controlo é d0
wᵢ
o peso da posição i: 1 e 3 alternadamente para um código de barras, i + 1 para o ISBN-10
D(d)
a duplicação de Luhn: 2d, menos 9 quando ultrapassa os 9, resultando em 0 2 4 6 8 1 3 5 7 9
S
a soma da contribuição de cada algarismo
m
o módulo, 10 para o algoritmo de Luhn e para o código de barras, 11 para o ISBN-10; o número passa quando S é um múltiplo de m
Pressupõe
Um erro de cada vez. Dois erros num número podem anular-se mutuamente, e as contagens da página não dizem nada sobre eles. A tabela considera que qualquer par de algarismos tem a mesma probabilidade, o que não acontece na escrita real: o único par vizinho invisível para o algoritmo de Luhn é 09 e 90, e a frequência com que ambos surgem lado a lado depende dos números.
Falha quando
Um dígito de controlo não garante segurança. Qualquer pessoa que conheça o sistema pode criar um número válido. É por isso que um número de cartão que passe no algoritmo de Luhn significa apenas que foi bem digitado. O ISBN-13 utiliza o sistema do código de barras porque um ISBN-13 é, em si mesmo, um número de código de barras, sob os prefixos 978 e 979 que a GS1 disponibilizou.

Luhn deteta qualquer troca de vizinhos exceto uma: 09 e 90

Prima 1234567890 + controlo. Troque o 9 e o 0 e o resultado, 12345678093, passa. O algoritmo de Luhn duplica os algarismos em posições alternadas e, quando o dobro tem dois algarismos, soma-os: o 9 passa a 18 e depois a 9, e o 0 mantém-se 0. Trocar dois vizinhos altera a soma na diferença entre o que a duplicação acrescenta a cada um, e a duplicação acrescenta 0 a um 0, 1 a um 1, 4 a um 4, −4 a um 5, −1 a um 8 e 0 a um 9. O 0 e o 9 são os únicos dois algarismos que o algoritmo trata da mesma forma. É por isso que a grelha da esquerda tem exatamente duas células vermelhas, 09 e 90, e o sistema deteta 97,8% das trocas de vizinhos. Prima IMEI: este não tem nenhum 9 ao lado de um 0, e nenhuma das suas 13 trocas de vizinhos consegue passar.

Nenhum dígito de controlo gerado pela soma de algarismos mod 10 deteta todas as trocas

Prima Código de barras UPC. Duas das suas nove trocas de vizinhos passam: o 3 com o 8, e o 0 com o 5. Um código de barras multiplica os algarismos em posições alternadas por 3 e 1. Assim, trocar a e b altera a soma em 2(a − b), um múltiplo de 10 sempre que tenham uma diferença de cinco. Isso corresponde a 10 dos 90 pares. Outros pesos não obtêm melhores resultados. Para detetar qualquer algarismo único errado, um peso tem de ser 1, 3, 7 ou 9 mod 10. A diferença entre quaisquer dois destes é um número par, e um número par multiplicado por 5 é um múltiplo de 10: 88,9% é o limite máximo para qualquer sistema de pesos. A duplicação de Luhn não é um peso e atinge os 97,8%. Contudo, não consegue chegar aos 100%: Gallian apresenta a demonstração de 1985 de H. P. Gumm, segundo a qual nenhum sistema que some os seus algarismos, independentemente da transformação prévia que cada posição lhes aplique, consegue detetar qualquer algarismo único errado e qualquer troca de vizinhos quando o módulo é par. J. Verhoeff conseguiu ambos em 1969 através da multiplicação no grupo diedral do pentágono, onde a ordem dos fatores tem importância.

Luhn nunca nota quando se trocam dois algarismos separados por uma posição

Prima IMEI. Todas as suas 12 trocas com um algarismo no meio passam. Os dois algarismos encontram-se em posições com a mesma paridade, pelo que o algoritmo de Luhn duplica ambos ou nenhum. O código de barras dá a ambos o mesmo peso. A sua troca não altera a soma, e a tabela coloca ambos os sistemas em 0,0%. O ISBN-10 dá a cada posição um peso próprio, de 10 até 1. Desta forma, uma troca altera a soma na diferença de dois pesos multiplicada pela diferença de dois algarismos. Como 11 é primo, esse produto nunca é múltiplo de 11. Prima ISBN-13 e depois ISBN-10: o mesmo número, e 9 em 9 dessas trocas passam no primeiro sistema contra 0 em 6 no segundo. Trata-se de um erro raro, correspondendo a 0,8% dos erros reais na contagem de Verhoeff contra os 10,2% das trocas de vizinhos. No entanto, o sistema mod 11 tem a sua própria falha: gasta um símbolo, o X, no dígito de controlo 10. Nas posições com os pesos 6 e 5, cuja soma é 11, deixa passar todos os erros de algarismos duplos.

Problema resolvido na íntegra

  1. Recuperar um algarismo manchado de um ISBN-10 4 passos

    Um ISBN-10 é lido como 0-11-000?22-9, com o sétimo algarismo manchado. Encontre-o e explique por que razão existe exatamente uma resposta. Prima ISBN-10 para verificar o resultado.

    Abrir este problema na ferramenta

    1. Os pesos vão de 10 até 1 a contar da esquerda, pelo que o sétimo algarismo manchado tem o peso 4. Some os outros nove algarismos multiplicados pelos respetivos pesos.

      S=10⋅0+9⋅1+8⋅1+7⋅0+6⋅0+5⋅0+3⋅2+2⋅2+1⋅9=36S=10\cdot0+9\cdot1+8\cdot1+7\cdot0+6\cdot0+5\cdot0+3\cdot2+2\cdot2+1\cdot9=36

    2. A soma total tem de ser um múltiplo de 11, por isso 4 vezes o algarismo em falta tem de compensar a diferença.

      36+4x≡0(mod11) ⇒ 4x≡−36≡8(mod11)36+4x\equiv0\pmod{11}\ \Rightarrow\ 4x\equiv-36\equiv8\pmod{11}

    3. Em mod 11 é possível dividir, porque 11 é um número primo: 4 × 3 = 12 é 1 unidade superior a 11. Desta forma, multiplicar por 3 reverte a multiplicação por 4.

      4⋅3=12≡1(mod11) ⇒ x≡8⋅3=24≡2(mod11)4\cdot3=12\equiv1\pmod{11}\ \Rightarrow\ x\equiv8\cdot3=24\equiv2\pmod{11}

    4. Reescreva o 2 e a soma apresentada na página será 44, exatamente quatro onzes.

      36+4⋅2=44=4⋅1136+4\cdot2=44=4\cdot11

    Resposta

    O algarismo é 2, e o ISBN é 0-11-000222-9. É o único algarismo possível. A multiplicação por 4 envia os onze valores de 0 a 10 para onze restos diferentes em mod 11, logo há exatamente um que recai sobre o 8. Esta é a mesma propriedade que permite ao sistema detetar qualquer algarismo errado nesta posição, vista na outra perspetiva: um peso que torne visível qualquer erro, torna também qualquer mancha recuperável. Um sistema mod 10 com um peso de 2 nesse lugar daria duas hipóteses ou nenhuma, e falharia qualquer algarismo errado nessa posição que estivesse a uma distância de cinco do algarismo certo.

    x=2:0-11-000222-9x=2:\quad 0\text{-}11\text{-}000222\text{-}9
Referências (3)

· Verificado com fontes publicadas. Correções bem-vindas.