Магия восстановления
данных
Как работают коды Рида-Соломона
Аудитория: Начинающие IT
Длина: ~45 минут
Уровень: ★★☆☆☆
Часть 1

Данные теряются.
Это нормально.

Любая передача режется на пакеты. Они летят независимо. Часть не доходит.

  • Перегруженный роутер выбрасывает пакеты в очереди
  • Плохой Wi-Fi искажает биты до неузнаваемости
  • ARQ: «не дошёл пакет №5 - пришли снова». Работает для почты, не для реального времени
  • Ждать 100–300 мс пока пакет долетит обратно = лаг
ИДЕАЛЬНО 1 2 3 4 1 2 3 4 РЕАЛЬНОСТЬ 1 3 4 1 ? 3 4 ARQ: «пришли пакет №2 снова» +100–300 мс задержки В реальном времени - неприемлемо. Нужно восстанавливать без повтора.
Часть 2

FEC: страховка
заранее

FEC - Forward Error Correction. Не реагируем на потерю - готовимся к ней.

ARQ - реактивно

Потеряли → попросили → подождали 200 мс.

FEC - упреждающе

Отправили с запасом → потеряли → восстановили.

RS(10, 4)

10 пакетов данных + 4 восстановительных = 14 итого.
Выживут любые 10 из 14 - исходные данные целы.
Восстановительные пакеты - не копия, это математически вычисленная избыточность.

ОТПРАВЛЯЕМ 14 ПАКЕТОВ D1 D2 D3 D4 D5 D6 D7 D8 D9 D10 R1 R2 R3 R4 любые 4 потеряны ПОЛУЧЕНО 10 ИЗ 14 D1 D3 D4 D6 D7 D8 D10 ✓ D1–D10 восстановлены
Часть 3

Школьная геометрия
как основа RS

Сколько точек нужно, чтобы однозначно провести прямую?

  • 1 точка - бесконечно много прямых. Ничего не фиксирует.
  • 2 точки - ровно одна прямая. Однозначно.
  • Идея RS: данные прячем в точках кривой. Лишние точки - страховка от потерь.
Обобщение

Полином степени k−1 однозначно задаётся k точками. Меньше - нельзя определить. Больше - можно восстановить при потерях.

1 ТОЧКА - ∞ ПРЯМЫХ A не определено 2 ТОЧКИ - 1 ПРЯМАЯ A B единственная прямая
Часть 3 · продолжение

Пример:
y = 4x − 1

Данные: 3 и 7. Кодируем как точки прямой.

  • Точки: (1, 3) и (2, 7)
  • Прямая: y = 4x − 1
  • Страховочная точка: x=3 → y=11
  • Отправляем: 3, 7, 11
Пакет «7» потерялся

Остались (1, 3) и (3, 11). Проводим прямую. При x=2 единственно возможное значение - 7. Восстановлено.

x y 1 2 3 3 7 11 (1, 3) ✓ (2, ?) ✗ (3, 11) ✓ при x=2 на этой прямой: y = 7
Часть 3 · продолжение

От прямых
к полиномам

RS-коды используют не прямые, а полиномы - кривые высоких степеней.

  • Прямая (степень 1) - нужно 2 точки
  • Парабола (степень 2) - нужно 3 точки
  • Полином степени k−1 - нужно k точек
Суть RS

k пакетов данных → k точек полинома. Добавляем лишние точки-пакеты. Потеряли несколько → восстановили кривую → восстановили данные.

x y 1 2 3 4 степень 1 2 точки степень 2 3 точки степень 3 4 точки степень k−1 → нужно k точек
Часть 3.5

Почему обычные числа
не работают

  • Дроби. Коэффициенты полинома почти всегда нецелые. Округление накапливается → вместо 7 декодер выдаёт 6.9999.
  • Переполнение. Байт: 0–255. При умножении полиномов числа уходят в миллионы.
Нужна арифметика, которая

① Только целые числа   ② Никогда не выходит за 0–255   ③ Сложение, умножение, деление работают корректно

Придумал Эварист Галуа в 1830-х. Ему было ~20 лет. Погиб на дуэли через год. Его математика работает в каждом QR-коде на планете.

ПРОБЛЕМА байт: 0 → 255 200 + 100 = 300 ← не влезает +45 255 y = 4.333...x − 1.666... в байт не положишь декодировано: 6.9999983 ожидалось: 7 → нужна другая арифметика
Часть 4

Поля Галуа:
арифметика в коробке

GF(256) - замкнутая система. Любая операция над числами 0–255 даёт результат в 0–255. Без исключений.

  • Сложение = XOR. Результат всегда в диапазоне.
  • XOR обратим: A⊕B=C, значит C⊕B=A. Декодирование возможно.
  • Умножение - через полиномы по модулю. Тоже всегда в 0–255.
На практике

Таблицы умножения для GF(256) вычислены заранее. Процессор смотрит готовый ответ за микросекунды.

АНАЛОГИЯ: ЧАСЫ 12 3 6 9 10 2 10 + 4 = 14 → 2 вышли за 12 → вернулись GF(256): то же, диапазон 0–255 XOR (⊕) A B A⊕B 0 0 0 0 1 1 1 0 1 1 1 0 обратимость A ⊕ B = C C ⊕ B = A ✓
Часть 4 · продолжение

Матрицы:
кодирование на деле

Весь процесс - умножение матриц в GF(256).

  • Данные = вектор (столбец чисел)
  • Матрица Вандермонда задаёт коэффициенты смешивания
  • Результат: данные + избыточные пакеты одним умножением
Восстановление

Строки матрицы выживших пакетов → обратная матрица → умножаем → оригинал. Все обратные матрицы вычислены заранее.

КОДИРОВАНИЕ 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 2 4 8 1 3 5 15 ← единичная (данные) ← Вандермонд (избыток) × D1 D2 D3 D4 = РЕЗУЛЬТАТ D1 D2 D3 D4 R1 R2 R3 данные без изменений избыточные пакеты ДЕКОДИРОВАНИЕ потеряны D2, R1 → вычёркиваем строки 2, 5 оставшиеся 5 строк → инверсия → × выжившие = D1…D4 ✓
Часть 4.5

Честный разговор:
за что платим

  • +40% трафика. 4 пакета на каждые 10. Платим каналом - экономим на задержке.
  • Burst loss. Потери подряд RS плохо переживает. Решение: interleaving - намеренно перемешать пакеты перед отправкой.
  • Вычисления. Алгоритм Берлекэмпа–Мэсси нетривиален. Для слабых чипов - имеет значение.
  • В 5G не RS - там LDPC и Polar-коды. Эффективнее на высоких скоростях.
ТРЕЙДОФФ БЕЗ FEC данные 100% +200 мс лаг С FEC · RS(10,4) данные 100% +40% 0 мс ✓ BURST LOSS - СЛАБОЕ МЕСТО без interleaving: 5 подряд → провал с interleaving: равномерно → RS справится
Часть 4.5 · продолжение

Interleaving:
антидот от burst loss

Намеренное перемешивание пакетов перед отправкой.

  • Burst loss «размазывается» по множеству полиномов
  • Ни один полином не теряет критическое число точек
  • Каждый полином восстанавливается независимо
Пример: CD

Царапина = burst loss. CIRC (двойной RS + interleaving) превращает её в равномерные единичные ошибки - RS восстанавливает их незаметно.

ДО ПЕРЕМЕШИВАНИЯ P1 P2 P3 A1 A2 A3 A4 B1 B2 B3 B4 C1 C2 C3 C4 → отправка по строкам: A1 A2 A3 A4 B1 B2 B3 B4 C1… ← burst loss P1 теряет 3/4 → RS не справится ↓ interleaving (по столбцам) ПОСЛЕ ПЕРЕМЕШИВАНИЯ порядок отправки: по столбцам A1 B1 C1 A2 B2 C2 A3 B3 C3 A4 B4 C4 тот же burst - 4 пакета НА ПРИЁМНИКЕ: РАСКЛАДЫВАЕМ ОБРАТНО P1 A1 ✗ ✗ A4 потеряно 2 → RS ✓ P2 B1 ✗ B3 B4 потеряно 1 → RS ✓ P3 C1 ✗ C3 C4 потеряно 1 → RS ✓ burst на 4 пакета → каждый полином теряет ≤2 → RS ✓
Часть 5

Где это работает
прямо сейчас

  • QR-коды. Уровень H - до 30% замазано, сканируется. Поэтому логотипы в центре.
  • CD/DVD. Царапина - burst loss. Двойной RS + interleaving спасают данные.
  • Космос. «Вояджер-1» - 23+ млрд км. Большинство битов теряется. Без RS - только шум.
  • RAID 6. Два диска падают одновременно - массив выживает.
QR · до 30% повреждено RS восстанавливает ✓ CD · царапина → OK Космос · Вояджер диск 1 ✓ диск 2 ✓ диск 3 ✓ ✗ ✗ диск 6 ✓ RAID 6 · 2 диска ✓
Часть 5 · продолжение

udp2raw
+ tinyfecVPN

udp2raw маскирует UDP под TCP. Сам по себе потери не лечит.

В связке с tinyfecVPN: RS-избыточность добавляется внутри туннеля, udp2raw скрывает туннель под TCP.

Результат

Провайдер видит TCP.
Потери восстанавливаются автоматически.
Математика Галуа из 1830-х - в вашем терминале.

СХЕМА РАБОТЫ UDP данные tinyfecVPN добавляет RS-избыточность udp2raw маскирует под TCP провайдер видит TCP ✓ данные восстановлены ✓
Итог · 0:47 – 0:50

Три вещи,
которые остаются

01

Избыточность - инструмент. Иногда +40% трафика лучше, чем 300 мс задержки.

02

Математика XIX века - в вашем телефоне. Галуа придумал это в 1830-х. Хорошая теория находит применение.

03

Инструмент под задачу. RS - не серебряная пуля. В 5G выбрали другое

ВСЯ ЦЕПОЧКА данные GF(256) + полином данные + избыток часть потеряна обратная матрица данные восстановлены ✓