Код преобразования Луби - Luby transform code

В Информатика, Коды преобразования Луби (Коды LT) являются первым классом практических коды фонтанов которые почти оптимальны коды исправления стирания. Они были изобретены Майкл Луби в 1998 г. и опубликовано в 2002 г.^[1] Как некоторые другие коды фонтанов, LT коды зависят от разреженных двудольные графы обменять накладные расходы на прием на скорость кодирования и декодирования. Отличительная особенность LT-кодов заключается в использовании особенно простого алгоритма, основанного на Эксклюзивный или операция ( ${ displaystyle oplus}$ ) для кодирования и декодирования сообщения.^[2]

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

Следующее поколение за пределами LT-кодов Коды Raptor (см., например, IETF RFC 5053 или IETF RFC 6330 ), которые имеют линейное кодирование и декодирование по времени. Коды Raptor используют два этапа кодирования для кодирования, где второй этап - LT-кодирование. Информация о наличии эффективной программной реализации кода RaptorQ указана в IETF RFC 6330 (самый продвинутый код фонтана), можно найти навеб-сайт проекта Codornices в ICSI .

Зачем использовать код LT?

Традиционная схема передачи данных по каналу стирания зависит от непрерывной двусторонней связи.

Отправитель кодирует и отправляет пакет информации.
Получатель пытается декодировать полученный пакет. Если его можно декодировать, получатель отправляет подтверждение обратно передатчику. В противном случае приемник просит передатчик снова отправить пакет.
Этот двусторонний процесс продолжается до тех пор, пока все пакеты в сообщении не будут успешно переданы.

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

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

Кодирование LT

Процесс кодирования начинается с разделения некодированного сообщения на п блоки примерно одинаковой длины. Закодированные пакеты затем производятся с помощью генератор псевдослучайных чисел.

Степень d, 1 ≤ d ≤ п, следующего пакета выбирается случайным образом.
Точно d блоки из сообщения выбираются случайным образом.
Если M_я это я-го блока сообщения, часть данных следующего пакета вычисляется как

{ Displaystyle M_ {i_ {1}} oplus M_ {i_ {2}} oplus cdots oplus M_ {i_ {d}} ,}

куда {я₁, я₂, …, я_d} - случайно выбранные индексы для d блоки, входящие в этот пакет.

К закодированному пакету добавляется префикс, определяющий, сколько блоков п в сообщении сколько блоков d были исключены в часть данных этого пакета, а список индексов {я₁, я₂, …, я_d}.
Наконец, некоторая форма кода обнаружения ошибок (возможно, такая же простая, как циклическая проверка избыточности ) применяется к пакету, и пакет передается.

Этот процесс продолжается до тех пор, пока получатель не сообщит, что сообщение получено и успешно декодировано.

LT-декодирование

В процессе декодирования используется символ "Эксклюзивный или "операция по извлечению закодированного сообщения.

Если текущий пакет не чистый или реплицирует уже обработанный пакет, текущий пакет отбрасывается.
Если текущий чисто полученный пакет имеет степень d > 1, он сначала обрабатывается для всех полностью декодированных блоков в области очереди сообщений (как более подробно описано в следующем шаге), а затем сохраняется в буферной области, если его уменьшенная степень больше 1.
Когда новый чистый пакет степени d = 1 (блок M_я) получен (или степень текущего пакета уменьшена до 1 на предыдущем шаге), он перемещается в область очереди сообщений, а затем сопоставляется со всеми пакетами степени d > 1 находится в буфере. Он вводится эксклюзивно в часть данных любого буферизованного пакета, который был закодирован с использованием M_я, степень этого совпадающего пакета уменьшается, и список индексов для этого пакета корректируется, чтобы отразить применение M_я.
Когда этот процесс открывает блок степеней d = 2 в буфере, этот блок уменьшается до степени 1 и, в свою очередь, перемещается в область очереди сообщений, а затем обрабатывается для пакетов, оставшихся в буфере.
Когда все п блоки сообщения были перемещены в область очереди сообщений, получатель сигнализирует передатчику, что сообщение было успешно декодировано.

Эта процедура декодирования работает, потому что А ${ displaystyle oplus}$ А = 0 для любой битовой строки А. После d - 1 отдельный блок был исключен в пакет степеней d, остается только исходное незакодированное содержимое несопоставленного блока. В символах мы имеем

{ displaystyle { begin {align} & {} qquad (M_ {i_ {1}} oplus dots oplus M_ {i_ {d}}) oplus (M_ {i_ {1}} oplus dots oplus M_ {i_ {k-1}} oplus M_ {i_ {k + 1}} oplus dots oplus M_ {i_ {d}}) & = M_ {i_ {1}} oplus M_ {i_ {1}} oplus dots oplus M_ {i_ {k-1}} oplus M_ {i_ {k-1}} oplus M_ {i_ {k}} oplus M_ {i_ {k + 1 }} oplus M_ {i_ {k + 1}} oplus dots oplus M_ {i_ {d}} oplus M_ {i_ {d}} & = 0 oplus dots oplus 0 oplus M_ {i_ {k}} oplus 0 oplus dots oplus 0 & = M_ {i_ {k}} , end {выравнивается}}}

Вариации

Возможны несколько вариантов описанных выше процессов кодирования и декодирования. Например, вместо того, чтобы указывать перед каждым пакетом список фактических индексов блока сообщений {я₁, я₂, …, я_d} кодировщик может просто послать короткий «ключ», который служил начальным значением для генератор псевдослучайных чисел (PRNG) или индексная таблица, используемая для построения списка индексов. Поскольку приемник, оснащенный тем же самым ГСЧ или индексной таблицей, может надежно воссоздать «случайный» список индексов из этого начального числа, процесс декодирования может быть успешно завершен. В качестве альтернативы, комбинируя простой LT-код с низкой средней степенью с надежным кодом исправления ошибок, код раптора могут быть сконструированы так, чтобы на практике превзойти оптимизированный LT-код.^[3]

Оптимизация LT-кодов

Есть только один параметр, который можно использовать для оптимизации прямого LT-кода: функция распределения степеней (описываемая как генератор псевдослучайных чисел для степени d в Кодирование LT раздел выше). На практике другие «случайные» числа (список индексов {я₁, я₂, …, я_d }) неизменно берутся из равномерного распределения на [0, п), куда п - количество блоков, на которые было разделено сообщение.^[4]

Сам Луби^[1] обсудили "идеальный распределение солитонов " определяется

{ Displaystyle { begin {align} mathrm {P} {d = 1 } & = { frac {1} {n}} [2pt] mathrm {P} {d = k } & = { frac {1} {k (k-1)}} qquad (k = 2,3, dots, n). , end {align}}}

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

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

Примечания и ссылки

^ ^а ^б М.Луби, "LT-коды", 43-й ежегодный симпозиум IEEE по основам информатики, 2002 г.
^ В Эксклюзивный или Операция (XOR), обозначаемая символом has, обладает очень полезным свойством: А ⊕ А = 0, где А это произвольная строка биты.
^ Коды фонтанов, автор: D.J.C. MacKay, впервые опубликовано в IEEE Proc.-Commun., Vol. 152, No. 6, декабрь 2005 г.
^ ^а ^б Оптимизация распределения LT-кодов по степени важности, Эса Хюйтия, Туомас Тирронен и Йорма Виртамо (2006).

внешняя ссылка

[Luby-1] а ^б М.Луби, "LT-коды", 43-й ежегодный симпозиум IEEE по основам информатики, 2002 г.

[2] В Эксклюзивный или Операция (XOR), обозначаемая символом has, обладает очень полезным свойством: А ⊕ А = 0, где А это произвольная строка биты.

[MacKay-3] Коды фонтанов, автор: D.J.C. MacKay, впервые опубликовано в IEEE Proc.-Commun., Vol. 152, No. 6, декабрь 2005 г.

[Tirronen-4] а ^б Оптимизация распределения LT-кодов по степени важности, Эса Хюйтия, Туомас Тирронен и Йорма Виртамо (2006).

[1]

[2]

[3]

[4]