Возвращаясь к нашему символу «0000011111», давайте на этот раз исказим не два бита, а четыре: «0100110101» и попробуем его восстановить. Изобразим процесс восстановления графически:

Листинг 4. Восстановление 4-битной ошибки.

0000000000 0000011111   1111100000   1111111111

0100110101 0100110101   0100110101   0100110101

----------  ----------  ----------   ----------

5 отличий   4 отличия   6 отличий    5 отличий

Грубо говоря, обнаружив ошибку, декодер последовательно сличает искаженный символ со всеми разрешенными символами алфавита, стремясь найти символ наиболее «похожий» на искаженный. Точнее, символ с наименьшим числом различий, а еще точнее, символ, отличающийся от искаженного не более чем в (d – 1) позициях. Легко видеть, что в данном случае нам повезло, и восстановленный символ совпал с истинным. Однако если бы четыре искаженных бита распределились бы так: «0111111111», то декодер принял бы этот символ за «1111111111» и восстановление оказалось бы неверным.

Таким образом, исправляющая способность кода определяется по следующей формуле: для обнаружения r ошибок расстояние Хемминга должно быть больше или равно r, а для коррекции r ошибок расстояние Хемминга должно быть по крайней мере на единицу больше удвоенного количества r.

Листинг 5. Корректирующие способности простого кода Хемминга.

обнаружение ошибок:     d >= r

исправление ошибок:     d > 2r

информационная емкость: 2^n/d

Теоретически количество обнаруживаемых ошибок неограничено, практически же информационная емкость кодовых слов стремительно тает с ростом d. Допустим, у нас есть 24 байта данных, и мы хотели бы исправлять до двух ошибок на каждый такой блок. Тогда нам придется добавить к этому блоку еще 49 байт, в результате чего реальная информационная емкость блока сократится всего… до 30%! Хорошенькая перспектива, не так ли? Столь плачевный результат объясняется тем, что биты кодового слова изолированы друг от друга и изменение одного из них никак не сказывается на окружающих. А что если…

Пусть все биты, номера которых есть степень двойки, станут играть роль контрольных битов, а оставшиеся и будут обычными («информационными») битами сообщения. Каждый контрольный бит должен отвечать за четность суммы[2] некоторой принадлежащей ему группы битов, причем один и тот же информационный бит может относиться к различным группам. Тогда один информационный бит сможет влиять на несколько контрольных и потому информационная емкость слова значительно (можно даже сказать, чудовищно) возрастет. Остается только выбрать наиболее оптимальное разделение сфер влияния.