4LDPC коды в системе DVB-T2.
Коды с малой плотностью проверок на четность (LDPC-код от англ. Low-densityparity-checkcode, LDPC-code, низкоплотностный код) были впервые предложены Робертом Галлагером и позднее исследовались во многих научных работах. Несмотря на то, что в течение долгого времени LDPC-коды были практически исключены из рассмотрения, в последние годы наблюдается увеличение количества исследований в этой области. Это связано с тем, что, обладая плохим минимальным расстоянием, коды с малой плотностью, тем не менее, обеспечивают высокую степень исправления ошибок при весьма малой сложности их декодирования. Было показано, что с ростом длины некоторые LDPC-коды могут превосходить турбо-коды и приближаться к пропускной способности канала с аддитивным белым гауссовским шумом. Вместе с тем многие предложенные конструкции LDPC-кодов являются циклическими или квазициклическими, что позволяет производить не только быстрое декодирование, но и эффективные процедуры кодирования. Кроме того, даже для LDPC-кодов, не обладающих свойством цикличности, были предложены эффективные процедуры кодирования.
В первоначальном виде, LDPC коды это линейные блочные коды характеризующиеся разреженной, т.е. низкоплотностной матрицей проверок на четность H столбцы которой имеют фиксированное число ненулевых элементов - dv и строки которой имеют фиксированное число ненулевых элементов - dc. Например матрица LDPC кода проверки четности с dv=3, dc=6:
По определению, если каждая строка матрицы содержит ровно K˂N, и каждый столбец ровно J˂R единиц, то код называется регулярным.
Допустим N-число столбцов проверочной матрицы, т. е. N это длина кодового слова. Пусть M
Hx =0, (4.2)
то есть число линейно независимых столбцов матрицы H, является равным K = N −M, которое также соответствует числу информационных битов в кодовом слове. Конечно очевидно, что сумма всех единиц во всех строках равняется сумме всех единиц во всех столбцах, поэтому:
Ndv = Mdc=(N − K)dc.
Откуда:
 (4.3)
Выражение R = K/N также называется скоростью кода, т.е. среднее число информационных символов в кодовом слове. Поэтому регулярный (dv, dc) LDPC код обладает скоростью кода R =1 − dv/dc.
Можно связать проверочную матрицу H с двудольным графом в непосредственном соответствии. Такой граф содержит два вида узлов: каждый узел первого вида, обозначенный как переменный узел, связан со столбцом H; каждый узел второго вида, обозначенный как проверочный, связан со строкой H.
Двудольный граф связанный с проверочной матрицей строится
следующим образом:
Рисунок 4.1 - Изображена иллюстрация построения графа для регулярных (2, 4) кодов LDPC [4]
Алгоритм построения двудольного графа для регулярных (2,4) кодов LDPC.
1. выделить массив переменных узлов - N, каждый из которых соответствует столбцу H;
2. выделить массив проверочных узлов - М, каждый из которых соответствует строке Н;
3. для каждого ненулевого элемента из матрицы Н, соединить ветвью перемененные и проверочные узлы каждого столбца и строки, соответственно.
В уравнении проверки четности (3,2), каждый столбец матрицы H умножается на соответствующий двоичный символ кодовой комбинации. Таким образом, каждый переменный узел связан с двоичным символом в кодовой комбинации. Положением бита представлено положение столбца, связанного с переменным узлом. С другой стороны, каждый узел проверки связан с уравнением проверки четности по указанной строке, соответствующей этому конкретному узлу проверки. Говорят, что узел "степени i". Если от i отходят ветви, то тогда с i связывают узлы другого рода другого рода.
Описанные выше двудольные графы для кодов LDPC так же называются графами Таннера для линейных блочных кодов. Они могут быть использованы для описания ограничений, которым должно удовлетворять кодовая комбинация, чтобы принадлежать определенному линейному блочному коду. Можно заметить, что заменяя любую строку в проверочной матрице Н с линейной комбинацией самой строки и любых других наборов строк, не изменяет набор кодовых слов удовлетворяющих уравнению контроля четности (3.2), т.е. полученная матрица является матрицей проверки четности для того же кода. Другими словами, каждый линейный блочный код допускает несколько проверочных матриц, или, эквивалентно, несколько представлений графов Таннера. Однако, в основном, описанный выше метод линейной комбинации не сохраняет разряженность проверочной матрицы.
Интересно отметить, что, хотя не исключено составление проверочной матрицы для регулярного (dv, dc) кода, когда dv четное число, эта матрица не будет иметь максимальный ранг поскольку существует по крайней мере одна линейная комбинация строк равная нулевому вектору. Действительно, рассмотрим вектор r = (r1, . . . , rN) получается путем суммирования всех векторов-строк в H. j-й элемент вектора r имеет вид:
где {hij} обозначает элементы Н. Таким образом, можно удалить строку из матрицы проверки четности, не изменяя набор кодовых слов и увеличивая скорость кода. Как следствие, не может существовать регулярный(dv,dc) LDPC код с четнымdv и скоростью 1 - dv/dc.
Обозначение (dv, dc) для регулярных LDPC кодов описывает особое свойство, т.е. то что код допускает проверочную матрицу, которая имеет ровно dv единиц в каждом столбце и dc единиц в каждой строке. Таких кодов может быть больше одного даже если длина кодового слова N фиксирована. Таким образом, это обозначение определяет класс или ансамбль (группу) кодов. Существует несколько аналитических методов представления LDPC кодов для кодирования ансамблей, в том смысле, что этот анализ характеризует ожидаемое исполнение, когда фактический код выбирается из всего ансамбля в случайном порядке.
Хотя предположение регулярности существенно упрощает анализ производительности, оно накладывает излишние ограничения на структуру матрицы проверки четности.
Построение двудольного графа не зависит от регулярности кода и, следовательно, так же применимо к нерегулярным LDPC кодам. В случае нерегулярности, количество ветвей привязанных к различным узлам может меняться от узла к узлу, независимо от их вида. Другими словами, узлы переменных (или проверочные) не обязаны иметь равную степень.
Чтобы дать описание нерегулярным LDPC ансамблям кодов, вводится понятие распределения степени. Распределения степени для LDPC кода задается парой полиномов.
 ,где
- коэффициент λi это часть ветвей графа соединяющих переменные узлы степени – i
-ρj это часть ветвей графа соединяющих проверочные узлы степени – j. Многочлен ρ(x) называется распределением степеней узлов проверок и λ(x) называется распределением степеней узлов переменных.
Коэффициенты {ρj} и {λi} должны удовлетворять следующим ограничениям:
Где третье и четвертое возникают потому что, «сумма всех граней графа» должна быть равна единице.
Если граф имеет l ветвей, т.е. соответствующая матрица проверки четности имеет l ненулевых элементов, число vi переменных узлов степени i
и число степень cj проверочных узлов
Поэтому число N переменных узлов задается
Число М узлов проверки задается
Таким образом, кодовая скорость выглядит следующим образом:
Можно заметить, что, для заданной скорости кода R, коэффициенты распределения степени должны удовлетворять следующему линейному ограничению:
Нерегулярные LDPC коды известны сегодня в числе самых мощных двоичных кодов.
На практике были получены нерегулярные LDPC коды с характеристиками близкими к пропускной способности для различных двоичных каналов без памяти, среди которых двоичный канал со стиранием (BEC) и двоичный симметричный канал (BSC).
|
