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

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



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

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

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



и передать их соответствующим информационным узлам 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.