Русская Википедия:Стирающий код
Стирающий код[1] (Шаблон:Lang-en) — в теории кодирования помехоустойчивый код[1], способный восстановить целые пакеты данных в случае их потери[2]. Такой код позволяет бороться с утечками данных при передаче по каналам связи или работе с памятью. Обычно он используется, когда точная позиция потерянных данных известна априори[3].
Принцип работы
Стирающий код преобразует сообщение из <math>k</math> символов в более длинное сообщение (кодовое слово) из <math>n</math> символов так, что исходное сообщение может быть восстановлено по <math>k'</math> любым символам. Такой код называется <math>(n, k)</math> кодом, выражение <math>r = k/n</math> — кодовой долей[4], выражение <math>k'/k</math> — эффективностью приёма[5][6].
Стирающий код обычно используется на верхних уровнях стека протоколов каналов передачи и хранения информации[3].
Оптимальный стирающий код
Оптимальный стирающий отличается тем, что любых <math>k</math> из <math>n</math> символов кодового слова достаточно для восстановления исходного сообщения[7], то есть они имеют оптимальную эффективность приёма[5][8].
Проверка чётности
Рассмотрим случай, когда <math>n = k + 1</math>. С помощью набора из <math>k</math> значений <math>\{v_i\}_{1 \leq i \leq k}</math> вычисляется контрольная сумма и добавляется к <math>k</math> исходным значениям:
- <math>v_{k+1} = - \sum_{i=1}^k v_i</math>.
Теперь в набор <math>\{v_i\}_{1 \leq i \leq k+1}</math> из <math>k+1</math> значений включена контрольную сумму. В случае потери одного из значений <math>v_e</math>, его можно будет с лёгкостью восстановить с помощью суммирования оставшихся:
- <math>v_{e} = -\sum_{i=1, i\neq e}^{k+1} v_i</math>.
Более сложные комбинации искомых и получаемых значений представляют собой Граф Таннера[4][5].
Линейный код
Важным подклассом стирающего кода является линейный код. Его название связано с тем, что он может быть проанализирован с помощью линейной алгебры. Пусть <math>x = x_0 \dots x_{k-1}</math> — исходные данные, <math>G</math> — матрица размера <math>n \times k</math>, тогда закодированные данные <math>(n, k)</math>- кода могут быть представлены как <math>\vec{y}=G\vec{x}</math>. Предположим, что приёмник получил <math>k</math> компонент вектора <math>\vec{y}</math>, тогда исходные данные могут быть восстановлены с помощью <math>k</math> уравнений, связанных с известными компонентами вектора <math>\vec{y}</math>. Пусть матрица <math>G'</math> размера <math>k \times k</math> соответствует этой системе уравнений. Восстановление возможно, если все эти уравнения линейно независимые и, в общем случае, это означает, что любая матрица размера <math>k \times k</math> обратима. Матрица <math>G</math> называется генерирующей матрицей кода, так как любой допустимый <math>\vec{y}</math> может быть получен как линейная комбинация столбцов матрицы <math>G</math>. Так как её ранг равен <math>k</math>, то любое подмножество из <math>k</math> закодированных элементов должно содержать информацию о всех <math>k</math> исходных данных. Для получения исходных данных необходимо решить линейную систему: <math>\vec{y'}=G'\vec{x}</math>, где <math>\vec{y'}</math> — подмножество из <math>k</math> элементов вектора <math>\vec{y}</math>, доступных на приёмнике[9].
Полиномиальная передискретизация
Пример: Неисправная электронная почта (Шаблон:Lang-en)
В случае, когда <math>k=2</math>, избыточные символы могут быть созданы как промежуточные точки на отрезке, соединяющем два исходных символа. Это показано на простом примере, называемом неисправной электронной почтой:
Алиса хочет отправить свой телефонный номер (555629) Бобу, используя неисправную электронную почту. Данный вид почты работает так же, как обычная электронная почта, за следующим исключением:
- Около половины всех сообщений теряются.
- Сообщения длиннее 5 символов запрещены.
- Это очень дорого.
Вместо того, чтобы спросить у Боба подтверждения сообщения, которое она отправила, Алиса придумывает следующую схему:
- Она разбивает свой телефонный номер на две части <math>a=555, b=629</math> и отправляет 2 сообщения Бобу — «A=555» и «B=629».
- Она строит линейную функцию <math>f(i)=a+(b-a)(i-1)</math>, в этом примере <math>f(i)=555+74(i-1)</math>. Таким образом <math>f(1)=555</math> и <math>f(2) = 629</math>.
- Она считает значения <math>f(3)=703, f(4)=777</math> и <math>f(5)=851</math>, а затем отправляет три избыточных сообщения: «C=703», «D=777» и «E=851».
Боб знает, что выражение для <math>f(k)</math> следующее <math>f(i)=a+(b-a)(i-1)</math>, где <math>a</math> и <math>b</math> — две части телефонного номера. Теперь предположим, что Боб получает «D=777» и «E=851».
Боб может восстановить телефонный номер Алисы с помощью <math>a</math> и <math>b</math>, используя значения <math>f(4)</math> и <math>f(5)</math>, которые он получил. Более того, он может это сделать, используя два любых полученных сообщения. Значит, в этом примере кодовая доля равна 40 %. Заметим, что Алиса не может закодировать свой номер телефона только в одном сообщении такой почты, так как он состоит из 6 символов, а максимальная длина одного сообщения — 5 символов. Если бы она отправляла свой номер телефона по частям, запрашивая подтверждения каждой части от Боба, то было бы отправлено минимум 4 сообщения (два от Алисы и два подтверждения от Боба)[5][10].
Общий случай
Приведённая выше линейная конструкция может быть обобщена до полиномиальной интерполяции. В таком случае точки теперь вычисляются над конечным полем <math>\mathbb{F}_{2^m}</math>, где <math>m</math> — число бит в символе. Отправитель нумерует символы данных от <math>0</math> до <math>k-1</math> и посылает их. Затем он строит, например, интерполяционный многочлен Лагранжа <math>p(x)</math> степени <math>k</math>, так что <math>p(i)</math> равен <math>i</math>-ому символу данных. Потом он отправляет <math>p(k),\ldots,p(n-1)</math>. С помощью полиномиальной интерполяции получатель сможет восстановить потерянные данные в случае, если он успешно принял <math>k</math> символов[5].
Реализация в реальном мире
Данный процесс реализован в Коде Рида — Соломона с кодовыми словами, сконструированными над конечным полем при использовании определителя Вандермонда[11].
Почти оптимальный стирающий код
Почти оптимальный стирающий код требует <math>(1+\varepsilon)k</math> символов, чтобы восстановить сообщение (где <math>\varepsilon > 0</math>). Величина <math>\varepsilon</math> может быть уменьшена за счёт дополнительного времени работы процессора. При использовании таких кодов необходимо решить, что предпочтительнее: сложность вычислений или возможность коррекции сообщений[11]. В 2004 году существовал только один почти оптимальный стирающий код с линейным временем кодирования и декодирования — Шаблон:Не переведено 5[8].
Применение
Стирающие коды применяются в[11]:
- Шаблон:Не переведено 5 (например, в группе по надёжному мультивещанию IETF)
- 3GPP (MBMS и eMBMS (Шаблон:Не переведено 5)
- одноранговых сетях, например, для решения проблемы передачи последнего блока данных
- Шаблон:Не переведено 5.
Примеры
Здесь приведены некоторые примеры различных кодов.
- Почти оптимальные стирающие коды
- Оптимальные стирающие коды
Примечания
Литература
