Введение в коды LDPC

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

Дизайн для беспроводных датчиков

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

Условия канала и выбор кода

Беспроводные сенсорные сети часто работают в средах со значительными помехами, многолучевым затуханием и различными соотношениями сигнал-шум (SNR). Фиксированная скорость кода может быть не оптимальной во всех условиях. Более низкие скорости кода (например, 1/2) обеспечивают более сильную коррекцию ошибок, но требуют большего количества битов четности, увеличения энергии передачи и задержки. Более высокие скорости кода (например, 3/4 или 7/8) уменьшают накладные расходы, но более чувствительны к нарушениям канала. Для датчиков с низким энергопотреблением адаптивные схемы скорости кода - где скорость кода регулируется на основе оценок канала в реальном времени - могут значительно повысить энергоэффективность, передавая меньше избыточных битов, когда канал хорош. Однако такая адаптивность добавляет сложность к дизайну кодера и декодера.

Ограничения и выбор оборудования

Аппаратное обеспечение сенсорных узлов обычно включает в себя микроконтроллер с малой мощностью с ограниченной памятью на чипе и без выделенного аппаратного ускорителя для коррекции ошибок. Внедрение декодирования LDPC исключительно в программном обеспечении может быстро истощить батарею. Дизайнеры часто выбирают структурированные коды LDPC, которые поддаются эффективным реализациям аппаратных средств, таких как квазициклические (QC) коды LDPC. Эти коды имеют матрицы проверки четности, состоящие из циклических сдвигов матриц идентификации, что позволяет осуществлять простое кодирование и декодирование на основе сдвига регистра. Кроме того, выбор квантования (число битов, используемых для представления внутренних декодирующих сообщений) непосредственно влияет как на использование памяти, так и на производительность декодирования. Грубое квантование (например, 3-4 бита) снижает требования к памяти и логике, но может ухудшить способность коррекции ошибок, в то время как более тонкое квантование (6-8 бит) улучшает производительность за счет более высокого энергопотребления.

Методы кодирования строительства

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

Случайное строительство

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

Структурированное строительство

Структурированные коды LDPC, особенно квазициклические (QC) коды LDPC, предпочтительны для беспроводных датчиков с низким энергопотреблением, поскольку они позволяют компактное представление и кодирование и декодирование с низкой сложностью. Коды QC-LDPC определяются разреженной базовой матрицей, где каждая запись представляет собой матрицу циклической перестановки (или нулевую матрицу) размера Z × Z. Полученный код имеет периодическую структуру, которая упрощает маршрутизацию в декодерах и обеспечивает эффективную параллельную обработку. Стандарты, такие как IEEE 802.11n (Wi-Fi), IEEE 802.16e (WiMAX), и спецификация 5G New Radio все используют коды QC-LDPC. Для WSN, адаптированные коды QC-LDPC могут быть разработаны для удовлетворения конкретных требований длины блока и скорости при сохранении низкой сложности декодера.

Протограф-ориентированные коды

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

Алгоритмы декодирования для низких мощностей

Алгоритм декодирования является основным драйвером энергопотребления в системе LDPC. Существуют два основных класса алгоритмов итеративного декодирования: распространение убеждений (BP) и его упрощенные варианты. Для датчиков малой мощности выбор не только в производительности, но и в количестве операций на итерацию и шаблонах доступа к памяти.

Распространение веры (алгоритм суммарного продукта)

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

Мин-сумма и ее вариации

Алгоритм min-sum упрощает обновление узла BP, заменяя сумму гиперболических касательных минимальной операцией. Это резко снижает вычислительную сложность — умножения заменяются сравнениями — и может быть реализовано с помощью низкоточной арифметики. Потеря производительности по сравнению с BP обычно составляет 0,1—0,3 дБ, что приемлемо для многих приложений WSN. Для восстановления некоторых утраченных характеристик нормализованные и офсетные алгоритмы min-sum применяют масштабирующий фактор (менее 1) к внешним сообщениям, улучшая оценку надежности. Коэффициент масштабирования можно определить офлайн через моделирование и хранить как постоянную, добавляя незначительные накладные расходы.

Для датчиков сверхнизкой мощности даже алгоритм min-sum может быть слишком требовательным. В конструкциях декодера часто используются критерии раннего прекращения — такие как остановка, когда определенное количество проверок четности удовлетворено, или когда проверка синдрома проходит — для прерывания итеративного процесса на ранней стадии, когда декодирование успешно. Это уменьшает среднее количество итераций и, следовательно, энергию на кадр. Другой распространенный метод заключается в использовании квантованного алгоритма min-sum всего с 3 или 4 битами на сообщение, что уменьшает использование памяти и снижает сложность компараторов в аппаратных декодерах.

Слое декодирование и альтернативные подходы

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

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

Компромиссы и оптимизация

Оптимизация кода LDPC для беспроводного датчика включает в себя навигацию по многомерному пространству дизайна.

  • Коды с нижними полом ошибок (нередуцируемые остаточные ошибки при высоком SNR) часто требуют более длинных блоков или более декодирующих итераций, увеличивая мощность. Для многих приложений датчиков приемлем умеренный пол ошибок, если область водопада достаточно крута, чтобы работать в целевом SNR.
  • Длина кода против латентности: Более короткие коды снижают требования к памяти и декодируют латентность, но имеют более слабую коррекцию ошибок.В потоках данных датчиков реального времени ограничения латентности могут заставлять использовать более короткие кадры, которые, в свою очередь, требуют более сильных кодов или лучшей оценки канала.
  • Программный параллелизм против мощности: Полностью параллельный декодер может достигать высокой пропускной способности, но занимает большую площадь чипа и потребляет пиковую мощность. Для датчиков с батарейным питанием более целесообразным является последовательный или полупараллельный декодер, который повторно использует вычислительные блоки в течение нескольких тактовых циклов, даже если он снижает пропускную способность.
  • Точность квантования: Как уже упоминалось, меньшее количество битов уменьшает сложность памяти и компаратора, но может ввести штраф за производительность. Оптимизация битовой ширины для внутренних сообщений и представление внутренних значений канала (например, коэффициентов лог-вероятности) является критическим шагом на этапе проектирования.

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

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

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

Адаптивные и реконфигурируемые коды

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

Машинное обучение — помощь в декодировании

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

Интеграция с энергосбережением и IoT

Поскольку беспроводные датчики все чаще становятся частью Интернета вещей (IoT), они часто полагаются на сбор энергии из источников окружающей среды. Перемежающееся и переменное питание требует, чтобы подсистема связи, включая декодер LDPC, могла работать в широком диапазоне энергетических бюджетов. Расчетные по нагрузке конструкции декодера, которые могут отменять пропускную способность для энергии - за счет снижения тактовой частоты и напряжения питания - могут позволить датчикам поддерживать связь даже в периоды низкой энергии. Аналогично, коды с очень низкой плотностью, которые могут быть декодированы в одной или очень малой плотности (так называемые «коды одной итерации») исследуются для событий сверхнизкой мощности, таких как случайные передачи маяков.

Недвоичные коды LDPC

Небинарные коды LDPC работают над полями Galois более высокого порядка (например, GF(4), GF(8) или GF(16)) и обеспечивают лучшую производительность коррекции ошибок для коротких длин блоков по сравнению с двоичными кодами LDPC. Шкалы сложности декодирования с размером поля, но для небольших полей (например, GF(4)) накладные расходы управляемы. Эти коды особенно привлекательны для сенсорных сетей, которые передают небольшие пакеты (например, 64-256 бит), потому что они могут достигать почти оптимальной производительности без необходимости больших длин блоков. Эффективные реализации небинарных декодеров с использованием быстрого преобразования Фурье (FFT) или алгоритмов на основе треллис являются активной областью исследований.

Заключение

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