Код преобразования Луби

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

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

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

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

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

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

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

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

Как упоминалось выше, код RaptorQ, указанный в IETF RFC 6330, на практике превосходит код LT.

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

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

• Степень d , 1 ≤  d  ≤  n , следующего пакета выбирается случайным образом.
• Случайным образом выбираются ровно d блоков сообщения.
• Если Mi _— i - й блок сообщения, часть данных следующего пакета вычисляется как

${\displaystyle M_{i_{1}}\oplus M_{i_{2}}\oplus \cdots \oplus M_{i_{d}}\,}$

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

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

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

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

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

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

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

${\displaystyle {\begin{aligned}&{}\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{aligned}}}$

Вариации

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

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

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

Сам Луби ^[1] обсуждал «идеальное распределение солитонов », определяемое формулой

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

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

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

• Онлайн коды
• Коды Раптора
• Коды Торнадо

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

1. М.Луби, «LT-коды», 43-й ежегодный симпозиум IEEE по основам компьютерных наук, 2002.
2. Операция исключающее или (XOR), обозначенная ⊕, обладает очень полезным свойством: A  ⊕  A  = 0, где A — произвольная строка битов .
3. Коды фонтанов, автор DJC MacKay, впервые опубликовано в IEEE Proc.-Commun., Vol. 152, № 6, декабрь 2005 г.
4. Оптимизация распределения степеней LT-кодов с помощью метода выборки по важности, Эса Хютия, Туомас Тирронен и Йорма Виртамо (2006).

Внешние ссылки

• «Реализация кода преобразования Luby на C#»
• «Реализация фонтанных кодов для хранения данных на C/C++»
• «Введение в фонтанные коды: LT-коды на Python»