Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску

В теории кодирования , фонтан кодов (также известную как rateless коды стирания ) представляют собой класс стирания кодов со свойством , что потенциально безгранична последовательность из кодирующих символов может быть сформирована из заданного набора исходных символов таким образом, что исходные исходные символы могут быть идеально восстанавливается из любого подмножества кодирующих символов, размер которых равен количеству исходных символов или лишь немного превышает его. Термин " фонтан" или " бесскоростной" относится к тому факту, что эти коды не имеют фиксированной кодовой скорости .

Исходный код является оптимальным, если исходные k исходных символов могут быть восстановлены из любых k успешно принятых кодирующих символов (т. Е. Исключая те, которые были стерты). Известны фоновые коды, которые имеют эффективные алгоритмы кодирования и декодирования и позволяют с высокой вероятностью восстанавливать исходные k исходных символов из любых k ' символов кодирования, где k' лишь немного больше k .

Коды LT были первой практической реализацией кодов фонтанов. Raptor коды и онлайн коды были впоследствии введены, и достичь линейное время кодирования и декодирования сложности через предварительного кодирования стадии входных символов.

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

Приложения [ править ]

Коды фонтана гибко применимы при фиксированной кодовой скорости или там, где фиксированная кодовая скорость не может быть определена априори, и где требуется эффективное кодирование и декодирование больших объемов данных.

Одним из примеров является карусель данных , когда некоторый большой файл непрерывно транслируется на набор приемников. [1] Используя код стирания с фиксированной скоростью, получатель, у которого отсутствует исходный символ (из-за ошибки передачи), сталкивается с проблемой сборщика купонов : он должен успешно получить кодирующий символ, которого у него еще нет. Эта проблема становится гораздо более очевидной при использовании традиционного короткого кода стирания, поскольку файл должен быть разделен на несколько блоков, каждый из которых кодируется отдельно: теперь получатель должен собрать необходимое количество недостающих символов кодирования для каждого блока. Используя исходный код, приемнику достаточно получить любойподмножество кодирующих символов размером немного больше, чем набор исходных символов. (На практике трансляция обычно планируется оператором на фиксированный период времени на основе характеристик сети и приемников и желаемой надежности доставки, и, таким образом, исходный код используется с кодовой скоростью, которая определяется динамически в то время, когда файл запланирован для трансляции.)

Другое применение - гибридный ARQ в сценариях надежной многоадресной рассылки : информация о четности, запрашиваемая получателем, потенциально может быть полезна для всех получателей в группе многоадресной рассылки.

Коды фонтанов в стандартах [ править ]

Коды Raptor являются наиболее эффективными исходными кодами в настоящее время [2], имеющие очень эффективные алгоритмы линейного кодирования и декодирования и требующие лишь небольшого постоянного числа операций XOR на сгенерированный символ как для кодирования, так и для декодирования. [3]

Код Raptor, указанный в IETF RFC 5053, 3GPP MBMS и других коммерческих стандартах [ править ]

IETF RFC 5053 подробно определяет систематический код Raptor, который был принят во многие стандарты помимо IETF, например, в стандарте 3GPP MBMS для широковещательной доставки файлов и потоковых услуг, стандарт DVB-H IPDC для доставки IP-услуг по сетям DVB. , и DVB-IPTVдля предоставления коммерческих ТВ-услуг по IP-сети. Этот код может использоваться с 8192 исходными символами в исходном блоке и в общей сложности до 65 536 кодированных символов, сгенерированных для исходного блока. Этот код имеет средние относительные издержки приема 0,2% при применении к исходным блокам с 1000 исходных символов и имеет относительные издержки приема менее 2% с вероятностью 99,9999%. [4] Относительные накладные расходы на прием определяются как дополнительные данные кодирования, требуемые сверх длины исходных данных для восстановления исходных данных, измеряемые в процентах от размера исходных данных. Например, если относительные накладные расходы на прием составляют 0,2%, это означает, что исходные данные размером 1  мегабайт могут быть восстановлены из 1,002 мегабайта данных кодирования.

Код RaptorQ, указанный в IETF RFC 6330 и ATSC 3.0 (телевидение следующего поколения) [ править ]

Более продвинутый код Raptor с большей гибкостью и улучшенными накладными расходами на прием, называемый RaptorQ, был определен в IETF RFC 6330. Указанный код RaptorQ может использоваться с до 56 403 исходных символов в исходном блоке, а всего до 16 777 216 закодированных символы, созданные для исходного блока. Этот код может восстанавливать исходный блок из любого набора кодированных символов, равного количеству исходных символов в исходном блоке, с высокой вероятностью, а в редких случаях - из немного большего, чем количество исходных символов в исходном блоке.

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

Коды фонтанов для хранения данных [ править ]

Коды стирания используются в приложениях для хранения данных благодаря значительной экономии количества единиц хранения для заданного уровня избыточности и надежности. Требования к дизайну кода стирания для хранения данных, особенно для приложений распределенного хранения, могут сильно отличаться от сценариев обмена данными или потоковой передачи данных. Одним из требований кодирования для систем хранения данных является систематическая форма, т. Е. Символы исходного сообщения являются частью закодированных символов. Систематическая форма позволяет считывать символы сообщения без декодирования из блока хранения. Кроме того, поскольку пропускная способность и коммуникационная нагрузка между узлами хранения могут быть узким местом, коды, обеспечивающие минимальную связь, очень полезны, особенно когда узел выходит из строя и требуется реконструкция системы для достижения начального уровня избыточности.В этом отношении ожидается, что исходные коды обеспечат эффективный процесс восстановления в случае сбоя: когда один кодированный символ потерян, он не должен требовать слишком большого объема обмена данными и вычислений среди других кодированных символов, чтобы восстановить потерянный символ. Фактически, задержка восстановления иногда может быть важнее экономии места для хранения. Коды ремонтируемых фонтанов[5] предназначены для решения задач проектирования фонтанного кода для систем хранения. Подробный обзор кодов фонтанов и их применения можно найти на сайте. [6]

Другой подход к распределенному хранилищу с использованием исходных кодов был предложен в Liquid Cloud Storage. [7] [8] Жидкое облачное хранилище основано на использовании большого кода стирания, такого как код RaptorQ, указанный в IETF RFC 6330 (который обеспечивает значительно лучшую защиту данных, чем другие системы), с использованием процесса фонового восстановления (что значительно сокращает ремонт требования к полосе пропускания по сравнению с другими системами), а также с использованием организации потоковых данных (которая обеспечивает быстрый доступ к данным, даже если доступны не все закодированные символы).

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

  • Онлайн коды
  • Линейное сетевое кодирование
  • Обмен секретами
  • Коды торнадо , предшественник кодов фонтана

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

  1. ^ J. Байерс, М. Лубы , М. Mitzenmacher , А. Rege (1998). «Подход цифрового фонтана к надежному распределению больших объемов данных» (PDF) .CS1 maint: несколько имен: список авторов ( ссылка )
  2. ^ «Технология Qualcomm Raptor - Прямое исправление ошибок» . 2014-05-30.
  3. ^ ( Шокроллахи 2006 )
  4. ^ Т. Штокхаммер, А. Shokrollahi, М. Уотсон, М. Лубы, Т. Gasiba (март 2008). Furht, B .; Ахсон, С. (ред.). «Прямое исправление ошибок прикладного уровня для мобильного мультимедийного вещания». Справочник по мобильному вещанию: DVB-H, DMB, ISDB-T и Media FLO . CRC Press .CS1 maint: несколько имен: список авторов ( ссылка )
  5. ^ Астерис, Мегастенис; Димакис, Александрос Г. (2012). «Ремонтные фонтанные коды». Журнал IEEE по избранным областям коммуникаций . 32 (5): 1037–1047. arXiv : 1401.0734 . DOI : 10.1109 / JSAC.2014.140522 .
  6. ^ Арслан, Суайб С. (2014). «Инкрементное резервирование, исходные коды и дополнительные темы». arXiv : 1402.6016 [ cs.IT ].
  7. ^ Луби, Майкл; Падовани, Роберто; Ричардсон, Томас Дж .; Миндер, Лоренц; Аггарвал, Пуджа (2019). «Жидкое облачное хранилище». ACM-транзакции в хранилище . 15 : 1–49. arXiv : 1705.07983 . DOI : 10.1145 / 3281276 .
  8. ^ Luby, M .; Padovani, R .; Richardson, T .; Миндер, Л .; Аггарвал П. (2017). «Жидкое облачное хранилище». arXiv : 1705.07983v1 [ cs.DC ].

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

  • Амин Шокроллахи и Майкл Луби (2011). «Коды хищников». Основы и тенденции в теории коммуникации и информации . Теперь издатели. 6 (3–4): 213–322. DOI : 10.1561 / 0100000060 .
  • Луби, Майкл (2002). «Коды LT». Симпозиум IEEE по основам информатики : 271–282. DOI : 10.1109 / sfcs.2002.1181950 . ISBN 0-7695-1822-2.
  • А. Shokrollahi (2006), "Раптор кода", IEEE Transactions по теории информации , 52 (6): 2551-2567, DOI : 10,1109 / tit.2006.874390.
  • П. Маймунков (ноябрь 2002 г.). «Онлайн-коды» (PDF) . (Технический отчет) .
  • Дэвид Дж. К. Маккей (2003). Теория информации, выводы и алгоритмы обучения . Издательство Кембриджского университета. Bibcode : 2003itil.book ..... M . ISBN 0-521-64298-1.
  • М. Луби , А. Шокроллахи , М. Уотсон, Т. Стокхаммер (октябрь 2007 г.), Схема прямого исправления ошибок Raptor для доставки объектов , RFC  5053CS1 maint: несколько имен: список авторов ( ссылка ).
  • М. Луби , А. Шокроллахи , М. Уотсон, Т. Стокхаммер, Л. Миндер (май 2011 г.), Схема прямого исправления ошибок RaptorQ для доставки объектов , RFC  6330CS1 maint: несколько имен: список авторов ( ссылка ).