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

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

Каково распределение степеней в кодах LDPC?

Распределение степеней — это краткое математическое описание схемы подключения в графе Таннера. Для заданного кода LDPC для захвата этой информации используются два полинома:

  • Распределение степени переменного узла (λ(x)): Многочлен λ(x) = Σ λi x^(i-1), где λi представляет собой долю краев, соединенных с переменными узлами степени i.
  • Проверить распределение степени узла (ρ(x)): Аналогично, ρ(x) = Σ ρi x^(i-1), где ρi представляет собой долю краев, соединенных с контрольными узлами степени i.

Эти полиномы обеспечивают компактный способ описания нерегулярности графа. В регулярном коде LDPC каждый переменный узел имеет одинаковую степень (dv) и каждый узл проверки имеет одинаковую степень (dc). Например, (3,6)-регулярный код имеет все переменные узлы, подключенные к 3 контрольным узлам, и все узлы проверки, подключенные к 6 переменным узлам. Напротив, нерегулярные коды LDPC позволяют изменяться степеням переменных и узлов проверки, часто приводя к лучшей производительности. Распределение степени нормализуется так, что фракции суммируются в одну, и скорость кода может быть получена из средних степеней узла.

Полиномиальное представление и его значение

Полиномы λ(x) и ρ(x) не просто описательные; они являются важными инструментами для анализа и проектирования. С помощью таких методов, как эволюция плотности, эти полиномы непосредственно определяют итеративное поведение декодирования. Структура λ(x) и ρ(x) влияет на поток внешней информации между переменными и контрольными узлами во время распространения убеждений. Например, переменный узел с высокой степенью получает больше информации от нескольких контрольных узлов, что может помочь быстрее исправить ошибки. Однако он также становится более чувствительным к корреляции в входящих сообщениях, потенциально вызывая явление, известное как «графовые циклы», которые ухудшают производительность.

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

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

Регулярные коды LDPC предлагают простоту и предсказуемую производительность, но они, как правило, неоптимальны с точки зрения порога. Нерегулярные коды, впервые предложенные Ричардсоном, Шокроллахи и Урбанке, могут достигать порогов, чрезвычайно близких к пределу Шеннона. Например, оптимизированный нерегулярный код на канале бинарной входной добавки белого гауссовского шума (BI-AWGN) может работать в пределах 0,0045 дБ мощности Шеннона, что невозможно при регулярных структурах. Причина заключается в эффекте «концентрации»: переменные узлы низкой степени помогают поддерживать стабильность декодера при низких SNR, в то время как переменные узлы высокой степени обеспечивают силу, необходимую для коррекции ошибок при более высоких SNR. Взаимодействие между этими узлами захватывается диаграммой EXIT (Extrinsic Information Transfer), которая визуализирует динамику передачи сообщений.

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

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

Порог декодирования, пожалуй, является наиболее важной метрической величиной для кодов LDPC. Он определяет границу между надежным и ненадежным декодированием. В контексте канала BI-AWGN порог обычно выражается в терминах SNR (Eb/N0), ниже которого резко падает скорость бит-ошибки (BER). Распределение степеней непосредственно формирует этот порог, определяя способность кода распространять информацию через граф.

Понимание порогов декодирования

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

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

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

Связь между распределением степени и порогом может быть понята через линзу диаграмм внешней передачи информации (EXIT). Эти диаграммы отображают взаимную информацию, обмениваемую между переменными узлами и контрольными узлами во время итеративного декодирования. Каждый тип узла имеет характерную кривую EXIT, которая зависит от его распределения степени. Сходимость декодера требует, чтобы кривая переменного узла находилась выше кривой контрольного узла во всех точках; точка пересечения определяет порог. Путем корректировки λ(x) и ρ(x) конструкторы могут формировать эти кривые, чтобы обеспечить широкую «туннель» для итеративного декодирования, приближая порог к пропускной способности канала.

Практические примеры иллюстрируют этот эффект. Рассмотрим (3,6)-регулярный код на канале BI-AWGN. Его порог составляет примерно 1,11 дБ, по сравнению с пределом Шеннона 0,187 дБ для кода скорости-1/2. Тщательно проектируя нерегулярное распределение (например, λ(x) = 0,38354x2 + 0,04237x3 + 0,57409x10 и ρ(x) = 0,2423x4 + 0,78877x5), порог может быть улучшен до уровня 0,17 дБ от предела Шеннона. Это резкое улучшение происходит из-за нерегулярности: переменные узлы низкой степени (степень 2) стабилизируют декодер при низких SNR, в то время как узлы высокой степени (степень 10) обеспечивают необходимую мощность коррекции.

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

Ошибка напольного покрытия

В то время как порог является основным фокусом для большинства приложений, пол ошибок имеет решающее значение в сценариях, требующих чрезвычайно низких BER, таких как оптические коммуникации или глубокие космические связи. Пол ошибок возникает из подструктур в графе Таннера, которые вызывают отказ итеративного декодера. Распределение степени влияет на количество и тяжесть этих подструктур. Например, высокая доля переменных узлов степени 2 может привести к низкому весу кодовых слов и высокому уровню ошибки. И наоборот, увеличение минимальной степени переменного узла или использование тщательно разработанного неправильного распределения может повысить уровень ошибки, но может принести в жертву некоторую пороговую производительность. Современные методы оптимизации, такие как ACE (Approximate Cycle Extrinsic message degree) и PEG (Progressive Edge Growth) , сосредоточены на построении графов, которые избегают вредных подструктур при соблюдении распределения целевой степени.

Стратегии проектирования для оптимизации производительности

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

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

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

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

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

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

Алгоритмы оптимизации

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

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

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

5G и беспроводные коммуникации

Стандарт 5G New Radio (NR) использует коды LDPC для каналов данных. Эти коды используют семейство совместимых со скоростью конструкций с оптимизированными распределениями степеней для поддержки переменных скоростей кода и высокой пропускной способности. Коды 5G LDPC имеют структуру базового графа, которая позволяет эффективно кодировать и декодировать при сохранении производительности на уровне близкой к емкости. Распределения степеней были тщательно отобраны для обеспечения высокой параллелизации в аппаратном обеспечении, поддерживая скорость передачи данных в десятки гигабит в секунду. Продолжаются исследования адаптивных распределений степеней для 6G, которые могут вводить массивные MIMO и миллиметровые каналы с уникальными затухающими профилями.

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

Спутниковые линии связи, такие как используемые в DVB-S2 и DVB-S2X, полагаются на коды LDPC с порогами, оптимизированными для условий с низким SNR. Эти каналы страдают от длительных задержек распространения и бюджетов низкой мощности, что делает каждый dB кодирования критическим. Распределения степеней для кодов спутников LDPC часто подчеркивают низкие полы ошибок и надежную производительность при фазовом шуме. Глубоководные миссии, как те, которыми управляют НАСА и ЕКА, используют коды LDPC с чрезвычайно низкими скоростями кода (например, 1/6), чтобы работать намного ниже предела Шеннона. Распределения степеней для таких кодов очень нерегулярны, со многими переменными узлами низкой степени для обеспечения стабильности при очень низких SNR.

Системы хранения данных

В магнитном и твердотельном накопителях коды LDPC заменили более старые коды Reed-Solomon из-за их превосходной производительности при наличии ошибок разрыва и интерсимволических помех. Современные жесткие диски используют коды LDPC с квазициклическими (QC) структурами, которые обеспечивают эффективную реализацию аппаратных средств. Распределения степеней оптимизированы для балансировки порога с полом ошибок, поскольку системы хранения требуют BER ниже 10-15. В недавней работе исследуются распределения переменной степени, которые адаптируются к соотношению сигнал-шум считываемого канала, концепции, известной как «адаптивное к скорости» кодирование LDPC. Этот подход позволяет диску максимизировать плотность хранения во время нормальной работы и переключаться на более сильное кодирование при увеличении ошибок.

Будущие исследования

Продолжает развиваться область оптимизации распределения степеней. К ключевым направлениям активных исследований относятся:

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

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

Заключение

Распределение степени кода LDPC - это не просто математическая деталь - это основной рычаг для управления порогом кода, полом ошибок и сложностью. Понимая, как λ(x) и ρ(x) влияют на процесс итеративного декодирования, инженеры могут разрабатывать коды, которые работают в ширине волоса от мощности Шеннона. Взаимодействие между регулярными и нерегулярными структурами, использование эволюции плотности и диаграмм EXIT и продолжающийся поиск адаптивных кодов - все указывает на будущее, где коды LDPC расширяются, спутники исследуют глубокий космос, а плотности хранения выдвигают физические ограничения, оптимизация распределения степени останется краеугольным камнем рецензируемых исследований в теории кодирования. Для практиков, овладение дизайном распределений степени имеет важное значение для построения систем, которые являются надежными и эффективными, гарантируя, что цифровая связь продолжает удовлетворять растущим требованиям информационной эпохи.