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

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

История

Идея циклических кодов восходит к работам американского математика и инженера Уильяма Уэсли Питерсона (William Wesley Peterson), который в 1961 году опубликовал монографию «Error-Correcting Codes», систематизировавшую теорию помехоустойчивого кодирования. Однако основы были заложены ранее: в 1957 году американский математик Юджин Прагер (Eugene Prange) впервые сформулировал понятие циклического кода. Дальнейшее развитие связано с именами Роберта Галлагера (Robert Gallager), Элвина Берлекэмпа (Elwyn Berlekamp) и Джеймса Мэсси (James Massey), которые разработали эффективные алгоритмы декодирования, такие как алгоритм Берлекэмпа — Мэсси (Berlekamp–Massey algorithm). В СССР теория циклических кодов развивалась в работах Владимира Васильевича Зяблова, Юрия Леонидовича Сагаловича и других учёных.

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

Циклические коды формально определяются как идеалы в кольце многочленов над конечным полем Галуа GF(q). Кодовые слова представляются многочленами степени не выше n-1, где n — длина кода. Код является циклическим, если для любого кодового многочлена a(x) многочлен x·a(x) mod (xⁿ−1) также принадлежит коду.

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

Циклический код полностью задаётся порождающим многочленом g(x) степени r = n − k, где k — размерность кода (число информационных символов). Порождающий многочлен является делителем многочлена xⁿ−1. Все кодовые многочлены кратны g(x): c(x) = u(x)·g(x), где u(x) — информационный многочлен степени не выше k−1.

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

Проверочный многочлен h(x) определяется из соотношения g(x)·h(x) = xⁿ−1. Он используется для проверки принадлежности слова коду: если c(x)·h(x) mod (xⁿ−1) = 0, то слово является кодовым.

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

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

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

Коды БЧХ — это класс циклических кодов, способных исправлять несколько ошибок. Они были независимо открыты в 1959–1960 годах американскими математиками Робертом Боузом (Robert Bose) и Д. К. Рэем-Чоудхури (D. K. Ray-Chaudhuri), а также французским инженером Алексисом Хоквингемом (Alexis Hocquenghem). Для кода БЧХ с конструктивным расстоянием d гарантируется исправление любых t = ⌊(d−1)/2⌋ ошибок. Наиболее распространены двоичные коды БЧХ, например, код (15,7) исправляет до 2 ошибок.

Коды Рида — Соломона (РС, RS)

Коды Рида — Соломона — это недвоичные циклические коды, работающие с символами из поля GF(q), где q > 2. Они были предложены в 1960 году американскими математиками Ирвингом Ридом (Irving Reed) и Гюставом Соломоном (Gustave Solomon). Код РС с длиной n = q−1 может исправлять до t ошибок при минимальном расстоянии d = n−k+1 = 2t+1. Коды РС широко применяются в системах хранения данных (CD, DVD, RAID 6) и спутниковой связи.

Коды Хэмминга

Циклические коды Хэмминга — это частный случай кодов БЧХ с минимальным расстоянием d=3, исправляющие одну ошибку. Длина кода Хэмминга равна 2^m−1, количество информационных символов — 2^m−m−1. Например, код (7,4) является классическим циклическим кодом Хэмминга.

Коды с повторением и проверкой на чётность

Простейшие циклические коды — это коды с повторением (например, код (3,1) с порождающим многочленом 1+x+x²) и коды с проверкой на чётность (порождающий многочлен 1+x). Однако они не обладают высокой корректирующей способностью.

Устройство и характеристики

Параметры

Циклический код характеризуется следующими параметрами:

• Длина кода n — число символов в кодовом слове.
• Размерность k — число информационных символов.
• Минимальное расстояние d — минимальное расстояние Хэмминга между любыми двумя кодовыми словами. Определяет корректирующую способность: код гарантированно исправляет t = ⌊(d−1)/2⌋ ошибок.
• Скорость кода R = k/n — отношение числа информационных символов к общей длине.

Кодирование

Кодирование циклического кода выполняется умножением информационного многочлена u(x) на порождающий многочлен g(x). Для систематического кодирования (когда информационные символы остаются в явном виде) используется процедура деления: к информационному многочлену дописываются r нулей, результат делится на g(x), и остаток добавляется в конец. В аппаратной реализации кодирование выполняется с помощью линейного сдвигового регистра с обратной связью (Linear Feedback Shift Register, LFSR).

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

Декодирование циклических кодов включает три этапа:

1. Вычисление синдрома — остатка от деления принятого многочлена r(x) на g(x). Если синдром равен нулю, ошибок нет (или они не обнаружены).
2. Поиск позиций ошибок — для кодов БЧХ и РС используется алгоритм Берлекэмпа — Мэсси или алгоритм Питерсона — Горенстейна — Цирлера (Peterson–Gorenstein–Zierler algorithm).
3. Исправление ошибок — инвертирование найденных символов.

Для кодов с малой длиной возможен табличный метод декодирования, где каждому синдрому сопоставляется вектор ошибок.

Применение

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

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

• Компакт-диски (CD) — используется код Рида — Соломона (32,28) с перекрестным перемежением (Cross-Interleaved Reed–Solomon Code, CIRC).
• DVD — применяются коды Рида — Соломона (208,192) и (182,172).
• Жёсткие диски (HDD) — в современных накопителях используются коды БЧХ и LDPC (Low-Density Parity-Check), которые также являются циклическими.
• RAID 6 — для восстановления данных при отказе двух дисков применяются коды Рида — Соломона.

Передача данных

• Спутниковая связь — коды Рида — Соломона используются в стандартах DVB-S (Digital Video Broadcasting — Satellite) и DVB-S2.
• Сотовая связь — в стандарте GSM применяются циклические коды для защиты служебных каналов.
• Wi-Fi (IEEE 802.11) — в протоколах используются коды БЧХ и LDPC.
• Квантовые коммуникации — циклические коды применяются для исправления ошибок в квантовых каналах.

Промышленность

• Контроль целостности данных — циклические избыточные коды (CRC, Cyclic Redundancy Check) являются подклассом циклических кодов и широко используются в протоколах Ethernet, USB, Bluetooth и в файловых системах.

Примеры

Пример 1: Код Хэмминга (7,4)

Порождающий многочлен: g(x)=1+x+x³. Длина n=7, размерность k=4, минимальное расстояние d=3. Код исправляет одну ошибку. Для информационного слова 1011 (многочлен 1+x²+x³) кодовое слово получается как u(x)·g(x) = (1+x²+x³)·(1+x+x³) = 1+x+x²+x⁴+x⁵+x⁶ (соответствует слову 1110111).

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

Используется в системах спутниковой связи. Длина 255 байт, из которых 223 байта информационные. Код исправляет до 16 ошибок в байтах. Скорость кода R ≈ 0.874.

Критика

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

• Фиксированная длина — классические циклические коды имеют жёстко заданную длину n, которая должна быть делителем 2^m−1 для двоичных кодов. Для произвольных длин используются укороченные циклические коды, но они теряют свойство цикличности.
• Сложность декодирования — для кодов с высокой корректирующей способностью (большое t) алгоритмы декодирования становятся вычислительно сложными. В современных системах их часто заменяют более эффективными LDPC-кодами или турбокодами.
• Неоптимальность для каналов с пакетными ошибками — хотя циклические коды хорошо исправляют случайные ошибки, для длинных пакетных ошибок (например, в мобильной связи) требуются дополнительные методы перемежения.

Источники

• Питерсон У. У., Уэлдон Э. Дж. Коды, исправляющие ошибки. — М.: Мир, 1976.
• Блейхут Р. Теория и практика кодов, контролирующих ошибки. — М.: Мир, 1986.
• Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. — М.: Связь, 1979.
• Зяблов В. В., Королев А. В., Портной С. Л. Помехоустойчивое кодирование. — М.: Радио и связь, 1986.
• Gallager R. G. Low-Density Parity-Check Codes. — MIT Press, 1963.
• Berlekamp E. R. Algebraic Coding Theory. — McGraw-Hill, 1968.