I.E.S. Izpisúa Belmonte

Departamento de Matemáticas
Proyecto ForMate

Proyecto  ForMate

SESIONES  20/27-02-2007

 CÓDIGOS PARA DETECTAR ERRORES.

Javier Serrano 1

Curso 2006/2007

 

Congruencias Códigos numéricos Detección de errores Otros ejercicios sobre códigos

 

 

1  INTRODUCCIÓN: CONGRUENCIAS.

Dado cualquier número entero n, llamamos sacar sietes de n al procedimiento consiste en restar o sumar 7 (según n sea positivo o negativo, respectivamente) a n de manera repetida hasta que el resultado de la última operación, r, sea un número entero comprendido entre 0 y 6, ambos inclusive, es decir, hasta que se cumpla que 0 ≤ r < 7.

Ejercicio 1.- Sacar los sietes de n=38

38-7=31; 31-7=24; 24-7=17; 17-7=10; 10-7=3. Entonces r=3.

Se dice que n es congruente con r módulo 7 y se escribe nº r (mod 7). En el ejemplo anterior escribiríamos 38º3 (mod 7).

Ejercicio 2.- Sacar los sietes de los números -45, 77, -8 y 40.

De la misma forma, podemos sacar de un número n los ochos, los dieces, los veintes...

Dado cualquier número entero n, el procedimiento llamado sacar emes de n consiste en restar o sumar m a n de manera repetida hasta que el resultado de la última operación, r, sea un número entero comprendido entre 0 y m-1, ambos inclusive. Se dirá que n es congruente con r módulo m y se escribirá n  º  r (mod m).

Ejercicio 3.- Sacar los nueves y los onces de los números 22, 27, -32, 99


Ejercicio 4.- Sacar los cincos del número 142.

El último ejercicio pone de manifiesto que si n es un número grande, el procedimiento descrito puede resultar demasiado largo. Para acortarlo, proponemos dos métodos, que podrán emplearse según sean las circunstancias del problema.

Método de la división: Para calcular n  º  r (mod m), basta con dividir n entre m. El resto de la división es el valor de r buscado.

Ejercicio 5.- Encontrar el valor de r en la congruencia 458  º  r (mod 12)

Al dividir 458 entre 12 se obtiene 38 como cociente y 2 como resto, es decir, 458=38·12+2. Entonces, r=2 y 458  º  2 (mod 12).

Método de la separación: Para calcular n  º  r (mod m) podemos separar el número n en sumandos, calcular la congruencia módulo m para cada sumando y sumar los resultados (volviendo a calcular la congruencia módulo m si fuera necesario).

Ejercicio 6.- Calcula 458  º  r (mod 12)

Hacemos, por ejemplo, 458=400+50+8. Dividimos 400 entre 12 y nos quedamos con el resto (le sacamos los doces). Da 4. Lo mismo hacemos con 50: le sacamos los doces y da 2. Al 8 no le podemos sacar doces. Entonces, tenemos que 458 º 400+50+8  º  4+2+8  º  14  º  2 (mod 12).

Ejercicio 7.- Calcula r en las siguientes congruencias:

  1. 28  º  r (mod 10)
  2. 5040  º  r (mod 11)
  3. 2500  º  r (mod 9)
  4. 456  º  r (mod 5)

Ejercicio 8.- ¿Para qué tipo de números n se cumple que n  º  0 (mod 5)?¿Y n  º  0 (mod 8)? ¿Y n  º  0 (mod m)?

Ejercicio 9.- Confecciona las tablas de sumar y de multiplicar módulo 6. ¿Son operaciones conmutativas como la suma y el producto usuales de números enteros?

Ejercicio 10.- Busca un número n tal que n  º  3 (mod 8). ¿Es único este número? ¿Cuántos valores podríamos encontrar para n?
Ejercicio 11.- Si a  º  r (mod m) y b  º  r (mod m), se puede escribir a  º  b (mod m). ¿Qué se puede decir de a-b módulo m? Revisa los ejercicios anteriores antes de contestar.
Ejercicio 12.- Se sabe que 132?5  º  5 (mod 6), pero se ha borrado un dígito. Calcúlalo. ¿Hay más de una solución? Responde a las mismas cuestiones sabiendo ahora que 132?7  º  2 (mod 6).
Ejercicio 13.- Encuentra el dígito que falta en 1?429  º  4 (mod 11).

Las dos propiedades de las congruencias que más usaremos en lo que sigue son:

Ley de cancelación:
Si a+c  º  b+c (mod m), entonces a  º  b (mod m) "cÎZ.
Ley de simplificación:
Si a·c  º  b·c (mod m), entonces a  º  b (mod m´), donde m´ resulta de dividir m entre mcd(m, c). Esto es válido para cualquier número c que no sea congruente con cero módulo m.

La Ley de cancelación nos dice que las congruencias se llevan bien con la suma de números enteros. Si dos números son congruentes, podemos sumarles (o restarles) a ambos el mismo número entero y los resultados de las sumas (o las restas) siguen siendo congruentes y, todo, sin cambiar el módulo de la congruencia. En cambio, la Ley de simplificación nos dice que las congruencias ya no se llevan tan bien con el producto (o la división) de enteros. Para dividir los dos miembros de una congruencia entre el mismo número, es necesario dividir también el módulo. El módulo permanecerá intacto sólo en los casos en los que simplifiquemos entre un número que no tenga divisores comunes con él.

Subir al principio

2  CÓDIGOS NUMÉRICOS

Los libros, las botellas de agua, las tarjetas de crédito, las cuentas bancarias... llevan una numeración que está pensada para evitar errores al ser introducida en los ordenadores. El propio sistema de numeración, al que llamaremos algoritmo, lleva implícito un método de autocontrol que nos informa de algunos posibles errores al teclear o escribir el código. Vamos a conocer algunos de los algoritmos de codificación de los más empleados.

 2.1  Cheque bancarios


El código de los cheques bancarios es del tipo
N-c
donde N es un número de siete cifras y c es un número de una cifra tales que
N  º  c (mod 7).

El dígito c se llama dígito de control y sirve para controlar que el número N esté bien tecleado.
 

Ejercicio 14.- Calcula el dígito de control de los siguientes cheques bancarios:
  1. 1407924-c
  2. 0561279-c
Ejercicio 15.- Los dígitos de control pueden ayudar a detectar números borrados o irreconocibles. Halla el número borrado en los siguientes cheques bancarios:
  1. 2481?57-4
  2. 004?722-4

2.2  Código de barras (Sistema Europeo, EAN)


Este código es del tipo
a1-a2a3a4a5a6a7-a8a9a10a11a12a13
tal que
(a1+a3+a5+a7+a9+a11+a13)+3(a2+a4+a6+a8+a10+a12)  º  0
(mod 10)

Los primeros dígitos especifican el país o área geográfica a la que pertenece el fabricante del producto. Para España se utilizan los dígitos 84. El siguiente grupo de dígitos (cuyo tamaño puede ser variable) corresponden al fabricante. El último grupo de dígitos corresponden al producto específico del que estamos leyendo su código de barras. El último dígito, a13, es el dígito de control c que se pone para que la operación anterior sea un múltiplo de 10, es decir, congruente con 0 módulo 10.

Ejercicio 16.- Halla los dígitos de control de los códigos de barras siguientes:
  1. Cuaderno ENRI: 8-412771-03017c
  2. Toallitas infantiles Deliplus: 8-480000-77541c
  3. Coca-Cola: 5-449000-00099c
  4. Agua Bezoya: 8-410128-00040c
  5. CD de Sony: 5-099747-49982c
Ejercicio 17.- ¿Son correctos los dígitos de barras siguientes?
  1. 9-788748-290208
  2. 8-410240-210402
Ejercicio 18.- Halla el número borrado en los siguientes códigos de barras:
  1. Barra de pan Mercadona: 8-480000-8?5482
  2. Batido de chocolate Hacendado: 8-480000-?00696

2.3  Códigos que identifican libros

2.3.1  El ISBN



Es un código del tipo
a1a2-a3a4a5-a6a7a8a9a10
tal que
10a1+9a2+8a3+7a4+6a5+5a6+4a7+3a8+2a9+a10  º  0 (mod 11)

Los grupos de dígitos pueden ser distintos. El dígito a10 puede interpretarse como el dígito de control c que se pone para que la operación anterior sea un múltiplo de 11. A veces, es necesario que a10=10, pero como 10 está compuesto por dos dígitos, se sustituye este valor por el número romano X.

Igual que en el código de barras, los primeros dígitos identifican el país o zona geográfica del editor del libro (para España también se usa el 84). El siguiente grupo se refiere al editor del libro y el último grupo al título del mismo.

Ejercicio 19.- Halla los dígitos de control de los siguientes ISBN:

  1. Matemáticas en la vida cotidiana: 84-7829-020-c
  2. No digas que fue un sueño: 84-320-8764-c
  3. Las crónicas de Arnia: 84-672-1507-c
Ejercicio 20.- Halla el dígito borrado en los siguientes ISBN:
  1. 84-743?-408-4
  2. 84-?223-844-X

2.3.2  El ISBN-13

Con la intención de que los códigos ISBN se parezcan lo máximo posible a los códigos de barras y simplificar y unificar así la gestión de códigos (por ejemplo, para comercios en los que no sólo se vendan libros), la comunidad internacional ha propuesto un nuevo algoritmo para el ISBN, llamado ISBN-13, idéntico al algoritmo del código de barras que entrará en vigor en 2007. El código ISBN-13 consta de trece dígitos, como los códigos de barras. Ya que los primeros dígitos del código de barras se refieren al país del fabricante del producto, los tres primeros del ISBN-13 serán siempre 978, lo que identifica al producto como un libro (estos tres dígitos son conocidos por el nombre de bookland, es decir, país de los libros). Por tanto, para adecuar los antiguos ISBN al nuevo método, se les añadirá 978 como los tres primeros dígitos y se recalculará el dígito de control.

Ejercicio 21.- Recalcula los ISBN de los libros que aparecen en el ejercicio 2.3.1

2.4  Código de las tarjetas de crédito (CODABAR)


Este código es del tipo
a1a2a3a4-a5a6a7a8-a9a10a11a12-a13a14a15a16
tal que
(a2+a4+a6+a8+a10+a12+a14+a16)+2(a1+a3+a5+a7+a9+a11+a13+a15)+número de dígitos en posición impar mayores que 4  º  0
(mod 10)

Ejercicio 22.- ¿Son válidos los siguientes códigos de tarjetas de crédito?
  1. 4599-8834-3278-8311
  2. 4599-8834-3278-8511
Ejercicio 23.- Halla el dígito borrado de las siguientes tarjetas de crédito:
  1. 1007-8606-2?90-1234
  2. 6540-98?0-7654-0103

2.5  Códigos de cuentas bancarias


Este código es del tipo
a3a4a5a6-a7a8a9a10-a0b0-b1b2b3b4b5b6b7b8b9b10
tal que
4a3+8a4+5a5+10a6+9a7+7a8+3a9+6a10+a0  º  0 (mod11)
y
b1+2b2+4b3+8b4+5b5+10b6+9b7+7b8+3b9+6b10+b0  º  0(mod 11)

Para recordar este algoritmo, nótese que cada ai y cada bi van multiplicados por el doble (calculado módulo 11) del número que multiplica a ai-1 o a bi-1, salvo en los casos de a1 y b1, que van multiplicados por 1. En este sentido, se considera que el subíndice 0 vale 11.

Los dígitos de control son a0 y b0. Pudiera ser que tanto uno como otro deban valer 10. En estos casos, se sustituye este valor por un 1, lo que crea cierta ambigüedad en el algoritmo.
 

Ejercicio 24.- Calcula los dígitos de control de las siguientes cuentas bancarias de solidaridad con las víctimas del atentado terrorista de Madrid del 11 de marzo de 2004:
  1. BBVA: 0182-5570-cc-0201502661
  2. Caja de Ahorros El Monte: 2098-0009-cc-0132028383

2.6  Número de identificación fiscal (NIF)


Este código es del tipo
N-L
tal que
N es un número de ocho dígitos (que constituye el DNI de cada persona)
y L es una letra que se asigna calculando r en
N  º  r (mod 23)
y aplicando la siguiente tabla.

Tabla de asignación de letras del NIF.
r 0 1 2 3 4 5 6 7 8 9 10
L T R W A G M Y F P D X
r 11 12 13 14 15 16 17 18 19 20 21 22
L B N J Z S Q V H L C K E

 

Ejercicio 25.- Calcula el NIF de los siguientes DNI:
  1. 27464129-?
  2. 05253478-?
Ejercicio 26.- ¿Cuál es el dígito borrado en el NIF 527?3705-P?

Subir al principio

3  DETECCIÓN DE ERRORES

Al teclear un código en un ordenador, los dos errores más frecuentes que se cometen son:
  • Cambiar el valor de un solo dígito del código.
  • Intercambiar dos dígitos consecutivos del código.

Algunos de los algoritmos presentados son capaces de detectar estos errores y otros no. La manera de detectar un error es comprobar si el dígito de control es correcto. Imaginemos que al teclear el número de cheque 4501282-2, cometemos un error y tecleamos 4503282-2. El programa de ordenador que estamos utilizando debe llevar un subprograma que, inmediatamente, calcula el dígito de control, lo compara con el dígito de control tecleado y, en caso de no ser iguales, lanza un mensaje de aviso.

Ejercicio 27.- Al introducir el cheque 4501282-2 en el ordenador, se ha tecleado por error el código 4503282-2. ¿Detectará el ordenador este error? ¿Por qué?
 
Ejercicio 28.- Al introducir el cheque 4501282-2 en el ordenador, se ha tecleado por error el código 4508282-2. ¿Detectará el ordenador este error? ¿Por qué? ¿Qué tipo de errores de un dígito no detectará este algoritmo?
 
Ejercicio 29.- ¿Detectará el intercambio de dos cifras consecutivas el algoritmo del código de los cheques bancarios?
 
Ejercicio 30.- ¿Detecta el algoritmo del código de barras todos los errores de un solo dígito?
 
Ejercicio 31.- El algoritmo del código de barras no es capaz de detectar algunos errores producidos por intercambio de dos dígitos consecutivos: averigua en qué casos puede producirse este hecho.
 
Ejercicio 32.- Investiga si el algoritmo del ISBN es capaz de detectar todos los errores de un solo dígito y los de intercambio de dos dígitos consecutivos.

Subir al principio

4  OTROS EJERCICIOS SOBRE CÓDIGOS

Ejercicio 33.- Los cheques de viaje de American Express usan como dígito de control el resto de dividir entre 9 el número de identificación del cheque. Calcula el dígito de control del cheque con número de identificación 210687315. ¿Detecta todos los errores de un solo dígito? ¿Detecta las trasposiciones de dos dígitos consecutivos?
 
Ejercicio 34.- Imagina que los tres últimos dígitos del número de socio de un equipo de fútbol de una mujer que nació en el mes m y en el día d son el resultado de 40(m-1)+d+500, mientras que para los hombres la fórmula es 40(m-1)+d. Para ambos, los dígitos cuarto y quinto comenzando por el final y en este orden indican el año de nacimiento. Encuentra las fechas de nacimiento de las personas cuyos últimos cinco dígitos son 17218 y 56953.
 
Ejercicio 35.- Un código de identificación tiene 3 dígitos abc y un dígito de control d; se forma por tanto el número abc-d. El dígito de control se elige de tal manera que la suma de los dígitos que ocupan los lugares pares, más el doble de la suma de los que ocupan los lugares impares, más el número de dígitos mayores que cuatro que están en lugares impares sea múltiplo de 10.
  1. Calcula el dígito de control para el número de identificación 834.
  2. Se sabe que hay un error en el segundo dígito de 486-4. ¿Puedes corregirlo?
  3. Estudia si este algoritmo detecta todos los errores de un solo dígito.
Ejercicio 36.- Investiga sobre el algoritmo del NIF:
  1. Encuentra el NIF del DNI número 12.326.413
  2. ¿Detecta este algoritmo todos los errores de un solo dígito?
  3. ¿Detecta este algoritmo todos los errores de intercambio de dos cifras consecutivas?
Ejercicio 37.- Explica por qué el algoritmo de las cuentas bancarias detectará el error 751¼ por 157¼, pero no lo hará el algoritmo del código de barras.
 
Ejercicio 38.- El ISBN 0-669-03925-4 es el resultado de la trasposición de dos dígitos adyacentes que no son ni el primero ni el último. Determina el ISBN correcto.

Notas:

1Basado en un tema preparado por Eugenio Hernández, de la Universidad Complutense de Madrid, para el proyecto ESTALMAT

Subir al principio

Página principal