stringtranslate.com

Фонтанный код

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

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

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

Приложения

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

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

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

В стандартах

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

Более продвинутый код Raptor с большей гибкостью и улучшенными накладными расходами на прием, называемый RaptorQ, был указан в IETF RFC 6330. Указанный код RaptorQ может использоваться с 56 403 исходными символами в исходном блоке и в общей сложности с 16 777 216 закодированными символами, сгенерированными для исходного блока. Этот код способен восстановить исходный блок из любого набора закодированных символов, равного количеству исходных символов в исходном блоке с высокой вероятностью, а в редких случаях — из немного большего количества исходных символов в исходном блоке. Код RaptorQ является неотъемлемой частью экземпляра ROUTE, указанного в ATSC A-331 (ATSC 3.0)

Для хранения данных

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

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

Смотрите также

Примечания

  1. ^ Дж. Байерс, М. Луби , М. Митценмахер , А. Реге (1998). «Цифровой фонтанный подход к надежному распределению объемных данных» (PDF) .{{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка )
  2. ^ "Qualcomm Raptor Technology - Forward Error Correction". 2014-05-30. Архивировано из оригинала 2010-12-29 . Получено 2011-06-07 .
  3. ^ (Шокроллахи 2006)
  4. ^ T. Stockhammer, A. Shokrollahi, M. Watson, M. Luby, T. Gasiba (март 2008 г.). Furht, B.; Ahson, S. (ред.). "Application Layer Forward Error Correction for Mobile Multimedia Broadcasting". Справочник по мобильному вещанию: DVB-H, DMB, ISDB-T и Media FLO . CRC Press .{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
  5. ^ Asteris, Megasthenis; Dimakis, Alexandros G. (2012). «Восстанавливаемые коды Fountain». Журнал IEEE по избранным областям в коммуникациях . 32 (5): 1037–1047. arXiv : 1401.0734 . doi : 10.1109/JSAC.2014.140522. S2CID  1300984.
  6. ^ Арслан, Суайб С. (2014). «Инкрементная избыточность, коды Fountain и продвинутые темы». arXiv : 1402.6016 [cs.IT].
  7. ^ Luby, Michael; Padovani, Roberto; Richardson, Thomas J.; Minder, Lorenz; Aggarwal, Pooja (2019). «Liquid Cloud Storage». ACM Transactions on Storage . 15 : 1–49. arXiv : 1705.07983 . doi : 10.1145/3281276. S2CID  738764.
  8. ^ Луби, М.; Падовани, Р.; Ричардсон, Т.; Миндер, Л.; Аггарвал, П. (2017). «Жидкое облачное хранилище». arXiv : 1705.07983v1 [cs.DC].

Ссылки