Код стирания - Erasure code

В теории кодирования , код стирания является коррекцией ошибок (FEC) код в предположении битовых подчисток (а не ошибки в битах), который преобразует сообщение из K символов в более длинное сообщение (кодовое слово) с п символами , такие , что исходное сообщение может быть восстановлено из подмножества n символов. Доля r  =  k / n называется кодовой скоростью . Доля k '/ k , где k' обозначает количество символов, требуемых для восстановления, называется эффективностью приема .

Оптимальные коды стирания

Оптимальные коды стирания обладают тем свойством, что любых k из n символов кодового слова достаточно для восстановления исходного сообщения (т. Е. Они имеют оптимальную эффективность приема). Оптимальные коды стирания - это коды с разделением на максимальное расстояние (коды MDS).

Проверка четности

Проверка четности - это особый случай, когда n = k + 1. Из набора k значений вычисляется контрольная сумма и добавляется к исходным k значениям: ${\ Displaystyle \ {v_ {я} \} _ {1 \ leq я \ leq k}}$

${\ displaystyle v_ {k + 1} = - \ sum _ {i = 1} ^ {k} v_ {i}.}$

Набор значений k  + 1 теперь согласован с контрольной суммой. Если одно из этих значений стерто, его можно легко восстановить, суммируя оставшиеся переменные: ${\ Displaystyle \ {v_ {я} \} _ {1 \ leq я \ leq k + 1}}$${\ displaystyle v_ {e}}$

${\ displaystyle v_ {e} = - \ sum _ {i = 1, i \ neq e} ^ {k + 1} v_ {i}.}$

Полиномиальная передискретизация

Пример: Err-mail ( k = 2)

В простом случае, когда k = 2, символы избыточности могут быть созданы путем выборки различных точек вдоль линии между двумя исходными символами. Это показано на простом примере, который называется err-mail:

Алиса хочет отправить Бобу свой номер телефона (555629), используя почту с ошибками . Err-mail работает так же, как и электронная почта, за исключением

1. Около половины всей почты теряется.
2. Сообщения длиной более 5 символов недопустимы.
3. Это очень дорого (похоже на авиапочту).

Вместо того, чтобы просить Боба подтвердить отправляемые ею сообщения, Алиса придумывает следующую схему.

1. Она разбивает свой телефонный номер на две части: a = 555, b = 629 и отправляет 2 сообщения - «A = 555» и «B = 629» - Бобу.
2. Она строит линейную функцию, в данном случае такую, что и .${\ Displaystyle е (я) = а + (ба) (я-1)}$${\ Displaystyle F (я) = 555 + 74 (я-1)}$${\ displaystyle f (1) = 555}$${\ displaystyle f (2) = 629}$

1. Она вычисляет значения f (3), f (4) и f (5), а затем передает три избыточных сообщения: «C = 703», «D = 777» и «E = 851».

Боб знает, что форма f ( k ) такова , где a и b - две части телефонного номера. Теперь предположим, что Боб получает «D = 777» и «E = 851». ${\ Displaystyle е (я) = а + (ба) (я-1)}$

Боб может восстановить номер телефона Алисы, вычислив значения a и b из полученных им значений ( f (4) и f (5)). Боб может выполнить эту процедуру, используя любые два сообщения об ошибках, поэтому код стирания в этом примере имеет коэффициент 40%.

Обратите внимание, что Алиса не может закодировать свой номер телефона только в одном сообщении об ошибке, потому что он содержит шесть символов, а максимальная длина одного сообщения об ошибке составляет пять символов. Если бы она отправляла свой номер телефона по частям, прося Боба подтвердить получение каждой части, в любом случае нужно было бы отправить по крайней мере четыре сообщения (два от Алисы и два подтверждения от Боба). Таким образом, код стирания в этом примере, для которого требуется пять сообщений, довольно экономичен.

Этот пример немного надуманный. Для действительно общих кодов стирания, которые работают с любым набором данных, нам понадобится что-то другое, кроме заданного f ( i ).

Общий случай

Вышеупомянутая линейная конструкция может быть обобщена на полиномиальную интерполяцию . Кроме того, точки теперь вычисляются по конечному полю .

Сначала мы выбираем конечное поле F с порядком не менее n , но обычно со степенью 2. Отправитель нумерует символы данных от 0 до k  - 1 и отправляет их. Затем он строит полином (Лагранжа) p ( x ) порядка k такой, что p ( i ) равен символу данных i . Затем он отправляет p ( k ), ..., p ( n  - 1). Получатель теперь также может использовать полиномиальную интерполяцию для восстановления потерянных пакетов при условии, что он успешно принимает k символов. Если порядок F меньше 2 ^b , где b - количество битов в символе, то можно использовать несколько полиномов.

Отправитель может создавать символы с k по n  - 1 «на лету», т. Е. Равномерно распределять рабочую нагрузку между передачей символов. Если получатель хочет выполнять свои вычисления «на лету», он может построить новый многочлен q , такой, что q ( i ) = p ( i ), если символ i < k был получен успешно, и q ( i ) = 0, когда символ i < k не получено. Пусть теперь r ( i ) = p ( i ) -  q ( i ). Во-первых, мы знаем, что r ( i ) = 0, если символ i < k был получен успешно. Во-вторых, если символ i ≥ k был принят успешно, то можно вычислить r ( i ) = p ( i ) -  q ( i ). Итак, у нас достаточно точек данных, чтобы построить r и оценить его, чтобы найти потерянные пакеты. Таким образом, и отправителю, и получателю требуется O ( n ( n  -  k )) операций и только O ( n  -  k ) пространства для работы «на лету».

Реализация в реальном мире

Этот процесс реализуется кодами Рида – Соломона с кодовыми словами, построенными над конечным полем с использованием матрицы Вандермонда .

Почти оптимальные коды стирания

Почти оптимальные коды стирания требуют (1 + ε) k символов для восстановления сообщения (где ε> 0). Уменьшение ε может быть выполнено за счет времени процессора. Near-оптимальные коды стирания торговли возможности коррекции для вычислительной сложности: практические алгоритмы кодирования и декодирования с линейной временной сложностью.

Коды фонтана (также известные как коды бесскоростного стирания ) являются яркими примерами почти оптимальных кодов стирания . Они могут преобразовывать k- символьное сообщение в практически бесконечную закодированную форму, т. Е. Они могут генерировать произвольное количество избыточных символов, которые все могут использоваться для исправления ошибок. Приемники могут начать декодирование после того, как они получили чуть больше k закодированных символов.

Регенерирующие коды решают проблему восстановления (также называемого восстановлением) потерянных закодированных фрагментов из существующих закодированных фрагментов. Эта проблема возникает в распределенных системах хранения, где связь для поддержания закодированной избыточности является проблемой.

Применение стирающего кодирования в системах хранения

Классическим способом восстановления после сбоев в системах хранения было использование репликации. Однако репликация приводит к значительным накладным расходам в виде потраченных байтов. Таким образом, все более крупные системы хранения, такие как те, что используются в центрах обработки данных, используют хранилища с стираемым кодом. Наиболее распространенной формой кодирования стирания, используемой в системах хранения, является код Рида-Соломона (RS) . В ( k , m ) коде RS заданный набор из k блоков данных, называемых «порциями», кодируется в ( k + m ) порций. Полный набор чанков представляет собой полосу . Кодирование выполняется таким образом, что пока доступны по крайней мере k из ( k + m ) фрагментов, можно восстановить все данные. Это означает, что ( k , m ) хранилище с кодированием RS может выдержать до m отказов.

Пример: в коде RS (10, 4), который используется в Facebook для их HDFS , 10 МБ пользовательских данных разделены на десять блоков по 1 МБ. Затем создаются четыре дополнительных блока четности по 1 МБ для обеспечения избыточности. Это может выдержать до 4 одновременных отказов. Накладные расходы на хранилище здесь составляют 14/10 = 1,4X.

В случае полностью реплицированной системы 10 МБ пользовательских данных необходимо будет реплицировать 4 раза, чтобы выдержать до 4 одновременных сбоев. Накладные расходы на хранение в этом случае будут 50/10 = 5X.

Это дает представление о меньших накладных расходах хранилища с кодировкой стирания по сравнению с полной репликацией и, следовательно, привлекательностью современных систем хранения.

Примеры

Вот несколько примеров реализации различных кодов:

Почти оптимальные коды стирания

• Коды торнадо
• Коды с низкой плотностью проверки четности

Коды, близкие к оптимальному фонтану (бесскоростное стирание)

• Код фонтана
• Онлайн коды
• Коды LT
• Коды хищников
• Сетевые коды

Оптимальные коды стирания

• Четность : используется в системах хранения RAID .
• Parchive
• Tahoe-LAFS включает zfec
• Коды Рида – Соломона
• Устойчивый к стиранию систематический код , код MDS, превосходящий по характеристикам код Рида – Соломона по максимальному количеству избыточных пакетов, см. RS (4,2) с 2 битами или RS (9,2) с 3 битами
• Восстановление кодов см. Также Storage Wiki .
• любой другой код MDS (тип «Максимального разделяемого кода расстояния»)

Другой

• Орфографический алфавит

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

• Коды прямого исправления ошибок.
• Совместное использование секрета (отличается тем, что исходный секрет зашифрован и скрыт до тех пор, пока не будет достигнут кворум декодирования)

использованная литература

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

• Jerasure - это библиотека свободного программного обеспечения, реализующая методы стирания кода Рида-Соломона и Коши с оптимизацией SIMD.
• Программное обеспечение FEC в компьютерных коммуникациях Луиджи Риццо описывает оптимальные коды коррекции стирания
• Feclib - это почти оптимальное расширение работы Луиджи Риццо, в котором используются ленточные матрицы. Можно установить множество параметров, например размер ширины полосы и размер конечного поля. Он также успешно использует большой размер регистров современных процессоров. Как это соотносится с упомянутыми выше кодами, близкими к оптимальным, неизвестно.
• Coding for Distributed Storage wiki для восстановления кодов и восстановления кодов стирания.
• ECIP «Интернет-протокол с кодом стирания», разработанный в 1996 году, был первым применением FEC «Прямое исправление ошибок» в Интернете. Впервые он был использован в коммерческих целях для * потоковой передачи живого видео сэра Артура Кларка из Шри-Ланки на UIUC в Индиане .