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 C constante y bloques más redundantes que los códigos de borrado Reed-Solomon , más eficientes en cuanto a datos , pero son mucho más rápidos de generar y pueden corregir borrados más rápidamente. Las implementaciones de códigos de tornado basadas en software son aproximadamente 100 veces más rápidas en longitudes pequeñas y aproximadamente 10.000 veces más rápidas en longitudes más grandes 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 de 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 posibilidades 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 de fallas. Los códigos Tornado dictan cuántos niveles, cuántos 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 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 recuperación) se detecta por algún otro medio. (Por ejemplo, un bloque del disco no pasa una verificación CRC o un paquete de red con un número de secuencia determinado nunca llegó).
El número de bloques de recuperación lo proporciona el usuario. Luego, se determina el número de niveles junto con el número de bloques en cada nivel. El número en cada nivel está determinado por 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 final utilizan un LDPC, que funciona mediante xor (exclusive-or). 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 3 valores cualesquiera, el valor faltante se puede recuperar.
Entonces, los bloques de recuperación en el nivel uno son solo el xor de algún conjunto de bloques de entrada. De manera similar, los bloques de recuperación en el nivel dos son cada uno de ellos el xor de algún conjunto de bloques en el nivel uno. Los bloques utilizados en el xor se eligen al azar, sin repetición. Sin embargo, el número de bloques xor'ed para hacer un bloque de recuperación se elige 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 para generar y recuperar. 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. Entonces, aunque Reed-Solomon es lento, solo tiene que manejar una pequeña cantidad de datos.
Durante la recuperación, primero se recupera el código Reed-Solomon. Se garantiza que esto funcionará si el número de bloques que faltan en el nivel penúltimo es menor que los bloques actuales en el nivel final.
Al bajar, el nivel de recuperación de LDPC (xor) se puede usar para recuperar el nivel debajo de él con alta probabilidad si todos los bloques de recuperación están presentes y al nivel debajo le faltan como máximo C' menos bloques que el nivel de recuperación. El algoritmo de recuperación es encontrar algún bloque de recuperación al que solo le falta uno de sus grupos electrógenos en el nivel inferior. Entonces el xor del bloque de recuperación con todos los bloques que están presentes es igual al bloque que falta.
Los códigos 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 Tornado y expiraron el 6 de noviembre de 2017. Patentes US6307487 B1 (presentada el 5 de febrero de 1999) y US6320520 B1 (presentada el 17 de septiembre de 1999) también menciona 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]
{{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace ){{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )Una descripción legible de CMU (PostScript) [1] y otra de Luby en el Instituto Internacional de Ciencias de la Computación (PostScript) [2].