Спирина, М.С. Дискретная математика

Рис. 6.9. Контроль по четности: а — в — представление исходной информации в виде кругов Эйлера; г — изме­ нение исходной информации в 4-м разряде; д, ж — проверка на четность; е — изменение исходной информации в 3-м разряде область на кругах Эйлера и, следовательно, возможность ее устра­ нения. Пусть, например, ошибка произошла в третьем разряде, т.е. получено кодовое слово 1001 (рис. 6.9, ё). Проверка кругов Эйлера на четность показывает, что нечетны все три круга А, В и С. Но на пересечении всех трех кругов лежит единственная об­ ласть 3 (рис. 6.9, ж), что и соответствует фактической ошибке. В случае возникновения большого числа ошибок исправление одной из них может повлечь за собой появление новых. Для того чтобы уменьшить такие последствия, вводится еще одна — вне­ шняя область, которая также заполняется битом четности. Значе­ ние этого бита выбирается так, чтобы полное число единиц на диаграмме было четным. Код Хемминга в таком случае дает воз­ можность лишь обнаружить, но не устранить ошибки. Код Хем­ минга и его модификации легко реализуются в ЭВМ. Поиски надежных шифров, как это ни странно, привели к использованию одного из известнейших и глубоко изученных воп­ росов математики — делению с остатком. Этот раздел математики и теории чисел был детально разрабо­ тан много лет назад применительно к другим проблемам. В насто­ ящее время он широко используется при разработке новых мето­ дов кодирования сообщений. Далее мы даем подробное изложение этого вопроса в связи с его актуальностью в новых криптографических исследованиях. 326