Теория по кодам Хемминга

1. Постановка задачи и реализация

Задача. Алиса хочет научиться сообщать любое число от 1 до N Бобу с помощью сообщения из "0" и "1" длины а) 7, б) 15. Из-за помех один из символов сообщения может отправиться неверно (вместо "0" отправится "1" или вместо "1" отправится "0"). Как Алисе и Бобу договориться о том, какие сообщения будет отправлять Алиса, в зависимости от числа К, которое она хочет отправить? Число N при этом должно быть как можно больше.

Некоторые размышления. Докажем, что N ≤ а) 2⁴, б) 2¹¹.
Каждое сообщение, которое соответствует некоторому числу K, образует группу искажённых сообщений из а) 8, б) 16 последовательностей "0" и "1" (включая "отсутствие искажения").
При этом для каждых различных K и L группы искажённых сообщений не имеют общих последовательностей (иначе Боб не сможет определить исходное число).
Тогда а) N ≤ 2⁷ : 2³ = 2⁴, аналогично б) N ≤ 2¹⁵ : 2⁴ = 2¹¹. (Где 2⁷ и 2¹⁵ - количество всех возможных сообщений).

Оказывается, что можно построить договорённость, в которой N = а) 2⁴, б) 2¹¹ с помощью так называемых кодов Хемминга.

Реализация №1. Простая для понимания, сложная для обобщения. На примере пункта а).
Пусть первые 4 бита (символа) будут кодировать число, которое мы хотим отправить. Будем записывать число в двоичной системе счисления, поставив в начале нули, если число слишком маленькое. К примеру: будем кодировать число 5 последовательностью "0101" (0*8 + 1*4 + 0*2 + 1*1 = 5).
Последующие 3 бита будем использовать как "резервные" и будем хранить в них вспомогательную информацию о первых 4.
Сопоставим битам комбинации из букв "ABC" следующим образом: первым 4 битам сопоставим комбинации "ABC", "AB", "AC", "BC", комбинации "A", "B", "C" - последним 3 вспомогательным.
Тогда запишем в первый резервный бит такую цифру, чтобы количество единиц в битах с буквой "A" (то есть в первых трёх и первом резервном) было чётно. Продолжая пример при K = 5, в первом резервном бите будет "1", т.к. среди 0101 нечётное количество единиц. Аналогично, во втором резервном бите запишем такую цифру, чтобы количество единиц в битах с буквой "B" было чётно. Ровно также сделаем для третьего резервного бита и буквы "С". Снова возвращаясь к примеру, во втором резервном бите будет "0", т.к. среди 0101 чётное количество единиц. Аналогично в третьем резервном бите будет "1" (смотрим на 0101). В итоге получаем "0101101".

Поймём, что произойдёт с чётностью единиц в битах с буквой "А", если сообщение искажается: если изменённый бит содержал букву "А", то чётность изменится, иначе чётность останется прежней. Таким образом, к примеру, если изменится бит с буквами "AC", то чётность количества единиц в битах и с "А", и с "С" изменится, а чётность количества единиц в битах с "B" останется прежней.
Поэтому, из-за того, что у каждого бита своя уникальная комбинация, то по буквам, у которых количество единиц нечётно, мы сможем однозначно определить, где случилась ошибка, и, таким образом, сможем её исправить.

Теперь как Бобу нужно расшифровывать код (пусть ему пришёл код "0111101"):
Он проверяет чётность единиц по буквам: подсчитав количество единиц в битах в следующих символах:
"0111101" - соответствующие первому вспомогательному биту (буква "А")
"0111101" - соответствующие второму вспомогательному биту (буква "B")
"0111101" - соответствующие третьему (буква "C")
В данном примере в первой и третьей группе "неправильное" количество единиц, поэтому ошибка была в том символе, которому соответствует комбинация "AC", то есть в третьем бите. Откуда изначальное сообщение было "0101101".
По изначальному сообщению уже легко восстановить K.

Реализация №2. Сложнее для понимания и реализации, но куда проще для обобщения. На примере пункта б).
Пронумеруем наши 15 бит числами от 1 до 15, и каждое число от 1 до 15 представим в двоичной системе. Заметим, что номеру бита в двоичной системе можно сопоставить неупорядоченную комбинацию из букв "ABCD", а именно - если i-тая цифра равна 0, то мы не берём i-тую букву, если же цифра равна 1, то берём i-тую букву. К примеру, номеру 5 (представимый в виде 0101₂ ) сопоставляется комбинация "BD". Тогда биты с номерами 1, 2, 4 и 8 будут резервными (т.к. в их комбинациях лишь 1 буква), остальные 11 - основные, и в них мы запишем информацию.

Попробуем зашифровать число 255. В двоичной записи записывается как 00011111111. Тогда запишем в 3, 5, 6, 7, 9, 10 ... 15-тые биты цифры из двоичной записи, получится _ _0_001_1111111.
Тогда в группе с первым вспомогательным битом будут  _ _0_001_1111111, то есть все нечётные индексы, откуда получаем 1_0_001_1111111.
Аналогично: 1_0_001_1111111 во второй группе, откуда 110_001_1111111.
Аналогично: 110_001_1111111 в третьей группе, откуда 1101001_1111111.
Аналогично: 1101001_1111111 в четвёртой группе, откуда 110100111111111.

Напомню, что в языках программирования существуют побитовые операции, которые взаимодействуют непосредственно с двоичной записью числа. Вот некоторые из них:
& - побитовое И, к примеру 5 & 9 = 0101₂ & 1001₂ = 0001₂ = 1
| - побитовое ИЛИ, к примеру 5 | 9 = 0101₂ | 1001₂ = 1101₂ = 13
^ - побитовое ИСКЛЮЧАЮЩЕЕ ИЛИ (он же XOR), к примеру 5 ^ 9 = 0101₂ ^ 1001₂ = 1100₂ = 12
<< - побитовый сдвиг влево на правый аргумент, к примеру 5 << 2 = 0101₂ << 2 = 010100₂ = 20. На самом деле является синонимом домножения на степень двойки.
>> - побитовый сдвиг вправо на правый аргумент, к примеру 13 >> 2 = 1101₂ >> 2 = 11₂ = 3. На самом деле является синонимом деления без остатка на степень двойки.
С помощью этих операций можно делать разные интересные вещи, к примеру, "вытащить" из числа X N-тый справа бит с помощью (X >> (N-1)) & 1. То есть (5 >> 2) & 1 = 1, т.к. третий бит справа равен 1. (Вспоминаем, что 5 = 0101₂).
Будьте аккуратнее со скобками (точнее их отсутствием), т.к. приоритеты операций могут быть не такими очевидными, как вы думаете.