Теория информации
Полярные коды
Цели урока
- Объяснить механизм поляризации канала через рекурсивное преобразование G_N
- Описать SC и SCL-декодирование и их сравнительные характеристики
- Сравнить полярные коды с LDPC по основным параметрам
- Знать применение полярных кодов в 5G NR и их ограничения
Предварительные знания
- Пропускная способность канала
- Коды исправления ошибок
Как рекурсивное XOR-преобразование за конечное число шагов создаёт каналы, часть из которых идеальна? Почему это первая явная конструкция, достигающая C?
- 5G NR PDCCH: полярные коды с SCL-8 и CRC-11 - в каждом смартфоне с 2019 года
- SCL-декодирование с L=32 превосходит турбо-коды LTE на 0.5-1 дБ при коротких блоках
- FlexPolar (Huawei, 2020): аппаратный ускоритель, 1 Гбит/с на 7нм
- Нейросетевые декодеры полярных кодов: новый класс методов на стыке IT и DL
60 лет поиска: от Shannon до Арыкана
Shannon (1948) доказал существование хороших кодов, но не указал конструкцию. Турбо-коды (Berrou, 1993) практически достигли C случайным образом. LDPC (Gallager 1960, Mackay-Neal 1995) - близко, но без теоретической гарантии для конечного N. Эрдал Арыкан (Bilkent University, 2008) - 'Channel Polarization'. Ключевой insight: рекурсивное преобразование поляризует N одинаковых каналов в N/2 лучших и N/2 худших. При n рекурсиях получаем N=2^n каналов с поляризацией -> совершенству. 2016: 3GPP выбирает полярные коды для 5G. Арыкан получает IEEE Hamming Medal в 2018 году.
Поляризация канала по Арыкану
2008 год. Эрдал Арыкан публикует 'Channel Polarization: A Method for Constructing Capacity-Achieving Codes'. За 60 лет после Shannon никто не нашёл явную конструкцию кодов, достигающих C. Арыкан нашёл. В 2016 году 3GPP принял полярные коды для управляющих каналов 5G NR. Простая рекурсивная идея - и ждала 60 лет.
Поляризация бинарного стирающего канала (BEC) особенно наглядна: хорошие каналы получают Z_i -> 0 (идеальные), плохие -> 1 (полностью стёртые). Для AWGN поляризация происходит аналогично, но асимптотически медленнее.
Что происходит с виртуальными каналами при полярном преобразовании при N -> infinity?
Теорема поляризации Арыкана: при N -> inf виртуальные каналы поляризуются - доля с I(W_N^(i)) > 1-delta стремится к I(W). Промежуточные каналы исчезают. Это позволяет выбрать ровно k = NR информационных позиций и достичь пропускной способности.
SC и SCL-декодирование
Successive Cancellation (SC) декодирование - простое и элегантное: биты декодируются последовательно, каждый предыдущий используется для следующего. Сложность O(N log N) - лучше, чем у многих кодов. Но при конечных N качество хуже LDPC. SCL (Successive Cancellation List) с CRC исправил это и вывел полярные коды в 5G.
Полярные коды в 5G NR
3GPP Release 15 (2018): полярные коды для PDCCH (физический нисходящий управляющий канал) и PUCCH (физический восходящий управляющий канал). Параметры: блоки 32-512 бит, SCL с L=8, CRC длины 11. Сравнение с turbo-кодами LTE: при блоке 100 бит и BLER=1% полярные коды выигрывают 0.5-1 дБ по SNR. При больших блоках преимущество уменьшается - поэтому для данных оставлены LDPC.
Кодирование полярными кодами - O(N log N) операций. SCL декодирование с L=8: O(L * N * log N). Для N=512, L=8: ~40,000 операций. Это реализуемо в реальном времени на DSP базовой станции. FlexPolar (2020) от Huawei: аппаратный ускоритель полярных кодов на 7нм, 1 Гбит/с при задержке 50 мкс.
Почему SCL-декодирование с CRC превосходит SC по производительности?
SC делает жёсткое решение на каждом шаге и не может его исправить. SCL хранит L лучших путей - при ошибке на одном пути правильный остаётся в списке. CRC в конце выбирает. При L=32 производительность близка к максимально правдоподобному декодированию.
Полярные коды vs LDPC: практический выбор
5G NR использует два вида кодов: полярные для управляющих каналов (короткие блоки), LDPC для данных (длинные блоки). Это не случайный выбор - компромисс между теоретическими и практическими свойствами каждого класса.
| Свойство | Полярные коды | LDPC коды |
|---|---|---|
| Достижение C | Теоретически при N->inf | Теоретически при оптим. распределении |
| Длина блока | Короткие (32-1K) | Длинные (1K-64K) |
| Декодирование | SC: последовательное | BP: параллельное |
| Применение в 5G | Управление (PDCCH/PUCCH) | Данные (PDSCH/PUSCH) |
| Задержка | Высокая (serial) | Низкая (parallel) |
Нейросетевые декодеры полярных кодов (2017-2024): обучение MLP/LSTM для декодирования заменяет SCL. При блоке 64 бита: нейросетевой декодер достигает 0.3 дБ от ML при сложности O(N^2) вместо O(2^k) для ML. TurboAE (2019): нейросетевой кодек конкурирует с LDPC при коротких блоках. Это активная область исследований на пересечении IT и DL.
Почему в 5G NR полярные коды используются для управляющих каналов, а LDPC для данных?
Управляющие каналы: блоки 32-512 бит, критична задержка -> SCL-полярные. Данные: блоки 1K-64K бит, критична пропускная способность -> LDPC с параллельным BP. Масштабирующий экспонент полярных кодов (~3.63) хуже LDPC (~2) при больших N, но при малых N разница невелика.
Связь с другими темами
Полярные коды используют: теорему поляризации (C достигается при N -> inf), SCL-декодирование (алгоритм beam search с L=2^k гипотезами), CRC (дополнительный код для выбора среди L путей). Связь с LDPC: оба применяются в 5G, но для разных блоков. Связь с глубоким обучением: нейросетевые декодеры применяют seq2seq-модели для декодирования. Scaling exponent полярных кодов (~3.63) хуже турбо-кодов (~2) - активная область улучшений.
- Information Theory — Связанная тема
Итоги
- Полярное преобразование G_N рекурсивно создаёт N=2^n виртуальных каналов из N одинаковых
- Теорема поляризации: доля хороших каналов -> I(W), плохих -> 1-I(W) при N -> inf
- SC: O(N log N) декодирование; SCL с L путями и CRC - близко к ML-декодированию
- 5G NR: полярные для управляющих каналов (короткие), LDPC для данных (длинные)
Вопросы для размышления
- Почему полярные коды более 60 лет не могли обнаружить до Арыкана, несмотря на простоту конструкции?
- Как SCL-декодирование балансирует между вычислительной сложностью и приближением к ML?
- Что ограничивает полярные коды при практических длинах блоков по сравнению с LDPC?