Хэмминг, 1950: три проверочных бита для исправления одной ошибки

Статья написана и переведена системой ИИ на основе указанных источников с автоматизированными проверками по редакционной методике News.

Концептуальная обложка создана ИИ: структурированные проверки упорядочивают нарушенный поток; это не буквальная схема и не доказательство неограниченной коррекции.

1. Надёжность благодаря структурированной избыточности

В апреле 1950 года Ричард Хэмминг опубликовал «Error Detecting and Error Correcting Codes» в Bell System Technical Journal. Задача была практической: обнаружение сбоя при вычислении без оператора могло остановить работу, а определение его места и исправление — позволить продолжить её. Статья даёт конкретные двоичные конструкции, а не обещает восстановление после любого повреждения. [1,2]

Новшество — сделать избыточность информативной. Троекратная передача каждого из четырёх битов требует двенадцати переданных битов. Код Хэмминга использует семь, защищая те же четыре бита данных от любого одиночного переворачивания в блоке. Это разные способы организации избыточности, а не доказательство оптимальности для всех каналов. Сжатие устраняет избыточность; коррекция ошибок добавляет её в управляемой форме.

2. Семь позиций, три вопроса

Пронумеруем позиции от 1 до 7. Позиции 1, 2 и 4 содержат проверочные биты, а 3, 5, 6 и 7 — данные d₁, d₂, d₃ и d₄. Символ ⊕ означает исключающее ИЛИ, сложение по модулю 2: 1 ⊕ 1 = 0. Следующие уравнения задают чётную парность. Индексы p обозначают позиции, а не порядок проверок. [1, §3]

$p_1=d_1\oplus d_2\oplus d_4$p1​=d1​⊕d2​⊕d4​

$p_2=d_1\oplus d_3\oplus d_4$p2​=d1​⊕d3​⊕d4​

$p_4=d_2\oplus d_3\oplus d_4$p4​=d2​⊕d3​⊕d4​

Приёмник проверяет {1,3,5,7}, {2,3,6,7} и {4,5,6,7}. Нарушенная проверка даёт бит синдрома 1, выполненная — 0. Обозначим их s₁, s₂ и s₄. При условии не более одного перевёрнутого бита его позиция j равна:

$j=s_1+2s_2+4s_4$j=s1​+2s2​+4s4​

Нулевой синдром означает отсутствие ошибки только при этом допущении; это не универсальное подтверждение целостности.

3. Исправление, которое можно воспроизвести

Возьмём данные 1010. Получаем p₁ = 1, p₂ = 0 и p₄ = 1. Передаваемое слово, читаемое слева направо в порядке позиций, — 1011010. Если перевернуть бит 6, приёмник получит 1011000. Первая проверка чётная, вторая и третья нечётные. Поэтому (s₁,s₂,s₄) = (0,1,1), а j = 0 + 2 + 4 = 6. Перевернём бит 6 обратно и прочтём позиции 3,5,6,7: данные 1010 восстановлены.

Это редакционный расчёт, не экспериментальное измерение.

Научная схема создана кодом; точные битовые строки, не экспериментальные данные.

Процедура исправляет и ошибку проверочного бита. Предполагаются известные границы блока и позиции; вставка или удаление бита относятся к другой модели ошибок.

4. Почему конструкция работает

У трёх двоичных проверок восемь исходов: ровно столько, сколько нужно для семи позиций одиночной ошибки и случая без ошибки. В общем случае двоичному коду с r проверочными битами и общей длиной n нужны как минимум n + 1 различных синдромов для исправления одной инверсии:

$2^r\ge n+1$2r≥n+1

Конструкция достигает этого числа при n = 2ʳ − 1 и k = n − r битах данных. При r = 3 получаем n = 7 и k = 4. Минимальное расстояние Хэмминга — наименьшее число различающихся позиций между допустимыми словами — равно 3. Принятое слово не может отличаться одним битом сразу от двух допустимых слов: расстояние между ними тогда было бы не более 2.

Есть 16 допустимых слов, у каждого семь соседей с одной инверсией. Вместе с самими словами эти непересекающиеся множества заполняют все 128 вариантов: 16 × 8 = 128. «Совершенный» описывает эту упаковку, а не безошибочность при любом шуме. [1, §§5,7]

5. Ловушка двух ошибок

Две инверсии всегда дают ненулевой синдром: детектор, лишь отмечающий недопустимые слова, обнаружит их. Но декодер, трактующий любой ненулевой синдром как одиночную ошибку, может ошибиться при исправлении. Инверсии позиций 2 и 5 дают тот же синдром, что инверсия позиции 7. Исправление бита 7 оставит три неверных бита и другое допустимое слово.

Добавление восьмого бита для общей чётной парности повышает минимальное расстояние до 4. Расширенный код позволяет исправлять одну ошибку и обнаруживать две: SECDED. Решения ниже предполагают не более двух инверсий; q — парность всех восьми принятых битов. [1, §4]

Три и более ошибки вне гарантии. Некоторые из них SECDED-декодер может исправить неверно; обнаружение двойных ошибок не означает диагностику любого более крупного сбоя.

6. Численный выигрыш при явных допущениях

Пусть каждый передаваемый бит независимо переворачивается с вероятностью p = 0,01, одинаковой для 0 и 1. Кодирование и декодирование идеальны, границы блоков известны. Для семибитного кода с описанным декодером восстановленное четырёхбитное сообщение неверно тогда и только тогда, когда произошло не менее двух инверсий:

$\begin{aligned} P_{\rm fail}&=1-(1-p)^7\\ &\quad-7p(1-p)^6. \end{aligned}$Pfail​​=1−(1−p)7−7p(1−p)6.​

Результат — около 0,002031, или 0,2031% блоков. Для четырёх битов без кодирования: 1 − (1 − p)⁴ = 0,039404, то есть 3,9404% сообщений с ошибкой. Это вероятности ошибки сообщения, не остаточные вероятности ошибки отдельного бита и не измеренная производительность устройства.

Цена — три дополнительных бита на четыре бита данных: на 75% больше переданных битов и скорость кода 4/7 ≈ 0,5714 бита данных на переданный бит. Сравнение фиксирует p, но не одновременно полосу, время передачи и энергию на сообщение.

7. Что результат гарантирует и чего не гарантирует

Долговременный вклад — конструктивная связь алгебры и надёжности: разнести допустимые слова, вычислить компактные проверки и локализовать ограниченный сбой. Семибитный случай допускает полный перебор. Для этой статьи проверены все 16 сообщений и 128 случаев без ошибки либо с одной ошибкой, а также 448 случаев двух ошибок расширенного кода.

Код не исправляет произвольные пакеты ошибок, повреждённое ПО, злонамеренные изменения или потерю синхронизации. Реальная система должна согласовать код с моделью сбоев и защитить кодер, декодер и окружающую логику. Статья Хэмминга не содержит измерений современного оборудования; наш численный пример отделён от таких утверждений. Он дополняет пределы связи Шеннона конкретной конечной конструкцией, а не универсальным решением, достигающим пропускной способности.

Методика News для этой статьи

Опорная редакция: HAMMING-EN-1. Первичная статья 1950 года прочитана полностью по архивному скану и OCR; конструкция и случаи SECDED дополнительно сверены со сканами страниц. Запись издателя подтверждает библиографическую дату. Конспект MIT использован для сравнения современных обозначений. Расчёты и конечные проверки выполнены воспроизводимым скриптом. Текст и семь переводов созданы ИИ; это не независимая экспертиза и не проверка человеком. Локализованная схема создана кодом. Обложка — концептуальная иллюстрация ИИ, не фотография, прибор или график измерений.

Источники

[1] R. W. Hamming — Error Detecting and Error Correcting Codes — DOI: 10.1002/j.1538-7305.1950.tb00463.x.

[2] Nokia Bell Labs — Error Detecting and Error Correcting Codes.

[3] MIT 6.02 — Coping with Bit Errors using Error Correction Codes.