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

Структура цифровой системы передачи данных

Предел Шеннона (теорема Шеннона — Хартли)
К.Шеннон «РАБОТЫ ПО ТЕОРИИ ИНФОРМАЦИИ И КИБЕРНЕТИКЕ»,
ИЗДАТЕЛЬСТВО ИНОСТРАННОЙ ЛИТЕРАТУРЫ, Москва 1963,
Статья «Математическая теория связи»

Предел Шеннона

Классификация кодов, исправляющих ошибки (ЕСС)

Классификация кодов, исправляющих ошибки (ЕСС)
Наиболее многочисленный класс разделимых кодов составляют линейные коды. Основная их особенность состоит в том, что избыточные символы образуются как линейные комбинации информационных символов.
В свою очередь, линейные коды могут быть разделены на два подкласса: систематические и несистематические. Все двоичные систематические коды являются групповыми. Это означает, что все кодовые комбинации, относящиеся к группе, обладают тем свойством, что сумма по модулю два любой пары кодов снова дает кодовую комбинацию, принадлежащую этой группе. Линейные коды, которые не могут быть отнесены к подклассу систематических, называются несистематическими. Нелинейные коды свойствами групповых кодов не обладают.
Наиболее известными представителями систематических кодов являются циклические коды и коды Хемминга.

Расстояние Хэмминга
Расстояние Хэмминга:
g – количество ошибок,
которые можно исправить

Код Хемминга

Код Хемминга (15, 11). Кодирование.

Код Хемминга (15, 11). Декодирование.

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

Идея кодирования.
Код повторения.

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

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

Цифровая система связи

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

О помехоустойчивом кодировании
Корректирующие коды:
k (информационных символов) -> n (n > k)
n-k - проверочные (избыточные символы)
Избыточность, корректирующая способность, относительная скорость кода R = k/n
Энергетический выигрыш кода – сравнение отношения энергии, приходящейся на один бит, к спектральной плотности мощности шума Eб/N0 d в системах с кодированием и без

О помехоустойчивом кодировании

О помехоустойчивом кодировании

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

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

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

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

Неблоковое кодирование

Неблоковое кодирование

Неблоковое кодирование

Классификация кодов, исправляющих ошибки (ЕСС)
В соответствии с этой классификацией корректирующие коды делятся на две группы: блочные и непрерывные. Блочные коды характеризуются тем, что последовательность передаваемых символов перед кодированием разделяется на блоки. Операции кодирования и декодирования в каждом блоке производятся независимо. Это означает, что кодер для блочного кода является устройством без памяти, отображающим последовательности из k входных символов в последовательности из n выходных символов. Термин «без памяти» указывает на то, что каждый выходной блок кодера из n символов зависит только от соответствующего входного блока из k символов и не зависит от других блоков. Основными параметрами блочного кода являются размерность кода n, длина информационной части k, скорость кода r = k/n и минимальное кодовое расстояние dmin. Если все комбинации имеют одинаковую длину, блочный код называется равномерным, в противном случае код является неравномерным.

Классификация кодов, исправляющих ошибки (ЕСС)
Отличительной особенностью непрерывных кодов является то, что обработка поступающих символов производится непрерывно, без разделения на блоки. В таких кодах избыточные символы размещается в определенном порядке между информационными символами.
Кодер для непрерывного кода является устройством с памятью, в котором из группы k входных символов формируются группы из n выходных символов. Каждая группа выходных символов непрерывного кодера зависит от текущей входной группы символов и от К - 1 предыдущих входных наборов. Параметр К называется конструктивной длиной непрерывного (сверточного) кода, а величина K·n – длиной кодового ограничения.
Корректирующие коды делятся на разделимые и неразделимые. В разделимых кодах можно выделить информационные и проверочные символы, которые занимают одни и те же позиции. В неразделимых кодах деление на информационные и проверочные символы отсутствует.

Корректирующие коды, используемые в системах ЦТВ
Блоковые
Рида-Соломона
БЧХ
LDPC
Сверточные
(кодовое ограничение К – количество учитываемых при кодировании предшествующих символов)
Каскадные
Турбокоды

Сверочные коды

Сверточный кодер со скоростью R = 1/2 на основе образующих полиномов g1(x) = x2 + x + 1, g2(x) = x2 + 1. Можно записать как (111)2 и (101)2 или (7, 5)8.
Граф, описывающий состояние кодера:

Сверточный кодер как цифровой фильтр:
Диаграмма
состояний:

Граф, описывающий
состояние кодера:
входная информационная
последовательность
{bi}=10100100
отображается
в кодовое слово
{ui1,ui2}=11 10 00 10 11 11 10 11
Решетчатая диаграмма кодера:

Декодирование сверточных кодов
Алгоритм Витерби
На i–м шаге декодирования, в течение которого принимается i–я n–символьная кодовая группа наблюдения выполняются следующие операции:
Определяются хэмминговы расстояния между принятой n–символьной кодовой группой и каждой из ветвей решетчатой диаграммы. Поскольку из каждого из 2M-1 узлов выходят две ветви, всего вычисляется 2M расстояний.
Рассматриваются две ветви, идущие из разных предшествующих состояний к каждому из 2M-1 узлов:
Отвечающие указанным ветвям расстояния Хэмминга прибавляются к накопленным до i–го шага расстояниям Хэмминга двух соответствующих путей для получения новых значений расстояний. Указанное накапливаемое расстояние пути называется метрикой.
Сравниваются метрики двух соревнующихся путей, идущих в одно и то же состояние. Путь, находящийся на большем расстоянии от наблюдения, чем другой, отбрасывается и больше не учитывается в процедуре декодирования. Оставшийся путь называется выжившим путем.
Для всех 2M-1 выживших путей запоминаются значения их метрик и декодер готов к переходу на (i+1)–й шаг процедуры.

Динамика декодирования сверточного кода по алгоритму Витерби:
Y = 01 00 11 00 00 00 00 (принятый)
B = 1 0 0 0 0 0 0 (декодировано)
U = 11 10 11 00 00 00 00 (передано)

Динамика декодирования сверточного кода по алгоритму Витерби:
Y = 01 00 11 00 00 00 00 (принятый)
B = 1 0 0 0 0 0 0 (декодировано)
U = 11 10 11 00 00 00 00 (передано)

DVB-S – внутреннее кодирование
Материнский сверточный код со скоростью 1/2 и 64 состояниями
Скорости кода: 1/2, 2/3, 3/4, 5/6, 7/8

Схема сверточного кодера
Сверточное (convolutional) кодирование можно пояснить, рассматривая действие кодирующего устройства. Структурная схема одного из вариантов построения такого устройства представлена на рис. Оно состоит из (M-1)-разрядного сдвигового регистра, N сумматоров по модулю два и коммутатора K.
Кодируемые биты источника bi в дискретные моменты времени i = 1, 2, … последовательно поступают на вход кодера. Последние M – 1 бит источника запоминаются в регистре сдвига. Вместе с поступившим в дискретный момент времени i битом bi они подаются на N сумматоров по модулю два. При этом в каждый дискретный момент времени i блок из M бит источника линейно преобразуется в N выходных двоичных кодовых символов сверточного кода ui1, ui2, …, uiN, которые с помощью коммутатора K занимают временной интервал, равный длительности одного бита источника bi. Опрашивая поочередно выходы N сумматоров в течение битового интервала τb, коммутатор преобразует параллельное представление кодовых символов в последовательное. С приходом очередного бита содержимое регистра сдвигается на одну ячейку вправо. В результате вновь формируется блок из M бит источника, запаздывающий на один бит относительно предыдущего и содержащий M – 1 прежних битов и один новый. Этот блок кодируется по тому же правилу, что и предыдущий. Подобные шаги непрерывно повторяются. На каждый новый бит источника кодер откликается N кодовыми символами, поэтому скорость кода в битах на кодовый символ равна R = 1/N.

Сверточный кодер, M=4, N=2
Кодер как бы просматривает битовый поток источника сквозь скользящее окно ширины в M битовых интервалов, и кодирует все биты, попадающие в это окно на текущем шаге, в N кодовых символов. После каждого шага окно смещается вправо на один бит источника и выполняется следующий шаг. Размер окна M или число бит источника, влияющих на кодовые символы на одном шаге, называется конструктивным или кодовым ограничением.

Сверточный кодер со скоростью R = 1/2 на основе образующих полиномов g1(x) = x2 + x + 1, g2(x) = x2 + 1.
Для краткости описания кодирующего устройства вместо двоичных полиномов обычно указываются их коэффициенты, которые объединяют в двоичное слово и представляют в восьмеричной системе счисления. Например, для вышеуказанного кодера коэффициенты образующих полиномов g1(x), g2(x) составляют двоичные числа (111)2 и (101)2, что соответствует паре восьмеричных чисел (7, 5)8.

Схема кодера систематического нерекурсивного сверточного кода со скоростью кодирования R = 1/2
При g1(x) = 1 сверточный код становится систематическим. В нем биты источника явно присутствуют на определенных позициях, чередуясь с проверочными. Для получения систематических сверточных кодов можно построить как нерекурсивные так и рекурсивные кодеры.
Систематические коды, как правило, оказываются не лучшими в отношении корректирующей способности. Поэтому в обстоятельствах, когда систематичность кода критически важна, сверточный кодер модифицируют в структуру с обратной связью. Такие кодеры называются рекурсивными.

Для перевода несистематическго сверточного кода со скоростью R = 1/2 в систематическую форму вычисляется остаток r(x) = b(x)/g1(x) от деления полинома b(x), описывающего кодируемую последовательность, на производящий полином g1(x). Определяются полиномы u1(x) = b(x) и u2(x) = r(x)/g2(x), описывающие систематический выход и проверочные символы. Остаток r(x) можно получить с использованием регистра сдвига с обратными связями, поэтому полином g1(x) называется полиномом обратной связи, а полином g2(x) – выходным полиномом. Формируемые таким образом коды называются рекурсивными сверточными кодами RSC (Recursive Systematic Convolutional).
Схема систематического рекурсивного сверточного кодера с порождающими полиномами g1(x) = x2 + x + 1 и g2(x) = x2 + 1:

При использовании сверточных кодов со скоростью R = 1/N наибольшая кодовая скорость равна 1/2. Во многих практических случаях желательно работать на более высоких скоростях (например, 2/3 или 3/4). Одним из путей повышения кодовой скорости является переход к скоростям R = S/N, где N и S < N – натуральные числа. Такие скорости могут быть получены, если скользящее окно сдвигать каждый раз не на один, а на S символов, и формировать N кодовых символов на интервале, занимаемом S информационными символами, а не одним. Однако в настоящее время такой вид кодеров не находит широкого применения вследствие того, что сложность декодера экспоненциально растет с увеличением S. Поэтому чаще применяют другой способ повышения кодовой скорости, называемый выкалыванием (puncturing).
Под выкалыванием понимается удаление из кода некоторых символов по правилу, согласованному между передающей и приемной сторонами. Количество удаляемых бит определяет получающуюся кодовую скорость. Например, если с выхода декодера со скоростью R = 1/2 удалять каждый четвертый выходной бит, то получится код со скоростью R = 2/3. Основной особенностью выкалывания является то, что с помощью простого изменения числа удаляемых бит на базе одного и того же кодера могут быть построены коды с широким диапазоном кодовых скоростей.

Выкалывание может существенно снизить корректирующие способности сверточного кода, поэтому для оптимизации кодов с выкалыванием произведен машинный поиск, в результате которого получен целый ряд кодов с хорошими характеристиками.
Повышение скорости кодирования с помощью выкалывания
при n = 2, l = 3, g = 2
Формируемый по рассмотренному правилу код с выкалыванием содержит l исходных бит сверточного кода в каждом блоке, длина которого после удаления g символов составляет (l – g)·n + g·(n – 1) = l·n – g символов, так что в результате получается код со скоростью
вектор выкалывания P

Порождающая и проверочная матрицы кода
Пусть С – двоичный линейный код (n, k, dmin)
Любое кодовое слово v ∈ C можно разложить по базису
v = u0v0 + u1v1 + … + uk-1vk-1, где ui ∈ {0, 1}, 0 ≤ i < k
Это уравнение можно записать в матричной форме через порождающую матрицу G и вектор-сообщение u = (u0, u1, …, uk-1):
v = uG, G = (v0 v1 … vk-1)T
Так как С является k-мерным вектором в V2, то существует
(n-k)-мерное дуальное пространство C⊥, которое порождается строками матрицы проверочной матрицы H, такой что GHT = 0
Любое кодовое слово v ∈ C удовлетворяет условию vHT = 0
Линейный код C⊥, генерируемый матрицей H, является двоичным линейным кодом (n, n-k, d ⊥ min), который называют дуальным коду C

Граф, описывающий
состояние кодера:
Решетчатая
диаграмма кодера:
входная информационная
последовательность
{bi}=10100100
отображается
в кодовое слово
{ui1,ui2}=1110001011111011

Декодирование сверточных кодов
Алгоритм Витерби
Алгоритм Витерби является оптимальным, он обеспечивает максимально правдоподобное решение и сводится к нахождении кодового слова, наиболее близкого к принятому наблюдению с точки зрения выбранного критерия.
Жесткое декодирование – в качестве критерия используется расстояние Хэмминга: наблюдение декодируется в такое кодовое слово, которое находится на наименьшем расстоянии Хэмминга от принятого наблюдения.

Декодирование сверточных кодов
Алгоритм Витерби
На i–м шаге декодирования, в течение которого принимается i–я n–символьная кодовая группа наблюдения выполняются следующие операции:
Определяются хэмминговы расстояния между принятой n–символьной кодовой группой и каждой из ветвей решетчатой диаграммы. Поскольку из каждого из 2M-1 узлов выходят две ветви, всего вычисляется 2M расстояний.
Рассматриваются две ветви, идущие из разных предшествующих состояний к каждому из 2M-1 узлов:
Отвечающие указанным ветвям расстояния Хэмминга прибавляются к накопленным до i–го шага расстояниям Хэмминга двух соответствующих путей для получения новых значений расстояний. Указанное накапливаемое расстояние пути называется метрикой.
Сравниваются метрики двух соревнующихся путей, идущих в одно и то же состояние. Путь, находящийся на большем расстоянии от наблюдения, чем другой, отбрасывается и больше не учитывается в процедуре декодирования. Оставшийся путь называется выжившим путем.
Для всех 2M-1 выживших путей запоминаются значения их метрик и декодер готов к переходу на (i+1)–й шаг процедуры.

Динамика декодирования
сверточного кода
по алгоритму Витерби:
Y = 01001100000000
B = 1000000
U = 11101100000000

Обобщенная схема турбокодера

Схема декодера турбокода

Коды LDPC
Коды с низкой плотностью проверок на четность (LDPC) – класс линейных блоковых кодов, позволяющих получить превосходную эффективность с относительно малыми вычислительными затратами на их декодирование. Эти коды были предложены Р. Галлагером в 1963 г. В 1981 г. Р.М. Таннером было предложено использовать двудольные неориентированные графы для описания структуры итеративно декодируемых кодов. В принципе, любой блоковый код размерности (N, M), где N – число бит, M – число проверок в кодовом слове, можно представить в виде двудольного графа Таннера. На рис. изображен такой граф для кода Хэмминга (7, 4), проверочная матрица которого имеет вид:
Вершины графа называются проверочными (check nodes – CN) и битовыми узлами (variable nodes – VN), они обозначены как mi и ni соответственно.

Коды LDPC
При помощи графа Таннера большинство алгоритмов декодирования LDPC кодов можно представить в виде процесса последовательного обмена сообщения между соединенными ребрами вершинами. Для проверочных и битовых узлов графа вводиться понятия степени – величины, показывающей число ребер входящих в рассматриваемый узел. Степени битовых и проверочных узлов обозначаются dc и dr соответственно. Если dc и dr фиксированы для всех узлов, код называют регулярным, а если хотя бы один из этих параметров изменяется от узла к узлу – нерегулярным. Для описания нерегулярных кодов вводится ряд распределения степеней, показывающий долю узлов, имеющих конкретную степень.
В 1996 г. вышла в свет первая после Р. Галлагера работа, посвященная использованию LDPC кодов в качестве кодов, способных вплотную приблизиться к границе Шеннона при достаточно большой длине кодового слова. Появление этой статьи породило целую волну исследований, посвященных поиску новых, более эффективных структур LDPC кодов, а также альтернативных алгоритмов их декодирования с различными соотношениями эффективность/производительность.
Использование LDPC кодов предусматривает большинство современных стандартов передачи данных (например, IEEE 802.11, IEEE 802.16) и цифрового вещания (например, DVB‑S2, DVB‑T2, DVB‑C2).

Классификация кодов LDPC
По определению, данному Р. Галлагером, код LDPC – это линейный код, проверочная матрица H которого, размерности M×N, содержит dc << M единиц в каждом столбце и dr << N единиц в каждой строке. Причем распределение единиц по столбцам и строкам, в общем случае, случайно. На практике случайное распределение единиц неудобно – для кодирования и декодирования необходимо хранить проверочные и генераторные матрицы, что достаточно накладно при больших длинах кодов.
Очевидным средством борьбы с этой проблемой является переход к кодам LDPC, проверочная матрица которых обладает какой-то структурой. Простейший вариант структуризации проверочной матрицы – использование циклических кодов. Проверочная матрица такого кода представляет собой циркулянтную матрицу размерности N×N, в которой каждая строка получается циклическим сдвигом вправо предыдущей строки. Значение влияния цикличности проверочной матрицы на сложность декодера LDPC кода сложно переоценить, поскольку каждая из строк матрицы однозначно определяется предыдущей строкой, в связи с чем реализация декодера может быть существенно упрощена по сравнению со случайной структурой проверочной матрицы.

Классификация кодов LDPC
К недостаткам циклических кодов можно отнести фиксированный для всех скоростей кодирования размер проверочной матрицы N×N, что подразумевает более сложный декодер, а также высокий Хэммингов вес строк, что усложняет структуру декодера. К достоинствам, помимо упрощения кодирования/декодирования, следует отнести большое минимальное расстояние и очень низкий порог при итеративном декодировании.
Желание преодолеть недостатки циклических LDPC кодов привело к появлению квазициклических LDPC кодов. Квазициклические коды также имеют хорошую структуру, позволяющую упростить кодер и декодер. В дополнение к этому они позволяют более гибко подойти к разработке кода, в частности позволяют синтезировать нерегулярные коды. Проверочная матрица такого кода представляет собой не что иное, как набор циркулянтных подматриц. Для получения низкоплотностного кода циркулянтные матрицы должны быть разреженными, что на практике означает использование в качестве циркулянтов единичных матриц. Для того чтобы получить нерегулярный код, какие-то подматрицы просто объявляются нулевыми.

Методы построения проверочных матриц кодов LDPC
Методы построения LDPC кодов также можно разбить на классы. К первому классу относятся все алгоритмические способы и способы, использующие вычислительную технику. А ко второму – способы, основанные на теории графов, математике конечных полей, алгебре и комбинаторике.
Первый класс методов позволяет получать как случайные, так и структурированные коды LDPC , в то время как второй нацелен на получение только структурированных кодов LDPC , хотя бывают и исключения.
В отличие от других линейных блоковых кодов, таких как БЧХ или кодов Рида‑Соломона, имеющих строгий алгоритм синтеза кодов с заданными параметрами, для кодов LDPC существует множество способов построения кодов.
Часто используются способы построения LDPC кодов, предложенные Галлагером и МакКеем. В некоторых стандартах используется более сложный алгоритм построения достаточно эффективных кодов повторения накопления.

LDPC коды Галлагера
Проверочная матрица кода строится из подматриц Ha, a = 1, …, dc, которые
имеют структуру, описываемую следующим образом:
для любых двух целых μ и dr, больших 1, каждая подматрица Ha имеет размерность μ×μ·dr, при этом веса строк этой подматрицы – dr, а столбцов – 1. Подматрица H1 имеет специфическую форму: для i = 0, 1, …, μ – 1 i-ая строка содержит все dr единиц на позициях с i от dr до (i + r)·r – 1. Оставшиеся подматрицы получаются перестановкой столбцов матрицы H1. Очевидно, что результирующая матрица H – регулярная матрица размерности μ·dc×μ·dr с весами строк и столбцов dr и dс соответственно.
Важной характеристикой матрицы LDPC кода является отсутствие циклов определённой кратности. Под циклом кратности 4 понимается наличие в двух разных столбцах проверочной матрицы ненулевых элементов на совпадающих позициях. Отсутствие цикла кратности 4 определяется вычислением скалярного произведения столбцов матрицы: если всевозможные скалярные произведения всех столбцов матрицы не превосходят 1, то это означает отсутствие в матрице циклов кратности 4. Цикл кратности 4 является минимально возможным и встречается существенно чаще циклов большей длины (6, 8, 10 и т. д.). Присутствие в матрице LDPC кода циклов любой кратности свидетельствует о заложенной в структуру матрицы избыточности, не приводящей к улучшению помехоустойчивых свойств кода.

LDPC коды Галлагера
Пример циклов кратности 4:
Рассмотренный алгоритм не гарантирует отсутствие циклов кратности 4, однако они могут быть удалены впоследствии. Галлагер показал , что ансамбль таких кодов обладает прекрасными свойствами. Также была показана возможность реализации достаточно простых кодеров,
поскольку проверочные биты такого кода
могут быть найдены по проверочной
матрице кода как функция
информационных узлов.
Проверочная матрица кода
Галлагера (20, 5) dc = 3, dr = 4, μ = 5
имеет следующий вид:

LDPC коды МакКея
Тридцать пять лет спустя МакКей, будучи незнакомым с работой Галлагера, повторно открыл преимущества кодов с разреженными матрицами. При помощи компьютерного моделирования он показал возможность этих кодов вплотную приблизиться к границе Шеннона как для двоичного симметричного канала, так и для канала с аддитивным белым гауссовским шумом.
МакКей предложил несколько компьютерных алгоритмов построения проверочных матриц кодов LDPC. Вот некоторые из них в порядке увеличения сложности реализации:
1. Проверочная матрица H синтезируется путем случайного генерирования столбцов веса dc и, насколько это возможно, равномерным распределением весов строк dr.
2. Проверочная матрица H синтезируется путем случайного генерирования столбцов веса dc и строк веса dr, с дополнительной проверкой на отсутствие циклов кратности 4.
3. Проверочная матрица H синтезируется по алгоритму 2, с дополнительным удалением циклов кратности 4.
4. Проверочная матрица H синтезируется по алгоритму 3, с дополнительным условием, что проверочная матрица имеет вид H = [H1H2], где H2 – обратимая матрица.
Недостатком алгоритмов МакКея является отсутствие какой-либо структуры в проверочных матрицах, что усложняет процесс кодирования.

LDPC коды повторения накопления
К настоящему времени разработано достаточно большое количество более сложных алгоритмов, позволяющих получать коды, обладающие лучшей эффективностью и хорошо структурированной проверочной матрицей.
В стандарте DVB‑T2 используется систематический нерегулярный код повторения-накопления (irregular repeat accumulate – IRA). IRA коды – это класс LDPC кодов, разработанный на основе кодов повторения-накопления (repeat accumulate – RA). Отличительными особенностями этого класса кодов является возможность использования алгоритмов кодирования по проверочной матрице, а также возможность использования компактных форм хранения самих проверочных матриц.
Граф Таннера для IRA кода изображают в необычной форме, для этих кодов битовые узлы удобно разбить на информационные узлы (information nodes – IN) и узлы четности (parity nodes – PN). На рис. изображен граф Таннера для кода повторения-накопления, битовые узлы обозначены кругами, а проверочные – квадратами; битовые узлы, расположенные слева – информационные, поскольку соответствуют исходным битам, требующим кодирования, а расположенные справа – узлы четности PN, они соответствуют полученным в результате кодирования проверочным битам.

LDPC коды повторения накопления
Код DVB‑T2 является нерегулярным – степени символьных вершин переменные, в то время как степени кодовых вершин одинаковы (исключение составляет только самый первый кодовый узел, степень которого на единицу меньше).
Для описания распределения степеней информационных вершин IRA кода вводится ряд распределения (f1, …, fJ), где fi обозначает долю информационных узлов, соединенных с i проверочными узлами, fi ≥ 0, Sum(fi) = 1. Каждый проверочный узел соединен с a информационными узлами и полная запись параметров IRA кода имеет вид (f1, …, fJ; a).
Слева расположены K информационных узлов, по середине и справа – M проверочных узлов и узлов четности соответственно. Каждый проверочный узел соединяется ровно с a информационными узлами, это соединение может быть описано при помощи матрицы случайных перестановок M×a ребер. Соединение узлов четности с проверочными изображено зигзагообразной линией.

LDPC коды повторения накопления
Из структуры рассмотренного графа Таннера видно, что проверочную матрицу кода можно представить в виде двух подматриц H = [HuHp].
Подматрица Hu размерности M×K – разреженная матрица, а подматрица Hp, размерности M×M – ступенчатая матрица, которой на рис. соответствует ломаная линия, соединяющая проверочные узлы с узлами четности.
Кодирование линейных блоковых кодов осуществляется при помощи генераторной матрицы, которую, в свою очередь, можно получить по проверочной. Генераторная матрица, соответствующая данной проверочной матрице H, имеет вид:
При этом получение матрицы не представляет особого труда,
а подматрица генераторной матрицы G для IRA кода
является верхней треугольной матрицей.

LDPC коды повторения накопления
Можно показать, что операция умножения на матрицу эквивалента накоплению результата в простейшем аккумуляторе. Таким образом, в общем случае IRA кодер, состоит из матричного умножителя и аккумулятора, кодовое слово при этом состоит из информационной части u (входа матричного умножителя) и проверочной части p (выхода аккумулятора).
Получение генераторной матрицы в классическом смысле не требуется – преобразование матрицы перестановок и синтез аккумулятора тривиальны, что позволяет использовать проверочную матрицу как для кодирования, так и для декодирования.
В стандарте DVB‑T2 используется аналогичная схема кодирования, однако она имеет ряд особенностей, связанных с тем, что проверочные матрицы хранятся в сжатом виде.

LDPC коды DVB-T2
Используемые в DVB-T2 проверочные матрицы LDPC кода, помимо того, что они описывают IRA код, имеют некоторую периодичность в структуре, что позволяет существенно упросить их хранение, а также позволяет получить эффективную архитектуру декодеров таких кодов.
Способ построения матрицы Hu заключается в делении информационных узлов на группы по Q узлов в каждой, причем все узлы группы должны иметь одинаковую степень. При этом для того, чтобы однозначно определить схему соединения всех Q информационных узлов с проверочными узлами, достаточно указать только те проверочные узлы, которые соединены с первым информационным узлом в рассматриваемой группе.
Обозначим как индексы проверочных узлов, соединенных с первым информационным узлом в группе, тогда индексы проверочных узлов любого i-го информационного узла в группе можно получить, воспользовавшись формулами:
где q = (n – k)/Q.

LDPC коды DVB-T2
Для полного описания структуры матрицы используемого кода необходимо указать проверочные узлы, соединенные с первым информационным узлом в каждой из групп. Код стандарта DVB‑T2 предусматривает использование фиксированного размера групп для всех скоростей и размеров блоков – это Q = 360 битовых узлов, число групп в матрице будет отличаться для различных скоростей и размеров блоков. В стандарте приводятся таблицы, в которых перечисляются проверочные узлы для первого битового узла каждой из групп для всех скоростей кодирования и используемых блоков передачи данных.
Пример таблицы для короткого блока (N = 16200) со скоростью кодирования 2/3 представляет собой запись матрицы размерности 10800×16200 и имеет следующий вид:
0 2084 1613 1548 1286 1460 3196 4297 2481 3369 3451 4620 2622
1 122 1516 3448 2880 1407 1847 3799 3529 373 971 4358 3108
2 259 3399 929 2650 864 3996 3833 107 5287 164 3125 2350
3 342 3529 1 2583 1180
4 4198 2147 2 1542 509
5 1880 4836 3 4418 1005
6 3864 4910 4 5212 5117
7 243 1542 5 2155 2922
8 3011 1436 6 347 2696
9 2167 2512 7 226 4296
10 4606 1003 8 1560 487
11 2835 705 9 3926 1640
12 3426 2365 10 149 2928
13 3848 2474 11 2364 563
14 1360 1743 12 635 688
0 163 2536 13 231 1684
14 1129 3894

Декодирование кодов LDPC
Р. Галлагер предложил два итеративных алгоритма декодирования кодов LDPC. Первый – алгоритм с распространением доверия (belief propagation, BP). Этот алгоритм обладает максимальной эффективностью среди всех известных алгоритмов декодирования. Доказано, что алгоритм BP достигает максимума правдоподобия, при условии, что проверочная матрица кода не содержит циклов. Расплата за столь высокую эффективность – максимальная вычислительная сложность среди всех известных алгоритмов.
Второй алгоритм, предложенный Р. Галлагером, – алгоритм с инверсией бита (bit flip algorithm, BF). Он очень прост в реализации и использует жесткие решения модема относительно принятых бит. Расплата за простоту – низкая эффективность этого алгоритма. Оба алгоритма в настоящее время хорошо исследованы и для них разработано множество модификаций. Также существует и множество альтернативных оригинальных алгоритмов декодирования LDPC кодов.

Декодирование кодов LDPC - BF
Алгоритм BF можно представить в виде основных шагов, выполняемых итеративно:
- инициализация,
- обновление проверочных узлов,
- обновление битовых узлов,
- инверсия бит.
Первый шаг алгоритма – инициализация – выполняется только один раз для каждого кодового слова. Суть ее заключается в вынесении жестких решений относительно принятых бит: xn = sing(yn), n = 1, …, N, xn – жесткие решения модема относительно принятых бит yn.
Второй шаг – обновление проверочных узлов ,
xni - входящие в проверочный узел m сообщения,
σm – исходящее из этого проверочного узла сообщение,
dr – количество смежных битовых узлов.
Здесь xn – по существу не что иное, как знак принятого из
канала значения, полученный на этапе инициализации.
В случае алгоритма с инверсией бита исходящее сообщение
σm может принимать всего два значения – 0 или 1, что,
в свою очередь, показывает, выполняется соответствующая
проверка или нет.

Декодирование кодов LDPC - BF
Третий шаг алгоритма – обновление битовых узлов: ,
Zn – исходящее из битового узла n сообщение,
σmi – входящие в этот битовый узел сообщения,
dc – количество смежных проверочных узлов.
В случае алгоритма с инверсией бита значение исходящего сообщения Zn равно числу невыполненных проверок для битового узла n. После того как найдены значения Zn для всех битовых узлов, находится и инвертируется бит, для которого Zn максимально.
Алгоритм является очень простым, а, следовательно, очень быстрым, однако эффективность этого алгоритма существенно ниже алгоритма BP. Другим существенным недостатком этого алгоритма является его медленная сходимость, особенно для блоков большой длины. В силу указанных недостатков этот алгоритм практически не используется.

Декодирование кодов LDPC - BP
Алгоритм BP можно представить в виде следующих шагов:
- инициализация,
- обновление проверочных узлов,
- обновление битовых узлов,
- вынесение жестких решений.
Последние три шага выполняются итеративно.
Инициализация алгоритма: Znmi – сообщения от битового узла n
к соответствующему проверочному узлу mi, rn – логарифмическое
отношение правдоподобия (log likelihood ratio, LLR) для битового
узла n.
Второй шаг алгоритма – обновление проверочных узлов:
Znim – входящие сообщения для проверочного узла m
от dr смежных битовых узлов,
ynim – исходящие сообщения от узла m
к битовым узлам ni. Исходящие сообщения рассчитываются
по следующей формуле:

Декодирование кодов LDPC - BP
Третий шаг – обновление битовых узлов:
ynmi – входящие сообщения для битового узла n от dc смежных
проверочных узлов, Znmi – исходящие сообщения для каждого
проверочного узла mi.
После обновления всех битовых узлов находятся жесткие оценки
принятых бит, которые представляют собой нечто иное, как знак Zn:
Если все проверки выполняются при подстановке в них жестких оценок принятых бит, это значит, что в результате декодирования найдено допустимое кодовое слово. При этом вычисления прекращаются, а найденное кодовое слово считается результатом декодирования. В противном случае выполняется еще одна итерация обновления проверочных и битовых узлов. В случае если достигнуто максимальное заданное число итераций декодирования, а допустимое кодовое слово не найдено, то вычисления прекращаются, а текущее кодовое слово считается результатом декодирования.
К недостаткам алгоритма BP относятся высокая сложность реализации, а также необходимость оценки отношения сигнал/шум на входе приемника для расчета логарифмических отношений правдоподобия.