Повышение эффективности LDPC-декодирования при использовании дополнительной априорной информации

Введение

В 1948 году К. Шеннон [1] доказал, что ошибки приема, вызванные шумом канала, могут быть сведены к минимуму при использовании достаточно большой длины кодового слова (введением достаточной избыточности в передаваемые данные).

Коды LDPC (проверки четности с низкой плотностью) представляют собой семейство кодов с исправлением ошибок. Теория LDPCкодирования была разработана Р. Галлагером [2] в 60-х годах XX века, но сами коды широко не использовались почти два десятилетия. В 80-х годах прошлого века, при появлении вычислительных устройств достаточной производительности, подходы Р. Галлагера получили дальнейшее развитие [3].

Код LPDC – это код, матрица проверки на четность которого имеет низкую плотность [4], то есть количество единиц в матрице мало по сравнению с количеством нулей.

В настоящее время существует множество методик снижения битовой вероятности ошибок (BER) при фиксированном отношении E_b/N₀ (соотношение энергии бита к спектральной плотности мощности шума) при декодировании LDPC: оценка E_b/N₀ [5], дополнительные корректирующие оценки на шагах декодирования [6] и другие.

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

Кодирование и декодирование LDPC

Кодирование и декодирование LDPC предполагает выбор размеров исходного блока данных (K), кодовой скорости (K/N, где N – размер кодированного блока данных) и порождающей матрицы H размером [M × N], где M = N – K.

Особенности порождающих матриц, их классификация, свойства и методы генерации рассматриваться не будут, отметим лишь, что для процедуры кодирования требуется матрица G размером [K × N], которую можно получить соответствующими преобразованиями из матрицы H [7]. В стандартах на каналы связи или способы помехоустойчивого кодирования обычно приводятся обе матрицы.

Матрица G представляет собой совокупность двух матриц: единичной матрицы I размером [K × K] и матрицы W размером [M × K].

Кодирование

Процедура кодирования выглядит следующим образом: исходный вектор данных транспонируется и умножается на матрицу G, затем в получившейся матрице значения в каждом столбце суммируются по требуемому модулю поля. Результирующий массив размером N – кодированный блок данных.

Пусть in – массив исходных данных, out – закодированное сообщение. Тогда алгоритм LDPC-кодирования выглядит следующим образом (1):

out(i) = Σ_j=1:M in( j) * G( j, i), (1)

где i = 1:N.

Декодирование

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

Первые два типа применяются при отсутствии дополнительной информации (оценка отношения E_b/N₀, характеристики вероятностей символов и т.д.; предполагается, что ошибки в любом из принятых символов равновероятны) и наименее требовательны к вычислительным ресурсам. Применяются для каналов с относительно высоким отношением E_b/N₀ [7]. Последние три типа предполагают (но не требуют) наличия дополнительной информации о данных.

Алгоритмы декодирования последних трех типов

Пусть r – входной массив данных в формате логарифмических коэффициентов правдоподобия (LLR), A(i) – индексы ненулевых ячеек матрицы H столбца i, B(j) – индексы ненулевых ячеек матрицы H строки j.

Алгоритм сумм-произведений выглядит следующим образом:

1. Подготовительный шаг (формирование матрицы M):

M( j, i) = r(i), (2)
где i ∈ B( j), j ∈ A(i).

2. Горизонтальный шаг (вычисление матрицы E):

 (3)
где i ∈ B( j), j ∈ A(i).

3. Вертикальный шаг (вычисление вектора L и вектора z):

L(n) = r(n) + Σ _{i ∈ B( j), j ∈ A(i)} E( j, i), (4)

 (5)
где n = 1:N. 

4. Проверка завершения декодирования: если

H * z^T = 0H * z^T = 0, (6)
то декодирование закончено.

5. Переход на следующую итерацию (формирование матрицы M):

M( j, i) = r(n) + Σ _{j'∈ A(i), j'≠ j} E( j', i), (7)
где n = 1:N, i ∈ B( j), j ∈ A(i).

Шаги со 2-го по 5-й называются итерацией декодирования и повторяются необходимое количество раз. Потенциально количество итераций увеличивает вероятность правильного декодирования данных. Если в качестве выходного массива использовать массив z – то декодер будет с жестким выходом, если L – то с мягким.

Следует отметить, что шаг проверки завершения (6) может использоваться не на каждой итерации или не использоваться совсем, то есть декодер может работать в режиме с фиксированным количеством итераций.

Алгоритм минимума-сумм повторяет описанный алгоритм, за исключением горизонтального шага (вместо выражения (3) нужно использовать выражение (8)):

 (8)
где i ∈ B( j), j ∈ A(i).

Модифицированные алгоритмы минимума-сумм отличаются наличием корректирующих коэффициентов на различных шагах, которые зависят от оценки E_b/N₀, оценки мощности сигнала и т.п.

Формирование и обработка информационного пакета

Для пояснения предлагаемой методики необходимо кратко рассмотреть используемую сигнально-кодовую конструкцию. На рисунке 1 представлена структурная схема приемопередатчика.

Исходные данные на передатчике представляют собой массив размером 224 бита. В массив добавляются биты пакетной синхронизации следующим образом: между каждыми семью битами данных вставляется соответствующий по индексу бит 31-элементной псевдослучайной М-последовательности (ПСП_с).

[ Данные [0..6]] [ПСП_с [0]] [Данные [7:13]] [ПСП_с [1] ]...

В результате получается массив данных размером 255 бит, который дополняется одним зарезервированным битом. Получившийся массив поступает на блок LDPC-кодера с кодовой скоростью 1/2. В выходном пакете размером 512 бит контрольные биты размещаются в первой половине пакета, а биты данных – во второй.

Пакет поступает на блок расширения спектра псевдослучайной последовательностью, который по значению соответствующего бита, равному 0, формирует 31-элементную псевдослучайную м-последовательность (ПСП₀) при значении 1 – ПСП₁.

Следующим звеном выступает ФМ-2 модулятор, затем сигнал излучается в пространство.

На приемной стороне после антенно-фидерного устройства расположен квадратурный демодулятор, выходом которого являются сигналы I_c(t) и Q_c(t).

Сигналы I_c(t) и Q_c(t) поступают на четыре параллельно расположенных коррелятора: коррелятор ПСП₀ для I_c(t) с выходом I_c0(t), ПСП₀ для Q_c(t) с выходом Q_c0(t), ПСП₁ для I_c(t) с выходом I_c1(t) и ПСП₁ для Q_c(t) с выходом Q_c1(t).

На следующем шаге рассчитываются магнитуды по псевдоканалам нуля (MAG₀ (t)) (9) и единицы (MAG₁ (t)) (10), а также синхросигнал (SYNC(t)) как их сумма (11):

MAG₀ (t) = I²_c0(t) + Q²_c0(t), (9)

MAG₁ (t) = I²_c1(t) + Q²_c1(t), (10)

SYNC(t) = MAG₀ (t) + MAG₁ (t). (11)

Следующий блок обработки – предварительный синхронизатор, который, используя сигнал SYNC(t) и обладая информацией о частоте следования данных, занимается поиском приблизительного интервала по критериям максимума сигнала SYNC(t) на известном интервале (длительность ПСП₀ или ПСП₁), а также по критерию регулярности следования этих максимумов. Вне зависимости от качества синхронизации на текущий момент синхронизатор в моменты максимума сигнала SYNC(t) выставляет сигнал валидности для сигналов MAG₀ (t) и MAG₁ (t).

По сигналам MAG₀ (t) и MAG₁ (t) рассчитывается сигнал LLRs(t) (12), который затем поступает на блок пакетной синхронизации.

LLRs(t) = log(MAG₀ (t)) – log(MAG₁ (t)). (12)

Блок пакетной синхронизации имеет память глубиной 512 ячеек для хранения входных LLR. При поступлении каждого нового отчета сигнала LLRs(t) данные записываются в конец памяти, при этом все находящиеся в памяти данные сдвигаются на одну ячейку, отсчет из младшей ячейки выбрасывается. Для текущего состояния памяти выполняется проверка на соответствие момента времени окончания приема пакета с использованием коррелятора ПСП_c (анализируются соответствующие биты предполагаемого пакета). Критерием детектирования пакета является превышение пиком корреляции ПСП_c порога, рассчитываемого по предыдущим пикам.

В случае успешного детектирования пакета в места расположения битов пакетной синхронизации пакета выставляются максимальные значения LLR, соответствующие битам ПСП_c. Таким образом, знание на приемнике ПСП_c используется в качестве априорной информации.

Принятый пакет поступает на обработку в LDPC-декодер, работающий по алгоритму минимума-сумм с шагом проверки завершения, описанным выше. В качестве матриц H и соответствующей ей матрицы G для процедуры кодирования/декодирования используются матрицы из экспериментального стандарта CCSDS 231.0-O-x.x для системы космической связи [8].

Оценка эффективности LDPC-декодирования

Оценка эффективности LDPC-декодирования проводилась методом моделирования в среде Matlab.

На рисунке 2 представлена зависимость BER от E_b/N₀, на рисунке 3 – зависимость требуемого количества итераций для полного восстановления (если это возможно) от E_b/N₀ (максимальное количество итераций – 50). В качестве канала используется канал с аддитивным белым гауссовским шумом. Размер выборки случайных данных – 10e5 бит для каждого значения E_b/N₀.

В первом случае (синяя пунктирная линия на рисунках 2 и 3) значение LLR в местах расположения битов пакетной синхронизации не изменялись, во втором (красная линия на рисунках 2 и 3) — изменялись по описанному выше алгоритму.

Из результатов моделирования следует, что корректировка LLR битов пакетной синхронизации, с учетом априорного знания их значений (ПСП_c), позволяет уменьшить количество итераций (до 1,5 раз) при декодировании и BER (до 7 раз) для диапазона E_b/N₀ от –2,6 до 0 дБ.

Вывод

Предложенная методика корректировки LLR битов, основанная на априорном знании бит пакетной синхронизации для представленной сигнально-кодовой конструкции, позволяет повысить эффективность LDPCдекодирования (количество итераций для достижения аналогичного BER до 1,5 раза меньше; BER до 7 раз меньше для одинакового количества итераций).