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

В информатике , коды преобразования Лубьев ( 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. Rq SDK является высокой производительностью коммерческого класс реализация SDK коды RaptorQ доступна BitRipple , компания,Майкл Луби стал соучредителем, чтобы обеспечить крупномасштабное распределение данных по проблемным сетям.

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

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

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

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

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

Как упоминалось выше, код RaptorQ, указанный в IETF RFC 6330, на практике превосходит код LT. Для примера некоторых из вариантов использования, описанных выше, см. Свойства программного пакета Mono (который основан на коде RaptorQ), предлагаемого BitRipple .

Кодировка LT [ править ]

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

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

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

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

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

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

LT-декодирование [ править ]

В процессе декодирования для извлечения закодированного сообщения используется операция « исключающее ИЛИ».

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

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

{\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] обсуждал «идеальное распределение солитонов », определяемое формулой

{\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, поэтому декодирование не удастся. Более того, некоторые из исходных блоков не будут преобразованы ни в один из пакетов передачи. Поэтому на практике модифицированное распределение, «робастное солитонное распределение", заменяется на идеальное распределение. Эффект от модификации, как правило, заключается в создании большего количества пакетов с очень малой степенью (около 1) и меньшего количества пакетов со степенью выше 1, за исключением пика пакетов с довольно большим количеством выбран, чтобы гарантировать, что все исходные блоки будут включены в какой-либо пакет. ^[4]

См. Также [ править ]

Примечания и ссылки [ править ]

^ a b М.Луби, "LT-коды", 43-й ежегодный симпозиум IEEE по основам компьютерных наук, 2002 г.
^ Операция исключающее ИЛИ (XOR), обозначенная символом ⊕, имеет очень полезное свойство: A ⊕ A = 0, где A - произвольная строка битов .
^ Fountain коды , DJC MacKay, впервые опубликованные в IEEE Proc.-Commun., Vol. 152, No. 6, декабрь 2005 г.
^ a b Оптимизация распределения степеней LT-кодов с помощью подхода выборки по важности, Эса Хюйтия, Туомас Тирронен и Йорма Виртамо (2006).

Внешние ссылки [ править ]

«Реализация кода преобразования Луби в C #»
«Введение в коды фонтанов: коды LT с Python»

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

[2] Операция исключающее ИЛИ (XOR), обозначенная символом ⊕, имеет очень полезное свойство: A ⊕ A = 0, где A - произвольная строка битов .

[MacKay-3] Fountain коды , DJC MacKay, впервые опубликованные в IEEE Proc.-Commun., Vol. 152, No. 6, декабрь 2005 г.

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

[1]