Система передачи информации
Источник
Кодер
Декодер
Приёмник
Моноид
Моноид — это тройка (M, ∘, e): множество M, бинарная операция ∘ : M × M → M и элемент e ∈ M, такие что:
- ассоциативность: (a ∘ b) ∘ c = a ∘ (b ∘ c) для любых a, b, c ∈ M;
- нейтральный элемент: e ∘ a = a ∘ e = a для любого a ∈ M.
Коммутативность (a ∘ b = b ∘ a) не требуется. Благодаря ассоциативности произведение a₁ ∘ a₂ ∘ … ∘ aₙ не зависит от расстановки скобок, а пустое произведение равно e.
—
—Свёртка: e ∘ a₁ ∘ a₂ ∘ … ∘ aₙ
Проверка аксиом
Таблица Кэли
Диофантовы уравнения
Диофантово уравнение — уравнение с целыми коэффициентами, решения которого ищутся в целых числах. Главный инструмент для линейных уравнений — теорема:
- уравнение ax + by = c разрешимо в целых числах ⇔ НОД(a, b) | c;
- если (x₀, y₀) — решение, то все решения: x = x₀ + (b/d)·t, y = y₀ − (a/d)·t, t ∈ ℤ, где d = НОД(a, b).
Частное решение даёт расширенный алгоритм Евклида: он находит коэффициенты Безу s, t с a·s + b·t = d.
—
—Сравнения по модулю
Целые числа a и b сравнимы по модулю m, если они дают одинаковые остатки при делении на m: a ≡ b (mod m) ⇔ m | (a − b).
- сравнения по одному модулю можно складывать, вычитать и перемножать, а значит — возводить в степень;
- делить обе части на c можно, только если НОД(c, m) = 1;
- все числа разбиваются на m классов вычетов 0, 1, …, m − 1 — это кольцо ℤₘ.
На арифметике остатков построены RSA, Диффи–Хеллман и контрольные суммы. Линейное сравнение ax ≡ b (mod m) разобрано в разделе «Диофантовы уравнения».
—
—Вычеты
Класс вычетов числа a по модулю m — множество [a]ₘ = {a + km : k ∈ ℤ} всех чисел, сравнимых с a. Любой элемент класса называется вычетом.
- полная система вычетов — по одному представителю из каждого из m классов, например 0, 1, …, m − 1;
- приведённая система вычетов — представители классов, взаимно простых с m; их φ(m) штук;
- классы складываются и перемножаются: [a] + [b] = [a + b], [a]·[b] = [ab] — это кольцо ℤₘ, а обратимые классы образуют группу ℤₘ*.
Квадратичные вычеты и критерий Эйлера разобраны в разделе «Сравнения» (пример 4).
—
—Визуализация кода
Таблица кодов
| Символ | Частота | Код |
|---|
Кодирование (символ → биты)
Декодирование (биты → символ)
Дерево кода
Визуализация кода Хэмминга
Кодирование (блок данных → кодовое слово)
биты данных биты чётности
Передача по каналу
Декодирование и самоконтроль (синдром → исправление)
ошибок нет ошибка найдена и исправлена — нажмите на блок для подробностей
Визуализация кода Адамара
Матрица Адамара
Кодирование (блок данных → строка матрицы)
первый бит данных — знак (0: строка H, 1: инвертированная строка), остальные — номер строки
Передача по каналу
Декодирование (максимум корреляции → исправление)
ошибок нет ошибки найдены и исправлены ошибок больше, чем код может исправить — декодировано неверно · нажмите на блок для подробностей