Избыточный код

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

В теории кодирования избыточный код — это код прямой коррекции ошибок в предположении о стирании битов данных (а не битов ошибок), который преобразует сообщение из символов в более длинное сообщение (кодовое слово) из n символов, так что исходное сообщение может быть восстановлено из подмножества слов, состоящих из символов. Выражение называется кодовой долей. Выражение , где обозначает количество символов, необходимых для восстановления, называется эффективностью приема.[1]

Оптимальные избыточные коды[править | править код]

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

Проверка четности[править | править код]

Проверка четности — особый случай, когда . С помощью набора из значений вычисляется контрольная сумма и добавляется к исходным значениям:

.

Набор из значений теперь содержит контрольную сумму. Если одно из этих значений потеряно, то оно может быть с легкостью восстановлено путем суммирования оставшихся:

.

Более сложные комбинации искомых и получаемых значений представляют собой Граф Таннера.[3]

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

Пример: Err-mail (k = 2)[править | править код]

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

Алиса посчитала значения и

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

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

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

  1. Она разбивает свой телефонный номер на две части и отправляет 2 сообщения Бобу — "A=555" и "B=629"
  2. Она строит линейную функцию , в этом примере . Таким образом и .
  3. Она считает значения и , а затем отправляет три избыточных сообщения: "C=703", "D=777" и "E=851

Боб знает, что выражение для следующее , где и — две части телефонного номера. Теперь предположим, что Боб получает "D=777" и "E=851".

Боб получает два сообщения с и

Боб может восстановить телефонный номер Алисы с помощью и , используя значения и , которые он получил. Боб может проделать эту операцию, используя любые два сообщения err-mail. Значит, в этом примере кодовая доля составляет 40%.Заметим, что Алиса не может закодировать свой номер телефона только в одном сообщении err-mail, так как он состоит из 6 символов, а максимальная длина одного сообщения err-mail — 5 символов. Если бы она отправляла свой номер телефона по частям, запрашивая подтверждения каждой части от Боба, то было бы отправлено минимум 4 сообщения (два от Алисы и два подтверждения от Боба). Таким образом, избыточный код, представленный в этом примере, довольно экономичный.

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

Общий случай[править | править код]

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

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

Отправитель может создавать символы от до "на лету", то есть равномерно распределять рабочую нагрузку между передаваемыми символами. Если получатель хочет выполнять эти расчеты "на лету", он может посчитать новый полином такой, что , если символ был успешно получен и в ином случае. Теперь положим . Во-первых, мы знаем, что , если символ был успешно получен. Во-вторых, если символ был успешно получен, то выражение может быть посчитано. Таким образом мы имеем достаточно точек, чтобы построить и использовать его, чтобы найти потерянные пакеты. Итак обоим, отправителю и получателю, требуется операций и лишь места для операций, производимых "на лету".

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

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

Почти оптимальные избыточные коды.[править | править код]

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

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

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

Примеры[править | править код]

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

Почти оптимальные избыточные коды[править | править код]

Оптимальные избыточные коды[править | править код]

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

  1. University, ITMO Избыточное_кодирование,_код_Хэмминга. ITMO University (29 октября 2015). Дата обращения 8 ноября 2019.
  2. Codes for Big Data: Erasure Coding for Distributed Storage. P. Vijay Kumar. Дата обращения 8 ноября 2019.
  3. Small parity-check erasure codes - exploration and observations. J.S. Plank Dept. of Comput. Sci., Tennessee Univ., Knoxville, TN, USA; A.L. Buchsbaum ; R.L. Collins ; M.G. Thomason. Дата обращения 8 ноября 2019.
  4. Improving the Coding Speed of Erasure Codes with Polynomial Ring Transforms. Jonathan Detchart, Jérôme Lacan. Дата обращения 8 ноября 2019.
  5. Dimakis, Alexandros G.; Godfrey, P. Brighten; Wu, Yunnan; Wainwright, Martin J.; Ramchandran, Kannan. Network Coding for Distributed Storage Systems (англ.) // IEEE Transactions on Information Theory (англ.) : journal. — 2010. — September (vol. 56, no. 9). — P. 4539—4551. — DOI:10.1109/TIT.2010.2054295. — arXiv:cs/0702015.