Алгоритм декодирования LDPC APP (ААВ)

Алгоритм вычисления апостериорных вероятностей (алгоритм АВ, ААВ, aposteriory probability, APP) получил свое название благодаря шагу обновления битовых узлов – если в других АРД-подобных алгоритмах (АРД – алгоритм распространения доверия) на этом шаге вычислялось сообщение (сумма ЛОП (ЛОП – логарифмическое отношение правдоподобия) – за исключением ЛОП исходящего из рассматриваемого узла), то в этом алгоритме сразу осуществляется расчет апостериорных вероятностей, и именно они используются для дальнейших расчетов. Алгоритм ААВ можно рассматривать как дальнейшее упрощение алгоритма АМС (алгоритм минимальной суммы). ААВ отличается от алгоритма АМС шагом обновления битовых узлов. Здесь вычисляется только одно исходящее сообщение от битового узла i , вместо dc - Хэммингова веса столбца (Li вместо Li→j), как это было во всех алгоритмах, основанных на алгоритме АСП (алгоритм сумма-произведение). Выражение для подсчета исходящих из информационного узла сообщений имеет вид:

где β – модуль Li→j.

Рисунок 1. Обновление битовых узлов в алгоритме ААВ

Введение подобного упрощения приводит к значительному ухудшению эффективности декодирования, с другой стороны это позволяет существенно снизить вычислительные затраты и затраты памяти на реализацию алгоритма. В целом алгоритм AАВ можно рассматривать как модификацию алгоритма ИБ (инверсия бита) для канала АБГШ (аддитивный белый гауссовский шум). Сходство с алгоритмом ИБ проявляется также и в работе алгоритма – как и алгоритм ИБ, он более эффективен при декодировании кодов с достаточно большой степенью проверочных узлов.

Обобщенная форма записи алгоритма имеет вид:

Шаг 1. Инициализация. Для всех информационных узлов i инициализировать значения Li по формуле:

где y i - принятое из канала значение для символа i. Затем для всех i и j, для которых h ij =1, устанавливается L(i→j)= Li.

Шаг 2. Обновление проверочных узлов. Для всех проверочных узлов CN вычислить исходящие сообщения Lj→i:

и передать их соответствующим информационным узлам VN.

Шаг 3. Обновление битовых узлов. Вычислить сообщения Lj→i, исходящие от информационных узлов VN:

и передать их соответствующим проверочным узлам.

Шаг 4. Вычисление апостериорных ЛОП.

Шаг 5. Получение жёстких решений. Для всех i = 0, 1, …, N-1 найти жесткие решения:

Шаг 6. Проверка правильности декодирования. Вычислить синдром:

где H - проверочная матрица LDPC кода. Если s = 0 или число итераций достигло максимума – вычисления прекращаются, а полученное жесткое решение считается результатом декодирования, в противном случае вычисления продолжаются с шага 2.

Также, как и к другим алгоритмам декодирования, к алгоритму ААВ можно применить модификацию с самокоррекцией. Основная идея данной модификации заключается в том, что все сообщения, сменившие свой знак между двумя очередными итерациями декодирования, приравниваются к нулю. Тогда шаг 3 выглядит следующим образом:

Шаг 3. Обновление битовых узлов. Вычислить сообщения Lj→i, исходящие от информационных узлов VN и численно равные апостериорным ЛОП:

где:

Сопутствующие материалы:

  1. Gallager R.G. Low-density parity-check codes // Cambridge, MA: M.I.T. Press. – 1963.
  2. Лихобабин Е.А. Упрощенные алгоритмы декодирования кодов с низкой плотностью проверок на четность, основанные на алгоритме распространения доверия // Цифровая обработка сигналов, № 3, 2013. С. 74-81.