Часть VI · Структуры Глава 42 из 60
Кольца, поля и коды
Как исправить ошибку в сообщении, если переспросить нельзя? Журнал инженера: от тройного повтора и трёх кругов Хэмминга до полей Галуа и кодов Рида — Соломона, которые спрятаны в каждом QR-коде.
Опирается на: 41 · Арифметика остатков и шифры
Вы научитесь
- кодировать и декодировать код Хэмминга (7, 4) и понимать, почему он исправляет любую одиночную ошибку
- отличать кольцо от поля и строить конечные поля вроде GF(4) из неприводимых многочленов
- объяснить, как коды Рида — Соломона восстанавливают сообщение по многочлену и почему для них нужно поле
Прошлая глава закончилась вопросом: какие ещё системы «чисел», кроме остатков по простому модулю, умеют все четыре действия? Ответ пригодится в задаче, которая на первый взгляд к алгебре отношения не имеет. «Вояджер-1» улетел дальше двадцати пяти миллиардов километров. Его передатчик мощностью около двадцати ватт посылает сигнал, который идёт до Земли почти сутки и приходит таким слабым, что едва выделяется из шума. Часть битов по дороге переворачивается: отправили ноль — приняли единицу. Переспросить нельзя: ответ дойдёт через двое суток, а корабль давно передаёт следующий кадр.
С той же бедой сталкивается проигрыватель компакт-дисков, когда луч попадает на царапину, и камера телефона, которая читает QR-код, заляпанный кофе. Получатель должен сам найти ошибку и сам её исправить. Эта глава — журнал инженера: мы соберём несколько прототипов кода, от наивного до того, что работает в каждом QR-коде, и на каждом шаге будем упираться в один вопрос — в какой арифметике вести вычисления. Ответом станут кольца и поля.
Канал с шумом
Начнём с простой модели. Сообщение — последовательность битов, и канал портит каждый бит независимо от остальных с одной и той же вероятностью $p$: ноль превращается в единицу или единица в ноль. При $p = 0{,}01$ в тексте из тысячи битов испорчено в среднем десять. Мало, но если это цифры банковского перевода или координаты кадра, достаточно и одной.
Код, исправляющий ошибки, — правило, по которому к сообщению добавляют проверочные символы так, чтобы получатель мог восстановить исходное сообщение, даже если часть символов испортилась в пути. Сообщение вместе с проверочными символами называют кодовым словом.
Прототип первый, самый наивный: повторить каждый бит трижды. Вместо $1$ отправляем $111$, вместо $0$ — $000$. Получатель голосует большинством: $101$ он прочтёт как $1$, $001$ — как $0$. Ошибиться он может, только если перевернутся хотя бы два бита из трёх.
Цена за это — втрое больше передачи. Инженеры меряют её так.
Скорость кода — отношение числа битов сообщения к числу переданных битов. У тройного повтора она равна $\frac13$: две трети канала заняты повторами.
Прототип второй — противоположная крайность. К каждым восьми битам добавим один, чтобы число единиц стало чётным: к $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$.
Код Хэмминга $(7, 4)$ превращает $4$ бита сообщения в кодовое слово из $7$ битов: проверочные биты на местах $1$, $2$, $4$ подбираются так, чтобы в каждом из трёх кругов было чётное число единиц. Его скорость $\frac47$.
Если в кодовом слове кода Хэмминга $(7, 4)$ перевернулся не больше чем один бит, получатель по принятому слову однозначно находит испорченный бит, а значит, восстанавливает сообщение.
Идея: каждый бит лежит в своём, неповторимом наборе кругов, и ошибка в нём ломает чётность ровно в этом наборе.
Круги удобны для глаз, а для компьютера то же самое записывают матрицей. Биты складываются как остатки по модулю $2$: $1 + 1 = 0$, это операция «исключающее или» (XOR). Проверка чётности круга — сумма его битов по модулю $2$. Три проверки — три строки матрицы, столбцы которой — номера позиций в двоичной записи.
Почему столбец выдаёт номер? У кодового слова $\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$-й столбец. Синдром не зависит от сообщения, только от ошибки.
Синдром принятого слова $\mathbf r$ — результат всех проверок, $\mathbf s = H\mathbf r$. Он равен нулю на кодовых словах и зависит только от ошибки, поэтому декодеру достаточно таблицы «синдром → ошибка».
Пришло слово $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$.
Сколько ошибок выдержит код
Почему код Хэмминга исправляет одну ошибку, а тройной повтор — одну из трёх? И как построить код, который исправляет больше? Ответ даёт геометрия, в которой расстояние между словами считают по числу несовпадений.
Расстояние Хэмминга между словами одной длины — число позиций, в которых они различаются. Между $10110$ и $11100$ оно равно $2$. Минимальное расстояние кода — наименьшее расстояние между его разными кодовыми словами.
Пусть любые два разных кодовых слова различаются не меньше чем в $d$ позициях. Тогда код замечает любые $d - 1$ ошибок в слове, а если заменять принятое слово ближайшим кодовым, он исправляет любые $t$ ошибок при $2t + 1 \le d$.
Идея: вокруг каждого кодового слова нарисовать «шар» — все слова, до которых можно дойти за $t$ ошибок, — и увидеть, что шары не пересекаются. Покажем на тройном повторе; в общем случае рассуждение то же.
Минимальное расстояние кода Хэмминга равно $3$. Сумма двух кодовых слов по модулю $2$ — снова кодовое слово (чётности складываются), а число единиц в ней — расстояние между исходными. Слово с одной единицей не кодовое: любая область лежит хотя бы в одном круге и ломает его чётность. Слово с двумя единицами в разных областях тоже не кодовое: у областей разные наборы кругов, и найдётся круг, в котором лежит ровно одна из них. А $1110000$ — кодовое: в кругах $A$ и $B$ по две единицы, в $C$ ни одной. По теореме код Хэмминга исправляет одну ошибку и замечает две.
Шары радиуса $1$ вокруг $16$ кодовых слов кода Хэмминга $(7, 4)$ покрывают все $2^7 = 128$ слов длины $7$, и каждое слово лежит ровно в одном шаре.
В шаре радиуса $1$ вокруг слова восемь слов: оно само и семь слов, отличающихся от него в одной позиции. Кодовых слов $2^4 = 16$, по одному на каждое сообщение, и по доказанной теореме их шары не пересекаются, так как $2 \cdot 1 + 1 \le 3$. Вместе в них $16 \cdot 8 = 128$ разных слов — ровно столько, сколько всего слов длины $7$. Значит, других слов не осталось.
Код Хэмминга не тратит впустую ни одного синдрома: каждое из $128$ возможных слов декодер понимает однозначно. Такие коды называют совершенными.
Прототип Хэмминга хорош против одиночных ошибок. Но царапина на диске уничтожает сотни битов подряд, и в одном блоке из семи окажется много ошибок сразу. Выход — считать не битами, а байтами: если испорчены все восемь битов байта, это одна ошибка в «букве» из $256$ возможных. Для этого нужна арифметика над алфавитом из $256$ символов, в которой, как в $\mathbb Z_2$, можно складывать, вычитать, умножать и делить: на делении стоит вся линейная алгебра кодов. Остатки по модулю $256$ не годятся: $2 \cdot 128 = 256 \equiv 0$, и на $2$ делить нельзя. Какие вообще бывают такие арифметики?
Где можно считать
Целые числа, остатки по модулю $n$, многочлены, квадратные матрицы — везде есть сложение и умножение, и почти все привычные правила выполняются. Общее у них описывает одно определение.
Кольцо — множество с двумя операциями, сложением и умножением, для которых выполнены аксиомы кольца. Кольцо коммутативно, если $ab = ba$ для всех $a$ и $b$.
Для любых элементов $a$, $b$, $c$:
- по сложению элементы образуют коммутативную группу (глава 40): $a + b = b + a$, $(a + b) + c = a + (b + c)$, есть нуль с $a + 0 = a$, и у каждого $a$ есть противоположный $-a$ с $a + (-a) = 0$;
- умножение ассоциативно: $(ab)c = a(bc)$;
- выполнены распределительные законы: $a(b + c) = ab + ac$ и $(a + b)c = ac + bc$;
- есть единица: $1 \cdot a = a \cdot 1 = a$.
Последнюю аксиому некоторые книги не требуют; у нас все кольца с единицей.
Кольца — это $\mathbb Z$, $\mathbb Z_n$, многочлены с действительными коэффициентами. Матрицы $2 \times 2$ тоже образуют кольцо, но некоммутативное: как мы видели в главе о матрицах, $AB$ и $BA$ обычно различаются. Деление в определение не входит. В $\mathbb Z$ нельзя разделить $1$ на $2$, а в $\mathbb Z_6$ случается то, чего не бывает с числами: $2 \cdot 3 = 0$, хотя ни $2$, ни $3$ не нули.
Делитель нуля — ненулевой элемент $a$ кольца, для которого найдётся ненулевой $b$ с $ab = 0$. В $\mathbb Z_6$ делители нуля — это $2$, $3$ и $4$ (так как $4 \cdot 3 = 12 \equiv 0$).
Там, где есть делители нуля, привычные рассуждения ломаются. Из $ab = 0$ уже не следует, что один из множителей нуль, а значит, нельзя решать уравнения разложением на множители.
Сколько решений у уравнения $x^2 = 1$ в $\mathbb Z_8$?
$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$ есть делители нуля, и правило «произведение равно нулю, только если нулю равен множитель» не работает.
Системы, где делить можно на всё, кроме нуля, получили своё имя.
Поле — коммутативное кольцо, в котором $1 \ne 0$ и у каждого ненулевого элемента $a$ есть обратный $a^{-1}$ с $aa^{-1} = 1$. В поле можно делить: $\frac ba = ba^{-1}$.
Поля — это $\mathbb Q$, $\mathbb R$, $\mathbb C$ и, как мы выяснили в прошлой главе, $\mathbb Z_p$ при простом $p$. Кольцо $\mathbb Z$ не поле: у $2$ нет целого обратного. В поле работает вся школьная алгебра: пропорции, формула корней квадратного уравнения (если есть квадратные корни и $2 \ne 0$), метод Гаусса для систем, интерполяция. Всё это держится на делении и на следующем свойстве.
Если $ab = 0$ в поле, то $a = 0$ или $b = 0$.
Пусть $a \ne 0$. Тогда у $a$ есть обратный, и умножим равенство $ab = 0$ на $a^{-1}$: $b = 1 \cdot b = (a^{-1}a)b = a^{-1}(ab) = a^{-1} \cdot 0 = 0$. Последнее равенство — общее правило колец: $x \cdot 0 = x(0 + 0) = x \cdot 0 + x \cdot 0$, и, вычитая $x \cdot 0$ из обеих частей, получаем $x \cdot 0 = 0$.
Кольцо $\mathbb Z_n$ при $n \ge 2$ — поле тогда и только тогда, когда $n$ простое.
Если $n = p$ простое, каждое ненулевое $a$ от $1$ до $p - 1$ взаимно просто с $p$ и потому обратимо по критерию из прошлой главы. Остальные аксиомы поля наследуются от целых чисел: сравнения можно складывать и перемножать, поэтому законы сложения и умножения целых чисел переносятся на остатки.
Если $n$ составное, $n = ab$ с $1 < a, b < n$, то $a$ и $b$ — ненулевые остатки, а $ab = n \equiv 0$. Это делители нуля, а в поле их не бывает, так что $\mathbb Z_n$ не поле.
Вычислите $\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 Q(\sqrt2) = \{a + b\sqrt2 : a, b \in \mathbb Q\}$ с обычными сложением и умножением — поле.
Идея: проверить, что четыре действия не выводят из множества; остальные аксиомы выполнены, потому что это действительные числа.
Сумма и разность: $(a + b\sqrt2) \pm (c + d\sqrt2) = (a \pm c) + (b \pm d)\sqrt2$. Произведение: $(a + b\sqrt2)(c + d\sqrt2) = (ac + 2bd) + (ad + bc)\sqrt2$, потому что $\sqrt2 \cdot \sqrt2 = 2$. Коэффициенты снова рациональны.
Обратный элемент. Пусть $a + b\sqrt2 \ne 0$. Умножим на «сопряжённое» $a - b\sqrt2$: $(a + b\sqrt2)(a - b\sqrt2) = a^2 - 2b^2$. Это рациональное число, и оно не нуль: если $a^2 = 2b^2$ при $b \ne 0$, то $\left(\frac ab\right)^2 = 2$, а $\sqrt2$ иррационален; если же $b = 0$, то $a^2 - 2b^2 = a^2 \ne 0$. Значит, $\frac{1}{a + b\sqrt2} = \frac{a}{a^2 - 2b^2} - \frac{b}{a^2 - 2b^2}\sqrt2$ — снова число нужного вида.
Если поле $F$ содержится в поле $K$ и операции в них одни и те же, говорят, что $K$ — расширение поля $F$. $\mathbb C$ — расширение $\mathbb R$, $\mathbb Q(\sqrt2)$ — расширение $\mathbb Q$, полученное добавлением корня многочлена $x^2 - 2$.
Теперь то же самое в $\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$.
| $\times$ | $0$ | $1$ | $\alpha$ | $\alpha + 1$ |
|---|---|---|---|---|
| $0$ | $0$ | $0$ | $0$ | $0$ |
| $1$ | $0$ | $1$ | $\alpha$ | $\alpha + 1$ |
| $\alpha$ | $0$ | $\alpha$ | $\alpha + 1$ | $1$ |
| $\alpha + 1$ | $0$ | $\alpha + 1$ | $1$ | $\alpha$ |
Например, $\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$.
Годится ли для этого трюка любой многочлен? Нет: если многочлен раскладывается на множители, воображаемый корень одного из них даст делители нуля. Нужны многочлены, которые не раскладываются.
Многочлен степени не меньше $1$ с коэффициентами из поля $F$ неприводим над $F$, если его нельзя записать произведением двух многочленов меньшей степени с коэффициентами из $F$. Так, $x^2 + x + 1$ неприводим над $\mathbb Z_2$: у многочлена второй степени, который раскладывается, был бы корень, а корней нет. А $x^2 + 1 = (x + 1)^2$ над $\mathbb Z_2$ приводим.
Пусть $p$ простое и $f$ — неприводимый над $\mathbb Z_p$ многочлен степени $n$. Тогда многочлены степени меньше $n$ с коэффициентами из $\mathbb Z_p$, если складывать их обычным образом, а умножать с последующим взятием остатка от деления на $f$, образуют поле из $p^n$ элементов.
Идея: повторить для многочленов то, что мы делали для чисел в прошлой главе. Остатки от деления на $f$ ведут себя как остатки по модулю $n$, а неприводимый многочлен играет роль простого числа.
Сколько элементов. Многочлен степени меньше $n$ задаётся $n$ коэффициентами, каждый из $p$ вариантов: всего $p^n$.
Аксиомы кольца. Деление с остатком на $f$ работает над $\mathbb Z_p$ так же, как над $\mathbb R$: на каждом шаге делим на старший коэффициент $f$, а в $\mathbb Z_p$ на ненулевой элемент делить можно. Остаток единствен. Лемма об остатках из прошлой главы переносится дословно: если $g - g'$ и $h - h'$ делятся на $f$, то делятся и $(g + h) - (g' + h')$, и $gh - g'h' = g(h - h') + (g - g')h'$. Поэтому остаток суммы и произведения зависит только от остатков, и все законы действий над многочленами переходят на остатки.
Обратный элемент. Пусть $g$ — ненулевой многочлен степени меньше $n$. Общий делитель $g$ и $f$ — делитель неприводимого $f$, то есть либо ненулевая константа, либо $f$, умноженный на константу; но $f$ не может делить ненулевой $g$ меньшей степени. Значит, наибольший общий делитель — константа, и её можно считать единицей. Алгоритм Евклида для многочленов (делим с остатком, пока остаток не станет нулём) и обратный ход дают, как в соотношении Безу, многочлены $u$ и $v$ с $ug + vf = 1$. Слагаемое $vf$ делится на $f$, поэтому остаток от деления $u$ на $f$ и есть обратный к $g$.
Конечное поле — поле из конечного числа элементов. Поле из $q$ элементов обозначают $GF(q)$ (от английского Galois field, поле Галуа) или $\mathbb F_q$. Так, $GF(p) = \mathbb Z_p$, а наше поле из четырёх элементов — $GF(4)$.
Из многочлена $x^3 + x + 1$, неприводимого над $\mathbb Z_2$ (у него нет корней, а многочлен третьей степени, который раскладывается, имеет множитель первой степени), получается $GF(8)$. Из $x^4 + x + 1$ — $GF(16)$. Переключите на них таблицу выше: при любом выборе каждая ненулевая строка — перестановка ненулевых элементов.
Характеристика поля — наименьшее натуральное $p$, для которого сумма $p$ единиц $1 + 1 + \dots + 1$ равна нулю. Если такого $p$ нет, как в $\mathbb Q$ и $\mathbb R$, характеристику считают нулевой. У $\mathbb Z_p$ и у $GF(4)$ характеристика $p$ и $2$.
Число элементов конечного поля — степень простого числа $p^n$, где $p$ — характеристика поля.
Идея: внутри любого конечного поля сидит $\mathbb Z_p$, а всё поле — векторное пространство над ним.
Характеристика — простое число. Суммы $1$, $1 + 1$, $1 + 1 + 1$, … не могут быть все различными, раз элементов конечное число. Если сумма $a$ единиц равна сумме $b$ единиц при $a < b$, то сумма $b - a$ единиц равна нулю, так что характеристика $p$ существует. Она больше $1$, потому что $1 \ne 0$. Если бы $p = ab$ с $1 < a, b < p$, то суммы $a$ единиц и $b$ единиц были бы ненулевыми (по выбору наименьшего $p$), а их произведение, по распределительному закону сумма $ab$ единиц, — нулём. В поле делителей нуля нет, значит, $p$ простое.
Внутри сидит $\mathbb Z_p$. Суммы $0, 1, 1 + 1, \dots$ из меньше чем $p$ единиц различны и складываются и умножаются как остатки по модулю $p$ — это копия поля $\mathbb Z_p$.
Подсчёт. Элементы поля можно складывать и умножать на элементы $\mathbb Z_p$, и все аксиомы векторного пространства выполнены, потому что это частные случаи аксиом поля. Пространство конечно, поэтому у него есть конечный базис $e_1, \dots, e_n$ (добавляем в набор элементы, не лежащие в линейной оболочке уже выбранных, пока оболочка не станет всем полем). Каждый элемент единственным образом записывается как $c_1e_1 + \dots + c_ne_n$ с $c_i \in \mathbb Z_p$, и таких записей $p^n$.
Существует ли поле из $6$ элементов?
Число элементов конечного поля — степень простого, а $6 = 2 \cdot 3$ не степень простого. Поля из $2, 3, 4, 5, 7, 8, 9$ элементов есть, из $6$ и $10$ — нет.
Обратное тоже верно: для каждого простого $p$ и натурального $n$ поле из $p^n$ элементов существует. Для небольших $n$ неприводимый многочлен легко найти перебором, как мы нашли $x^2 + x + 1$, а в общем случае помогает другой путь.
Для любого простого $p$ и натурального $n$ существует поле из $p^n$ элементов.
Доказательство: корни многочлена $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$ значений — запас: даже если часть их испортилась, многочлен, проходящий через большинство принятых точек, можно найти.
Почему две? Всё держится на теореме, которую мы доказали для действительных многочленов в главе 14. Над полем она верна так же, а без поля ломается: в $\mathbb Z_8$, как мы видели, у $x^2 - 1$ четыре корня.
У ненулевого многочлена степени $d$ с коэффициентами из поля не больше $d$ различных корней в этом поле.
Повторим доказательство из главы 14 и отметим, где нужно поле. Индукция по $d$; многочлен степени $0$ — ненулевая константа, корней у него нет. Пусть $a$ — корень многочлена $P$ степени $d$. Деление с остатком на $x - a$ возможно над любым полем (делим на старший коэффициент $1$), а остаток равен $P(a) = 0$, так что $P(x) = (x - a)Q(x)$ со степенью $Q$, равной $d - 1$. Если $b \ne a$ — ещё один корень, то $0 = P(b) = (b - a)Q(b)$. Здесь нужно поле: $b - a \ne 0$, делителей нуля нет, значит, $Q(b) = 0$. Все корни $P$, кроме $a$, — корни $Q$, их не больше $d - 1$ по предположению индукции, а всего не больше $d$.
Два разных кодовых слова кода Рида — Соломона с параметрами $n$ и $k$ различаются не меньше чем в $n - k + 1$ позициях. Поэтому код исправляет любые $t$ ошибок при $2t \le n - k$.
Пусть кодовые слова получены из разных многочленов $f$ и $g$ степени меньше $k$. Их разность $f - g$ — ненулевой многочлен степени меньше $k$, и по предыдущей теореме у него не больше $k - 1$ корней. Значит, $f$ и $g$ совпадают не больше чем в $k - 1$ точках из $n$, а различаются не меньше чем в $n - k + 1$. Минимальное расстояние кода $d \ge n - k + 1$, и по теореме о расстоянии и ошибках код исправляет $t$ ошибок, если $2t + 1 \le n - k + 1$, то есть $2t \le n - k$.
В нашем примере $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$. Формула корней квадратного уравнения — тоже добавление корня, квадратного. Формула Кардано для кубического уравнения добавляет квадратные и кубические корни, формула Феррари для уравнения четвёртой степени — ещё несколько. А для уравнения пятой степени формулы в радикалах нет. Почему у уравнения пятой степени нет формулы? Ответ нашёл тот же Галуа, чьё имя носят конечные поля: он изучал симметрии корней и расширения полей, которые эти корни порождают. Об этом — следующая глава.