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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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