Замороженные биты

Замороженные биты (англ. frozen bits) — в помехоустойчивом кодировании, в частности в полярных кодах, фиксированные, заранее известные значения, которые вставляются в информационную последовательность на позициях с наименьшей надёжностью (наименьшей пропускной способностью подканалов) перед процедурой кодирования. В отличие от информационных битов, которые несут полезные данные, замороженные биты не изменяются в процессе кодирования и служат для обеспечения коррекции ошибок при декодировании, обычно устанавливаются в ноль.

История

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

В 2016 году полярные коды с замороженными битами были стандартизированы в 3GPP для канала управления восходящей линии связи (PUCCH) в стандарте 5G NR (New Radio). Это стало первым массовым применением данной технологии в коммерческих системах связи.

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

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

Полярные коды основаны на операции поляризации: два независимых канала с одинаковой пропускной способностью объединяются в два новых подканала — один с лучшей, другой с худшей характеристикой. При многократном повторении этой операции (например, для длины кода N = 2ⁿ) образуется набор из N подканалов, пропускная способность которых стремится к 0 или 1.

Выбор замороженных битов

Перед кодированием определяется, какие подканалы являются «надёжными» (с высокой пропускной способностью), а какие — «ненадёжными». Для этого используются различные критерии:

• Пропускная способность (I(W)): подканалы с I(W) > 0.5 считаются надёжными.
• Вероятность ошибки (Pe): подканалы с Pe < порогового значения.
• Алгоритм плотности эволюции (Density Evolution): для каждого подканала вычисляется вероятность ошибки при декодировании.

На позициях «ненадёжных» подканалов размещаются замороженные биты (обычно нули). Информационные биты занимают оставшиеся позиции.

Кодирование

Процесс кодирования полярного кода длины N с K информационными битами и N-K замороженными битами описывается матричным умножением:

u = x * G

где:

• u — вектор длины N, содержащий информационные биты на позициях I (множество индексов надёжных подканалов) и замороженные биты на позициях F (множество индексов ненадёжных подканалов).
• x — вектор кодового слова длины N.
• G — матрица поляризации (обычно матрица Кронекера от базовой матрицы [[1,0],[1,1]]).

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

При декодировании используется алгоритм последовательного исключения (Successive Cancellation, SC). Декодер последовательно оценивает каждый бит, начиная с первого. Если позиция соответствует замороженному биту, декодер просто присваивает ему известное значение (ноль). Если позиция информационная, декодер вычисляет отношение правдоподобия (LLR) и принимает решение. Наличие замороженных битов позволяет декодеру корректировать ошибки, так как они служат опорными точками.

Классификация и виды

По способу выбора

• Фиксированные замороженные биты: все замороженные биты устанавливаются в ноль. Это наиболее распространённый подход.
• Динамические замороженные биты: значения замороженных битов могут зависеть от предыдущих информационных битов. Используются в модифицированных полярных кодах (например, Polar Codes with Dynamic Frozen Bits) для улучшения характеристик.

По типу кода

• Полярные коды с замороженными битами: классические полярные коды, где замороженные биты размещаются на «плохих» подканалах.
• Полярные коды с CRC (Cyclic Redundancy Check): замороженные биты используются для размещения контрольной суммы, что улучшает обнаружение ошибок.
• Полярные коды с LDPC (Low-Density Parity-Check): в некоторых гибридных схемах замороженные биты могут быть частью кода LDPC.

Применение

Телекоммуникации

• 5G NR: полярные коды с замороженными битами используются для кодирования канала управления восходящей линии связи (PUCCH) и канала управления нисходящей линии связи (PDCCH). В стандарте 3GPP TS 38.212 определена конфигурация замороженных битов для различных длин кода.
• Спутниковая связь: применяются в системах с низкой задержкой, где требуется высокая надёжность.
• Оптоволоконные линии: используются в системах передачи данных с высокой скоростью (например, 100G Ethernet).

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

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

Квантовые вычисления

• Квантовые полярные коды: замороженные биты используются для стабилизации квантовых состояний при коррекции ошибок.

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

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

• Низкая сложность декодирования: алгоритм SC имеет сложность O(N log N), что значительно меньше, чем у турбокодов или LDPC.
• Достижение пропускной способности: при бесконечной длине кода полярные коды с замороженными битами достигают пропускной способности канала.
• Детерминированность: структура замороженных битов заранее известна, что упрощает реализацию.

Недостатки

• Чувствительность к длине кода: при коротких длинах (N < 128) эффективность падает.
• Зависимость от канала: выбор замороженных битов зависит от характеристик канала, что требует адаптации.
• Ограниченная гибкость: для каждого набора параметров (N, K) требуется отдельный расчёт.

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

• Название «замороженные биты» (frozen bits) было предложено Арыканом из-за их фиксированного, неизменного состояния в процессе кодирования.
• В 2017 году компания Qualcomm предложила использовать полярные коды с замороженными битами для 5G, что привело к их стандартизации.
• В некоторых реализациях замороженные биты могут быть не нулями, а случайными значениями, известными только приёмнику и передатчику, что повышает безопасность.

Источники

• Arıkan, E. (2008). «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. (2013). «How to Construct Polar Codes». IEEE Transactions on Information Theory.
• Korada, S. B., & Urbanke, R. L. (2010). «Polar Codes: Characterization of Exponent, Bounds, and Constructions». IEEE Transactions on Information Theory.
• Arikan, E. (2009). «A Performance Comparison of Polar Codes and Reed-Muller Codes». IEEE Communications Letters.