Линейная алгебра
Линейная алгебра над конечными полями
Как передать 1 петабайт через спутниковый канал с 30% потерями без повторной отправки? Линейная алгебра над конечными полями - единственный математически гарантированный ответ.
- **5G NR:** коды LDPC с кодовой ставкой 8/9 и скоростью декодирования 10 Гбит/с на ASIC Qualcomm - основа физического уровня 5G
- **QR-коды:** код Рида-Соломона над GF(2^8) исправляет до 30% потерянных данных - поэтому повреждённые QR-коды сканируются
- **Дисковые массивы RAID-6:** два избыточных диска по схеме Reed-Solomon гарантируют восстановление при двух одновременных отказах
- **Спутниковая связь:** DVB-S2X использует коды LDPC + BCH для работы при SNR = -2 дБ (сигнал ниже уровня шума)
Предварительные знания
- Конечные поля GF(q)
- Векторные пространства
- Расстояние Хэмминга
Векторные пространства над GF(q)
Линейная алгебра над GF(2) лежит в основе всех линейных кодов исправления ошибок. Код Хэмминга (7,4) - первый систематический код (Хэмминг, 1950, Bell Labs). Коды LDPC (Gallager, 1963) используются в 5G NR с кодовыми ставками до 8/9 и скоростью декодирования 10 Гбит/с на ASIC-чипах Qualcomm.
Линейная алгебра над GF(q) отличается от вещественной в одном ключевом аспекте: характеристика поля конечна. GF(2): 1+1=0. GF(q) для простого q - поле вычетов Z/qZ. GF(q^m) - расширение через неприводимый многочлен над GF(q). Все стандартные теоремы (ранг, ядро, образ) сохраняются дословно.
Над GF(2) все арифметические операции выполняются по модулю 2: сложение = XOR, умножение = AND. Это делает реализацию аппаратно крайне эффективной - на FPGA весь декодер Хэмминга(7,4) занимает 12 логических элементов.
Сколько векторов содержит подпространство размерности k над GF(q)?
Подпространство размерности k над GF(q) имеет q^k элементов: каждый из k координат в выбранном базисе может принимать любое из q значений поля. Над GF(2) это 2^k - объясняет связь с теорией кодирования.
Линейные коды и теорема Синглтона
Линейный код [n, k, d] над GF(q) - это k-мерное подпространство в GF(q)^n. Параметры: n - длина кодового слова, k - размерность сообщения, d - минимальное расстояние Хэмминга. Код Рида-Соломона достигает границы Синглтона d = n - k + 1 и используется в QR-кодах, дисках Blu-ray, спутниках Voyager.
Что утверждает граница Синглтона для линейного кода [n, k, d]?
Граница Синглтона: минимальное расстояние d линейного кода [n, k, d] удовлетворяет d <= n - k + 1. Доказательство через подсчёт размерности: проколов n - d позиций, получают инъекцию GF(q)^k → GF(q)^(n-d), откуда k <= n - d. Коды Рида-Соломона достигают равенства.
Применения в криптографии
В криптографии линейная алгебра над GF(2) и GF(2^k) - основа AES, McEliece-cryptosystem, кодов Гольдрайха-Левина. AES SubBytes использует афинное преобразование над GF(2^8); MixColumns - умножение на матрицу 4×4 над GF(2^8). Атаки на код-коды (code-based cryptography) опираются на NP-трудность декодирования произвольного линейного кода.
Граница Синглтона d <= n-k+1 - это прямое следствие того, что любые k столбцов матрицы H должны быть линейно независимы для обеспечения единственности исправления. MDS - это достижение этой границы.
Почему AES оперирует именно в GF(2^8), а не просто над GF(2)?
GF(2) даёт только линейные операции (XOR). GF(2^8) при тех же байтовых данных предоставляет мультипликативную структуру. Мультипликативный обратный в GF(2^8) - нелинейная функция, ключевой источник криптографической стойкости S-box. Без этой структуры не было бы нелинейности в AES.
Связи с алгеброй, информатикой и криптографией
Линейная алгебра над конечными полями пронизывает всю современную цифровую технологию.
- Криптография (AES, ECC) — Связанная тема
- Теория кодирования: LDPC — Связанная тема
- Алгебраическая геометрия — Связанная тема
- Квантовые коды — Связанная тема
Итоги
- Линейный код [n,k,d] - подпространство размерности k в GF(q)^n с минимальным расстоянием d
- G (k x n) - порождающая матрица; H ((n-k) x n) - проверочная; H*G^T = 0 над GF(q)
- Синдром s = H*r^T: s = 0 iff r - кодовое слово; s != 0 однозначно задаёт ошибку при wt(e) <= t
- Граница Синглтона: d <= n-k+1; MDS коды достигают её (RS-коды над GF(q^m))
- RS[255,223] над GF(2^8) исправляет 16 ошибок в 255 байтах - используется в CD, QR, RAID
- LDPC: разреженная H над GF(2) + Tanner-граф + BP-декодирование - основа 5G, Wi-Fi 6, DVB
Код Хэмминга (7,4) над GF(2) имеет параметры [n=7, k=4, d=3]. Сколько ошибок он исправляет и почему не является MDS кодом?
t = floor((d-1)/2) = floor(2/2) = 1. Граница Синглтона: d <= n-k+1 = 7-4+1 = 4. Хэмминг(7,4) имеет d=3 < 4, поэтому не MDS. MDS-код [7,4,4] существует только над полем с q >= 7 (например, GF(7) или GF(8)). Над GF(2) такого кода не существует.