В информатике коды Raptor ( rap id tor nado ; [ 1] см. Коды Tornado ) являются первым известным классом фонтанных кодов с линейным временем кодирования и декодирования. Они были изобретены Амином Шокроллахи в 2000/2001 годах и впервые опубликованы в 2004 году в качестве расширенного реферата. Коды Raptor являются значительным теоретическим и практическим улучшением по сравнению с кодами LT , которые были первым практическим классом фонтанных кодов .
Коды Raptor, как и фонтанные коды в целом, кодируют заданный исходный блок данных, состоящий из числа k исходных символов одинакового размера, в потенциально неограниченную последовательность кодирующих символов, так что прием любых k или более кодирующих символов позволяет восстановить исходный блок с некоторой ненулевой вероятностью. Вероятность того, что исходный блок может быть восстановлен, увеличивается с числом полученных кодирующих символов, превышающим k, становясь очень близким к 1, как только число полученных кодирующих символов становится лишь немного больше k . Например, с последним поколением кодов Raptor, кодами RaptorQ, вероятность сбоя декодирования при получении k кодирующих символов составляет менее 1%, а вероятность сбоя декодирования при получении k+2 кодирующих символов составляет менее одного на миллион. Символ может быть любого размера, от одного байта до сотен или тысяч байт.
Коды Raptor могут быть систематическими или несистематическими . В систематическом случае символы исходного блока источника, т. е. исходные символы, включены в набор символов кодирования. Некоторые примеры систематического кода Raptor — это использование проекта 3rd Generation Partnership Project в мобильном сотовом беспроводном вещании и многоадресной передаче, а также стандартами DVB-H для IP-передачи данных на портативные устройства. [ необходима цитата ] Коды Raptor, используемые в этих стандартах, также определены в IETF RFC 5053.
Онлайн-коды являются примером несистематического фонтанного кода.
Самой продвинутой версией Raptor является код RaptorQ, определенный в IETF RFC 6330. Код RaptorQ представляет собой систематический код, может быть реализован таким образом, чтобы достичь линейной производительности кодирования и декодирования, имеет близкие к оптимальным свойства восстановления, поддерживает до 56 403 исходных символов и может поддерживать практически неограниченное количество символов кодирования.
Код RaptorQ, определенный в IETF RFC 6330, указан как часть стандарта Next Gen TV ( ATSC 3.0 ) для обеспечения высококачественной потоковой передачи видео (надежное мобильное ТВ) и эффективной и надежной доставки файлов вещания (datacasting). В частности, код RaptorQ указан в A/331 в ATSC 3.0. [2] См. Список стандартов ATSC для списка частей стандарта ATSC 3.0. Next Gen TV (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. [3]
Qualcomm, Inc. опубликовала заявление об IPR для кода Raptor, указанного в IETF RFC 5053, и заявление об IPR для более продвинутого кода RaptorQ, указанного в IETF RFC 6330. Эти заявления отражают лицензионные обязательства, принятые Qualcomm, Inc. в отношении стандарта MPEG DASH . Стандарт MPEG DASH был развернут широким кругом компаний, включая компании-члены DASH Industry Forum.