Штабелированные коды

Штабелированные коды — это класс помехоустойчивых кодов, используемых в системах передачи и хранения цифровых данных. Основная идея заключается в том, что исходная информационная последовательность кодируется, а затем разбивается на ортогональные или псевдоортогональные части (слои), которые объединяются (штабелируются) для формирования результирующего кодового слова. Такой подход позволяет одновременно реализовать высокую корректирующую способность и обеспечивать гибкость в отношении длины и скорости кода, а также упрощать процедуры кодирования и декодирования.

История и развитие

Термин «штабелированные коды» (stacked codes, layered codes) не является формальным названием единственного алгоритма, а скорее описывает класс методов, объединённых общей архитектурой. Предпосылки к появлению этой концепции возникли в середине XX века, вскоре после создания теории помехоустойчивого кодирования Клодом Шенноном.

Ранние этапы

В 1940-х — 1950-х годах были разработаны линейные блочные коды (Хэмминга, Рида — Соломона, Боуза — Чоудхури — Хоквингема) и свёрточные коды. Однако все они страдали либо от ограничений по длине кодового слова, либо от экспоненциальной сложности декодирования при стремлении к теоретической пропускной способности канала. Идея «штабелирования» появилась как способ обойти эти ограничения: вместо того чтобы строить один сложный декодер, предлагалось использовать несколько параллельных или последовательно соединённых простых декодеров, каждый из которых обрабатывает свою часть кодовой структуры.

Каскадные и турбо-коды

Исторически первыми широко применяемыми кодами с многоуровневой структурой стали каскадные коды (1966 г., Форни). В них, однако, «штабелирование» понималось больше как последовательное соединение (внешний код — внутренний код), что позволяло увеличить минимальное кодовое расстояние. Настоящий прорыв произошёл в 1993 году с открытием турбо-кодов (Берру, Главьё, Титтимайшя). В турбо-кодах два (или более) рекурсивных систематических свёрточных кода соединяются параллельно через перемежитель. Это классический пример штабелирования: два кода работают над одной и той же информацией, но в разном порядке следования бит. Итеративное декодирование с обменом «мягкими» решениями между декодерами позволило достичь результатов, близких к пределу Шеннона.

Коды с малой плотностью проверок на чётность (LDPC)

Одновременно с турбо-кодами была переоткрыта технология LDPC-кодов (впервые предложенная Галлагером в 1963 году). LDPC-коды представляют собой линейные блочные коды, задаваемые разреженной матрицей проверок на чётность. Эти коды также могут быть интерпретированы как штабелированные. Современные варианты, такие как квазициркуляционные (QC) LDPC, строятся из нескольких циклических сдвигов базовой матрицы, что по сути является «штабелированием» однотипных кодовых подслов. Сложность декодирования LDPC-кодов растёт линейно с длиной блока, что делает их оптимальными для многих современных стандартов связи (Wi-Fi, DVB, 5G NR) и систем хранения данных.

Современное состояние

Сегодня под штабелированными кодами часто понимают класс многоуровневых (multi-level) кодов, где информационные биты распределяются по нескольким уровням, каждый из которых защищается собственным помехоустойчивым кодом. Такие коды широко применяются в цифровом телевидении (DVB), в оптических системах связи и в флэш-памяти (NAND). Также активно развивается направление полярных кодов (Арикан, 2009), которые, хотя и не относятся к штабелированным в классическом смысле, используют канальное вырождение — последовательное «штабелирование» отдельных подканалов для достижения идеальной ёмкости канала.

Принцип работы и классификация

Штабелированные коды объединяет общий принцип: разбиение задачи кодирования на несколько подзадач, каждая из которых решается независимым кодером, а затем результаты этих решений объединяются. Различают несколько основных архитектур: параллельное, последовательное и иерархическое штабелирование.

Параллельное штабелирование (турбо-коды)

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

Этот подход обеспечивает очень высокую корректирующую способность, но требует сложного декодера и может страдать от эффекта «битовой ямы» при плохом перемежении.

Последовательное штабелирование

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

Иерархическое (многоуровневое) штабелирование

Этот подход применяется, когда канал передачи вносит разные уровни искажений для разных разрядов символа. Например, при модуляции QAM (квадратурная амплитудная модуляция) с 256 точками сигнала, младшие биты символа более уязвимы к шуму, чем старшие. Многоуровневое кодирование (MLC) разбивает информационные биты на группы по степени важности и кодирует каждую группу своим кодом с соответствующей степенью защиты. Так, старшие биты кодируются кодом с высокой скоростью и низкой избыточностью, а младшие — кодом с высокой избыточностью (низкой скоростью). Это позволяет существенно повысить спектральную эффективность в каналах с аддитивным белым гауссовским шумом (AWGN).

Применение

Штабелированные коды нашли широкое применение в современной цифровой технике, где требуется высокая надёжность передачи больших объёмов данных.

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

• Стандарты сотовой связи: LTE и 5G NR используют LDPC-коды для канала данных и полярные коды для служебных каналов управления. Турбо-коды были основой 3G (UMTS) и 4G (LTE) для канала данных.
• Спутниковая и космическая связь: применяются каскадные и турбо-коды для обеспечения связи на гигантских расстояниях (Deep Space Network).
• Цифровое телевидение (DVB-T2, DVB-S2X): используют LDPC-коды в сочетании с перемежением.

Системы хранения данных

• Жёсткие диски (HDD): современные HDD используют LDPC-коды для коррекции ошибок считывания (например, код с низкой плотностью проверок).
• Твердотельные накопители (SSD): флэш-память NAND (SLC, MLC, TLC, QLC) активно использует многоуровневые штабелированные коды для защиты от износа и ошибок чтения/записи.

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

• Поверхностные коды (surface codes) — это класс стабилизаторных кодов, которые фактически являются реализацией штабелированного подхода в квантовой коррекции ошибок. Ошибки в квантовых битах корректируются путём многократного повторения парах измерений (штабелирование слоёв).

Спутниковая навигация

Системы GPS и ГЛОНАСС используют специальные помехоустойчивые коды с перемежением, что также является формой штабелированного кодирования для борьбы с пакетными ошибками.

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

Ключевые достоинства штабелированных кодов:

• Близость к пределу Шеннона: при правильном проектировании (достаточная длина блока, хорошее перемежение) обеспечивают скорость передачи, близкую к теоретическому максимуму.
• Гибкость: можно варьировать скорость кода (от 1/3 до 0,95) и длину блока в широких пределах, используя одни и те же базовые кодеры/декодеры.
• Масштабируемость: сложность декодирования растёт полиномиально (часто линейно) от длины блока, что позволяет реализовывать коды длиной до миллиона бит на современном оборудовании.
• Параллельность декодирования: итеративные декодеры для LDPC и турбо-кодов допускают распараллеливание на многоядерных процессорах и ПЛИС.

Недостатки:

• Задержка и сложность декодирования: итеративный обмен данными между декодерами увеличивает вычислительную сложность и энергопотребление по сравнению с простыми кодами (например, Хэмминга).
• Пороговые эффекты: при малом количестве итераций или плохом перемежении может наблюдаться «ошибка-перекличка» (error floor) — резкое ухудшение эффективности при низком уровне шума.
• Зависимость от контекста: для коротких сообщений (меньше 100–200 бит) штабелированные коды часто уступают по эффективности классическим блочным кодам (например, кодам Рида — Соломона).