Стирающий код

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

Принцип работы 
Стирающий код преобразует сообщение из  символов в более длинное сообщение (кодовое слово) из  символов так, что исходное сообщение может быть восстановлено по  любым символам. Такой код называется  кодом, выражение  — кодовой долей, выражение  — эффективностью приёма.

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

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

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

 .

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

 .

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

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

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

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

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

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

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

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

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

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

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

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

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

Применение 
Стирающие коды применяются в:
  (например, в группе по надёжному мультивещанию IETF)
 3GPP (MBMS и eMBMS ()
 одноранговых сетях, например, для решения проблемы передачи последнего блока данных
 .

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

Почти оптимальные стирающие коды
 Код с малой плотностью проверок на чётность

Оптимальные стирающие коды
 Бит чётности
 Код Рида — Соломона

Примечания

Литература 
 

Обнаружение и устранение ошибок
Теория кодирования