Кодирование и автоматы (6 февраля 2024)

1. CRC-32
   1. Один из вариантов хеширования последовательности бит a₀, a₁, ... a_n-1 − остаток от деления многочлена A(x)*x^k на G(x),
   где G(x) -- специальный многочлен, и k = deg G.
   1. В CRC-32-IEEE-802.3 (используется в v.42, mpeg-2, png, POSIX cksum) k = 32, G(x) = 0xEDB88320 (32 бита).
   2. Вычисление взятия по модуля одним проходом за O(n) при w ≥ k
   3. Даны CRC-32(A) и CRC-32(B). Найдите CRC-32(A XOR B)
   4. Зная CRC-32(A), посчитайте за O(1) CRC-32(A1)
   
   
2. Коды Рида-Соломона
   1. Пример 1: передать 1 бит по каналу, где любой 1 бит может быть заменён. 00, 11 − плохой код. 000, 111 − хороший.
   2. Пример 2: только проверка на корректность, без исправления ошибок. Передать xor.
   3. Пример 3: передать n бит. Код повторять три раза. Код частичные суммы.
   4. Критерий того, что при k ошибках всё можно однозначно декодировать: расстояния Хэмминга не менее 2k+1.
   
   
3. Коды Рида-Соломона.
   1. Задача: хотим передать n слов из поля F_q, q > n, не более k ошибок.
   2. Какие бывают q, чтобы ∃ поле F_q? q = pⁿ. Поля простого размера − остатки по модулю; для размера pⁿ − нужно найти неприводимый многочлен степени n над F_p.
   3. F_2³² − конечные поля имеют размер pⁿ, размера p это просто остатки по модулю p (Z/pZ), размера pⁿ (2³²) − остатки по модулю неприводимого многочлена над F_p степени n. F_2³² = F₂[x] / (x³² + x²² + x² + x + 1).
   4. Входные данные − многочлен. Алгоритм кодирования − вычисление значений многочлена в произвольных n+2k точках x_i.
   5. Корректность кодирования: у A₁-A₂ не более n-1 корней ⇒ у A₁ и A₂ значения хотя бы в 2k+1 точке различны
   6. Проверка наличия ошибок − интерполяция имеет степень не более n-1.
   7. Исправление ошибок: A(x) − входные данные, A'(x) − интерполяция переданного, E(x) = (x-x_e1)...(x-x_ek) − многочлен ошибок. У B(x) = A(x)E(x) и A'(x)E(x) совпадают значения во всех n+2k точках. СЛАУ: неизвестные − коэффициенты B и E, каждая из n+2k точек даёт уравнение.
   8. Асимптотика декодирования. Гаусс O((n+k)³). Бэрликэмп-Мэсси O((n+k)²).
   9. Рид-Соломон. Где же ответ? B = A*E, A'*E, неизвестные - коэффициенты B и E
   
   
4. Сверхбыстрая линейная рекуррента
   1. Фибоначчи за O(logn): возведение матрицы в степень
   2. Линейная рекурренты длины k за O(k³logn): возведение матрицы в степень
   3. Линейная рекурренты длины k за O(klogklogn): xⁿ mod A(x), где A(x) = x^k - ∑x^k-ia_i
   
   
5. ??? Бэрликэмп-Мэсси O((n+k)²).

1. Автоматы. База.
   1. Определение детерминированного и недетерминированного.
   2. Принятие строки детерминированным O(|s|) и недетерминированным O(m|s|).
   3. Детерминизация: новые вершины = множества 2ⁿ.
   
   
2. Эквивалентность и минимизация
   1. Проверка эквивалентности двух автоматов: очередь пар разных состояний O(m²).
   2. Минимизация автомата: правые контексты, разбиение вершин на классы эквивалентности, корректность определения мин автомата.
   3. Минимизация автомата: алгоритм за O(nm) перебором рёбер "вперёд" (n split-ов).
   4. Суффиксный автомат: прелюдия, мы уже почти понимаем что это и как это строить (минимизация суф. дерева). Он линейный (2n вершин, 3n рёбер).
   5. Проверка эквивалентности через минимизацию: попадут ли в один класс s₁ и s₂.
   6. Минимизация через детерминизацию (Алгоритм Бржозовского): A_min = d(r(d(r(A)))) = drdrA. Подходит для недетерминированных. [paper].
   
   
3. Хопкрофт: Минимизация за O(nklogn)
   1. Замыкание автомата до полного ⇒ m = nk.
   2. Алгоритм за O(nm) −- переделываем на перебор рёбер "назад".
   3. Лемма: делить нужно только по любой одной из половин ⇒ по меньшей.
   4. Время работы: каждая вершина перекрасится ≤logn раз ⇒ O(mlogn).
   5. Реализация: Split(class, char) за линию с перекраской меньшей половины каждого затронутого split-ом класса.
   
   
4. Изоморфность
   1. Изоморфность двух автоматов за O(m₁+m₂).
   2. Проверка изоморфности минимальному за O((n₁+n₂)k).