Циклический код

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

История

Теоретические основы циклических кодов были заложены в середине XX века. В 1957 году американский математик Юджин Прайндж (Eugene Prange) впервые описал класс кодов, замкнутых относительно циклического сдвига. В 1960 году американские инженеры Роберт Галлагер (Robert Gallager) и Ирвинг Рид (Irving Reed) независимо друг от друга разработали методы построения циклических кодов на основе неприводимых многочленов. Значительный вклад в теорию внесли советские учёные В. Д. Колесник и Э. Т. Миронов, которые в 1960-х годах предложили эффективные алгоритмы декодирования для циклических кодов, используемых в отечественных системах связи. В 1970-х годах циклические коды стали стандартом для многих промышленных протоколов, включая Ethernet (код CRC-32) и системы спутниковой связи.

Математическое описание

Циклические коды основаны на алгебре многочленов над конечным полем Галуа GF(q), где q — простое число или степень простого числа. Для двоичных кодов q=2. Кодовое слово длины n представляется многочленом степени не выше n-1:

\[ c(x) = c_{n-1}x^{n-1} + c_{n-2}x^{n-2} + \dots + c_1x + c_0, \quad c_i \in \{0,1\} \]

Свойство цикличности означает, что если \(c(x)\) — кодовое слово, то \(x \cdot c(x) \mod (x^n - 1)\) также является кодовым словом. Это эквивалентно сдвигу коэффициентов вправо (или влево) с циклическим переносом.

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

Циклический код полностью задаётся порождающим многочленом \(g(x)\) степени \(r = n - k\), где \(k\) — число информационных символов, а \(n\) — длина кода. Многочлен \(g(x)\) является делителем \(x^n - 1\) и имеет степень \(r\). Все кодовые слова образуются как произведения информационного многочлена \(m(x)\) степени не выше \(k-1\) на \(g(x)\):

\[ c(x) = m(x) \cdot g(x) \]

При этом \(g(x)\) должен быть неприводимым (или произведением неприводимых многочленов) для обеспечения минимального расстояния кода.

Проверочный многочлен

Проверочный многочлен \(h(x)\) определяется из соотношения:

\[ g(x) \cdot h(x) = x^n - 1 \]

Степень \(h(x)\) равна \(k\). Условие принадлежности многочлена \(c(x)\) к коду: \(c(x) \cdot h(x) \equiv 0 \mod (x^n - 1)\).

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

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

По исправляющей способности

• Коды с обнаружением ошибок — позволяют только определить факт наличия ошибки, но не её местоположение (например, CRC).
• Коды с исправлением одиночных ошибок — исправляют одну ошибку в блоке (например, код Хэмминга, который является циклическим при определённых условиях).
• Коды с исправлением многократных ошибок — исправляют две и более ошибки (коды БЧХ, Рида — Соломона).

По типу многочлена

• Примитивные коды — порождающий многочлен является примитивным многочленом над GF(q). Длина такого кода \(n = q^m - 1\).
• Непримитивные коды — порождающий многочлен не является примитивным, длина кода меньше \(q^m - 1\).

По области применения

• Систематические коды — информационные символы входят в кодовое слово в явном виде, что упрощает декодирование.
• Несистематические коды — информационные символы не выделяются явно, все символы кодового слова являются проверочными.

Примеры циклических кодов

Коды CRC (Cyclic Redundancy Check)

CRC — это семейство циклических кодов, предназначенных исключительно для обнаружения ошибок. Наиболее распространённые варианты:

• CRC-32 (полином 0x04C11DB7) — используется в Ethernet, ZIP, PNG. Длина кода 32 бита, обнаруживает все одиночные, двойные и пакетные ошибки длиной до 32 бит.
• CRC-16 (полином 0x8005) — применяется в протоколах Modbus, USB. Длина 16 бит.
• CRC-8 (полином 0x07) — используется в 1-Wire, SMBus.

Коды БЧХ (Боуза — Чоудхури — Хоквингема)

Названы в честь Р. Боуза, Д. Чоудхури и А. Хоквингема (1960). Позволяют задавать минимальное расстояние кода \(d_{\min}\) и исправлять до \(t = \lfloor (d_{\min} - 1)/2 \rfloor\) ошибок. Порождающий многочлен строится как произведение нескольких минимальных многочленов. Пример: код БЧХ(15,7) с \(d_{\min}=5\) исправляет две ошибки.

Коды Рида — Соломона

Частный случай недвоичных циклических кодов БЧХ, работающих над полем GF(q), где q — степень простого числа. Широко применяются в системах хранения данных (CD, DVD, QR-коды), спутниковой связи и цифровом телевидении (DVB). Пример: RS(255,223) — код длиной 255 байт, из которых 223 информационных, исправляет до 16 ошибок.

Применение

Циклические коды нашли применение в самых разных областях цифровой техники:

• Сети передачи данных — CRC-32 в Ethernet, CRC-16 в HDLC, CRC-8 в CAN-шине.
• Хранение данных — коды Рида — Соломона в RAID-массивах, жёстких дисках, оптических носителях.
• Цифровое телевидение и радиовещание — стандарты DVB-T, DVB-S, ATSC используют коды БЧХ и Рида — Соломона.
• Космическая связь — коды Рида — Соломона применяются в системах связи с зондами (например, «Вояджер»).
• Криптография — циклические коды используются в некоторых криптосистемах (например, код Мак-Элиса).

Достоинства и недостатки

Достоинства

• Простота аппаратной реализации на сдвиговых регистрах.
• Высокая скорость кодирования и декодирования.
• Возможность обнаружения пакетных ошибок (для CRC).
• Хорошая корректирующая способность для кодов БЧХ и Рида — Соломона.

Недостатки

• Ограниченная длина кода (зависит от степени порождающего многочлена).
• Для кодов с исправлением ошибок требуется более сложное декодирование (алгоритм Берлекэмпа — Мэсси, алгоритм Питерсона — Горенстейна — Цирлера).
• Неэффективность при высокой плотности ошибок (требуются более мощные коды, например, турбокоды или LDPC).

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

• Код CRC-32, используемый в Ethernet, был разработан в 1975 году и остаётся стандартом до сих пор.
• Коды Рида — Соломона используются в системе GPS для коррекции ошибок в навигационных сообщениях.
• В 1990-х годах советские инженеры разработали циклический код (31,16) с порождающим многочленом \(x^{15} + x^{11} + x^7 + x^5 + 1\) для системы управления космическими аппаратами «Энергия» — «Буран».
• Теоретическая основа циклических кодов лежит в основе более сложных конструкций, таких как свёрточные коды и турбокоды.

Источники

• Блейхут Р. Теория и практика кодов, контролирующих ошибки. — М.: Мир, 1986.
• Колесник В. Д., Миронов Э. Т. Циклические коды. — М.: Связь, 1972.
• Peterson W. W., Weldon E. J. Error-Correcting Codes. — MIT Press, 1972.
• MacWilliams F. J., Sloane N. J. A. The Theory of Error-Correcting Codes. — North-Holland, 1977.
• ГОСТ Р 34.11-2012 (Информационная технология. Криптографическая защита информации. Функция хэширования) — содержит описание CRC как вспомогательного средства.