Введение
В информатике онлайн-коды являются примером кодов стирания без ограничения скорости (rateless erasure codes). Эти коды могут кодировать сообщение в набор символов таким образом, что знание любой доли этих символов позволяет восстановить исходное сообщение (с высокой вероятностью). Коды без ограничения скорости генерируют произвольно большое количество символов, которые могут передаваться до тех пор, пока получатели не получат достаточное количество символов. Алгоритм онлайн-кодирования состоит из нескольких фаз. Сначала сообщение разбивается на n блоков сообщения фиксированного размера. Затем внешнее кодирование представляет собой код стирания, который создает вспомогательные блоки, добавляемые к блокам сообщения для формирования составного сообщения. На основе этого внутреннего кодирования генерируются контрольные блоки. Получив определенное количество контрольных блоков, можно восстановить часть составного сообщения. После восстановления достаточного объема данных внешнее декодирование может быть использовано для восстановления исходного сообщения.
Детальное обсуждение
Онлайн-коды параметризуются размером блока и двумя скалярами, q и ε. Авторы рекомендуют значения q=3 и ε=0,01. Эти параметры определяют компромисс между сложностью и эффективностью кодирования. Сообщение, состоящее из n блоков, может быть восстановлено с высокой вероятностью из (1+3ε)n контрольных блоков. Вероятность ошибки составляет (ε/2)q+1.
Декодирование
Очевидно, декодер внутренней ступени должен хранить контрольные блоки, которые он пока не может декодировать. Контрольный блок может быть декодирован только тогда, когда известны все блоки, к которым он привязан, кроме одного. График слева показывает прогресс работы внутреннего декодера. По оси X откладывается количество полученных контрольных блоков, а пунктирной линией – количество контрольных блоков, которые в данный момент не могут быть использованы. Поначалу эта линия растет почти линейно, так как поступает много контрольных блоков со степенью > 1, но они оказываются непригодными для использования. В определенный момент некоторые контрольные блоки внезапно становятся пригодными, что позволяет декодировать больше блоков, а затем – использовать больше контрольных блоков. Очень быстро весь файл может быть декодирован. Как показывает график, внутренний декодер некоторое время после получения n контрольных блоков не может декодировать все данные. Внешнее кодирование гарантирует, что несколько неуловимых блоков, оставшихся после работы внутреннего декодера, не создадут проблем, поскольку файл можно восстановить и без них.