Коды с исправлением ошибок

QR-код на кофейной упаковке можно прочитать даже если он наполовину испачкан кофе - это коды Рида-Соломона. Wi-Fi 6 работает вблизи теоретического предела Шеннона - это LDPC. Voyager 1 передаёт данные с расстояния 23 млрд км при мощности 20 Вт - RS + Golay.

• **QR-коды** используют RS(n,k) с четырьмя уровнями коррекции. Уровень H позволяет восстановить 30% повреждённого кода - именно поэтому компании рисуют логотипы поверх QR.
• **5G NR** использует LDPC для пользовательских данных и polar-коды для управляющих каналов. Polar-коды - первые, теоретически достигающие предела Шеннона.
• **RAID-6** использует RS-коды для защиты от отказа двух дисков одновременно. Это та же математика, что и в космических зондах.

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

• Communication Channel and Capacity

Код Хэмминга

Ричард Хэмминг работал на ранних релейных компьютерах Bell Labs в выходные дни, когда никого не было рядом. Ошибки в перфокартах раздражали его - компьютер просто останавливался. В 1950 году он придумал элегантный способ: добавить несколько «проверочных битов», которые позволяют не только обнаружить, но и исправить одну ошибку. Код Хэмминга (7,4) добавляет 3 бита к каждым 4 информационным, позволяя исправить любую одиночную ошибку.

**Код Хэмминга (n,k):** n = 2^r − 1, k = n − r, r проверочных битов. Кодовое расстояние d_min = 3: можно исправить 1 ошибку или обнаружить 2. Скорость R = k/n = (2^r − 1 − r)/(2^r − 1). При r=3: (7,4), R=4/7≈0.57. При r→∞: R→1 (асимптотически оптимально).

Коды Рида-Соломона

Коды Рида-Соломона (1960) работают не с битами, а с символами (байтами или словами). Они основаны на полиномах над конечными полями: сообщение кодируется как полином, а кодовое слово - это значения этого полинома в n точках. При наличии до t ошибок можно восстановить полином по (n-t) точкам. Классика: RS(255,223) из стандарта CD и космических зондов.

**RS(n,k) код:** n символов в кодовом слове, k информационных. Исправляет t = (n-k)/2 ошибок. Кодовое расстояние d_min = n-k+1 (достигает границы Синглтона!). Работает над GF(2^m): RS(255,223) над GF(256), исправляет до 16 байт ошибок.

LDPC коды

LDPC (Low-Density Parity-Check) коды - матрица проверок чётности, в которой мало единиц. Придуманы Галлагером в 1963 году, забыты на 30 лет (компьютеров не хватало), переоткрыты Маккаем и Нилом в 1995. Ключевой алгоритм декодирования - belief propagation: сообщения передаются по графу Тэннера между «битовыми» и «проверочными» узлами, итерационно уточняя оценки вероятностей.

**LDPC:** H·c = 0 (мод 2), где H - разреженная матрица проверок. Belief propagation декодирует за O(n) операций. Достигает предела Шеннона на ~0.0045 дБ (в 2001). Используется в: Wi-Fi (802.11n/ac/ax), 10G Ethernet, DVB-S2, 5G NR.

Turbo-коды

Turbo-коды (Берру и Гллавьё, 1993) стали сенсацией: первый практический код, подошедший на 0.5 дБ к пределу Шеннона. Идея: два рекурсивных свёрточных кодера (RSC), разделённых перемежителем (interleaver), работают параллельно. Декодирование - итерационный обмен «мягкой» информацией между двумя BCJR-декодерами через общий «турбо» цикл.

**Turbo-код:** Кодовое слово = [u, p1, p2], где u - информация, p1 = RSC1(u), p2 = RSC2(π(u)), π - перемежитель. Декодирование: BCJR1 и BCJR2 итерационно передают L-values (мягкие биты). 5-10 итераций дают хороший результат. Скорость обычно 1/3 или 1/2. Используется в 3G (UMTS), 4G (LTE).

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

• **Хэмминг (7,4):** первый практический FEC-код, исправляет 1 ошибку. Основа для всех последующих разработок.
• **Рид-Соломон:** работает с символами, основан на полиномах над GF(q). CD, QR, RAID-6, космос.
• **LDPC:** разреженные матрицы + belief propagation. Подходит на ~0.05 дБ к пределу Шеннона. Wi-Fi 6, 5G.
• **Turbo-коды:** два RSC-кодера + перемежитель + итерационное BCJR-декодирование. Революция 1993 года. Используются в 4G.

Связанные темы

Коды с исправлением ошибок опираются на теорию каналов и применяются в сжатии:

• Канал связи и пропускная способность — Предел Шеннона - цель, к которой приближаются все эти коды
• Типичные последовательности — AEP используется в доказательстве существования хороших кодов
• Info Theory на собеседовании — Коды Хэмминга - частая тема на системных интервью

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

• Почему идею LDPC пришлось «переоткрывать» через 30 лет? Что это говорит о связи математики и вычислительных мощностей?
• QR-коды уровня H позволяют читать 30%-повреждённый QR. Какова цена этого: что меняется по сравнению с уровнем L?
• Turbo-коды и LDPC оба близки к пределу Шеннона. Почему 5G выбрал LDPC вместо turbo?

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

• alg-01-big-o
• crypto-19-hash-functions