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

В информатике коды преобразования Луби ( коды 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 блоков из сообщения.
  • Если M i — это i -й блок сообщения, то часть данных следующего пакета вычисляется как
М я 1 ⊕ М я 2 ⊕ ⋯ ⊕ М я г {\displaystyle M_{i_{1}}\oplus M_{i_{2}}\oplus \cdots \oplus M_{i_{d}}\,}
где { i 1 ,  i 2 , ...,  i d } — случайно выбранные индексы для d блоков, включенных в этот пакет.
  • К закодированному пакету добавляется префикс, определяющий, сколько блоков n содержится в сообщении, сколько блоков d было включено в часть данных этого пакета с помощью операции «исключающее ИЛИ», а также список индексов { i 1 ,  i 2 , ...,  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}  

( М я 1 ⊕ ⋯ ⊕ М я г ) ⊕ ( М я 1 ⊕ ⋯ ⊕ М я к − 1 ⊕ М я к + 1 ⊕ ⋯ ⊕ М я г ) = М я 1 ⊕ М я 1 ⊕ ⋯ ⊕ М я к − 1 ⊕ М я к − 1 ⊕ М я к ⊕ М я к + 1 ⊕ М я к + 1 ⊕ ⋯ ⊕ М я г ⊕ М я г = 0 ⊕ ⋯ ⊕ 0 ⊕ М я к ⊕ 0 ⊕ ⋯ ⊕ 0 = М я к {\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 \точки \oplus 0\oplus M_{i_{k}}\oplus 0\oplus \точки \oplus 0\\&=M_{i_{k}}\,\end{aligned}}}

Вариации

Возможны несколько вариаций процессов кодирования и декодирования, описанных выше. Например, вместо того, чтобы добавлять к каждому пакету список индексов реальных блоков сообщений { i 1 ,  i 2 , ...,  i d }, кодер может просто отправить короткий «ключ», который служит начальным числом для генератора псевдослучайных чисел (PRNG) или таблицы индексов, используемых для построения списка индексов. Поскольку приемник, оснащенный тем же RNG или таблицей индексов, может надежно воссоздать «случайный» список индексов из этого начального числа, процесс декодирования может быть успешно завершен. В качестве альтернативы, путем объединения простого кода LT низкой средней степени с надежным кодом исправления ошибок, можно построить код Raptor , который на практике превзойдет оптимизированный код LT. [3]

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

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

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

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

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

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

  1. ^ М. Луби, «LT Codes», 43-й ежегодный симпозиум IEEE по основам компьютерной науки, 2002.
  2. ^ Операция исключающего ИЛИ (XOR), обозначаемая символом ⊕, имеет очень полезное свойство: A  ⊕  A  = 0, где A — произвольная строка битов .
  3. ^ Фонтанные коды, DJC MacKay, впервые опубликованы в IEEE Proc.-Commun., Vol. 152, No. 6, декабрь 2005 г.
  4. ^ ab Оптимизация распределения степеней кодов LT с использованием подхода выборки по важности, Эса Хютиа, Туомас Тирронен и Йорма Виртамо (2006).
  • «Реализация кода преобразования Luby на языке C#»
  • «Реализация кодов Fountain для хранения на языке C/C++»
  • «Введение в фонтанные коды: LT-коды на Python»
Получено с "https://en.wikipedia.org/w/index.php?title=Luby_transform_code&oldid=1237714914"