Universidade de Coimbra ~ Códigos detectores de erros ~ A álgebra dos números de identificação

Universidade de Coimbra

~ Códigos detectores de erros ~

A álgebra dos números de

identificação

Sistemas de identificação

Maio 2003 A álgebra dos números de identificação 1

Códigos de barras

UPC / EAN

Maio 2003 A álgebra dos números de identificação 1

Maio 2003 A álgebra dos números de identificação 1Maio 2003 A álgebra dos números de identificação 1

Sistema ISBN

(International Standard Book Number)

Maio 2003 A álgebra dos números de identificação 1Maio 2003 A álgebra dos números de identificação 1

Bilhetes de Avião

Maio 2003 A álgebra dos números de identificação 1Maio 2003 A álgebra dos números de identificação 1

Sistema VIA VERDE

Maio 2003 A álgebra dos números de identificação 1Maio 2003 A álgebra dos números de identificação 1

e muitos mais exemplos ...• cartões de crédito

• cheques, contas bancárias (NIB)• NIF, passaportes• correio expresso, vales postais• revistas (ISSN)• cartões de utilizador (bibliotecas, lojas, ...)

• cd’s, telemóveis, comunicações com satélites ...

Maio 2003 A álgebra dos números de identificação 2Maio 2003 A álgebra dos números de identificação 2

Identifica ofabricante

Códigos de barras

Identifica oproduto

Algarismode

Controle

Identifica opaís

European Article Number

Sistema

Maio 2003 A álgebra dos números de identificação 2Maio 2003 A álgebra dos números de identificação 2

Código de barras EAN

a13 a12 a11 a10 a9 a8 a7 a6 a5 a4 a3 a2 a1

a1 é o algarismo em {0,1,2,3,4,5,6,7,8,9} tal que

a13+3a12+a11+3a10+a9+ ... +3a4+a3+3a2+a1

é divisível por 10

?

x3 x3 x3 x3 x3 x3 x1 x1 x1 x1 x1 x1 x1

Maio 2003 A álgebra dos números de identificação 2Maio 2003 A álgebra dos números de identificação 2

5 6 0 1 1 9 9 0 7 2 6 7 ?

Código de barras EAN

5 0 1 9 7 6 ?

103 10+ 7 =

+18+ +3+ +27+ +0+ +6+ +21+

3

Maio 2003 A álgebra dos números de identificação 3Maio 2003 A álgebra dos números de identificação 3

Para que serve tal algarismo de controle?

Maio 2003 A álgebra dos números de identificação 3Maio 2003 A álgebra dos números de identificação 3

Os testes de qualidade garantem:

poderão ocorrer quando muito erros singulares

(um algarismo errado)

5 6 0 1 1 9 9 0 7 7 6 7 7x3

3 + 7 + 15

X3

= 25

3x(7-2)

3 + 7 = 10

Maio 2003 A álgebra dos números de identificação 3Maio 2003 A álgebra dos números de identificação 3

ESSENCIAL:

max. div. comum (3,10)=1

max. div. comum (1,10)=1

Maio 2003 A álgebra dos números de identificação 4Maio 2003 A álgebra dos números de identificação 4

Sistema ISBN

criado pelas

editoras

Maio 2003 A álgebra dos números de identificação 4Maio 2003 A álgebra dos números de identificação 4

Erros mais comuns

Tipo de erro Freq. Rel.

Singular: a b 79.1%

Troca de algarismos adjacentes: ab ba 10.2%

Maio 2003 A álgebra dos números de identificação 4Maio 2003 A álgebra dos números de identificação 4

Os códigos de barras não detectam

todas as “trocas de algarismos adjacentes”

porque

m.d.c.(3-1,10)=2

EFICIÊNCIA 88,9%

Maio 2003 A álgebra dos números de identificação 5Maio 2003 A álgebra dos números de identificação 5

Sistema ISBN

a10 a9 a8 a7 a6 a5 a4 a3 a2 a1

?

0 - 3 8 7 - 9 4 6 6 5 - 9país editora n.º identificação alg. controle

a1 {0,1,2,3,4,5,6,7,8,9,10} tal que10a10 +9a9 + 8a8 + ... + 3a3 + 2a2 + a1

é divisível por 11

Quando a1 =10 faz-se a1 = X

Maio 2003 A álgebra dos números de identificação 5Maio 2003 A álgebra dos números de identificação 5

Maio 2003 A álgebra dos números de identificação 6Maio 2003 A álgebra dos números de identificação 6

Sistema do BI foi COPIADO do ISBN

a10 a9 a8 a7 a6 a5 a4 a3 a2 a1

n.º identificação alg. controle

X10 x9 x8 x7 x6 x5 x4 x3 x2 x1

A soma tem que ser divisível por 11

Maio 2003 A álgebra dos números de identificação 6Maio 2003 A álgebra dos números de identificação 6

6 2 3 5 0 0 8 ?

x8 x7 x6 x5 x4 x3 x2 x1

Sistema do BI foi COPIADO do ISBN

48 14 18 25 0 0 16 ?

121

8 8

00

Maio 2003 A álgebra dos números de identificação 6Maio 2003 A álgebra dos números de identificação 6

Sistema do BI foi COPIADO do ISBN

a1 {0,1,2,3,4,5,6,7,8,9} {X}

Disparate!a1 = 10

mas,mal copiado!

Maio 2003 A álgebra dos números de identificação 6Maio 2003 A álgebra dos números de identificação 6

6 2 3 5 0 0 3 0

x8 x7 x6 x5 x4 x3 x2 x1

111 101

Maio 2003 A álgebra dos números de identificação 6Maio 2003 A álgebra dos números de identificação 6

O sistema do BI não detecta

todos os “erros singulares” !!!

88

Maio 2003 A álgebra dos números de identificação 7Maio 2003 A álgebra dos números de identificação 7

Sistema do número identif. fiscal (NIF)

é igual ao do BI

Disparate!

Maio 2003 A álgebra dos números de identificação 8Maio 2003 A álgebra dos números de identificação 8

Os matemáticos criaram métodos muito eficientes.

Porque razão se continua a usar sistemas tão primitivos?

Maio 2003 A álgebra dos números de identificação 9Maio 2003 A álgebra dos números de identificação 9

Sistemas de identificação módulo m

Tipo de erro Condições

Singulares: ai a’i mdc(pi,m)=1

Troca de algarismos: ai+1 ai ai ai+1 mdc(pi+1-pi,m)=1

an an-1 ... a2 a1

pn an + pn-1 an-1 + ... + p2 a2 + p1 a1

é divisível por m

Maio 2003 A álgebra dos números de identificação 10Maio 2003 A álgebra dos números de identificação 10

Generalização

n(an) + n-1(an-1) + ... + 2(a2) +

1(a1)

é divisível por m

EFICIÊNCIA 97,8%m=10

i :ai pi ai

{0,1,...,m-1} {0,1,...,m-1}

an an-1 ... a2

a1

Maio 2003 A álgebra dos números de identificação 11Maio 2003 A álgebra dos números de identificação 11

Aritmética Modular

Z10 ={0,1,2,...,9}

n(an) 10 n-1(an-1) 10 ... 10 2(a2) 10 1(a1) = 0

a+b divisível por 10 a 10 b = 0

Espiral Modular

Maio 2003 A álgebra dos números de identificação 12Maio 2003 A álgebra dos números de identificação 12

an an-1 ... a2 a1

n(an) n-1(an-1) ... 2(a2) 1(a1) = 0

Para cada m existe sempre um grupo comEFICIÊNCIA = 100%

(Z10 , 10) outros grupos (G,)

Generalização

Maio 2003 A álgebra dos números de identificação 13Maio 2003 A álgebra dos números de identificação 13

Grupo Diedral D5grupo das simetrias de um pentágono regular

0 1 2 3 4 5 6 7 8 9

0123456789

0 1 2 3 4 5 6 7 8 9

3 4 0 1 7 8 9 5 64 0 1 2 8 9 5 6 70 1 2 3 9 5 6 7 89 8 7 6 0 4 3 2 15 9 8 7 1 0 4 3 26 5 9 8 2 1 0 4 37 6 5 9 3 2 1 0 48 7 6 5 4 3 2 1 0

r1

r2

r3

r4

r5

1=72º

0 1 2 3 4 r1 r2 r3 r4 r5

3 4 0 6 7 8 9 5

2=144º

3=216º

4=288º

0=0º

123456789

2

C D

A

EBE B

CD

A

A

B

E

C

D

A

B E

C D

m=10

AA

Maio 2003 A álgebra dos números de identificação 14Maio 2003 A álgebra dos números de identificação 14

MARCO ALEMÃO

Maio 2003 A álgebra dos números de identificação 15Maio 2003 A álgebra dos números de identificação 15

L 4 Finlândia

M 5 Portugal

N 6 Áustria

P 8 Holanda

R 1 Luxemburgo

S 2 Itália

Maio 2003 A álgebra dos números de identificação 15Maio 2003 A álgebra dos números de identificação 15

T 3 Irlanda

U 4 França

V 5 Espanha

X 7 Alemanha

Y 8 Grécia

Z 9 Bélgica

M3132681541?

Maio 2003 A álgebra dos números de identificação 15Maio 2003 A álgebra dos números de identificação 15

M3132681541?

5+3+1+3+2+6+8+1+5+4+1+?

39

“noves fora” 3

div. por 9

?=6

Maio 2003 A álgebra dos números de identificação 15Maio 2003 A álgebra dos números de identificação 15

M31326815416

Maio 2003 A álgebra dos números de identificação FIMMaio 2003 A álgebra dos números de identificação FIM

Não detecta os erros singulares 0 9

9 0

Não detecta nenhuma troca!!!

Disparate!