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.
Біти парності займають позиції степенів 2: 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 біт повідомлення). Але довші повідомлення також накопичують більше шуму, піднімаючи ризик подвійної помилки, що ковзає через як хибна одна коригування.
Рівень коригування vs. виявлення: торгування одною коригуванням помилки для двох додаткових виявлень помилок. Оптимальна розділення залежить від характеристик шуму каналу.
Цінність для польового обслуговування: як обладнання стає комплекснішим, технічні фахівці не можуть діагностувати кожну відмову з перших принципів. Самодіагностична система драматично зменшує кваліфікацію, необхідну для обслуговування. Хеммінг назвав це одним з найважливіших переваг, часто більш важливе, ніж сам приріст надійності.
Стиль: удача посміхається підготованому розуму
Хеммінг закрив розділ 12 з прямим викликом. Він описав виявлення як вимагаючи трьох до шести місяців роботи, здебільшого в непарні моменти під час виконання своїх основних обов'язків у Bell Labs.
Він визначив три речі, які зробили це можливим:
1. Підготовка: глибока знайомість з перевірками парності, двійковою арифметикою, & теорією груп, перед тим як проблема з'явилась.
2. Переглядання успіхів: звичка переглядати минулі рішення, щоб інтеріоризувати їх стиль. Трикутний код спав йому на думку під час розумово переглядання прямокутного коду на комуті.
3. Нез встяганням за 'виглядає добре': він обпалив свої пальці раз, прийнявши очевидну оптимальність. Він тиснув, доки не міг довести, що код найкращий.