Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску
Эта статья о кодах исправления ошибок. Для кодовых баз с именем raptor см. Raptor (значения) .

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

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

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

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

Код RaptorQ [ править ]

Наиболее продвинутой версией Raptor является код RaptorQ, определенный в IETF RFC 6330. Код RaptorQ является систематическим кодом, может быть реализован таким образом, чтобы обеспечить линейное время кодирования и декодирования, имеет почти оптимальные свойства восстановления (см. Вероятность восстановления и раздел служебных данных ниже для получения дополнительной информации), поддерживает до 56 403 исходных символов и может поддерживать практически неограниченное количество символов кодирования. Есть несколько реализаций RaptorQ доступны, в том числе основной реализации TvRq , пригодная для тестирования совместимости, версии , разработанной в проекте OpenRQ , в версии libRaptorQ , в реализации ржавчины RaptorQ , а высокопроизводительная коммерческая реализация RaptorQ, предлагаемая BitRipple .

Next Gen TV (ATSC 3.0) включает код RaptorQ [ править ]

Код RaptorQ, определенный в IETF RFC 6330, определен как часть стандарта Next Gen TV ( ATSC 3.0 ) для обеспечения высококачественной потоковой передачи видеоизображения (надежное мобильное телевидение) и эффективной и надежной доставки файлов широковещания (передача данных). В частности, код RaptorQ указан в A / 331: Сигнализация, доставка, синхронизация и защита от ошибок в рамках ATSC 3.0 (см. Список стандартов ATSC для получения списка стандартных частей ATSC 3.0). Новое поколение телевидения (ATSC 3.0) выходит далеко за рамки традиционного телевидения и обеспечивает широковещательный Интернет, позволяющий предоставлять общие услуги доставки данных.

Обзор [ править ]

Коды хищников образуются путем объединения двух кодов.

Код стирания с фиксированной скоростью , обычно с довольно высокой скоростью, применяется как «предварительный код» или «внешний код». Этот предварительный код сам по себе может быть конкатенацией множества кодов, например, в коде, стандартизированном 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.

Правовой статус [ править ]

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

См. Также [ править ]

  • Код стирания
  • Код LT
  • Коды фонтанов
  • Майкл Луби
  • Коды торнадо

Заметки [ править ]

  1. ^ Амин Шокроллахи (31 января 2011). Разработка кодов хищников (речь). Приглашенный доклад в Kungliga Tekniska högskolan . Проверено 24 февраля 2012 года .

2. Реализацию Raptor Code RFC5053 с открытым исходным кодом можно найти здесь: https://code.google.com/p/raptor-code-rfc/ [ мертвая ссылка ]

3. Информацию об эффективной программной реализации кода RaptorQ, указанного в IETF RFC 6330 (наиболее продвинутый исходный код), можно найти на этой веб-странице BitRipple .

Ссылки [ править ]

  • Амин Шокроллахи и Майкл Луби (2011). «Коды хищников». Основы и тенденции в теории коммуникации и информации . Теперь издатели. 6 (3–4): 213–322. DOI : 10.1561 / 0100000060 . S2CID  1731099 .
  • Шокроллахи, Амин, «Коды хищников», IEEE Transactions on Information Theory, vol. 52, pp. 2551-2567, 2006. PDF (требуется авторизация)
  • ATSC 3.0 (Комитет по передовым телевизионным стандартам 3.0)
  • 3GPP (Проект партнерства третьего поколения)
  • DVB (цифровое видеовещание)
  • 3GPP TS26.346 Техническая спецификация 3GPP для службы мультимедийного вещания / многоадресной передачи: протоколы и кодеки.
  • RFC5053 Схема прямого исправления ошибок Raptor для доставки объектов
  • Характеристики IP-передачи данных DVB-H
  • RFC6330 Схема прямого исправления ошибок RaptorQ для доставки объектов
  • [1] Результат поиска "IPR" для RFC 5053 с заявлениями некоторых владельцев патентов.
  • [2] Результат поиска "IPR" для RFC 6330 с заявлениями некоторых владельцев патентов.