Алгоритм декодирования LDPC MSA A-Min (АМС*)

Рассмотрим алгоритм, представляющий собой комбинацию алгоритмов ЛАРД и АМС – аппроксимированный алгоритм «минимум–сумма» (А–АМС, англ. approximate min–sum, A–Min), отличающийся от ЛАРД меньшим числом операций, выполняемых при расчете сообщений от проверочных узлов [16, 17]. В общем виде для ЛАРД эта операция имеет вид:

где – функция поиска минимального значения. Таким образом, на шаге об-новления сообщений из проверочного узла требуется найти всего два сообщения – первое для узла, сообщение от которого было минимальным, а второе – для всех остальных узлов.

Алгоритм АМС* использует ту же идеологию – в каждом проверочном узле рассчитывается всего два сообщения – одно для информационного узла, приславшего сообщение с минимальным весом, второе для всех остальных информационных узлов. Отличие заключается лишь в том, что вместо обычного минимума из двух аргументов используется оператор , в котором помимо операции поиска минимума используется еще и функция корректировки g(L₁, L₂)

В обобщенном виде этот алгоритм выглядит следующим образом.

1 шаг. Инициализация декодера. Для всех узлов i инициализируются значения L_i в зависимости от используемой модели канала связи:

где y_i - принятое из канала значение для символа i. Затем для всех i и j, для которых h_ij = 1, устанавливается L_i→j = L_i.

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

для всех остальных:

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

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

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

4 шаг. Вычисление апостериорных ЛОП. Для всех j=0,1...,N-1 вычислить:

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

.

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

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

Подобная модификация позволяет снизить вычислительные затраты на вычисление сообщений из проверочного узла для АРД-подобных алгоритмов с 3(d_c-1) до (d_c-1) операции ⊞. По эффективности этот алгоритм занимает промежуточное место между АРД-подобными алгоритмами и алгоритмом АМС.

В алгоритме используется оператор ⊞, а значит, при реализации может быть использована любая его интерпретация. Видно, что алгоритм сводится к поиску всего двух отсылаемых сообщений вместо d_c. Вычисление этих двух сообщений займет d_c-1 арифметических операций. Правомерность применения такого упрощения можно пояснить, рассмотрев работу алгоритмов АРД и АМС. Если при декодировании проверочного узла два или более входящих в проверочный узел сообщений недостоверны, то недостоверными будут все сообщения, исходящие из этого узла. Это свойство сохраняется и при введении рассматриваемой модификации. Если всего одно входящее в проверочный узел сообщение не верно, то исходящее сообщение для недостоверного информационного узла будет достоверным для всех трех декодеров. Как видно из описания рассматриваемого упрощения, в обоих рассмотренных случаях сообщение, отправляемое к самому ненадежному информационному узлу, всегда будет в точности таким же, как и для алгоритма АРД.

Обобщенный алгоритм МС*

В общем виде выражение для обновления проверочных узлов, для обобщенного алгоритма ОАМС*, примет вид:

Для узла с минимальной достоверностью:

для всех остальных:

Видно, что частный случай АМС*, при ⊞₁ требует меньших затрат на реализацию чем ОАМС*, поскольку вторая сумма, для оставшихся узлов, может быть найдена из первой, как это сделано выше. Что позволяет выполнить обновление проверочных узлов за (d_r-1) операции ⊞. В обобщенном алгоритме на это требуется (d_r-2) операции

и (d_r-1) операций , что больше чем для АМС*, но меньше, чем для классической схемы реализации АРД-подобных алгоритмов декодирования, а следовательно подобная реализация имеет право на жизнь и требует дополнительного исследования. Обобщенное представление алгоритма АМС* позволяет получить еще одну модификацию, не очевидную при анализе частного случая АМС*.

Модификация МОАМС (ma-min)

Основой алгоритма является тот факт, что необходимым условием для вычисления

является нахождение индекса проверки с минимальным весом i_min, а следовательно можно найти вес минимальной проверки всего за одно обращение к памяти. То есть в данном случае в качестве используется реализация ⊞₂, поскольку в этом случае есть ни что иное как оператор поиска минимального значения среди весов проверок.

Таким образом, получаем модификацию ОАМС* алгоритма, требующего (d_r-2) операции и 1 операцию обращения к памяти, что меньше чем для алгоритма АМС*. Обозначим его как МОАМС* - минимальный ОАМС*.