El fundamento matemático del CRC nos habla de códigos de bloques lineales expresados como polinomios en cuerpos de Galois, pero si profundizamos por este camino nos podría dar una hemorragia cerebral.
En vez de eso, comenzaremos por dar un ejemplo sencillo, pasando de lo particular a lo general.
Imaginemos que nuestro mejor amigo nos manda el mensaje “SOS” por cualquier medio, indicándonos que se encuentra en peligro. Pero por desgracia durante la transmisión del mensaje ha habido interferencias electromagnéticas que han alterado el contenido del mensaje y lo que recibimos es “OSO”.
No solamente no prestamos ayuda a nuestro amigo, sino que además nos cabreamos con él por llamarnos OSO.
Para evitar lo anterior y asegurarnos que el mensaje que nos llega está inalterado, nuestro amigo le aplicará un CRC, es decir, le añadirá al mensaje otro símbolo (de ahí viene lo de redundancia) que nos indicará si el mensaje ha sido alterado o no.
Ese símbolo extra no es más que el resto de dividir el mensaje por un valor previamente pactado en ambas partes.
Veamos el proceso:
Según el estándar ASCII el mensaje “SOS” se codifica como:
‘S’ es codificado con el valor 83.
‘O’ es codificado con el valor 79.
El mensaje sería 837983 y lo vamos a dividir por el símbolo ‘P’ que en ASCII es 80, el resto de esta división se concatena al mensaje origen:
837983 MOD 80 = 63
63 equivale a el símbolo ‘?’, por lo tanto el mensaje listo para enviar sería “SOS?”.
Cuando recibamos el mensaje, como pactamos el CRC con nuestro amigo, repetimos el proceso y comprobamos si coincide.
Si el mensaje recibido hubiese sido “OSO?”, calcularíamos el CRC de “OSO”:
798379 MOD 80 = 59
59 equivale al símbolo ‘;’ que es distinto de ‘?’, luego ya estamos en condiciones de advertir que el mensaje no es fiable.
Para que los dispositivos electrónicos operen justamente como nosotros acabamos de hacer, los matemáticos, esos grandes inventores de realidades, idearon una manera magistral de entender y analizar los códigos cíclicos mediante polinomios.
Un patrón de 0 y 1 se representa como un polinomio con coeficientes de valor 0 y 1.
La potencia de cada término del polinomio muestra la posición del bit y el coeficiente el valor del bit.
Por ejemplo, el polinomio:
se representa como 10000010000010001.
Como se observa el beneficio es inmediato ya que un patrón de 17 bits se representa con un polinomio de 4 términos.
Sin embargo hay que recalcar que la elección del divisor, llamado polinomio generador, no es trivial, pero nuevamente nuestros amigos matemáticos han elaborado algunos polinomios generadores estandarizados y que se aproximan al 100% de la detección del error en mensajes grandes.
Alguno de estos son:
- CRC-12.
- CRC-16.
- CRC-CCITT.
- CRC-32.
Puede veniros bien profundizar en el cálculo del resto de una divisón de polinomios mediante operaciones lógicas XOR para entender luego el código que publicaré en sucesivas entregas.
Aconsejo visitar:
Como veis la teoría es fácil, pero en la práctica, un fichero se compone de millones de bits y calcular el resto de una división de tal calibre es impensable.
En lugar de esto lo que se suele hacer es una mezcla de checksum con CRC, pero esto lo veremos en la próxima entrega, donde nos meteremos de lleno con un código que calcula el CRC de un fichero.
