Алгоритм декодирования LDPC BF (АИБ)

Алгоритм с инверсией бита (АИБ, англ. bit–flip, BF) основывается на вычислении всех проверочных уравнений в матрице H с последующей инверсией тех бит в полученном кодовом слове, которые участвуют более чем в некотором заданном числе невыполненных проверок . Этот шаг повторяется с изменённым кодовым словом либо пока все проверки на четность не будут выполнены, либо пока не будет достигнуто некоторое максимальное число итераций.

На невыполненные проверочные уравнения указывают элементы синдрома s = yHT, где y – принятое кодовое слово, а их число для каждого кодового бита можно найти, используя следующее выражение:



причем умножение матриц выполняется над целыми числами, а не над двоичными. Вектор f называют профилем достоверности, а его элементы fj являются ничем иным, как достоверностями приема соответствующих бит, причем достоверность тем меньше, чем больше значение fj. При этом диапазон значений fj лежит в пределах [0, dc], и очевидно, что чем больше вес проверок для каждого из бит, тем более точно можно определить достоверность их приема.

Порог t – расчетная величина, которая должна быть выбрана таким образом, чтобы максимизировать эффективность декодирования при минимизации вычислительных затрат, и зависит от вероятности перехода в канале, а также dc и dr (где dr - Хэммингов вес строки ). В [1] приводится правило выбора оптимального порога для регулярных LDPC кодов при заданной вероятности перехода в канале. Рассчитывать порог в условиях изменяющихся характеристик канала не всегда оправданно, однако существует удобный, хоть и не оптимальный, способ выбора порога, эффективно адаптирующегося к изменению качества канала. Суть его сводится к тому, что инвертируются те биты, для которых число невыполненных проверок максимально, при этом возможны модификации с инверсией только одного бита или нескольких бит за итерацию.

Алгоритм ИБ можно представить в обобщённом виде следующим образом:

Шаг 1. Инициализация. Для всех информационных узлов i инициализировать αi,сообщения, хранящиеся в информационных узлах, жёсткими оценками принятых бит.

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


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

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


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

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


выполнить инверсию:

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



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

Представленный выше алгоритм ИБ представляет собой итеративный процесс. Вычисление проверочных сумм - двоичные операции. Однако, расчеты профилей достоверности и операции сравнения с порогом – это операции с целыми числами. Для АИБ порог t жестко не фиксирован и может меняться от итерации к итерации в зависимости от характеристик канала, что вынуждает выполнять операции с целыми числами для получения оценок достоверности бит и сравнения их с порогом t.

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

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