Код Торнадо

В теории кодирования коды Торнадо представляют собой класс стирающих кодов , которые поддерживают исправление ошибок . Коды Торнадо требуют на константу C большего количества избыточных блоков, чем более эффективные по данным стирающие коды Рида-Соломона , но они генерируются намного быстрее и могут быстрее исправлять стирания. Программные реализации кодов торнадо примерно в 100 раз быстрее при малых длинах и примерно в 10 000 раз быстрее при больших длинах, чем стирающие коды Рида – Соломона. С момента появления кодов 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 блока восстановления со всеми присутствующими блоками равен отсутствующему блоку.

Патентные вопросы

Коды Торнадо ранее были запатентованы в Соединенных Штатах Америки. Патенты US6163870 A (подана 6 ноября 1997 г.) и US 6081909 A (подана 6 ноября 1997 г.) описывают коды Tornado, срок их действия истек 6 ноября 2017 г. Патенты US6307487 B1 (подана 5 февраля 1999 г.) и US6320520 B1 (подана 5 февраля 1999 г.) 17 сентября, 1999) также упоминают коды Торнадо, срок действия которых истек 5 февраля 2019 г. и 17 сентября 2019 г. соответственно.

Цитаты

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

См. также

• Код стирания
• Код Раптора

Ссылки

• Байерс Дж.В., Луби М., Митценмахер М., Реге А. (октябрь 1998 г.). «Цифровой фонтанный подход к надежному распределению больших объемов данных». SIGCOMM '98: Труды . Конференция ACM SIGCOMM '98 по приложениям, технологиям, архитектурам и протоколам компьютерной связи. стр. 56–67. дои : 10.1145/285237.285258 .
• Луби М , Митценмахер М , Шокроллахи А , Шпильман Д , Стеманн В (1997). «Практические коды, устойчивые к потерям». Труды двадцать девятого ежегодного симпозиума ACM по теории вычислений : 150–159.
• Луби М , Митценмахер М , Шокроллахи А (1998). «Анализ случайных процессов посредством оценки дерева И-ИЛИ». Материалы 9-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам : 364–373.
• Митценмахер М (2004). «Цифровые фонтаны: обзор и взгляд в будущее». Учеб. 2004 Семинар IEEE по теории информации (ITW) .

Внешние ссылки

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