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