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.

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

Soma das contribuições	60
O que o controlo lê	0
Dígito de controlo exigido pelos restantes	7
O número é válido?	Sim
Um algarismo errado, e o controlo lê o mesmo	0 de 135
Vizinhos trocados, e o controlo lê o mesmo	0 de 13

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

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 é d₀
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

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 \cdot 0 + 9 \cdot 1 + 8 \cdot 1 + 7 \cdot 0 + 6 \cdot 0 + 5 \cdot 0 + 3 \cdot 2 + 2 \cdot 2 + 1 \cdot 9 = 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 + 4 x \equiv 0 (mod 11) \Rightarrow 4 x \equiv - 36 \equiv 8 (mod 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 \cdot 3 = 12 \equiv 1 (mod 11) \Rightarrow x \equiv 8 \cdot 3 = 24 \equiv 2 (mod 11)$
4. Reescreva o 2 e a soma apresentada na página será 44, exatamente quatro onzes.
  
  $36 + 4 \cdot 2 = 44 = 4 \cdot 11$
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 - 9$

Referências (3)

The Luhn check digit as the IMEI standard defines it, step by step, with the worked example the page's IMEI preset reproduces (26053179311383, sum 53, check digit 7): 3GPP TS 23.003, "Numbering, addressing and identification", Annex B (normative): IMEI Check Digit computation. Published as ETSI TS 123 003 V18.7.0 (2024-09).
The ISBN-13 check digit, the 1-3 weighting that barcodes use, with the manual's own example 978-0-11-000222-4: International ISBN Agency, ISBN Users' Manual, International Edition, sixth edition. London, 2012. Appendix 1, "Check digit calculation".
ISBN-10's mod 11, the barcode's blind pairs 05, 16, 27, 38, 49 and Luhn's 09 and 90, the frequencies of real mistakes from Verhoeff's study, Gumm's theorem that no even-modulus scheme catches every swap, and Verhoeff's dihedral scheme with its tables: J. A. Gallian, "Error detection methods." ACM Computing Surveys 28(3), 1996, pp. 504-517. DOI 10.1145/243439.243457

Pela equipa 42Math · Verificado com fontes publicadas. Correções bem-vindas.