Сравнительный анализ аппаратных архитектур декодера LDPC кодов для систем радиосвязи IEEE ad А.А. Шевченко 1, 2, Р.О. Масленников 2, А.А. Мальцев 1, М.В. Пантелеев 1, 2, А.Ф. Клюев 1, 2, А.Г. Ветчинкин 1, 2 1 Нижегородский государственный университет им. Н.И.Лобачевского 2 ООО «Радио Гигабит»

Содержание [2] Вступление Спецификация рассматриваемого LPDC кода Описание алгоритмов декодирования Обзор аппаратных архитектур декодера Анализ аппаратной эффективности рассматриваемых архитектур декодера Заключение

Вступление [3] Коды с малой плотностью проверок на четность (Low Density Parity Check - LDPC) широко распространены в современных беспроводных системах связи - IEEE ad, 2nd Gen. DVB, IEEE 802.3an Преимущество – высокая корректирующая способность кода и доступность высокопроизводительной аппаратной реализации с пропускной способность несколько Гбит/с Относительный недостаток – в общем для кода в общем случае ограниченное число доступных вариантов аппаратных архитектур декодера Решение – структурированные LDPC коды имеющие промежуточные решения аппаратных архитектур декодера

[4] Введение в LDPC коды Определяются проверочной матрицей H размером M×N обладающей свойством разреженности Структура LDPC кода представляется в виде графа Таннера o Биты кодового слова - кодовые вершины (узлы) (VNm) o Проверочные уравнения – проверочные вершины (узлы) (CNm) o Ненулевые элементы матрицы Н – ребра между вершинами

[5] Спецификация LDPC кода стандарта IEEE ad Квази-циклический LDPC код Макроматрица 8×16 с размером элементарной матрицы 42×42 Результирующий размер матрицы H – 336 × 672 Длина кодового слова бита Скорость кода - ½ Слоистая структура проверочной матрицы - 4 слоя

[6] Алгоритм декодирования Belief Propagation Наиболее распространенный алгоритм декодирования - Belief-Propagation (BP) Использует логарифмические метрик отношения правдоподобия для каждого бита (LLR) кодового слова Каждый узел графа Таннера рассматривается как независимый процессор LLR бит итеративно обновляются каждым Кодовым узлом на основе информации от других Кодовых узлов Возможность раннего завершения декодирования на основе проверки синдромов В этом случае выполнение всех N max итераций не требуется

[7] Модифицированный алгоритм декодирования Рассматриваемый код может быть декодирован модификацией BP алгоритма называемой Layered Belief-Propagation (LBP) Требуется свойство слоистости H матрицы Одна итерация BP алгоритма разбивается на несколько под итераций Обновление LLR бит производится каждую под итерацию – в 4 раза чаще Быстрее сходимость алгоритма декодирования Улучшается корректирующая способность и уменьшается среднее число итераций декодирования для заданного кода

[8] Полностью параллельная архитектура декодера Доступен для любого LDPC кода Напрямую реализует BP алгоритм – каждый узел соответствует аппаратному блоку Одна итерация алгоритма выполняется за один такт Преимущества Наибольшая пропускная способность и наименьшая задержка на декодирование Недостатки Наибольшее количество ресурсов и затруднительность трассировки 672 аппаратных кодовых узла 336 аппаратных проверочных узлов 4368 соединений

[9] Слоистая архитектура декодера Реализует LBP алгоритм – требует свойства слоистости Переиспользует аппаратные проверочные узлы между под итерациями Упрощается аппаратная архитектура кодовых узлов Одна под итерация выполняется за один такт – требуется 4 такта для выполнения одной итерации 672 упрощенных кодовых узлов 84 битовых узлов 2 переконфигурируемых 672-на-672 коммутатора 672 линии задержки

[10] Последовательно-параллельная архитектура Использует квазициклическое свойство кода Разбивает одну итерацию LBP алгоритма на N ne под итераций – 52 такта на выполнение одной итерации Последовательно одновременно обновляются Z кодовых и проверочных узлов Сообщения распределяются с помощью Z-на-Z коммутатора, управляемого значением циклического сдвига 42 кодовых узла 42 проверочных узла 2 переконфигурируемых 42-на-42 коммутатора сообщений

[11] Сравнительный анализ архитектур декодера 1/2 Пропускная способность аппаратного LDPC декодера: N iter выбирается как среднее число итераций для рабочего значения отношения сигнал-шум Используемая аппаратная платформа – ПЛИС Xilinx Kintex7 XC7K325T (speed grade -2) Единицы измерения аппаратных ресурсов - Slice LUTs и Slice registers Аппаратная эффективность декодера – отношение пропускной способности декодера к числу задействованных Slice LUT (1 Мбит/с к 1000 LUT) f - частота тактирования блока, L – длина кодового слова в битах, R – скорость кода, N iter – число итераций декодирования S – число тактов выполнения одной итерации

[12] Сравнительный анализ архитектур декодера 1/2 Полностью параллельная Наибольшая пропускная способность Гбит/с Лучшая аппаратная эффективность на 1 Мбит/с пропускной способности Слоистая архитектура 2.08 Гбит/с пропускной способности – результат пере использования проверочных узлов и лучшей сходимости На 42% ниже аппаратная эффективность Последовательно-параллельная архитектура Самая компактная аппаратная реализация - 11% используемых ресурсов от полностью параллельного случая Результирующая пропускная способность Мбит/с Fully parallel Layered Serial- Parallel Число тактов одной итерации декодирования, S 1452 Число итераций декодирования, N iter Пропускная способность, Мбит/с LUTs, абсолютное LUTs, относительное % Число регистров, абсолютное Число регистров, относительное % Аппаратная эффективность, Mbit/s/1K LUT Частота тактирования цифрового блока декодера единая для всех архитектур и равна 100 МГц

[13] Заключение Представлены результаты для трех аппаратных реализаций декодера LDPC кода стандарта IEEE ad Полностью параллельная архитектура – рекомендуется для задач требующих максимальную пропускную способность и минимальную задержку на декодирование Слоистая архитектура – является промежуточным решением между последовательно-параллельным и полностью параллельным вариантами Последовательно-параллельная архитектура – является платформой LDPC декодера для систем с относительно низкой пропускной способностью, но значительными аппаратными ограничениями Использование малого числа ресурсов позволяет увеличить пропускную способность за счет параллельного использования нескольких декодеров

[14] Спасибо за внимание!

[15] Описание алгоритма Belief Propagation 1/2 В рамках одной итерации алгоритма последовательно обновляются проверочные и кодовые узлы o Обновление проверочных узлов o Обновление кодовых узлов Проверочный узел CNm формирует сообщение r m,n (k) каждому смежному с ним n-ому кодовому узлу VNn согласно: q j,m (k-1) – сообщение от кодового узла j к проверочному узлу m на (k-1)-ой итерации, N m –множество индексов кодовых узлов смежных с проверочным CNm Кодовый узел VNn обрабатывает входные сообщения от смежных проверочных узлов, вычисляя сообщение для проверочного узла CNm M n – множество индексов проверочных узлов смежных с кодовым VNn

[16] Описание алгоритма Belief Propagation 2/2 Пересчет LLR бит кодового слова производится на каждой итерации на основе сообщений от проверочных узлов Обновленные метрики бит используются для получения «жесткого» решения для каждого бита кодового слова, используемого для вычисления синдрома ошибок Алгоритм завершает работу, если значение синдрома ошибки s равно нулевому вектору или при выполнении алгоритмом максимального количества итераций K max Λ n (k) - LLR of n-th bit of the decoded codeword at k-th iteration