Оптимизация min-sum алгоритма декодирования LDPC-кодов

УДК 621.391.1

А. А. Хлынов

ФГУП НИИ Радио Московский физико-технический институт

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

LDPC-кодов

В работе рассматривается модель низкоплотностного LDPC-кодека в канале с аддитивным белым гауссовым шумом. Исследуется влияние поправочных коэффициентов на эффективность исправления ошибок оптимизированным min-sum декодером. LDPC-кодек использует реализацию декодера по методу min-sum с линейной коррекцией промежуточных метрик. Приведены результаты моделирования, показывающие, что оптимизированный min-sum декодер имеет ЭВК, близкий к sum-product декодеру. Оптимизированный декодер хорошо подходит для реализации на ПЛИС.

Ключевые слова: norm min-sum, декодер, LDPC, ПЛИС.

A. A. Khlinov

Radio Research and Development Institute Moscow Institute of Physics and Technology

Optimized min-sum decoding algorithm for LDPC-codes

In this paper, the simulation of a lowdensity LDPC-code with AWGN is presented. The error performance of the min-sum decoder with normalization factors is showen. LDPC uses an implementation of the decoder based on the min-sum method with linear correction of node metrics. Some simulation results are given, which show that the error performance of the optimized min-sum decoder is close to that of the sumproduct decoder. An optimized decoder is suitable for implementation on FPGAs as well as an ordinary min-sum decoder.

Key words: norm min-sum, decoder, LDPC, FPGA.

1. Введение

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

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

2. Алгоритм с нормализацией проверочных метрик

Для декодирования LDPC-кодов применяются как декодеры с «мягким», так и с «жёстким» решением. Декодеры с мягким решением более эффективны, т.к. получают больше информации, но при этом сложнее в реализации. Одним из наиболее эффективных алгоритмов декодирования низкоплотностных кодов является алгоритм «распространения доверия» («belief-propagation»). В реализации декодера (далее - sum-product алгоритм), на входе которого используются llr-значения бит (llr - log-likelihood ratio - логарифмический

коэффициент правдоподобия), метрики узлов переменных инициализируются значениями 11г априорной вероятности, вычисленными из принятых демодулятором значений У;, а метрики проверочных узлов для каждой итерации декодирования вычисляются как

= 2 * tanh-1 Л tanh(-

j = Nm,n\n

j,m

А обновлённые значения Уг^ получают через данные от проверочных узлов:

= llrn + ^

j=Nm>n\m

На каждой итерации вычисляются апостериорные значения 11г каждого бита, т.н. «мягкий выход».

Подобные вычисления при реализации декодера на ПЛИС требуют много ресурсов для реализации функций 1апИ-1 и 1апИ (обычно реализуется в виде чтения из памяти заранее вычисленных значений), поэтому широкое распространение среди аппаратных реализаций получил алгоритм декодирования тт-8ит, в котором используется приближенное вычисление проверочных метрик, где основной является операция вычисления минимума вектора метрик узлов переменных, которая требует гораздо меньше ресурсов ПЛИС и позволяет использовать вычисления с большей разрядностью данных (таблицы 16 битных значений предварительно вычисленных функций должны занимать ~ 1Мбит памяти):

c'n,m = min (vNm,n\n,m) * П si9n(vj,m^

j=Nm,n\n

Благодаря такой замене функции вычисления метрик алгоритм min-sum нечувствителен к линейному масштабированию входных данных, что также упрощает приёмник благодаря отсутствию необходимости измерять значение дисперсии шума, которое входит в формулу вычисления llr как масштабирующий коэффициент. Для рассматриваемого кода из [1] с длиной кодового слова 2048 бит и кодовой скоростью r = 1 получаем проигрыш эффективности исправления ошибок ~ 1 дБ по отношению к значениям BER, указанным

в[1].

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

а из (1) следует

получим, что

|tanhx\ < 1

|tanhx1\ < \tanhx2\ ^ \x1\ < \x2\

tanh

П tanh( v-f.) j = Nm,n\n

\Cn,m\ < mm \vNmn\n

— \n,m\

3. Вычисление коэффициента нормализации

Таким образом, удобно применить нормализацию метрик для получения значений, более близких к sum-product алгоритму. В работе [2] для получения более точных значений метрик предлагается использовать коэффициент нормализации cf = щ~сц, заданный как

c

2

v

и

c

2

отношение значений математического ожидания c и c' соответственно. Нормализованные метрики вычисляются умножением на масштабирующий коэффициент cf :

cn,m cn,m * cf

Реализаиция на ПЛИС умножения на коэффициент требует использования дополнительных умножителей либо использования операции сложения и сдвига, если коэффициент имеет короткую запись в двоичном виде [3, 4].

На рис. 1 показаны зависимости разности метрик проверочных узлов || — |с| (cf = 1) и \с"\ — |c| (cf = 0, 702) как функций двух аргументов vi и V2, вычисленные методом Монте-Карло с выбором равномерного распределения значений аргументов.

Рис. 1. Ошибка вычисления метрики проверочных узлов

Однако, хотя использование теоретически вычисленного значения улучшает эффективность алгоритма шт-8иш, можно получить лучшее значение коэффициента в результате симуляций методом Монте-Карло или минимизацией функции с одним параметром, т.к. нормализация среднего значения [2] не означает отсутствие потерь эффективности исправления ошибок. Для поиска оптимального значения коэффициента была написана программа в среде МАТЬАВ, использующая оператор ^тБвагсй. для поиска минимума функции, вычисляющей количество неисправленных ошибок декодером, с различными значениями коэффициента с/. Для поиска минимума МАТЬАВ использует метод Нелдера-Мида [5], также известный как метод деформируемого многогранника и симплекс-метод, — метод безусловной оптимизации функции от нескольких переменных, не использующий производной (точнее — градиентов) функции, а поэтому легко применим к негладким и/или зашумлённым функциям. Для моделирования был сгенерирован набор тестовых векторов информации и шума с -щ = 1.5 дБ (больший уровень шума вносит слишком много ошибок для нормальной работы канала, слишком маленький уровень шума ведёт к резкому

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

4. Результаты

В результате нескольких попыток вычисления коэффициента с/ для различных тестовых наборов кодовых слов с наложенным шумом (использовалась сигнальная конструкция QPSK и декодер с максимальным числом итераций 50) были получены несколько значений с/ ~ 0, 702 и для дальнейшего моделирования было выбрано именно это значение коэффициента (в работе [2] для этого значения шума с/ = 0, 61). Эффективность оптимизированного кодека в результате моделирования на большем числе пакетов и различных значениях уровня шума приведена на рис. 2, где для различных декодеров показана вероятность битовой и пакетной ошибок. Также для сравнения приведена эффективность JPL-декодера от авторов стандарта [1] (точные характеристики алгоритма и число итераций неизвестно).

Eb/No, дБ

Рис. 2. Вероятность битовой (BER) и кадровой (FER) ошибки для различных декодеров

На основании результатов моделирования можно сделать вывод, что декодер с оптимизированными вычислениями проверочных метрик значительно ближе по эффективности к sum-product декодеру и проигрывает ему всего ~ 0.2 дБ, против ~ 0.9 дБ потерь у min-sum декодера. В качестве предмета дальнейших исследований предлагается рассмотреть возможность адаптивной подстройки коэффициента cf для разных значений -щ в канале.

Литература

1. The Consultative Committee for Space Data Systems TM synchronization and channel coding — summary of concept and rationale // CCSDS 130.1-G-2. 2012.

2. Chen J., Fossorier M. Near optimum universal belief propagation based decoding of low-density parity check codes // IEEE transactions on communications. 2002. V. 50, N 3. P. 406-414.

3. Wu X., Song Y, Jiang M., Zhao C. Adaptive-normalized/offset min-sum algorithm. IEEE communications letters. 2010. V. 14, N 7.

4. Emran A.A., Elsabrouty M. Simplified variable-scaled min-sum LDPC decoder for irregular LDPC codes — Personal, Indoor, and Mobile Radio Communication (PIMRC) // IEEE 25th Annual International Symposium. 2014.

5. Lagarias, J.C., Reeds J.A., Wright M.H., Wright P.E. Convergence Properties of the Nelder-Mead Simplex Method in Low Dimensions // SIAM Journal of Optimization. 1998. V. 9, N 1. P. 112-147.

References

1. The Consultative Committee for Space Data Systems TM synchronization and channel coding — summary of concept and rationale. CCSDS 130.1-G-2. 2012.

2. Chen J., Fossorier M. Near optimum universal belief propagation based decoding of low-density parity check codes. IEEE transactions on communications. 2002, V. 50, N 3. P. 406414.

3. Wu X., Song Y, Jiang M, Zhao C. Adaptive-normalized/offset min-sum algorithm. IEEE communications letters. 2010. V. 14, N 7.

4. Emran A.A., Elsabrouty M. Simplified variable-scaled min-sum LDPC decoder for irregular LDPC codes — Personal, Indoor, and Mobile Radio Communication (PIMRC). IEEE 25th Annual International Symposium. 2014.

5. Lagarias, J.C., Reeds J.A., Wright M.H., Wright P.E. Convergence Properties of the Nelder-Mead Simplex Method in Low Dimensions. SIAM Journal of Optimization. 1998. V. 9 N 1, P. 112-147.

Поступила в редакцию 02.10.2016