Линейные коды над полями Галуа

Voyager-1 передаёт данные с расстояния 24 миллиарда км через код Рида-Соломона RS(255, 223), исправляющий до 16 ошибок в блоке. CD-диск с царапиной проигрывается без щелчков благодаря CIRC-коду. QR-код Wi-Fi-логина с закрашенным углом сканируется. За всем этим - линейные коды над полями Галуа: подпространства над конечными полями, защищающие информацию от ошибок канала.

• QR-коды: RS(255, 223) над GF(256), уровень коррекции H исправляет до 30% повреждения
• RAID-6: два диска XOR с весами из GF(256) - код исправляет отказ любых двух дисков
• Глубокий космос: Voyager использовал BCH + свёрточный код с перемежением для надёжной связи на расстоянии 20 млрд км

Предварительные знания

• Algebra and Cryptography

Поля Галуа GF(q): построение и арифметика

**Поле Галуа GF(q)** существует тогда и только тогда, когда q = p^n - степень простого. Обозначение: GF(q) = 𝔽_q. **GF(p)** = Z/pZ: простое поле, p элементов. Арифметика по модулю p. **GF(p^n)** = GF(p)[x]/(f(x)), где f - неприводимый многочлен степени n над GF(p). Элементы - полиномы степени < n, умножение - по модулю f. **Структура:** Мультипликативная группа GF(q)* = GF(q) \ {0} - циклическая порядка q-1. Генератор называется примитивным элементом. **GF(2^8) для AES:** f(x) = x^8 + x^4 + x^3 + x + 1 (неприводим над GF(2)). Каждый байт - элемент GF(256). XOR - это сложение, полиномиальное умножение mod f - умножение поля. **Характеристика** поля GF(p^n) равна p: p·1 = 0. Это означает, что (a+b)^p = a^p + b^p (бином Фробениуса).

**Единственность полей Галуа:** Для каждой степени простого q = p^n существует ровно одно поле из q элементов (с точностью до изоморфизма). Это глубокий теоретический факт: любые два поля GF(p^n) изоморфны. Поэтому говорят «поле GF(q)», а не «поле из q элементов, построенное таким-то способом».

Линейные коды: матрицы G и H

**Линейный [n, k]-код** C над GF(q) - k-мерное подпространство GF(q)^n. **Порождающая матрица G** (k×n): строки образуют базис C. Кодирование: c = m·G, где m ∈ GF(q)^k - информационный вектор. **Проверочная матрица H** (r×n, r = n-k): c ∈ C ⟺ H·cᵀ = 0. Столбцы H - «синдромные» векторы. **Расстояние Хемминга:** d(u, v) = |{i : u_i ≠ v_i}| - число позиций, в которых слова отличаются. Минимальное расстояние кода d_min = min{d(u,v) : u,v ∈ C, u≠v} = min{wt(c) : c ∈ C, c≠0} (т.к. C - подпространство). **Исправление ошибок:** код с d_min исправляет t = ⌊(d_min-1)/2⌋ ошибок и обнаруживает d_min-1 ошибок. **Синдромное декодирование:** синдром ошибки e: s = H·eᵀ = H·(c+e)ᵀ. Если ошибка ≤ t, по синдрому однозначно определяется паттерн ошибки.

**Граница Хемминга (граница упаковки шаров):** Линейный [n, k]-код над GF(q), исправляющий t ошибок, удовлетворяет: ∑_{i=0}^{t} C(n, i)·(q-1)^i ≤ q^{n-k} Коды, достигающие этой границы - **совершенные коды**. Единственные нетривиальные совершенные коды над GF(2): код Хемминга и код Голея [23, 12, 7]. Доказательство единственности - выдающийся результат 1970-х годов.

BCH-коды: исправление t ошибок через алгебру

**BCH-коды** (Боуз-Чоудхури-Хоквингем) - мощный класс циклических кодов, способных исправлять заданное число ошибок t. **Конструкция:** Выберем примитивный элемент α поля GF(q^m). BCH-код порождается полиномом: g(x) = НОК(m_1(x), m_2(x), ..., m_{2t}(x)), где m_i(x) - минимальный полином α^i над GF(q). **Граница BCH:** Если g(x) имеет среди корней 2t последовательных степеней α^b, α^{b+1}, ..., α^{b+2t-1}, то d_min ≥ 2t+1. **Декодирование (алгоритм Берлекэмпа-Мэсси):** 1. Вычислить синдромы S_i = r(α^i) для i = 1, ..., 2t. 2. Найти полином локатора ошибок σ(x) - корни указывают позиции ошибок. 3. Исправить ошибки по значениям σ(x) и полинома значений ошибок. **RS-коды как BCH:** Коды Рида-Соломона RS(n, k) над GF(q) - это BCH-коды с параметрами m=1, q первичное, достигающие границы Синглтона d_min = n-k+1.

**Совершенные коды:** Код Хемминга [2^r-1, 2^r-1-r, 3] совершенен: шары Хемминга радиуса 1 вокруг кодовых слов точно покрывают GF(2)^n без перекрытия. Код Голея [23, 12, 7] - другой совершенный двоичный код, открытый Голеем в 1949 году. Доказано (Тит, 1973): это все нетривиальные совершенные коды над простыми полями.

Ключевые идеи

• GF(q) существует ⟺ q = p^n; GF(p^n) = GF(p)[x]/(f), f - неприводимый степени n
• Линейный [n,k]-код: подпространство размерности k в GF(q)^n; кодирование c = m·G
• Проверочная матрица H: c ∈ C ⟺ H·cᵀ = 0; синдром ошибки s = H·eᵀ
• BCH-коды: 2t последовательных корней порождающего полинома ⟹ d_min ≥ 2t+1 ⟹ исправление t ошибок

Дальнейшие пути

Линейные коды - это линейная алгебра над конечными полями. Алгебраическая геометрия обобщает их до кодов Гоппы на кривых. Теория BCH прямо связана с алгебраической теорией полиномиальных корней - следующий шаг к коммутативной алгебре.

• Коммутативная алгебра — Циклические коды - идеалы в кольце полиномов GF(q)[x]/(x^n - 1); теория идеалов объясняет структуру кодов
• Алгебра и криптография — Коды Рида-Соломона - BCH-коды над большим полем, применяемые и в криптографии (секретное разделение Шамира)

Вопросы для размышления

• Докажите, что минимальное расстояние линейного кода равно минимальному весу ненулевого кодового слова. Используйте линейность C.
• Постройте явно код Хемминга [7,4,3] над GF(2): напишите все 16 кодовых слов и убедитесь, что минимальное расстояние равно 3.
• Почему код Голея [23,12,7] совершенен? Проверьте: подсчитайте суммарный объём шаров Хемминга радиуса 3 вокруг 2^12 кодовых слов и убедитесь, что она равна 2^23.

Связанные уроки

• nt-11