Коды Торнадо: Быстрое исправление ошибок в кодировании стирания.

Введение

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

Обзор

Входные данные разделены на блоки. Блоки — это последовательности битов одинакового размера. Данные для восстановления используют тот же размер блока, что и входные данные. Обнаружение стирания блока (входного или восстанавливающего) производится иными средствами. (Например, блок с диска не проходит CRC-проверку или сетевой пакет с заданным порядковым номером не получен.) Пользователь задает количество восстанавливающих блоков. Затем определяется количество уровней и количество блоков на каждом уровне. Количество блоков на каждом уровне определяется коэффициентом B, который меньше единицы. Если имеется N входных блоков, то первый уровень восстановления содержит B*N блоков, второй — B*B*N, третий — B*B*B*N и так далее. Все уровни восстановления, кроме последнего, используют LDPC, работающий на основе операции XOR (исключающее ИЛИ). XOR оперирует с бинарными значениями, 1 и 0. Результат XOR для A и 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 только подмножества блоков входных данных (или более низкого уровня восстановления), восстанавливающие блоки могут быть сгенерированы быстро. Последний уровень использует код Рида — Соломона. Коды Рида — Соломона оптимальны с точки зрения восстановления после ошибок, но медленны в генерации и восстановлении. Поскольку каждый уровень содержит меньше блоков, чем предыдущий, код Рида — Соломона имеет небольшое количество восстанавливающих блоков для генерации и использования при восстановлении. Таким образом, несмотря на медлительность кода Рида — Соломона, ему требуется обработать лишь небольшой объем данных. В процессе восстановления сначала восстанавливается код Рида — Соломона. Это гарантированно работает, если количество недостающих блоков на предпоследнем уровне меньше количества блоков на последнем уровне. Переходя к более низким уровням, уровень восстановления LDPC (XOR) может быть использован для восстановления уровня ниже с высокой вероятностью, если все восстанавливающие блоки присутствуют и на уровне ниже отсутствует не более чем на C' блоков меньше, чем на восстанавливающем уровне. Алгоритм восстановления заключается в поиске восстанавливающего блока, в котором отсутствует только один блок из его генерирующего набора на нижнем уровне. Тогда XOR восстанавливающего блока со всеми присутствующими блоками равен недостающему блоку.

The input data is divided into blocks. Blocks are sequences of bits that are all the same size. Recovery data uses the same block size as the input data. The erasure of a block (input or recovery) is detected by some other means. (For example, a block from disk does not pass a CRC check or a network packet with a given sequence number never arrived.) The number of recovery blocks is given by the user. Then the number of levels is determined along with the number of blocks in each level. The number in each level is determined by a factor B which is less than one. If there are N input blocks, the first recovery level has B*N blocks, the second has B*B*N, the third has B*B*B*N, and so on. All levels of recovery except the final one use an LDPC, which works by xor (exclusive or). Xor operates on binary values, 1s and 0s. A xor B is 1 if A and B have different values and 0 if A and B have the same values. If you are given result of (A xor B) and A, you can determine the value for B. (A xor B xor A = B) Similarly, if you are given result of (A xor B) and B, you can determine the value for A. This extends to multiple values, so given result of (A xor B xor C xor D) and any 3 of the values, the missing value can be recovered. So the recovery blocks in level one are just the xor of some set of input blocks. Similarly, the recovery blocks in level two are each the xor of some set of blocks in level one. The blocks used in the xor are chosen randomly, without repetition. However, the number of blocks xor'ed to make a recovery block is chosen from a very specific distribution for each level. Since xor is a fast operation and the recovery blocks are an xor of only a subset of the blocks in the input (or at a lower recovery level), the recovery blocks can be generated quickly. The final level is a Reed–Solomon code. Reed–Solomon codes are optimal in terms of recovering from failures, but slow to generate and recover. Since each level has fewer blocks than the one before, the Reed–Solomon code has a small number of recovery blocks to generate and to use in recovery. So, even though Reed–Solomon is slow, it only has a small amount of data to handle. During recovery, the Reed–Solomon code is recovered first. This is guaranteed to work if the number of missing blocks in the next to final level is less than the present blocks in the final level. Going lower, the LDPC (xor) recovery level can be used to recover the level beneath it with high probability if all the recovery blocks are present and the level beneath is missing at most C' fewer blocks than the recovery level. The algorithm for recovery is to find some recovery block that has only one of its generating set missing from the lower level. Then the xor of the recovery block with all of the blocks that are present is equal to the missing block.

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

Коды торнадо ранее были запатентованы в Соединенных Штатах Америки. Патенты 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 года соответственно.

Цитаты

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