Онлайн-коды

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

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

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

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

• 1 Подробное обсуждение
  • 1.1 Внешнее кодирование
  • 1.2 Внутреннее кодирование
  • 1.3 Декодирование
• 2 Внешние ссылки

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

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

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

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

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

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

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

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

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

$p\; 1\; =\; 1\; -\; 1\; +\; 1\; /\; F\; 1\; +\; ϵ\; \{\backslash \; displaystyle\; p\_\; \{1\}\; =\; 1\; -\; \{\backslash \; frac\; \{1\; +\; 1\; /\; F\}\; \{1+\; \backslash \; epsilon\}\}\}$

$pi\; =\; (1\; -\; p\; 1)\; F\; (F\; -\; 1)\; i\; (i\; -\; 1)\; \{\backslash \; displaystyle\; p\_\; \{i\}\; =\; \{\backslash \; frac\; \{(1-p\_\; \{1\})\; F\}\; \{(F-1)\; i\; (i-1)\}\}\}$для $2\; \le \; i\; \le \; F\; \{\backslash \; displaystyle\; 2\; \backslash \; leq\; i\; \backslash \; leq\; F\}$

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

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

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

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

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