Код стирания

В теории кодирования , код стирания является коррекцией ошибок (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]
Сообщения длиной более 5 символов недопустимы.
Это очень дорого (похоже на авиапочту).

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

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

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

Боб знает, что форма f ( k ) такова , где a и b - две части телефонного номера. Теперь предположим, что Боб получает «D = 777» и «E = 851». $f(i)=a+(b-a)(i-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 - л ) пространство для работы «на лету».

Реализация в реальном мире [ править ]

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

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

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

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

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

Примеры [ править ]

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

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

Коды почти оптимального фонтана (бесскоростное стирание) [ править ]

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

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

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

Другое [ править ]

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

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

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

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

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

Внешние ссылки [ править ]

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

[1] Некоторые версии этой истории относятся к демону err-mail.

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

[1]