LDPC

LDPC (Low-Density Parity-Check, код с малой плотностью проверок на чётность) — это класс линейных блоковых кодов, исправляющих ошибки, используемых в системах цифровой связи и хранения данных. Коды LDPC характеризуются разреженной (с малой плотностью ненулевых элементов) проверочной матрицей, что позволяет эффективно декодировать их с помощью итеративных алгоритмов, приближаясь к пропускной способности канала связи (границе Шеннона). LDPC-коды являются одними из наиболее распространённых помехоустойчивых кодов в современных стандартах беспроводной и спутниковой связи, а также в системах хранения данных, таких как NAND-флеш-память.

История

Ранние работы (1960-е годы)

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

Переоткрытие (1990-е годы)

В 1990-х годах, с развитием вычислительной техники и появлением турбо-кодов (Berrou et al., 1993), интерес к итеративному декодированию возродился. В 1996 году Маккей (David J.C. MacKay) и Нил (Radford M. Neal) независимо переоткрыли LDPC-коды, показав, что при достаточно длинных блоках они могут достигать производительности, близкой к теоретическому пределу Шеннона. Это привело к активному исследованию LDPC-кодов в академической и промышленной среде.

Стандартизация и коммерческое применение (2000-е — настоящее время)

С 2000-х годов LDPC-коды начали включаться в международные стандарты. Они были приняты в стандарте цифрового телевидения DVB-S2 (2005) и его последующих версиях, в стандарте беспроводной связи IEEE 802.11n (Wi-Fi 4, 2009) и IEEE 802.11ac (Wi-Fi 5, 2013), а также в стандарте 10GBASE-T Ethernet (2006). Особенно широкое распространение LDPC-коды получили в стандарте 5G NR (New Radio, 2018), где они используются для каналов передачи данных (Data Channel). В системах хранения данных LDPC-коды стали стандартом де-факто для NAND-флеш-памяти, начиная с 2010-х годов, заменив более старые коды Рида-Соломона и Боуза-Чоудхури-Хоквингема (БЧХ).

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

Линейные блоковые коды

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

Проверочная матрица

Ключевой особенностью LDPC-кода является его проверочная матрица \( H \) размером \( m \times n \), где \( m = n - k \) (для систематических кодов). Матрица \( H \) является разреженной — количество ненулевых элементов (единиц) в ней значительно меньше, чем количество нулей. Обычно плотность единиц составляет от 0,01% до 1% от общего числа элементов. Каждая строка матрицы \( H \) соответствует уравнению проверки на чётность, которому должно удовлетворять любое кодовое слово \( c \): \( H \cdot c^T = 0 \).

Граф Таннера

LDPC-код может быть представлен в виде двудольного графа, называемого графом Таннера. Граф состоит из двух типов вершин:

• Переменные узлы (variable nodes) — соответствуют битам кодового слова (столбцам матрицы \( H \)).
• Проверочные узлы (check nodes) — соответствуют уравнениям проверки на чётность (строкам матрицы \( H \)).

Ребро между переменным узлом \( i \) и проверочным узлом \( j \) существует, если элемент \( H_{ji} = 1 \). Декодирование LDPC-кода основано на итеративном обмене сообщениями между этими узлами.

Классификация

По типу матрицы

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

По способу конструирования

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

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

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

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

Итеративное декодирование

Основным методом декодирования LDPC-кодов является итеративный алгоритм, основанный на передаче сообщений (message passing algorithm). Наиболее распространённая реализация — алгоритм «сумма-произведение» (Sum-Product Algorithm, SPA) или его упрощённая версия — алгоритм «минимум-сумма» (Min-Sum Algorithm, MSA).

Алгоритм работает следующим образом:

1. Инициализация: каждый переменный узел получает априорную вероятность (или логарифмическое отношение правдоподобия, LLR) от канала.
2. Итерация: сообщения передаются между переменными и проверочными узлами по рёбрам графа. На каждом шаге узлы обновляют свои сообщения на основе полученных данных и правил алгоритма.
3. Принятие решения: после каждой итерации вычисляется жёсткое решение для каждого бита. Если все проверки на чётность удовлетворены (\( H \cdot c^T = 0 \)) или достигнуто максимальное число итераций, процесс останавливается.

Особенности

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

Применение

Спутниковая и широковещательная связь

• DVB-S2/S2X: стандарт цифрового спутникового телевидения использует LDPC-коды с кодовыми скоростями от 1/4 до 9/10, обеспечивая высокую помехоустойчивость при низких отношениях сигнал/шум.
• DVB-T2: стандарт наземного цифрового телевидения также использует LDPC-коды для повышения эффективности передачи.

Беспроводные сети

• IEEE 802.11n/ac/ax (Wi-Fi): LDPC-коды являются опциональным, но широко поддерживаемым методом кодирования для повышения скорости и надёжности передачи.
• 5G NR (New Radio): LDPC-коды используются для каналов передачи данных (PDSCH, PUSCH) с длинами блоков до 8448 бит. Для каналов управления применяются полярные коды.

Проводные сети

• 10GBASE-T Ethernet: стандарт для медных кабелей витой пары использует LDPC-коды для достижения скорости 10 Гбит/с на расстояниях до 100 метров.

Хранение данных

• NAND-флеш-память: начиная с многоуровневых ячеек (MLC, TLC, QLC), LDPC-коды стали стандартом для коррекции ошибок в твёрдотельных накопителях (SSD) и картах памяти. Они способны исправлять многократные ошибки, возникающие из-за износа ячеек и помех при чтении/записи.

Космическая связь

• CCSDS (Consultative Committee for Space Data Systems): LDPC-коды рекомендованы для использования в космических миссиях (например, для телеметрии и передачи данных с научных аппаратов).

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

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

• Высокая помехоустойчивость: LDPC-коды позволяют работать вблизи теоретического предела Шеннона (до 0,0045 дБ от границы при длинных блоках).
• Гибкость: возможность выбора кодовой скорости и длины блока под конкретные требования.
• Эффективное декодирование: итеративные алгоритмы имеют линейную сложность и хорошо поддаются параллельной реализации на аппаратном уровне (FPGA, ASIC).

Недостатки

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

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

• LDPC-коды были запатентованы Галлагером в 1963 году (патент США № 3,214,696), но патент истёк до их широкого распространения, что способствовало свободному использованию технологии.
• В 2020 году LDPC-коды были выбраны для стандарта 5G NR вместо турбо-кодов, использовавшихся в 4G LTE, из-за лучшей производительности при высоких скоростях передачи данных.
• В системах NAND-флеш-памяти LDPC-коды могут исправлять до 100 и более ошибок на 1 КБ данных, что значительно превышает возможности кодов БЧХ.

Источники

• Gallager, R. G. (1962). Low-density parity-check codes. IRE Transactions on Information Theory, 8(1), 21-28.
• MacKay, D. J. C., & Neal, R. M. (1996). Near Shannon limit performance of low density parity check codes. Electronics Letters, 32(18), 1645-1646.
• Richardson, T. J., & Urbanke, R. L. (2001). The capacity of low-density parity-check codes under message-passing decoding. IEEE Transactions on Information Theory, 47(2), 599-618.
• Стандарт ETSI EN 302 307 (DVB-S2).
• 3GPP TS 38.212: Multiplexing and channel coding (5G NR).
• IEEE Std 802.11-2020.