Коды LDPC

LDPC-коды (Low-Density Parity-Check codes, коды с малой плотностью проверок на чётность) — это класс линейных блочных помехоустойчивых кодов, используемых для коррекции ошибок при передаче данных по каналам связи с шумом. Отличительной особенностью LDPC-кодов является разрежённость их проверочной матрицы (матрицы H), то есть малое количество ненулевых элементов по сравнению с её размерами. Благодаря этому свойству, для декодирования LDPC-кодов могут применяться эффективные итеративные алгоритмы, позволяющие приблизиться к пропускной способности канала (пределу Шеннона) с вычислительной сложностью, линейно зависящей от длины кода. LDPC-коды широко применяются в современных системах цифровой связи, включая стандарты Wi-Fi (IEEE 802.11n/ac/ax), цифровое телевидение (DVB-S2, DVB-T2, DVB-C2), спутниковую связь, системы хранения данных (NAND-флэш-память) и технологию 5G NR.

История

Открытие и ранние работы

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

Переоткрытие и развитие

В 1993 году Клод Берру и Ален Главиё открыли турбокоды, которые показали близкую к пределу Шеннона производительность и вызвали новый интерес к итеративным методам декодирования. В 1996 году Дэвид Маккей и Радлифф Нил, а также независимо Микаэль Люби, Майкл Митценмахер и Амир Шокроллахи, переоткрыли LDPC-коды. Они показали, что при достаточно длинных блоках и использовании разрежённых проверочных матриц, LDPC-коды могут превзойти турбокоды по производительности, особенно при больших длинах кодовых слов. С этого момента началось интенсивное изучение и совершенствование LDPC-кодов.

Практическое внедрение

С начала 2000-х годов LDPC-коды стали внедряться в промышленные стандарты. Первым массовым применением стал стандарт спутникового телевидения DVB-S2 (2005 год). Затем последовали стандарты цифрового телевидения DVB-T2 и DVB-C2, стандарты Wi-Fi (IEEE 802.11n, 2009 год), а также стандарты 10GBASE-T Ethernet. В 2018 году LDPC-коды были выбраны в качестве основного канального кодирования для канала данных в технологии 5G NR (New Radio), заменив турбокоды, использовавшиеся в 4G LTE.

Определение и основные понятия

LDPC-код является линейным блочным кодом. Это означает, что он преобразует блок из \( k \) информационных бит в блок из \( n \) бит (кодовое слово), где \( n > k \). Избыточность кода характеризуется скоростью кода \( R = k/n \).

Ключевым элементом является проверочная матрица \( H \) размером \( m \times n \), где \( m = n - k \) (для полноранговой матрицы). Строки матрицы соответствуют проверкам на чётность, а столбцы — битам кодового слова. Кодовое слово \( c \) (длиной \( n \)) удовлетворяет условию:

\[ H \cdot c^T = 0 \]

Условие «малой плотности» (Low-Density) означает, что матрица \( H \) содержит очень мало единиц (ненулевых элементов) по сравнению с нулями. Обычно доля единиц составляет от 0.1% до 1% от общего числа элементов.

LDPC-коды удобно представлять в виде графа Таннера — двудольного графа, где одна доля вершин представляет биты (переменные), а другая — проверки. Ребро соединяет битовую вершину с проверочной, если соответствующий элемент матрицы \( H \) равен 1. Такой граф наглядно иллюстрирует связи между битами и проверками и лежит в основе итеративного декодирования.

Классификация LDPC-кодов

LDPC-коды классифицируются по нескольким признакам.

По регулярности

• Регулярные коды: Каждый столбец матрицы \( H \) содержит одинаковое количество единиц (\( d_v \)), и каждая строка содержит одинаковое количество единиц (\( d_c \)). В графе Таннера все битовые вершины имеют степень \( d_v \), а все проверочные — степень \( d_c \).
• Нерегулярные коды: Степени вершин в графе Таннера могут различаться. Нерегулярные коды, как правило, показывают лучшую производительность, так как биты с большей степенью получают больше информации от проверок и быстрее «исправляются».

По способу построения

• Случайные коды: Матрица \( H \) генерируется случайным образом с заданными ограничениями на степени вершин. Такие коды часто показывают хорошую производительность, но их реализация может быть сложной из-за отсутствия структуры.
• Структурированные коды: Матрица \( H \) строится на основе алгебраических или комбинаторных конструкций (например, циклические сдвиги, конечные поля, геометрии). Примеры: квазициклические LDPC-коды (QC-LDPC). Они обладают регулярной структурой, что упрощает кодирование и декодирование, и широко используются в стандартах (например, в 5G NR, DVB-S2).

По типу канала

• Двоичные LDPC-коды: Предназначены для двоичных каналов (например, двоичный симметричный канал, канал с аддитивным белым гауссовским шумом (AWGN) с двоичной модуляцией).
• Небинарные LDPC-коды: Работают с символами из полей Галуа \( GF(q) \) при \( q > 2 \). Они могут обеспечивать лучшую производительность на каналах с высокой плотностью ошибок, но требуют более сложного декодирования.

Декодирование LDPC-кодов

Основным методом декодирования LDPC-кодов является итеративное декодирование на основе распространения доверия (Belief Propagation, BP). Алгоритм работает на графе Таннера и заключается в обмене сообщениями между битовыми и проверочными вершинами.

Алгоритм распространения доверия

1. Инициализация: Каждая битовая вершина получает априорную вероятность (или логарифмическое отношение правдоподобия, LLR) от канала.
2. Итерации:

• Обновление проверок: Каждая проверочная вершина собирает сообщения от всех связанных с ней битовых вершин и вычисляет новые сообщения для каждой из них на основе условия чётности (сумма по модулю 2 равна 0). В логарифмической области для этого используется операция \( \tanh \).
• Обновление битов: Каждая битовая вершина собирает сообщения от всех связанных с ней проверочных вершин и суммирует их с априорной информацией от канала. Результат отправляется обратно на проверки.

1. Принятие решения: После каждой итерации (или по завершении заданного числа итераций) на основе суммарной информации в каждой битовой вершине принимается жёсткое решение (0 или 1). Если полученный вектор удовлетворяет всем проверкам (\( H \cdot \hat{c}^T = 0 \)), декодирование считается успешным.

Варианты и упрощения

• Минимаксный алгоритм (Min-Sum): Упрощение алгоритма BP, где вместо сложных операций с \( \tanh \) используется вычисление минимума. Это снижает вычислительную сложность ценой небольшой потери производительности.
• Декодирование с жёсткими решениями: Используются только двоичные значения (0/1) вместо вероятностей. Пример — алгоритм Галлагера. Менее эффективен, но очень прост в реализации.

Применение LDPC-кодов

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

• Цифровое телевидение: Стандарты DVB-S2 (спутниковое), DVB-T2 (эфирное), DVB-C2 (кабельное). Обеспечивают высокую помехоустойчивость при передаче видео высокой чёткости (HDTV) и сверхвысокой чёткости (UHDTV).
• Спутниковая связь: Используются в системах спутникового интернета (например, Starlink, OneWeb) и для связи с космическими аппаратами (NASA, ESA).
• Беспроводные сети: Стандарты Wi-Fi (IEEE 802.11n/ac/ax/be) и 5G NR. В 5G NR LDPC-коды применяются для канала данных (UL-SCH, DL-SCH), обеспечивая высокую скорость передачи и низкую задержку.
• Проводные сети: Стандарт 10GBASE-T (10 Gigabit Ethernet over twisted pair).
• Системы хранения данных: Используются в современных твердотельных накопителях (SSD) на основе NAND-флэш-памяти для коррекции ошибок, возникающих из-за износа ячеек и помех.
• Оптические сети: Применяются в системах дальней оптической связи (например, в стандартах ITU-T G.709).

Преимущества и недостатки

Преимущества

• Близость к пределу Шеннона: Длинные LDPC-коды могут работать на расстоянии менее 0.01 дБ от теоретического предела пропускной способности канала.
• Эффективное декодирование: Итеративные алгоритмы имеют линейную вычислительную сложность по длине кода и хорошо поддаются параллельной реализации.
• Гибкость: Возможность построения кодов с различной длиной и скоростью, в том числе с помощью структурных методов.
• Отсутствие эффекта «ошибки пола»: В отличие от турбокодов, LDPC-коды при правильном проектировании не имеют нижней границы вероятности ошибки (error floor) вплоть до очень малых значений.

Недостатки

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

Интересные факты

• LDPC-коды были изобретены на 30 лет раньше турбокодов, но не получили признания из-за отсутствия вычислительных мощностей.
• В стандарте 5G NR для разных размеров транспортных блоков используются различные базовые матрицы (BG1 и BG2), оптимизированные для разных диапазонов скоростей кода.
• LDPC-коды используются в системе лазерной связи NASA (LCRD) для передачи данных с Луны и Марса.
• Квазициклические LDPC-коды (QC-LDPC) являются подклассом циклических кодов и могут быть закодированы с использованием сдвиговых регистров, что упрощает аппаратную реализацию.

Источники

• R. G. Gallager, «Low-Density Parity-Check Codes», IRE Transactions on Information Theory, 1962.
• D. J. C. MacKay, «Good Error-Correcting Codes Based on Very Sparse Matrices», IEEE Transactions on Information Theory, 1999.
• T. Richardson, R. Urbanke, «Modern Coding Theory», Cambridge University Press, 2008.
• W. E. Ryan, S. Lin, «Channel Codes: Classical and Modern», Cambridge University Press, 2009.
• 3GPP TS 38.212, «NR; Multiplexing and channel coding», 2018.
• ETSI EN 302 307, «Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other broadband satellite applications (DVB-S2)», 2005.