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

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

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

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

0. Начало

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

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

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

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

1.3 Контекст

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

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

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

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

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).

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

Игнорируя любые строки, выходящие за пределы изображения, существует восемь возможных шестибитных строк, соответствующих допустимым кодовым словам: (т.е. 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.

Во время кодирования кадра биты входных данных (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. Поскольку переданное сообщение должно удовлетворять кодовым ограничениям, сообщение может быть представлено путем записи полученного сообщения в верхней части графа факторов.

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

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

Этот результат может быть подтвержден путем умножения исправленного кодового слова 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 кадр (K_bch бит) должен быть обработан подсистемой FEC кодирования для формирования FECFRAME кадра (N_ldpc бит). Биты проверки на четность (BCHFEC) внешнего систематического BCH кода должны быть добавлены после BBFRAME кадра, а биты проверки на четность (LDPCFEC) внутреннего LDPC кодера должны быть добавлены после поля BCHFEC, как показано на рисунке 12.

Рисунок 12 — Формат данных перед битовым перемежением
(N_ldpc = 64 800 бит для стандартного FECFRAME кадра, N_ldpc = 16 200 бит для короткого FECFRAME кадра)

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

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

Скорость LDPC кодирования	Размер блока до BCH кодирования Kbch	Размер блока после BCH кодирования Nbch Размер блока до LDPC кодиро;вания Kldpc	Корректирующая способность BCH кода	Nbch—Kbch	Размер блока после LDPC кодирования Nldpc
1/2	32 208	32 400	12	192	64 800
3/5	38 688	38 880	12	192	64 800
2/3	43 040	43 200	10	160	64 800
3/4	48 408	48 600	12	192	64 800
4/5	51 648	51 840	12	192	64 800
5/6	53 840	54 000	10	160	64 800

Таблица 6b. Параметры кодирования (для короткого FECFRAME кадра N_ldpc = 16 200 бит).

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

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

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

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

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

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

Идентификатор скорости LDPC кодирования	Размер блока до BCH кодирования Kbch	Размер блока после BCH кодирования Nbch Размер блока до LDPC кодирования Kldpc	Корректирующая способность BCH кода	Nbch—Kbch	Эффективная скорость LDPC кодирования Kldpc/16 200	Размер блока после LDPC кодирования Nldpc
1/4 (смотрите примечание)	3 072	3 240	12	168	1/5	16 200
1/2	7 032	7 200	12	168	4/9	16 200
3/5	9 552	9 720	12	168	3/5	16 200
2/3	10 632	10 800	12	168	2/3	16 200
3/4	11 712	11 880	12	168	11/15	16 200
4/5	12 432	12 600	12	168	7/9	16 200
5/6	13 152	13 320	12	168	37/45	16 200

Таблица 7a. BCH полиномы (для стандартного FECFRAME кадра N_ldpc = 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 кадра N_ldpc = 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 кодирования (N_ldpc, K_ldpc) приведены в таблице 6.

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

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

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

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

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

Скорость кодирования	Qldpc
1/4	36
1/3	30
2/5	27
1/2	25
3/5	18
2/3	15
3/4	12
4/5	10
5/6	8

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

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

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

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

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

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

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

Модуляция	Строки Nr		Столбцы Nc
	Nldpc = 64 800	Nldpc = 16 200
16-QAM	8 100	2 025	8
64-QAM	5 400	1 350	12
256-QAM	4 050	—	16
	—	2 025	8

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

Таким образом, для 64-QAM и N_ldpc = 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.

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

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

Моду­ляция	Стол­бцы Nc	Nldpc	Параметр закручивания tc
			Стол­бец 0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
16-QAM	8	64 800	0	0	2	4	4	5	7	7	—	—	—	—	—	—	—	—
		16 200	0	0	0	1	7	20	20	21	—	—	—	—	—	—	—	—
64-QAM	12	64 800	0	0	2	2	3	4	4	5	5	7	8	9	—	—	—	—
		16 200	0	0	0	2	2	2	3	3	3	6	7	7	—	—	—	—
256-QAM	16	64 800	0	2	2	2	2	3	7	15	16	20	22	22	27	27	28	32
	8	16 200	0	0	0	1	7	20	20	21	—	—	—	—	—	—	—	—

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

Источник

Все, что вы хотели узнать об 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) — есть ничто иное, как перемножение вектора информационного сообщения длинной на некоторую порождающую матрицу :

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

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

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

где — это, так называемая, четная (parity) часть, а — единичная (identity) матрица.

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

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

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

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

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

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

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

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

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

Собственно говоря, эта матрица и определяет последние две буквы в аббревиатуре 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]

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

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

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

(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 кодов мы стремимся сделать проверочные матрицы разреженными. А если матрицы проверки не попадают под стандартную форму, значит не совсем понятно, как для них формировать порождающие матрицы.

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

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

Была такая матрица :

От нее, путем перемещений и преобразований строк по модулю 2, а также перемещений столбцов, перешли к матрице :

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где обозначает вероятность, а обозначает некоторое событие.

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

Итак, Belief propagation.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На этом этапе нужно пересчитать матрицу :

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лучше открыть в новой вкладке для полноты эффекта.

Можно запустить любой эксперимент и под свой вкус. Для этого нужно будет по инструкции (см. 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-кодов (наверное).

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

Литература

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:

где — это сложение по модулю (в нашем случае modulo 2).

Соответственно, процедура замены нулей на единицы в матрице — это сложение двух матриц:

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

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

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

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

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

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

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

Источник