Графические модели и декодирование методом передачи сообщений

 

Графические модели широко используются во многих классических многомерных вероятностных системах, изучаются в таких областях, как статистика, теория информации, распознавание образов и теория кодирования.

Одним из важных шагов в графическом представлении кодов стало введение фактор графов [29], которые сделали процесс анализа гораздо яснее. Концепция фактор графов является достаточно общей. Фактор граф помогает разложить многомерную функцию на более простые функции. Например, на рис. 2.1 показаны фактор графы следующего разложения:

На рис. 2.1 переменные показаны кружками, а функции квадратами. Функция является смежной для всех её аргументов.

PDF-функция (probability density function - совместная функция плотности вероятности) часто представляется в виде местных PDF-функций, каждая из которых является функцией от многих переменных. Таким образом, фактор граф является графической моделью, которая более удобна для решения проблем, имеющих статистическую сторону.

 

Рис. 2.1. Фактор граф, представляющий разложение равенства (2.1).

 

Когда фактор граф циклически свободен, то есть, когда есть более чем один путь между каждой парой узлов графа, используя алгоритм sum-product [29], все предельные PDF-функции могут быть вычислены. Алгоритм sum-product эквивалентен алгоритму Перла в общих байесовских сетях [29]. Он сводит задачу маргинализации глобальной функции на множество локальных операций передачи сообщений.

Термин «передающий сообщения декодер» берет свое название от способа передачи сообщений алгоритма sum-product. Важность декодеров, передающих сообщения в том, что их декодирующая сложность растет линейно с длиной кода. Следует отметить, что декодирование методом передачи сообщений является неоптимальным, если основной фактор граф имеет циклы. Тем не менее, использование этого алгоритма на графах с одним или более циклами в контексте кодирования на удивление хорошо. Похоже, что хорошие показатели являются результатом большой длины большинства циклов в графе, в результате чего зависимость сообщений распадается [30].

В последних работах, таких как [23,31-34] исследуется влияние циклов на работоспособность этого алгоритма. В большинстве случаев анализа кодов, определённых на графах, тем не менее, эффект от циклов игнорируется.

Рис. 2.2. Двудольный граф, представляющий собой проверочной код.

 

LDPC коды: структура

 

LDPC код является линейным блочным кодом и, поэтому имеет проверочную матрицу. Существенным отличием LDPC кодов от обычных линейных кодов является матрица проверки четности, в которой число ненулевых элементов на много меньше, чем общее число записей, которые могут быть найдены для неё.

Графическое представление LDPC кодов настолько популярно, что большинство людей думает и говорит о LDPC кодах с точки зрения структуры их фактор графов. Как упоминалось ранее, графическое представление линейных кодов началось с графов Таннера [4]. Здесь мы сосредоточимся на фактор графах, в связи с их более общим характером происхождения.

Фактор граф всегда является двудольным графом, вершины которого разбиты на переменные узлы и функции (проверки) узлов [29,35]. Мы считаем удобным взять двудольный граф и показать, как двоичный линейный код может быть из него сформирован.

Рассмотрим двудольный граф Q с n левыми узлами (назовем их переменными узлами) и r правыми узлами (назовем их проверочными узлами) и E дугами. На Рис. 2.2 показан пример такого двудольного графа. Обратите внимание, что на этом рисунке переменные узлы показаны кружками, а проверочные узлы - квадратами, так же, как и для всех фактор графов.

Переменный узел является бинарной переменной из алфавита {0,1}, а проверочный узел является ограничительным для соседних переменных узлов, т.е.

где есть множество всех «соседей» и - суммирование по модулю два.

В результате получается двоичный линейный код длины и размерности с равенством тогда и только тогда, когда все проверочные ограничения линейно независимы. Проверочной матрицей этого кода является матрица смежности графа т. е. , входящие в равно 1, тогда и только тогда, когда ( -ый узел проверки) подключен к ( -ому переменному узлу).

LDPC коды могут быть расширены до , рассматривая множество ненулевых весов для рёбер . Проверочная матрица в этом случае формируется с помощью множества весов. Другими словами . В оставшейся части данной работы мы предполагаем, что коды – двоичные, если не указано иное.

Это легко объясняется, если предположить, что любой двудольный граф приводит к линейному коду. В случае LDPC кодов число E дуг в фактор графе, сравнимое с количеством дуг в построенном случайно двудольном графе, то есть двудольном графе, который с вероятностью имеет грань между левой вершиной и правой вершиной очень мало. Как мы увидим позже, для LDPC кода с фиксированной скоростью , число ребер порядка , а в случайно построенном двудольном графе дуг. Таким образом, с ростом , величина уменьшается, что приводит к «редкому» коду.

LDPC коды, в зависимости от их структуры, могут быть классифицированы, как равномерные или неравномерные. Равномерные коды имеют переменные узлы с фиксированными степенями и проверочные узлы с фиксированными степенями. Обозначая степень переменных узлов, как и степень проверочных узлов, как получим:

Таким образом, скорость кода R может быть вычислена, как

Если строки линейно независимы, то . В ряде работ величина называется кодируемой скоростью [12], но обычно возможная линейная зависимость между строками игнорируется и кодируемая скорость считается равной действительной.

Теперь рассмотрим ансамбль равномерных LDPC кодов с переменной степенью проверочной степенью и длиной . Если достаточно велико, обычное поведение этого ансамбля почти во всех случаях концентрируется вокруг ожидаемого поведения [12]. Следовательно, равномерные LDPC коды относятся к своим переменным и проверочным степеням и их длинам. Когда вероятность ошибочного декодирования и характеристики бесконечно длинные (или достаточно длинные) на равномерные LDPC коды следует обратить внимание, они будут представлены только степенью их переменного и проверочного узла. Например, (3, 6) LDPC код является кодом с переменным узлом степени 3 и проверочным узлом степени 6. Кодируемая скорость этого кода из (2.3) 1/2.

Хотя показатели равномерных LDPC кодов близки к пропускной способности, у них имеется большой интервал от пропускной способности, в отличие от турбо кодов. Основное преимущество равномерных LDPC коды над турбо кодами заключается в их лучшей, так называемой, "ошибке нижнего уровня". Из Рис. 1.2 видно, что, по сравнению с низкими SNR, BER кривая турбо кодов для умеренных и высоких SNR имеет меньший наклон. Это явление называется "ошибкой нижнего уровня". Рис. 3 в [36] отображает качественное поведение BER кривой относительно для турбо кодов и классифицирует различные участки кривой BER. Явление "ошибки нижнего уровня" является фундаментальной особенностью из-за низкого свободного расстояния турбо кодов [3]. Таким образом, в турбо кодах будут "ошибки нижнего уровня" даже при оптимальном декодировании. LDPC коды, однако, как замечено в [9], а также можно увидеть на рис. 1.2 имеют лучшие показатели "ошибки нижнего уровня". Кроме того, [37] показано, что LDPC коды могут достичь предела Шеннона при оптимальном декодировании.

LDPC коды стали более привлекательными, когда Люби с коллегами показал, что разрыв пропускной способности может быть сокращен с помощью неравномерных LDPC кодов [17]. LDPC код называется неравномерным, если на его фактор графе не все переменные (и/или проверочные) узлы имеют равные степени. Тщательно кодируя неравномерность графа, можно получить коды с показателями, очень близкими к пропускной способности [13,17,21,28].

Ансамбль неравномерных LDPC кодов определяется его переменным распределением степеней дуг и его проверочным распределением степеней дуг , где обозначает долю дуг, падающую на переменные узлы степени , и обозначает долю дуг, падающую на проверочные узлы степени . Другой способ описания того же ансамбля кодов заключается в представлении последовательностей и с помощью их порождающих многочленов и . Оба варианта описаны в [17] и были использованы в литературе впоследствии. Обратите внимание, что граф характеризуется с точки зрения доли дуг каждой ступени, а не узлов каждой степени. Позже мы увидим, что это представление является более удобным. В оставшейся части данной работы под переменными (проверочными) степенями распределения мы будем иметь в виду переменные (проверочные) степени распределения дуг.

На подобие равномерным кодам, в [12] показано, что обычное поведение ансамбля неравномерных кодов, почти во всех случаях сосредоточено вокруг ожидаемого поведения, когда код достаточно велик. Кроме того, ожидаемое поведение сводится к случаю без циклов [12].

Учитывая степень распределения LDPC кода и число дуг , легко заметить, что число переменных узлов

и число проверочных узлов

 

Поэтому кодируемая скорость кода будет

или, что эквивалентно

Поиск “хорошего” асимптотически длинного семейства неравномерных кодов эквивалентен поиску “хорошей” степени распределения. Очевидно, что для различных приложений, различные атрибуты будут являться предпочтительными. Задача поиска степени распределения, которая в результате даёт семейство кодов с определёнными нужными свойствами, не является тривиальной задачей и является одной из основных задач данной работы. Мы попытаемся сформулировать представление семейства кодов с точки зрения степени его распределения в простой форме, чтобы обеспечить максимальную гибкость на стадии кодирования, и в то же время избежать излишнего упрощения, чтобы наши полученные результаты в итоге были близки к реальным.

 

LDPC коды: декодирование

 

Из (2.4) видно, что, фиксируя переменную степень распределения кода, число дуг в фактор графе такого кода пропорционально n. Это важное свойство LDPC кодов, которое создает их декодирующую сложность линейно с длиной кода, с учетом фиксированного числа итераций. Это связано с тем, что декодирование производится путем передачи сообщения по дугам графа, следовательно, сложность одной итерации будет порядка Е.

Есть много различных алгоритмов передачи сообщений для LDPC кодов. Целью данного раздела является представление некоторых из этих алгоритмов декодирования. Мы начнем с алгоритма sum–product и, используя интерпретацию декодирования методом sum-product, нам станут понятны другие алгоритмы декодирования.

 

Алгоритм sum-product

 

В приложение A описывается алгоритм sum-product в общем виде. Рассматривая основную цель этой главы, мы ориентируемся на упрощенный случай, в котором переменные узлы имеют двоичное значение и функциональные узлы ограничены контролем четности. Не вдаваясь в детали, определим характер сообщений и упрощенные правила их корректировки. Затем мы используем это, чтобы сформировать объяснение декодирования LDPC кодов методом передачи сообщений.

Для двоичных переменных узлов сообщение которое является функцией соседнего переменного узла имеет только два значения, . Когда сообщения являются условными PMF-функциями (probability mass functions – функции вероятностных мер), , поэтому передача только одного из сообщений эквивалентна передаче функции . Равнозначно мы можем передавать комбинации такие, что . Последняя величина или в случае PMF-функций известна, как отношение LLR (log likelihood ratio - логарифмическое правдоподобие) и наиболее распространенным типом сообщения, используемым в литературе. Причина заключается в том, что здесь методы корректировки просты и в компьютерной реализации это можно представить вероятностными значениями, которые очень близки к нулю или очень близки к единице, не вызывая ошибки в погрешности. Здесь мы только приводим методы корректировки, когда сообщения LLR. Для сообщений, взамен µ, мы используем m, чтобы различать общие методы передачи сообщений и методы передачи сообщений LLR. Методы корректировки для других видов сообщений можно найти в [29]. Обратите внимание, что сообщение уже не функция, а действительное число.

Правило корректировки узла контроля четности :

где представляет собой LLR сообщение, отправленное из узла в узел b, и представляет собой представляет собой совокупность всех соседних узлов в графе.

Правило корректировки переменного узла :

где является внутренним сообщением для переменного узла . Внутреннее сообщение вычисляется из наблюдаемого канала и без использования избыточности в коде. Декодируемые сообщения, как правило, посылаются как внешние сообщения. Внешние сообщения соответствуют структуре кода и изменяются итерация за итерацией. Успешное декодирование улучшает качество внешних сообщений итерация за итерацией.

На рис. 2.3 показан фактор граф LDPC кода в декодере. Здесь показаны внутренние и внешние сообщения на переменный узел . Здесь также изображено, что исходящие сообщения на дугу , соединенные с узлом (в данном случае ), зависят от всех входящих сообщений на этот узел, кроме входящих сообщений на . Это свойство является одним из основных направлений анализа LDPC кодов. На рис. 2.3 функциональные узлы на левой стороне соответствуют каналу. Эти функциональные узлы соединяют бит передатчика с тем же битом приемника. В зависимости от типа канала и модели шума, эти функции могут быть вычислены.

MAP решение (примерное MAP решение соответствует наличию циклов) для переменного узла может быть сделано на основании следующего метода решения:

Если , то обе и имеют одинаковые вероятности и решение может быть осуществлено случайно.

В оставшейся части этой работы, когда мы ссылаемся на алгоритм sum-product, мы имеем в виду упрощенный случай для двоичного кода с контролем четности, если не указано иное.

Рис. 2.3. Внутренние и внешние сообщения на переменном узле А также внутренние сообщения, которые влияют на исходящее сообщение на переменном узле .