1 –> 0001; 5 –> 0101;   9 –> 1001;   13 –> 1101;

2 –> 0010; 6 –> 0110;   10 –> 1010;  14 –> 1110;

3 –> 0011; 7 –> 0111;   11 –> 1011;  15 –> 1111;

Это обыкновенный двоичный код, который можно встретить в некоторых однокристаллках, вмещающий в свои 4 бита 16 символов (т.е. с его помощью можно закодировать 16 букв алфавита). Как нетрудно убедиться, два любых символа отличаются по меньшей мере на один бит, следовательно, расстояние Хемминга для такого кода равно единице (что условно обозначает как d = 1).

А вот другой 4-битный код:

Листинг 2. Пример 4-битного кода с расстоянием Хемминга, равным двум, способного обнаруживать одиночные ошибки.

0 –> 0000; 4 –> 1001;

1 –> 0011; 5 –> 1010;

2 –> 0101; 6 –> 1100;

3 –> 0110; 7 –> 1111;

На этот раз два произвольных символа отличаются как минимум в двух позициях, за счет чего информационная емкость такого кода сократилась с 16 до 8 символов. «Постойте-постойте! – воскликнет иной читатель. – Что это за бред? Куда делась комбинация 0001 или 0010, например?». Нет, это не бред, и указанных комбинаций бит в данном коде действительно нет, точнее, они есть, но объявлены запрещенными. Благодаря этому обстоятельству наш подопечный код способен обнаруживать любые одиночные ошибки. Возьмем, например, символ «1010» и исказим в нем произвольный бит (но только один!). Пусть это будет второй слева бит, тогда искаженный символ станет выглядеть так: «1110». Поскольку комбинация «1110» является запрещенной, декодер может засвидетельствовать наличие ошибки. Увы, только засвидетельствовать, но не исправить, т.к. для исправления даже одного-единственного сбойного байта требуется увеличить расстояние Хемминга как минимум до трех. Поскольку 4-битный код с d = 3 способен вмещать в себя лишь два различных символа, то он крайне ненагляден и потому нам лучше выбрать код с большей разрядностью. Хорошо, пусть это будет 10-битный код с d = 5.

Листинг 3. Пример 10-битного кода, с расстоянием Хемминга, равным пяти, способного обнаруживать 4-битные ошибки, а исправлять 2-битные.

0000000000 0000011111   1111100000   1111111111

Возьмем, к примеру, символ «0000011111» и искорежим два любых бита, получив в итоге что-то наподобие: «0100110111». Поскольку такая комбинация является запрещенной, декодер понимает, что произошла ошибка. Достаточно очевидно, что если количество сбойных бит меньше расстояния Хемминга хотя бы наполовину, то декодер может гарантированно восстановить исходный символ. Действительно, если между двумя любыми разрешенными символами существует не менее пяти различий, то искажение двух бит всякого такого символа приведет к образованию нового символа (обозначим его k), причем расстояние Хемминга между k и оригинальным символом равно числу непосредственно искаженных бит (т.е. в нашем случае двум), а расстояние до ближайшего соседнего символа равно: d – k (т.е. в нашем случае трем). Другими словами, пока d – k > k декодер может гарантированно восстановить искаженный символ. В тех случаях, когда d > k > d – k, успешное восстановление уже не гарантируется, но при удачном стечении обстоятельств все-таки оказывается в принципе возможным.