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

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

И под оператором min* понимается поиск минимума, и, получаем, что для подсчета сообщений из проверочного узла требуется найти всего два сообщения – первое для узла, сообщение от которого было минимальным, а второе – будет одинаковым для всех остальных узлов.

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

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

1 шаг. Инициализация. Для всех узлов i инициализировать значения Li в зависимости от используемой модели канала связи. Затем для всех i и j, для которых hij = 1, устанавливается Li→j = Li.

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

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

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

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

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

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

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

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

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

Если

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

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

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

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

  1. Витязев В.В., Лихобабин Е.А. Алгоритмы декодирования кодов с низкой плотностью проверок на четность, основанные на структуре алгоритма «минимум-сумма» // Успехи современной радиоэлектроники. – 2014. – №6. – С. 26-35.
  2. Vityazev V., Likhobabin E., Ustinova E., “Min-Sum Algorithm-Structure Based Decoding Algorithms for LDPC Codes”, 3rd Mediterrian Conference on Embedded Computing, Budva, Montenegro. –2014, June. – pp. 256-259.
  3. Jones C., Valles E., Smith M., Villasenor J. Approximate-min* constraint node updating for LDPC code decoding // IEEE Military Communication Conference. – 2003, October. – pp. 157-162.
  4. Витязев В.В., Лихобабин Е.А. Алгоритмы декодирования кодов с низкой плотностью проверок на четность, основанные на алгоритме «минимум-сумма» // Труды РНТОРЕС имени А.С.Попова. Серия: Цифровая обработка сигналов и ее применение – М.Выпуск XVI-1. – 2014. – С.117-121.