2.3 Ldpc коды: декодирование
Из (2.4) видно, что, фиксируя переменную степень распределения кода, число дуг в фактор графе такого кода пропорционально n. Это существенное свойство LDPC кодов, которое создает их декодирующую сложность линейно с длиной кода, с учетом фиксированного числа итераций. Это связано с тем, что декодирование производится путем передачи сообщения по дугам графа, следовательно, сложность одной итерации порядка Е.
Есть много различных алгоритмов передачи сообщений для LDPC кодов. Целью данного раздела является представить некоторые из этих алгоритмов декодирования. Мы начнем с алгоритма sum –product и, используя интерпретацию декодирования методом sum-product, нам станут понятны другие алгоритмы декодирования.
2.3.1 Алгоритм sum-product
Приложение A описывается алгоритмом sum-product в общем виде. Рассматривая основную цель этой главы, мы ориентируемся на упрощенный случай, в котором переменные узлы имеют двоичное значение и функциональные узлы ограничены контролем четности. Не вдаваясь в детали, определим характер сообщений и упрощенные правила их корректировки. Затем мы используем это, чтобы сформировать объяснение декодирования методом передачи сообщений LDPC кодов.
Для
двоичных переменных узлов, сообщение
которое является функцией соседнего
переменного узла
имеет только два значения,
.
Когда сообщения являются функциями
условных вероятностных мер (фувм),
,
поэтому передача только одного из
сообщений
эквивалентна
передаче функции
.
Равнозначно мы можем передавать
комбинации
,
такие, что
.
Последняя величина
или
в случае фувм
известна
как отношение логарифмического
правдоподобия (LLR) и
наиболее распространенным типом
сообщения, используемом в литературе.
Причина заключается в том, что здесь
методы корректировки просты и в
компьютерной реализации, это можно
представить вероятностными значениями,
которые очень близки к нулю или очень
близки к единице, не вызывая ошибки в
погрешности. Здесь мы только приводим
методы корректировки, когда сообщения
LLR. Для сообщений, взамен
µ, мы используем m, чтобы различать общие
методы передачи сообщений и методы
передачи сообщений LLR.
Методы корректировки для других видов
сообщений можно найти в [29]. Обратите
внимание, что сообщение уже не функция,
а действительное число.
Метод
корректировки узла контроля четности
где
представляет собой LLR
сообщение, отправленное из узла
в узел b, и
представляет собой представляет собой
совокупность всех соседних узлов
в графе.
Метод
корректировки переменного узла
где
является внутренним сообщением для
переменного узла
.
Внутреннее сообщение вычисляется из
наблюдаемого канала и без использования
избыточности в коде. Декодируемые
сообщения, как правило, посылаются как
внешние сообщения. Внешние сообщения
соответствуют структуре кода и изменяются
итерация за итерацией. Успешное
декодирование улучшает качество внешних
сообщений итерация за итерацией.
На рис.
2.3 показан фактор граф LDPC
кода в декодере. Здесь показаны внутренние
и внешние сообщения на переменный узел
.
Здесь также изображено, что исходящие
сообщения на дугу
,
соединенные с узлом
(в данном случае
),
зависят от всех входящих сообщений на
этот узел, кроме входящих сообщений на
.
Это свойство является одним из основных
направлений анализа LDPC
кодов. На рис. 2.3 функциональные узлы на
левой стороне соответствуют каналу.
Эти функциональные узлы соединяют бит
передатчика с тем же битом приемника.
В зависимости от типа канала и модели
шума, эти функции могут быть вычислены.
MAP решение (примерное MAP решение соответствует наличию циклов) для переменного узла может быть сделано на основании следующего метода решения
Если
,
то обе
и
имеют одинаковые вероятности и решение
может быть осуществлено случайно.
В оставшейся части этой работы, когда мы ссылаемся на алгоритм sum-product, мы имеем в виду упрощенный случай для двоичного кода с контролем четности, если не указано иное.
Рисунок
2.3: Внутренние и внешние сообщения на
переменном узле
А также внутренние сообщения, которые
влияют на исходящее сообщение на
переменном узле
.