Введение
Сообщения, передаваемые в пакетных сетях, имеют конечный размер и представляют собой файлы данных. Файлы пересылаются отправителем последовательностью пакетов. Размер пакета в битах обычно «навязан» стандартами или давно существующей архитектурой сети. В идеале каждый из пакетов должен быть принят без ошибок получателем файла. Однако часть пакетов может быть не доставлена до получателя («потеряна»), а часть – доставлена с обнаруженными получателем ошибочными битами. Содержимое таких пакетов, в последовательности принимаемых получателем, можно считать стёртыми. Поэтому в качестве базовой математической модели для описания канала с помехами в пакетных сетях используется модель канала со стираниями (erasure channel) пакетов.
 |
| Рис. 1. Модель канала со стираниями 3-битовых пакетов. |
Модель канала имеет q входов и q+1 выход, где q=2k, k – число бит в пакете (рис.1). Выход, отмеченный знаком "?", является стирающим. Стирание происходит с вероятностью P. Правильный приём пакетов производится с вероятностью 1-P.
Для обнаружения ошибок в пакетах получателем отправитель обычно использует код. Простейшим примером такого кода является контрольная сумма бит пакета. В большинстве сетевых приложений используются более сложные коды. Классическими кодами для обнаружения, как независимых ошибок, так и серии ошибок в последовательно расположенных битах, являются циклические коды, которые принято обозначать как CRC-r (где r=4,8,16,32)1 . Эти коды гарантировано обнаруживают серии ошибок длины r.
Для любого кода, и для CRC-r в частности, существует отличная от нуля вероятность не обнаруженной ошибки. Код не способен обнаружить ошибку в ситуации, когда переданное кодовое слово было преобразовано помехами в канале в другое кодовое слово. Такое преобразование иногда называют трансформацией кодовых слов. Поэтому модель канала со стиранием пренебрегает вероятностью ошибочно принятого пакета, связанной с трансформацией кодовых слов. Для большинства применений такое пренебрежение оправдано ввиду чрезвычайно малой вероятности трансформации. Именно эта ситуация и предполагается при использовании рассмотренной выше модели канала со стиранием.
Традиционно для повышения достоверности доставки сообщений в каналах со стиранием используются методы (протоколы), основанные на использовании обратного канала от получателя к отправителю. Примером таких протоколов являются Интернет-протоколы TCP (FTP, HTTP).
А что следует ожидать от использования кодирования в таких каналах? Рассмотрим пример. Пусть файл, состоящий из K исходных пакетов, передаётся по каналу со стиранием с помощью N кодовых пакетов. При этом некоторая случайная часть пакетов будет потеряна, оставшаяся часть будет правильно принята получателем. Предположим, что эта часть равна или почти равна K. Может ли при этом декодер по этим K случайно выбранным из N кодовым пакетам восстановить (реконструировать) K исходных пакетов? Да, может. Если это так, то время доставки файла минимально при "быстрых" алгоритмах кодирования и декодирования. Значит, при использовании кодирования необходимость в обратном канале отпадает.
В этой связи уместно обратить внимание на двойственность термина FEC. В сетевой терминологии под этим термином понимаются коды в каналах со стираниями (erasure codes). О них пойдёт речь в статье. Это не противоречит несколько иному, использованному в аннотации статьи, толкованию термина, связывающего его с кодированием для систем без обратного канала. Именно при использовании кодирования во многих сетевых приложениях отпадает необходимость в обратном канале и значительно снижается объём сетевого трафика.
Аргументы «за» и требования к коду
Целью этого раздела является рассмотрение нескольких характерных задач доставки сообщений в пакетных сетях с традиционным использованием обратного канала (А) и без обратного канала или с его ограниченным использованием при наличии помехоустойчивого кодирования (Б). Рассмотрение этих задач позволяет в общих чертах понять разумность использования кодирования и сформулировать требования к помехоустойчивому коду.
Задача «один – одному»
В этой простейшей задаче один отправитель отправляет сообщение одному получателю.
- При использовании доставки с обратным каналом возможно несколько схем (протоколов) организации связи. Рассмотрим две из них.
В первой схеме получатель может использовать обратный канал только для передачи информации отправителю о стёртых пакетах. При получении такого сообщения отправитель ретранслирует (передаёт повторно) стёртый пакет.
Во второй альтернативой схеме получатель передаёт по обратному каналу каждый принятый пакет. Отправитель сравнивает его с переданным пакетом. В случае их несоответствия пакет объявляется стёртым, и производится его ретрансляция.
Очевидно, что при передаче сообщений по первой схеме число ретрансляций пропорционально вероятности стирания пакета P . При передаче сообщений по второй схеме число копий одного пакета, принятых получателем, также пропорционально вероятности P. Каждый принятый пакет передаётся по обратному каналу. Значит, и в этом случае загруженность обратного канала пропорциональна вероятности стирания пакета P.
Итак, повышение достоверности приёма сообщения при ретрансляционных методах достигается за счёт увеличения нагрузки на обратный канал.
- Какой код следует использовать? Не претендуя на строгость, основное свойство "хорошего" кода для канала со стиранием, можно найти из следующих рассуждений. Пропускная способность канала со стиранием равна 1-P пакетов (или (1-P)k бит). Это означает, что из достаточно большого числа N переданных пакетов только (1-P)N пакетов в среднем будут доставлены; остальные – стёрты. Согласно теореме Шеннона, к этой величине можно приблизиться сколь угодно близко помехоустойчивым кодированием. Пусть через канал со стиранием блоковым (N,K) кодом передаётся файл, состоящий из K исходных пакетов. Тогда, если величина (1-P)N не меньше K, в среднем будут доставлены K пакетов. Отсюда следует, что достичь пропускной способности канала позволяет код со скоростью Rc=1-P, где Rc=K/N, при условии возможности реконструкции исходного сообщения по любым K кодовым пакетам. Этот принцип доставки файла по любым K кодовым пакетам уже был сформулирован во «Введении». Он стал отправной точкой для конструирования кодов в каналах со стираниями.
Скорость кода Rc=K/N должна быть выбрана исходя из ожидаемой вероятности стирания P до передачи сообщения. Если же реальная вероятность стирания неизвестна и больше ожидаемой, получатель в среднем будет принимать меньше чем K пакетов, в результате снизится вероятность доставки сообщения2 . В такой ситуации требуется введение дополнительных проверочных символов, т.е. использование кода (N`,K) с меньшей скоростью, когда N`>N. В результате приходим к необходимости добавить "на лету" (on-the-fly, on-line) немного проверочных символов. Будем считать, что это возможно. Более того, будем считать, что есть код типа файл поток или файл фонтан. Это означает, что кодер может закодировать файл потенциально-неограниченным потоком пакетов. Без предпринятая каких-либо мер по перекрытию фонтана поток кодированных пакетов будет литься от кодера сколь угодно долго. На практике кран кодового фонтана рано или поздно будет перекрыт. Сделать это может как сам отправитель, так и получатель сообщения. В первом случае отправитель может руководствоваться принципом достаточности. Во втором – получатель отправляет одно сообщение-квитанцию (ограниченное использование обратного канала) отправителю, подтверждающее полученное в целом сообщение из K пакетов. Если кран перекрыл отправитель, а получатель всё-таки не получил сообщение, посылается запрос на открытие кодового фонтана для получения небольшого числа кодовых пакетов (вновь ограниченное использование обратного канала). И кодер должен быть способен по запросу сгенерировать небольшое число кодовых пакетов за приемлимое время.
Задача «один – многим»
Рассмотрим задачу, в которой один отправитель посылает сообщение группе из большого числа клиентов. Для примера, в качестве отправителя может выступать как одиночный сервер, так и ближайший к группе получателей узел IP Multicast-дерева.
 |
| Рис.2. Фонтан – прототип кодового потока. |
- При отсутствии кодирования сообщение от отправителя до отдельного получателя проходит свой канал со стиранием. Эти каналы статистически не зависимы, поэтому каждый клиент получит случайную часть (1-P)N пакетов из N, переданных отправителем. Если при этом каждый пакет, который был потерян одним или более получателями, будет ретранслирован отправителем, то каждый получатель примет копии ранее принятых (не потерянных) пакетов. В результате прямой канал будет использован далеко не самым эффективным образом. При этом стоимость доставки сообщения в расчёте на одного получателя оказывается высокой.
- Из кодера бьёт фонтан пакетов (рис.2). Часть «брызг» (пакетов) теряется для отдельного получателя. Через некоторое время получатель, приняв K кодовых пакетов, отключается от приёма. Другой получатель примет «по брызгам» в общем случае другие K кодовых пакетов и т.д. Поскольку по любым K кодовым пакетам декодер каждого получателя может реконструировать сообщение, все клиенты примут из фонтана сообщение. Отправителю требуется лишь перекрыть фонтан пакетов исходя из принципа разумной достаточности по отношению ко всем получателям. В результате общий объём трафика прямого канала будет значительно ниже в сравнении с рассмотренным выше случаем использования обратного канала. Стоимость доставки в расчёте на одного получателя также будет ниже.
Задача «многие – одному»
Рассмотрим задачу доставки файлов, копии которых расположены на нескольких зеркальных серверах.
- Традиционным способом доставки является способ доставки с одного из ближайших зеркальных серверов.
- Предположим, что кодер каждого сервера может генерировать независимые друг от друга кодовые пакеты. Тогда декодер получателя файла, приняв, в общей сложности, от всех серверов любые K кодовых пакетов, реконструирует файл. В итоге реализуется параллельная загрузка.
Задача «многие – многим»
Если в задаче «один многим» в качестве отправителя рассматривать много зеркальных серверов, то задача доставки многим получателям объединяет в себе черты двух предыдущих задач.
Коды и алгоритмы кодирования/декодирования
Сегодня можно говорить о создании нового класса помехоустойчивых кодов для каналов со стиранием. Кодами из этого класса можно закодировать сообщение конечного размера (файл) потенциально-неограниченным потоком независимых пакетов. Это свойство нового класса кодов принципиально отличает его от классических блоковых или свёрточных, помехоустойчивых кодов с заданной скоростью. При кодировании файла этими кодами получаем также файл кодированных данных, а не поток. По этой причине, для кодов из нового класса появился термин "rateless" в противовес классическим кодам, для которых используется термин "fixed rate". Новый класс кодов также называют классом фонтанных кодов (Digital Fountain Codes) [2,5]. Кодер такого кода по запросу всегда может добавить "на лету" (on-the-fly, on-line) небольшое число кодовых пакетов. При этом время формирования каждого кодового пакета постоянно. Это свойство кодера в зарубежной литературе иногда именуют термином "local encodability". Независимость генерирования кодовых символов обеспечивается применением статистического кодирования. Добавить "на лету" немного проверочных пакетов (символов) для классических кодов не всегда удаётся. Кодовые символы оказываются зависимыми друг от друга.
Центральное место в этом разделе отводится LT коду как наиболее значимому, идейно интересному и исторически первому конструктивному "хорошему" rateless коду. Для лучшего понимания сути вопроса кратко рассмотрены два важных типа кодов с фиксированной скоростью.
А. Коды с фиксированной скоростью
Из теории кодирования известно, что линейный блоковый (N,K) код может восстановить сообщение из K символов при максимальном числе стираний E среди N кодовых символов, равном M=N-K. Это положение является следствием границы Синглтона. Код, удовлетворяющий этой границе, допускает максимальное число стираний. При чётном значении M таким оптимальным кодом является код Рида–Соломона.
Код Рида–Соломона
Код Рида–Соломона представляет собой блоковый код, в котором символы состоят из k бит. Если эти символы рассматривать как пакеты сообщения, то код может быть использован для доставки сообщений в канале со стираниями. Основным свойством кода является следующее: для доставки K информационных сиволов достаточно принять любые K сиволов из N. Или иначе: для правильного приёма сообщения из K сиволов в блоке из N пакетов любые из M=N-K сиволов могут быть стёртыми.
Оптимальность кода в указанном выше смысле достигается его жёсткой алгебраической структурой. В результате существует проблема добавления «на лету» небольшого числа проверочных символов. При переходе от M=N-K проверочных символов к большему числу M`=N`-K все проверочные символы требуется пересчитывать. Для примера рассмотрим код (N, 3) в поле q=2k=8. Требуется закодировать сообщение, представленное вектором [4 6 1] из K=3 символов. Код Рида–Соломона систематический. Это значит, что при кодировании к сообщению добавляются проверочные символы. При N=5 к этому сообщению добавится вектор [1 2] из M=2 символов, а при N`=7 – вектор [3 3 4 1] из M`=4 символов. Видно, что помимо сформированных новых двух проверочных символов [4 1], два предыдущих оказались пересчитанными с [1 2] на [3 3]. Этот факт является следствием жёсткой зависимости проверочных символов друг от друга.
Алгебраическая структура кода препятствует и неограниченному увеличению числа проверочных символов в коде. Код существует лишь при N Жёсткая структура кода приводит и к значительным вычислительным затратам при кодировании и декодировании. В каждый проверочный символ кода входят все K исходных символов (пакетов) сообщения. Поэтому при кодировании требуется K(N-K) операций над символами (сложений и умножений). Существуют, однако, "быстрые" алгоритмы декодирования кодов Рида–Соломона на основе алгоритма быстрого преобразования Фурье. При этом время декодированияпропорционально ln2(N) операций над символами. Однако более важно не само число операций, а то, что они производятся в конечном поле Галуа размерности q. Эти операции требуют времени, а при табличной реализации – памяти. Итак, код Рида–Соломона обладает замечательным свойством восстанавливать сообщение. Вместе с тем, коду присущи и ограничения, связанные с жёсткой алгебраической структурой. Главным побуждающим мотивом создания кода явилась необходимость в более эффективных алгоритмах кодирования и декодирования в сравнении с соответствующими алгоритмами для кодов Рида–Соломона. В то же время, код представляет конструкцию с эффективно реализованным базовым звеном, использующим кодер/декодер Рида–Соломона как подпрограмму. Исторически код явился ступенькой к созданию «rateless» кодов. Поэтому ниже cделан лишь акцент на основные идеи базового звена кода. В оригинальной работе [2] кодер представлен графом типа графа Таннера, рассмотренного для кодов LDPC (Low Density Parity Code) в [1]. Граф имеет две группы узлов, одна группа состоит из K исходных узлов (символов), вторая – из M=N-K проверочных узлов3 . Число рёбер, входящее в i-й узел проверочного узла, называется степенью узла di, i=1, 2,…, M. В отличие от кода Рида–Соломона, для которого степень каждого узла равна K, для кода Торнадо она является небольшим числом. В матричной терминологии это означает, что код имеет низкую плотность порождающей матрицы. Поэтому рассмотренный граф логично назвать порождающим. Степень проверочного узла этого графа является не просто малым, но и значением случайной величины d с распределением плотности вероятности ρ(d). Алгоритм декодирования кода представляет собой обменный алгоритм (message passing decoding) между узлами порождающего графа кода, во многом напоминающий алгоритм для LDPC [1]. Базовой математической операцией при кодировании и декодировании является простая операция сложения по модулю два (XOR) над битами пакетов. Платой за снижение вычислительной сложности является несколько большее в сравнении с кодом Рида–Соломона число требуемых для реконструкции сообщения кодовых символов K`=K(1+ε), где ε – небольшое положительное число (к примеру, 0.05). Величину Δ=K`-K принято именовать термином «overhead».4 При декодировании сообщения по K` символам требуется N ln(1/ε) операций XOR. Код Торнадо отчасти позволил преодолеть ограничения кода Рида–Соломона. В [2] приводится пример кода с параметрами (N,K)=(3.2*104,1.6*104). Средняя степень проверочного узла кода равна 14. В целом это хороший результат с точки зрения объёма вычислительных затрат при кодировании и декодировании. Тем не менее, время декодирования по-прежнему определяется величиной N, а не K. Этот же вывод относится и к объёму памяти для реализации алгоритмов. Предыдущий материал позволяет сформулировать требования к идеальному кодовому «фонтану». Рассмотренные ниже коды и кодовые конструкции представляют аппроксимации идеального "фонтана". Перед их рассмотрением сделаем одно концептуальное замечание. Неограниченный поток символов можно рассматривать как кодовый процесс с дискретным временем i, а кодер – как источник процесса. Процесс успешно завершается, если декодер реконструировал сообщение. Поскольку алгоритм декодирования должен быть быстрым, будем говорить о требовании быстрого завершения процесса. Код является несистематическим. В каждый из кодовых символов с вероятностью 0.5 входит каждый из K исходных символов. Сложением бит по модулю 2 (операцией XOR) всех входящих исходных символов вычисляются значения k бит кодового символа. В результате кодер генерирует случайный код (random fountain), в среднем используя K/2 операций XOR для вычисления одного кодового символа. Эта величина, называемая стоимостью кодирования, оказывается сравнимой с K, и поэтому её следует считать большой. Порождающая матрица кода имеет высокую плотность единиц (рис.3). Алгоритм кодирования можно сформулировать и на порождающем графе кода (рис.4). В среднем степень каждого проверочного узла графа оказывается равной K/2. Для декодирования кода требуется использование алгоритма максимального правдоподобия (МП). Анализ показывает, что процесс завершается по K` кодовым символам с вероятностью 1-δ, где δ<2-Δ, Δ=K`-K [3,7]. К примеру, для K=104 имеем δ<10-6 при K`=K+20~=K. Это замечательный результат. Однако какой ценой он достигается на практике? Анализ показывает, что алгоритм МП требует порядка K2 операций над символами. В результате, для случайного фонтанного кода процесс завершается медленно. Код был создан М. Лаби (Michael Luby) в 1998 г. и наиболее подробно описан в [6]. Своё название он получил от «Laby transform» (преобразование Лаби). Алгоритм кодирования аналогичен алгоритму случайного фонтанного кода, однако имеет принципиально иное распределение ρ(d). Суть LT кода именно в сочетании этого «хорошего» распределения с простым и быстрым алгоритмом декодирования. В основе нахождения ρ(d) и алгоритма декодирования лежит несложная вероятностная задача. Есть сообщение (книга) из K исходных символов (страниц). Из этого множества с вероятностью 1/K производится K` случайных выборок символов (страниц). В результате формируется множество из K` кодовых символов (случайно выдернутых страниц). Вопрос: чему должно быть равно K` для того, чтобы с вероятностью 1-δ каждый из всех K исходных символов (страниц) оказался хоть один раз (All-At-Once) среди K` кодовых символов (кодовых страниц)? Ответ: K`~=K ln(K/δ) при достаточно большом K. Имея такое число кодовых символов (случайно выдернутых из книги страниц), можно реконструировать исходное сообщение (книгу) с вероятностью 1-δ. Алгоритм реконструкции предельно быстрый и использует лишь информацию о нумерации символов (страниц). Кодирование и декодирование в этой задаче тривиальное. Однако интерпретация и обобщение результата оказываются весьма плодотворными. Кодовый символ (пакет) формируется из di=1 исходных символов (страниц). Будем считать, что di – значение случайной величины d с тривиальным распределением плотности вероятности ρ(1)=1 (All-At-Once distribution). Порождающий граф кодового процесса с таким распределением приведён на рис.5. Назовём такой код фонтанным кодом «один в один». Если сумму степеней кодовых символов назвать весом, то полученный результат можно сформулировать следующим образом. Из финитной части процесса веса W~= K ln(K/δ) можно реконструировать исходное сообщение (книгу) с вероятностью 1-δ. Или: процесс завершается с вероятностью 1-δ при условии W~= K ln(K/δ). Размер K` этой финитной части совпадает с её весом. В результате, для кода «один в один» процесс может быть завершён со сколь угодно высокой вероятностью быстро. Однако значение K`, по крайней мере, в ln(K/δ) раз, больше желаемого. Алгоритм декодирования даже такого простого кода предполагает наличие априорной информации от кодера о параметрах порождающего графа кода: степени каждого кодового символа di и списке номеров исходных символов (страниц), подключённых на графе к кодовым символам. Эта информация может быть передана декодеру различными способами. К примеру, если отправитель и получатель синхронизированы и используют идентичные генераторы случайных чисел для выбора степеней di и номеров исходных символов, проблема решается автоматически. Альтернативным является метод передачи ключа кодового символа в его заголовке. В ключе содержится информация как о его степени di, так и списке номеров исходных символов, входящих в кодовый символ. Теперь обобщим изложенное на произвольное вероятностное распределение при ограничении ρ(1)>0. Оно означает, что вероятность кодового символа со степенью единица отлична от нуля. Воспользуемся снова связью процесса с вышеупомянутой вероятностной задачей и рассмотрим кодирование книги. Кодовую страницу, сформированную при di>1 с помощью операции XOR, назовём нечитаемой (шифрованной), страницу со значением di=1 – читаемой (нешифрованной). Тогда возможен следующий алгоритм декодирования. Если декодер обнаружил читаемую (расшифрованную) кодовую страницу, он исключает как её содержимое (той же операцией XOR) из всех кодовых страниц,которые её содержат, так и её номер из их списка номеров. В результате снижаются на единицу степени этих кодовых страниц, и, тем самым, растёт вероятность появления читаемой (расшифрованной) страницы. Если декодер вновь обнаружит читаемую станицу, он снова исключает …и т.п. Значит, имея лишь одну читаемую страницу, принципиально возможна реконструкция всей книги очень простым алгоритмом. Это условие является необходимым условием старта алгоритма. Изложенный алгоритм относят к классу итеративных алгоритмов с распространением доверия (РД, Belief Propagation). Пример алгоритма с РД на порождающем графе кода приведён на рис. 6, a)-f). Одна итерация алгоритма состоит из следующих шагов. xi`= xi`-sj Этой операцией удаляются копии j-го символа (страницы) из всех кодовых символов (пакетов страниц), в которых он участвовал при кодировании. На рис. 6,с) обновлены значения двух крайних кодовых символов. di`=di`-1 . На рис. 6,d)-e) приведены ещё две итерации. Результат полного декодирования представлен на рис. 6,f). Итак, порождающий граф кода должен иметь вид, подобный рис.7. условие ρ(1)>0 является необходимым условием старта алгоритма декодирования. В противном случае декодирование по изложенному алгоритму невозможно. К примеру, если ρ(K)=1, то декодер на первом шаге всегда будет заявлять об отказе от декодирования, поскольку никогда не найдёт кодового символа со степенью 1. В результате и сообщение никогда не будет декодировано. Для рассмотренного выше случайного фонтанного кода ρ(1)=1/K>0. Однако очевидно, что вероятность отказа от декодирования чрезвычайно высокая. Более того, она оказывается высокой уже на первой итерации. Каким же свойством должен обладать код с «подходящим» распределением? Процесс, как и для случая «один в один», должен завершиться с вероятностью 1-δ при условии W~=K ln(K/δ)! Очевидно, что этот вес можно «набрать» при меньшем числе принятых символов K`, чем для процесса «один в один». И платой за эту возможность является стоимость кодирования, которая в предельном случае K`~=K оказывается равной ln(K/δ). В этом и состоит философия LT кода. Осталось найти «хорошее» распределение. Итак, алгоритм с РД стартует лишь при наличии хотя бы одного кодового символа со степенью, равной 1. На каждой итерации требуется, чтобы в графе остался хоть один символ, который имеет степень 1. Поэтому идеальной для алгоритма была бы ситуация, при которой после каждой итерации декодирования в графе оставался бы лишь один кодовый символ со степенью 1. Идеальное распределение, моделирующее такую ситуацию, имеет вид: Интуитивно ясно: для того чтобы восстановить исходный символ, он должен входить в большинство кодовых символов. Это означает, что степень каждого кодового символа должна быть близка к K. С другой стороны, большая часть символов должна иметь низкую степень для снижения вероятности отказа от декодирования в алгоритме РД. Этим требованиям отвечает распределение: Компромисс между двумя распределениями разрешается путем использования следующего распределения: На рис.9 приведена экспериментальная гистограмма числа кодовых символов для реконструкции сообщения из K символов. Видно, что это значение в среднем лишь на 5-10% превышает величину K. Этот результат подтверждает следующую теоретическую формулировку: исходное сообщение будет декодировано с вероятностью 1-δ по K`=K(1+ε) символам, где ε=2S ln(S/δ)/K; [3]. Отметим, что ε~ln2(K/δ)/√K. В результате параметром распределения c можно добиться требуемого значения K`. Стоимость декодирования оказывается порядка ln(K/δ) операций XOR. Эта величина при достаточно больших K и приемлемых δ оказывается много меньше K, и поэтому код можно отнести к классу кодов с низкой плотностью порождающей матрицы, как и код Торнадо. Для декодирования сообщения требуется порядка K ln(K/δ) операций XOR. В результате, время декодирования почти линейно зависит от K, в отличие от случайного фонтанного кода. Следует обратить внимание, что приведённые теоретические результаты являются асимптотическими. Результаты на практике тем ближе к теоретическим, чем больше K. Поэтому в приведённых примерах для LT кода фигурировало «достаточно большое» значение K=104, как и для случайного фонтанного кода. Итак, для LT кода процесс завершается достаточно быстро. Высокой вероятности декодирования сообщения удаётся добиться при K`~=1.1K. Код представляет собой кодовую конструкцию с внутренним (по отношению к каналу) LT кодом. В качестве внешнего кода можно использоваться «почти» любой блоковый код (c фиксированной скоростью). Разработка и исследование кода принадлежит A. Shokrollahi [7]. На рис.10 приведён пример. Сообщение из K=16 символов сначала кодируется систематическим блоковым кодом (K,K1)=(16,20), восстанавливающим E=3 стирания (напомним, что согласно границе Синглтона максимальное число стираний для такого кода равно 4). Затем K1=20 символов кодируются LT кодом. Для реконструкции всего сообщения в целом декодеру LT кода достаточно восстановить любые K1-E =17 символов блокового кода. На рис.10 тёмными кружками выделены не восстановленные LT декодером символы. Остальные 17 символов внешнего кода декодер LT кода восстанавливает по K`=18 кодовым символам. Анализ конструкции показывает, что исходное сообщение может быть реконструировано с вероятностью 1-δ по K`=K(1+ε) символам, где ε – небольшое положительное число. Стоимость декодирования оказывается порядка ln(1/ε) операций XOR. Для декодирования сообщения требуется порядка Kln(1/ε) операций XOR. На сегодняшний день код является, возможно, лучшей аппроксимацией идеального фонтанного кода. Название кода [M. Maymounkov, 4] подчеркивает способность кодера генерировать независимые кодовые символы "на лету". Код так же, как и код Raptor, представляет собой каскадную конструкцию, однако в качестве внутреннего кода используется код с отличным от LT кода вероятностным распределением. Код разработан независимо от разработчиков LT и Raptor кодов. В целом, код имеет асимптотические характеристики, близкие к коду Raptor. Также как и код Raptor, он имеет хорошие показатели для относительно небольших размеров сообщений. Так, при K~103 декодер позволяет реконструировать сообщение с вероятностью 1-10-8 по числу принятых кодовых символов лишь на 3% больше K. По-видимому, LT код продолжает цепочку открытий в помехоустойчивом кодировании, к которым относятся коды Галлагера с низкой плотностью проверок на чётность и турбо-коды. Все эти коды имеют простые алгоритмы декодирования и позволяют на практике получать результаты, близкие к предельным возможностям помехоустойчивого кодирования. «Почти» потоковые коды конструировались и до изобретения фонтанных кодов. Основу конструирования составлял низкоскоростной блоковый или свёрточный материнский код. При необходимости к этому коду не добавляются «на лету», а удаляются (выкалываются) из него кодовые символы. Тем самым принципиально можно получить код с широкой областью скоростей. В этом подходе, однако, сложность декодирования определяется материнским низкоскоростным кодом. При этом, чем меньше скорость этого кода, тем больше сложность. Для рассмотренных "rateless" кодов такой проблемы нет. Немаловажен и рост эффективности использования кодирования с увеличением размера сообщения. Некоторое ограничение эффективности кодирования естественно наблюдается при небольших объёмах данных. Это ограничение является платой за использование статистических методов. Для многих практических приложений, однако, оно не столь существенно. В то же время, благодаря статистическому кодированию возможно решение нетривиальных сетевых задач, как, например, одновременная загрузка файла большого размера с нескольких сайтов. Отметим также, что алгоритмы кодирования и декодирования принципиально не зависят от размера пакета. Обратим внимание и на универсальность потоковых кодов. Они могут быть использованы в любом канале со стираниями, независимо от статистики стираний. Более того, потоковые коды принципиально можно использовать и для повышения достоверности доставки сообщений в каналах со сложной помеховой обстановкой, например, в радиоканалах. Для этого физический канал с помехами следует представить моделью в виде внешнего канала со стираниями и внутреннего канала с ошибками. При этом для внутреннего канала можно использовать какой-либо хороший код для борьбы с помехами, для внешнего канала – потоковый код для борьбы со стираниями. Такие каскадные кодовые конструкции сегодня реально рассматриваются. Алгоритмы, связанные с рассмотренными кодами, защищены большим числом патентов. На практике коды используются в таких программно-аппаратных изделиях для компьютерных сетей как Digital Fountain Multicast Client, DF Raptor for Streaming, DF Broadcast и т.п. Помимо компьютерных сетей фонтанные коды начинают проникать и другие пакетные сети. Недавно была распространена информация о включении кодов Raptor в стандарты мобильной связи третьего поколения. Привлекли они внимание DSL и спутниковых операторов, что выразилось в покупке лицензий на новую технологию кодирования. 1 Полный код CRC образуется из циклического кода Хэмминга (n,k)=(2m-1,2m- m-1) удалением одного информационного бита и расширением этого кода путём дополнительной проверки на чётность. В результате код остаётся циклическим (в отличие от расширенного проверкой на чётность кода Хэмминга, который принципиально не является циклическим). Как любой циклический код, CRC обнаруживает все серии ошибок длины r=n-k. Доля необнаруженных серий ошибок длины m+2 (m+3) равна 2-m(2-( m-1)). Все кодовые слова кодов CRC имеют чётный вес, поэтому код обнаруживает любое нечётное число независимых ошибок. CRC также обнаруживает 2 любые ошибки. CRC-4: m=3, (n,k)=(7,3). CRC-8: m=7, (n,k)= (127,119). CRC-16: m=15, (n, k)=(32767,32751). На практике при кодировании данных произвольной длины используются укороченные от приведённых выше полных CRC кодов. 2 Иногда каналы с неизвестной вероятностью стирания в зарубежной литературе называют free erasure channel. 3LDPC описываются проверочным графом, одна группа узлов которого состоит из N кодовых символов, вторая – из M=N-K проверочных узлов. 4 Иногда под термином «overhead» понимают и величину K`/K=(1+ε). Текст в формате PDF Телемультимедиа № 4 (32), 2005 Код Торнадо
Б. Коды без фиксированной скорости
Случайный фонтанный код
Рис.3. Матричная интерпретация фонтанного кодирования. LT код
Рис.4. Порождающий граф случайного фонтанного кода. 
Рис.5. Порождающий граф фонтанного кода с единичным весовым распределением. 
Рис.6. Пример декодирования LT кода. Однобитовые пакеты, K=3, K`=4. 
Рис.7. Порождающий граф LT кода. 
Это распределение (рис.8) носит название Ideal Soliton distribution [6]. Стоимость кодирования этим распределением минимальна и равна ln K. Использовать его в качестве ρ(d), однако, неразумно. Почему? 
Рис.8. Пример компонент μ(d) и τ(d) вероятностного распределения LT кода. Параметры кода K=104, с=0.2, δ=2•10-2 дают значения S=244, K/S=41. Распределение τ(d) имеет максимумы в точках d=1 и d=K/S 
где 
число исходных символов, хоть один раз входящих в кодовые символы степени d=K/S . Здесь c – параметр, величина которого меньше единицы. Это распределение повышает вероятность высокой степени. В то же время, с ростом S растёт и вероятность при малых степенях. В результате это распределение имеет «двугорбый» вид с максимумами в степенях d=1 и d= K/S (рис. 8).
где Z – нормирующий множитель вероятностного распределения. Это параметрическое распределение LT кода, которое носит название Robust Soliton distribution.
Рис.9. Гистограммы числа кодовых пакетов для декодирования сообщения из K пакетов. K=104, δ=const. Код Raptor
Рис.10. Порождающий граф Raptor кода. Код On-line
Заключение
Литература
