Как работает код Хэмминга?

Код Хэмминга работает в два этапа: habr.com spravochnick.ru

1. Первая часть кодирует исходное сообщение, вставляя в него в определённых местах контрольные биты, вычисленные особым образом. habr.com spravochnick.ru
2. Вторая часть получает входящее сообщение и заново вычисляет контрольные биты (по тому же алгоритму, что и первая часть). habr.com spravochnick.ru

Если все вновь вычисленные контрольные биты совпадают с полученными, то сообщение получено без ошибок. habr.com В противном случае выводится сообщение об ошибке и при возможности ошибка исправляется. habr.com

Пример работы кода Хэмминга: допустим, нужно передать сообщение «habr» без ошибок. habr.com Для этого исходное сообщение представляют в бинарном виде и делят на блоки по 16 бит, которые кодируют отдельно друг от друга. habr.com Затем в строго определённых местах (позиции с номерами, равными степеням двойки) вставляют контрольные биты. habr.com После этого вычисляют значение каждого контрольного бита: смотрят, сколько среди контролируемых им битов единиц, и если число чётное, то ставят ноль, в противном случае — единицу. habr.com

Когда закодированное сообщение приходит с ошибкой, во второй части алгоритма заново вычисляют все контрольные биты и сравнивают их с полученными. habr.com Сложив номера позиций неправильных контрольных бит, получают позицию ошибочного бита. habr.com Затем инвертируют его и отбрасывают контрольные биты, получая исходное сообщение без ошибок. habr.com