Исследование LDPC декодеров

Введение

После привлечения внимания к LDPCкодам в середине 90-х [1] много усилий было направлено на их исследование. Благодаря своей корректирующей способности эти коды уж стали частью некоторых современных стандартов передачи данных, таких как DVB-S2, 10 GigabitEthernet, WiMAX, Wi-Fi. Однако декодеры таких кодов на данный момент имеют множество ограничений, и их проектирование представляет сложную задачу.

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

Декодирование LDPC кодов

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

Будем рассматривать лишь алгоритмы мягкого декодирования. На вход декодера поступают логарифмы отношений правдоподобия принятых символов:

Алгоритмы декодирования представляют собой алгоритмы передачи сообщений между двумя типами вершин. Подробное их описание можно найти в [2][3]. Здесь приведем формулы вычисления сообщений для двух наиболее часто используемых алгоритмов. Первый алгоритм является классическим алгоритмом сумма-произведение (SPA). В его случае сообщения от кодовой вершины к проверочной описываются выражением:

Сообщения от проверочной вершины к кодовойописываются выражением:

где , и

Второй алгоритм называется алгоритмом минимума суммы (MinSum, MS) и использует тот факт, что значение функциивелико лишь при малых аргументах, что приводит к следующей формуле:

Алгоритм MSупрощает вычисления, но при этом снижается энергетический выигрыш от кодирования.

Архитектуры декодеров

В общем случае можно выделить три основных класса архитектур декодеров: параллельная, последовательная и частично параллельная. Базовыми элементами в структуре декодера при любой архитектуре являются блоки вычисления значений (Блок Символ-Проверка, БСП) и (Блок Проверка-Символ, БПС). Реализация БСПтривиальна, а структураБПС [4] для формулы (3) представлена на рисунке 1. Таблицы используются для вычисления функции .

Рисунок 1. Структура БПС

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

Рисунок 2. Параллельная архитектура.

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

Альтернативой является вычисление сообщений последовательно на нескольких вычислительных блоках. Такая архитектура представлена на рисунке 3.Здесь все вычисления происходят на небольшом числе блоков, а обмен сообщениями осуществляется через память.

Рисунок 3. Последовательная архитектура

Такой подход требует объема памяти, пропорционального числу вершин в графе Таннера, а также быстродействие в значительной мере определяется быстродействием элементов памяти. Однако, такая архитектура является наиболее гибкой. Усовершенствование подхода заключается в использовании памяти, позволяющей чтение нескольких ячеек одновременно, использование банков памяти и планировщиков [4]. Реализуется обычно такая архитектура программно на микропроцессорах и цифровых сигнальных процессорах и как правило ограничивает скорость передачи до нескольких сотен Кб/с [4].

Ещё одним подходом является частично параллельная архитектура [5]. Она предусматривает разбиение проверочной матрицы по строкам и столбцам таким образом, чтобы была возможность вычисления набора сообщений за один цикл. Такой способ потенциально может ограничить применимость данной архитектуры лишь к регулярным кодам, обладает бо̀льшим энергопотреблением и меньшей скоростью, чем полностью параллельная архитектура, но меньшей сложностью реализации. Здесь применяются ASICи ПЛИС.

Проектирование аппаратных декодеров

Максимальная производительность декодера обеспечивается при его реализации в ASIC. В работе [5]выделены шесть основных критериев, которые должны быть учтены при проектировании аппаратного декодера на базе ASIC для конкретного приложения: площадь кристалла, скорость, потребление энергии на бит, задержка, приближение к пределу Шеннона и порог ошибки. Эти факторы, за исключением пощади, применимы и к другим платформам.

Приближение к пределу Шеннона определяет способность декодера работать при большом уровне шумов и практически полностью зависит от выбранного кода. Лучшее приближение к пределу Шеннона имеют сложные нерегулярные коды большой длины, например, в работе [6] продемонстрирован код, который в данный момент имеет наилучшее приближение к пределу Шеннона. Однако сильная нерегулярность связей в графах таких кодов делает их параллельную реализацию практически невозможной, а последовательная приведет к низкой скорости и большим задержкам. К тому же такие коды имеют низкий порог ошибки.

Итеративно декодируемые коды имеют особенность заключающуюся в том, что кривая помехоустойчивостис определенного момента перестает спадать также быстро по мере роста и становится пологой. Это называется порогом ошибки[7]. В некоторых приложениях важно чтобы декодер работал как можно лучше при большой энергии сигнала. Для этого применяют внешние коды, такие как БЧХ, Рида-Соломона.

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

Для многих приложений задержка является важным параметром. Этот параметр определяется во многом архитектурой, а также количеством необходимых итераций, которое зависит как от кода, так и от алгоритма декодирования.

Скорость работы декодера определяет его пропускную способность. Коды LDPC применяются в основном в приложениях с большой скоростью передачи информации. Этот параметр определяется кодом, алгоритмом и архитектурой.

Энергопотребление является важным моментом в беспроводных приложениях. Энергопотребление можно снизить, например, с помощью остановки вычислений после того, как будут выполнены все проверочные уравнения. Для этого требуется на каждом шаге принимать решения относительно символов и делать проверку. Можно также отключать блоки, которые в данный момент не используются.

В работе [5] приведены различные количественные характеристики декодеров и архитектур. Показаны и проанализированы зависимости параметров от технологической базы. На этой основе сделан вывод, что улучшение технологической базы в незначительной степени влияет на параметры декодеров, поэтому исследования в ближайшее время должны быть направлены на поиски оптимальных кодов, архитектурных и алгоритмических решений.

Основываясь также на работе [5] можно сказать, что также приоритетным направлением в исследовании декодеров являются многоскоростные реконфигурируемые декодеры, что обусловлено принятием LDPC кодов во многих стандартах и возможностью их применения в одном устройстве.

Заключение

Таким образом, при проектировании декодера необходимо учитывать множество факторов, чтобы добиться компромисса между различными параметрами, такими как скорость работы, энергопотребление, задержка, приближение к пределу Шеннона, порог ошибки, площадь кристалла (в случае ASIC) . Также важным является время и стоимость разработки и производства. Перспективными направлениями в исследовании декодеров в ближайшее время можно считать построение кодов, разработку архитектур и алгоритмов декодирования, а также многоскоростные и реконфигурируемые декодеры.

Литература:

1. D. MacKay and R. Neal, “Good codes based on very sparse matrices”, 1995

2. William E. Ryan, “An introduction to LDPC codes”, 2003

3. Sarah J. Johnson, “Iterative Error Correction”, 2010

4. Engling Yeo, BorivojeNikoli, and VenkatAnantharam, “Architectures and Implementations of Low-Density Parity Check Decoding Algorithms”, 2002

5. TinooshMohsenin and Bevan Baas, “Trends and Challenges in LDPC Hardware Decoders”, 2009

6. S. Y. Chung, G. D. Forney, T. J. Richardson, R. Urbanke, “On the design of low-density parity-check codes within 0.0045dB of the Shannon limit”, 2001

7. T. J. Richardson, “Error Floors of LDPC Codes”, 2003