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

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

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

Оптимальные коды стирания обладают тем свойством, что любые k вне п символов кодового слова достаточно для восстановления исходного сообщения (т. е. они имеют оптимальную эффективность приема). Оптимальные коды стирания: коды максимального расстояния (Коды МДС).

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

Смотрите также: Бит четности

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

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

Набор k + 1 значения ${\displaystyle \{v_{i}\}_{1\leq i\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. Err-mail работает так же, как и электронная почта, за исключением

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

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

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

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

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

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

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

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

Общий случай

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

• Паритет: используется в RAID системы хранения.
• Parchive
• Тахо-ЛАФС включает zfec
• Коды Рида – Соломона
• Устойчивый к стиранию систематический код, MDS-код превосходит код Рида – Соломона по максимальному количеству избыточных пакетов, см. RS (4,2) с 2 битами или же RS (9,2) с 3 битами
• Регенерирующие коды^[2] смотрите также Хранилище вики.
• любой другой Код MDS (тип «Максимального отделяемого кода расстояния»)

Другой

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

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

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

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

1. Некоторые версии этой истории относятся к демону err-mail.
2. Dimakis, Alexandros G .; Годфри, П. Брайтэн; У, Юньнань; Уэйнрайт, Мартин Дж .; Рамчандран, Каннан (сентябрь 2010 г.). «Сетевое кодирование для распределенных систем хранения». IEEE Transactions по теории информации. 56 (9): 4539–4551. arXiv:cs / 0702015. CiteSeerX  10.1.1.117.6892. Дои:10.1109 / TIT.2010.2054295.

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

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