Saltar a contenido

Códigos de corrección de errores

El DNI

El DNI (Documento Nacional de Identidad) es «el documento que acredita […] la identidad, los datos personales que en él aparecen y la nacionalidad española de su titular»1. Cada DNI tiene asignado un código formado por 8 cifras y 1 letra. La letra sirve como dígito de control, y se asigna en función del resto obtenido al dividir el número entre 23, según la tabla.

Resto 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
Letra T R W A G M Y F P D X B N J Z S Q V H L C K E

Calculadora letra DNI

 -     

ISBN

Coge un libro y busca su código de barras. Encontrarás un número de 10 o 13 cifras: es el ISBN (International Standard Book Number). El ISBN identifica a cada edición de un libro, y puesto que es un código que va a ser leído tanto por humanos como por máquinas, incluye un dígito de control que permite detectar errores.

Formato del ISBN

Calentamiento

  • ¿Cuánto hay que sumar a 37 para obtener un múltiplo de 10?
  • ¿Cuánto hay que sumar a 15 para obtener un múltiplo de 8?
  • ¿Cuánto hay que sumar a 23 para obtener un múltiplo de 17?
  • ¿Cuánto hay que sumar a 14293 para obtener un múltiplo de 23?

ISBN-10

El ISBN-10 está formado por 10 cifras: 9 que identifican al libro más 1 dígito de control. Para calcular el dígito de control, debemos saber que un ISBN es válido si cumple la siguiente ecuación.

\[ 10x_1+9x_2+8x_3+7x_4+6x_5+5x_6+4x_7+3x_8+2x_9+x_{10} \equiv 0 \pmod{11} \]

Es decir, al multiplicar el primer dígito por 10, el segundo por 9, el tercero por 8, …, el noveno por 2 y el décimo (el dígito de control) por 1, y sumar esos productos, el resultado ha de ser múltiplo de 11.

Descubre el error

  1. ¿Son válidos estos ISBN-10?
    1. 0801866103
    2. 0486261537
    3. 8478443746
    4. 8467552270
  2. Calcula el dígito de control correcto para los ISBN inválidos.
  3. ¿Puedes corregir los ISBN inválidos cambiando un dígito que no sea el dígito de control?
Solución
  1. Sí, no, sí, no.

  2. En el b, la suma de las 9 primeras cifras por sus pesos es de

    \[ 10 \times 0 + 9 \times 4 + 8 \times 8 + 7 \times 6 + 6 \times 2 + 5 \times 6 + 4 \times 1 + 3 \times 5 + 2 \times 3 = 209 \]

    Como \(209 = 19 \times 11\), la suma ya es un múltiplo de 11 y no hace falta sumar nada. Por lo tanto, el dígito de control correcto es 0, y el ISBN válido sería 0486261530.

    En el d, la suma es

    \[ 10 \times 8 + 9 \times 4 + 8 \times 6 + 7 \times 7 + 6 \times 5 + 5 \times 5 + 4 \times 2 + 3 \times 2 + 2 \times 7 = 296 \]

    Como \(296 = 286 + 10 = 26 \times 11 + 10\), nos pasamos en 10 unidades del anterior múltiplo de 11 y debemos sumar 1 para alcanzar el siguiente múltiplo. El dígito de control ha de ser 1, y el ISBN válido es 8467552271.

  3. En el b, la suma completa da \(209+7=216=19\times11+7\). Para eliminar ese resto de 7, podemos restar 1 unidad a la cifra cuyo peso es 7 (la cuarta). Es decir, cambiar el 6 por un 5. Así, estamos restando 7 a la suma total (pasamos de \(7 \times 6\) a \(7 \times 5\)) y el resultado ya es un ISBN válido, 0485261537. ¿Hay otras opciones?

    En el d, la suma completa es \(296+0=296=286+10=26\times11+10\). Para eliminar ese resto de 10, podemos restar 1 unidad a la cifra de peso 10 (la primera) o 2 unidades a la cifra de peso 5 (la sexta). En el primer caso obtendríamos el ISBN 7467552270, y en el segundo, 8467532270. ¿Qué otras opciones hay?

ISBN-13

En el ISBN-13 los pesos son más sencillos, 1 para las cifras impares y 3 para las pares. Al multiplicar cada cifra por su peso y sumar todos los productos, el resultado ha de ser múltiplo de 10.

\[ x_1+3x_2+x_3+3x_4+x_5+3x_6+x_7+3x_8+x_9+3x_{10}+x_{11}+3x_{12}+x_{13} \equiv 0 \pmod{10} \]

Más ideas

Para cada tipo de ISBN:

  • ¿Qué tipo de error puede detectar?
  • ¿Qué tipo de error puede corregir?
  • ¿Podemos obtener un ISBN válido si introducimos un dígito erróneo?
  • ¿Y si intercambiamos dos dígitos adyacentes?

Códigos de Hamming

Hasta ahora hemos visto códigos que pueden detectar errores, pero no corregirlos. Los códigos de Hamming, inventados por Richard Hamming en 1950, son una familia de códigos que permiten o bien detectar errores de 1 o 2 bits o bien corregir errores de 1 bit sin detectar otros errores. Hablamos de bits porque son códigos binarios, en los que cada cifra es un bit (binary digit, 0 o 1).

Para comprender bien los códigos de Hamming, veamos algunos códigos que se usaban anteriormente.

Paridad

La paridad añade un único dígito de control (0 o 1) que indica si el número de unos en el mensaje anterior es par (0) o impar (1), de manera que el total de 1s en el código sea siempre par.

Por ejemplo, al mensaje \(\texttt{1011}\) se le añadiría la paridad 1, y quedaría \(\texttt{10111}\). En un mensaje binario, cambiar un único dígito cambia la paridad. Por lo tanto, este método puede detectar una cantidad impar de errores. Por ejemplo, cambiando el primer dígito obtenemos \(\texttt{00111}\), que es inválido, ya que contiene una cantidad impar de 1s. En cambio, si en nuestro código \(\texttt{10111}\) cambian dos dígitos, y pasa a ser \(\texttt{11011}\), el código sigue siendo válido y no se detecta como error.

¿Errores y aciertos?

Averigua si cada uno de los códigos siguientes es válido. Después, imagina que todos son incorrectos (es decir, no son el código que se pretendía transmitir) y escribe dos posibilidades para el código correcto.

  1. \(\texttt{101011}\)
  2. \(\texttt{001101}\)
  3. \(\texttt{111101}\)
  4. \(\texttt{11000011}\)

Dos de cinco

Estos códigos usan cinco bits que constan de tres 0s y dos 1s. Esto proporciona \({5 \choose 2} = 10\) combinaciones, suficientes para representar las cifras del 0 al 9. Este sistema puede detectar todos los errores de 1 bit, todos los errores de una cantidad impar de bits y algunos errores de una cantidad par de bits (por ejemplo, cambiar los dos 1s). Sin embargo, este código no puede corregir ningún error.

Un ejemplo de codificación es el siguiente:

Cifra Código Cifra Código
1 \(\texttt{11000}\) 6 \(\texttt{10001}\)
2 \(\texttt{10100}\) 7 \(\texttt{01001}\)
3 \(\texttt{10010}\) 8 \(\texttt{00101}\)
4 \(\texttt{01010}\) 9 \(\texttt{00011}\)
5 \(\texttt{00110}\) 0 \(\texttt{01100}\)

Teléfono equivocado

Un amigo me ha pasado su número de teléfono usando la codificación de la tabla anterior. Lo he intentado descifrar, ¡pero me parece que tiene errores! Si sabemos que solo hay un bit erróneo, ¿cuál puede ser su número de teléfono?

\[ \texttt{00011,11000,00110,00101,01100,01001,00101,01101,01100} \]
Solución

Todas las cifras corresponden a códigos correctos, excepto la penúltima, ya que \(\texttt{01101}\) tiene tres 1s en vez de dos. Sabiendo que solo hay un error, este debe ser uno de los 1s, que debería ser un 0. Cambiando cada uno de ellos, tenemos tres opciones:

  • \(\texttt{00101} = 8\)
  • \(\texttt{01001} = 7\)
  • \(\texttt{01100} = 0\)

Por lo tanto, el teléfono de mi amigo es de la forma \(\text{9158078X0}\), donde \(\text{X}\in\{0,7,8\}\).

Repetición

Otro código usado anteriormente consistía en repetir la cifra un cierto número de veces, por ejemplo 3. Para transmitir el mensaje \(\texttt{1}\), el código enviado sería \(\texttt{111}\). Cualquier secuencia de tres cifras no todas iguales sería detectada como un error. Suponiendo que lo más probable es que haya un único error por palabra, los códigos \(\texttt{001}\), \(\texttt{010}\), \(\texttt{100}\) se interpretarían como \(\texttt{1}\), por lo que errores en un solo bit pueden ser corregidos con este código. En cambio, si hubiera dos bits erróneos, el código sería interpretado incorrectamente y no se detectaría ningún error.

Probabilidad de error

Hemos recibido el código \(\texttt{101}\) y lo hemos interpretado como el mensaje \(\texttt{1}\). Si la probabilidad de que ocurra un error en un dígito cualquiera es \(p\), ¿cuál es la probabilidad de que el mensaje original fuera \(\texttt{0}\)?

Solución

Si el mensaje original era \(\texttt{0}\), ha habido dos errores. La probabilidad de que eso ocurra es \(p^2(1-p)\) (dos errores y un no-error). Por otro lado, la probabilidad de que ocurra un único error es \(p(1-p)^2\), es decir, \(\frac{1-p}{p}\) veces la de que haya dos errores. Para \(p = 0{,}05\) es 19 veces más probable que ocurra un único error a que ocurran dos. Otro modo de verlo: de cada veinte códigos que contengan errores, uno de ellos se corregirá erróneamente.

  1. Ideas Básicas, www.dnielectronico.es ↩