Código de tornados

En teoría de la codificación , los códigos Tornado son una clase de códigos de borrado que admiten corrección de errores . Los códigos Tornado requieren una constante C bloques redundantes más que los códigos de borrado Reed-Solomon , que son más eficientes en datos, pero son mucho más rápidos de generar y pueden corregir borrados más rápidamente. Las implementaciones basadas en software de los códigos Tornado son aproximadamente 100 veces más rápidas en longitudes pequeñas y aproximadamente 10 000 veces más rápidas en longitudes mayores que los códigos de borrado Reed-Solomon. ^{[ 1 ]} Desde la introducción de los códigos Tornado, han surgido muchos otros códigos de borrado similares, en particular los códigos Online , los códigos LT y los códigos Raptor .

Los códigos Tornado emplean un enfoque por capas. Todas las capas, excepto la última, utilizan un código de corrección de errores LDPC , que es rápido pero tiene cierta probabilidad de fallar. La capa final utiliza un código de corrección Reed-Solomon, que es más lento pero óptimo en términos de recuperación ante fallos. Los códigos Tornado determinan la cantidad de niveles, la cantidad de bloques de recuperación en cada nivel y la distribución utilizada para generar bloques para las capas no finales.

Los datos de entrada se dividen en bloques. Los bloques son secuencias de bits del mismo tamaño. Los datos de recuperación utilizan el mismo tamaño de bloque que los datos de entrada. El borrado de un bloque (de entrada o de recuperación) se detecta por otros medios. (Por ejemplo, si un bloque del disco no supera una comprobación CRC o si un paquete de red con un número de secuencia determinado no llega).

El usuario especifica el número de bloques de recuperación. A continuación, se determina el número de niveles y el número de bloques en cada nivel. El número de bloques en cada nivel se determina mediante un factor B menor que uno. Si hay N bloques de entrada, el primer nivel de recuperación tiene B*N bloques, el segundo tiene B×B×N, el tercero tiene B×B×B×N, y así sucesivamente.

Todos los niveles de recuperación, excepto el último, utilizan un LDPC, que funciona mediante XOR (OR exclusivo). XOR opera con valores binarios, 1 y 0. A xor B es 1 si A y B tienen valores diferentes y 0 si A y B tienen valores iguales. Si se le da el resultado de (A xor B) y A, puede determinar el valor de B. (A xor B xor A = B) De manera similar, si se le da el resultado de (A xor B) y B, puede determinar el valor de A. Esto se extiende a múltiples valores, por lo que dado el resultado de (A xor B xor C xor D) y cualesquiera 3 de los valores, se puede recuperar el valor faltante.

Así, los bloques de recuperación del nivel uno son simplemente el resultado de la operación XOR de un conjunto de bloques de entrada. De forma similar, los bloques de recuperación del nivel dos son, cada uno, el resultado de la operación XOR de un conjunto de bloques del nivel uno. Los bloques utilizados en la operación XOR se eligen aleatoriamente, sin repetición. Sin embargo, el número de bloques que se combinan mediante la operación XOR para formar un bloque de recuperación se elige a partir de una distribución muy específica para cada nivel.

Dado que la operación XOR es rápida y los bloques de recuperación son el resultado de la operación XOR de solo un subconjunto de los bloques de entrada (o con un nivel de recuperación inferior), los bloques de recuperación se pueden generar rápidamente.

El nivel final es un código Reed-Solomon. Los códigos Reed-Solomon son óptimos para recuperarse de fallos, pero su generación y recuperación son lentas. Dado que cada nivel tiene menos bloques que el anterior, el código Reed-Solomon tiene un número reducido de bloques de recuperación que generar y utilizar. Por lo tanto, aunque Reed-Solomon es lento, solo tiene que procesar una pequeña cantidad de datos.

Durante la recuperación, primero se recupera el código Reed-Solomon. Esto garantiza su funcionamiento si el número de bloques faltantes en el penúltimo nivel es menor que el número de bloques presentes en el último nivel.

Descendiendo aún más, el nivel de recuperación LDPC (xor) puede utilizarse para recuperar el nivel inferior con alta probabilidad si todos los bloques de recuperación están presentes y al nivel inferior le faltan como máximo C' bloques menos que al nivel de recuperación. El algoritmo de recuperación consiste en encontrar un bloque de recuperación cuyo conjunto generador falte solo uno en el nivel inferior. Entonces, el xor del bloque de recuperación con todos los bloques presentes es igual al bloque faltante.

Los códigos Tornado fueron patentados anteriormente en los Estados Unidos de América. ^{[ 2 ]} Las patentes US6163870 A (presentada el 6 de noviembre de 1997) y US 6081909 A (presentada el 6 de noviembre de 1997) describen los códigos Tornado y expiraron el 6 de noviembre de 2017. Las patentes US6307487 B1 (presentada el 5 de febrero de 1999) y US6320520 B1 (presentada el 17 de septiembre de 1999) también mencionan los códigos Tornado y expiraron el 5 de febrero de 2019 y el 17 de septiembre de 2019, respectivamente.

Michael Luby creó los códigos Tornado. ^{[ 3 ] [ 4 ]}

• Código de borrado
• Código Raptor

• Byers JW, Luby M, Mitzenmacher M, Rege A (octubre de 1998). "Un enfoque de fuente digital para la distribución confiable de grandes volúmenes de datos". SIGCOMM '98: Actas . Conferencia ACM SIGCOMM '98 sobre aplicaciones, tecnologías, arquitecturas y protocolos para la comunicación informática. págs. 56–67 . doi : 10.1145/285237.285258 . 
• Luby M , Mitzenmacher M , Shokrollahi A , Spielman D , Stemann V (1997). «Códigos prácticos resistentes a pérdidas». Actas del vigésimo noveno simposio anual de la ACM sobre Teoría de la Computación - STOC '97 . págs. 150–159 . doi : 10.1145/258533.258573 . ISBN  0-89791-888-6.
• Luby M , Mitzenmacher M , Shokrollahi A (1998). "Análisis de procesos aleatorios mediante evaluación de árboles AND-OR". Actas del 9º Simposio Anual ACM-SIAM sobre Algoritmos Discretos : 364– 373.
• Mitzenmacher M (2004). «Fuentes digitales: Un estudio y perspectivas de futuro». Manufacturing Engineer . pp. 271–276 . doi : 10.1109/ITW.2004.1405313 . ISBN  0-7803-8720-1.

Una descripción legible de CMU (PostScript)y otra de Luby en el Instituto Internacional de Ciencias de la Computación (PostScript).