Алгоритмы декодирования LDPC-кодов
Декодирование – это процедура поиска и исправления ошибки, возникших в кодовом слове при передаче по каналу связи, или поиск кодового слова по вектору, принятому из канала. В зависимости от вида решений в демодуляторе различают мягкое и жесткое декодирование.
Применение мягких решений несколько усложняет декодер, но позволяет получить дополнительный выигрыш от декодирования – порядка нескольких децибел.
Алгоритм ”Сумма произведений”.
Декодирование по максимуму правдоподобия, на символ или кодовое слово обобщенного линейного блочного кода, в общем, непростая задача.
Тем не менее, Галлагер предложил три субоптимальных итерационных алгоритма декодирования для LDPC кодов, которые используют разреженность проверочной матрицы этого кода. Два из них являются простыми и основаны на алгоритмах жесткого решения и техники побитовой обработки, тогда как третий является более точным алгоритмом, который основан на итерационном обмене действительными надежностями бит кодового слова .Эти алгоритмы широко известны как алгоритмы Галлагера А, B, и C.
Все эти алгоритмы обладают привлекательным свойством - возможностью применения графа Таннера для декодирования. В частности, они характеризуются тем, что узлы, как переменных, так и проверочные, выступают в качестве процессоров обмена вещественными сообщениями по кодовому графу. Вся обработка производится локально, т. е. для каждого узла, она основана только на доступных ему сообщениях. Сообщения представляют надежность значения битов кодового слова, в частности, они представляют оценку вероятности того, что каждый конкретный бит кодового слова равен "1".
Алгоритм Галлагера С, в настоящее время, введен с акцентом на его реализацию в логарифмической области. Учитывая бинарность случайной величины X, принимающей значения в интервале {0,1}, её отношение правдоподобия λx определяется как
 (4.3.1)
и соответствующие логарифмическое отношение правдоподобия:
На каждой итерации алгоритма декодирования: во-первых, каждый узел переменной вычисляет выходное сообщение для каждой соединенной с ним вершиной (i), и, затем узел проверок вычисляет выходное сообщение для каждой подключенной к нему вершины (ii). Порядок вычисления сообщения, как правило, показывают графиком.
Рисунок 4.3.1 - Узел переменной: величины входящие в расчет j – того выхода [4]
На рисунке 4.3.1, показана степень dv узла переменных и показаны входные и выходные сообщения. Можно отметить, что существует вход, соединенный с узлом и чье значение отмечено как m0, который представляет входное значение надежности, связанное с соответствующим битом узла переменной, выраженной логарифмом правдоподобия. Это значение входной надежности, как правило, рассчитываются на основе наблюдений за каналом [6].
Алгоритм декодирования может быть получен на основании вероятности домена, и как следствие в результате вычисления логарифма отношения правдоподобия (LLR) домена. Сообщение на выходе узла переменных это вероятность того, что соответствующий бит X кодового слова равен "1", из всего множества независимых наблюдений относительно бита. Предположим, что есть dv независимых наблюдений ξ1, . . . ,ξdv. Тогда отношение вероятностей наблюдений будет выглядеть:
 (4.3.2)
Вероятность равенства Х = 0 в данных наблюдениях
 (4.3.3)
и соответствующее отношение правдоподобия
 (4.3.4)
которое предполагает P(X = 0) = P(X = 1) = 1/2, в
 (3.3.2)
где  .
Алгоритм декодирования узла переменных, может быть разработан в области логарифма правдоподобия. Каждый узел переменной степени-dv, как показано на рисунке 3.3.1, вычисляет dv выходных сообщений, следовательно:
 (4.3.5)
где mvj - j – тое выходное сообщение и mvi - i – тое входное сообщение от узла проверки. Другими словами узел переменных обрабатывает все сообщения на его входе как независимые данные: dv – один от узлов проверок и один m0, соответствует отношению правдоподобия, ассоциирующееся с первичными данными.
Можно заметить, что сумма явно исключает сообщения, приходящее от ребра, выходное сообщение которого было вычислено.
Рисунок 4.3.2 - Узел проверки: показаны величины, входящие в расчет
j – ого выходного сообщения [4]
На рисунке 4.3.2 показан общий узел проверки степени - dc. Проверочный узел представляет разбиение на биты кодового слова, связанных с узлами переменных, соединенных с ним. Это ограничение выражается в соответствующей строке проверочной матрицы: сумма бит кодового слова по модулю 2, связанных с проверочным узлом, равна 0. В этом случае, проблема заключается в следующем:
 (4.3.6)
Для данных вероятностей, соответствующих dc−1 битам из dc бит, соединенных с узлом проверки четности, вычислим вероятность P0, что их сумма по модулю 2 равна 0 (мы знаем, что сумма всех битов dc по модулю 2 равна 0 ). Предположим что все данные наблюдений, ведущих к вычислению P(X1 = 1), . . . , P(Xdc−1 = 1) независимы, тогда
 (4.3.7)
где "х: четная сумма" обозначает все биты векторов х длины dc-1, сумма которых является четным числом, то есть, х содержит четное число единиц. Вычисление этой величины может быть выполнено по следующим принципам.
Во-первых, рассмотрим следующий многочлен q(t):
 (4.3.8)
Заметим, что коэффициент αi задается как
 (4.3.9)
Другими словами, αi - это вероятность наличия i единиц и dc-1-i нулей среди dc-1 бит. Заметим теперь, что q(1) это сумма всех коэффициентов и q(−1) сумма всех коэффициентов, где все нечетные коэффициенты изменили знак. Следовательно
 (4.3.10)
равна удвоенной сумме всех четных коэффициентов, т. е. удвоенной вероятности приема четного числа единиц. Как следствие,
 (4.3.11)
Соответствующее логарифмическое отношение правдоподобия, есть
 (4.3.12)
где
Рассмотрим проверочный узел на рисунке 4.3.2, чтобы вычислить общее выходное сообщение. Каждый проверочный узел выполняет следующие вычисления:
 (4.3.13)
-где mcj является j-тым выходным сообщением и mci это i-тое входное сообщение приходящее от узлов переменных. Как и в случае узла переменных, сообщение приходящее от j-ого ребра не используется для вычисления исходящего сообщения в j-том ребре. Сообщения могут быть интерпретированы как LLR битов связанных с узлами переменных по направлению из которых сообщение направляется. В конце процесса декодирования, каждый узел переменных вычисляет выходное значение надежности следующим образом:
 , (4.3.16)
где dv- степень узла.
Иными словами, выходное значение надежности бит кодового слова является суммой всех сообщений, направленных на соответствующий узел переменных. Из (3.3.1), LLR, относительно двоичной случайной величины, может быть непосредственно использована для вычисления MAP (максимума апостериорной вероятности) оценки случайной величины. В самом деле, если знак LLRs положительный, вероятность того, что случайная величина равна 0 больше, чем вероятность того, что случайная величина равна 1. И наоборот, если знак LLRs отрицательный, вероятность случайной величины быть равной 0 меньше, чем вероятность случайной величины быть равной 1.
Таким образом, знаки LLRs в (4.3.5) необходимые для принятия решения о битах кодового слова. Подводя итог, алгоритм декодирования Галлагера C включает в себя следующие шаги:
1. Вычисление всех значений для надежности символов в кодовом слове. Эти значения соответствуют, для каждого узла переменных, значению m0 на рисунке 4.3.2.
2. Установить равным 0 все сообщения, приходящие из проверочных узлов.
3. Вычислить выходные сообщения переменных узлов с помощью (3.1.3).
4. Передача сообщений на проверочные узлы.
5. Вычислить сообщения проверочных узлов, используя (4.3.4).
6. Передача сообщений на переменные узлы.
7. Проверка того, что выполнен критерий остановки декодирования, описанный в следующем пункте. Если нет, переход к шагу 2.
8. Вычислить конечные значения надежности, используя (4.3.5).
Критерий остановки декодирования может быть основан на нескольких возможных событиях. Два самых общих это:
- Декодируемые символы формируют действительное кодовое слово (выполняются все проверки)
- Достигается заданное число итераций.
Было обнаружено, что алгоритм Галлагера С обладает интересным свойством – он показывает очень малую вероятность необнаружения ошибочного результата декодирования, т.е. когда процесс декодирования не удается, декодер фиксирует случай необнаружения ошибки. В действительности, в отличии от турбо-кодов, алгоритм BP для LDPC кодов оперирует битами кодового слова, а не информационными битами. Это легко заметить при наблюдении, информационные биты и биты проверок обрабатываются одинаковым способом. Кажется очевидным, что всегда, когда возникает ошибка декодирования, получаемая последовательность бит не является кодовым словом, в том смысле, что обычно не выполняется соотношение (4.2).
В описанном выше алгоритме структура передачи сообщений жестко фиксирована – сначала свои сообщения формирует каждый узел переменных, затем эти сообщения посылаются узлам проверок, которые в свою очередь вычисляют сообщения для своих выходов. Все полученные сообщения затем передаются обратно узлам переменных. Эта схема оптимальна при применении древовидных двудольных графов, т.е. графов без циклов. Если граф имеет циклы, то алгоритм становится подоптимальным и может иметь смысл в адаптации другой схемы планирования вычислений. Другая мотивация для использования других принципов планирования вычислений, в отличие от алгоритма Галлагера, это улучшение вычислительной и реализационной эффективности схем, реализующих алгоритм LDPC.
|
