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

УДК 621.3.049.77

РЕАЛИЗАЦИЯ LDPC-ДЕКОДЕРА НА МАССИВНО-ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ УСТРОЙСТВАХ

А.В. Башкиров, А.Ю. Савинков, М.В. Хорошайлова

Представлены архитектуры LDPC- кодера и декодера. Приведены сравнительные результаты моделирования LDPC-кода в параллельных и последовательных гетерогенных системах с применением CPU и GPU. Показан выигрыш во времени декодирования и сложности аппаратной реализации

Ключевые слова: архитектура, кодирование, LDPC- код

Введение. LDPC-коды - это FEC коды (Forward Error Correction, FEC, помехоустойчивое кодирование) и, следовательно, скорость передачи данных больше. Они относятся к классу линейных кодов, исправляющих ошибки, для передачи сообщения по зашумленному каналу. Коды LDPC находят все более широкое применение в приложениях, требующих надежной и высокоэффективной передачи информации через шумные каналы. Эти коды способны работать на пределе, близкому к пределу Шеннона. Основным преимуществом матрицы контроля по четности является декодер, который может исправить все ошибки в одном разряде.

Коды низкой плотности проверки на четности (LDPC) в последнее время привлекли огромное внимание исследователей из-за их отличной вычислительной способности коррекции ошибок и высокой параллельной схемы декодирования. Коды LDPC были использованы в цифровом стандарте видео вещания (DVB) и серьезно рассматриваются в различных реальных приложениях, таких как магнитное хранения, 10 Гб Ethernet, и высокой пропускной беспроводной локальной сети [1].

Это класс линейных блоковых кодов, а их название низкой плотности означает, что число единиц в матрице контроля четности очень мало по сравнению с нулями. Условие для низкой плотности является WC << m и Wr << n, где WC представляет собой вес столбца и Wr представляет вес строки. Разряженность матрицы контроля четности гарантирует, что сложность алгоритма декодирования увеличивается только при увеличении длины кода.

В этой методике кодирования будет использоваться две матрицы: генераторная матрица G кодера и проверочная матрица Н декодера. Строки матрицы контроля четности представляют проверочные узлы, а столбцы представляют переменные узлы на графе Таннера. Биты в кодовом слове основаны на переменных узлах, а биты в векторе со-

Башкиров Алексей Викторович - ВГТУ, канд. техн. наук, доцент, тел. 8-952-543-99-88, e-mail: kipr@vorstu.ru Савинков Андрей Юрьевич - ВГТУ, д-р техн. наук, профессор, тел. 8(473) 246-66-47, e-mail: kipr@vorstu.ru Хорошайлова Марина Владимировна - ВГТУ, аспирант, тел. 8-920-415-15-65, e-mail: pmv2205@mail.ru

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

Модель системы

Здесь представлено разделение LDPC системы на три основных блока (рис. 1):

1) LDPC кодер;

2) блок введения шума (канал с аддитивным белым гауссовским шумом AWGN);

3) ЬЭРС декодер.

Рис. 1. Архитектура

LDPC алгоритм: Кодовое слово С образуется как С=Ш,

где К - вектор сообщения,

G - генераторная матрица. Действительное кодовое слово может быть проверено с использованием

НСТ =0,

где Н - матрица проверки четности. Если результат (2) не 0, то кодовое слово С ошибочно и в этом случае должна быть выполнена процедура исправления ошибки. Побитовый метод использует вектор, который называется синдром и вычисляется как

S=HYT,

где Y - поврежденное кодовое слово. Синдром указывает, в какой строке Н не обнуляется вектор Y и какие биты должны быть исправлены в декодере [2]. Если проверочная матрица небольшого размера, то можем найти ошибки кода LDPC, где каждый неверный бит исправлен и

BER соотношение ошибок по битам (BER - bit error ratio) близко к нулю или нуль.

Модель кодера

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

[A\In-k \

а генераторная матрица задается как

G = [h\A \.

Первоначально матрица контроля по четности создается, используя эту порождающую матрицу. Есть два типа матриц четности LDPC-кодирования: регулярная матрица и нерегулярная матрица.

Регулярный матрица, в которой столбец WC является одинаковым для всех колонок и вес строки задается Wr = Wc (n/m). В данной статье используется регулярная матрица 8x16. 1001100000000010 1000000001001 100 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 Рис. 2. Регулярная проверочная матрица

Для передачи матрицы проверки на четность в стандартной форме, т.е. H = \ä \ I n_k \ используется метода исключения Гаусса, примененный к вышеуказанной матрице [3].

Матрица H вводится в этой форме посредством применения элементарные операции для строк, меняя местами две строки или добавление одного ряда в другой по модулю 2. Получаем матрицу контроля четности в стандартной форме, как показано на рис. 3.

ooooooooiooooooo ooiiioiioioooooo ooiiiooiooiooooo ooioiooooooioooo oioooioiooooiooo lllllliooooooioo loiiioooooooooio lioiioiooooooooi

Рис. 3. Стандартная проверочная матрица

H=

Полученная проверенная матрицы четности переведена в стандартной форме генераторной матрицы, т.е. G = |/к | А1 ] и представлена на рис. 4.

G =

looooooooooooi oiooooooooooi l o o i o o o o o o i o i o o o o i o o o o o i i o o i

io

ii oi l 0 0 ii iii

00

01 ooo

00001000011 00000100001011 00000010010001 00000001011

Рис. 4. Генераторная матрица

Теперь информационные биты сообщения кодируются путем умножения его с упомянутой выше порождающей матрицей, т.е. С = [и] чтобы получить кодовое слово. Ниже рис. .5 показывает

блок-схему кодера.

Messagsi---v

Veda 1-u-

Codtwwd

Рис. 5. Блок-схему кодера

Каждая структура обозначена G {0,1,,, м-1}, i это «Исключающее ИЛИ» структуры, выполняют операции по модулю 2 на входящих битах сообщения, и полученные кодовые слова будут иметь N бит. Рассмотрим информационное сообщение из 10 бит и=[00001100],

[i 0 0 i 0 i o o\ •

1000000000000111 0100000000001 101 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0

C = [1001010001101100]

Рис. 6. Кодирование

Предложим модификацию алгоритма LDPC для реализации на GPU.

Введем следующие обозначения: l - длина кодового ограничения; M0[2W] - массив для хранения метрик выживших путей, вычисленных на предыдущем шаге; M1 [2W] - массив вычисляемых метрик; P [w*2w] - массив, хранящий номер предыдущего состояния, для выжившего состояния пути;

i - номер процессорного элемента (kernel в терминологии OpenCL);

m0 - значение метрики, при условии, что предыдущим для состояния i (или i-2l-2, при i>2l-2) было состояние i*2 ((i-2l-2)*2);

т1 - значение метрики, при условии, что предыдущим для состояния i или i-2l'2 было состояние 1*2+1 ((г-21-2)*2+1);

t - номер шага подсчета метрик путей. Каждым процессорным элементом: 1. Вычисляется М1 [г],

¡<21'2, равный большему из значе-

в P[i] записывается i*2, если M0[i*2]+m0

1>21'2, соответствующий большему из значений м0[(г-21-2)*2]+т0 и М0[(г-21-2)*2+1]+т1;

в P[t] записывается г*2, если М0[(г-21-2)*2]+т0 > М0[(г-21-2)*2+1]+т1 и г*2+1 в противном случае.

2. Производится обновление массивов метрик: на первом шаге подсчета метрик - М0[г] = М1 [г] = -да, М0[0] = 0;

в остальных случаях - М0[г] = М1[г], М1[г] = -

16 1016 2016 3016 4016 5016 6016 7016 8016 Число СОСТОЯНИЙ

а)

НЕ8400

5770 -4650

Длина кодового ограничения б)

Рис. 7. Моделирование LDPC кодирования с декодированием по: а) зависимость времени вычислений от числа состояний кодера; б) зависимость времени вычислений от длины кодового ограничения

Данную модификацию алгоритма можно применить при распараллеливании подсчета метрик. Для сравнения выигрыша во времени декодирования и сложности аппаратной реализации проводилось моделирование в 100 итераций. Длина одного зашумленного пакета составила 1024 бита, при уровне шума в 1; 1,5; 2; 2,5 дБ. Результаты моделирования представлены на рис. 7.

Кривые, представленные на рис. 7: E8400 -временные затраты при последовательном вычислении на CPU (Intel Core 2 Duo E8400) LDPC кода; 5770 - это затратам на моделирование с применением распараллеливания вычислений на GPU (типа Radeon HD 5770); 4650 - тоже распараллеливание вычислений на видеопроцессоре GPU Radeon HD 4650.

Вывод: Для видеопроцессора GPU Radeon HD 5770 временной выигрыш при моделировании кодирования-декодирования LDPC кода по отношению к одноядерному процессору CPU E8400 можно наблюдать уже при 21-1=128; для видеопроцессора Radeon HD 4650 - при 2/-1=512. Результаты применения распараллеливания кодирования-декодирования дают нам однозначные основания считать такой подход перспективным, для решения задачи уменьшения временных затрат при реализации кодеков, работающих на базе LDPC и других низкоплотностных и свёрточных кодов.

Литература

1. R. G. Gallager, —Low density parity check codes,! IRE Trans. Inform. Theory, vol. IT-8, no.1, pp. 21-28, Jan. 1962

2. Башкиров, А.В. Использование LDPC-кодов [Текст] / А.В. Башкиров, Л.Н. Коротков, И.В. Свиридова // Вестник Воронежского государственного технического университета. -2013. -Т. 9. -№ 6-3. - С. 41-44.

3. R. M. Tanner, —A Recursive Approach to Low Complexity Codes,! IEEE Trans. Inform. Theory, vol. IT-27, no.5, pp. 533-547, Sep. 1981

4. S. J. Johnson, —Introducing Low-Density Parity-Check Codes,! unpublished.

5. T. Richardson, —Error floors of LDPC codes,! in Proc. Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, pp. 1426-1435, Oct. 2003.

Воронежский государственный технический университет

SALES LDPC- DECODER MASSIVELY PARALLEL COMPUTING DEVICES

A.V. Bashkirov, A.Yu. Savinkov, M.V. Horoshaylova

This paper presents the architecture LDPC- encoder and decoder. The comparative results of simulation mo-LDPC code in parallel and serial heterogeneous systems using the CPU and GPU. In kettle saving in decoding time and complexity of hardware implementation

on

Key words: architecture, coding, LDPC code