Онлайн коды - Online codes

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

Взгляд высокого уровня на использование онлайн коды

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

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

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

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

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

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

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

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

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

Внутреннее кодирование принимает составное сообщение и генерирует поток проверочных блоков. Блок проверки - это XOR всех блоков составного сообщения, к которому он прикреплен.

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

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

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

${\displaystyle p_{i}={\frac {(1-p_{1})F}{(F-1)i(i-1)}}}$ за ${\displaystyle 2\leq i\leq F}$

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

Расшифровка

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

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

внешняя ссылка

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