Рассматривается несколько подходов к аппаратной реализации декодеров LDPC-кодов на примере наиболее известных алгоритмов декодирования: Belief Propagation (BP), Uniformly Most Powerful Belief Propagation (UMP BP), многопороговое декодирование (MT) и турбодекодирование на примере турбодекодера с ядром BCJR. Сравнение различных схем рассматривается на примере LDPC-кода (2048, 1723), принятого в стандарт IEEE 802.3an (стандарт физического уровня сети 10G Ethernet).

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

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

Одна итерация каждого алгоритма декодирования состоит из двух фаз: в первой фазе происходит обновление надежностей всех проверочных вершин на основании надежностей символьных вершин, во второй – обновление всех надежностей символьных вершин на основании надежностей проверочных вершин. В каждой фазе обновление надежностей для каждой вершины происходит независимо и, следовательно, может выполняться параллельно. Представление проверочной матрицы LDPC-кода в виде графа Таннера дает простой и естественный способ аппаратной реализации декодера. В данном случае символьные и проверочные вершины графа Таннера реализуются аппаратно как соответствующие вычислительные элементы (символьные и проверочные), а ребра графа задают систему связей (шин и проводов) между вычислительными элементами и блоками памяти, хранящими значения вычисляемых в процессе декодирования надежностей. Далее вычислительные элементы, соответствующие проверочным вершинам, будем обозначать CNU (check node processing unit), а элементы, соответствующие символьным элементам, – VNU (variable node processing unit).

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

Для коммутации сигналов между ячейками памяти и вычислительными элементами используется специальный блок «маршрутизатор», который может быть выполнен на базе стандартных логических элементов: мультиплексоров и демультиплексоров. При этом потребуется:

1. NCNU ρw-битных [R/ NCNU ] →1 мультиплексоров для коммутации сигналов, передаваемых от ячеек памяти к проверочным элементам, где NCNU – количество проверочных элементов в схеме; ρ – количество единиц в строке проверочной матрицы; w– разрядность коммутируемых надежностей (количество битов, требуемое для хранения одной надежности); R – количество строк в проверочной матрице. Как правило, это число равно 5–7 битам в зависимости от алгоритма декодирования и реализации.

2. NCNU ρw-битных 1→[R/ NCNU ] демультиплексоров для коммутации сигналов, передаваемых от проверочных элементов к ячейкам.

3. N VNU (γ+1) w-битных [N/ NCNU ] →1 мультиплексоров для коммутации сигналов, передаваемых от ячеек памяти к символьным элементам, где N VNU – количество символьных элементов в схеме; γ –количество единиц в столбце проверочной матрицы; N – длина кода.

4. N VNU γw-битных 1→[N/ NCNU ] демультиплексоров для коммутации сигналов, передаваемых от символьных элементов к ячейкам памяти.Видно, что количество логических элементов, требуемых для реализации «маршрутизатора», не зависит от количества вычислительных элементов в схеме, а зависит лишь от размеров проверочной матрицы кода и количества единиц в строках и столбцах этой матрицы.

Под пропускной способностью декодера традиционно понимается среднее количество битов в единицу времени, обрабатываемое или выдаваемое декодером. Здесь под пропускной способностью будем понимать количество информационных битов, выдаваемых декодером. Пропускная способность декодера зависит не только от степени параллельности вычислений в схеме декодирования. Другим важным фактором является время работы вычислительных элементов. Для различных декодеров это время различно. В табл. 1 приведено время работы вычислительных элементов (символьных и проверочных) для рассматриваемых в статье декодеров. Для каждого декодера оценкавремени работы была получена путем синтеза вычислительных элементов для реализации на ASIC при использовании библиотеки элементов TSMC 0.18 мкм.

Из табл. 1 видно, что для одного и того же кода и одной и той же степени параллельности схемы декодирования максимальная пропускная способность разных декодеров будет различна, поскольку в разных декодерах отличается время работы вычислительных элементов. В табл. 2 приведены оценки пропускной способности каждого декодера для различных схем. Здесь и далее сравнение различных схем декодирования проводится на примере декодеров, построенных для декодирования (2048, 1723) LDPC-кода, содержащего 384 проверки, 32 единицы в строках и 6 единиц в столбцах проверочной матрицы. Предполагается, что декодирование состоит из 10 итераций.

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

Потенциально пропускная способность декодеров BP, UMP BP и MT может быть увеличена за счет использования двух тактовых генераторов и независимого тактирования символьных и проверочных элементов. Но использование двух тактовых генераторов сильно усложнило бы процесс работы с памятью (чтение/запись надежностей), а как следствие, и аппаратную реализацию декодера в целом. Второй способ увеличения пропускной способности состоит в использовании конвейерных вычислений в вычислительных элементах. Использование конвейеров разной длины в проверочных и символьных элементах позволяет «выровнять» частоты работы этих элементов и увеличить, таким образом, общую пропускную способность декодера. Пример реализации конвейера длины 3 в проверочном элементе алгоритма MT приведен схематично на рис. 3. Пропускная способность различных декодеров при использовании конвейерных вычислений представлена в табл. 3.

Из табл. 2 и 3 видно, что прирост производительности от использования конвейерных вычислений для различных декодеров различен и зависит от степени параллельности в схеме реализации. Для полностью параллельной схемы прирост может быть получен только для декодеров BP, MT и UMP BP, поскольку для них конвейерные вычисления позволяют «выровнять» частоты проверочных и символьных вычислительных элементов. Для этих декодеров прирост производительности в полностью параллельной схеме составил 13–16%. В полностью параллельной реализации турбодекодера, наоборот, наблюдается некоторое падение производительности. Происходит это из-за того, что элементы памяти, формирующие задержки в конвейерах, увеличивают время работы символьного вычислительного элемента, а из-за отсутствия в явном виде проверочного вычислительного элемента не «выравниваются» частоты. Для частично-параллельной схемы реализации прирост производительности от использования конвейерных вычислений существует для всех декодеров, в том числе для турбодекодера. Причем, чемменьше степень параллельности и чем больше длина конвейеров, тем выше прирост производительности. Так, для декодеров BP, MT и UMP BP использование конвейерных вычислений в схеме с одним проверочным и одним символьным вычислительным элементом обеспечивает прирост производительности приблизительно в 3 раза, а для турбодекодера – в 5 и 18 раз для быстрой и традиционной схем реализации алгоритма BCJR соответственно.

Для схемы, в которой количество вычислительных элементов равно 1/4 от количества, необходимого для полностью параллельной реализации, т. е. для схемы со степенью параллельности 1/4, прирост производительности для декодеров BP, MT и UMP BP составил 100–106%, а для турбодекодера – 150 и 200% для быстрой и традиционной схем соответственно.

Платой за такое увеличение пропускной способности является увеличение количества элементов памяти, необходимых для формирования задержки сигналов в конвейерах, которое приводит к росту общей площади кристалла. Причем, чем больше длина конвейера, тем больше требуется элементов памяти и тем сильнее увеличивается площадь кристалла. Так, для полностью параллельной реализации декодеров BP, MT и UMP BP при использовании конвейеров длины 2 и 3 в символьных и проверочных элементах соответственно рост площади составил 12–34%, для быстрой реализации турбодекодера с конвейером длины 6–15%, для традиционной реализации с конвейером длины 32 – почти в 2 раза.

Оценка пропускной способности и площади кристалла для различных схем реализации декодеров

Оценка пропускной способности и площади для различных схем реализации рассматриваемых декодеров представлена на рис. 4–7. Оценка пропускной способности была получена путем независимого синтеза всех вычислительных элементов декодера, определения частоты работы каждого элемента и последующего вычисления оценки по формуле:

C = Fbmin /Nclks*K,

где Fbmin – частота работы наиболее медленного элемента декодера; Nclks – количество тактов, необходимых для декодирования одного кодового слова; K – количество информационных символов в одном кодовом слове.

Рис. 5. Характеристики декодера MT: а – оценка пропускной способности; б – оценка площади;

Оценка площади была получена по формуле:

S = ScnuNcnu + SvnuNvnu + S0,

где Scnu – площадь проверочного элемента; Ncnu – количество проверочных элементов в схеме; Svnu – площадь символьного элемента;

Nvnu – количество символьных элементов; S0 – сумма площадей остальных вычислительных элементов, включая входные и выходные буферы, блок инициализации, блок управления, блоки коммутации сообщений между памятью и вычислительными элементами и т. д.

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

При использовании полностью параллельной архитектуры (см. рис. 4–7) пропускная способность декодеров BP, UMP BP и MT достигает 6–8,5 Гб/с. Таким образом, параллельная архитектура может быть использована на физическом уровне высокоскоростных протоколов передачи данных (например, в сети 10G Ethernet или в других средствах связи, пропускная способность которых составляет до 10 Гб/с) для исправления ошибок, возникающих при передаче данных в каналах связи. Сравнивая площади различных декодеров, можно видеть, что площадь декодера Belief Propagation оказывается наименьшей. Однако так называемые «быстрые декодеры» (UMP BP и MT) могут быть эффективно реализованы с использованием параллельных ассоциативных вычислений (ассоциативных процессоров) [9]. При этом при использовании ассоциативных вычислений кажется возможным уменьшить площадь декодеров минимум в 1,5–2 раза, хотя для получения точных оценок требуются дополнительные исследования. Таким образом, с учетом качества декодирования алгоритмы Belief Propagation и Multi-Threshold являются наиболее подходящими кандидатами для реализации в высокоскоростных схемах передачи. В приложениях, где требуемая пропускная способность не превышает 1–2 Гб/с (например, в протоколах беспроводной связи), может использоваться частично-параллельная архитектура. В таком случае наилучшим вариантом оказывается турбодекодер, пропускная способность которого оказывается достаточной, а качество работы выше, чем у других декодеров.

Используемая литература:

1.А. Г. Ефимов, ОБ АППАРАТНОЙ РЕАЛИЗАЦИИ ДЕКОДЕРОВ LDPC- КОДОВ

2.А. А. Овчинников, К ВОПРОСУ О ПОСТРОЕНИИ LDPC- КОДОВ НА ОСНОВЕ ЕВКЛИДОВЫХ ГЕОМЕТРИЙ

3.ВОПРОСЫ ПЕРЕДАЧИ И ЗАЩИТЫ ИНФОРМАЦИИ. Сборник статей под редакцией доктора технических наук, профессора Е. А. Крука, Санкт-Петербург 2006