Теория информации
LDPC-коды
Цели урока
- Определить LDPC-код через разреженную матрицу H и граф Таннера
- Описать алгоритм belief propagation в LLR-форме для AWGN-канала
- Объяснить density evolution и понятие порогового SNR
- Знать применение LDPC в 5G NR, Wi-Fi 6 и NVMe SSD
Предварительные знания
- Пропускная способность канала
- Коды исправления ошибок
Как разреженная матрица, изобретённая в 1960-м, оказалась лучшим практическим кодом через 35 лет? Почему belief propagation - оптимален на деревьях?
- Wi-Fi 6 (802.11ax): LDPC обязателен для MCS >= 10, обеспечивает 9.6 Гбит/с в 8x8 MIMO
- 5G NR: LDPC для PDSCH/PUSCH, блоки 500-8448 бит, R от 1/3 до 22/24
- NVMe SSD: LDPC адаптируется к деградации NAND-флеша, продлевая ресурс в 3-5 раз
- QR-код: Reed-Solomon, но его улучшенный потомок LDPC используется в NFC/Bluetooth
35 лет в ящике стола
Роберт Галлагер (MIT, 1960): докторская диссертация 'Low-Density Parity-Check Codes'. Показал: при оптимальном распределении степеней LDPC работает близко к пределу Shannon. Проблема: для n=10000 нужны миллионы операций BP - на ЭВМ 1960-х невозможно. Работа забыта. 1993: турбо-коды Berrou - похожая идея (итерационное декодирование), произвели революцию. 1995: David MacKay и Radford Neal переоткрывают LDPC через Интернет-архивы. Сравнение с турбо-кодами: LDPC работает лучше при длинных блоках. 2003: IEEE 802.3an (10GBase-T Ethernet) использует LDPC. 2009: Wi-Fi 802.11n. 2018: 5G NR. Галлагер получил IEEE Hamming Medal в 2000 году.
LDPC-коды: разреженные матрицы и граф Таннера
Роберт Галлагер разработал LDPC-коды в MIT в 1960 году в рамках своей докторской диссертации. Идея: проверочная матрица с очень малым числом единиц в каждой строке и столбце. Галлагер показал, что такие коды при n -> inf работают вблизи предела Shannon. Мир проигнорировал работу на 35 лет - не было вычислительных мощностей для декодирования. В 1995 году Mackay и Neal переоткрыли LDPC, назвали 'turbo codes in disguise' и показали: это лучшие практические коды. Сегодня LDPC стоит в каждом Wi-Fi чипсете и в каждом NVMe SSD.
Wi-Fi 802.11n (2009): LDPC-коды как опциональная функция, длины блоков 648-1944 бита, кодовые скорости 1/2, 2/3, 3/4, 5/6. IEEE 802.11ax (Wi-Fi 6): LDPC обязателен для MCS >= 10. Каждый современный Wi-Fi роутер реализует графы Таннера в аппаратном LDPC-декодере на несколько Гбит/с.
Что означает 'разреженность' в LDPC - и почему это ключевое свойство?
Разреженность H => граф Таннера с малой степенью узлов => сообщения BP почти независимы (нет циклов длины 4) => BP сходится к оптимальному декодированию. Плотная H дала бы зависимости сообщений и сбои BP.
Belief Propagation: алгоритм декодирования
Belief Propagation - это MCMC-подобный алгоритм, придуманный для LDPC как 'sum-product'. Но это же алгоритм работает в байесовских сетях Judea Pearl (1988), в алгоритме Витерби для скрытых марковских моделей, в modern neural belief propagation. Один алгоритм - везде. Галлагер нашёл его для кодов за 25 лет до Pearl.
Почему BP сходится к оптимальному декодированию на деревьях, но не гарантированно на циклах?
На дереве: каждое сообщение несёт новую независимую информацию -> BP = MAP-декодирование. На циклах: 'корреляция через петлю' - узел получает от соседей информацию, в которую уже вложен свой LLR. Это называется 'belief propagation without extrinsic correction'.
Density Evolution и порог пропускной способности
Density Evolution (Richardson-Urbanke, 2001) - точный инструмент анализа BP для LDPC. Вместо отслеживания отдельных LLR отслеживается их распределение при n -> inf. Результат: для каждого (lambda, rho) существует пороговый SNR - ниже BP сходится к нулевой ошибке, выше - нет.
NVMe SSD и LDPC
NVMe PCIe Gen4 SSD (Samsung 990 Pro): LDPC с блоком 64KB, кодовой скоростью 14/15. Флеш-память NAND деградирует: свежая ячейка имеет BER 10^-4, после 3000 циклов стирания - 10^-2. LDPC адаптируется: при малом BER использует жёсткое решение (hard-decision BP), при деградации переключается на мягкое (soft-decision BP с считыванием 3 порогов вместо 1). Это и есть density evolution в продакшне: порог BP адаптируется к текущей плотности ошибок флеша.
LoRA и квантование нейросетей через LDPC: идея Information Bottleneck LDPC (Stark et al., 2019) - коды из нейросетей, обученных минимизировать I(X;X-hat) с ограничением I(X;Y) >= C - delta. Это прямая связь LDPC с information bottleneck principle Tishby. Нейросеть обнаруживает структуру, аналогичную density evolution, но без явного использования BP.
Что такое пороговый SNR в density evolution для LDPC?
Пороговый SNR: ниже него BP сходится (PE -> 0 при n -> inf), выше - не сходится. Цель оптимизации LDPC: приблизить пороговый SNR как можно ближе к предел Shannon (capacity-approaching). Density evolution позволяет точно вычислить этот порог для конкретного (lambda, rho).
LDPC в 5G, Wi-Fi 6 и дисковых системах
LDPC-коды буквально везде. Каждое устройство с Wi-Fi 6, каждый телефон с 5G NR, каждый NVMe SSD - все используют LDPC. Это самый широко развёрнутый класс кодов, приближающихся к пределу Shannon.
Производительность LDPC в 5G NR при BLER=10^-2: на AWGN-канале при R=0.5 и блоке 6144 бита - SNR 1.1 дБ от предела Shannon. При более коротких блоках (300 бит) отставание возрастает до 1.8 дБ. Полярные коды выигрывают при блоках < 512 бит - именно поэтому в 5G NR два класса кодов сосуществуют.
Min-sum приближение в BP: вместо точного tanh/atanh используется min-операция над LLR: L_{c->v} ≈ min_{v' != v}|L_{v'->c}| * sign(prod). Потеря < 0.2 дБ при 3-4-кратном снижении сложности. Все реальные LDPC-чипсеты используют min-sum.
Почему в 5G NR используются две базовые матрицы (BG1 и BG2) вместо одной?
LDPC с большим N работает лучше относительно предела Shannon. Для коротких блоков нужны другие параметры (lambda, rho), оптимизированные через density evolution. BG1: 500-8448 инф. бит. BG2: 40-2560 инф. бит. Выбор в реальном времени по длине пакета.
Связь с другими темами
LDPC объединяет: теорию информации (density evolution, capacity-approaching), теорию графов (граф Таннера, обхват), алгоритмы (belief propagation = message passing = sum-product). BP - универсальный алгоритм вывода: тот же алгоритм работает в байесовских сетях (Pearl 1988), HMM (Viterbi), Kalman-фильтре. Information Bottleneck principle Tishby связывает LDPC с нейросетевым обучением: минимизация I(X;Z) при максимизации I(Z;Y) - это и есть нахождение хорошего кода.
- Information Theory — Связанная тема
Итоги
- LDPC определяется разреженной H: малый вес строк/столбцов => граф Таннера с малой степенью
- BP-декодирование: итерационный обмен LLR-сообщениями по рёбрам графа, O(n) за итерацию
- Density evolution: пороговый SNR для конкретного (lambda, rho); оптимизация через LP
- 5G NR: QC-LDPC BG1/BG2, блоки 500-8448 бит, в 1.1 дБ от Shannon при больших блоках
Вопросы для размышления
- Почему 35 лет LDPC оставались невостребованными и как это изменилось с ростом вычислительных мощностей?
- Чем min-sum BP отличается от точного sum-product и когда это различие критично?
- В чём глубинная связь между LDPC, байесовскими сетями и нейросетевым обучением через BP?