		*Últimos Cambios*
	Blog personal: El hilo del laberinto

Grabación de redundancia Reed-Solomon en CD/DVD

Última Actualización: 30 de octubre de 2006 - Lunes

Los códigos Reed-Solomon son códigos correctores de errores. En un futuro escribiré un documento detallando su funcionamiento, pero de momento nos interesa simplemente una definición funcional: Se trata de códigos en los que la información es troceada en "n" bloques y, a partir de la misma, se generan "x" bloques de redundancia adicional. El receptor puede reconstruir los "n" bloques de información originales a partir de los "n+x" bloques de datos transmitidos, siempre que no hayan desaparecido o se hayan corrompido más de "x" bloques. El número de bloques "x" de redundancia generados es un parámetro de la codificación, ajustable según nuestras necesidades.

Es decir, si dividimos un fichero en mil bloques y, a partir de ellos, generamos diez bloques adicionales y enviamos los mil diez bloques de datos, el receptor puede reconstruir los mil bloques originales siempre que reciba mil bloques o más en total. Es decir, se toleran hasta diez fallos en los mil diez bloques.

Esto es muy interesante, porque permite que los datos sufran degradación o pérdida, pudiéndose reconstruir mientras el nivel de corrupción no supere un umbral, configurable, dado.

En el contexto de esta página web vamos a utilizar esta tecnología a la hora de grabar DVDs, con el fin de poder reconstruir los datos grabados si un día el DVD empieza a darnos errores de lectura. Para ello utilizaremos la tecnología "par2", que es un estándar basado en Reed-Solomon, disponible en múltiples implementaciones para varios sistemas operativos.

Aunque la fiabilidad de los DVDs es bastante superior a los CDs (en especial porque la capa sensible a la luz está recubierta de policarbonato por ambas caras), el problema que yo quería solucionar es el "relleno" de los DVDs. Es decir, si estás grabando AVIs en un DVD, es muy posible que te sobren varios megabytes que no puedes aprovechar para nada en absoluto. Este técnica te permite grabar el DVD al 100% de su capacidad, aprovechando ese espacio inutilizado para mejorar nuestras posibilidades de recuperar información si, en el futuro, ese disco empieza a dar errores de lectura.

A continuación describo los pasos a seguir utilizando la línea de comando de un entorno UNIX. Para clientes GUI en Windows o Macintosh, por ejemplo, leer la descripción y aplicar el sentido común y un mínimo de inteligencia :-)

Lanzamos el programa de grabación de DVDs y seleccionamos los ficheros que vamos a grabar en el disco, hasta que ya no quepan más.
Tomamos el número de bytes libres en el DVD, no utilizables. En este ejemplo, tomaremos 260.2 Megabytes. Vamos a utilizar esa capacidad desaprovechada para almacenar redundancia que nos pueda ayudar en el futuro a recuperar la información contenida en el disco, si empieza a dar errores de lectura.
Ahora nos interesa saber el tamaño de bloque Reed-Solomon. En la linea de comandos lanzamos la siguiente instrucción:
```
par2 c z.par2 fichero1 fichero2...
```
En cuanto se lance el programa, lo cortamos (control+c) y nos fijamos en la siguiente información:
```
Block size: 2217300
Source file count: 7
Source block count: 2000
```
Lo que nos interesa es el "Block Size", o "Tamaño de Bloque".
Otra opción es calcular el tamaño de bloque "a mano", si tenemos pocos ficheros y son muy grandes: vemos el espacio ocupado por los ficheros y lo dividimos por 2000, que es el número de bloques por defecto en este software (aunque esta cifra es configurable).
Ahora vemos cuantos bloques de redundancia nos entran en el espacio libre que quedaba en el DVD: 260.2*1024*1024/2217300 = 123'050. Generamos, entonces 123 bloques de redundancia.
En realidad si generamos 123 bloques, nos pasaremos por un par de megas del objetivo. ¿Por qué?. Porque hay cierta "sobrecarga" que debemos valorar. Por ejemplo, cada bloque de datos requiere unos 21 bytes adicionales (para guardar su MD5 y su CRC), y esta información, que no es reconstruible en caso de problemas, se repite varias veces en la redundancia para poder acceder a ella aunque haya corrupción. Por lo tanto, cuando los decimales que nos salen son pequeños, es preferible curarse en salud y generar un bloque menos de redundancia. En este caso los decimales son 0'050, así que generamos 122 bloques de redundancia, en vez de 123.
Lo peor que puede pasar si no haces esta operación es que te pases por un par de megabytes y tengas que generar la redundancia (corregida) de nuevo. Es un proceso lento, así que es mejor ahorrárselo. Si, por el contrario, reduces en uno el número de bloques de redundancia y no era necesario, el efecto es que te quedarán un par de megabytes libres en el DVD. Nada grave.
De todas formas intentaré explicar mejor esta casuística más adelante.
Ahora generamos la redundancia en sí con el comando:
```
par2 c -u -c122 z.par2 fichero1 fichero2...
```
Esta operación es bastante lenta, así que tomaros vuestro tiempo para cenar, ir al baño, tener un hijo, o lo que se tercie.

Al terminar, tendremos algo de este estilo en el directorio:

-rw-------  1 jcea users     42028 2006-10-31 01:13 z.par2
-rw-------  1 jcea users  40122364 2006-10-31 01:13 z.vol000+18.par2
-rw-------  1 jcea users  40122364 2006-10-31 01:13 z.vol018+18.par2
-rw-------  1 jcea users  40122364 2006-10-31 01:13 z.vol036+18.par2
-rw-------  1 jcea users  37904996 2006-10-31 01:13 z.vol054+17.par2
-rw-------  1 jcea users  37904996 2006-10-31 01:13 z.vol071+17.par2
-rw-------  1 jcea users  37904996 2006-10-31 01:13 z.vol088+17.par2
-rw-------  1 jcea users  37904996 2006-10-31 01:13 z.vol105+17.par2

Ahora grabamos los ficheros originales junto con estos ficheros de redundancia. Nos quedan en el DVD apenas 700Kbytes libres. ¡Misión cumplida!.

En este momento hemos grabado 2122 "bloques", 2000 de datos y 122 de redundancia. En caso de problemas de lectura, podemos recuperar los 2000 bloques de datos siempre que de los 2122 bloques seamos capaces de leer al menos 2000 bloques correctos, cualesquiera.

Dado que cada bloque mide 2217300 bytes, en teoría podemos recuperar la información si fallan hasta 258 megabytes. Pero en la práctica no importan cuántos bytes fallan sino cuántos bloques fallan. Es decir, si fallan solo 150 bits en todo el DVD, pero esos 150 fallos están distribuidos de forma que cada uno cae en un bloque diferente, estamos perdidos.

Por supuesto, en la práctica esto no ocurre. Los fallos normales de un DVD se presentan, normalmente, concentrados en torno a puntos concretos. Por ello, en la práctica, las posibilidades de recuperar la información son muy altas.

Prácticamente la única posibilidad de perder la información (aparte de frotar el disco con una lija :-) ) es que ocurra un error en la zona de directorio, que haga el disco ilegible. En muchos años de experiencia, esto no me ha pasado nunca. Pero es una posibilidad a tener en cuenta.

Pero incluso esa posibilidad puede ser eliminada. Supongamos lo siguiente: En vez de grabar un DVD aislado, grabamos un grupo de DVDs. Supongamos que en cada DVD se almacenan 4 gigabytes de datos y quedan libres 400 megabytes que podemos utilizar como redundancia. Si grabamos diez DVDs de un golpe, estaremos grabando 40 gigabytes de información y 4 gigabytes de redundancia. Es decir, ¡redundancia suficiente para recuperar uno de los DVDs entero!. Es decir, podemos perder uno de los diez DVDs por completo, y aún así recuperarlo por completo mediante los nueve DVDs que aún nos quedan.

Hay otras cosas que habría que comentar, como experimentar con el tamaño de los bloques y su número, qué pasa cuando intentamos proteger muchos ficheros pequeñitos (por ejemplo, fotografías o documentos PDF) en vez de pocos ficheros muy grandes, etc. Pero eso será otro día.

Historia

30/oct/06: Primera versión de este documento.

Más información sobre los OpenBadges

Donación BitCoin: 19niBN42ac2pqDQFx6GJZxry2JQSFvwAfS