Оптимизация алгоритма декодирования min-sum для кодов с низкой плотностью проверок на четность

Среди многих существующих помехоустойчивых кодов коды с низкой плотностью проверок на. четность (LDPC-коды) являются одними из самых мощных, эффективность которых приближается к пределу Шеннона. [1, 2]. LDPC-коды впервые были представлены Робертом Галлагером [3] в 1963 г., однако из-за. сложности реализации коды практически не нашли применения. С развитием компьютерных технологий и ростом требований к точности передачи информации LDPC-коды вновь привлекли к себе внимание исследователей. В последнее время эти коды применяются во многих современных стандартах, таких как DVB-S2, DVB-T2 и IEEE 802.Зап [1, 4, 5].

Существует множество алгоритмов декодирования LDPC-кодов. Среди них самым известным является алгоритм «sum-product» [6], который обеспечивает высокую эффективность декодирования, но требует больших вычислительных затрат. В связи с этим существуют альтернативные методы, целью которых является снижение вычислительных затрат. Среди них одним из самых популярных является алгоритм «min-sum» [6, 7]. Алгоритм «min-sum» является аппроксимацией алгоритма, «sum-product» с использованием простых © Ле В.Ш., 2021

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

2.    Алгоритмы декодирования LDPC-кодов

LDPC-код представляет собой линейный блочный код, характеризующийся разряжённой проверочной матрицей Н (N х М ), г де М - количество проверочных строк; N - длина кода, т.е. количество столбцов в матрице; К - длина исходных данных. Если количество ненулевых элементов в каждой строке равно d_T < N и количество ненулевых элементов в каждом столбце равно d_c< М, то код называется регулярным, в противном случае -нерегулярным.

Графически LDPC-коды можно представить с помощью графа Таннера (рис. 1).

Рис. 1. Представление регулярного LDPC-кода в виде графа. Таннера.

На рис. 1 вершины li,12 ••• 1м ~ проверочные у злы, а вершины ci, С2 ••• c n - битовые узлы. Таким образом, из графа видно, что d_T = 3 и d_c = 2.

Для декодирования LDPC-кодов используются различные алгоритмы декодирования с «жёстким» и «мягким» входом [8]. Причём «жёсткие» декодеры имеют достаточно простую конструкцию, их легко реализовать на практике, но они обладают невысокой эффективностью. А «мягкие» декодеры, наоборот, более сложные, но обладают высокой эффективностью. В данной работе рассмотрены только «мягкие» декодеры.

2.1.    Алгоритм декодирования «sum-product»

Для пояснения алгоритма введём следующие обозначения:

Mj,t - сообщение от г-го битового узла к j'-му проверочному узлу; Ej,t - сообщение от j- го проверочного узла к г-му битовому узлу; Аг - множество проверок, в которых участвует г-й символ; Bj - множество символов, которые участвуют в j-й проверке.

Алгоритм «sum-product» описан в [6, 9]. Его можно представить в виде следующих шагов:

Шаг 1. Инициализация: для каждого принятого символа сг установить значения Mj,f.

где L(c-) - априорная функция логарифмического отношения правдоподобия (LLR) принятого символа сд

L ( c , ) = ln

p ( c , = 0)

P^(ci = 1)"

Шаг 2. Формирование сообщений от битовых узлов к проверочным (для первой итерации используется формула (1)):

M_j,ⁱ = Цс) + ^2.‘_eA._d‘=i ^Ej',v                             (3)

Шаг 3. Формирование сообщений от проверочных узлов к битовым:

Ej,i = 2tanh

1 (n..6Bj w      м/2)) •

Шаг 4- Расчёт значения общего суммарного LLR и определение новых значений битов кодового слова:

L(Pi) = L(ci) + ^_а E .,                         (5)

По полученным значениям L(Pi) определить новые значения битов кодового слова:

Г1, L(Pi) < 0, (0, L(Pi)>0.

Процесс декодирования будет остановлен тогда, когда будет найдено допустимое кодовое слово, т.е. с Н^т = 0, или пока не будет выполнено заданное количество итераций.

2.2.    Алгоритм декодирования «min-sum»

Алгоритм «min-sum» является модифицированным алгоритмом «sum-product», полученный путём упрощения вычисления сообщений от проверочных узлов к битовым. Для этого применено упрощение расчёта LLR суммы по модулю 2 множества случайных статистически независимых величин Ci, С2 ... С_п [4]:

L(Ci ф С2 • • • Ф С„) «( Щ1 sign(L(Ci)^ • _iminJ|L(Ci)|).

Таким образом, в алгоритме «min-sum» упрощается вычисление E., считая что элемент, соответствующий наименьшему М.,.., является определяющим при расчёте. Поэтому Ej,i может быть аппроксимирован следующим образом:

Ej,i

(П ,«,,„    ^v • ^„(м.^-'».

Вычисление значения Ej,i теперь требует только простых операций поиска минимума и сложения.

3.    Модифицированные алгоритмы «min-sum»

Как уже было сказано выше, из-за упрощения алгоритм «min-sum» обладает достаточно большим энергетическим проигрышем, порядка 0.2 ... 0.5 дБ, по сравнению с «sumproduct» алгоритмом. В связи с этим задача его модификации с целью повышения эффективности является актуальной. Ниже представлены модифицированные версии алгоритма «min-sum».

3.1.    Алгоритм «min-sum normalized»

Отличие алгоритма «min-sum normalized» [2, 4, 6] от алгоритма «min-sum» состоит в том, что теперь к расчёту сообщений от проверочных узлов к битовым добавляется один элемент, так называемый коэффициент нормализации а для сокращения разницы в значениях, вычисляемых по формулам (4) и (8):

^Е* =Д ILe»,^     ^M 0 • «тдз^-'¹)-

где значение а варьируется, как правило, в пределах (0, 1].

Для нахождения оптимального значения коэффициента а конкретного кода (в данном случае использовался регулярный LDPC-код со скоростью R = 1/2) было проведено исследование в среде моделирования Matlab. При этом использовалась проверочная матрица регулярного кода Н (408 х 204) [10]. Вес каждого столбца: d_c = 3, а вес каждой строки: d_r = 6. Максимальное количество итераций - 5, канал связи - АБГШ, модуляция - BPSK.

Рис. 2. Зависимость вероятности битовой ошибки ( BER) от коэффициент а нормализации а при E _b /No = 1 дБ

На рис. 2 видно, что при а = 0.69 вероятность битовой ошибки достигает минимума -0.081533.

3.2.    Алгоритм «min-sum offset»

Алгоритм «min-sum offset» [1, 2, 4] является альтернативной модификацией «min-sum» алгоритма. В отличие от алгоритма «min-sum normalized», в расчёте Е^, используется коэффициент сдвига 3^:

■ maxfL min ,⁽\^M3-i' I) — ³\ 0) . \\ г’еВ, ,г'=г                 /    /

Значение 3 также варыірус'тся в пределах (0,1]. При таких же ус.товнях. как и для а. была построена зависимость для нахождения оптимального значения 3- На рис. 3 показано, что значение BER достигло мшшмума - 0.082560 щш 3 = 0.73-

Рис. 3. Зависимость вероятности битовой ошибки ( BER) от коэффициента сдвига 3 при E _b /No = 1 дБ

3.3.    Комбинированный алгоритм «min-sum»

Для достижения максимальной эффективности, приближенной к алгоритму «sumproduct», предложен следующий вариант комбинации двух вышерассмотренных алгоритмов: «min-sum normalized» и «min-sum offset», т.е. в расчёте Ej,, присутствуют одновременно два коэффициента а и 3^:

■ ^max(L minJWj,,' I)—Л 0) • \\ I'EBj ,r =               / /

На рис. 4 представлена поверхность, иллюстрирующая зависимость вероятности битовой ошибки от коэффициентов а и 3- Можно заметить, что минимальная вероятность битовой ошибки достигается при а = 0.84, 3 = 0.44.

В табл. 1 приведены оптимальные значения а и 3 для нескольких значений Eb/No для различных алгоритмов декодирования.

Таблица!

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

Еъ/No	«min-sum»	«min-sum normalized»		«min-sum offset»		Комбинированный
		a	BER	3	BER	a	3	BER
1	0.10601-10-0	0.69	0.81533•10-1	0.73	0.82560^10—1	0.84	0.44	0.8055240-1
2	0.41161-10—1	0.77	0.26561 • 10-1	0.53	0.27528^10—1	0.81	0.22	0.2539940-1
3	0.45882-10—2	0.81	0.26443 • 10-2	0.42	0.27289^10—2	0.86	0.14	0.2382340-2

Из рис. 4 и табл. 1 видно, что значения вероятности ошибки на бит при комбинированном алгоритме для различных значений Eb/No являются минимальными по сравнению с двумя другими модификациями «min-sum» алгоритма.

В табл. 2 представлены расчёты количества операций для выполнения одной итерации рассмотренных алгоритмов. Для конкретной проверочной матрицы Н (408 х 204), имеющей вес каждого столбца: d_c = 3, а вес каждой строки: d_r = 6, получена табл. 3.

Рис. 4. Зависимость вероятности битовой ошибки ( BER) от коэффициеитов а и /3 при E _b /No = 1 дБ

Т а б л и ц а 2

Количество вычислительных операций для выполнения одной итерации алгоритмов декодирования «min-sum», «min-sum normalized», «min-sum offset» и предложенного комбинированного алгоритма

Операция	Количество операций
	« min- sum»	«min-sum normalized»	«min-sum offset»	«Комбинированный»
Сложение	Nd^	Nd2	Nd2 + Mdr	Nd^ + Mdr
Умножение	Mdr (dr - 1)	Mdr (dr -1HMdr	Mdr (dr - 1)	Mdr (dr - 1) + Mdr
Сравнение	Mdr (dr -2)+N	Mdr (dr - 2) + N	Mdr (dr -1)+N	Mdr (dr - 1) + N
Взятие модуля числа	Mdr (dr - 1)	Mdr (dr - 1)	Mdr (dr - 1)	Mdr (dr - 1)
Сложение по модулю 2	Mdr	Mdr	Mdr	Mdr

Т а б л и ц а 3

Количество вычислительных операций, необходимых для выполнения одной итерации алгоритмов декодирования для LDPC-кода 408 х 204 [10]

Операция	Количество операций
	«min-sum»	«min-sum normalized»	«min-sum offset»	«Комбинированный»
Сложение	3672	3672	4896	4896
Умножение	6120	7344	6120	7344
Сравнение	5304	5304	6528	6528
Взятие модуля числа	6120	6120	6120	6120
Сложение по модулю 2	1224	1224	1224	1224

Также построена гистограмма для сравнения количества операций для выполнения одной итерации различных алгоритмов декодирования (рис. 5). Из гистограммы видно, что самым сложным является комбинированный метод, затем алгоритмы «min-sum offset», «min-sum normalized» и «min-sum».

Рис. 5. Сложность различных алгоритмов декодирования

4.    Заключение

В статье рассмотрены несколько алгоритмов декодирования LDPC-кодов, основанных на алгоритме «min-sum». Была исследована возможность использования двух коэффициентов (коэффициент нормализации и коэффициент сдвига) для повышения эффективности алгоритма «min-sum», получены их оптимальные значения для каждого алгоритма. А также предложен комбинированный алгоритм «min-sum», в котором использовались одновременно два коэффициента, и получены их оптимальные значения для разных значений E_b/No.

Также проведено сравнение рассмотренных алгоритмов по эффективности. Следует отметить, что самым эффективным оказался предложенный комбинированный алгоритм.

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