Введение
Класс кодов в теории кодирования
В теории кодирования фонтанные коды (также известные как коды стирания без ограничения скорости) представляют собой класс кодов стирания, обладающих свойством, что из заданного набора исходных символов может быть сгенерирована потенциально неограниченная последовательность кодирующих символов, при этом исходные символы могут быть идеально восстановлены из любого подмножества кодирующих символов, размер которого равен или лишь незначительно превышает количество исходных символов. Термин "фонтан" или "без скорости" отражает тот факт, что эти коды не имеют фиксированной скорости кодирования. Фонтанный код считается оптимальным, если исходные k исходных символов могут быть восстановлены из любых k успешно принятых кодирующих символов (то есть исключая стертые). Существуют фонтанные коды с эффективными алгоритмами кодирования и декодирования, позволяющие восстановить исходные k исходных символов из любого k’ кодирующих символов с высокой вероятностью, где k’ лишь немного больше k.
In coding theory, fountain codes (also known as rateless erasure codes) are a class of erasure codes with the property that a potentially limitless sequence of encoding symbols can be generated from a given set of source symbols such that the original source symbols can ideally be recovered from any subset of the encoding symbols of size equal to or only slightly larger than the number of source symbols. The term fountain or rateless refers to the fact that these codes do not exhibit a fixed code rate. A fountain code is optimal if the original k source symbols can be recovered from any k successfully received encoding symbols (i. e., excluding those that were erased). Fountain codes are known that have efficient encoding and decoding algorithms and that allow the recovery of the original k source symbols from any k’ of the encoding symbols with high probability, where k’ is just slightly larger than k.
LT-коды стали первой практической реализацией фонтанных кодов. Впоследствии были разработаны коды Raptor и онлайн-коды, достигающие линейной временной сложности кодирования и декодирования за счет предварительного этапа кодирования входных символов.
Приложения
Коды-источники гибко применимы при фиксированной скорости кодирования или в тех случаях, когда фиксированную скорость кодирования невозможно определить априори, и когда требуется эффективное кодирование и декодирование больших объемов данных. Одним из примеров является карусель данных, где большой файл непрерывно транслируется группе приемников. При использовании кода стирания с фиксированной скоростью, приемник, потерявший исходный символ (из-за ошибки передачи), сталкивается с проблемой коллекционера купонов: ему необходимо успешно принять кодирующий символ, которого у него еще нет. Эта проблема становится особенно заметной при использовании традиционного кода стирания малой длины, поскольку файл необходимо разделить на несколько блоков, каждый из которых кодируется отдельно: приемнику теперь нужно собрать необходимое количество недостающих кодирующих символов для каждого блока. При использовании кода-источника достаточно, чтобы приемник получил любое подмножество кодирующих символов, размер которого лишь немного превышает размер набора исходных символов. (На практике трансляция обычно планируется оператором на фиксированный период времени, исходя из характеристик сети и приемников, а также требуемой надежности доставки, и, следовательно, код-источник используется с динамически определяемой скоростью кодирования в момент планирования трансляции файла.) Другое применение – гибридный ARQ в надежных сценариях многоадресной рассылки: информация о четности, запрошенная приемником, потенциально может быть полезна для всех приемников в группе многоадресной рассылки.
В стандартах
Коды Raptor являются наиболее эффективными фонтанными кодами на сегодняшний день, обладая высокоэффективными алгоритмами кодирования и декодирования с линейной сложностью и требуя лишь небольшого постоянного числа операций XOR на генерируемый символ как при кодировании, так и при декодировании. IETF RFC 5053 подробно описывает систематический код Raptor, который был принят во множество стандартов, выходящих за рамки IETF, таких как стандарт 3GPP MBMS для доставки файлов и потоковых сервисов, стандарт DVB-H IPDC для предоставления IP-услуг по сетям DVB и DVB-IPTV для предоставления коммерческих телевизионных услуг по IP-сети. Этот код может использоваться с блоком источника, содержащим до 8192 исходных символов, и генерировать в общей сложности до 65536 кодированных символов для этого блока. При применении к блокам источника с 1000 исходными символами этот код имеет средний относительный избыток приема 0,2%, а относительный избыток приема составляет менее 2% с вероятностью 99,9999%. Относительный избыток приема определяется как дополнительные данные кодирования, необходимые сверх объема исходных данных для восстановления исходных данных, выраженные в процентах от объема исходных данных. Например, если относительный избыток приема составляет 0,2%, это означает, что исходные данные размером 1 Мбайт могут быть восстановлены из 1,002 Мбайт закодированных данных. Более продвинутый код Raptor с большей гибкостью и улучшенным избытком приема, известный как RaptorQ, описан в IETF RFC 6330. Указанный код RaptorQ может использоваться с блоком источника, содержащим до 56403 исходных символа, и генерировать в общей сложности до 16777216 кодированных символов для этого блока. Этот код способен восстановить блок источника из любого набора кодированных символов, равного числу исходных символов в блоке источника, с высокой вероятностью, а в редких случаях – из немного большего числа исходных символов в блоке источника. Код RaptorQ является неотъемлемой частью реализации ROUTE, определенной в ATSC A 331 (ATSC 3.0).