Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Обзор [ править ]

Входные данные разбиты на блоки. Блоки - это последовательности битов одинакового размера. Данные для восстановления используют тот же размер блока, что и входные данные. Стирание блока (вход или восстановление) обнаруживается каким-либо другим способом. (Например, блок с диска не проходит проверку CRC или сетевой пакет с заданным порядковым номером так и не прибыл.)

Количество блоков восстановления задается пользователем. Затем определяется количество уровней и количество блоков на каждом уровне. Число на каждом уровне определяется коэффициентом B меньше единицы. Если имеется N входных блоков, первый уровень восстановления имеет B * N блоков, второй - B * B * N, третий - B * B * B * N и так далее.

Все уровни восстановления, кроме последнего, используют LDPC, который работает с помощью xor (исключающее ИЛИ). Xor работает с двоичными значениями, единицами и нулями. 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 является быстрой операцией, а блоки восстановления являются 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] и еще одно из Luby из Международного института компьютерных наук (PostScript) [2] .

См. Также [ править ]

Заметки [ править ]

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

Ссылки [ править ]

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