Чётность обнаруживает, но не находит

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

Пересекающееся покрытие

Каждый бит чётности покрывает своё подмножество позиций, выбранное так, чтобы каждый бит данных в итоге проверялся уникальной комбинацией битов чётности. В стандартной схеме бит чётности p1 покрывает все позиции, у которых установлен 0-й бит двоичного индекса, p2 — все позиции с установленным 1-м битом, p4 — со 2-м, и так далее — каждый бит данных проверяется ровно теми битами чётности, что соответствуют единичным битам номера его собственной позиции.

Синдром указывает на виновника

При приёме каждый бит чётности пересчитывается тем же способом и берётся XOR с переданным значением. Собрав результирующие биты несовпадения вместе (несовпадение p1 как бит 0, p2 — как бит 1, и так далее), получаем синдром — двоичный номер позиции того самого перевёрнутого бита, или нули, если ничего не перевернулось. Небольшой декодер превращает этот синдром прямо в сигнал «переверни этот бит» с одной активной линией.

Попробуйте сами

Соберите вентили XOR для проверки чётности небольшого слова с кодом Хэмминга в редакторе схем, переверните ровно один бит данных переключателем INPUT и убедитесь, что получившиеся биты синдрома — считанные с нескольких элементов OUTPUT — складываются в двоичный номер позиции того бита, который вы перевернули.