Недвоичные циклические коды

Недвоичные циклические коды — это класс корректирующих кодов, алфавит которых состоит не из двух символов (0 и 1), а из элементов конечного поля — поля Галуа GF(q), где q — степень простого числа (q = p^m, p — простое). Как и двоичные циклические коды, они обладают свойством цикличности: любой циклический сдвиг кодового слова, рассматриваемый как последовательность символов из GF(q), также является кодовым словом. Недвоичные коды применяются для обнаружения и исправления ошибок в цифровых системах передачи и хранения данных, особенно при работе с многомодульными сигналами (например, в каналах с многопозиционной модуляцией) или при кодировании недвоичных данных, таких как байты или символы в памяти современных процессоров (ECC-память). Наиболее известными представителями являются коды Рида — Соломона, нашедшие широкое применение в оптических дисках, спутниковой связи и системах массового хранения.

История

Теория недвоичных циклических кодов начала развиваться в конце 1950-х — начале 1960-х годов как обобщение двоичных кодов, впервые систематически описанных У. У. Петерсоном (W. W. Peterson) в 1961 году. Важнейший этап связан с работами И. С. Рида (Irving S. Reed) и Г. Соломона (Gustave Solomon), которые в 1960 году представили код, ныне носящий их имя — код Рида — Соломона. Этот код является недвоичным циклическим, поскольку алфавит кодовых слов состоит из элементов поля GF(q). В 1960-х годах Р. Блют (R. Blahut) и Э. Берлекэмп (E. Berlekamp) разработали эффективные алгоритмы декодирования, такие как алгоритм Берлекэмпа — Месси, что сделало коды Рида — Соломона практически применимыми. К 1970-м годам недвоичные циклические коды стали стандартом в системах хранения данных (CD, DVD, Blu-ray) и спутниковой связи (например, в системе «Вояджер»). В России теория развивалась в работах А. А. Марковникова, В. Д. Колесника, Е. Т. Мирочникова, а также в рамках советской школы теории помехоустойчивого кодирования.

Определение и алгебраическая структура

Недвоичный циклический код над полем GF(q) длины n определяется как идеал факторкольца многочленов GF(q)[x]/(xⁿ — 1). Формально код является идеалом, порождённым порождающим многочленом g(x) степени r = n — k, где k — размерность кода (число информационных символов). Многочлен g(x) делит xⁿ — 1 без остатка. Все кодовые слова представляют собой многочлены степени не выше n-1, кратные g(x). Длина кода n должна удовлетворять условию n | q^m — 1, где m — минимальное целое, такое что n делит q^m — 1. Это связано с тем, что многочлен xⁿ — 1 разлагается на множители в поле GF(q^m).

Порождающий и проверочный многочлены

Порождающий многочлен g(x) имеет степень r = n — k. Его корни являются элементами поля GF(q^m) — это некоторые степени примитивного элемента α поля. Проверочный многочлен h(x) = (xⁿ — 1) / g(x) имеет степень k. Каждое кодовое слово c(x) удовлетворяет уравнению c(x) h(x) ≡ 0 mod (xⁿ — 1), что эквивалентно ортогональности проверочной матрице.

Виды и классификация

Недвоичные циклические коды делятся на несколько основных типов:

• Коды Рида — Соломона (РС-коды) — наиболее распространённый подкласс с длиной n = q — 1 (для полей GF(q)) или n = q + 1 для расширенных вариантов. Они являются максимально возможными по кодовому расстоянию для заданных n и k (код с максимальным расстоянием, MDS-код). Исправляют любые комбинации ошибок в символах поля.
• БЧХ-коды (Боуза — Чоудхури — Хоквенгема) в недвоичном варианте — циклические коды, порождающий многочлен которых имеет корнями последовательные степени α^b, α^(b+1), ..., α^(b+δ-2). Они позволяют задавать конструктивное расстояние δ. Для двоичного случая δ нечётно, для недвоичного — может быть любым.
• Коды с повторением — простейшие циклические коды, где каждый символ повторяется несколько раз; имеют низкую скорость.
• Свёрточные коды — хотя обычно рассматриваются отдельно, некоторые свёрточные коды могут быть представлены как циклические в расширенном смысле (например, коды на основе полиномов свёртки).

Параметры и характеристики

Основными параметрами недвоичного циклического кода являются:

• q — мощность алфавита (число элементов поля Галуа). Обычно q = 2^m, где m — число бит на символ (например, q = 256 для кодов Рида — Соломона, используемых в ECC-памяти).
• n — длина кода (число символов в кодовом слове).
• k — размерность кода (число информационных символов).
• Минимальное кодовое расстояние d_min — наименьшее расстояние по Хэммингу между двумя различными кодовыми словами, определяющее корректирующую способность. Для кодов Рида — Соломона d_min = n — k + 1.
• Корректирующая способность t — максимальное число ошибок в символах (не битах), которое код гарантированно может исправить: t = floor((d_min — 1)/2).
• Скорость кода R = k/n.

Для недвоичных кодов важна способность исправлять не только отдельные ошибочные символы, но и их пакеты (burst errors), так как искажение одного символа в поле GF(2^m) эквивалентно искажению m бит.

Применение

Недвоичные циклические коды, особенно коды Рида — Соломона, находят применение в следующих областях:

• Цифровая запись и хранение: компакт-диски (CD, DVD, Blu-ray), жёсткие диски, твердотельные накопители (SSD) — для защиты от ошибок чтения/записи. Например, в CD используется код Рида — Соломона с перестановкой (CIRC).
• Спутниковая и космическая связь: стандарты CCSDS (Consultative Committee for Space Data Systems) — для передачи изображений и телеметрии с космических аппаратов.
• Цифровое телевидение: стандарты DVB-T/T2, DVB-S/S2, ATSC.
• Аудио- и видеоформаты: MPEG-2, MPEG-4 используют коды Рида — Соломона для защиты потоков данных.
• Сети передачи данных: в протоколах Ethernet (10GBASE-T), WiMAX, а также в системах мобильной связи (4G LTE, 5G NR) — как часть схем помехоустойчивого кодирования (турбокоды, LDPC часто комбинируются с RS-кодами).
• Память с коррекцией ошибок (ECC): в модулях оперативной памяти ECC (Error-Correcting Code) используются коды Рида — Соломона или их разновидности для исправления однобитовых ошибок и обнаружения двубитовых.
• Сжатие данных с контролем целостности: в архиваторах (RAR, ZIP) и файловых системах (ZFS, Btrfs) — для восстановления данных после повреждений.

Пример: код Рида — Соломона RS(255, 223)

Рассмотрим код Рида — Соломона RS(255, 223) над полем GF(2^8). Параметры:

• q = 256, n = 255, k = 223.
• Минимальное расстояние d_min = 33 (n — k + 1 = 255 — 223 + 1 = 33).
• Скорость кода R = 223/255 ≈ 0,8745.
• Корректирующая способность t = 16 символов (33 — 1)/2 = 16). То есть код может исправить до 16 ошибочных байтов в одном блоке длиной 255 байт. Этот код широко используется в спутниковой связи и в системах хранения данных.

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

Основные алгоритмы декодирования недвоичных циклических кодов, особенно кодов Рида — Соломона, включают:

• Синдромное декодирование — вычисление синдрома S = r(α^i) для корней порождающего многочлена. Затем по синдромам находятся положения ошибок (через алгоритм Берлекэмпа — Месси) и их значения (через алгоритм Форни). Этот подход эффективен для кодов с малой длиной или малым числом ошибок.
• Алгоритм Берлекэмпа — Месси — итеративный метод нахождения многочлена локаторов ошибок на основе синдромов. Он требует O(n²) операций, но практически применим для кодов с n до 255.
• Алгоритм Петерсона — Горенштейна — Цирлера — для кодов с малым расстоянием (d_min ≤ 10) решает систему линейных уравнений.
• Декодирование с мягкими решениями (например, алгоритм Кётера — Варма) — используется в современных системах для повышения эффективности при низком отношении сигнал/шум.

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

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

• Высокая корректирующая способность для пакетов ошибок.
• Свойство MDS (maximum distance separable) для кодов Рида — Соломона: при фиксированных n и k они достигают теоретически максимального минимального расстояния.
• Относительно простая реализация алгебраического декодирования.
• Хорошо подходят для многомодульной модуляции (QAM, PSK) в цифровой связи.

Недостатки:

• Ограниченная длина кодов (n ≤ q-1 для RS-кодов), что для больших q требует больших полей и высокой сложности.
• Сложность декодирования растёт квадратично с длиной кода, что ограничивает применение в системах с очень большими блоками (миллионы символов).
• Для кодов с малым алфавитом (q = 4, 8) эффективность исправления пакетов ошибок ниже, чем для двоичных кодов с перемежением.
• При использовании в каналах с редкими ошибками более выгодны двоичные LDPC-коды, которые имеют лучшие пороговые характеристики.

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

• Коды Рида — Соломона являются частным случаем БЧХ-кодов при n = q — 1.
• В 1977 году коды Рида — Соломона были выбраны для передачи изображений с космических аппаратов «Вояджер» к Юпитеру и Сатурну; они позволили исправить ошибки, вызванные шумами на расстоянии миллиардов километров.
• В CD-дисках используется схема CIRC (Cross-Interleaved Reed-Solomon Code), где два кода Рида — Соломона (C1 и C2) переплетаются для исправления как одиночных, так и пакетных ошибок.
• В стандарте цифрового телевидения DVB-T2 для кодирования данных используется комбинация БЧХ-кода и кода Рида — Соломона — так называемая схема с внешним и внутренним кодированием (concatenated code).
• Недвоичные циклические коды являются основой для построения каскадных кодов и кодов с перемежением, что повышает их устойчивость к длинным пакетам ошибок.

См. также

• Код Рида — Соломона
• Коды Боуза — Чоудхури — Хоквенгема (БЧХ-коды)
• Циклический код
• Двоичный код
• Конечное поле
• Теория информации

Источники

• Петерсон У. У., Уэлдон Э. Дж. Коды, исправляющие ошибки. — М.: Мир, 1976.
• Бёрлекэмп Э. Алгебраическая теория кодирования. — М.: Мир, 1971.
• Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. — М.: Техносфера, 2005.
• Блахут Р. Теория и практика кодов, контролирующих ошибки. — М.: Мир, 1986.
• Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. — М.: Связь, 1979.
• Лидл Р., Нидеррайтер Г. Конечные поля. — М.: Мир, 1988.
• Марковников А. А. Недвоичные циклические коды и их применение // Проблемы передачи информации. — 1975. — Т. 11, № 3. — С. 3–13.