Код торнадо - Tornado code

В теория кодирования, Коды торнадо являются классом коды стирания эта поддержка исправление ошибки. Коды торнадо требуют постоянного C большего количества избыточных блоков, чем более эффективных данных Коды стирания Рида – Соломона, но гораздо быстрее создаются и могут быстрее исправлять стирания. Программные реализации кодов торнадо примерно в 100 раз быстрее на малых длинах и примерно в 10 000 раз быстрее на больших длинах, чем коды стирания Рида – Соломона.[1] С момента появления кодов Tornado появилось много других подобных кодов стирания, в первую очередь Онлайн коды, Коды LT и Коды Raptor.

В кодах торнадо используется многоуровневый подход. Все слои, кроме последнего, используют LDPC код исправления ошибок, который работает быстро, но может привести к сбою. На последнем уровне используется код коррекции Рида – Соломона, который работает медленнее, но является оптимальным с точки зрения восстановления после сбоя. Коды торнадо определяют количество уровней, количество блоков восстановления на каждом уровне и распределение, используемое для генерации блоков для незавершенных слоев.

Обзор

Входные данные разбиты на блоки. Блоки - это последовательности битов одинакового размера. Данные для восстановления используют тот же размер блока, что и входные данные. Стирание блока (ввод или восстановление) обнаруживается другими способами. (Например, блок с диска не проходит проверку 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) и любые 3 значения, пропущенное значение может быть восстановлено.

Таким образом, блоки восстановления на первом уровне - это просто xor некоторого набора входных блоков. Точно так же каждый блок восстановления на уровне два является xor некоторого набора блоков на уровне один. Блоки, используемые в xor, выбираются случайным образом, без повторения. Тем не менее номер блоков xor'ed для создания блока восстановления выбирается из очень специфического распределения для каждого уровня.

Поскольку 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 г.) также упоминаются коды Торнадо, срок действия которых истек 5 февраля 2019 г. и 17 сентября 2019 г. соответственно.

Цитаты

Майкл Луби создал коды Торнадо.[3][4]

внешняя ссылка

Читаемое описание из CMU (PostScript) [1] и еще один от Луби в Международный институт компьютерных наук (PostScript) [2].

Смотрите также

Примечания

  1. ^ Цифровой фонтан для надежного распределения больших объемов данных. http://portal.acm.org/citation.cfm?id=285243.285258
  2. ^ (Митценмахер 2004 )
  3. ^ (Луби 1997 )
  4. ^ (Луби 1998 )

Рекомендации

  • М. Митценмахер (2004). «Цифровые фонтаны: обзор и взгляд в будущее». Proc. 2004 г. IEEE Информационная теория семинара (ITW).
  • М. Луби, М. Митценмахер, А. Шокроллахи, Д. Спилман , В. Стеманн (1997). «Практические отказоустойчивые коды». Материалы двадцать девятой ежегодной ACM симпозиум по теории вычислений (STOC ): 150–159.CS1 maint: несколько имен: список авторов (связь)
  • М. Луби, М. Митценмахер, А. Шокроллахи (1998). «Анализ случайных процессов с помощью And-Or Tree оценки». Протокол 9-го Ежегодного ACM -SIAM симпозиум по дискретным алгоритмам: 364–373.CS1 maint: несколько имен: список авторов (связь)