Кольца, поля и коды

Прошлая глава закончилась вопросом: какие ещё системы «чисел», кроме остатков по простому модулю, умеют все четыре действия? Ответ пригодится в задаче, которая на первый взгляд к алгебре отношения не имеет. «Вояджер-1» улетел дальше двадцати пяти миллиардов километров. Его передатчик мощностью около двадцати ватт посылает сигнал, который идёт до Земли почти сутки и приходит таким слабым, что едва выделяется из шума. Часть битов по дороге переворачивается: отправили ноль — приняли единицу. Переспросить нельзя: ответ дойдёт через двое суток, а корабль давно передаёт следующий кадр.

С той же бедой сталкивается проигрыватель компакт-дисков, когда луч попадает на царапину, и камера телефона, которая читает QR-код, заляпанный кофе. Получатель должен сам найти ошибку и сам её исправить. Эта глава — журнал инженера: мы соберём несколько прототипов кода, от наивного до того, что работает в каждом QR-коде, и на каждом шаге будем упираться в один вопрос — в какой арифметике вести вычисления. Ответом станут кольца и поля.

Канал с шумом

Начнём с простой модели. Сообщение — последовательность битов, и канал портит каждый бит независимо от остальных с одной и той же вероятностью $p$: ноль превращается в единицу или единица в ноль. При $p = 0{,}01$ в тексте из тысячи битов испорчено в среднем десять. Мало, но если это цифры банковского перевода или координаты кадра, достаточно и одной.

Прототип первый, самый наивный: повторить каждый бит трижды. Вместо $1$ отправляем $111$, вместо $0$ — $000$. Получатель голосует большинством: $101$ он прочтёт как $1$, $001$ — как $0$. Ошибиться он может, только если перевернутся хотя бы два бита из трёх.

Перевернулись ровно два бита из трёх. Какой из трёх уцелел, можно выбрать тремя способами, и у каждого варианта вероятность $p \cdot p \cdot (1 - p)$: биты портятся независимо. Перевернулись все три. Пример: при $p = 0{,}01$ получаем $P = 3 \cdot 0{,}0001 - 2 \cdot 0{,}000001 = 0{,}000298$ — ошибок стало в $33$ раза меньше. При $p = 0{,}1$ выходит $0{,}028$. А при $p$ больше половины голосование только вредит: канал чаще ошибается, чем нет.

Цена за это — втрое больше передачи. Инженеры меряют её так.

Прототип второй — противоположная крайность. К каждым восьми битам добавим один, чтобы число единиц стало чётным: к $1011\,0010$ добавляем $0$, к $1011\,0011$ — $1$. Скорость $\frac89$, почти без потерь. Если по дороге перевернётся один бит, чётность нарушится, и получатель увидит, что байт испорчен. Но какой именно из девяти битов виноват, он не знает, а две ошибки в одном байте вовсе не заметит: чётность вернётся на место.

Для модема, который может переспросить, этого хватает, для «Вояджера» — нет. Сравните прототипы на картинке, которую нужно передать.

Тройной повтор надёжен, но расточителен. Можно ли исправлять ошибки дешевле?

Три круга Хэмминга

В конце 1940-х годов Ричард Хэмминг работал в Bell Labs и по выходным ставил задачи на релейную вычислительную машину. Машина проверяла себя кодами вроде чётности и, заметив ошибку, бросала задачу и переходила к следующей. В понедельник Хэмминг находил вместо ответа пустоту. По его собственному рассказу, в какой-то момент он разозлился: если машина умеет обнаружить ошибку, почему она не может найти, где она, и исправить? В 1950 году он опубликовал коды, которые умеют именно это.

Самый известный из них удобно рисовать тремя пересекающимися кругами. Круги делят плоскость на семь областей, и в каждую кладём по биту. Четыре бита сообщения занимают области, где круги пересекаются. Три проверочных бита занимают области, принадлежащие только одному кругу, и подбираются так, чтобы в каждом круге оказалось чётное число единиц.

Пронумеруем области числами от $1$ до $7$ так, чтобы двоичная запись номера говорила, в каких кругах лежит область: младший разряд — круг $A$, средний — круг $B$, старший — круг $C$. Область $5 = 101_2$ лежит в кругах $A$ и $C$, но не в $B$; область $7 = 111_2$ — в центре, во всех трёх. Проверочные биты стоят на местах $1$, $2$ и $4$, биты сообщения — на местах $3$, $5$, $6$ и $7$.

Идея: каждый бит лежит в своём, неповторимом наборе кругов, и ошибка в нём ломает чётность ровно в этом наборе.

Три круга делят плоскость на семь областей внутри кругов, по одной на каждый непустой набор кругов: $A$, $B$, $C$, $AB$, $AC$, $BC$, $ABC$. Разных наборов ровно семь, и каждой области достался свой. Отправитель подбирает проверочные биты $1$, $2$, $4$. Это всегда можно сделать, причём единственным образом: каждый из них лежит только в одном круге и выравнивает чётность своего круга, не трогая остальные. Пусть по дороге перевернулся один бит. В каждом круге, который содержит его область, число единиц изменилось на один и стало нечётным. В остальных кругах ничего не изменилось. Значит, «сломаны» ровно те круги, в которых лежит испорченный бит. Разные области лежат в разных наборах кругов, поэтому по набору сломанных кругов область восстанавливается однозначно. Если ошибки не было, сломанных кругов нет, а пустой набор не отвечает ни одной области, так что и этот случай не спутать ни с каким другим. Получатель проверяет три круга, находит область и переворачивает её бит обратно. Номер испорченного бита — просто двоичное число из сломанных кругов: $C$ даёт $4$, $B$ — $2$, $A$ — $1$. Передвиньте ошибку в другую область: загораются другие круги.

Круги удобны для глаз, а для компьютера то же самое записывают матрицей. Биты складываются как остатки по модулю $2$: $1 + 1 = 0$, это операция «исключающее или» (XOR). Проверка чётности круга — сумма его битов по модулю $2$. Три проверки — три строки матрицы, столбцы которой — номера позиций в двоичной записи.

Синдром — три числа, $0$ или $1$: сломан ли круг $C$, $B$, $A$. Прочитанный как двоичное число, он равен номеру испорченного бита, а $000$ означает, что ошибок нет. Проверочная матрица $H$. Её $j$-й столбец — двоичная запись числа $j$: строка $C$ отмечает позиции $4$–$7$, строка $B$ — позиции $2, 3, 6, 7$, строка $A$ — нечётные позиции. Принятое слово — столбец из семи битов. Пример: сообщение $1011$ кодируется словом $0110011$ (проверьте: в каждом круге чётное число единиц). Пусть испортился шестой бит, и пришло $\mathbf r = 0110001$. Строка $C$: биты $4$–$7$, то есть $0 + 0 + 0 + 1 = 1$. Строка $B$: биты $2, 3, 6, 7$: $1 + 1 + 0 + 1 = 1$. Строка $A$: биты $1, 3, 5, 7$: $0 + 1 + 0 + 1 = 0$. Синдром $110_2 = 6$.

Почему столбец выдаёт номер? У кодового слова $\mathbf c$ все проверки чётны, $H\mathbf c = \mathbf 0$. Если испорчен бит $j$, то $\mathbf r = \mathbf c + \mathbf e_j$, где у $\mathbf e_j$ единица только на месте $j$, и $H\mathbf r = H\mathbf c + H\mathbf e_j = H\mathbf e_j$ — это $j$-й столбец. Синдром не зависит от сообщения, только от ошибки.

Пришло слово $1110101$ (биты с первого по седьмой). Известно, что ошибок не больше одной. В какой позиции ошибка? Если её нет, ответьте $0$.

Строка $C$ (биты $4$–$7$): $0 + 1 + 0 + 1 = 0$. Строка $B$ (биты $2, 3, 6, 7$): $1 + 1 + 0 + 1 = 1$. Строка $A$ (биты $1, 3, 5, 7$): $1 + 1 + 1 + 1 = 0$. Синдром $010_2 = 2$: испорчен второй бит, проверочный. Исправленное слово $1010101$, и сообщение (биты $3, 5, 6, 7$) — $1101$.

Сколько ошибок выдержит код

Почему код Хэмминга исправляет одну ошибку, а тройной повтор — одну из трёх? И как построить код, который исправляет больше? Ответ даёт геометрия, в которой расстояние между словами считают по числу несовпадений.

Идея: вокруг каждого кодового слова нарисовать «шар» — все слова, до которых можно дойти за $t$ ошибок, — и увидеть, что шары не пересекаются. Покажем на тройном повторе; в общем случае рассуждение то же.

Слова длины $3$ — вершины куба, ребро соединяет слова, отличающиеся одним битом. Расстояние Хэмминга — наименьшее число рёбер между вершинами: каждый шаг по ребру исправляет одно несовпадение. Для любых слов $u$, $v$, $w$ выполнено неравенство треугольника $d(u, w) \le d(u, v) + d(v, w)$: в каждой позиции, где различаются $u$ и $w$, слово $v$ отличается хотя бы от одного из них. Кодовые слова тройного повтора $000$ и $111$ стоят в противоположных углах куба, $d = 3$. Вокруг каждого нарисуем шар радиуса $t = 1$: само слово и три соседа. Шары не пересекаются: если бы слово $w$ было не дальше $t$ от обоих кодовых слов, то по неравенству треугольника между ними было бы не больше $2t < d$. Здесь $1 + 1 = 2 < 3$. Шары вокруг $000$ и $111$ делят куб пополам. Если ошибок не больше $t$, принятое слово лежит в шаре отправленного и ни в каком другом, так что ближайшее кодовое слово — отправленное. А меньше чем $d$ ошибок не превратят одно кодовое слово в другое, поэтому их всегда видно: принятое слово не кодовое.

Минимальное расстояние кода Хэмминга равно $3$. Сумма двух кодовых слов по модулю $2$ — снова кодовое слово (чётности складываются), а число единиц в ней — расстояние между исходными. Слово с одной единицей не кодовое: любая область лежит хотя бы в одном круге и ломает его чётность. Слово с двумя единицами в разных областях тоже не кодовое: у областей разные наборы кругов, и найдётся круг, в котором лежит ровно одна из них. А $1110000$ — кодовое: в кругах $A$ и $B$ по две единицы, в $C$ ни одной. По теореме код Хэмминга исправляет одну ошибку и замечает две.

Код Хэмминга не тратит впустую ни одного синдрома: каждое из $128$ возможных слов декодер понимает однозначно. Такие коды называют совершенными.

Прототип Хэмминга хорош против одиночных ошибок. Но царапина на диске уничтожает сотни битов подряд, и в одном блоке из семи окажется много ошибок сразу. Выход — считать не битами, а байтами: если испорчены все восемь битов байта, это одна ошибка в «букве» из $256$ возможных. Для этого нужна арифметика над алфавитом из $256$ символов, в которой, как в $\mathbb Z_2$, можно складывать, вычитать, умножать и делить: на делении стоит вся линейная алгебра кодов. Остатки по модулю $256$ не годятся: $2 \cdot 128 = 256 \equiv 0$, и на $2$ делить нельзя. Какие вообще бывают такие арифметики?

Где можно считать

Целые числа, остатки по модулю $n$, многочлены, квадратные матрицы — везде есть сложение и умножение, и почти все привычные правила выполняются. Общее у них описывает одно определение.

Кольца — это $\mathbb Z$, $\mathbb Z_n$, многочлены с действительными коэффициентами. Матрицы $2 \times 2$ тоже образуют кольцо, но некоммутативное: как мы видели в главе о матрицах, $AB$ и $BA$ обычно различаются. Деление в определение не входит. В $\mathbb Z$ нельзя разделить $1$ на $2$, а в $\mathbb Z_6$ случается то, чего не бывает с числами: $2 \cdot 3 = 0$, хотя ни $2$, ни $3$ не нули.

Там, где есть делители нуля, привычные рассуждения ломаются. Из $ab = 0$ уже не следует, что один из множителей нуль, а значит, нельзя решать уравнения разложением на множители.

Сколько решений у уравнения $x^2 = 1$ в $\mathbb Z_8$?

Два: $x = 1$ и $x = 7$ Четыре Одно Восемь

$1^2 = 1$, $3^2 = 9 \equiv 1$, $5^2 = 25 \equiv 1$, $7^2 = 49 \equiv 1$. Уравнение второй степени с четырьмя корнями! Разложение $(x - 1)(x + 1) = 0$ не помогает: при $x = 3$ множители равны $2$ и $4$, оба ненулевые, а их произведение $8 \equiv 0$. В $\mathbb Z_8$ есть делители нуля, и правило «произведение равно нулю, только если нулю равен множитель» не работает.

Системы, где делить можно на всё, кроме нуля, получили своё имя.

Поля — это $\mathbb Q$, $\mathbb R$, $\mathbb C$ и, как мы выяснили в прошлой главе, $\mathbb Z_p$ при простом $p$. Кольцо $\mathbb Z$ не поле: у $2$ нет целого обратного. В поле работает вся школьная алгебра: пропорции, формула корней квадратного уравнения (если есть квадратные корни и $2 \ne 0$), метод Гаусса для систем, интерполяция. Всё это держится на делении и на следующем свойстве.

Вычислите $\frac35$ в поле $\mathbb Z_7$ — число от $0$ до $6$.

Разделить на $5$ — умножить на $5^{-1}$. Так как $5 \cdot 3 = 15 \equiv 1 \pmod 7$, то $5^{-1} = 3$, и $\frac35 = 3 \cdot 3 = 9 \equiv 2$. Проверка: $5 \cdot 2 = 10 \equiv 3$.

Поле из четырёх элементов

Для байтов нужно поле из $256$ элементов, а $\mathbb Z_{256}$ — не поле. Попробуем для начала построить поле из четырёх элементов, где $\mathbb Z_4$ тоже не годится: $2 \cdot 2 = 0$. Подсказку дают числа, которые мы уже умеем строить: $\mathbb C$ получилось из $\mathbb R$ добавлением корня уравнения $x^2 + 1 = 0$, у которого действительных корней нет (глава 15). Так же можно добавить к $\mathbb Q$ корень из двух.

Теперь то же самое в $\mathbb Z_2$. У многочлена $x^2 + x + 1$ там нет корней: при $x = 0$ он равен $1$, при $x = 1$ тоже $1 + 1 + 1 = 3 \equiv 1$. Добавим воображаемый корень $\alpha$, для которого $\alpha^2 + \alpha + 1 = 0$, то есть $\alpha^2 = \alpha + 1$: в $\mathbb Z_2$ минус и плюс совпадают. Элементы нового поля имеют вид $a + b\alpha$ с $a, b \in \{0, 1\}$ — их четыре: $0$, $1$, $\alpha$, $\alpha + 1$. Складываются они покоординатно, а умножаются как многочлены, после чего $\alpha^2$ заменяется на $\alpha + 1$.

Например, $\alpha(\alpha + 1) = \alpha^2 + \alpha = (\alpha + 1) + \alpha = 1$, потому что $\alpha + \alpha = 2\alpha = 0$. Значит, $\alpha$ и $\alpha + 1$ обратны друг другу, а $1$ обратна сама себе: каждый ненулевой элемент обратим. Нулей вне нулевой строки и столбца нет. Это поле из четырёх элементов, и устроено оно совсем не так, как $\mathbb Z_4$: в нём $1 + 1 = 0$.

Годится ли для этого трюка любой многочлен? Нет: если многочлен раскладывается на множители, воображаемый корень одного из них даст делители нуля. Нужны многочлены, которые не раскладываются.

Из многочлена $x^3 + x + 1$, неприводимого над $\mathbb Z_2$ (у него нет корней, а многочлен третьей степени, который раскладывается, имеет множитель первой степени), получается $GF(8)$. Из $x^4 + x + 1$ — $GF(16)$. Переключите на них таблицу выше: при любом выборе каждая ненулевая строка — перестановка ненулевых элементов.

Существует ли поле из $6$ элементов?

Да, это $\mathbb Z_6$ Нет Да, но устроено оно не так, как $\mathbb Z_6$

Число элементов конечного поля — степень простого, а $6 = 2 \cdot 3$ не степень простого. Поля из $2, 3, 4, 5, 7, 8, 9$ элементов есть, из $6$ и $10$ — нет.

Обратное тоже верно: для каждого простого $p$ и натурального $n$ поле из $p^n$ элементов существует. Для небольших $n$ неприводимый многочлен легко найти перебором, как мы нашли $x^2 + x + 1$, а в общем случае помогает другой путь.

Доказательство: корни многочлена $x^{p^n} - x$

Идея: построить поле, в котором многочлен $x^q - x$, где $q = p^n$, раскладывается на множители первой степени, и увидеть, что его корни сами образуют поле, причём их ровно $q$.

Корень всегда можно добавить. Пусть $F$ — поле и $g$ — многочлен над ним степени не меньше $1$. Возьмём неприводимый множитель $h$ многочлена $g$. Как в теореме о поле из многочленов по модулю неприводимого (её доказательство годится над любым полем $F$), остатки от деления на $h$ образуют поле, содержащее $F$. В нём остаток многочлена $x$ — корень $h$, а значит, и корень $g$. Отщепим от $g$ множитель первой степени и повторим то же с частным. Через конечное число шагов получим поле $L \supset \mathbb Z_p$, в котором $x^q - x$ раскладывается на $q$ множителей первой степени.

Корни образуют поле. В поле характеристики $p$ верно $(a + b)^p = a^p + b^p$: по биному Ньютона остальные слагаемые содержат коэффициенты $\binom pk$ при $0 < k < p$, а они делятся на $p$ — в числителе $p!$ множитель $p$ есть, а в знаменателе $k!(p - k)!$ его нет. Повторяя $n$ раз, получаем $(a + b)^q = a^q + b^q$. Поэтому если $a^q = a$ и $b^q = b$, то и $(a + b)^q = a + b$, и $(ab)^q = ab$, и $(-a)^q = -a$ (при $p = 2$ это то же, что $a$, ведь $-1 = 1$), и $(a^{-1})^q = a^{-1}$. Корни $x^q - x$ замкнуты относительно всех четырёх действий — это поле.

Их ровно $q$. Пусть $r$ — корень. Тогда $x^q - x = (x - r)^q + r^q - x = (x - r)^q - (x - r) = (x - r)\bigl((x - r)^{q-1} - 1\bigr)$. Второй множитель при $x = r$ равен $-1 \ne 0$, так что $r$ — простой корень, а не кратный. Многочлен степени $q$ разложился на $q$ множителей первой степени, и все корни различны — их $q$. Это и есть поле из $p^n$ элементов.

Ненулевые элементы конечного поля образуют группу по умножению, и она всегда циклическая: найдётся элемент $g$, степени которого пробегают все ненулевые элементы. Доказательство слово в слово повторяет доказательство существования первообразного корня из прошлой главы. Там использовались только три вещи: что порядок элемента делит число ненулевых элементов, что у многочлена степени $d$ над полем не больше $d$ корней (это мы докажем в следующем разделе для любого поля) и подсчёт с функцией Эйлера. В $GF(4)$ образующая — $\alpha$: $\alpha^1 = \alpha$, $\alpha^2 = \alpha + 1$, $\alpha^3 = 1$. Поэтому в микросхемах умножение в конечном поле часто делают сложением показателей по таблице логарифмов — так же, как умножали по таблицам Непера.

Код из многочленов

Теперь у нас есть поле, в котором «буква» — байт. Как построить из него код? В 1960 году Ирвинг Рид и Густав Соломон из Линкольновской лаборатории Массачусетского технологического института опубликовали пятистраничную статью «Многочленные коды над некоторыми конечными полями» с идеей, которую мы уже видели в главе о многочленах: многочлен степени меньше $k$ однозначно восстанавливается по своим значениям в любых $k$ точках.

Сообщение из $k$ символов поля объявим коэффициентами многочлена $f$ степени меньше $k$. Отправим не коэффициенты, а значения $f$ в $n > k$ различных точках поля. Лишние $n - k$ значений — запас: даже если часть их испортилась, многочлен, проходящий через большинство принятых точек, можно найти.

Многочлен над конечным полем, в который упаковано сообщение. Сообщение — $k$ элементов поля, коэффициенты многочлена. Различные точки поля, в которых вычисляют $f$. Их $n$, поэтому $n$ не больше числа элементов поля; в поле $GF(256)$ обычно $n = 255$. Пример в поле $\mathbb Z_{11}$: сообщение $(3, 1, 4)$ — многочлен $f(x) = 3 + x + 4x^2$. Его значения в точках $0, 1, \dots, 6$: $3, 8, 10, 9, 5, 9, 10$ (например, $f(2) = 3 + 2 + 16 = 21 \equiv 10$). Это кодовое слово длины $n = 7$ для сообщения длины $k = 3$; оно выдерживает две ошибки.

Почему две? Всё держится на теореме, которую мы доказали для действительных многочленов в главе 14. Над полем она верна так же, а без поля ломается: в $\mathbb Z_8$, как мы видели, у $x^2 - 1$ четыре корня.

В нашем примере $n = 7$, $k = 3$, и $2t \le 4$: две ошибки. Больше выжать нельзя: у любого кода, который превращает $k$ символов в $n$, расстояние не больше $n - k + 1$ (оно называется границей Синглтона), так что коды Рида — Соломона тратят проверочные символы оптимально.

Декодер в этой картинке действует в лоб: перебирает тройки точек, проводит через каждую многочлен по формуле Лагранжа и ищет тот, что проходит не меньше чем через пять точек. Для $n = 7$ троек всего $35$, но для $n = 255$ перебор безнадёжен. Быстрый алгоритм декодирования нашёл Элвин Берлекэмп в 1968 году, и именно он сделал коды Рида — Соломона практичными. Заметьте, что формула Лагранжа делит на разности точек $x_i - x_j$: без поля не обойтись и здесь.

Где работает этот код, перечислить трудно. На компакт-дисках (1982) два кода Рида — Соломона над $GF(256)$ переплетены так, что царапина, уничтожившая несколько тысяч битов подряд, превращается в разрозненные ошибки в разных кодовых словах, и все они исправляются. В QR-коде можно выбрать уровень коррекции: $L$, $M$, $Q$ или $H$ восстанавливают примерно $7$, $15$, $25$ или $30$ процентов кодовых слов, поэтому заляпанный или надорванный код всё равно читается. Код Рида — Соломона в паре со свёрточным кодом защищает передачи «Вояджеров», запущенных в 1977 году. Он же работает в DVD, Blu-ray, цифровом телевидении и в массивах жёстких дисков RAID 6.

Стандарт космической связи CCSDS использует код Рида — Соломона над $GF(256)$, который превращает $223$ байта сообщения в $255$ байт. Сколько испорченных байт в каждом блоке он гарантированно исправляет?

$n = 255$, $k = 223$, проверочных байт $n - k = 32$. Условие $2t \le 32$ даёт $t = 16$. Если в каждом из шестнадцати испорченных байт перевернулись все восемь битов, это $128$ битовых ошибок в одном блоке — и все они исправляются.

Потренируйтесь кодировать и декодировать код Хэмминга: вычислять проверочные биты, находить синдром и исправлять ошибку.

Куда дальше

Мы строили поля, добавляя корни: к $\mathbb Q$ — корень из двух, к $\mathbb R$ — мнимую единицу, к $\mathbb Z_2$ — корень многочлена $x^2 + x + 1$. Формула корней квадратного уравнения — тоже добавление корня, квадратного. Формула Кардано для кубического уравнения добавляет квадратные и кубические корни, формула Феррари для уравнения четвёртой степени — ещё несколько. А для уравнения пятой степени формулы в радикалах нет. Почему у уравнения пятой степени нет формулы? Ответ нашёл тот же Галуа, чьё имя носят конечные поля: он изучал симметрии корней и расширения полей, которые эти корни порождают. Об этом — следующая глава.