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

Помимо модификаций АИБ, изменяющих процесс расчета сообще­ний от проверочных узлов, существует ряд модификаций, изме­няющих процесс расчета апостериорной вероятности для принятых бит. Одной из наиболее популярных модификаций является алгоритм инвер­сии бита с градиентным спуском (градиентный алгоритм инверсии бита, АИБГС, ГАИБ, англ. gradient descent bit-flipping, GDBF). Основной идеей данного алгоритма является то, что при расчете апостериорной вероятности бита учитываются не только сообщения от соединённых с ним проверочных узлов (как это происходит в АИБ), но и принятое из канала значение Li со знаком α i :



В обобщенном виде ГАИБ можно представить в виде следующих шагов.

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

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



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

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



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

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


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


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



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

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

  1. Zhang, J.A Modified weighted bit-flipping decoding of low­-density parity-check codes / J. Zhang, M. P. C. Fossorier //IEEE Communications Letters. — 2004. — Т. 8, No 3. — С. 165–167.
  2. Nouh, A. Bootstrap decoding of low-density parity-check codes /A Nouh, A. H. Banihashemi //IEEE Communications Letters. — 2002.— Т. 6, No 9. — С. 391–393.23.
  3. Gradient Descent-Bit Flipping Algorithms for Decoding LDPCCodes / Tadashi Wadayama, Masayuki Yagita, Yuuki Funahashi и др. //CoRR. — 2007. — Т. 0711.0261.
  4. Gallager R.G. Low-density parity-check codes // Cambridge, MA: M.I.T. Press. – 1963.