En la teoría de la 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 más bloques 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 de códigos 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, sobre todo 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 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 son todos 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 (entrada o recuperación) se detecta por algún otro medio. (Por ejemplo, un bloque del disco no pasa una verificación de CRC o nunca llegó un paquete de red con un número de secuencia dado).
El número de bloques de recuperación lo proporciona el usuario. Luego, el número de niveles se determina 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 por xor (exclusive-or). Xor opera con valores binarios, 1 y 0. A x o B es 1 si A y B tienen valores diferentes y 0 si A y B tienen los mismos valores. Si obtiene el resultado de (A x o B) y A, puede determinar el valor de B. (A x o B x o A = B) De manera similar, si obtiene el resultado de (A x o B) y B, puede determinar el valor de A. Esto se extiende a múltiples valores, por lo que dado el resultado de (A x o B x o C x o D) y cualquiera de los 3 valores, se puede recuperar el valor faltante.
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 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.