Bell Labs, 1947
Ричард Хэмминг присоединился к Bell Telephone Laboratories в 1946 году. Релейные компьютеры там работали только в будни, когда техники могли перезапустить их после ошибок. По выходным машины останавливались при любом сбое — оставляя задачи в очереди до понедельника.
Хэмминг был в ярости. 'Если машина может обнаружить ошибку,' думал он, 'почему она не может её найти и исправить?' Это разочарование, в сочетании с глубоким знанием двоичной арифметики и проверок чётности, создало предпосылки.
Первое озарение: коды прямоугольной формы
Первая идея Хэмминга: расположить биты сообщения в прямоугольнике m×n, добавить проверку чётности к каждой строке и каждому столбцу. Одна ошибка даёт ровно одну неудачную проверку строки и одну неудачную проверку столбца. Их пересечение указывает позицию ошибки.
Коэффициент избыточности: (m+1)(n+1) / mn. Анализ показывает, что квадрат минимизирует это при фиксированном размере сообщения. Но по мере роста m и n вероятность двойной ошибки увеличивается — инженерное решение без универсального ответа.
Минимизация избыточности прямоугольной формы
Прямоугольник 4×4 содержит 16 бит сообщения с 4 проверками строк и 4 проверками столбцов, плюс 1 бит чётности углов = 9 контрольных бит на 16 бит сообщения.
Коэффициент избыточности: (m+1)(n+1) / mn = 25/16 ≈ 1,56.
Для прямоугольника 10×10: 100 бит сообщения, 121 всего бит, избыточность ≈ 1,21.
Синдром как двоичное число
Через несколько недель после озарения о прямоугольном коде Хэмминг ехал в Нью-Йорк через фермы Нью-Джерси, мысленно повторяя свои успехи. К нему пришла идея треугольного кода — лучшая избыточность. Потом куб. Потом 4-мерный, 5-мерный...
Каждое дополнительное измерение улучшало избыточность. Гиперкуб со стороной 2 в n измерениях использует только n+1 проверок чётности для 2^n вершин. Но было ли это оптимальным?
Аргумент подсчёта
n+1 бит синдрома создают синдром: (n+1)-битное двоичное число. Этот синдром должен определить 2^n + 1 различных исходов: каждую из 2^n позиций ошибки, плюс специальный исход 'нет ошибки'.
2^(n+1) = 2·2^n — почти достаточно. Недостаток в коэффициент 2. Хэмминг отложил проблему.
Ключевое озарение
Позже Хэмминг вернулся с новой идеей: использовать сам синдром как двоичное число, указывающее позицию ошибки. Позиция 1 = двоичный 001, позиция 2 = двоичный 010, позиция 3 = двоичный 011 и т. д. Зарезервировать все нули для 'нет ошибки'.
Это преобразует синдром из выхода проверок чётности в адрес. Проверки чётности спроектированы так, чтобы выдать ровно правильный адрес при переворачивании любого одного бита.
Проектирование кода (7,4)
Для 7-битного кода (3 бита синдрома, 4 бита сообщения) позиции 1–7 в двоичной системе: 001, 010, 011, 100, 101, 110, 111.
Проверка чётности 1 охватывает позиции, где бит 0 = 1: позиции 1, 3, 5, 7.
Проверка чётности 2 охватывает позиции, где бит 1 = 1: позиции 2, 3, 6, 7.
Проверка чётности 3 охватывает позиции, где бит 2 = 1: позиции 4, 5, 6, 7.
Биты синдрома занимают позиции степеней двойки: 1, 2, 4. Биты сообщения занимают остальное: 3, 5, 6, 7.
Если бит 6 переворачивается, проверки чётности 2 и 3 не срабатывают (110 в двоичной = 6). Синдром читает 110 = 6. Переворачиваем позицию 6. Готово.
Исправление одной ошибки, обнаружение двойной
Код (7,4) Хэмминга исправляет одиночные ошибки. Но что если два бита переворачиваются? Без дополнительной защиты декодер применяет правило синдрома и 'исправляет' кодовое слово на неправильное сообщение — тихая ошибка исправления.
SECDED: ещё один бит чётности
Добавьте один бит чётности p₀, охватывающий всё кодовое слово (все 7 бит). Теперь синдром имеет 4 элемента: исходные 3 проверки плюс p₀.
``
старый синдром новый p₀ значение
000 0 правильно
000 1 ошибка только в p₀
xxx 1 одиночная ошибка, старый синдром указывает её
xxx 0 двойная ошибка — обозначить
``
Четыре случая исчерпывающи. Двойная ошибка переворачивает два бита: старый синдром не прочитает 000 (оба бита вместе повреждают две из его проверок), но p₀ переворачивается дважды и возвращается к 0. Паттерн xxx + 0 неошибочен.
Почему SECDED работает
Правило SECDED использует модульную структуру чётности. При чётной чётности любое одиночное переворачивание меняет p₀. Любое двойное переворачивание оставляет p₀ неизменным. Поэтому p₀ считает ошибки по модулю 2.
Геометрическая картина
Хэмминг пришёл в то же место с другого направления: аналитическая геометрия. Представьте каждую n-битную строку как вершину n-мерного гиперкуба. Одиночный переворот бита перемещает точку на одну длину ребра вдоль одной оси. Два переворота: два ребра. Метрика — расстояние Хэмминга.
Определите шар Хэмминга радиуса t вокруг кодового слова c: все точки в пределах t переворотов бита от c. Для исправления одиночной ошибки, t = 1.
Условие исправления одиночной ошибки: шары радиуса 1 вокруг каждой пары различных кодовых слов не должны перекрываться. Если они перекрываются, принятое слово в пересечении может принадлежать любому кодовому слову и декодер не срабатывает.
Это прямо переводится в минимальное расстояние: два шара радиуса 1 не перекрываются, если и только если кодовые слова находятся на расстоянии не менее 3 (d_min ≥ 3).
Код (7,4) достигает d_min = 3. Граница Хэмминга: 2^7 / (1 + 7) = 16 = 2^4. Ровно 16 кодовых слов. Совершенный код: 16 шаров радиуса 1 мозаируют {0,1}^7 без промежутков и перекрытий.
Инженерные решения
Хэмминг был явно ясен: коды исправления ошибок включают инженерные решения, а не чистую математику.
Длина сообщения: более длинные сообщения позволяют более эффективное кодирование (log n битов синдрома для n битов сообщения). Но более длинные сообщения также накапливают больше шума, повышая риск того, что двойная ошибка пройдёт как ложное одиночное исправление.
Уровень исправления против обнаружения: торговля одного исправления ошибки на два дополнительных обнаружения ошибок. Оптимальное разделение зависит от характеристик шума канала.
Ценность полевого обслуживания: по мере усложнения оборудования техники полевого обслуживания не могут диагностировать каждый отказ с первых принципов. Система самодиагностики драматически снижает требуемый уровень подготовки техников. Хэмминг назвал это одним из наиболее важных преимуществ, часто более важным, чем сырой прирост надёжности.
Стиль: удача благоволит подготовленному уму
Хэмминг завершил главу 12 прямым вызовом. Он описал открытие как требующее трёх-шести месяцев работы, в основном в нечетные моменты, выполняя свои основные задачи в Bell Labs.
Он определил три вещи, которые это сделали возможным:
1. Подготовка: глубокое знакомство с проверками чётности, двоичной арифметикой и теорией групп, до того, как появилась проблема.
2. Обзор успехов: привычное повторение прошлых решений для усвоения их стиля. Идея треугольного кода пришла к нему, пока он мысленно повторял прямоугольный код в поезде.
3. Отсутствие удовлетворения 'выглядит хорошо': он обжёгся один раз, приняв кажущуюся оптимальность. Он толкал, пока не смог доказать, что код лучший.