LDPC-коды описываются низкоплотностой проверочной матрицей, содержащей в основном нули и относительно малое количество единиц. По определению, если каждая строка матрицы содержит ровно k < n и каждый столбец ровно j < r единиц, то код называют регулярным (в противном случае — нерегулярным). В общем случае количество единиц в матрице имеет порядок O(n) , то есть растёт линейно с увеличением длины кодового блока (количества столбцов проверочной матрицы).
Обычно рассматриваются матрицы больших размеров. Например, в работе Галлагера в разделе экспериментальных результатов используются «малые» количества строк n=124, 252, 504 и 1008 строк (число столбцов проверочной матрицы немного больше). На практике применяются матрицы с большим количеством элементов — от 10 до 100 тысяч строк. Однако количество единиц в строке или в столбце остаётся достаточно малым, обычно меньшим 10. Замечено, что коды с тем же количеством элементов на строку или столбец, но с большим размером, обладают лучшими характеристиками.
Рисунок 1.Проверочная матрица LDPC-кода(9, 2, 3) с минимальным циклом длины 8
Важной характеристикой матрицы LDPC-кода является отсутствие циклов определённого размера. Под циклом длины 4 понимают образование в проверочной матрице прямоугольника, в углах которого стоят единицы. Отсутствие цикла длины 4 можно также определить через скалярное произведение столбцов (или строк) матрицы. Если каждое попарное скалярное произведение всех столбцов (или строк) матрицы не более 1, это говорит об отсутствии цикла длины 4. Циклы большей длины (6, 8, 10 и т. д.) можно определить, если в проверочной матрице построить граф, вершинами которого являются единицы, а рёбра — все возможные соединения вершин, параллельные сторонам матрицы (то есть вертикальные или горизонтальные линии). Минимальный цикл в этом графе и будет минимальным циклом в проверочной матрице LDPC-кода. Очевидно, что цикл будет иметь длину как минимум 4, а не 3, так как рёбра графа должны быть параллельны сторонам матрицы. Вообще, любой цикл в этом графе будет иметь чётную длину, минимальный размер 4, а максимальный размер обычно не играет роли (хотя, очевидно, он не более, чем количество узлов в графе, то есть n×k).
Описание LPDC-кода возможно несколькими способами:
Способ задания кода проверочной матрицей является общепринятым для линейных кодов, когда каждая строка матрицы является элементом некоторого множества кодовых слов. Если все строки линейно-независимы, строки матрицы могут рассматриваться как базис множества всех кодовых векторов кода. Однако использование данного способа создаёт сложности для представления матрицы в памяти кодера — необходимо хранить все строки или столбцы матрицы в виде набора двоичных векторов, из-за чего размер матрицы становится равен j×k  бит.
Распространённым графическим способом является представление кода в виде двудольного графа. Сопоставим все k строк матрицы k нижним вершинам графа, а n столбцов — верхним, и соединим верхние и нижние вершины графа, если на пересечении соответствующих строк и столбцов стоят единицы.
Рисунок 2. Представление LDPC-кода в виде двудольного графа
К другим графическим способам относят преобразования двудольного графа, происходящие без фактического изменения самого кода. Например, можно все верхние вершины графа представить в виде треугольников, а все нижние — в виде квадратов, после чего расположить рёбра и вершины графа на двухмерной поверхности в порядке, удобном для визуального понимания структуры кода. Например, такое представление используется в качестве иллюстраций в книгах Девида Маккея.
Рисунок 3. Представление (9, 2, 3) LDPC-кода в виде графа специального вида 
Вводя дополнительные правила графического отображения и построения LDPC-кода, можно добиться, что в процессе построения код получит определённые свойства. Например, если использовать граф, вершинами которого являются только столбцы проверочной матрицы, а строки изображаются многогранниками, построенными на вершинах графа, то следование правилу «два многогранника не разделяют одно ребро» позволяет избавиться от циклов длины 4.
При использовании специальных процедур построения кода могут использоваться и свои способы представления, хранения и обработки (кодирования и декодирования). 
 Кодирование и декодирование LDPC-кодов
Кодирование в LDPC осуществляется путем умножения кодовых слов с на проверочную матрицу H и получения векторов y. При реализации кодера в нем может храниться сама проверочная матрица H (например, для коротких кодов), однако чаще встречаются другие аппаратные реализации. Наибольший интерес для исследователей представляет процедура декодирования, ввиду того что она является более времязатратной и ресурсоемкой.
Декодирование – это процедура поиска и исправления ошибки, наложенной каналом на кодовое слово, по принятому из канала вектору или собственно поиск кодового слова по вектору, принятому из канала.
Декодирование по максимуму правдоподобия кода C обозначает нахождение по заданному принятому вектору y такого кодового слова c из C (множества всех кодовых слов), которое максимизирует вероятность того, что передавалось слово c при условии принятия вектора y. Задача декодирования по максимуму правдоподобия является NP-полной.
Для оценки качества работы различных декодеров используется оценка вероятности ошибки декодирования (BER) на информационный бит, вычисляемая как отношение количества ошибочных информационных бит после декодирования к общему количеству переданных информационных бит. Итеративные схемы декодирования кодов с низкой плотностью проверок на четность не являются декодерами по максимуму правдоподобия, но позволяют получить разумный баланс по сложности и вероятности ошибки декодирования по сравнению с декодированием по максимуму правдоподобия. Итеративное декодирование подразумевает, что нахождение кодового слова будет производиться не за один проход, а за несколько, с последовательным уточнением результата на каждом шаге. Применяются следующие основные схемы декодирования.
«Жесткое» декодирование
«Жесткое» декодирование – это схема декодирования для двоичного симметричного канала при небольшом количестве ошибок в канале. «Жесткое» декодирование инвертированием битов – самая простая схема декодирования кодов с низкой плотностью проверок на четность.
Под проверкой понимается любая строка h = {h0, ..., hN–1} из проверочной матрицы кода с низкой плотностью проверок на четность. Будем говорить, что проверка для некоего вектора y = {y0, ..., yN–1} выполняется тогда, когда скалярное произведение вектора y на проверку дает ноль. Будем говорить, что элемент yi принятого вектора y участвует в проверке h = {h0, ..., hN–1} тогда, когда соответствующий элемент проверки hi не равен нулю.
Одна итерация «жесткого» декодирования инвертированием битов производится следующим образом.
1. Для принятого вектора вычисляются все проверки.
2. Если некоторый бит принятого вектора участвовал более чем в половине невыполнившихся проверок, бит инвертируется.
3. После такого анализа всех символов принятого вектора вектор проверяется на принадлежность коду. Если вектор является кодовым словом, декодирование заканчивается, в противном случае выполняется следующая итерация алгоритма.
Такая процедура декодирования применима для кодов с низкой плотностью проверок на четность потому, что большинство проверок в таком случае будут содержать одну ошибку или не будут содержать ошибок вообще и тогда невыполнение большого количества проверок для символа принятого слова будет обозначать наличие в нем ошибки.
Сложность одной итерации «жесткого» декодирования инвертированием бит является линейной, количество итераций декодирования обычно выбирается около log2(N), где N – длина кодового слова.
Декодирование по вероятностям
Декодирование по вероятностям является «мягким» декодированием, т. е. декодированием на основе вектора, состоящего не из дискретных значений (0 и 1), а из вещественных величин, полученных на выходе канала путем пересчета вероятностей (англ. belief propagation decoding).
На основе принятого из канала вектора формируются два (для двоичного случая) вектора вероятностей того, что в принятом векторе на данной позиции находился заданный символ.
Каждому ненулевому элементу проверочной матрицы кода с низкой плотностью проверок на четность приписываются две величины: qxi,j и rxi,j. Величина qxi,j является вероятностью того, что j-й символ принятого вектора имеет значение x по информации, полученной из всех проверок, кроме i-й. Величина rxi,j является вероятностью того, что проверка i выполняется, если j-й символ принятого вектора равен x, а все остальные символы проверок имеют распределение вероятностей, заданное величинами {qxi,j : j из N(i)\j}, где N(i) – множество символов, входящих в i-ю проверку.
Перед началом работы алгоритму требуется инициализация, далее алгоритм работает по принципу пересчета вероятностей символов принятого вектора (belief propagation), используя для пересчета вероятностей правило Байеса для апостериорной вероятности события. Одна итерация алгоритма представляет собой следующую последовательность действий.
1. Для всех проверок вычисляются величины Δ ri,j и пересчитываются вероятности rxi,j для x = {0, 1}.
2. Для всех символов принятого вектора пересчитываются вероятности qxi,j.
3. Формируются векторы псевдоапостериорной вероятности q0j и q1j.
4. Формируется вектор решения c’ по следующему правилу: c’j = 1, если q1j > ½, иначе 0.
Если вектор c’ является кодовым словом, декодирование заканчивается, в противном случае выполняется следующая итерация алгоритма.
Сложность данного алгоритма выше, чем сложность «жесткого» декодирования инверти-рованием битов, но качество декодирования повышается за счет использования дополнительной информации на выходе канала. Однако точность работы такого алгоритма зависит от инициализации: чем точнее она произведена, тем точнее будет конечный результат. Для канала с гауссовским шумом инициализация может быть произведена при помощи информации о дисперсии шума в канале. Для других распределений шума в канале или при неизвестных характеристиках шума точная инициализация алгоритма может оказаться сложной задачей.
Быстрое декодирование LDPC
Несмотря на то что декодирование пересчетом вероятностей является эффективным методом для каналов с непрерывным выходом, тот факт, что сложность его значительно выше, чем сложность «жесткого» декодирования, создает предпосылки для поиска более быстрых алгоритмов декодирования, обладающих приемлемым качеством.
Сложность декодера UMP (быстрого декодирования по надежностям) значительно ниже, чем сложность декодера, пересчитывающего вероятности, за счет того, что пересчет надежностей выполняется по упрощенной схеме (схеме «взвешенного» мажоритарного голосования, в качестве «весов» используется надежность проверок), а также за счет возможности использования исключительно целочисленных операций сложения и сложения по модулю два. Также к достоинствам быстрого декодера по надежностям можно отнести то, что декодеру не требуется знать характеристики шума в канале (дисперсию и т. д.), следовательно, такой декодер может работать в любом симметричном канале с двоичным входом.
Недостатком быстрого декодера по надежностям является оценка вероятности ошибки декодирования, которая для канала с аддитивным гауссовским шумом оказывается на 0,5 дБ хуже, чем вероятность ошибки декодирования вероятностного декодера.
Многопороговое декодирование
Основная идея многопорогового декодирования по надежностям состоит в том, чтобы изменять значения порогов инвертирования символов от одной итерации к другой следующим образом: на первых итерациях порог инвертирования символов выбирается так, чтобы количество инвертированных символов было минимальным (вплоть до инвертирования только одного символа на первой итерации); на последующих итерациях пороги инвертирования постепенно повышаются.
При многопороговом декодировании, если на первой итерации была исправлена хотя бы одна ошибка, декодирование на последующих итерациях становится значительно проще и общее качество декодирования улучшается. По-прежнему для работы декодеру не требуется информация о шуме в канале, достаточно лишь задать надежности.
Декодер, работающий по многопороговой схеме, позволяет получить вероятность ошибки декодирования на 0,1–0,4 дБ лучше, чем обеспечивает быстрый декодер по надежностям UMP, практически приближаясь к вероятности ошибки, получаемой при вероятностном декодировании кодов с низкой плотностью проверок на четность. Помимо независимости от характеристик канала многопороговый декодер обладает свойством декодеров кодов с низкой плотностью проверок на четность, а именно универсальностью и применимостью для любой конструкции таких кодов.
Следует отметить, что эффективность нерегулярных LDPC-кодов оказывается выше эффективности регулярных кодов. Это объясняется тем, что в нерегулярных кодах из-за различного числа единиц в строках и столбцах информационные символы защищены по-разному. В результате при декодировании проявляется так называемый эффект волны, когда более защищенные биты декодируются быстрее и затем как бы помогают при декодировании менее защищенных бит.
Рисунок 4. Пороги для многопорогового декодирования
Используемая литература:
  1. http://ru.wikipedia.org/wiki/LDPC
  2. Sarah Johnson, Introducing Low-Density Parity-Check Codes, ACoRN Spring School 2006.
  3. Bernhard M.J. Leiner, Stud.ID., LDPC Codes – a brief Tutorial, April 8, 2005.
  4. А. А. Овчинников, К вопросу о построении LDPC- кодов на основе евклидовых геометрий.
  5. А. В. Белоголовый, Е. А. Крук, Многопороговое декодирование кодов с низкой плотностью проверок на четкость.