Algoritmos de detección y corrección de errores

¿Cuántas veces nos hemos encontrado con que un fichero se niega a cargar, tras repetirnos incesantemente nuestro ordenador un mensaje del estilo de "Error leyendo Backup: (R)epetir (I)gnorar (P)ánico"?

Este error tan poco deseado es común a cualquier sistema de almacenamiento: es imposible crear un sistema fiable al 100%. Ni siquiera las RAMs se salvan: en el ambiente hay muchos tipos de radiación capaces de alterar el bit preciso para que nuestro programa cuelgue irremisiblemente el ordenador. Si bien la probabilidad de que ocurra es bastante baja para una sola celda de memoria (del orden de varios millones de años), cuando agrupamos varios millones de ellas para formar los tan comunes 4 megas, dicha probabilidad sube, hasta situarse en unos 20 días. Esta es la razón de que los grandes ordenadores incluyan un código de control en sus memorias.

El problema se agrava cuando no es solo nuestra paciencia la que depende de esos datos, sino, por ejemplo, los miles de millones de dolares invertidos en una misión espacial (la misión VOYAGER a los planetas exteriores), la seguridad económica de un pais (transaccion electrónica de capital entre bancos), la salud de una persona (transferencia electrónica de partes clínicos entre hospitales) o la reputación de un sistema de grabación de música revolucionario (el Compact Disc). En estos casos, un error en un solo bit puede dar al traste con todo, por lo que se hace necesario el poder detectarlos y corregirlos.

Se han ideado multitud de sistemas de detección y corrección de errores. Si bien en general son muy distintos entre sí, todos se basan en añadir información extra a los datos originales, de tal forma que permitan detectar si han sido o no dañados, y recuperar la información original.

El sistema más simple de detección de errores es el llamado Checksum, o suma de comprobación. Se basa simplemente en añadir al final del bloque de datos la suma de todos ellos. El receptor debe comprobar que este dato se corresponde efectivamente con la suma de los datos recibidos. De no ser así, es que ha ocurrido un error, por lo que debe pedir al transmisor que repita el bloque de datos.

Normalmente, este sistema se aplica a pequeñas porciones del bloque total a transmitir; por ejemplo, cada 256 bytes o 1 Kbyte. De este modo, si sucede un error, la cantidad de datos a repetir es menor.

Un segundo sistema es el control de paridad. Se basa en añadir a cada porción del bloque un bit extra, el cual tomará el valor adecuado de forma que el número de bits a cero o a uno de la porción sea siempre par, o siempre impar, según sea el tipo de paridad escogido.

Este sistema se usa, por ejemplo, en las memorias de los PCs compatibles, para detectar si algún bit ha sido alterado. Sin embargo, el uso más común se le da en la transmisión de textos ASCII vía MODEM. Dado que el ASCII usa solo 7 bits, se suele aprovechar el octavo para fijar la paridad del byte que se transmite. De ese modo se puede saber si algún carácter ha resultado alterado. En caso de trabajar con textos en EBDIC, que son de ocho bits por carácter, es necesario usar un bit extra para la paridad, por lo que no se suele aplicar.

Estos dos métodos, si bien son de simple aplicación, tienen el inconveniente de que necesitan que les sea retransmitida la información erronea, con el consiguiente aumento de tiempo en la transmisión, así como la mayor complejidad del protocolo de comunicación.

Si bien con un MODEM no es muy problematico emplear unas centésimas de segundo para pedir de nuevo el bloque, en otros casos no se puede permitir tal pérdida de tiempo. Tal es el caso de, por ejemplo, las sondas espaciales destinadas a otros planetas del sistema solar, en las que una señal puede tardar en llegar al ingenio de entre 1,2 segundos (Luna) hasta más de cuatro horas (Neptuno y Plutón). En estos casos, además, debido a la naturaleza dinámica de la información a enviar, cuando llegue la señal de pedido, puede ser ya demasiado tarde.

Otro caso es, por ejemplo, los lectores de Compact Disc, o de CD-ROM. En ellos, los errores son muy frecuentes debidos a pequeños rayazos o partículas de polvo, que llegan a cubrir cientos de bits. Aquí no se puede volver a leer un sector, pues es seguro que el error permanecerá. Asimismo, debido a la naturaleza mecánica del medio, puede tardarse tanto en reposicionar la cabeza de lectura, que la pausa sea perceptible por el oido.

Es aquí donde los códigos de corrección de errores encuentran su mayor aplicación, pues, aunque aumentan la cantidad de información a transmitir, permiten recuperar los datos dañados a partir del bloque recibido, sin necesidad de volver a transmitirlo.

El sistema más simple de corrección de errores se basa en la fuerza bruta: consiste en repetir la información tres veces, de modo que si se pierde uno de los datos, quedarán los otros dos para descubrir cual era el adecuado. Tiene el grave inconveniente de que triplica la cantidad de los datos a transmitir, por eso no es muy utilizado.

Existe otro sistema mucho más fiable, consistente en añadir unas palabras de control intercaladas entre los datos. Es un sistema de redundancia cíclica. Sin embargo, no debemos confundirlo con el CRC, pues el CRC es sólo un sistema de detección de errores, pero no permite su corrección a partir de los datos recibidos, sino que estos deben ser reenviados.

Hay varias maneras de generar estas palabras. La más simple es coger dos datos adyacentes e intercalar entre ellos su suma. De este modo, si tenemos n datos de m bits cada uno, le añadiremos n-1 datos de m+1 bits cada uno. Luego, si se produce un error en una palabra, será facil detectar cual es y recuperar su valor original con una simple resta.

Otra manera, mucho más versatil, se basa en aplicar el control de paridad a traves de una operación lógica XOR (OR EXclusivo). Esta es una función binaria de dos entradas y una salida, y cuyo funcionamiento es el siguiente: cuando sus entradas tienen el mismo valor (dos unos, o dos ceros), su salida es cero; cuando sus entradas tienen valores distintos, su salida es uno. Su tabla de verdad es la siguiente:

Esta operación se aplica bit a bit a cada pareja de datos, y el resultado se intercala entre ellos. El procedimiento es el mismo que con la suma, pero tiene la ventaja de que los datos resultantes tienen el mismo número de bits que los de entrada. Además, si volvemos a aplicar la operación lógica XOR entre el resultado y uno de los datos, obtendremos el otro. Esto aumenta la velocidad de proceso del algoritmo.

Una de las grandes ventajas de este sistema es que permite realizar la codificación, descodificación y corrección de errores a medida que se va realizando la transmisión o la recepción, sin necesidad de almacenar una determinada cantidad inicial para poder proceder a su inspección. Sin embargo, tiene el inconveniente de que es muy sensible a los errores de explosión o de ráfaga.

¿Qué es un error de explosión? Cuando se produce un error en una transmisión, lo normal es que no sea un único bit el afectado, sino también una serie de bits adyacentes. En el caso de una transmisión de radio, por ejemplo, si se produce una interferencia, puede durar el tiempo suficiente como para volver erroneas varias decenas de bits; sin embargo, esos bits alterados no están distribuidos aleatoriamente, sino agrupados todos juntos en la zona del mensaje donde se produjo dicha interferencia. Asimismo, en un CD, una mota de polvo o un rayazo tapará unos cientos de bits, los cuales recibirán un valor erroneo; pero esos bits están situados correlativamente. Por eso se llaman errores de explosión: no dañan puntos aislados, sino que producen un gran cráter de errores concentrados.

Este sistema no es capaz de corregir con fiabilidad absoluta más de un error seguido, por lo que los errores de explosión resultan tremendamente peligrosos. Por eso se recurre a desordenar los datos antes de su transmisión, de modo que luego, al recibirlos, los posibles errores de explosión habrán afectado realmente a datos dispersos, y no a datos consecutivos.

Debido a lo que ya comentamos, es necesario que al menos dos de cada tres datos estén en buen estado si queremos recuperar la información sin problemas, luego es necesario separar entre sí los datos correspondientes a las posiciones N, N+1 y N+2 como mínimo. De este modo aseguramos que la información necesaria para recuperar un dato no se encuentra consecutiva a dicho dato.

Una manera de desordenar dicha información consiste en agrupar todos los datos en tres, de modo que en el primer bloque estén los datos situados en N, N + 3, N + 6, N + 9..., en el segundo bloque los datos situados en N + 1, N + 4, N + 7, N + 10..., y en el tercer bloque los datos situados en N + 2, N + 5, N + 8, N + 11... Para aumentar el desorden, se puede aumentar a 4 o más el número de bloques a crear, y para simplificar el proceso de reordenamiento y permitir una operación más o menos en tiempo real, se pueden usar grupos de una longitud fija, p.e. 256 bytes. De este modo, se cogen los primeros 256 bytes, se desordenan y se envian; luego los siguientes 256 bytes, se desordenan y se envian;... así sucesivamente. Dado que el último dato de un grupo y el primero del grupo siguiente, una vez reordenados, van igualmente consecutivos, puede ser conveniente agrupar los tres bloques que forman el primer grupo en orden ascendente, y los tres bloques que forman el segundo grupo en orden descendente; así sucesivamente; de este modo ningún byte que sea consecutivo de otro antes del desordenamiento lo seguirá siendo después de éste, reduciendo de este modo la posibilidad de que un error de explosión machaque datos necesarios para la recuperación.

Un dato importante a la hora de elegir un sistema de desordenamiento es el número máximo de bytes seguidos que es capaz de perder sin posibilidad de recuperación. En nuestro caso, ese número coincide con la longitud de cada bloque de bytes. De este modo, si tomamos grupos de 3072 bytes (3K) y hacemos tres bloques por grupo, podremos perder un máximo de 1024 bytes seguidos si queremos poder seguir recuperando la información. Otros tamaños y otros números de grupos dan distintas cantidades de bytes posibles.

Por poner un ejemplo, el sistema de corrección de errores del Compact Disc es capaz de recuperar hasta 14000 bits seguidos erroneos. Discos con agujeros de 2 milimetros en su superficie son reproducidos sin ninguna clase de errores.

Este sistema es, sin duda, muy simple. Existen otros como el Reed Solomon, o la Clave Golay, mucho más eficientes (y complejos de entender), y son los que se usan en las sondas espaciales, los lectores de CD, etc.

El uso de estas técnicas de corrección de errores supone sin duda una valiosa ayuda a la hora de transmitir información a traves de canales ruidosos. Sin embargo, como es lógico, no podemos pedirles imposibles. Si bien son más seguras que la transmisión de los datos sin protección, siempre es posible que surja algún error fatal que destruya parte de la información sin posibilidad de corrección. Afortunadamente para todos, son casos muy extremos y muy poco probab!6jk?,§a

Esta obra está bajo una licencia de Creative Commons Reconocimiento-CompartirIgual 4.0 Internacional.