Введение в коды проверки паритета низкой плотности

Коды с низкой плотностью проверки паритета (LDPC) являются одними из самых мощных кодов коррекции ошибок в современных цифровых коммуникациях. Впервые введенные Робертом Галлагером в его кандидатской диссертации 1960 года, эти коды были в значительной степени забыты на десятилетия, прежде чем были вновь открыты в середине 1990-х годов. Их способность приближаться к пределу Шеннона с практической сложностью декодирования сделала их краеугольным камнем бесчисленных систем, от спутниковых телевизионных передач до 5G New Radio и NAND flash storage. Ключ к их производительности лежит в очень разреженной матрице проверки четности: большинство записей равны нулю, что упрощает алгоритмы декодирования на основе графов, которые могут быть реализованы в аппаратном обеспечении.

В высокопроизводительных средах программная декодировка просто не может идти в ногу. По мере того, как скорость передачи данных в оптических транспортных сетях возрастает до 100 Гбит/с, требования к декодерам LDPC становятся экстремальными. Это подтолкнуло отрасль к специализированным аппаратным ускорителям, которые используют параллелизм на каждом уровне. Достижения, описанные в этой статье, представляют собой современное состояние в параллельных архитектурах декодирования, предлагая как скорость, так и эффективность для реальных приложений.

Связанная технология: Обзор основ кода LDPC см. в статье Википедия о кодах LDPC .

Теоретический фон: расшифровка алгоритмов

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

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

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

Традиционные архитектуры декодирования и их ограничения

Ранние аппаратные декодеры LDPC использовали полностью последовательный подход: один процессор обновляет каждый переменный узел в свою очередь, затем каждый контрольный узел в свою очередь, повторяясь до конвергенции. Эта последовательная архитектура требует наименьших аппаратных ресурсов — только одного вычислительного блока — но страдает от высокой задержки и низкой пропускной способности. Например, декодеру, обрабатывающему код длиной 10 000 бит, может потребоваться десятки микросекунд на итерацию, что неприемлемо для современных многогигабитных систем.

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

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

Параллельные архитектуры декодирования: состояние искусства

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

Слоеное декодирование

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

Слоевое расписание резко ускоряет конвергенцию. В то время как стандартное расписание затопления обновляет все переменные узлы, а затем все узлы проверки на итерацию, слоистое расписание обновляет как переменные, так и узлы проверки в каждом слое за один проход. Это эффективно уменьшает количество требуемых итераций в два или более раза. Например, слоистый декодер может сходиться в 5-10 итерациях, где декодер затопления нуждается в 20–30. Результатом является пропорциональное снижение задержки.

Слоеные декодеры также предлагают преимущества промежуточной пропускной способности. Поскольку одновременно должны храниться только сообщения для одного слоя, требования к памяти меньше, чем в полностью параллельных конструкциях, что делает многоуровневое декодирование привлекательным для реализации FPGA, где блоковая оперативная память ограничена. Крупные поставщики FPGA предоставляют IP-ядра, которые реализуют многоуровневые декодеры LDPC, совместимые со стандартами Wi-Fi, 5G и спутников.

Пример: Послойный декодер для кода (64800, 64800–17280), используемого в DVB-S2, может достигать пропускной способности, превышающей 1 Гбит/с на современных FPGA Xilinx, как это описано в этой статье IEEE о высокопроизводительных декодерах LDPC .

Пипелиновая обработка

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

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

Интеритерация трубопроводов более агрессивна: она перекрывает обработку итерации i с итерацией i+1. Для этого требуется отсоединение воспоминаний сообщения, чтобы можно было писать, а другое читать. Глубина трубопровода может быть несколько итераций, и следует соблюдать особую осторожность, чтобы избежать опасности данных, когда более поздняя итерация зависит от результатов, которые еще не получены. Некоторые исследования показали, что методы поиска или измененные графики обновлений могут устранить эти опасности, обеспечивая высокую степень параллелизма между ссылками.

Пипелинированные архитектуры обычно используются в реализациях ASIC, где декодер является частью более крупной системы на чипе (SoC). Например, декодер LDPC в процессоре базовой полосы 5G часто использует 4-ступенчатый трубопровод для поддержания пропускной способности 20 Гбит / с при установке в строгой оболочке мощности.

Полностью параллельные архитектуры

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

Цена — огромная аппаратная сложность. Полностью параллельный декодер для кода с 10 000 переменными узлами и 5000 чековыми узлами потребовал бы 15 000 обрабатывающих элементов плюс сеть маршрутизации для их подключения по матрице четности. Проводка доминирует в области чипа. Исторически только очень короткие коды LDPC (с несколькими сотнями бит) могли быть реализованы полностью параллельно на одном чипе.

Однако достижения в технологии ASIC — сокращение технологических узлов, плотная 3D-интеграция и высокоширотные сети на чипах — сделали полностью параллельные декодеры более тягостными. Недавние исследовательские прототипы демонстрируют полностью параллельные декодеры для кодов длиной 2000-4000 бит, которые могут работать при 1-10 Гбит/с. Они по-прежнему не подходят для очень длинных кодов (например, 64k бит для DVB-S2), но они идеально подходят для чувствительных к задержке приложений, таких как оптические межсоединения и спутниковые связи на низкой околоземной орбите.

Казовое исследование: Полностью параллельный декодер LDPC для стандарта IEEE 802.11ad (60 ГГц WiGig) был продемонстрирован в 28-нм чипе CMOS, достигнув 10 Гбит/с с мощностью 350 мВт, как описано в этой статье IEEE Journal of Solid-State Circuits .

Другие известные подходы

Следует упомянуть несколько дополнительных методов параллелизации:

  • Стохастическое декодирование: Представляет сообщения как последовательности случайных битов, позволяя чрезвычайно простое оборудование (один флип-флоп на сообщение) за счет более медленной конвергенции. Параллелизм, естественно, высок, потому что каждый узел работает независимо. Стохастические декодеры были исследованы для очень маломощных приложений, таких как имплантированные медицинские устройства.
  • Quasi-циклические (QC) декодеры LDPC: Большинство современных стандартов используют квазициклические коды LDPC, где матрица проверки четности состоит из круговых смещённых подматриц идентичности. Эта структура позволяет декодеру использовать переключатели ствола или сети перестановок для маршрутизации сообщений между элементами обработки, что значительно упрощает межсоединение. Почти все слоистые и частично параллельные декодеры для кодов QC-LDPC используют эту регулярность.
  • Частичные параллельные архитектуры: Компромисс между многоуровневыми и полностью параллельными конструкциями, частично параллельные декодеры назначают фиксированное количество процессорных блоков для обработки нескольких узлов в течение нескольких тактовых циклов. Путем тщательного планирования операций они могут достигать пропускной способности, близкой к полной параллели, используя при этом значительно меньшую площадь.

Аппаратные платформы для реализации декодера LDPC

Выбор платформы — FPGA, ASIC или GPU — сильно влияет на достижимый параллелизм и компромиссы в дизайне.

FPGA-основатели

FPGA предлагают реконфигурируемость, что делает их популярными для прототипирования и для систем, которые должны поддерживать несколько стандартов. Современные FPGA содержат тысячи срезов DSP и обильную блок-ОЗУ, что позволяет использовать многоуровневые декодеры с умеренным параллелизмом. Полностью параллельные декодеры редко реализуются на FPGA из-за перегруженности маршрутизации, но частичные параллельные и многоуровневые конструкции могут достигать многогигабитной пропускной способности. Гибкость FPGA также позволяет адаптировать параметры кода во время выполнения, что ценно для программно-определяемых радиостанций.

ASIC-основатели Decoders

Специфические для приложений интегральные схемы (ASIC) являются рабочими лошадками коммуникационных чипов массового рынка. Они могут интегрировать сотни элементов обработки с пользовательскими иерархиями памяти и выделенной маршрутизацией. ASIC-декодеры для 5G NR и Wi-Fi 6 обычно превышают 10 Гбит/с с использованием многоуровневых или трубопроводных архитектур. Эффективность энергопотребления является ключевым преимуществом: хорошо оптимизированный ASIC-декодер может достигать менее 1 pJ на декодированный бит.

GPU-основанные декодеры

Графические процессоры (GPU) обычно не используются в приемниках производственной связи, но они бесценны для исследований и офлайн-декодирования. Современный GPU может параллельно имитировать тысячи обновлений узлов с помощью своей архитектуры SIMT (одноинструкция, многопоточность). Исследователи используют декодеры на основе GPU для тестирования новых алгоритмов и конструкций кода без обязательств перед аппаратным обеспечением. Однако задержка памяти между CPU и GPU, а также накладные расходы запусков ядра ограничивают пропускную способность для декодирования высокоскоростных потоков данных в режиме реального времени.

Проблемы в параллельном дизайне декодера

Несмотря на впечатляющий прогресс, остаются некоторые препятствия, прежде чем параллельные декодеры LDPC смогут удовлетворить все требования приложений.

  • Потребление энергии: Параллельные процессоры потребляют значительную динамическую мощность. Для устройств с батарейным питанием бюджет мощности может ограничивать степень параллелизма. Часовое сетчатое соединение, масштабирование напряжения и приблизительные вычисления являются активными областями исследований для снижения мощности без больших штрафов за пропускную способность.
  • Программная сложность: Маршрутизация и память, необходимые для высокой параллелизма, увеличивают площадь чипа и усилия по проектированию. Для полностью параллельных декодеров межсоединение может занимать более 70% площади матрицы. Для управления сложностью исследуются иерархические и сетевые архитектуры на чипе.
  • Напольный слой ошибок: Некоторые параллельные архитектуры вводят эффекты квантования или упрощенные алгоритмы, которые вызывают пол ошибок — область, где частота ошибок бита перестает улучшаться по мере увеличения отношения сигнал-шум.
  • Масштабируемость: По мере роста длины кода LDPC (до 64k или 128k бит) становится сложнее поддерживать параллелизм без конфликтов памяти. Слоеные декодеры требуют, чтобы каждый слой обрабатывался без конфликтов; матричный дизайн и алгоритмы наслоения являются активной областью исследований.

Будущие направления

Следующее поколение декодеров LDPC, вероятно, будет сочетать параллелизм с новыми вычислительными парадигмами.

  • Машинное обучение — помощь в декодировании:] Нейронные сети могут быть обучены для приближения алгоритма распространения убеждений, потенциально уменьшая количество итераций при сохранении производительности. Например, декодеры распространения нейронных убеждений используют изученные веса и смещения, и они могут быть реализованы в аппаратном обеспечении с минимальными накладными расходами. Задача состоит в том, чтобы поддерживать адаптивность к различным условиям канала.
  • Перестраиваемые и адаптивные архитектуры: Будущие декодеры могут динамически регулировать степень параллелизма на основе требований к качеству канала и пропускной способности. Например, декодер может переключаться между многоуровневым и полностью параллельным режимами в реальном времени. Для этого требуется гибкая ткань связи и логика управления временем выполнения.
  • Интеграция с квантовой коррекцией ошибок:] По мере созревания квантовых вычислений коррекция ошибок для кубитов потребует чрезвычайно быстрых декодеров — порядка наносекунд. Параллельные декодеры LDPC, вдохновленные классическими конструкциями, оцениваются для поверхностных кодов и других квантовых кодов, исправляющих ошибки, хотя ограничения совершенно разные (например, измерение синдрома неразрушающее).
  • 3D-интеграция и оптические межсоединения: Закладывание памяти гибнет непосредственно поверх логических матриц, что может облегчить узкие места в полосе пропускания памяти. Оптические межсоединения на чипе могут заменить глобальные проводные маршруты в полностью параллельных декодерах, уменьшая задержку и мощность.

Более подробные исследования можно найти в , в этом IEEE Communications Surveys & Учебные материалы по декодерным архитектурам LDPC и в , в этой статье ACM Computing Surveys по энергоэффективным декодерам LDPC .

Заключение

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