В информатике коды Raptor ( rap id tor nado ; [1] см . коды Торнадо ) — первый известный класс фонтанных кодов с линейным кодированием и декодированием по времени. Они были изобретены Амином Шокроллахи в 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 представляет собой систематический код, который может быть реализован таким образом, чтобы обеспечить линейное время кодирования и декодирования, имеет почти оптимальные свойства восстановления (см. Вероятность восстановления и раздел служебных данных ниже для более подробной информации), поддерживает до 56 403 исходных символов и может поддерживать практически неограниченное количество символов кодирования.
Код RaptorQ, определенный в IETF RFC 6330, указан как часть стандарта телевидения следующего поколения ( ATSC 3.0 ) для обеспечения высококачественной потоковой передачи видео (надежное мобильное телевидение) и эффективной и надежной доставки широковещательных файлов (передача данных). В частности, код RaptorQ указан в документе A/331: Сигнализация, доставка, синхронизация и защита от ошибок в ATSC 3.0 (список частей стандарта ATSC 3.0 см. в Списке стандартов ATSC). Телевидение следующего поколения (ATSC 3.0) выходит далеко за рамки традиционного телевидения и обеспечивает широковещательный Интернет, обеспечивающий общие услуги доставки данных.
Коды Raptor образуются путем объединения двух кодов.
Код стирания с фиксированной скоростью , обычно с довольно высокой скоростью, применяется в качестве «предварительного кода» или «внешнего кода». Этот предварительный код сам по себе может быть конкатенацией нескольких кодов, например, в коде, стандартизированном 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. опубликовала заявление о защите прав интеллектуальной собственности для кода Raptor, указанного в IETF RFC 5053, а также заявление о защите прав интеллектуальной собственности для более продвинутого кода RaptorQ, указанного в IETF RFC 6330. Эти заявления отражают лицензионные обязательства, взятые на себя компанией Qualcomm, Inc. в отношении стандарт MPEG DASH . Стандарт MPEG DASH используется множеством компаний, включая компании-члены DASH Industry Forum.