LDPC-коды

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

История

Ранние разработки

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

Возрождение в 1990-х годах

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

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

В начале 2000-х годов LDPC-коды были включены в ряд международных стандартов:

• DVB-S2 (2003) — стандарт спутникового телевидения;
• IEEE 802.11n (2009) — стандарт беспроводной связи Wi-Fi;
• IEEE 802.16e (2005) — стандарт мобильного WiMAX;
• 5G NR (2018) — стандарт мобильной связи пятого поколения, где LDPC-коды используются для каналов передачи данных.

Принцип работы

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

LDPC-код относится к классу линейных блоковых кодов. Исходное сообщение длиной \( k \) бит кодируется в кодовое слово длиной \( n \) бит (\( n > k \)). Избыточность кода определяется скоростью \( R = k/n \). Проверочная матрица \( H \) размера \( (n-k) \times n \) задаёт линейные ограничения на кодовые слова: для любого кодового слова \( c \) выполняется \( H \cdot c^T = 0 \).

Разрежённость матрицы

Основное свойство LDPC-кода — малая плотность единиц в проверочной матрице \( H \). Обычно количество единиц в строке (вес строки) и столбце (вес столбца) значительно меньше размеров матрицы. Например, для кода длины 1000 бит вес строки может составлять 3–5 единиц. Это свойство критически важно для эффективности итеративного декодирования.

Представление в виде графа Таннера

LDPC-код удобно представлять с помощью двудольного графа Таннера, который содержит два типа узлов:

• Узлы переменных (variable nodes) — соответствуют битам кодового слова (их \( n \) штук);
• Узлы проверок (check nodes) — соответствуют строкам проверочной матрицы (их \( n-k \) штук).

Ребро соединяет узел переменной \( i \) с узлом проверки \( j \), если элемент \( H_{ji} = 1 \). Разрежённость матрицы означает, что каждый узел соединён лишь с несколькими узлами другого типа.

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

Регулярные и нерегулярные коды

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

Двоичные и недвоичные коды

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

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

• Случайные LDPC-коды — проверочная матрица строится случайным образом с заданными степенными распределениями. Обеспечивают хорошую производительность, но сложны в реализации.
• Структурированные LDPC-коды — матрица строится на основе алгебраических или комбинаторных конструкций (например, циклические сдвиги). К таким относятся коды QC-LDPC (Quasi-Cyclic LDPC), широко используемые в стандартах из-за простоты реализации.

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

Итеративный алгоритм распространения доверия

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

1. Узлы переменных отправляют узлам проверок вероятности (или логарифмические отношения правдоподобия) того, что соответствующий бит равен 0 или 1.
2. Узлы проверок вычисляют новые вероятности на основе ограничения чётности для каждой строки и отправляют их обратно.
3. Процесс повторяется итеративно до тех пор, пока не будет найдено кодовое слово, удовлетворяющее всем проверкам, или не будет достигнуто максимальное число итераций.

Упрощённые алгоритмы

Для снижения вычислительной сложности используются упрощённые варианты:

• Алгоритм минимальной суммы (Min-Sum) — заменяет операцию произведения на нахождение минимального значения, что уменьшает сложность за счёт некоторой потери точности.
• Алгоритм битового переворота (Bit-Flipping) — простейший жёсткий алгоритм, где на каждой итерации переворачиваются биты, нарушающие наибольшее число проверок.

Применение

Спутниковая и радиосвязь

• DVB-S2 и DVB-S2X — стандарты спутникового телевидения, где LDPC-коды обеспечивают высокую помехоустойчивость при низких отношениях сигнал/шум.
• 5G NR — в каналах передачи данных (PDSCH, PUSCH) используются QC-LDPC-коды с двумя базовыми матрицами для разных диапазонов скоростей.

Беспроводные локальные сети

• IEEE 802.11n/ac/ax (Wi-Fi) — опциональное использование LDPC-кодов для повышения надёжности на высоких скоростях.

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

• NAND Flash-память — некоторые современные контроллеры SSD используют LDPC-коды для коррекции ошибок, что позволяет увеличить количество циклов перезаписи и ёмкость памяти.
• Оптические диски — LDPC-коды применяются в стандартах Blu-ray для коррекции ошибок.

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

• CCSDS (Консультативный комитет по космическим системам данных) — рекомендует LDPC-коды для глубокого космоса и спутниковых линий связи.

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

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

• Близость к пределу Шеннона — при больших длинах кода (например, 10000 бит и более) LDPC-коды могут работать на расстоянии 0.1–0.5 дБ от теоретического предела.
• Параллелизуемость — итеративное декодирование хорошо поддаётся параллельной реализации на FPGA или ASIC.
• Гибкость — возможность выбора скорости и длины кода под конкретное приложение.

Недостатки

• Высокая сложность кодирования — в отличие от турбо-кодов, LDPC-коды требуют более сложных процедур кодирования, хотя для QC-LDPC она упрощается.
• Ошибки в виде «пола» — при высоких отношениях сигнал/шум может наблюдаться эффект «error floor», когда частота ошибок перестаёт уменьшаться с ростом сигнала.
• Требования к памяти — для хранения проверочной матрицы и сообщений при декодировании требуется значительный объём памяти.

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

• В 2009 году Роберт Галлагер получил премию Маркони за вклад в теорию кодирования, включая LDPC-коды.
• LDPC-коды используются в системе связи NASA для миссии «Марс-2020» (марсоход Perseverance).
• В стандарте 5G NR для управления и передачи данных используются разные типы кодов: полярные коды — для каналов управления, LDPC-коды — для каналов данных.

Источники

• Gallager R. G. Low-Density Parity-Check Codes. — MIT Press, 1963.
• MacKay D. J. C., Neal R. M. Near Shannon limit performance of low density parity check codes // Electronics Letters. — 1996. — Vol. 32, No. 18. — P. 1645–1646.
• Richardson T., Urbanke R. Modern Coding Theory. — Cambridge University Press, 2008.
• 3GPP TS 38.212: Multiplexing and channel coding (5G NR).
• ETSI EN 302 307: Digital Video Broadcasting (DVB); Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other broadband satellite applications (DVB-S2).