Войти
В информатике, коды хищника (rap id tor nado; см. коды торнадо ) - первый известный класс исходных кодов с линейным кодированием и декодированием по времени. Они были изобретены Амином Шокроллахи в 2000/2001 году и впервые были опубликованы в 2004 году в виде расширенного реферата. Коды Raptor являются значительным теоретическим и практическим улучшением по сравнению с кодами LT, которые были первым практическим классом кодов фонтанов.
коды Raptor, как и коды фонтанов в целом, кодируют данный исходный блок данные, состоящие из числа k символов одинакового размера, в потенциально неограниченную последовательность таких, что прием любых k или более символов кодирования позволяет восстановить исходный блок с некоторой ненулевой вероятностью. Вероятность того, что исходный блок может быть восстановлен, увеличивается по мере того, как количество символов кодирования, принятых выше k, становится очень близким к 1, если количество принятых символов кодирования лишь очень немного превышает k. Например, с последним поколением кодов Raptor, кодами RaptorQ, вероятность сбоя декодирования при получении k кодирующих символов составляет менее 1%, а вероятность сбоя декодирования при кодировании k + 2 количество полученных символов меньше одного из миллиона. (См. Раздел Вероятность восстановления и накладные расходы ниже для более подробного обсуждения этого вопроса.) Символ может иметь любой размер, от одного байта до сотен или тысяч байтов.
Коды Raptor могут быть систематическими или несистематическими. В систематическом случае символы исходного исходного блока, то есть исходные символы, включаются в набор символов кодирования. Примером систематического кода Raptor является код, определенный Партнерским проектом третьего поколения для использования в мобильной сотовой беспроводной широковещательной и многоадресной передаче, а также используемый в стандартах DVB-H для передачи данных по IP на портативные устройства (см. Внешние ссылки). Коды Raptor в этих стандартах определены также в IETF RFC 5053. Самая продвинутая версия практического кода Raptor - это RaptorQ, определенный в IETF RFC 6330.
Информация об эффективной программной реализации кода RaptorQ, указанном в IETF RFC 6330 (самый продвинутый код фонтана), можно найти на веб-сайте проекта Codornices по адресу ICSI..
Онлайн-коды являются еще одним примером несистематического кода фонтана.
Коды хищников образуются путем объединения двух кодов.
Фиксированный код стирания , обычно с довольно высокой скоростью, применяется как «предварительный код» или «внешний код». Этот предварительный код сам по себе может быть конкатенацией нескольких кодов, например, в коде, стандартизированном 3GPP, полученная из двоичной последовательности Грея объединена с простым обычным кодом проверки четности с низкой плотностью. Другой возможностью было бы объединение кода Хэмминга с кодом проверки четности с низкой плотностью.
Внутренний код принимает результат операции предварительного кодирования и генерирует последовательность символов кодирования. Внутренний код представляет собой форму LT-кодов. Каждый кодирующий символ представляет собой XOR псевдослучайно выбранного набора символов из вывода предварительного кода. Количество символов, которые объединяются с помощью операции XOR для формирования выходного символа, выбирается псевдослучайно для каждого выходного символа в соответствии с конкретным распределением вероятностей.
Это распределение, а также механизм генерации псевдослучайных чисел для выборки этого распределения и выбора символов для XOR должны быть известны как отправителю, так и получателю. В одном из подходов каждый символ сопровождается идентификатором, который может использоваться в качестве начального числа для генератора псевдослучайных чисел для генерации этой информации, при этом отправитель и получатель выполняют один и тот же процесс.
В случае несистематических кодов Raptor исходные данные, которые должны быть закодированы, используются в качестве входных данных на этапе предварительного кодирования.
В случае систематических кодов Raptor вход на этап предварительного кодирования получается путем сначала применения операции, обратной операции кодирования, которая генерирует первые k выходных символов к исходным данным. Таким образом, применение нормальной операции кодирования к результирующим символам вызывает повторное создание исходных исходных символов в качестве первых k выходных символов кода. Необходимо гарантировать, что псевдослучайные процессы, которые генерируют первые k выходных символов, генерируют операцию, которая является обратимой.
Для декодирования кодов Raptor возможны два подхода. При конкатенированном подходе сначала декодируется внутренний код с использованием алгоритма распространения уверенности, который используется для кодов LT. Декодирование считается успешным, если эта операция восстанавливает достаточное количество символов, так что внешний код может восстановить оставшиеся символы с использованием алгоритма декодирования, подходящего для этого кода.
В комбинированном подходе отношения между символами, определяемыми как внутренним, так и внешним кодами, рассматриваются как единый комбинированный набор одновременных уравнений, который может быть решен обычными средствами, обычно с помощью исключения Гаусса.
Кодам Raptor требуется время O (размер символа) для генерации символа кодирования из исходного блока и требуется время O (размер исходного блока) для восстановления исходного блока из, по меньшей мере, k символов кодирования.
Накладные расходы - это количество дополнительных кодирующих символов сверх количества k исходных символов в исходном исходном блоке, которые необходимо принять для полного восстановления исходного блока. (Основываясь на соображениях элементарной теории информации, полное восстановление исходного блока с k исходными символами невозможно, если принято менее k кодирующих символов.) Вероятность восстановления - это вероятность того, что исходный блок полностью восстановлен после получения заданного количества случайные символы кодирования, генерируемые из исходного блока. Код RaptorQ, указанный в IETF RFC 6330, имеет следующий компромисс между вероятностью восстановления и накладными расходами на восстановление:
Эти утверждения справедливы для всего диапазона k, поддерживаемого в IETF RFC 6330, т. е. k = 1,..., 56403. Подробнее см. IETF RFC 6330.
Qualcomm, Inc. опубликовала заявление IPR для кода Raptor, указанного в IETF RFC 5053 и оператор IPR для более продвинутого кода RaptorQ, указанного в IETF RFC 6330. Эти утверждения отражают лицензионное обязательство Qualcomm, Inc. в отношении стандарта MPEG DASH. Стандарт MPEG DASH внедрен множеством компаний, в том числе компаниями-членами отраслевого форума DASH.
2. Реализацию Raptor Code RFC5053 с открытым исходным кодом можно найти здесь: https://code.google.com/p/raptor-code-rfc/
3. Информацию об эффективной программной реализации кода RaptorQ, указанного в IETF RFC 6330 (наиболее продвинутый исходный код), можно найти на веб-сайте проекта Codornices в ICSI..
