Код Раптора

В информатике Raptor коды ( rap id tor nado ; ^[1] см. коды Торнадо ) — первый известный класс фонтанных кодов с линейным кодированием и декодированием по времени. Они были изобретены Амином Шокроллахи в 2000/2001 году и впервые опубликованы в 2004 году в виде расширенного реферата. Коды Raptor представляют собой значительное теоретическое и практическое усовершенствование по сравнению с кодами LT , которые были первым практическим классом фонтанных кодов .

Коды Raptor, как и фонтанные коды в целом, кодируют заданный исходный блок данных, состоящий из числа k исходных символов одинакового размера, в потенциально неограниченную последовательность кодирующих символов, так что прием любых k или более кодовых символов позволяет исходному блоку быть восстановлены с некоторой ненулевой вероятностью. Вероятность того, что исходный блок может быть восстановлен, увеличивается по мере того, как количество принятых символов кодирования выше k становится очень близким к 1, как только количество полученных символов кодирования лишь немного превышает k . Например, в кодах Raptor последнего поколения, кодах RaptorQ, вероятность сбоя декодирования при k получении k+2 символов кодирования составляет менее 1%, а вероятность сбоя декодирования при получении символов кодирования меньше. чем один на миллион. Символ может иметь любой размер: от одного байта до сотен и тысяч байт.

Коды Raptor могут быть систематическими и несистематическими . В систематическом случае символы исходного исходного блока, т.е. исходные символы, включаются в набор символов кодирования. Некоторыми примерами систематического кода Raptor является использование в рамках проекта партнерства третьего поколения в мобильном сотовом беспроводном вещании и многоадресной передаче, а также в стандартах DVB-H для IP-передачи данных на портативные устройства. ^{[ нужна ссылка ]} Коды Raptor, используемые в этих стандартах, также определены в IETF RFC 5053.

Онлайн-коды являются примером несистематического исходного кода.

Код РаптораQ

Самой продвинутой версией Raptor является код RaptorQ, определенный в IETF RFC 6330. Код RaptorQ представляет собой систематический код, который может быть реализован таким образом, чтобы обеспечить производительность кодирования и декодирования с линейным временем, имеет почти оптимальные свойства восстановления, поддерживает до 56 403 исходные символы и может поддерживать практически неограниченное количество символов кодирования.

Код RaptorQ, определенный в IETF RFC 6330, указан как часть стандарта телевидения следующего поколения ( ATSC 3.0 ) для обеспечения высококачественной потоковой передачи видео (надежное мобильное телевидение) и эффективной и надежной доставки широковещательных файлов (передача данных). В частности, код RaptorQ указан в A/331 в ATSC 3.0. ^[2] Список стандартов ATSC стандартных деталей ATSC 3.0 см. в Списке . Телевидение следующего поколения (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, имеет следующий компромисс между вероятностью восстановления и накладными расходами на восстановление:

Вероятность восстановления более 99% с накладными расходами в 0 символов (восстановление из k полученных кодовых символов).
Вероятность восстановления более 99,99% с накладными расходами в 1 символ (восстановление из k+1 полученных кодовых символов).
Вероятность восстановления более 99,9999% с накладными расходами в 2 символа (восстановление из k+2 полученных символов кодирования).

Эти утверждения справедливы для всего диапазона k, поддерживаемого в IETF RFC 6330, т. е. k =1,...,56403. см. в IETF RFC 6330. Дополнительную информацию ^[3]

Юридический статус

Компания Qualcomm, Inc. опубликовала заявление о защите прав интеллектуальной собственности для кода Raptor, указанного в IETF RFC 5053, а также заявление о защите прав интеллектуальной собственности для более продвинутого кода RaptorQ, указанного в IETF RFC 6330. Эти заявления отражают лицензионные обязательства, взятые на себя компанией Qualcomm, Inc. в отношении тот Стандарт MPEG DASH . Стандарт MPEG DASH используется множеством компаний, включая компании-члены DASH Industry Forum.

См. также

Примечания

^ Амин Шокроллахи (31 января 2011 г.). Разработка кодов Raptor (Речь). Приглашенный доклад в Королевском технологическом институте . Проверено 24 февраля 2012 г.
^ Кандидатский стандарт ATSC: сигнализация, доставка, синхронизация и защита от ошибок (A/331) (PDF) (отчет). Комитет по передовым телевизионным системам. 22 марта 2017. ATSC S33-174r6.
^ Луби М., Шокроллахи А., Уотсон М., Стокхаммер Т., Миндер Л. (август 2011 г.). Запрос комментариев: 6330. Схема прямого исправления ошибок RaptorQ для доставки объекта (отчет). ISSN 2070-1721 .

Ссылки

ATSC 3.0 (Комитет по передовым телевизионным стандартам 3.0)
3GPP (Проект партнерства третьего поколения)
DVB (цифровое видеовещание)
3GPP TS26.346 Техническая спецификация 3GPP для службы мультимедийного вещания/многоадресной передачи: протоколы и кодеки.
RFC5053 Схема прямого исправления ошибок Raptor для доставки объекта
Характеристики IP-передачи данных DVB-H

Дальнейшее чтение

Шокроллахи, Амин (июнь 2006 г.). «Коды Раптора» (PDF) . Транзакции IEEE по теории информации . 52 : 2551–2567. дои : 10.1109/TIT.2006.874390 .
Результат поиска «IPR» для RFC 5053 с заявлениями некоторых владельцев патентов.
Результат поиска «IPR» для RFC 6330 с заявлениями некоторых владельцев патентов.

[1] Амин Шокроллахи (31 января 2011 г.). Разработка кодов Raptor (Речь). Приглашенный доклад в Королевском технологическом институте . Проверено 24 февраля 2012 г.

[2] Кандидатский стандарт ATSC: сигнализация, доставка, синхронизация и защита от ошибок (A/331) (PDF) (отчет). Комитет по передовым телевизионным системам. 22 марта 2017. ATSC S33-174r6.

[RFC_6330-3] Луби М., Шокроллахи А., Уотсон М., Стокхаммер Т., Миндер Л. (август 2011 г.). Запрос комментариев: 6330. Схема прямого исправления ошибок RaptorQ для доставки объекта (отчет). ISSN 2070-1721 .

[1]

[2]

[3]