Циклические коды: кодирование через многочлены и деление с остатком

Каждый кадр Ethernet несёт в хвосте четыре байта CRC-32; тот же приём охраняет ZIP-архивы и PNG-файлы. Приёмник делает одну операцию — делит принятое слово на заранее известный многочлен — и по остатку выносит вердикт: канал чистый или в данных дыра. Никаких проверочных битов на степенях двойки, как в коде Хэмминга, — вся механика свелась к школьному делению уголком, только в арифметике из нулей и единиц. За этим лаконизмом стоит целый класс — циклические коды, и в нём живут все рабочие лошадки связи: CRC, коды БЧХ, Рида—Соломона в QR-кодах и на компакт-дисках.

Слова как многочлены#

Битовая строка записывается многочленом с коэффициентами 0 и 1, старший бит — старшая степень: слово $1101$ — это $x^3+x^2+1$. Сдвиг строки влево на один разряд — умножение на $x$. Сложение многочленов — поразрядный XOR, потому что все вычисления идут в поле ${\mathbb{F}}_2$, где $1+1=0$: минус и плюс неотличимы, вычитание — то же сложение. Умножение — обычное школьное, с приведением по модулю 2.

В этом языке циклический код длины $n$ определяется одним предложением: это множество многочленов степени меньше $n$, кратных фиксированному порождающему многочлену $g(x)$ степени $r$, причём $g(x)$ обязан делить $x^n-1$. Число проверочных символов равно степени $r$, информационных — $k=n-r$; код обозначается $(n,k)$. Требование $g\mid (x^n-1)$ выглядит техническим, а отвечает за главную фишку: циклический сдвиг любого кодового слова снова кодовое слово. Доказательство в одну строку: сдвиг — это умножение на $x$ с заворотом старшего бита, то есть $xc(x)\mathrm{mod}(x^n-1)$; оба слагаемых кратны $g$ (второе — потому что $x^n\equiv 1$), значит, кратность сохраняется.

Кодирование: умножение или деление#

Два способа превратить информационный многочлен $m(x)$ степени меньше $k$ в кодовое слово. Несистематический: просто умножить, $c(x)=m(x)g(x)$ — быстро, но данные перемешиваются с проверками, прочитать исходное сообщение в кодовом слове глазами не выйдет. Систематический — рабочий: припишем $r$ нулей справа от сообщения, поделим с остатком:

Кодовое слово $c(x)$ кратно $g(x)$ по построению — именно поэтому приёмник, поделив принятое на $g(x)$, при отсутствии ошибок получит ноль в остатке. Любой сбой в канале портит кратность, и остаток «звенит». Множитель $x^r$ — это просто $r$ нулевых позиций, зарезервированных под проверки; данные стоят в слове открыто, как и в коде Хэмминга.

Полный пример: код (7,4) с порождающим $x^3 + x + 1$#

Многочлен $g(x)=x^3+x+1$ делит $x^7+1$ — проверяется делением уголком за четыре шага, — значит, из него выходит циклический код $(7,4)$ с тремя проверочными битами. Оказывается, это циклическая версия хэмминговского $(7,4)$: те же 16 кодовых слов, та же способность чинить одиночную ошибку, только устройство кодировщика несравнимо проще — один регистр сдвига с парой XOR-элементов. Закодируем сообщение $m=1101$, то есть $m(x)=x^3+x^2+1$.

Теперь пустим слово по испорченному каналу. Пусть сбой перевернул бит при $x^2$: принято $c+x^2=x^6+x^5+x^3+x^2+1$, двоично $1101101$. Приёмник делит на $g$ и получает остаток $x^2$ — не ноль, тревога. Красиво то, что остаток зависит только от разности: $(c+x^2)\mathrm{mod}g=x^2\mathrm{mod}g$, поскольку часть $c$ делится нацело. Остаток — подпись ошибки, тот же синдром, что и в коде Хэмминга, только вычисленный делением: вектор ошибки веса один даёт остаток, равный остатку от деления $x^i$ на $g$.

Синдромы одиночных ошибок для $g=x^3+x+1$ легко выписать заранее: $x^0\to 1$, $x^1\to x$, $x^2\to x^2$, $x^3\to x+1$, $x^4\to x^2+x$, $x^5\to x^2+x+1$, $x^6\to x^2+1$ — все семь различны, поэтому одиночная ошибка не просто обнаруживается, а локализуется по позиции. Это ровно условие $d_{\min }=3$: код исправляет одну ошибку и обнаруживает две, как и всякий код с минимальным расстоянием 3 из таблицы урока Хэмминга.

Почему класс такой живучий#

Аппаратная цена кодирования и проверки смехотворна: сдвиговый регистр из $r$ ячеек, между которыми вкручены XOR-сумматоры согласно коэффициентам $g(x)$, — за $n$ тактов регистр и содержит остаток. В приёмнике это считанные такты, в передатчике — тоже; программная реализация — таблица из 256 предвычисленных байтов. Ни один универсальный код не даёт проверки дешевле, чем «деление на константу».

Теория обещает больше, чем удобство. Многочлены вида $x^n-1$ раскладываются в произведение неприводимых над ${\mathbb{F}}_2$ множителей, и выбор $g$ как произведения нескольких из них — это конструктор: набрали множители с нужными корнями — получили гарантированное минимальное расстояние кода. Так рождаются коды БЧХ: при аккуратном выборе $g$ код $(15,7)$ исправляет две ошибки, $(31,16)$ — три, а расширенные семейства доходят до десятков. Коды Рида—Соломона — родственники того же класса над полем из 256 элементов: именно они позволяют царапанному диску звучать как новым и QR-коду читаться с трети площади.

CRC — усечённый родственник циклических кодов: он не исправляет, а только обнаруживает, зато находит всё подряд. Стандартный полином CRC-32 (Ethernet, ZIP) — $x^{32}+x^{26}+x^{23}+\cdots +1$. Теоретическая гарантия поражает: любая одиночная и двойная ошибка, любая ошибка нечётного веса (благодаря множителю $x+1$ в составе полинома), любой взрыв ошибок длиной до 32 подряд. Для каналов, где ошибки приходят пачками (щелчок по проводу портит соседние биты), это именно то, что нужно.

Пара деталей, на которых спотыкаются. Первая: вычитание в ${\mathbb{F}}_2$ — это сложение, знак остатка ни на что не влияет, но студенты упорно «минусуют» и получают минус перед одночленом, которого в поле не бывает. Вторая: не забыть про множитель $x^r$ — кодировать сообщение без приписанных нулей значит забыть место под проверки. Третья: проверка $\mathrm{deg}s<\mathrm{deg}g$ — если после очередного XOR старшая степень остатка не упала ниже степени делителя, деление не закончено. Арифметика многочленов — та же индуктивная техника, что в рекуррентных соотношениях: каждый шаг опирается на предыдущий, и ошибка шага съедает весь остаток.

• Слово — многочлен над ${\mathbb{F}}_2$; циклический код $(n,k)$ — кратные $g(x)$ степени $<n$, где $g\mid x^n-1$, $r=n-k$
• Систематическое кодирование: $c(x)=x^{r}m(x)+(x^{r}m(x)\mathrm{mod}g(x))$
• Проверка на приёмнике — деление на $g$; ненулевой остаток = обнаруженная ошибка, остаток — её подпись
• CRC-32 ловит одиночные, двойные, нечётные и пачечные ошибки до 32 бит; БЧХ и Рида—Соломона исправляют больше