Влияние оптимизации распределения степеней на пороговые значения кода Ldpc и производительность

Введение в коды LDPC и важность распределения степеней

Коды с низкой плотностью паритетной проверки (LDPC) являются краеугольным камнем современной коррекции ошибок, обеспечивающей надежную передачу данных по шумным каналам. Впервые открытые Робертом Галлагером в его докторской диссертации 1960 года, коды LDPC в течение десятилетий были в значительной степени упущены из виду из-за вычислительной сложности их алгоритмов декодирования.Возобновление этих кодов в середине 1990-х годов в сочетании с достижениями в аппаратном и итеративном декодировании привело к их широкому использованию в таких стандартах, как DVB-S2, Wi-Fi (IEEE 802.11n), 5G NR и спутниковая связь.

Производительность кода LDPC внутренне привязана к его распределению степени, которое определяет, сколько связей (краев) каждый переменный узел (представляющий биты) и каждый узл проверки (представляющий ограничения четности) обладает в графе Tanner кода & #8217. Оптимизация этих распределений степени - это не просто теоретическое упражнение; это непосредственно определяет способность кода & #8217 приближаться к мощности Шеннона, его порогу декодирования и его поведению на уровне ошибок. В этой статье исследуется влияние оптимизации распределения степени на пороги кода LDPC и производительность, обеспечивая всеобъемлющий взгляд на базовую теорию, ключевые методы оптимизации и реальные последствия.

Понимание кодов LDPC и распределения степеней

Структура графа Таннера

Код LDPC определяется разреженной матрицей проверки четности H, которая может быть представлена в виде двухстороннего графа, известного как граф Таннера. Граф состоит из двух разрозненных наборов узлов: переменных узлов (по одному для каждого бита кодового слова) и контрольных узлов (по одному для каждого уравнения проверки четности). На эдах подключение переменного узла к контрольному узлу, если соответствующая запись в H ненулевое (обычно 1 в двоичных кодах LDPC).H гарантирует, что граф имеет относительно мало соединений, что позволяет эффективно итеративное декодирование с использованием распространения убеждений (алгоритм sum-product) или алгоритмы min-sum.

Степень узла — это число ребер, падающих на него.Распределение степени для переменных узлов, обозначаемое λ(x), и для контрольных узлов, обозначаемое ρ(x), обычно выражается полиномами:

Эти многочлены удовлетворяют λ(1) = ρ(1) = 1 и определяются по краю перспективы, а не по узлу перспективы, что упрощает анализ эволюции плотности.Скорость проектирования кода может быть вычислена как R = 1 – (∑ ρj/j]/ (∑ λ]i/i).

Регулярные и нерегулярные распределения степеней

Ранние коды LDPC были регулярными: каждый переменный узел имел одинаковую степень (например, 3), а каждый контрольный узел имел одинаковую степень (например, 6). Регулярные коды просты в построении, но часто демонстрируют неоптимальные пороги. Нерегулярные коды LDPC, введенные Luby, Mitzenmacher, Shokrollahi и Spielman в конце 1990-х годов, позволяют переменным и контрольным узлам иметь разные степени. Эта гибкость может значительно улучшить порог кода & #8217. Например, некоторые переменные узлы высокой степени действуют как & #8220; Heavy & #8221; узлы, которые получают сильную внешнюю информацию от нескольких контрольных узлов, в то время как переменные узлы низкой степени более уязвимы, но помогают сохранить разреженный график. Оптимальное распределение степени для заданной скорости и канала - тонкий баланс, который максимизирует порог.

Роль оптимизации распределения степеней

Основная цель оптимизации распределения степени состоит в максимизации порога декодирования, определяемого как самый высокий параметр канала (например, дисперсия шума & #963; 2 для каналов AWGN, или вероятность кроссовера p для двоичных симметричных каналов), при которой итеративный декодер все еще может достигать произвольно низкой вероятности ошибки, поскольку длина блока стремится к бесконечности. Этот порог является фундаментальным пределом производительности ансамбля кода, независимо от конкретной конструкции кода. Оптимизированные распределения степени могут привести порог чрезвычайно близко к пределу пропускной способности Шеннона, часто в пределах долей децибела.

Помимо пороговых значений, распределение степеней также влияет на другие показатели эффективности:

  • Пол ошибки: Область с высоким отношением сигнал/шум, где вероятность ошибки медленно уменьшается из-за небольших наборов захвата или поглощающих наборов. Правильный дизайн распределения степени может поднять пол ошибки или полностью устранить его.
  • Скорость сближения: Количество итераций декодирования, необходимых для достижения правильного кодового слова. Распределения, которые обеспечивают более надежные сообщения на ранней стадии, могут уменьшить задержку.
  • Минимальное расстояние: Самый маленький вес Хамминга ненулевого кодового слова.В то время как коды LDPC обычно имеют относительно небольшие минимальные расстояния, распределение степеней влияет на скорость роста минимального расстояния с длиной блока.
  • Сложность: Узлы более высокой степени требуют большего количества вычислений на итерацию; оптимизация должна сбалансировать пропускную способность и потребление энергии.

Ключевые методы оптимизации

Эволюция плотности

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

EXIT Chart Анализ графиков

Внешние диаграммы передачи информации (EXIT), введенные десятью Бринками, обеспечивают графический метод визуализации обмена взаимной информацией между декодерами переменных узлов (VND) и декодерами контрольных узлов (CND). Нанося на график характеристики взаимной передачи информации обоих декодеров, можно определить, будет ли итеративное декодирование сходится с низкой вероятностью ошибки. Область под кривой EXIT связана с скоростью кода и порогом. Графики EXIT намного быстрее эволюции полной плотности и широко используются для быстрого прототипирования градусных распределений, особенно для двоичных входных каналов AWGN.

Генетические алгоритмы и эволюционный поиск

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

Линейные методы программирования

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

Альтернативная оптимизация и эвристические правила

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

Влияние на пороговые значения и производительность

Приближаясь к пределу Шеннона

Одним из наиболее ярких достижений оптимизации распределения степеней является способность приближаться к мощности Шеннона произвольно близко. Например, было показано, что нерегулярные коды LDPC с оптимизированными распределениями работают в пределах 0,0045 дБ предела пропускной способности для канала бинарного стирания (BEC). Для канала AWGN пороги в пределах 0,1 дБ емкости обычно сообщаются для умеренных длин блоков. Это сопоставимо или лучше, чем турбокоды, которые были доминирующими кодами, приближающимися к емкости до возрождения LDPC.

Пороговое насыщение с помощью спациально связанных кодов LDPC

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

Уменьшение этажа ошибки

В то время как высокие пороги необходимы для работы в области водопада (умеренное SNR), многие приложения (например, оптическое хранилище, связь в глубоком космосе) также требуют чрезвычайно низких погрешностей, часто ниже 10 15 битовой частоты ошибок. Оптимизация распределения степени может помочь смягчить погрешности, избегая небольших наборов ошибок. Набор ловушек - это подграф из переменных узлов, который при итеративном декодировании остается в ошибке. Обеспечивая, что переменные узлы степени 2 минимальны и что градусы проверки достаточно велики, можно проектировать распределения, которые свободны от доминирующих наборов ловушек. Такие методы, как оптимизация ACE (Approximate Cycle Extrinsic) и PEG (Progressive Edge-Growth) строительные работы рука об руку с дизайном распределения степени для получения кодов конечной длины с низкими погрешностями.

Скорость и задержка сходимости

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

Практическое применение и будущие направления

5G NR и другие

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

Спутниковые и дальнекосмические коммуникации

В спутниковых линиях, где отношение сигнал/шум часто очень низкое, используются оптимизированные коды LDPC с низкоскоростными распределениями степеней (например, скорость 1/3 или 1/4). CCSDS (Консультативный комитет по космическим системам данных) стандартизировал коды LDPC с почти емкостью для телеметрии и телекоманд. Распределения степеней для этих кодов были получены посредством обширной эволюции плотности и анализа диаграмм EXIT для обеспечения надежной производительности при сильном затухании и доплеровских эффектах.

Оптические коммуникационные системы

Длинномагистральные оптоволоконные линии все чаще полагаются на коды LDPC для борьбы с шумом от усилителей и нелинейностей. Однако оптические каналы часто имеют ограничения квантования с мягким решением и асимметричные распределения шума. Оптимизация распределений степени для таких каналов требует изменения контекста эволюции плотности (например, с использованием дискретных распределений или моделей гауссовской смеси). Недавние работы показали, что адаптированные нерегулярные коды LDPC могут превосходить стандартные обычные коды на 0,5 дБ или более в реалистичных моделях оптических каналов.

Хранение данных и флэш-память NAND

Флэш-память NAND страдает от ошибок из-за цикличности программы/удаления, удержания и нарушения чтения. Коды LDPC с оптимизированными распределениями степеней теперь стандартны в высокопроизводительных твердотельных накопителях (Solid-State Drives). Канал сильно асимметричен с квантователем мягкого выхода; оптимизация распределения степеней должна учитывать неравномерную дисперсию шума на уровнях памяти. Используются низкоскоростные коды (около 0,7 до 0,9), а дизайн часто фокусируется на снижении уровня ошибок до уровня ниже 10-15 для удовлетворения требований к надежности предприятия.

Квантовые коды LDPC

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

Адаптивная и машинная оптимизация

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

Заключение

Оптимизация распределения степеней - это не просто академическое упражнение; это ключ к раскрытию полного потенциала кодов LDPC в широком спектре технологий связи и хранения. Тщательно выбирая граничные связи между переменными и контрольными узлами, инженеры могут произвольно приближать пороги кода к пределу Шеннона, уменьшать уровни ошибок до незначительных уровней и адаптировать поведение конвергенции к ограничениям задержки и сложности, характерным для приложений. Такие методы, как эволюция плотности, диаграммы EXIT, генетические алгоритмы и линейное программирование, обеспечивают надежный инструментарий для этой оптимизации. По мере того, как стандарты развиваются в направлении 6G, квантовых сетей и сверхнадежных систем с низкой задержкой, постоянное уточнение дизайна распределения степеней останется критическим фактором коррекции ошибок следующего поколения. Исследователи и практики должны инвестировать в понимание этих принципов для разработки кодов, которые не только отвечают, но и превосходят требования будущих систем связи.

Дальнейшее чтение