В теории кодирования коды Торнадо представляют собой класс стирающих кодов , которые поддерживают исправление ошибок . Коды Торнадо требуют на константу C большего количества избыточных блоков, чем более эффективные по данным стирающие коды Рида-Соломона , но они генерируются намного быстрее и могут быстрее исправлять стирания. Программные реализации кодов торнадо примерно в 100 раз быстрее на малых длинах и примерно в 10 000 раз быстрее на больших длинах, чем стирающие коды Рида – Соломона. [1] С момента появления кодов Tornado появилось множество других подобных кодов стирания, в первую очередь онлайн-коды , коды LT и коды Raptor .
Коды Tornado используют многоуровневый подход. Все уровни, кроме последнего, используют код коррекции ошибок LDPC , который работает быстро, но имеет вероятность сбоя. Последний уровень использует корректирующий код Рида-Соломона, который медленнее, но оптимален с точки зрения восстановления после сбоя. Коды Tornado определяют, сколько уровней, сколько блоков восстановления на каждом уровне и распределение, используемое для генерации блоков для нефинальных слоев.
Входные данные разбиты на блоки. Блоки — это последовательности битов одинакового размера. Данные восстановления используют тот же размер блока, что и входные данные. Стирание блока (ввода или восстановления) обнаруживается каким-то другим способом. (Например, блок с диска не проходит проверку CRC или сетевой пакет с заданным порядковым номером так и не пришел.)
Количество блоков восстановления задается пользователем. Затем определяется количество уровней и количество блоков на каждом уровне. Число на каждом уровне определяется коэффициентом B, меньшим единицы. Если входных блоков N, то первый уровень восстановления имеет блоки B*N, второй — B*B*N, третий — B*B*B*N и так далее.
Все уровни восстановления, кроме финального, используют LDPC, который работает по принципу xor (исключающее-или). Xor работает с двоичными значениями, 1 и 0. A xor B равен 1, если A и B имеют разные значения, и 0, если A и B имеют одинаковые значения. Если вам дан результат (A xor B) и A, вы можете определить значение для B. (A xor B xor A = B) Аналогично, если вам дан результат (A xor B) и B, вы можете определить значение для A. Это распространяется на несколько значений, поэтому, учитывая результат (A xor B xor C xor D) и любых трех значений, недостающее значение можно восстановить.
Таким образом, блоки восстановления на первом уровне — это просто операция xor некоторого набора входных блоков. Аналогично, каждый из блоков восстановления на втором уровне представляет собой операцию xor некоторого набора блоков на первом уровне. Блоки, используемые в xor, выбираются случайным образом, без повторения. Однако количество блоков, подвергнутых xor'у для создания блока восстановления, выбирается из очень специфического распределения для каждого уровня.
Поскольку xor — это быстрая операция, а блоки восстановления представляют собой xor только подмножества блоков на входе (или на более низком уровне восстановления), блоки восстановления могут быть сгенерированы быстро.
Последний уровень — это код Рида–Соломона. Коды Рида-Соломона оптимальны с точки зрения восстановления после сбоев, но медленно генерируются и восстанавливаются. Поскольку каждый уровень имеет меньше блоков, чем предыдущий, код Рида-Соломона имеет небольшое количество блоков восстановления, которые нужно генерировать и использовать при восстановлении. Таким образом, хотя алгоритм Рида-Соломона работает медленно, ему приходится обрабатывать лишь небольшой объем данных.
Во время восстановления сначала восстанавливается код Рида-Соломона. Это гарантированно сработает, если количество недостающих блоков на предпоследнем уровне меньше, чем количество имеющихся блоков на последнем уровне.
Спускаясь ниже, уровень восстановления LDPC (xor) можно использовать для восстановления уровня ниже него с высокой вероятностью, если все блоки восстановления присутствуют, а уровень ниже отсутствует не более чем на C' меньше блоков, чем уровень восстановления. Алгоритм восстановления состоит в том, чтобы найти некоторый блок восстановления, у которого на нижнем уровне отсутствует только один из его генераторного набора. Тогда xor блока восстановления со всеми присутствующими блоками равен отсутствующему блоку.
Коды Торнадо ранее были запатентованы в Соединенных Штатах Америки. [2] Патенты US6163870 A (подана 6 ноября 1997 г.) и US 6081909 A (подана 6 ноября 1997 г.) описывают коды Tornado, срок их действия истек 6 ноября 2017 г. Патенты US6307487 B1 (подана 5 февраля 1999 г.) и US6320520 B1 (поданный 17 сентября 1999 г.) также упоминает коды Tornado, срок действия которых истек 5 февраля 2019 г. и 17 сентября 2019 г. соответственно.
Майкл Луби создал коды Торнадо. [3] [4]
{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка ){{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )Читабельное описание от CMU (PostScript) [1] и еще одно от Луби из Международного института компьютерных наук (PostScript) [2].