Алгоритм декодирования кодов с малой плотностью проверок на четность с большим распараллеливанием

X КОДИРОВАНИЕ И ПЕРЕДАЧА ИНФОРМАЦИИ

УДК 004.032.2: 004.932

АЛГОРИТМ ДЕКОДИРОВАНИЯ КОДОВ С МАЛОЙ ПЛОТНОСТЬЮ ПРОВЕРОК НА ЧЕТНОСТЬ С БОЛЬШИМ РАСПАРАЛЛЕЛИВАНИЕМ

Ф. И. Иванов,

аспирант И. В. Жилин, аспирант В. В. Зяблов,

доктор техн. наук, профессор

Институт проблем передачи информации им. А. А. Харкевича, г. Москва

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

Ключевые слова — МПП-код, векторный декодер, матрица перестановок.

Введение

Двоичные коды с малой плотностью проверок на четность (МПП-коды) были предложены Гал-лагером [1]. Данные линейные блочные коды задаются с помощью проверочной матрицы H, характеризуемой относительно малым числом единиц в строках и столбцах. Часто проверочную матрицу H МПП-кода удобно представлять в виде графа Таннера [2].

Также в работе [1] был предложен итеративный алгоритм декодирования «распространения доверия» (belief propagation). Данный алгоритм основан на декодировании по апостериорным вероятностям на выходе канала и требует порядка O(nlog(n)) операций, где n — длина кода.

Помимо случайных МПП-кодов нередко используют алгебраические МПП-коды, основанные на матрицах перестановок специального вида [3-7].

В данной работе рассмотрена модификация алгоритма декодирования «распространения доверия» для случая, когда проверочная матрица H кода с малой плотностью проверок на четность состоит из произвольных матриц перестановок. Основное преимущество данного алгоритма заключается в том, что он имеет параллельную реализацию, работая не с отдельными символами, а с векторами.

Структура проверочной матрицы случайного МПП-кода

Для лучшего понимания изложенного в статье материала мы приведем алгоритм построения проверочной матрицы случайного МПП-кода.

В 1960 г. Р. Галлагер предложил алгоритм генерации проверочной матрицы H случайного кода с малой плотностью проверок на четность [1]. Ниже приведен алгоритм построения этой матрицы.

Пусть H — проверочная матрица кода проверки на четность длины я0:

Но = (1 1 ... 1).

(_____у_____/

«о

Запишем блочно-диагональную матрицу Hm с т проверочными матрицами ^ на главной диагонали:

0 ... 0 '

Но  :

•. 0 ’

... 0 Но,

----V--------J

т

где т достаточно велико. Так как размер матрицы ^ равен 1 х По, то размер матрицы Hm - т х тп^.

Hm

(Ho

О

Пусть — случайная перестановка столбцов

матрицы Hm. Тогда матрица ^ составленная из l > 2 таких перестановок в качестве слоев:

" л1(Нт )'

H

ж1

является разреженной проверочной матрицей размера ml х mn0), которая определяет ансамбль МПП-кодов Галлагера длины п = mn0y Обозначим этот ансамбль 6с(1, По, m).

Элементы ансамбля 6G(l, По, m) получаются путем независимого выбора без возвращений перестановок I = 1...1. Все перестановки выбираются равновероятно, таким образом, на ансамбле 6G(l, По, m) задано равномерное распределение вероятностей.

Проверочная матрица H МПП-кода Галлаге-ра, построенная указанным выше способом, содержит l единиц в каждом столбце и По единиц в каждой строке. Такие кодовые конструкции назовем регулярными (I, По)-кодами.

Нижняя оценка на скорость Я кода из 6G(l, п0, та) определяется формулой Я > 1 - 1(1 - Яо), где Яо = = (По - 1)/По — скорость кода проверки на четность. Таким образом, получим оценку на скорость МПП-кода Галлагера

Я > 1—-.

«о

Декодирование случайного МПП-кода Галлагера

Для большего понимания алгоритма декодирования МПП-кодов, основанных на матрицах перестановок, который будет рассмотрен ниже, в данном разделе мы напомним классический алгоритм декодирования, предложенный Галлаге-ром [1]. Описанный здесь декодер относится к классу так называемых вероятностных алгоритмов декодирования. На вход алгоритму передается оценка вероятностного распределения символов, полученная из канала, и далее декодер работает с численными значениями вероятностей.

Рассматриваемый декодер МПП-кодов работает с представлением кода в виде фактор-графа, также известного как граф Таннера.

Граф Таннера — это двудольный граф, состоящий из двух подмножеств вершин: вершин-символов (вершин-переменных) и вершин-проверок (рис. 1). Ребро соединяет вершину-переменную и вершину-проверку в том случае, если соответствующая переменная (символ) входит в проверку.

Рассматриваемый алгоритм является итеративным. Каждая итерация состоит из последова-

Вершины-переменные

Рис. 1. Граф Таннера регулярного (l, Пд) МПП-кода длины n

тельной обработки сначала данных вершин-проверок, а затем вершин-переменных.

Пусть 1 < i < n, 1 < j < M, где n = mn0 (длина кода), M = ml (количество проверок на четность). Введем некоторые обозначения:

LLR — логарифм отношения правдоподобия (log likelihood ratio);

ai — знак LLR i-й переменной из канала;

Pi — модуль LLR i-й переменной из канала;

а[ — вычисленный знак LLR i-й переменной;

P- — вычисленный модуль LLR i-й переменной;

Yji — сообщение от j-й проверки к i-й переменной;

aji — знак сообщения от i-й переменной к j-й проверке (принимает значения +1 или -1);

Pji — модуль сообщения от i-й переменной к j-й проверке;

I(j) — набор переменных ik, которые участвуют в проверке j;

I(j)\i — набор I(j), кроме бита i;

J(i) — набор проверок, в которых участвует i-я переменная;

J(i)\j — набор J(i), кроме бита j.

Декодер включает в себя следующие шаги.

1. Инициализацию: присвоим V j = 1...M: ajiPji = = aipi-

2. Горизонтальный шаг: вычисление сообщений от вершин-проверок к вершинам-переменным; при использовании LLR оно будет выглядеть следующим образом:

Y ji = П a ji1 Ф ' Е Ф(Р,г)'

І' щ j)V і'еЦ j)\i

где функция

ех +1 ф(х) = 1п -х+-. ех-1

3. Вертикальный шаг: вычисление сообщений от вершин-переменных к вершинам-проверкам:

а;р; = а;Р; + ^ Уу;

а дру = а;Р; + ^ У / г.

1 '^(г)\у

Далее по вычисленным <Ь < п)строится

вектор x, который является «жестким решением», и проверяется равенство нулю синдрома HxT.

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

Отметим также, что если составить М х п матрицу

H = [Н-Ь: Н-г = 1 ^ Ь-я переменная входит в --ю проверку, Н-Ь = о иначе},

то H будет являться проверочной матрицей МПП-кода. Таким образом, существует взаимно-однозначное отображение между фактор-графом и проверочной матрицей МПП-кода. Данный факт позволяет дать процессу декодирования матричное описание.

МПП-коды, основанные на матрицах перестановок

Определение: Пусть m, П), 1еЫ, причем По > I, от.! > ,По. Рассмотрим группу ТП1 матриц перестановок размерности m, |Р^ = m!. Выберем 1по случайных матриц [Р-^еТ^, Ь = 1...1, ] = 1...п0. Потребуем также, что если Р„ = Р^в, то - = £, Ь = в. Ясно, что

і-

такие условия выбора матриц перестановок Pji со

ответствуют урновой модели без возвращений. Построим проверочную матрицу H следующего вида:

H

Pll .............. P

ln0

Pll ................... P

l, no

Указанный выше способ построения матрицы H гарантирует, что все матрицы в каждой строке и каждом столбце будут различны. Так как Р-Ь — квадратная m х m матрица, то размерность Н - ml х mn0. Н определяет ансамбль регулярных (I, По)-кодов с малой плотностью проверок на четность длины п = mn0, который мы обозначим Вр(1, По, m). Элементы ансамбля Вр(1, По, m) получаются путем выбора без возвращений матриц перестановок [Р-ДеР^ - = 1...1, Ь = 1...п0. Произвольный код Севр(1, По, m) назовем кодом, основанным на матрицах перестановок.

Как и для произвольного кода из ансамбля SG(l, По, m), для кода из Вр(1, По, ж.) также справедлива оценка на скорость (1).

Одним из наиболее распространенных на практике и простых по структуре кодов из ан-

самбля Вр(1, По, ш) является квазициклический МПП-код.

Дадим определение ансамбля таких кодов. Определение: Пусть I, ПцбЫ, По > I, Iр — m х m

матрица р;;-кратного циклического сдвига столб-

}*

цов единичной m х m матрицы I, 1 < - < I, 1 < Ь < По, 1 < р-Ь < m. Построим I х По матрицу Н следующего вида:

И =

Pll

I

Pln

Pa

I

Pi,,

Поскольку размерность Iр - m х m, то размерность Н - ml х mn)y Н определяет ансамбль регулярных (I, По) МПП-кодов длины п = mn)y Обозначим этот ансамбль в^(1, п>, m). Элементы ансамбля Вд(1, По, m) получаются путем равновероятного выбора (возможно, с возвращениями) матриц р--кратных циклических сдвигов. Произвольный код Се &д(1, По, m) назовем квазицикли-ческим МПП-кодом.

Очевидно, что ансамбль Вд(1, По, m) является подансамблем ансамбля Вр(1, п0, m). В то же время, поскольку проверочная матрица Н квазици-клического МПП-кода полностью определяется набором из 1по чисел Р^ о < Р-Ь < m - 1, 1 < - 1

1 < Ь < По, то для хранения Н нам достаточно хранить матрицу

Pll P-2

Pll Pl2

Pl

no

Pl,

n0

Хранение данной матрицы вместо H позволяет существенно оптимизировать процедуру хранения. Поскольку для представления проверочной матрицы H в форме (2) нам потребовалось бы mln0 чисел, то достигается m-кратная экономия памяти. Матрицы перестановок Р;;, исполь-

ji

зованные в (2), для квазициклического МПП-кода являются матрицами ^-кратного циклического сдвига.

Отметим, что из работ [8, 9] следует, что коды из ансамблей Вр(1, По, m), Bq(1, По, m) и sG(l, По, m) при одинаковых параметрах обладают практически одинаковыми корректирующими свойствами.

Вычисление синдрома для МПП-кода, основанного на матрицах перестановок

Пусть H =

ll

r1nn

проверочная

Pl1 ....... Pl, n0 /

матрица регулярного (l, По)-кода с малой плотно-

стью проверок на четность, причем размер Р-Ь, 1 < - < I, 1 < Ь < По, равен mхm, тогда матрицу Н можно представить в следующем виде:

H

л11

л11

л-П0 л1, no

где - — перестановка, соответствующая матрице Р-Ь.

Поскольку длина МПП-кода с проверочной матрицей Н равна п = mn)), то кодовое слово с = (С1, е2, ... сП), сЬев^(2), можно представить в следующем виде:

с = (с]_, с2, сПо),

где с — двоичный вектор длины m. Напомним, что синдром Я для принятого слова у вычисляется по формуле Я = Нут, причем Я = о тогда и только тогда, когда у является кодовым словом.

Пусть проверочная матрица задана соотношением (3), а принятое слово у — соотношением (4), тогда у является кодовым тогда и только тогда, когда

л11

л-П0

У- О'

К. О 0

П11 ..... п1, п0

Последнее соотношение эквивалентно следующей системе из I уравнений:

л1і(Уі) + л12(У2) +  + л1п0 (уп0 ) = 0 лп(Уі) + л12(у2) +  + л1,п0 (уп0 ) = 0

Таким образом, доказано следующее утверждение.

Вектор у = (У1, У2, , уп ), где У і — двоичный вектор длины т, является кодовым словом кода с малой плотностью проверок на четность длины п = тп0, задаваемого проверочной матрицей (3), тогда и только тогда, когда выполняется I соотношений

п0

2 піі (У і ) = 0 і =1—и

і=1

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

Декодирование МПП-кодов, основанных на матрицах перестановок

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

Как и при декодировании случайного МПП-кода Галлагера, на вход алгоритму передается оценка вероятностного распределения символов, полученная из канала. Данная оценка представляет из себя вектор длины n LLR, т. е. LLRe.Rn. Так как n = mn00, то для LLR справедливо представление

LLR = (L-, L2,..., Ln0 ),

причем L; є Rm, 1 < i < ng.

Выше было введено множество I(j) — набор переменных {1,..., |, участвующих в j-й провер-

ке, и множество J(i) — набор проверок {c-l),c2l),...,с^}, вкоторые входит i-я переменная. Рассмотрим произвольный вектор L; є Rm. Так как размерность L; равна m, а матрицы Pi., P2., ..., Pli - m x m матри-

цы перестановок (т. е. содержат ровно 1 единицу в каждой строке и каждом столбце), то Ь; участвует в ті различных проверках. Таким образом, | J(Ь;)| = ті. Полученное равенство позволяет нам сделать вывод

0 том, что элементы Ь; участвуют во всех проверках. Таким образом, при декодировании нам не требуется искать J(L;) для каждого вектора Ь;. Проводя аналогичные рассуждения, можно показать, что в т проверках участвуют ти0 переменных, поэтому вычисление Ду) для каждой у-й проверки также не требуется.

Введем необходимые обозначения:

LLR = L2,..., L«o) — принятый из канала вектор логарифмов отношения правдоподобия, причем

Li е_Ят, L; = (іі,4,...,т), 1 < і < П0; _ _ _ . . .

а. — вектор знаков (+1 или -1) вектора L^, полученного из канала, т. е. а. = sign(Li) = (а1, а2,..., ат),

где а\ = sign(lt), і = 1...т;

Р. — вектор модулей вектора L;, полученного из канала, т. е. Р. = = (Р1, Р2,...,Рт), где Рі = ^

1 = 1...т;

а- — вычисленный вектор знаков для вектора L^;

Р- — вычисленный вектор модулей для вектора Ь;;

у; — вектор сообщений от у-й группы из т проверок к L^;

а. — вектор знаков (покомпонентный) сообщений от переменных L; к у-й группе из т проверок;

Рд — вектор модулей (покомпонентный) сообщений от переменных L; к у-й группе из т проверок. Изложенный ниже алгоритм декодирования применим только для МПП-кодов, основанных на матрицах перестановок, и работает с проверочной матрицей, представленной в форме (3):

И:

'41

'Чі

1«о

Щ, «о

Декодирование включает в себя следующие шаги.

1. Начальную проверку: по принятому из канала вектору LLR = ^, L2,..., L«) строится «жесткое решение» х, вычисляется синдром Нхт согласно алгоритму, описанному в предыдущем разделе. Если синдром равен нулевому вектору, то декодирование прекращается и х является результатом выполнения алгоритма, иначе переходим к шагу 2.

2. Инициализацию: строим матрицы А и В по правилу

а11 а12 . .. а1, «о —1 а1«о ’ л11 ^п^)) л12

А = а21 а22 . а « о 1 1—1 а2«о = л2і

_ аі1 аі2 . .. аі, «о —1 а1, «о , лі1 ^п^1)) лі2 (^П^2 )) . . Ч «о —1 (sign(L«0 —1)) Ч «о (sign(L«0 ))_

Р11 Р12 . .. Р1, «о —1 Р1«о лп( Ll ) Л12( L2 ) ... л1, «о —і( Ч —1 ) Л1«о («о ^

В = Р21 Р22 . .. Р2, «о —1 Р2«о = Л21 ( Ll ) л22 ( L2 ) ... л2, «о —і( ( —1 ) Л2«о («о ^

. Рі1 Рі2 . .. Рі, «о—1 Рі, «о Лі1 ( Ll ) лі2 ( L2 ) ... %1, «о—1( Ч —1 ) %1, «о («о ^

3. Горизонтальный шаг: строим матрицу I х ге0 сообщений от у-й группы проверок к 1-му вектору переменных:

Г =

Уіі

Уіі

Уі, п0 -1 у1п

п

і=1

і^і

а;

ф

«о

і: ф(р.і

і=1

і^і

уі, «о —1 уі, «о

причем отображение Ф: Ят ^ Ят имеет следующий вид: Ф(х) = 1п

ех + 1

ех — 1

«

4. Вертикальный шаг: вычисление сообщений от г-го вектора переменных к у-й группе проверок:

_ _ I

агрг = а;р; + ^ я-1 (Уи);

Ь=1

адРд = п j

“iPi +^ Щ11 (у ti] t=1 t^j

5. Вычисление синдрома: по вычисленным а-Р-,

1 < г < По, строится «жесткое решение» х и вычисляется синдром Я; если Я = 0, то декодирование прекращается и х считается результатом работы декодера. Если синдром не нулевой, то возвращаемся на шаг 3.

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

Описанный выше алгоритм оперирует только с векторами длины т, не обращаясь явно к отдельным символам. Таким образом, процесс декодирования можно осуществлять параллельно для т символов.

Результаты имитационного моделирования

Для практической реализации описанного в статье алгоритма декодирования МПП-кодов, основанных на матрицах перестановок, была написана функция для Ма^аЬ. Для рассмотренного в работе декодера производилось имитационное моделирование с использованием среды Ма^аЬ. Передача данных осуществлялась по каналу с аддитивным белым гауссовым шумом и двоичной фазовой модуляцией. Максимальное число итераций ограничивалось 50. В качестве МПП-кодов, основанных на матрицах перестановок, были выбраны квазициклические коды QC-LDPC.

Результаты моделирования 4 кодов различных длин из ансамбля &д(1, ^, т) при фиксированном числе слоев и столбцов и скорости представлены на рис. 2. Из рисунка следует, что энергетический выигрыш при использовании кода длины 2000 по сравнению с кодом длины 1000 составляет около 0,35 дБ (по уровню вероятности ошибки на блок 103); в то же время при переходе от длины 2000 к 4000 выигрыш составляет уже порядка 0,3 дБ при аналогичном уровне вероятности ошибки; увеличение длины кода от 4000 к 8000 уже практически не улучшает корректирующих свойств (выигрыш менее 0,1 дБ).

Результаты моделирования 8 квазицикличе-ских кодов длин ~ 1000 при фиксированной скорости и различном числе слоев I представлены

Рис. 2. Зависимость вероятности ошибки на блок (РЕИ) от отношения сигнал/шум на кодовый бит (Ев\Мо) для регулярных квазицикличе-ских МПП-кодов при различных длинах п

на рис. 3. Как следует из рисунка, наилучшими корректирующими свойствами обладает код с наименьшим числом слоев 1 = 3. Переход от I = 3 к I = 4 приводит к энергетическому проигрышу порядка 0,3 дБ (по уровню вероятности ошибки на блок 104). Дальнейшее увеличение I также приводит к ухудшению корректирующих свойств кода, хотя при I > 6 ухудшение становится незначительным.

----(3,6) regular QC-LDPC R=0.5 N=996

----(4,8) regular QC-LDPC R=0.5 N=1000

----(5,10) regular QC-LDPC R=0.5 N=1000

----(6,12) regular QC-LDPC R=0.5 N=996

----(7,14) regular QC-LDPC R=0.5 N=994

----(8,16) regular QC-LDPC R=0.5 N=992

----(9,18) regular QC-LDPC R=0.5 N=990

----(10,20) regular QC-LDPC R=0.5 N=1000

Ев\Ыо

Рис. 3. Зависимость вероятности ошибки на блок (РЕИ) от отношения сигнал/шум на кодовый бит (Ев\Мо) для регулярных квазици-клических МПП-кодов при различном числе слоев I

Размер m матрицы перестановки

Рис. 4. Зависимость отношения TC\TV (TC — время декодирования классическим алгоритмом belief propagation, TV — время декодирования векторным belief propagation) от m для (З, б) регулярного квазициклического МПП-кода при отношении сигнал/шум на бит Es\No = 2 дБ

В то же время из работ [1, 9, 10] следует, что увеличение I при фиксированной длине кода п и его скорости Я приводит к увеличению минимального кодового расстояния 1. Следовательно, чем больше число слоев I, тем меньшую часть

Литература

1. Галлагер Р. Дж. Коды с малой плотностью проверок на четность. — М.: Мир, 1966. — 90 с.

2. Tanner M. A. Recursive Approach to Low Complexity Codes // IEEE Trans. Inform. Theory. 1981. Vol. 27. N. 5. P. 533-547.

3. Fossorier P. C. Quasi-cyclic low-density parity-check codes from circulant permutation matrices // IEEE Trans. Inform. Theory. 2004. Vol. 50. N. 8. P. 1788-1793.

4. Lu J., Moura M. F., Niesen U. Grouping-and-shifting designs for structured LDPC codes with large girth // Proc. of IEEE Intern. Symp. on Information Theory (ISIT‘04). 2004. P. 236.

5. Gabidulin E., Moinian A., Honary B. Generalized construction of quasi-cyclic regular LDPC codes based on permutation matrices // Proc. of IEEE Intern. Symp. on Information Theory (ISIT‘06). 2006. P. 679-683.

6. Ivanov F. I., Zyablov V. V., Potapov V. G. Low-Destiny Parity-Check Codes Based on Galous Field // Information Processes. 2012. Vol. 12. N. 1. P. 68-83.

доли исправляемых ошибок реализует алгоритм belief propagation.

Таким образом, belief propagation хорошо работает только с кодами с наихудшими потенциальными корректирующими свойствами.

Вывод о том, что предложенный в статье алгоритм декодирования уже при сравнительно небольших т дает выигрыш по времени декодирования минимум в 5 раз по сравнению с декодером, предложенным в работе [1], позволяет сделать рис. 4. Отметим, что моделирование обоих алгоритмов проводилось в среде MatLab. При m = 600 векторный алгоритм декодирования работает примерно в 20 раз быстрее классического belief propagation. Причем следует отметить практически линейную зависимость отношения TC/TV от т.

Заключение

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

7. Иванов Ф. И., Зяблов В. В., Потапов В. Г. Оценка минимальной длины циклов квазициклических регулярных кодов с малой плотностью проверок на четность // Информационно-управляющие системы. 2012. № 3. С. 42-45.

8. Иванов Ф. И., Зяблов В. В., Потапов В. Г. Сравнение различных конструкций двоичных МПП-кодов, построенных на основе матриц перестановок // Информационные процессы. 2012. Т. 12. № 1. С. 31-52.

9. Шридхаран А. и др. О минимальном расстоянии низкоплотностных кодов с проверочными матрицами, составленными из перестановочных матриц // Проблемы передачи информации. 2005. Т. 41. № 1. С. 39-52.

10. Зяблов В. В., Пинскер М. С. Оценка сложности исправления ошибок низкоплотностными кодами Гал-лагера // Проблемы передачи информации. 1975. Т. 11. № 1. С. 23-36.