ldpc кодирование для чайников

Кодирование для чайников, ч.1

Не являясь специалистом в обозначенной области я, тем не менее, прочитал много специализированной литературы для знакомства с предметом и прорываясь через тернии к звёздам набил, на начальных этапах, немало шишек. При всём изобилии информации мне не удалось найти простые статьи о кодировании как таковом, вне рамок специальной литературы (так сказать без формул и с картинками).

Статья, в первой части, является ликбезом по кодированию как таковому с примерами манипуляций с битовыми кодами, а во второй я бы хотел затронуть простейшие способы кодирования изображений.

0. Начало

Давайте рассмотрим некоторые более подробно.

1.1 Речь, мимика, жесты

1.2 Чередующиеся сигналы

В примитивном виде кодирование чередующимися сигналами используется человечеством очень давно. В предыдущем разделе мы сказали про дым и огонь. Если между наблюдателем и источником огня ставить и убирать препятствие, то наблюдателю будет казаться, что он видит чередующиеся сигналы «включено/выключено». Меняя частоту таких включений мы можем выработать последовательность кодов, которая будет однозначно трактоваться принимающей стороной.

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

1.3 Контекст

2. Кодирование текста

Текст в компьютере является частью 256 символов, для каждого отводится один байт и в качестве кода могут быть использованы значения от 0 до 255. Так как данные в ПК представлены в двоичной системе счисления, то один байт (в значении ноль) равен записи 00000000, а 255 как 11111111. Чтение такого представления числа происходит справа налево, то есть один будет записано как 00000001.

Итак, символов английского алфавита 26 для верхнего и 26 для нижнего регистра, 10 цифр. Так же есть знаки препинания и другие символы, но для экспериментов мы будем использовать только прописные буквы (верхний регистр) и пробел.

Тестовая фраза «ЕХАЛ ГРЕКА ЧЕРЕЗ РЕКУ ВИДИТ ГРЕКА В РЕЧКЕ РАК СУНУЛ ГРЕКА РУКУ В РЕКУ РАК ЗА РУКУ ГРЕКУ ЦАП».

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

2.1 Блочное кодирование

Информация в ПК уже представлена в виде блоков по 8 бит, но мы, зная контекст, попробуем представить её в виде блоков меньшего размера. Для этого нам нужно собрать информацию о представленных символах и, на будущее, сразу подсчитаем частоту использования каждого символа:

Источник

Содержание

История

Приложения

В 2008 годе LDPC бить сверточные турбокоды как прямая коррекция ошибок системы (ПИО) для МСЭ-Т G.hn стандарта. G.hn предпочел коды LDPC турбокодам из-за их меньшей сложности декодирования (особенно при работе со скоростями передачи данных, близких к 1,0 Гбит / с), а также потому, что предложенные турбокоды демонстрируют значительный минимальный уровень ошибок в желаемом диапазоне работы.

Коды LDPC также используются для 10GBASE-T Ethernet, который передает данные со скоростью 10 гигабит в секунду по кабелям витой пары. С 2009 года коды LDPC также являются частью стандарта Wi-Fi 802.11 в качестве дополнительной части 802.11n и 802.11ac в спецификации PHY с высокой пропускной способностью (HT).

Оперативное использование

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

Игнорируя любые строки, выходящие за пределы изображения, существует восемь возможных шестибитных строк, соответствующих допустимым кодовым словам: (т.е. 000000, 011001, 110010, 101011, 111100, 100101, 001110, 010111). Этот фрагмент кода LDPC представляет трехбитовое сообщение, закодированное как шесть битов. Здесь используется избыточность для увеличения шансов восстановления после ошибок канала. Это линейный код (6, 3) с n = 6 и k = 3.

Снова игнорируя строки, выходящие за пределы изображения, матрица проверки на четность, представляющая этот фрагмент графа, имеет вид

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

Шаг 2: Ряд 1 добавлен к ряду 3.

Шаг 3: строки 2 и 3 меняются местами.

Шаг 4: Ряд 1 добавляем к ряду 3.

Битовая строка «101» находится как первые 3 бита кодового слова «101011».

Пример кодировщика

На рисунке 1 показаны функциональные компоненты большинства кодеров LDPC.

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

Во время кодирования кадра биты входных данных (D) повторяются и распределяются по набору составляющих кодеров. Составляющие кодеры обычно являются накопителями, и каждый накопитель используется для генерации символа четности. Единственная копия исходных данных (S 0, K-1 ) передается с битами четности (P), чтобы составить кодовые символы. S битов от каждого составляющего кодера отбрасываются.

Бит четности может использоваться в другом составляющем коде.

В примере с использованием кода DVB-S2 со скоростью 2/3 размер кодированного блока составляет 64800 символов (N = 64800) с 43200 битами данных (K = 43200) и 21600 битами четности (M = 21600). Каждый составляющий код (контрольный узел) кодирует 16 бит данных, за исключением первого бита четности, который кодирует 8 битов данных. Первые 4680 битов данных повторяются 13 раз (используются в 13 кодах четности), а остальные биты данных используются в 3 кодах четности (нерегулярный код LDPC).

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

Код LDPC, напротив, использует параллельно множество составляющих кодов (аккумуляторов) низкой глубины, каждый из которых кодирует только небольшую часть входного кадра. Многие составляющие коды можно рассматривать как множество «сверточных кодов» с низкой глубиной (2 состояния), которые связаны посредством операций повтора и распределения. Операции повтора и распределения выполняют функцию перемежителя в турбо-коде.

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

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

Расшифровка

Как и в случае с другими кодами, декодирование с максимальной вероятностью кода LDPC в двоичном симметричном канале является NP-полной проблемой. Оптимальное декодирование NP-полного кода любого полезного размера нецелесообразно.

Декодирование кодов SPC часто упоминается как обработка «узла проверки», а перекрестная проверка переменных часто упоминается как обработка «узла переменной».

В практической реализации декодера LDPC наборы кодов SPC декодируются параллельно для увеличения пропускной способности.

Напротив, распространение убеждений по каналу двоичного стирания особенно просто, если оно состоит из итеративного удовлетворения ограничений.

Например, предположим, что действительное кодовое слово 101011 из приведенного выше примера передается по двоичному каналу стирания и принимается со стертыми первым и четвертым битами, что дает «01» 11. Поскольку переданное сообщение должно удовлетворять кодовым ограничениям, сообщение может быть представлено путем записи полученного сообщения в верхней части графа факторов.

В этом примере первый бит еще не может быть восстановлен, потому что все связанные с ним ограничения имеют более одного неизвестного бита. Чтобы продолжить декодирование сообщения, необходимо определить ограничения, связанные только с одним из стертых битов. В этом примере достаточно только второго ограничения. Рассматривая второе ограничение, четвертый бит должен быть равен нулю, поскольку только ноль в этой позиции будет удовлетворять ограничению.

Затем эта процедура повторяется. Новое значение четвертого бита теперь можно использовать вместе с первым ограничением для восстановления первого бита, как показано ниже. Это означает, что первый бит должен быть единицей, чтобы удовлетворить крайнему левому ограничению.

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

Этот результат может быть подтвержден путем умножения исправленного кодового слова r на матрицу проверки на четность H :

Поскольку результатом z ( синдромом ) этой операции является нулевой вектор размером 3 × 1, результирующее кодовое слово r успешно проверяется.

После завершения декодирования исходные биты «101» сообщения могут быть извлечены путем просмотра первых 3 бита кодового слова.

Хотя этот пример стирания является иллюстративным, он не показывает использование декодирования с мягким решением или передачи сообщений с мягким решением, которые используются практически во всех коммерческих декодерах LDPC.

Обновление информации об узле

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

Построение кода

Построение конкретного кода LDPC после этой оптимизации делится на два основных типа методов:

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

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

Коды LDPC против турбокодов

Источник

EN 302 755. 6.1 FEC кодирование

Данная подсистема должна осуществлять внешнее кодирование (BCH), внутреннее кодирование (LDPC) и битовое перемежение. Входной поток должен состоять из BBFRAME кадров, а выходной — из FECFRAME кадров.

Каждый BBFRAME кадр (Kbch бит) должен быть обработан подсистемой FEC кодирования для формирования FECFRAME кадра (Nldpc бит). Биты проверки на четность (BCHFEC) внешнего систематического BCH кода должны быть добавлены после BBFRAME кадра, а биты проверки на четность (LDPCFEC) внутреннего LDPC кодера должны быть добавлены после поля BCHFEC, как показано на рисунке 12.

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников Рисунок 12 — Формат данных перед битовым перемежением
(Nldpc = 64 800 бит для стандартного FECFRAME кадра, Nldpc = 16 200 бит для короткого FECFRAME кадра)

В таблице 6(a) приведены параметры кодирования для стандартного FECFRAME кадра (Nldpc = 64 800 бит), а в таблице 6(b) — для короткого FECFRAME кадра (Nldpc = 16 200 бит).

Таблица 6a. Параметры кодирования (для стандартного FECFRAME кадра Nldpc = 64 800 бит).

Скорость LDPC кодированияРазмер блока до BCH кодирования
Kbch
Размер блока после BCH кодирования
Nbch
Размер блока до LDPC кодиро;вания
Kldpc
Корректирующая способность BCH кодаNbchKbchРазмер блока после LDPC кодирования
Nldpc
1/232 20832 4001219264 800
3/538 68838 8801219264 800
2/343 04043 2001016064 800
3/448 40848 6001219264 800
4/551 64851 8401219264 800
5/653 84054 0001016064 800
Таблица 6b. Параметры кодирования (для короткого FECFRAME кадра Nldpc = 16 200 бит).

Данная скорость кодирования используется только для защиты сигнализации L1-pre, но не для защиты данных.

Для Nldpc = 64 800, а также для Nldpc = 16 200 скорость LDPC кодирования задается отношением Kldpc/Nldpc. В таблице 6a скорости LDPC кодирования для Nldpc = 64 800 заданы значениями столбца «Скорость LDPC кодирования». В таблице 6b скорости LDPC кодирования для Nldpc = 16 200 заданы значениями столбца «Эффективная скорость LDPC кодирования», т.е. для Nldpc = 16 200 «идентификатор скорости LDPC кодирования» не эквивалентен скорости LDPC кодирования.

Для использования совместно с T2-Lite задан немного другой набор скоростей кодирования — смотрите приложение I.

6.1.1 Внешнее кодирование (BCH)

Исправляющее BCH кодирование (Nbch, Kbch) должно быть применено к каждому BBFRAME кадру для формирования пакета, защищенного от ошибок. Параметры BCH кодирования для Nbch = 64 800 приведены в таблице 6a, а для Nbch = 16 200 — в таблице 6b.

Порождающий полином BCH кодера для исправления t ошибок получается перемножением первых t полиномов в таблице 7a для Nbch = 64 800 или в таблице 7b для Nbch = 16 200.

Идентификатор скорости LDPC кодированияРазмер блока до BCH кодирования
Kbch
Размер блока после BCH кодирования
Nbch
Размер блока до LDPC кодирования
Kldpc
Корректирующая способность BCH кодаNbchKbchЭффективная скорость LDPC кодирования
Kldpc/16 200
Размер блока после LDPC кодирования
Nldpc
1/4
(смотрите примечание)
3 0723 240121681/516 200
1/27 0327 200121684/916 200
3/59 5529 720121683/516 200
2/310 63210 800121682/316 200
3/411 71211 8801216811/1516 200
4/512 43212 600121687/916 200
5/613 15213 3201216837/4516 200
Таблица 7a. BCH полиномы (для стандартного FECFRAME кадра Nldpc = 64 800 бит).

g1(x)1+x 2 +x 3 +x 5 +x 16
g2(x)1+x+x 4 +x 5 +x 6 +x 8 +x 16
g3(x)1+x 2 +x 3 +x 4 +x 5 +x 7 +x 8 +x 9 +x 10 +x 11 +x 16
g4(x)1+x 2 +x 4 +x 6 +x 9 +x 11 +x 12 +x 14 +x 16
g5(x)1+x+x 2 +x 3 +x 5 +x 8 +x 9 +x 10 +x 11 +x 12 +x 16
g6(x)1+x 2 +x 4 +x 5 +x 7 +x 8 +x 9 +x 10 +x 12 +x 13 +x 14 +x 15 +x 16
g7(x)1+x 2 +x 5 +x 6 +x 8 +x 9 +x 10 +x 11 +x 13 +x 15 +x 16
g8(x)1+x+x 2 +x 5 +x 6 +x 8 +x 9 +x 12 +x 13 +x 14 +x 16
g9(x)1+x 5 +x 7 +x 9 +x 10 +x 11 +x 16
g10(x)1+x+x 2 +x 5 +x 7 +x 8 +x 10 +x 12 +x 13 +x 14 +x 16
g11(x)1+x 2 +x 3 +x 5 +x 9 +x 11 +x 12 +x 13 +x 16
g12(x)1+x+x 5 +x 6 +x 7 +x 9 +x 11 +x 12 +x 16
Таблица 7b. BCH полиномы (для короткого FECFRAME кадра Nldpc = 16 200 бит).

g1(x)1+x+x 3 +x 5 +x 14
g2(x)1+x 6 +x 8 +x 11 +x 14
g3(x)1+x+x 2 +x 6 +x 9 +x 10 +x 14
g4(x)1+x 4 +x 7 +x 8 +x 10 +x 12 +x 14
g5(x)1+x 2 +x 4 +x 6 +x 8 +x 9 +x 11 +x 13 +x 14
g6(x)1+x 3 +x 7 +x 8 +x 9 +x 13 +x 14
g7(x)1+x 2 +x 5 +x 6 +x 7 +x 10 +x 11 +x 13 +x 14
g8(x)1+x 5 +x 8 +x 9 +x 10 +x 11 +x 14
g9(x)1+x+x 2 +x 3 +x 9 +x 10 +x 14
g10(x)1+x 3 +x 6 +x 9 +x 11 +x 12 +x 14
g11(x)1+x 4 +x 11 +x 12 +x 14
g12(x)1+x+x 2 +x 3 +x 5 +x 6 +x 7 +x 8 +x 10 +x 13 +x 14

6.1.2 Внутреннее кодирование (LDPC)

Параметры LDPC кодирования (Nldpc, Kldpc) приведены в таблице 6.

6.1.2.1 Внутреннее кодирование для стандартного FECFRAME кадра

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

6.1.2.2 Внутреннее кодирование для короткого FECFRAME кадра

Kldpc битов, кодированных кодом BCH, для формирования Nldpc битов должны быть подвергнуты систематическому кодированию, описанному в разделе 6.1.2.1 с заменой таблицы 8a на таблицу 8b, а таблиц приложения A на таблицы приложения B.

Таблица 8b. Значения Qldpc для коротких кадров.

Скорость кодированияQldpc
1/436
1/330
2/527
1/225
3/518
2/315
3/412
4/510
5/68

6.1.3 Битовый перемежитель (для 16-QAM, 64-QAM и 256-QAM)

Выходные данные Λ LDPC кодера должны быть подвергнуты битовому перемежению, которое состоит из перемежения битов четности с последующей процедурой перемежения с закручиванием столбцов. Выходные данные перемежителя битов четности обозначаются U, а выходные данные перемежителя с закручиванием столбцов — V.

В перемежителе битов четности перемежение битов четности происходит согласно формулам:

где Qldpc указана в таблицах 8a и 8b.

Для T2-Lite, при модуляции QPSK только со скоростями кодирования 1/3 и 2/5 применяется только перемежение битов четности (смотрите приложение I).

Конфигурация перемежения с закручиванием столбцов для каждого формата модуляции указана в таблице 9.

Таблица 9. Структура битового перемежителя.

МодуляцияСтроки NrСтолбцы Nc
Nldpc = 64 800Nldpc = 16 200
16-QAM8 1002 0258
64-QAM5 4001 35012
256-QAM4 05016
2 0258

В блоке перемежения с закручиванием столбцов биты данных ui из перемежителя битов четности поочередно постолбцово записываются в перемежитель с закручиванием столбцов и поочередно построчно считываются из него (MSB заголовка BBHEADER считывается первым) как показано на рисунке 13, где начальная позиция записи в каждом столбце сдвинута на tc в соответствии с таблицей 10. Данный перемежитель описывается следующим:

Таким образом, для 64-QAM и Nldpc = 64 800 порядок выходных битов перемежителя с закручиванием столбцов будет выглядеть следующим образом:

Более полный список индексов на правой стороне, демонстрирующий все 12 столбцов: 0, 5 400, 16 198, 21 598, 26 997, 32 396, 37 796, 43 195, 48 595, 53 993, 59 392, 64 791, …… 5 399, 10 799, 16 197, 21 597, 26 996, 32 395, 37 795, 43 194, 48 594, 53 992, 59 391, 64 790.

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников Рисунок 13 — Схема битового перемежения для стандартной длины FECFRAME кадра и 16-QAM

Таблица 10. Параметр закручивания столбцов tc.

Моду­ляцияСтол­бцы NcNldpcПараметр закручивания tc
Стол­бец 0123456789101112131415
16-QAM864 80000244577
16 20000017202021
64-QAM1264 800002234455789
16 200000222333677
256-QAM1664 8000222237151620222227272832
816 20000017202021

Перевод раздела 6.1 «FEC encoding» стандарта ETSI EN 302 755 версии 1.3.1.

Источник

Все, что вы хотели узнать об LDPC кодах, но стеснялись спросить (наверное)

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

Предисловие

С кодами малой плотности проверок на чётность, которые дальше мы будем именовать коротко LDPC (Low-density parity-check codes), мне удалось познакомиться более или менее близко, работая над семестровым научным проектом в ТУ Ильменау (магистерская программа CSP). Моему научному руководителю направление было интересно в рамках педагогической деятельности (нужно было пополнить базу примеров, а также посмотреть в сторону недвоичных LDPC), а мне из-за того, что эти коды были плюс-минус на слуху на нашей кафедре. Не все удалось рассмотреть в том году, и поэтому исследование плавно перетекло в мое хобби… Так я набрал некоторое количество материала, которым сегодня и хочу поделиться!

Кому может быть интересна данная статья:

В общем, присоединяйтесь!

Внимание:
Предполагается, что читатель знаком с основами помехоустойчивого кодирования. Если тема совсем нова, то от себя в качестве ликбеза могу предложить данный материал: Channel codes basics (CommPy).

Содержание

Краткая историческая справка

LDPC коды — идея довольно старая, впервые они были описаны Робертом Галлагером ещё в 1963 г. в его работе на степень PhD [1]. Однако, из-за своей неоправданной сложности (по тем временам) они не находили применения в технике относительно долгое время.

И только в 1990-х годах эти коды были, так сказать, заново открыты М. Дэви и Д. Маккеем, которые предложили инновационные на тот момент способы построения LDPC кодов с уменьшенной сложностью [2].

Сейчас LDPC коды это:

Кроме того, все больше LDPC коды проникают и в спутниковую связь. В свое время, я делал небольшой обзор по малым спутникам CubeSat (посмотреть можно по ссылке) — там тенденция однозначная и обусловлена внедрением стандартов DVB-S2/S2X.

И я думаю, это прекрасная мотивация узнать о данных кодах немного больше.

Азы блочного кодирования

LDPC коды — это линейные блочные коды, а значит проверочные биты в данной схеме кодирования добавляются в конец информационного сообщения — блоком.

Соответсвенно, процедура кодирования (encoding) — есть ничто иное, как перемножение вектора информационного сообщения длинной ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайниковна некоторую порождающую матрицу ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

где символ ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников— это умножение по модулю (см. modulo). Для двоичных кодов это modulo 2, для недвоичных modulo q, исходя из полей Галуа ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников.

Соответственно, и кодовая скорость тоже задается через порождающую матрицу:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

Порождающая матрица состоит из двух конкатенированных (соединенных) частей:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

где ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников— это, так называемая, четная (parity) часть, а ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников— единичная (identity) матрица.

Дело в том, что при умножении и сложении по модулю нужно соблюдать правила сопоставления отрицательных и положительных чисел:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

На двоичном случае все это незаметно, и поэтому минус иногда пропускают.

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

Обратите внимание, identity-часть нужна для того, чтобы оставлять код систематическим: информационное сообщение остается неизменным, а проверочные биты добавляются в конец блоком. При такой схеме, правильно восстановив кодовое слово, можно восстановить и изначальное сообщение, просто убрав проверочные биты. Удобно, не правда ли?

Порождающая матрица напрямую связана с другой важнейшей матрицей, использующейся во время процедуры декодирования: с матрицей проверки на четность (parity-check matrix).

Матрица проверки на четность имеет ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайниковстрок и ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайниковстолбцов, где ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайниковсоответствует требуемой длине кодового слова, а ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников, повторим, соответствует длине сообщения:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

Ее основную идею очень удобно объяснять с помощью графа Таннера:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

То есть существует два вида узлов: так называемые, узлы переменных (variable nodes), количество которых соответствуют числу столбцов ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников, и узлы проверки (check nodes), соответствующие числу строк (ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников). Узлы связаны между собой, и связь определяется положением единиц в матрице ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников. Картинка справа — это моя собственная мнемоничка моего же производства. Как мне кажется, это самый простой способ уловить суть структуры: если элемент матрицы равен 1, значит связь между узлами есть, если равен 0 — связи нет.

Для того, чтобы считать процедуру декодирования успешной, нужно, чтобы на всех проверочных узлах сформировались определенные значения — как правило, нули (см. декодирование на основе синдромов):

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

Собственно говоря, эта матрица и определяет последние две буквы в аббревиатуре LDPC (Parity-Check).

Азы LDPC кодов

Но всё выше описанное — это общие моменты для большинства блочных кодов. Чем же тогда LDPC отличаются от тех же кодов Хэмминга?

В общем-то, тем, что и определяет их как low-density: их матрицы проверки на четность должны быть разряженными (sparce), то есть нулей в них должно быть значительно больше, чем чего-либо другого:

«Low density parity check codes are codes specified by a parity check matrix containing mostly zeros and only small number of ones.» [1]

Например, у того же Галлагера данная матрица была такой:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

(3,4)-регулярная матрица проверки на четность длинною 12. Пояснение: кодовое слово, которое будет закодировано с помощью такого кода, будет иметь длину 12 бит; в каждом столбце 3 единицы, а в каждой строке 4, отсюда обозначение (3,4); количество единиц в строках и столбцах — это константы (в нашем случае 3 и 4), а значит код — регулярный.

У Маккея и Нила матрица проверки на четность была такой:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

(3,4)-регулярная матрица проверки на четность длинною 12.

В стандарте DVB-S2 приняты уже нерегулярные (irregular) матрицы проверки на четность. См.:

Eroz M., Sun F. W., Lee L. N. DVB‐S2 low density parity check codes with near Shannon limit performance //International Journal of Satellite Communications and Networking. – 2004. – Т. 22. – №. 3. – С. 269-279.

Связано это с лучшей помехоустойчивостью нерегулярных схем.

Однако, ничего не замечаете? Правильно: эти матрицы не попадают под стандартную форму из формулы (3), ведь для LDPC кодов мы стремимся сделать проверочные матрицы разреженными. А если матрицы проверки не попадают под стандартную форму, значит не совсем понятно, как для них формировать порождающие матрицы.

Ответ, конечно, есть (и не один). Допустим, такой: изначальную матрицу ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайниковприводят к стандартной форме через метод Гаусса (Gaussian elimination), из стандартной формы получают порождающую матрицу, а ее используют для кодирования.

Приведем пример из данного учебного материала:

Была такая матрица ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников:

От нее, путем перемещений и преобразований строк по модулю 2, а также перемещений столбцов, перешли к матрице ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

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

Формируем порождающую матрицу:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

Создаем кодовое слово:

И проверяем синдром (то есть закодировали мы слово матрицей, произведенной от ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников, а в процессе декодирования будем использовать разреженную матрицу ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников):

Магия линейной алгебры сработала!

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

Декодирование LDPC кодов

По LDPC кодам есть неплохой подбор материалов на Medium:

Однако, лично мне объяснение одного из центральных и самых, наверное, популярных алгоритмов декодирования — алгоритма Belief propagation (aka SPASum-product algorithm) показалось, мягко говоря, слишком формальным (там просто прикреплена научная статья). Душа просит картинок и примеров!

За основу возьмем уже знакомый нам учебный материал:

Итак, во-первых, предположим, что у нас есть некая система связи:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

Система связи состоит из:

Передатчик состоит из :

Приемник состоит из:

Договоримся, что под цифровыми модемами будем понимать в первую очередь самые популярные их разновидности: PSK и QAM.

Чем интересны для нас данные типы модуляции? Во-первых, тем, что именно они входят в стандарты современных беспроводных систем (LTE, Wi-Fi, DVB и т.д. ).

А, во-вторых, тем, что они умеют представлять зашумленные значения, полученные из канала связи, в форме, так называемых, мягких значений демодуляции (soft decisions). Или, если выражаться более наукообразно, в форме логарифмированных коэффициентов правдоподобия (LLRlog likelihood ratios):

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

где ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайниковобозначает вероятность, а ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайниковобозначает некоторое событие.

Несложно догадаться, что схема, состоящая только из источника сообщений и модема, весьма чувствительна к сильным шумам, а значит и к ошибкам демодуляции. Благо, что мы включили в нашу схему помехоустойчивый (канальный) кодек. Декодер нам эту ошибку как раз и исправит. А точнее тот алгоритм, который в этот самый декодер зашит.

Итак, Belief propagation.

Потому что алгоритм работает с вероятностями. А точнее, с теми натуральными логарифмами от отношений вероятностей, которые мы указали в формуле (5).

Потому что эти вероятности будут итеративно «пересылаться» от узлов переменных к узлам проверки (сообщение V2CVariable-to-Check) и наоборот (сообщение C2VCheck-to-Variable).

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

На этапе инициализации алгоритма LLR соответствуют априорным вероятностям. SPA является одним из алгоритмов максимальной апостериорной вероятности (MAP — maximum a posteriori probability), а значит он стремится максимизировать апостериорную вероятность, полученную после итеративной пересылки между узлами проверок и переменных.

Предлагаю рассмотреть пошагово.

Предупреждение:
Ниже будет представлено некоторое количество математических формул, и иногда они будут довольно непростыми для визуального восприятия. Поэтому если вы не настроены в данный момент на штудирование, предлагаю перейти сразу к пункту «Пример декодирования через SPA на Python (numpy)». Вернетесь к теории, когда будет время и настроение или когда захочется посмотреть, что лежит в основе скриптов (наверное).

1. Инициализация

Итак, для начала рассмотрим априорные вероятности.

Начальной точкой для нашего алгоритма является матрица значений LLR, повторяющая структуру матрицы ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников. Подберем аналитическое описание:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

где ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайниковявляется массивом единиц, а ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайниковобозначает произведение Адамара (поэлементное умножение). На практике без единичной матрицы можно будет обойтись: заменим скобку на итерационное умножением Адамара вектора LLR со столбцами матрицы контроля четности (нужен будет дополнительный цикл). Если матрицы будут достаточно большими, такой подход может быть более эффективным с точки зрения памяти.

2. Сообщение V2C

Затем следует, так называемый, горизонтальный шаг: алгоритм требует обработки сообщения (V2C) в области вероятности. Для перехода от LLR к вероятностям воспользуемся отношением между гиперболическим тангенсом и натуральным логарифмом [4, с.32 ]:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

Собственно говоря, процедура передачи V2C сообщения — это перемножение ненулевых вероятностей в каждой строке:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

где j — это номер определенной строки, i — это номер определенного столбца, ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников— это множество ненулевых значений в j-ой строке, а выражение ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайниковозначает, что мы исключаем i-ый узел переменных (variable node) из рассмотрения.

То есть на данном этапе нам нужно:

Пункт с исключением узла из рассмотрения можно провести двумя способами: 1) выяснять нужное подмножество до перемножения вероятностей или удалять значение из результата после подсчетов. Я, простоты ради, буду пользоваться вторым методом.

Я думаю, кто-то из вас, возможно, слышал названия и других алгоритмов декодирования LDPC кодов. Например, Min-sum [5], Log-SPA [6] или еще какие-нибудь [7]. Такие алгоритмы еще иногда называются субоптимальными. В чем их отличие? Собственно, в данном пункте: данные алгоритмы стремятся снизить сложность декодирования и для этого используют иные формулы для вычисления горизонтального шага. Как правило, здесь начинается подсчет рисков: каким количеством помехоустойчивости мы готовы пожертвовать ради повышения скорости декодирования.

3. Проверка критерия остановки декодирования

Итак, мы подходим к концу первой итерации, а значит пора обновить наши априорные вероятности — сделать их апостериорными:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

где ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников— это множество элементов, отвечающих ненулевым элементам матрицы проверки на четность в ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников-ом столбце.

Наложим их на биты через обратный NRZ:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

И вычислим синдром по формуле (4). Если вектор нулевой — останавливаем декодирование. Если нет, то переходим к следующему шагу.

4. Сообщение C2V

На этом этапе нужно пересчитать матрицу ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников
ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

И далее перейти к вычислению матрицы ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников. И так до тех пор, пока не выполнится пункт 3 (или не кончится количество доступных итераций).

Пример декодирования через SPA на Python (numpy)

А теперь давайте перейдем к вещам более интересным — к примерам и скриптам!

Возьмем все тот же пример из [4, с.33 ]:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

Начинаем декодировать (должна понадобиться одна итерация).

Попробуем другой пример [4, с.36 ]:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

Исправить нужно первый и последний биты.

Готовые решения для моделирования

Ну, что же, теперь мы знаем азы блочного кодирования, в целом, и LDPC кодов, в частности, и даже попробовали сделать что-то, так сказать, своими руками. Можно считать, что стадия перехода от обезьяны к человеку пройдена — теорию усвоили (или хотя бы запасли на будущее).

Давайте использовать готовые решения.

Наверное, первое, что придет вам на ум, — это Communication Toolbox от MathWorks (MatLab). Решение, пожалуй, действительно хорошее, но мне оно не нравится по нескольким причинам:

Поэтому я отправился в путешествие по проектам на GitHub и нашел весьма интересный инструментарий: проект aff3ct, написанный на C++.

Прочтем, как проект позиционируют его разработчики:

Работает ПО не только для LDPC кодов, но и для других кодеков (например, можно рассмотреть Turbo-коды и полярные коды).

У проекта есть хорошая документация в формате PDF, в формате WEB-страниц, а также онлайн-версия с визуализацией уже полученных результатов (BER/FER Comparator).

Выберем что-нибудь для примера:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников
Лучше открыть в новой вкладке для полноты эффекта.

Можно запустить любой эксперимент и под свой вкус. Для этого нужно будет по инструкции (см. Instalation) установить ПО и запустить его из командной строки с нужными параметрами.

Устанавливать нужно путем сборки из исходников. Поэтому не забывайте про суперпользователей и места нахождения make-файлов.

Например, я запустил на досуге такую модель к командной строке Ubuntu 18.04:

В итоге сформировалась такая таблица:

Даже такое аскетичное представление данных — как мне кажется, это уже классная возможность.

Можно, конечно, пойти дальше написать какие-нибудь обертки для отрисовки графиков.

У создателей проекта есть и собственные решения по визуализации. Например, PyBER. Суть «тулзы» заключается в том, что с помощью GUI вы можете выбирать сформированные aff3ct txt-файлы, PyBER вам их распарсит и отрисует (полученное можно даже экспортировать, вроде). Лично мне не понравилось представление: графики представлены через plot, а не через более логичный semilogy. Поэтому оставляю опыт использования PyBER на ваше усмотрение.

Допустим, результаты моделирования можно сохранить в txt-файл, а значения отношений битовых ошибок (BER — bit error ratio) можно вытащить уже из него c помощью простой манипуляции с awk:

Все это передать, допустим, в Python и нарисовать графики под свой вкус.

Для кодовых скоростей 1/2 и 3/4 (AWGN канал) у меня получились такая картинка:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

Без изысков, но в качестве первого шага неплохо, как мне кажется.

Послесловие

Не спорю, сколько я ни пытался объять необъятное, прошлись мы все же только по вершкам. Однако, я все же надеюсь, что данная статья хоть сколько-то снизит порог вхождения человеку, желающему погрузиться в тему LDPC-кодов (наверное).

Конструктивная критика только приветствуется. И спасибо за ваше внимание!

Литература

R.G. Gallager Low-Density Parity-Check Codes, IRE Transactions on Information Theory, 1962

D.J.C. MacKay Good Error-Correcting Codes Based on Very Sparse Matrices, IEEE Transactions on Information Theory, VOL.45, NO 2., March 1999

«3GPP RAN1 meeting #87 final report». 3GPP. Retrieved 31 August 2017.

Johnson, S. J. (2006). Introducing low-density parity-check codes. University of Newcastle, Australia, V1

Declercq D., Fossorier M. Decoding algorithms for nonbinary LDPC codes over GF(q) //IEEE transactions on communications. – 2007. – Т. 55. – №. 4. – С. 633-643.

Wymeersch H., Steendam H., Moeneclaey M. Log-domain decoding of LDPC codes over GF (q) //2004 IEEE International Conference on Communications (IEEE Cat. No. 04CH37577). – IEEE, 2004. – Т. 2. – С. 772-776.

Chen J. et al. Reduced-complexity decoding of LDPC codes //IEEE transactions on communications. – 2005. – Т. 53. – №. 8. – С. 1288-1299.

Приложения

Хотите немного линейной алгебры?

Давайте порассуждаем о том, как можно найти подмножества ненулевых вероятностей?

Для второго способа нужна будет, правда, заранее подготовленная матрица, которая будет повторять структуру матрицы H с точностью до наоборот: вместо единиц в ней будут нули, а вместо нулей единицы. Назовем ее «зеркалом» матрицы H:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

где ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников— это сложение по модулю (в нашем случае modulo 2).

Соответственно, процедура замены нулей на единицы в матрице ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников— это сложение двух матриц:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

После перемножения нужно будет вернуть структуру к исходному виду:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

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

Вопрос о сложности и простоте декодирования, может быть, не так хорошо просматривается на двоичных кодах, однако на кодах недвоичных встает, так сказать, во весь рост. Пример для GF(4).

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

Во-первых, вместо вектора LLR, нам придется работать с матрицей LLR (нужно ведь проверять вероятность уже не только двух событий):

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

Соответственно, пересылаемые сообщения — это уже тензоры, которые придется разбивать на слои и обрабатывать в цикле:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

И уже потом выбирать наиболее вероятное значение:

ldpc кодирование для чайников. Смотреть фото ldpc кодирование для чайников. Смотреть картинку ldpc кодирование для чайников. Картинка про ldpc кодирование для чайников. Фото ldpc кодирование для чайников

Сложность будет расти пропорционально увеличению q в выражении GF(q). Волей-неволей задумаешься о более быстрых алгоритмах…

Источник

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *