Алгоритм sum-product

В приложение A описывается алгоритм sum-product в общем виде. Рассматривая основную цель этой главы, мы ориентируемся на упрощенный случай, в котором переменные узлы имеют двоичное значение и функциональные узлы ограничены контролем четности. Не вдаваясь в детали, определим характер сообщений и упрощенные правила их корректировки. Затем мы используем это, чтобы сформировать объяснение декодирования LDPC кодов методом передачи сообщений.

Для двоичных переменных узлов сообщение которое является функцией соседнего переменного узла имеет только два значения, . Когда сообщения являются функциями условных вероятностных мер (pmfs), , поэтому передача только одного из сообщений эквивалентна передаче функции . Равнозначно мы можем передавать комбинации такие, что . Последняя величина или в случае pmfs известна, как отношение логарифмического правдоподобия (LLR) и наиболее распространенным типом сообщения, используемым в литературе. Причина заключается в том, что здесь методы корректировки просты и в компьютерной реализации это можно представить вероятностными значениями, которые очень близки к нулю или очень близки к единице, не вызывая ошибки в погрешности. Здесь мы только приводим методы корректировки, когда сообщения LLR. Для сообщений, взамен µ, мы используем m, чтобы различать общие методы передачи сообщений и методы передачи сообщений LLR. Методы корректировки для других видов сообщений можно найти в [29]. Обратите внимание, что сообщение уже не функция, а действительное число.

Правило корректировки узла контроля четности :

где представляет собой LLR сообщение, отправленное из узла в узел b, и представляет собой представляет собой совокупность всех соседних узлов в графе.

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

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

На рис. 2.3 показан фактор граф LDPC кода в декодере. Здесь показаны внутренние и внешние сообщения на переменный узел . Здесь также изображено, что исходящие сообщения на дугу , соединенные с узлом (в данном случае ), зависят от всех входящих сообщений на этот узел, кроме входящих сообщений на . Это свойство является одним из основных направлений анализа LDPC кодов. На рис. 2.3 функциональные узлы на левой стороне соответствуют каналу. Эти функциональные узлы соединяют бит передатчика с тем же битом приемника. В зависимости от типа канала и модели шума, эти функции могут быть вычислены.

MAP решение (примерное MAP решение соответствует наличию циклов) для переменного узла может быть сделано на основании следующего метода решения:

Если , то обе и имеют одинаковые вероятности и решение может быть осуществлено случайно.

В оставшейся части этой работы, когда мы ссылаемся на алгоритм sum-product, мы имеем в виду упрощенный случай для двоичного кода с контролем четности, если не указано иное.

Рис. 2.3. Внутренние и внешние сообщения на переменном узле А также внутренние сообщения, которые влияют на исходящее сообщение на переменном узле .

Поиск по сайту: