Онлайн коды

В информатике являются онлайн-коды примером кодов стирания без скорости . Эти коды могут кодировать сообщение в такое количество символов, что знание любой их части позволяет восстановить исходное сообщение (с высокой вероятностью). Бесскоростные коды создают произвольно большое количество символов, которые могут передаваться до тех пор, пока у получателей не будет достаточно символов.

Общий обзор использования онлайн-кодов

онлайн-кодирования Алгоритм состоит из нескольких этапов. Сначала сообщение разбивается на n блоков сообщений фиксированного размера. Тогда внешнее кодирование представляет собой код стирания , который создает вспомогательные блоки, которые добавляются к блокам сообщений для формирования составного сообщения.

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

Подробное обсуждение

Онлайн-коды параметризуются размером блока двумя скалярами и q и ε . Авторы предполагают q =3 и ε=0,01. Эти параметры задают баланс между сложностью и производительностью кодирования. Сообщение, состоящее из n может быть восстановлено блоков, с высокой вероятностью из (1+3ε) n проверочных блоков. Вероятность отказа равна (ε/2) ^д+1 .

Внешняя кодировка

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

Для каждого блока сообщения псевдослучайным образом выберите q вспомогательных блоков. (из общего количества 0,55 q ε n вспомогательных блоков), к которым его можно прикрепить. Каждый вспомогательный блок представляет собой операцию XOR всех блоков сообщений, которые были к нему присоединены.

Внутреннее кодирование

График полученных контрольных блоков в сравнении с количеством блоков сообщений, фиксированным для сообщения размером 10 000 блоков.

Внутреннее кодирование принимает составное сообщение и генерирует поток контрольных блоков. Контрольный блок — это операция XOR всех блоков составного сообщения, к которому он прикреплен.

Степень . проверочного блока — это количество блоков, к которым он прикреплен Степень определяется путем выборки случайного распределения p , которое определяется как:

$F=\left\lceil {\frac {\ln(\epsilon ^{2}/4)}{\ln(1-\epsilon /2)}}\right\rceil$

$p_{1}=1-{\frac {1+1/F}{1+\epsilon }}$

$p_{i}={\frac {(1-p_{1})F}{(F-1)i(i-1)}}$ для $2\leq i\leq F$

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

Декодирование

Очевидно, что декодер внутреннего этапа должен содержать контрольные блоки, которые он в данный момент не может декодировать . Контрольный блок может быть декодирован только в том случае, если известны все блоки, кроме одного, к которому он прикреплен. График слева показывает ход работы внутреннего декодера. По оси X отложено количество полученных контрольных блоков, а пунктирная линия показывает количество контрольных блоков, которые в данный момент нельзя использовать. Сначала это происходит почти линейно, так как многие контрольные блоки со степенью > 1 получены, но непригодны для использования. В определенный момент некоторые из контрольных блоков внезапно становятся пригодными для использования, разрешая больше блоков, что затем делает возможным использование большего количества контрольных блоков. Очень быстро весь файл можно декодировать.

Как также видно на графике, внутренний декодер некоторое время не успевает декодировать все после получения n контрольных блоков. Внешнее кодирование гарантирует, что несколько неуловимых блоков внутреннего декодера не станут проблемой, поскольку файл можно восстановить без них.

Внешние ссылки

• Оригинальная бумага
• Безоценочные коды и большие загрузки (более доступная статья того же автора)
• Доклады Петра Маймункова
• Проект Ruby, размещенный на RubyForge, содержащий библиотеку Ruby для онлайн-кодирования.