Логарифмический алгоритм распространения доверия (ЛАРД) основывается на критерии максимума апостериорной вероятности, который в свою очередь базируется на вычислении апостериорной вероятности того, что конкретный бит xi в переданном кодовом слове x = [x0, x1, …, xN-1] равен единице, при условии приема из канала кодового слова y = [y0, y1, …, yN-1]:
тогда отношение правдоподобия для этого бита равно:
или же, если перевести в логарифмическую форму:
данное отношение и называется логарифмическим отношением правдоподобия.
В алгоритме ЛАРД можно выделить несколько основных шагов [1]-[3].
Шаг 1. Инициализация декодера. Для всех узлов i инициализируются значения Li в зависимости от используемой модели канала связи:
где yi - принятое из канала значение для символа i. Затем для всех i и j, для которых hij = 1, устанавливается Li→j = Li.
Шаг 2. Обновление проверочных узлов. Для всех проверочных узлов CNj вычисляются исходящие сообщения Lj→i, а затем передаются их соответствующим информационным узлам VN.
где ⊞ - оператор суммы логарифмических отношений правдоподобия:
Шаг 3. Обновление информационных узлов. Для всех информационных узлов VN вычисляются исходящие сообщения Li→j, а затем передаются соответствующим проверочным узлам CN.
Шаг 4. Вычисление апостериорных ЛОП. Для всех j = 0, 1, …, N – 1 вычисляется апостериорная ЛОП:
Шаг 5. Получение жестких решений. Для всех i = 0, 1, …, N – 1 элементов кодового слова находятся жесткие решения:
Шаг 6. Проверка условия остановки. Вычисляется синдром декодирования:
Если синдром равен нулю (s = 0) или достигнуто максимальное число итераций, процесс декодирования останавливается, в ином случае, вычисления продолжаются со второго шага.
Для увеличения быстродействия блока применяется модификация ЛАРД по Якоби, позволяющая уменьшить вычислительные затраты, без изменения эффективности декодирования. Данная модификация основана на численной аппроксимации выражения из шага 2 при помощи логарифма Якоби:
дважды применив логарифм Якоби к данному выражению, получим:
Можно показать [4], что:
тогда окончательно имеем:
где:
При этом g(L1, L2) обычно представляют в виде:
где:
Кроме того, для увеличения эффективности декодирования предусмотрена возможность включения Self-Correction модификации для алгоритма ЛАРД [5]. Данная модификация добавляет к шагу обновления информационных узлов (шаг 4) дополнительное условие: если после очередной итерации декодирования сообщение Li→j от информационного узла i к проверочному узлу j изменило знак, данное сообщение считается равным 0. Подробнее о данной модификации можно узнать в [5] и [6].
Сопутствующие материалы:
- Gallager R.G. Low-density parity-check codes // Cambridge, MA: M.I.T. Press. – 1963.
- Лихобабин Е.А. Упрощенные алгоритмы декодирования кодов с низкой плотностью проверок на четность, основанные на алгоритме распространения доверия // Цифровая обработка сигналов, № 3, 2013. С. 54-60.
- Ryan W.E., Lin S. Channel codes. Classical and modern. Cambridge: University Press, 2009.
- Chen J., Dholakia A., Eleftheriou E., Fossorier M., Hu X.-Y. Near optimal reduced-complexity decoding algorithms for LDPC codes // Proceedings IEEE International Symposium on Information Theory, Lausanne, Switzerland. – 2002, July.
- Likhobabin E., Vityazev V. Error floor reduction for LDPC codes using self-correction technique // Proceedings 24th Telecommunications Forum (TELFOR), Belgrade, Serbia. – 2016, November.
- V. Savin, “Self-corrected min-sum decoding of LDPC codes,” IEEE International symposium on Information Theory, 2008. pp. 146-150.
