Открыть главное меню

Удаляющий (избыточный) код

(перенаправлено с «Избыточный код»)

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

Графическое представление процессов кодирования и декодирования.
Графическое представление процессов кодирования и декодирования.

Принцип работыПравить

Удаляющий код преобразует сообщение из   символов в более длинное сообщение (кодовое слово) из   символов, так что исходное сообщение может быть восстановлено по   любым символам. Такой код называется   кодом, выражение   - кодовой долей, выражение   - эффективностью приема[4][5].

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

Оптимальный удаляющий кодПравить

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

Простейшая реализацияПравить

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

 .

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

 .

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

Линейный кодПравить

Интересным подклассом удаляющего кода является линейный код. Его название связано с тем, что он может быть проанализирован с помощью линейной алгебры. Пусть   - исходные данные,   - матрица размера  , тогда закодированные данные  - кода могут быть представлены как  . Предположим, что приемник получил   компонент вектора  , тогда исходные данные могут быть восстановлены с помощью   уравнений, связанных с известными компонентами вектора  . Пусть матрица   размера   соответствует этой системе уравнений. Восстановление возможно, если все эти уравнения линейно независимые и, в общем случае, это означает, что любая матрица размера   обратима. Матрица   называется генерирующей матрицей кода, так как любой допустимый   является линейной комбинацией столбцов матрицы  . Поскольку ее ранг равен  , любое подмножество из   закодированных элементов должно содержать информацию о всех   исходных данных. Для получения исходных данных необходимо решить линейную систему:  , где   - подмножество из   элементов вектора  , доступных на приемнике.[9]

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

Пример: 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 сообщения (два от Алисы и два подтверждения от Боба). Таким образом, удаляющий код, представленный в этом примере, довольно экономичный[10].

Общий случайПравить

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

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

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

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

Почти оптимальный удаляющий кодПравить

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

Удаляющий код для передачи медиа-информации в режиме реального времениПравить

На качество передачи аудио и видео данных в режиме реального времени влияет по большой мере не число общих потерь в канале связи, а так называемые "взрывные потери" - те, что произошли последовательно. Согласно исследованиям, проведенным с распределениями Бернулли и Гильберта-Эллиота для потерь при передаче, ожидаемая величина длины последовательных потерь при использовании удаляющего кода выше, чем без него.[13]

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

ПримерыПравить

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

Почти оптимальные удаляющие кодыПравить

Оптимальные удаляющие кодыПравить

СсылкиПравить

  1. Университет ИТМО. Избыточное кодирование, код Хэмминга. Университет ИТМО. Университет ИТМО (29 октября 2015).
  2. Luigi Rizzo. Effective Erasure Codes for Reliable Computer Communication Protocols (англ.) // ACM Computer Communication Review. — 1997. — Апрель. — С. 3.
  3. Katina Kralevska. [https://arxiv.org/pdf/1803.01358.pdf Applied Erasure Coding in Networks and Distributed Storage] (англ.). — 2018. — Март. — С. 7.
  4. University, ITMO Избыточное_кодирование,_код_Хэмминга. ITMO University (29 октября 2015). Дата обращения 8 ноября 2019.
  5. Alexandros G. Dimakis, P. Brighten Godfrey, Martin J. Wainwright and Kannan Ramchandran. [https://arxiv.org/pdf/cs/0702015.pdf Network Coding for Distributed Storage Systems] (англ.). — 2007. — 1 февраля. — С. 2.
  6. Katina Kralevska. [https://arxiv.org/pdf/1803.01358.pdf Applied Erasure Coding in Networks and Distributed Storage] (англ.). — 2018. — Март. — С. 7.
  7. Codes for Big Data: Erasure Coding for Distributed Storage. P. Vijay Kumar. Дата обращения 8 ноября 2019.
  8. 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.
  9. Luigi Rizzo. Effective Ersure Codes for Reliable Computer Communication Protocols (англ.) // ACM Computer Communication Review. — 1997. — Т. 27, № 2. — С. 24-36.
  10. Hamid Jafarkhani, Mahdi Hajiaghayi. United States Patent Application Publication. COST-EFFICIENT REPAIR FOR STORAGE SYSTEMS USING PROGRESSIVE ENGAGEMENT 1 (22.10.2015).
  11. Jonathan Detchart. Improving the coding speed of erasure codes with polynomial ring transforms (англ.). — 2018. — 2 октября. — С. 1.
  12. Ning Cao, Shucheng Yu, Zhenyu Yang, Wenjing Lou, Y. Thomas Hou. [https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6195814 LT Codes-based Secure and Reliable Cloud Storage Service] (англ.) // IEEE. — 2012. — С. 696.
  13. Bobak McCann, Kerry Fendick. The Effect of Erasure Coding on the Burstiness of Packet Loss. — 2019. — Октябрь. — С. 6.