En teoría de codificación , los códigos Tornado son una clase de códigos de borrado que admiten la corrección de errores . Los códigos Tornado requieren una constante C de bloques más redundantes que los códigos de borrado Reed-Solomon más eficientes en datos , pero son mucho más rápidos de generar y pueden corregir borrados más rápido. 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 utilizan un enfoque en capas. Todas las capas, excepto la última, utilizan un código de corrección de errores LDPC , que es rápido pero tiene una probabilidad de fallar. La capa final utiliza un código de corrección Reed-Solomon, que es más lento pero es óptimo en términos de recuperación de fallas. Los códigos Tornado dictan cuántos niveles, cuántos bloques de recuperación hay 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 que tienen todos el 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 algún otro medio. (Por ejemplo, un bloque del disco no pasa una comprobación CRC o un paquete de red con un número de secuencia determinado nunca llega).
El usuario proporciona la cantidad de bloques de recuperación. Luego, se determina la cantidad de niveles junto con la cantidad de bloques en cada nivel. La cantidad en cada nivel se determina mediante un factor B que es 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 por xor (o 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 los mismos valores. 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.
Por lo tanto, los bloques de recuperación del nivel uno son simplemente el xor de un conjunto de bloques de entrada. De manera similar, los bloques de recuperación del nivel dos son cada uno el xor de un conjunto de bloques del nivel uno. Los bloques utilizados en el xor se eligen de manera aleatoria, sin repetición. Sin embargo, la cantidad de bloques que se han sometido al xor para formar un bloque de recuperación se elige a partir de una distribución muy específica para cada nivel.
Dado que xor es una operación rápida y los bloques de recuperación son un xor de solo un subconjunto de los bloques en la entrada (o en 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 en términos de recuperación de fallas, pero lentos en su generación y recuperación. Dado que cada nivel tiene menos bloques que el anterior, el código Reed-Solomon tiene una pequeña cantidad de bloques de recuperación para generar y usar en la recuperación. Por lo tanto, aunque Reed-Solomon es lento, solo tiene una pequeña cantidad de datos para manejar.
Durante la recuperación, primero se recupera el código Reed-Solomon. Se garantiza que esto funcionará si la cantidad de bloques faltantes en el penúltimo nivel es menor que la cantidad de bloques actuales en el último nivel.
Al descender, el nivel de recuperación LDPC (xor) se puede utilizar para recuperar el nivel que se encuentra debajo con alta probabilidad si todos los bloques de recuperación están presentes y el nivel que se encuentra debajo tiene como máximo C' menos bloques faltantes que el nivel de recuperación. El algoritmo para la recuperación consiste en encontrar algún bloque de recuperación al que solo le falte uno de sus grupos generadores en el nivel inferior. Entonces, el xor del bloque de recuperación con todos los bloques que están presentes es igual al bloque faltante.
Los códigos de tornado se patentaron 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 códigos de 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 códigos de 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]
Una descripción legible de CMU (PostScript) [1] y otra de Luby en el Instituto Internacional de Ciencias de la Computación (PostScript) [2].