Статья написана и переведена системой ИИ на основе указанных источников с автоматизированными проверками по редакционной методике News.
Обновление — 7 октября 2026 года. Обложка заменена, поскольку при доступных средствах доступа не удалось восстановить её исходный файл и запись о генерации. Новое изображение получено от встроенного инструмента и визуально проверено; файл, инструкция и источники сохранены в закрытом редакционном досье. Предыдущая обложка и её неподтверждённое происхождение остаются в истории. Это иллюстрация, а не экспериментальное доказательство; основной научный результат сохранён.
Концептуальная иллюстрация, созданная ИИ: код Хэмминга (7,4) — четыре информационных и три проверочных бита, исправление одного инвертированного бита в блоке. Плитки символические, это не схема.
Перед формулами
Бит — это значение 0 или 1. Инверсия заменяет одно другим. Проверка чётности определяет, чётное или нечётное число единиц содержит группа. Например, в 101 две единицы, поэтому чётность чётная. Избыточность означает передачу дополнительных сведений, позволяющих получателю проверить данные. Здесь три перекрывающиеся проверки находят перевёрнутый бит, если в семибитном блоке он не более чем один.
Чтобы понять идею, разберите пример в разделе 3, затем вернитесь к формулам раздела 2. Для проверки используйте полную программу ниже. Спросите себя: доказывает ли успешная проверка, что ни один бит не изменился? Раздел 5 объясняет, почему ответ зависит от модели ошибок.
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]
p1=d1⊕d2⊕d4
p2=d1⊕d3⊕d4
p4=d2⊕d3⊕d4
Приёмник проверяет {1,3,5,7}, {2,3,6,7} и {4,5,6,7}. Нарушенная проверка даёт бит синдрома 1, выполненная — 0. Обозначим их s₁, s₂ и s₄. При условии не более одного перевёрнутого бита его позиция j равна:
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 различных синдромов для исправления одной инверсии:
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]
| Синдром j | Парность q | Действие при указанном допущении |
|---|---|---|
| 0 | 0 | Нет ошибки |
| 0 | 1 | Исправить бит 8 |
| ненулевой | 1 | Исправить бит j |
| ненулевой | 0 | Сообщить о двух ошибках; не исправлять |
Три и более ошибки вне гарантии. Некоторые из них SECDED-декодер может исправить неверно; обнаружение двойных ошибок не означает диагностику любого более крупного сбоя.
6. Численный выигрыш при явных допущениях
Пусть каждый передаваемый бит независимо переворачивается с вероятностью p = 0,01, одинаковой для 0 и 1. Кодирование и декодирование идеальны, границы блоков известны. Для семибитного кода с описанным декодером восстановленное четырёхбитное сообщение неверно тогда и только тогда, когда произошло не менее двух инверсий:
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 случаев двух ошибок расширенного кода.
Код не исправляет произвольные пакеты ошибок, повреждённое ПО, злонамеренные изменения или потерю синхронизации. Реальная система должна согласовать код с моделью сбоев и защитить кодер, декодер и окружающую логику. Статья Хэмминга не содержит измерений современного оборудования; наш численный пример отделён от таких утверждений. Он дополняет пределы связи Шеннона конкретной конечной конструкцией, а не универсальным решением, достигающим пропускной способности.
8. Воспроизвести конечный расчёт
Протокол HAMMING-REPRO-1. Скопируйте полный блок Python в reproduce_hamming.py и выполните python3 reproduce_hamming.py. Используется только стандартная библиотека Python, без сети, загрузки данных и начального значения генератора случайных чисел. Для этой редакции программа выполнена в CPython 3.12.14. Позиции нумеруются с 1; восьмой бит обеспечивает общую чётность. Программа перебирает все 16 сообщений, отдельно строит допустимые семибитные слова из условий чётности и сравнивает их с выходом кодера.
Ожидаемый вывод: status PASS, codewords 16, minimum_distances [3, 4]. Счётчики: 128 правильных восстановлений при нуле или одной ошибке для семи битов; 144 для восьми; 448 обнаруженных двойных ошибок расширенного кода; 336 неверных исправлений двойных ошибок семибитным декодером; 896 неверных исправлений тройных ошибок описанным восьмибитным декодером. Последние два — отрицательные контроли: они показывают ограничения, а не успешные исправления. При p = 0,01 coded_message_error приблизительно равно 0,00203104163494, uncoded_message_error — 0,03940399. Предполагаются независимые инверсии при фиксированном p, а не одинаковые энергия или полоса.
"""News HAMMING-REPRO-1: finite mathematical check, not hardware validation."""
from itertools import combinations, product
import json
import platform
def encode(data):
a, b, c, d = data
return (a ^ b ^ d, a ^ c ^ d, a, b ^ c ^ d, b, c, d)
def syndrome(word):
a, b, c, d, e, f, g = word[:7]
return (a ^ c ^ e ^ g) + 2 * (b ^ c ^ f ^ g) + 4 * (d ^ e ^ f ^ g)
def flip(word, positions):
result = list(word)
for position in positions:
result[position - 1] ^= 1
return tuple(result)
def decode7(word):
position = syndrome(word)
return flip(word, (position,)) if position else word
def decode8(word):
position, parity = syndrome(word), sum(word) % 2
if parity:
return flip(word, (position or 8,))
return None if position else word
def distance(a, b):
return sum(x != y for x, y in zip(a, b))
def require(condition, label):
if not condition:
raise RuntimeError(label)
messages = list(product((0, 1), repeat=4))
code7 = [encode(data) for data in messages]
code8 = [word + (sum(word) % 2,) for word in code7]
# Independent enumeration uses parity sums rather than the encoder equations.
groups = ((1, 3, 5, 7), (2, 3, 6, 7), (4, 5, 6, 7))
oracle = {
word for word in product((0, 1), repeat=7)
if all(sum(word[p - 1] for p in group) % 2 == 0 for group in groups)
}
require(len(set(code7)) == 16 and set(code7) == oracle, "codebook")
min7 = min(distance(a, b) for a, b in combinations(code7, 2))
min8 = min(distance(a, b) for a, b in combinations(code8, 2))
require((min7, min8) == (3, 4), "minimum distances")
counts = {"seven_zero_or_one": 0, "eight_zero_or_one": 0,
"eight_double_detected": 0, "seven_double_miscorrected": 0,
"eight_triple_miscorrected": 0}
for word in code7:
for positions in [()] + [(i,) for i in range(1, 8)]:
require(decode7(flip(word, positions)) == word, "seven-bit recovery")
counts["seven_zero_or_one"] += 1
for positions in combinations(range(1, 8), 2):
received = flip(word, positions)
require(syndrome(received) != 0, "double error detectable")
require(decode7(received) != word, "double error outside correction guarantee")
counts["seven_double_miscorrected"] += 1
for word in code8:
for positions in [()] + [(i,) for i in range(1, 9)]:
require(decode8(flip(word, positions)) == word, "eight-bit recovery")
counts["eight_zero_or_one"] += 1
for positions in combinations(range(1, 9), 2):
require(decode8(flip(word, positions)) is None, "double error must be flagged")
counts["eight_double_detected"] += 1
for positions in combinations(range(1, 9), 3):
result = decode8(flip(word, positions))
require(result is not None and result != word and result in code8,
"triple error counterexample")
counts["eight_triple_miscorrected"] += 1
require(list(counts.values()) == [128, 144, 448, 336, 896], "case counts")
require(encode((1, 0, 1, 0)) == (1, 0, 1, 1, 0, 1, 0), "worked example")
require(syndrome((1, 0, 1, 1, 0, 0, 0)) == 6, "worked syndrome")
p = 0.01
failure = 1 - (1-p)**7 - 7*p*(1-p)**6
uncoded = 1 - (1-p)**4
require(abs(failure - 0.00203104163494) < 1e-12, "probability")
print(json.dumps({"protocol": "HAMMING-REPRO-1", "python": platform.python_version(),
"codewords": len(code7), "minimum_distances": [min7, min8],
"counts": counts, "p": p, "coded_message_error": failure,
"uncoded_message_error": uncoded, "status": "PASS"}, indent=2))PASS означает успешное прохождение этих конечных математических проверок. Это не доказательство характеристик аппаратуры, устойчивости к другим моделям ошибок или независимого воспроизведения. Поле python указывает версию вашего интерпретатора и может отличаться. При RuntimeError сохраните скрипт и полный вывод и исследуйте названную проверку; частичный запуск не является валидацией.
Методика News для этой статьи
2026-10-03 — Редакция HAMMING-EN-2 добавляет последовательное введение и полный протокол воспроизведения. Научный текст и программно построенная схема сохранены из HAMMING-EN-1. При обновлении конструкция и ограничения повторно сверены со статьёй 1950 года и разделами 5.6–5.7 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.