Полярные коды

Полярные коды — это класс линейных корректирующих кодов, основанных на явлении поляризации канала, которые позволяют достичь пропускной способности симметричного канала без памяти (например, двоичного симметричного канала) при использовании алгоритма последовательного исключения (successive cancellation, SC) с полиномиальной сложностью декодирования. Разработаны Эрдалом Ариканом в 2008 году и впервые представлены в 2009 году. Полярные коды являются первым (и на данный момент единственным) классом кодов, для которых строго доказано достижение пропускной способности канала при конечной длине кодового слова, хотя на практике для этого требуются значительные длины.

История

Идея поляризации канала была предложена турецким учёным Эрдалом Ариканом (Erdal Arıkan) в 2008 году. В 2009 году он опубликовал основополагающую статью «Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels», в которой математически обосновал, что при многократном рекурсивном преобразовании двоичных входных каналов происходит их поляризация: часть каналов становится «идеальной» (с пропускной способностью, стремящейся к 1), а часть — «шумовой» (с пропускной способностью, стремящейся к 0). Доля «идеальных» каналов стремится к пропускной способности исходного канала.

До появления полярных кодов достижение пропускной способности канала считалось возможным лишь асимптотически, при бесконечной длине кодового слова, и без строгих доказательств (например, для турбо-кодов и LDPC-кодов). Полярные коды стали первым классом с формальным доказательством.

В 2016 году полярные коды были выбраны в качестве стандарта кодирования для канала управления (control channel) в системах 5G NR (New Radio) — спецификации 3GPP Release 15. Это решение было принято из-за их низкой сложности декодирования и хорошей производительности при коротких длинах кодовых слов.

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

Поляризация канала

Основная идея полярных кодов заключается в преобразовании \(N\) независимых копий исходного двоичного симметричного канала (BSC) или двоичного канала с аддитивным белым гауссовским шумом (BI-AWGN) в \(N\) «поляризованных» каналов. Преобразование выполняется с помощью рекурсивной структуры, основанной на ядре Арикана — матрице \(2 \times 2\):

\[ G_2 = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \]

Для длины \(N = 2^n\) матрица кодирования \(G_N\) строится как \(n\)-кратное произведение Кронекера матрицы \(G_2\):

\[ G_N = G_2^{\otimes n} \]

Входные биты \(u_1, u_2, \dots, u_N\) преобразуются в кодовые символы \(x_1, x_2, \dots, x_N\) по формуле:

\[ \mathbf{x} = \mathbf{u} \cdot G_N \]

После передачи по \(N\) независимым каналам и приёма сигналов \(y_1, y_2, \dots, y_N\) декодер последовательно оценивает биты \(u_i\) в порядке возрастания индекса, используя уже принятые решения для предыдущих битов. Этот процесс называется последовательным исключением (successive cancellation, SC).

Выбор информационных битов

Не все \(N\) каналов становятся одинаково надёжными. В результате поляризации часть каналов (с индексами, соответствующими «хорошим» каналам) имеет высокую пропускную способность, а часть — низкую. Для передачи информации используются только биты, соответствующие «хорошим» каналам. Остальные биты (замороженные биты) фиксируются на известные значения (обычно 0). Набор индексов «хороших» каналов определяется заранее на основе расчёта надёжности (например, с помощью алгоритма плотности эволюции или метода Гауссовой аппроксимации).

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

По типу декодирования

• Полярные коды с последовательным исключением (SC-полярные коды) — базовый алгоритм, имеющий сложность \(O(N \log N)\).
• Полярные коды с последовательным исключением и списком (SCL-полярные коды) — модификация, при которой декодер хранит \(L\) наиболее вероятных путей (кандидатов). Сложность \(O(L \cdot N \log N)\). При \(L = 32\) или \(L = 64\) производительность приближается к турбо-кодам и LDPC-кодам.
• Полярные коды с CRC-аппаратным декодированием (CRC-aided SCL) — к списку кандидатов добавляется проверка циклическим избыточным кодом (CRC), что позволяет отбрасывать неверные пути. Используется в 5G NR.

По длине кодового слова

• Короткие коды (длина до 256 бит) — применяются в каналах управления 5G.
• Средние коды (длина от 512 до 2048 бит) — используются в спутниковой связи и некоторых системах хранения данных.
• Длинные коды (длина от 4096 бит и выше) — теоретически достигают пропускной способности, но на практике требуют больших вычислительных ресурсов.

Характеристики

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

• Достижение пропускной способности — строго доказано для симметричных каналов без памяти.
• Низкая сложность кодирования — \(O(N \log N)\).
• Детерминированная структура — не требует случайных перестановок, как турбо-коды.
• Хорошая производительность при коротких длинах — особенно в сочетании с CRC и SCL-декодированием.

Недостатки

• Высокая задержка декодирования — последовательное исключение требует обработки битов по порядку, что ограничивает параллелизм.
• Чувствительность к ошибкам в замороженных битах — ошибка в ранних битах может распространяться на последующие.
• Сложность выбора информационных битов — для длинных кодов требуется точный расчёт надёжности.

Применение

5G NR (New Radio)

Полярные коды используются для кодирования канала управления (UCI — Uplink Control Information, DCI — Downlink Control Information) и широковещательного канала (PBCH — Physical Broadcast Channel). В стандарте 3GPP Release 15 (2018) полярные коды заменили турбо-коды для этих целей. Для канала данных (PUSCH/PDSCH) по-прежнему применяются LDPC-коды.

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

Полярные коды применяются в системах спутниковой связи для повышения помехоустойчивости при ограниченной мощности передатчика. Например, в проектах по созданию низкоорбитальных спутниковых группировок (Starlink, OneWeb) используются полярные коды с SCL-декодированием.

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

В системах хранения данных (например, твердотельные накопители, NAND-флеш-память) полярные коды применяются для коррекции ошибок, вызванных износом ячеек и шумами чтения. Их преимущество — низкая сложность кодирования и возможность адаптации к изменяющимся условиям канала.

Квантовая связь

В квантовых коммуникациях полярные коды используются для коррекции ошибок в квантовых ключах (QKD — Quantum Key Distribution) и для кодирования квантовых состояний.

Пример

Рассмотрим полярный код длины \(N = 4\) (2 канала). Исходный канал — двоичный симметричный канал с вероятностью ошибки \(p = 0.1\). Матрица кодирования:

\[ G_4 = G_2^{\otimes 2} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{pmatrix} \]

Пусть информационные биты: \(u_3 = 1\), \(u_4 = 0\) (индексы 3 и 4 — «хорошие» каналы). Замороженные биты: \(u_1 = 0\), \(u_2 = 0\). Кодовые символы:

\[ \mathbf{x} = (0, 0, 1, 0) \cdot G_4 = (1, 1, 1, 0) \]

После передачи по каналу с шумом приёмник получает, например, \(y = (1, 0, 1, 0)\). Декодер SC последовательно оценивает:

• \(u_1\) (заморожен) — 0.
• \(u_2\) (заморожен) — 0.
• \(u_3\) — вычисляется как \(y_1 \oplus y_2 \oplus y_3 \oplus y_4 = 1 \oplus 0 \oplus 1 \oplus 0 = 0\) (ошибка, так как истинное значение 1).
• \(u_4\) — вычисляется как \(y_3 \oplus y_4 = 1 \oplus 0 = 1\) (ошибка, истинное значение 0).

Таким образом, при \(p = 0.1\) вероятность ошибки для данного кода составляет около 0.2. Для увеличения длины кода вероятность ошибки снижается.

Критика

Несмотря на теоретическую привлекательность, полярные коды имеют ряд ограничений. Основная критика связана с высокой задержкой декодирования при последовательном исключении, что делает их менее подходящими для приложений реального времени с жёсткими требованиями к задержке (например, голосовая связь). Кроме того, для достижения производительности, сопоставимой с турбо-кодами или LDPC-кодами, требуются большие длины кодовых слов (более 10 000 бит), что увеличивает сложность реализации в аппаратуре.

Также отмечается, что полярные коды чувствительны к ошибкам в замороженных битах, что может приводить к каскадным ошибкам. Для смягчения этого эффекта используются CRC-проверки и SCL-декодирование, но это увеличивает сложность.

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

• Эрдал Арикан получил премию IEEE Claude E. Shannon Award в 2018 году за разработку полярных кодов.
• Полярные коды являются единственным классом кодов, для которых доказано достижение пропускной способности канала без использования случайных кодовых книг.
• В 2017 году компания Huawei активно лоббировала включение полярных кодов в стандарт 5G, что и было реализовано в 3GPP Release 15.

Источники

• Arıkan, E. (2009). «Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels». IEEE Transactions on Information Theory.
• 3GPP TS 38.212: «Multiplexing and channel coding» (Release 15).
• Tal, I., & Vardy, A. (2015). «List Decoding of Polar Codes». IEEE Transactions on Information Theory.
• Korada, S. B., & Urbanke, R. L. (2010). «Polar Codes are Optimal for Lossy Source Coding». IEEE Transactions on Information Theory.