От сбоев релейных машин к оборонной математике холодной войны
В конце 1940-х годов математик Ричард Уэсли Хэмминг работал в лаборатории Bell Labs на электромеханической релейной машине Bell Model V, выполнявшей одну операцию за несколько секунд и считывавшей данные с капризных перфолент шириной семь восьмых дюйма (до шести отверстий в ряду). В будни при сбое реле машина останавливалась и мигала сигнальными лампами, позволяя операторам вручную поправить данные, но в выходные дежурных не было, и при первой же ошибке машина сбрасывала расчёт и переходила к следующей задаче. Потеряв очередные выходные расчёты, Хэмминг сформулировал вопрос, позднее пересказанный им в интервью: если машина уже умеет обнаружить ошибку, почему она не может определить её позицию и сама её исправить?
Простые методы кодирования задачу не решали. Один бит чётности (кодовое расстояние 2) фиксировал лишь нечётное число искажений и не знал, какой именно бит повреждён; код «два из пяти» проверял десятичные цифры 0–9 без исправления; а прямое троекратное повторение каждого бита (3,1) снижало полезную скорость канала на две трети. Опираясь на теорию информации коллеги по Bell Labs Клода Шеннона (1948), Хэмминг в апреле 1950 года опубликовал в журнале Bell System Technical Journal статью «Коды с обнаружением и исправлением ошибок», введя понятия минимального кодового расстояния и «совершенного» линейного блочного кода.
Однако для радиолокации и систем связи холодной войны одиночной коррекции битов не хватало: атмосферные помехи и радиопротиводействие в американской системе ПВО SAGE порождали пакетные ошибки, ломавшие десятки бит подряд. Чтобы защитить военные каналы, в Лаборатории Линкольна MIT на средства ВВС и Министерства обороны США исследователи Ирвинг Рид и Густав Соломон в июне 1960 года опубликовали пятистраничную статью «Полиномиальные коды над некоторыми конечными полями», научив алгоритмы восстанавливать целые разрушенные фрагменты сообщений.
Геометрия кодов Хэмминга и алгебра Рида — Соломона
Код Хэмминга строит перекрывающиеся проверки на чётность. В классическом блочном коде (7,4) к четырём информационным битам добавляются три контрольных на позициях степеней двойки (1, 2, 4, 8…), а для 5-битного телеграфного кода Бодо применялся усечённый вариант (9,5) от семейства (15,11). В общем виде для r проверочных бит длина блока равна n = 2r − 1, а число бит данных — k = 2r − r − 1 (верхний предел плотности задаёт граница Хэмминга). При приёме декодер умножает слово на проверочную матрицу H по модулю 2 и получает синдром ошибки: ненулевой синдром прямо равен двоичному номеру сбойного бита, что позволяет мгновенно инвертировать его. Добавление общего бита чётности расширяет код до расстояния d = 4 (схемы (8,4) или (72,64)) — режим SECDED, исправляющий одиночную и надёжно фиксирующий двойную ошибку.
Коды Рида — Соломона RS(n, k) переходят от отдельных битов к многобитным символам (байтам) как коэффициентам многочленов степени меньше k над конечным полем Галуа GF(2m), где n = 2m − 1. Поскольку многочлен степени меньше k однозначно задаётся любыми k точками, добавление 2t = n − k контрольных символов позволяет алгебраически восстановить до t произвольно искажённых байтов (или до 2t стираний с известным местом), делая схему нечувствительной к сериям помех. Промышленное применение этой алгебры открыли быстрые алгоритмы декодирования Элвина Берлекэмпа (1968) и Джеймса Мэсси (1969).
Прорыв в космонавтике, архитектуре ЭВМ и экономике носителей
Корректирующие коды радикально повысили надёжность трёх ключевых отраслей. Во-первых, по мере миниатюризации микросхем память стала уязвима к сбоям от фонового альфа-излучения и космических частиц. Начиная с суперкомпьютера IBM 7030 Stretch (1961) расширенные коды Хэмминга SECDED в вариантах (39,32) и (72,64) стали стандартом серверной памяти ECC RAM, а также применялись в дисковых массивах RAID 2 (и RAID 6 на базе алгебры Рида — Соломона), обеспечив круглосуточную работу банков, бирж и дата-центров.
Во-вторых, в годы космической гонки конкатенированный код (внутренний свёрточный код плюс внешний Рид — Соломон (255,223)) преодолел барьер теплового шума на межпланетных трассах. Именно эта связка позволила зондам NASA «Вояджер-1» и «Вояджер-2» (1977) передать на Землю чёткие снимки Юпитера, Сатурна, Урана и Нептуна с расстояния в миллиарды километров при мощности передатчика около 20 ватт.
В-третьих, кодирование совершило революцию в потребительской культуре. При создании компакт-диска (CD) в 1982 году Philips и Sony внедрили перемежаемый код Рида — Соломона (CIRC), позволяющий восстанавливать сплошные выпадения дорожки длиной до 4 000 бит (около 2,5 мм). Устойчивость к царапинам и пыли сделала CD, DVD и Blu-ray экономически рентабельными и вытеснила уязвимый винил и магнитные кассеты. Та же математика защищает двумерные QR-коды (Denso Wave, 1994), сохраняющие читаемость при повреждении до 30 % поверхности, спутниковое ТВ DVB и линии DSL.
Наследие: от предела Шеннона к облачным хранилищам XXI века
К XXI веку в серверных контроллерах памяти классические матрицы Хэмминга сменили сбалансированные деревья чётности для 128–256-битных слов (хотя схема (72,64) до сих пор востребована в ПЛИС FPGA). Для сверхплотных беспроводных каналов вблизи теоретического предела Шеннона пришли итеративные вероятностные схемы: турбокоды (1993), возрождённые LDPC-коды Галлагера (Wi-Fi, спутниковое вещание DVB-S2, контроллеры SSD) и полярные коды Эрдала Арикана (2009), принятые в каналах управления 5G.
При этом коды Рида — Соломона обрели вторую жизнь в облачных дата-центрах (Ceph, HDFS, объектные хранилища). Вместо дорогостоящего трёхкратного копирования файлов современное стирающее кодирование (erasure coding) дробит данные на блоки с расчётной избыточностью (например, 10+4), гарантируя сохранность петабайтов информации при одновременном отказе нескольких серверов и более чем вдвое снижая затраты на оборудование и энергию.
