Lo queramos o no, los seres humanos vamos dejando huella por todas partes: dejamos huella en la gente a la que conocemos, en los amigos, en los enemigos… y en los CDs; y, al igual que una huella dejada por una persona en otra puede producir en esta última un cambio radical de su forma de apreciar el mundo, puede cambiar por completo su estructura de valores, creencias, miedos, etc., también una huella en un CD puede transformar totalmente la información almacenada en el mismo… ¿Qué hacer? En el caso de la huella dejada por una persona en otra, las matemáticas no pueden decir ni “mu”, habrá que hacer uso de otros recursos si es que queremos cambiar eso; sin embargo, las matemáticas sí que tienen mucho que decir en el caso del CD.
Fuente de la imagen: http://columbia.edu
Un CD no es nada más que un Disco Compacto, un disco con un montón de información almacenada en espiral (si pusiéramos recta la espiral su longitud sería de más o menos ¡5 km!) en forma de “valles” y “llanuras” (que, matemáticamente, podemos hacer corresponder con ceros y unos). El lector láser es el encargado de “leer” estos “valles” y “llanuras” para poder “traducirlo” a un lenguaje comprensible para el ser humano (una melodía, una imagen, palabras…). Lógicamente, el lector láser no es infalible en su lectura, sobre todo si hay algún tipo de interferencia, como una huella, que puede cambiar la disposición de ceros y unos y, con ello, la información final. ¿Cómo hacer frente a estos errores? Pues mediante códigos correctores de errores.
La tecnología digital, tan imprescindible hoy en día, almacena la información, precisamente, en forma de, para entendernos, ceros y unos, es decir, únicamente dos símbolos. Gracias a ello muchos procedimientos, como la corrección de errores, se pueden matematizar fácilmente. Veamos qué serie de pasos hay que seguir para ello:
- Antes de corregir hay que detectar el error
- Para detectar el error hay que introducir información redundante
- Al introducir información redundante no todas las “palabras” de nuestro código serán válidas
- La corrección de errores se basa en la “distancia” entre estas “palabras”
- Si la lista recibida no es una “palabra” válida, le asignaremos la “palabra” más “cercana”.
Veamos más en profundidad cada uno de ellos:
Antes de corregir hay que detectar el error
Creo que este paso no requiere ninguna aclaración.
Para detectar el error hay que introducir información redundante
¿Cómo hacerlo? Por ejemplo, podríamos repetir cada lista de información, de manera que si la repetición no coincide con el original, hay algún error. Claro, esto alargaría demasiado el mensaje, así que tendremos que buscar otras formas. Aquí es donde entran en escena el NIF, los códigos de barras, el Código Cuenta Cliente de los bancos, el ISBN… Todos ellos contienen información redundante que nos “avisa” de si es correcto o no en algunos casos determinados. Por ejemplo, veamos un poco el caso del NIF. El número del DNI está compuesto de 8 cifras. Pues bien, cualquier número de 8 cifras podría ser un DNI válido, de tal manera que si nos confundimos y en lugar de 71446957 escribimos 71449657, no habría forma de detectar el error. La letra al final de la ristra de dígitos es la información redundante que se usa para evitar estas situaciones, y lo que nos indica en realidad es el resto de dividir el número del DNI entre 23 (cada uno de los posibles restos tiene asociado una letra distinta). Como vemos, el resto es una información redundante, es una información que ya viene implícita en el número del DNI.
Fuente de la imagen: http://lewebpedagogique.com
Lo mismo ocurre con los otros números y códigos mencionados más arriba. Hay información sobre ello en las referencias.
Al introducir información redundante no todas las “palabras” de nuestro código serán válidas
En la lengua española no vale cualquier palabra. Por ejemplo, “acita” no es una palabra válida a pesar de que, por la construcción, podría serlo… Algo parecido ocurre cuando introducimos información redundante en un código. En el ejemplo del DNI, que es el que nos ocupa, aunque cualquier número de 8 cifras se puede dar por válido, no son correctas cualesquiera “palabras” formadas por 8 dígitos y una letra. Así, aunque 71449657 y 71446957 son ambos DNIs válidos, no ocurre lo mismo con 71449657L y 71446957L: el primero es un NIF válido (el resto de 71449657 entre 23 es 19, que se corresponde con la letra L), pero no así el segundo (el resto en este caso es 10, que tiene asociada la letra X y no la L).
Esto nos permite detectar el error si hemos llegado a una “palabra” no válida (un procesador de textos, por ejemplo, es capaz de detectar un error y subrayarlo en rojo porque “conoce” las palabras que son válidas y las que no. Claro, a veces no nos corrige algo aunque sea erróneo porque, a pesar de que no era lo que queríamos decir, sí que es una palabra válida. Eso también puede ocurrir en el caso del DNI, pero no es lo normal).
La corrección de errores se basa en la “distancia” entre estas “palabras” válidas.
Puede que el lector sólo conozca lo que se denomina distancia euclídea y piense que las distancias se miden únicamente en metros o en cualquier otra medida de longitud… Lo cierto es que ésta no es la única distancia posible, por lo menos en matemáticas. A los matemáticos les gusta generalizar los conceptos para así poder generalizar también las propiedades que se desprenden de esos conceptos a diversos contextos. Un ejemplo de distancia distinta a la habitual nos la mostraba hace tiempo emulenews en su blog.
Volviendo al diccionario y al idioma español. ¿Qué palabras te parecen más cercanas, cana y casa o cana y coto? Desde luego la primera pareja es más “cercana” de alguna manera, porque sólo se diferencian en una letra.
Veamos un ejemplo binario. ¿Qué “palabras” están a menor “distancia”, 11011 y 11010 ó 11011 y 00101? Salta a la vista que la primera pareja vuelve a estar a menor “distancia”…
Surge así la denominada distancia de Hamming, que es el número de posiciones de dos palabras que tienen bit diferente (si en una es 0, en la otra es 1 y al revés). Así, la primera pareja está a distancia 1 porque difieren en la última posición y la segunda pareja a distancia 4, porque difieren en todas las posiciones menos en la última.
Si la lista recibida no es una “palabra” válida, le asignaremos la “palabra” más “cercana”.
Imaginemos que hemos escrito “cisa”. El procesador de textos nos la subraya de rojo porque no es una palabra válida y nos ofrece varias palabras válidas alternativas para corregir, pero claro, cualquier palabra del español no nos es ofrecida como alternativa, sólo aquellas palabras que están “cerca” de la palabra errónea, como sisa, cesa, cima, cita, ciña, casa… Cojamos otra palabra, por ejemplo, polabra. En este caso el procesador sólo nos da una alternativa, “palabra”, porque es la única palabra válida que se encuentra cerca de polabra.
Imaginemos ahora un ejemplo parecido con las palabras binarias de 5 cifras. Imaginemos que sólo son válidas las palabras 11111 y 00000. En este caso, si recibimos la palabra 11110, la podemos cambiar por 11111, que está más cerca que 00000, sin demasiado riesgo de confundirnos.
*************
Pues en todos estos conceptos e ideas previas se basa un código corrector de errores. Veamos ahora un ejemplo, el código Hamming (7,4), que, aunque es muy rudimentario, nos puede dar una idea mayor de cómo funcionan estos códigos:
-
Antonia quiere enviar el siguiente mensaje: “MENSAJE”, a su amigo Benjamín.
-
Para ello codifica el mensaje a través de, por ejemplo, el código ASCII, del que aparecen las equivalencias aquí abajo:
|
Binario |
Decimal |
Representación |
Binario |
Decimal |
Representación |
|
01000001 |
65 |
A |
01001110 |
78 |
N |
|
01000010 |
66 |
B |
01001111 |
79 |
O |
|
01000011 |
67 |
C |
01010000 |
80 |
P |
|
01000100 |
68 |
D |
01010001 |
81 |
Q |
|
01000101 |
69 |
E |
01010010 |
82 |
R |
|
01000110 |
70 |
F |
01010011 |
83 |
S |
|
01000111 |
71 |
G |
01010100 |
84 |
T |
|
01001000 |
72 |
H |
01010101 |
85 |
U |
|
01001001 |
73 |
I |
01010110 |
86 |
V |
|
01001010 |
74 |
J |
01010111 |
87 |
W |
|
01001011 |
75 |
K |
01011000 |
88 |
X |
|
01001100 |
76 |
L |
01011001 |
89 |
Y |
|
01001101 |
77 |
M |
01011010 |
90 |
Z |
Dando como resultado la siguiente lista de ceros y unos:
01001101010001010100111001010011010000010100101001000101
-
Ahora Antonia divide el mensaje en “palabras” de 4 cifras y a cada una de ellas le añade tres bits redundantes para obtener “palabras” de 7 cifras (ahora entenderá el lector por qué el código se llama (7, 4) ). ¿Cómo añade esos bits redundantes? Para ello tenemos que introducir otro concepto que nos llevará a la conclusión de que, a pesar de que muchos lo nieguen, 1 + 1= 0. El concepto es la suma en el cuerpo de 2 elementos, cuyos elementos son el 0 y el 1 y cuya tabla de sumar es la siguiente:
| + | 0 | 1 |
| 0 | 0 | 1 |
| 1 | 1 | 0 |
Que, como podemos observar, se basa en la siguiente ley: si la suma es par, el resultado es 0, si la suma es impar, el resultado es 1.
Bien, pues a nuestra palabra original a1a2a3a4 le añadimos 3 bits redundantes p1, p2, p3, calculados de la siguiente manera:
P1= a1+a2+a4
P2=a1+a3+a4
P3=a2+a3+a4
Donde la suma es la descrita un poco más arriba, es decir, el resultado será 0 si la suma da un número par y 1 si da un resultado impar.
A continuación transformamos cada palabra a1a2a3a4 en la palabra p1p2a1p3a2a3a4, en este caso, transformamos:
0100 1101 0100 0101 0100 1110 0101 0011 0100 0001 0100 1010 0100 0101
en:
1001100 1010101 1001100 0100101 1001100 0010110 0100101 1000011 1001100 1101001 1001100 1011010 1001100 0100101.
-
Y ya Antonia está en condiciones de enviar el mensaje, pero por el camino se producen algunos errores (este código tiene una distancia de Hamming entre palabras de 3, por lo que sólo se podrá corregir la palabra si hay un único error), que se señalan en negrita.
1001000 1010101 1001100 0100101 1011100 0010110 0100101 1000011 1001100 1101001 1001100 1011010 1001100 0000101.
-
Benjamín recibe el mensaje y pasa a comprobar si hay algún error. Para ello mira a ver si las palabras recibidas son todas válidas. ¿Cómo lo hace? Bien, pues volviendo a calcular por su cuenta los bits de redundancia, es decir, en la palabra p1p2a1p3a2a3a4, calcula, de la misma forma que antes, p1, p2 y p3 (a los que por comodidad, ahora llamaremos s1, s2 y s3). Puede ocurrir que éstos bits coincidan o que no. Calcularemos entonces tres números r1, r2 y r3 de la siguiente manera: rn es igual a 0 si pn y sn coinciden, en caso contrario es igual a 1. En el caso en el que las tres “r” sean igual a 0, la palabra es una palabra válida y será correcta o, por lo menos, este código no es capaz de detectar el error. Si ese no es el caso, lo único que hay que hacer es construir el número r=r3r2r1 y pasarlo a base decimal. El número en base decimal nos indica el lugar en el que se ha cometido el error. La razón se deduce de la siguiente tabla (recordemos que este código sólo corrige un error):
|
|
r3 |
r2 |
r1 |
Decimal |
|
Error en p1 |
0 |
0 |
1 |
1 |
|
Error en p2 |
0 |
1 |
0 |
2 |
|
Error en a1 |
0 |
1 |
1 |
3 |
|
Error en p3 |
1 |
0 |
0 |
4 |
|
Error en a2 |
1 |
0 |
1 |
5 |
|
Error en a3 |
1 |
1 |
0 |
6 |
|
Error en a4 |
1 |
1 |
1 |
7 |
Hagamos el proceso en una de las palabras erróneas, por ejemplo en 1001000.
s1= 0, p1= 1. Entonces r1 = 1
s2= 0, p2= 0. Entonces r2 = 0
s3= 0, p3= 1. Entonces r3 = 1
El número r será 101, que en base decimal se corresponde con 5, por lo tanto la cifra que ocupa el lugar 5 es errónea, así, la palabra correcta será 1001100.
Y los detalles que quedan se los dejo al lector, que puede ojear las referencias si quiere más información.
Referencias:
- Códigos numéricos: NIF, ISBN…
LEZAUN, M. (2009): Matemáticas para detectar y corregir errores [pdf]. Números, nº 71, 87-100
BEATO, J. (2008): Códigos numéricos para la vida. Suma, nº 57, 43-54
http://www.gratisweb.com/juanfco20004/PAG.12-24.pdf
- Códigos correctores de errores
FERNÁNDEZ, P. (2000): Códigos, quinielas y empaquetamientos [pdf].
LEZAUN, M. (2009): Matemáticas para detectar y corregir errores [pdf]. Números, nº 71, 87-100
LÓPEZ, J.A.; PERALTA, J. (2006): Las matrices, la base 2 y la tecnología digital[Pdf]. Suma, nº 51, 9-13
Muy interesante y muy bien explicado para ser la primera toma de contacto con este tema.