Технология и формат 1950–1960 гг.

Коды Хэмминга и Рида — Соломона (помехоустойчивое кодирование)

Математическая теория исправления ошибок в памяти ЭВМ и зашумлённых каналах связи (1950–1960), обеспечившая надёжность космических миссий, серверов и оптических дисков.

Краткая справка

Помехоустойчивое кодирование, созданное Ричардом Хэммингом (1950) и обобщённое Ирвингом Ридом с Густавом Соломоном (1960), позволило не просто фиксировать сбои в памяти и радиолиниях, но и автоматически восстанавливать утраченные данные. Одиночная коррекция Хэмминга (SECDED) стала опорой серверной памяти ECC с 1961 года, а алгебраические коды Рида — Соломона сделали возможной дальнюю космическую связь («Вояджер»), защищённые оптические диски CD/DVD и QR-коды.

Графическая схема классического двоичного кода Хэмминга (7,4) с четырьмя информационными и тремя проверочными битами
Диаграмма Венна для кода Хэмминга (7,4): три контрольных круга (p1, p2, p3) перекрывают четыре информационных бита (d1–d4), позволяя однозначно вычислить позицию одиночной ошибки. Иллюстрация: User:Cburnett, CC BY-SA 3.0

От сбоев релейных машин к оборонной математике холодной войны

В конце 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), гарантируя сохранность петабайтов информации при одновременном отказе нескольких серверов и более чем вдвое снижая затраты на оборудование и энергию.

Частые вопросы и ответы

В чём принципиальное различие между кодом Хэмминга и кодом Рида — Соломона?
Код Хэмминга оперирует отдельными битами и идеален для редких случайных однобитных сбоев в оперативной памяти (ECC), тогда как код Рида — Соломона работает с многобитными символами (байтами) как коэффициентами многочленов в конечных полях Галуа и эффективно исправляет пакетные серии ошибок на дисках, в радиолиниях и QR-кодах.
Что означает режим SECDED и почему обычного кода Хэмминга (7,4) не хватает для серверов?
Базовый код Хэмминга имеет кодовое расстояние 3: он исправляет одиночную ошибку, но при двойной ошибке может принять её за одиночную и «исправить» неверный бит. Добавление одного общего бита чётности увеличивает расстояние до 4 (SECDED — Single Error Correction, Double Error Detection), позволяя чинить 1 бит и безошибочно фиксировать двойной сбой.
Почему коды Рида — Соломона 1960 года получили массовое применение лишь спустя два десятилетия?
Алгебраическое декодирование многочленов над полями Галуа требовало огромных вычислений для элементной базы начала 1960-х годов. Ситуация изменилась только после открытия быстрых алгоритмов Берлекэмпа — Мэсси (1968–1969) и удешевления микросхем СБИС к концу 1970-х — началу 1980-х годов (проекты «Вояджер» и CD).
Как коды Рида — Соломона позволили компакт-дискам воспроизводить музыку с царапинами?
В стандарте CD-DA используется схема CIRC, сочетающая два кода Рида — Соломона с временным перемежением (чередованием) байтов по дорожке. Благодаря этому физическая царапина на поверхности пластика распадается при декодировании на множество мелких одиночных выпадений в разных блоках, которые легко восстанавливаются математически.
Почему в современных 5G-сетях и SSD рядом с классическими кодами используют LDPC и полярные коды?
При очень больших скоростях и крайне слабом сигнале итеративные LDPC-коды и полярные коды подходят вплотную к теоретическому пределу пропускной способности Шеннона, обеспечивая лучшую энергетическую эффективность на высоких частотах, тогда как коды Хэмминга (SECDED) и Рида — Соломона остаются эталоном для сверхбыстрой памяти и блочного стирающего кодирования.

Научная литература и источники

  1. Код Хэмминга — Википедия (история, матричное кодирование и декодирование, граница Хэмминга) [ru.wikipedia.org]
  2. Hamming code — Wikipedia (SECDED, IBM 7030 Stretch, ECC memory, математический формализм) [en.wikipedia.org]
  3. R. W. Hamming — Error Detecting and Error Correcting Codes // Bell System Technical Journal, April 1950 [doi.org]
  4. Reed–Solomon error correction — Wikipedia (работы И. Рида и Г. Соломона 1960 г., алгоритм Берлекэмпа — Мэсси, «Вояджер», CD) [en.wikipedia.org]
  5. David J. C. MacKay — Information Theory, Inference, and Learning Algorithms (Cambridge University Press) [www.inference.phy.cam.ac.uk]