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 de bloques más redundantes que los códigos de borrado de 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ápido. Las implementaciones basadas en software de los códigos de 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 de Reed-Solomon. [1] Desde la introducción de los códigos Tornado, han surgido muchos otros códigos de borrado similares, sobre todo códigos en línea , códigos LT y 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 de 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.
Descripción general
Los datos de entrada se dividen en bloques. Los bloques son secuencias de bits que tienen 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 (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, 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 mediante xor (exclusivo-o). Xor opera con valores binarios, unos y ceros. A xor 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 xor B) y A, puede determinar el valor de B. (A xor B xor A = B) De manera similar, si obtiene 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 de los valores, 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 el xo 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 más bajo), 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 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 el número de bloques que faltan en el nivel siguiente al final es menor que los bloques presentes en el nivel final.
Al bajar, el nivel de recuperación LDPC (xor) se puede utilizar para recuperar el nivel por debajo de él con alta probabilidad si todos los bloques de recuperación están presentes y el nivel inferior falta 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.
Problemas de patentes
Los códigos Tornado se patentaron anteriormente dentro de 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 han expirado el 6 de noviembre de 2017. Patentes US6307487 B1 (presentada el 5 de febrero de 1999) y US6320520 B1 (presentado el 17 de septiembre de 1999) también menciona los códigos Tornado y han expirado el 5 de febrero de 2019 y el 17 de septiembre de 2019, respectivamente.
Citas
Michael Luby creó los códigos Tornado. [3] [4]
enlaces externos
Una descripción legible de CMU (PostScript) [1] y otra de Luby en el Instituto Internacional de Ciencias de la Computación (PostScript) [2] .
Ver también
Notas
- ^ Un enfoque de fuente digital para la distribución confiable de datos a granel. http://portal.acm.org/citation.cfm?id=285243.285258
- ^ Mitzenmacher 2004
- ^ Luby 1997
- ^ Luby 1998
Referencias
- M. Mitzenmacher (2004). "Fuentes digitales: una encuesta y mirar hacia el futuro". Proc. 2004 IEEE Information Theory Workshop (ITW) .
- M. Luby , M. Mitzenmacher , A. Shokrollahi , D. Spielman , V. Stemann (1997). "Códigos prácticos resistentes a pérdidas". Actas del Vigésimo Noveno Simposio Anual de ACM sobre Teoría de la Computación : 150-159.CS1 maint: varios nombres: lista de autores ( enlace )
- M. Luby , M. Mitzenmacher , A. Shokrollahi (1998). "Análisis de procesos aleatorios mediante evaluación de árboles y-or". Actas del noveno simposio anual ACM-SIAM sobre algoritmos discretos : 364–373.CS1 maint: varios nombres: lista de autores ( enlace )