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

Введение в коды LDPC и их эффективность

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

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

В этой статье подробно рассматривается оптимизация распределения степеней для кодов LDPC. Сначала мы рассматриваем основы декодирования и порогов LDPC. Затем мы анализируем роль распределений степеней и изучаем классические методы оптимизации, такие как эволюция плотности и диаграммы EXIT. Впоследствии мы адаптируем обсуждение к конкретным моделям каналов - бинарному симметричному каналу (BSC), аддитивному белому гауссовскому каналу шума (AWGN), каналу бинарного стирания (BEC) и каналам затухания Рэлея - показывая, как следует адаптировать распределения. Наконец, мы касаемся соображений конечной длины и практического проектирования кода, поддерживаемого внешними ссылками для дальнейшего чтения.

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

Код LDPC длины n и размерности k определен mnnnmnk[[FLT]]n, как правило, O[n]. В представлении графа Таннера переменные узлы соответствуют столбцам H и проверяют узлы на строки.vv, еслиHc,v[FLT:

Алгоритм декодирования работает путем итеративного обмена сообщениями по этим краям. Для BEC сообщения представляют собой стирания, биты или неизвестные символы. Для симметричных каналов, таких как BSC и AWGN, сообщения представляют собой соотношения лог-вероятности (LLRs). Алгоритм сходится, когда все проверки четности удовлетворяются или после максимального количества итераций. Порог ] определяется через эволюцию плотности: для заданного ансамбля кода (определяемого распределениями степеней) можно вычислить максимальный параметр канала (например, вероятность кроссовера ]p для BSC, дисперсия шума σ2 для AWGN, вероятность стирания ε для BEC) так, что вероятность ошибки декодирования стремится к нулю, как n → ∞. Пороги являются фундаментальной мерой асимптотической производительности ансамбля и служат руководством для практического проектирования код

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

Для переменных узлов, как правило, представлены полиномами.λ[ FLT:51]¹ρx)dx)/₀¹λx)dx.

Выбор распределений критически влияет на поток внешней информации во время декодирования.dv_vvv, после чего пересылает обновленные сообщения обратно., переменные узлы высокой степени получают более разнообразные чековые сообщения, которые могут ускорить конвергенцию, но они также распространяют больше ошибок, если чековые сообщения ненадежны.dddd_{c_,, выполняют операцию чётности; узлы более высокой степени могут обрабатывать больше ограничений, но также создают более длительные циклы в графе, потенциально ухудшая производительность при итеративном декодировании.}

Переменный узел Степень распространения

Распределение степени переменного узла оказывает сильное влияние на порог декодирования кода . В основополагающей работе Luby, Mitzenmacher, Shokrollahi и Spielman (1998) по нерегулярным кодам LDPC было показано, что переменные узлы со смесью степеней — некоторые высокие, некоторые низкие — могут достигать порогов, чрезвычайно близких к пределу Шеннона для BEC. Интуиция заключается в том, что узлы высокой степени, которые получают много сообщений, быстро узнают их правильное значение, а затем помогают узлам более низкой степени через контрольные узлы. Для канала AWGN нерегулярные распределения с тщательной оптимизацией достигли порогов в пределах 0,0045 дБ емкости. Общие шаблоны включают несколько переменных узлов высокой степени (например, степень 20, 30) и многие узлы низкой степени (например, степень 2, 3). Однако наличие переменных узлов степени 2 может создать пол ошибки из-за небольших циклов; часто узлы степени 2 избегают или ограничивают.

Проверка распределения степени узла

Степени контрольного узла также имеют значение, хотя их воздействие часто вторично по сравнению с переменными узлами. Для BEC оптимальное распределение контрольного узла сосредоточено вокруг одного градуса (часто 4-10), чтобы максимизировать порог, как показано Shokrollahi (2002). Для каналов AWGN градусы контрольного узла обычно варьируются от 3 до 10; более высокие градусы увеличивают сложность контрольного узла, но могут улучшить порог. ρ x x 3 x x 3 + ... + m x x ^ m −1. Оптимизация должна сбалансировать увеличение порога с увеличением сложности декодирования и риском введения коротких циклов.

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

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

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

Эволюция плотности, введенная Ричардсоном и Урбанке (2001), отслеживает функцию плотности вероятности (pdf) сообщений, обмениваемых во время итеративного декодирования, предполагая, что для BEC сообщения являются двоичными (стирание или известными), поэтому DE уменьшается до отслеживания вероятности стирания через граф. Для каналов AWGN DE отслеживает pdf LLR, что при симметричном гауссовском приближении уменьшается до отслеживания среднего m гауссианского. Порог обнаруживается путем увеличения шума канала до тех пор, пока рекурсия DE не сойдет к нулю ошибки. Процесс оптимизации включает поиск пространства λ x и ρx x x x , удовлетворяющего ограничения скорости и мак

EXIT Charts

Графики EXIT, разработанные десятью Бринк (2001), предоставляют графический инструмент для анализа конвергентного поведения итеративных декодеров. Они отображают взаимную информацию (MI), передаваемую от переменных узлов к контрольным узлам, по сравнению с MI, передаваемой от контрольных узлов к переменным узлам. Полученные кривые, называемые характеристическими кривыми, не должны пересекаться для успешной декодирования. Оптимизация градусных распределений с использованием графиков EXIT включает в себя сопоставление области под кривой переменных узлов с областью под кривой контрольных узлов, с разницей в области, связанной с разрывом к емкости. Графики EXIT особенно популярны для каналов AWGN, потому что они вычислительно проще полного DE и дают интуитивное понимание. Однако они полагаются на гауссовское приближение LLR-распределений, которое становится менее точным для сильного шума или нерегулярных распределений.

Линейное программирование и другие подходы

Для БЭК задача оптимизации может быть отлита как линейная программа, поскольку условие DE сводится к линейному неравенству по коэффициентам λ и ρ. Для общих каналов ограничения являются нелинейными, поэтому используются эвристические методы, такие как смоделированное отжигание, генетические алгоритмы или методы на основе градиента. Последние достижения используют машинное обучение (например, обучение с подкреплением) для поиска пространства распределений степени. Другой подход заключается в использовании диаграммы внешней передачи информации (EXIT), соответствующей функции стоимости на основе свойства области. Независимо от метода, результатом является набор пар степеней (d_v, d_c и фракций, которые максимизируют порог для фиксированной скорости и конкретной модели канала.

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

Различные каналы имеют разные статистические свойства, которые влияют на характер обмениваемых сообщений и, следовательно, на оптимальное распределение степеней. Ниже мы обсуждаем четыре основные модели каналов: BEC, BSC, AWGN и Rayleigh fading.

Бинарный канал удаления (BEC)

BEC — простейший нетривиальный канал: с вероятностью ε бит стирается (неизвестно), а иначе получен правильно. Порог — максимальный ε, такой, что декодирование удаётся. Для BEC оптимальные распределения степеней известны аналитически посредством линейного программирования. В 2001 году Luby et al. показали, что неправильные коды LDPC могут достигать пропускной способности (ε = 1 − R) асимптотически. Оптимальное распределение переменных узлов включает в себя узлы высокой степени (например, степени до 50 или 100) и большую долю узлов степени-2. Однако узлы степени-2 создают уязвимость «остановительного набора» на конечных длинах, приводя к поломке ошибки. Практические конструкции для BEC (например, коды раптора) используют распределения степеней с всего несколькими узлами степени-2 и тяжелым хвостом. Распределение контрольных узлов обычно концентрируется на одной степени, часто dc

Бинарный симметричный канал (BSC)

BSC переворачивает биты независимо с вероятностью p. Оптимальные распределения степени для BSC более сложны, потому что сообщения являются двоичными (жесткие решения) в декодере жесткого решения (например, алгоритм Галлагера A/B) или мягкими значениями, если использовать BP с LLR. Для декодирования жесткого решения градусные распределения часто являются регулярными (все переменные узлы одной и той же степени, все узлы проверки одной и той же степени), потому что нерегулярность обеспечивает небольшой выигрыш. Оптимальный регулярный код LDPC для BSC под алгоритмом Галлагера имеет переменную степень 3 и чековую степень 6 для скорости 1/2, достигая порога около p ≈ 0,02. Для мягкого решения BP на BSC (с использованием LLR, преобразованных из жестких битов), нерегулярные распределения могут улучшить порог, но выигрыш скромный по сравнению с AWGN. Исследования

Белый гауссовский шум (AWGN)

Канал AWGN является наиболее изученной моделью. Цель состоит в том, чтобы максимизировать порог SNR (часто выражается как E_b/N₀000] для заданной скорости кода кода кода.] Используя эволюцию плотности под гауссовским приближением, Ричардсон и Урбанке (2001) вывели оптимизированные распределения степеней для различных скоростей. Например, скорость-1/2 нерегулярного кода LDPC может иметь переменные узлы степеней 2, 3, 6 и 10 в конкретных фракциях, и чековые узлы степеней 4, 5 и 6. Порог может быть столь же низким, как и 0,19 дБ от предела Шеннона (который при скорости 1/2 равен 0 дБ для двоичной модуля

Rayleigh Fading Channel (с CSI или без него)

В канале затухания Рэлея амплитуда принимаемого сигнала изменяется из-за затухания. При идеальной информации о состоянии канала (CSI) у приемника эффективный канал представляет собой набор гауссовских подканалов с различным усилением. Оптимальное распределение степени должно адаптироваться к затухающей статистике. Как показали Хоу, Сигел и Милштейн (2003), нерегулярные коды LDPC с оптимизированными распределениями степени могут достигать порогов, которые приближаются к средней взаимной информации затухающего канала. Ключевое понимание заключается в том, что переменные узлы, испытывающие глубокие затухания, нуждаются в большей защите от подключенных контрольных узлов, подразумевая необходимость в более тяжелых хвостах, чем для AWGN; Узлы высокой степени (например, 20–30) появляются чаще. Для систем без CSI (некогерентное затухание), проблема более сложна, а распределения степени часто оптимизируются для конкретных доплеровских спредов с использованием диаграмм EXIT. Исследования А. Гранта и других показали, что согласованные распределения степени могут давать прирост 0,5

Расширенные темы в оптимизации распределения степени

Эффекты конечной длины и пол ошибок

Асимптотические пороги направляют конструкцию, но практические коды имеют конечную длину n (например, с 648 по 1944 бит в 5G). На конечных длинах пол ошибки — область очень низкой вероятности ошибки, которая не уменьшается быстро с SNR — становится критическим. Пол ошибки кодов LDPC в первую очередь вызван небольшими стоп-ситуациями (для BEC) или наборами захватов (для AWGN). Распределения степеней со многими переменными узлами низкой степени (особенно степень 2) склонны к таким структурам. Для смягчения пола ошибки оптимизация должна включать ограничения на обхват графа (минимальная длина цикла) и спектральные свойства кода. Некоторые подходы принимают многообъективную оптимизацию: максимизировать порог при минимизации числа небольших наборов захватов. Это часто приводит к распределениям с меньшим количеством узлов 2 степени и более концентрированными узлами переменных. Коды LDPC на основе прототипа, которые определяют код с помощью небольшой базовой матрицы, которая поднимается, позволяют явно контролировать распределение степе

Рассмотрение осуществления

В то время как высокоградусные узлы улучшают пороги, они увеличивают сложность декодирования. Для каждой итерации количество операций на краю пропорционально степени. Для переменного узла степени 30 требуется 30 дополнений (для обновлений LLR) на итерацию, по сравнению с 3 для узла степени-3. В аппаратном обеспечении ограничения памяти и пропускной способности часто ограничивают максимальную степень примерно до 10-20. Аналогично, высокие градусы проверки увеличивают количество операций с min-sum или sum-product. Многие практические энкодеры (например, для Wi-Fi) используют ограниченный набор степеней: переменные степени только 2, 3, 4, 6 и 10; градусы проверки только 4-8. Оптимизация при таких ограничениях является активной областью. Еще одна проблема - потеря скорости кода из-за необходимости битов четности: скорость проектирования из формулы распределения степени может немного отличаться от фактической скорости после построения графа. Необходимо позаботиться о том, чтобы уравнения распределения были согласованы.

Примеры дизайна кода

Для иллюстрации рассмотрим код скорости-1/2 LDPC для канала AWGN. Используя линейное программирование с эволюцией плотности, часто приводится следующее распределение (от Richardson & Urbanke, 2001):

Variable degree Fraction of edges

2 0.289

3 0.171

6 0.486

10 0.055

И проверьте распределение узлов: ρ(x) = 0,497 x3 + 0,503 x4 (т.е. фракции краев, падающих на узлы 4 и 5 степени)]E_b/N₀ = 0,19 дБ. В отличие от этого, обычный (3,6) код имеет порог около 0,7 дБ. Нерегулярная конструкция получает около 0,5 дБ. Для BEC оптимальное распределение скорости-1/2 (Shokrollahi, 2002) это:

Variable degree Fraction of edges

2 0.420

3 0.020

10 0.010

100 0.550

Распределение контрольных узлов сосредоточено на степени 4 (100%). Порог ε = 0,499, очень близок к емкости 0,5. Однако узел высокой степени-100 делает код непрактичным для декодеров с низкой сложностью.

Заключение

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

По мере того, как стандарты связи развиваются в направлении более высокой пропускной способности и более низкой задержки, спрос на оптимизированные коды LDPC продолжается. Недавние исследования исследуют оптимизацию на основе машинного обучения, модификации протографов и комбинированную оптимизацию степени и обхвата. Понимание основ оптимизации распределения степени оснащает инженеров для разработки лучших кодов для беспроводных, спутниковых и систем хранения следующего поколения. Для дальнейшего чтения см. классический учебник «Современная теория кодирования» Ричардсона и Урбанке , основополагающую статью «Дизайн кодов с нерегулярной плотностью-подходящими кодами» Chung et al. (2001) и всеобъемлющий обзор «Десятилетие кодов LDPC» Джонсона и Веллера . Для практических деталей реализации спецификации стандарта 5G доступны из 3GPP TS 38.212