Код фонтана

Класс кодов в теории кодирования

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

Фонтанный код является оптимальным, если исходные 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 исходными символами в исходном блоке и в общей сложности с 65536 закодированными символами, сгенерированными для исходного блока. Этот код имеет средние относительные издержки приема 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 — прямое исправление ошибок» . 30 мая 2014 г.
3. (Шокроллахи 2006)
4. Т. Стокхаммер, А. Шокроллахи, М. Уотсон, М. Луби, Т. Гасиба (март 2008 г.). Фурт, Б.; Ахсон, С. (ред.). «Прямое исправление ошибок прикладного уровня для мобильного мультимедийного вещания». Справочник мобильного вещания: DVB-H, DMB, ISDB-T и Media FLO . ЦРК Пресс .{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
5. Астерис, Мегасфенис; Димакис, Александрос Г. (2012). «Ремонтные коды фонтанов». Журнал IEEE по избранным областям коммуникаций . 32 (5): 1037–1047. arXiv : 1401.0734 . doi : 10.1109/JSAC.2014.140522. S2CID  1300984.
6. Арслан, Суайб С. (2014). «Дополнительная избыточность, фонтанные коды и дополнительные темы». arXiv : 1402.6016 [cs.IT].
7. Луби, Майкл; Падовани, Роберто; Ричардсон, Томас Дж.; Миндер, Лоренц; Аггарвал, Пуджа (2019). «Жидкое облачное хранилище». Транзакции ACM в хранилище . 15 : 1–49. arXiv : 1705.07983 . дои : 10.1145/3281276. S2CID  738764.
8. Луби, М.; Падовани, Р.; Ричардсон, Т.; Миндер, Л.; Аггарвал, П. (2017). «Жидкое облачное хранилище». arXiv : 1705.07983v1 [cs.DC].

Рекомендации

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