В предыдущей главе были рассмотрены основы эффективного кодирования данных, задача которого — представить подлежащие передаче сообщения в максимально компактной форме. Целью помехоустойчивого кодирования является такое представление сообщений, которое бы предотвращало или парировало искажения, возникающие при передаче. На практике ситуации с естественным или намеренным изменением информации встречаются чрезвычайно часто.
Для начала рассмотрим задачу о разведчиках, которая поможет изучить основные подходы и алгоритмы помехоустойчивого кодирования.
8 Задача о разведчиках[1]. Разведывательный отряд в составе командира и восьми бойцов высадился на вражеском острове вблизи перекрестка, откуда исходят дороги по четырем направлениям. Задача отряда — обнаружить секретный объект противника. Об объекте известно, что он расположен на одной из четырех дорог в часе ходьбы от перекрестка. Командиру известно, что двое из его бойцов — предатели, которые будут стараться обмануть командира, чтобы не допустить обнаружения объекта. Необходимо спланировать действия командира по обнаружению объекта и предателей.
К этой задаче мы будет обращаться многократно. Для указания на то, что рассматривается задача о разведчиках, будем использовать символ о .
При передаче информации по каналу связи с помехами в принятых данных могут возникать ошибки. Если такие ошибки имеют небольшую величину или возникают достаточно редко, информация может быть использована потребителем. При большом числе ошибок полученной информацией пользоваться нельзя.
Ранее уже говорилось о понятии помехоустойчивости (способности информационных систем противостоять воздействию помех). Для реализации принципа помехоустойчивости информационных систем может быть использовано помехоустойчивое кодирование.
Помехоустойчивыми (корректирующими) называются коды, позволяющие обнаружить и при необходимости исправить ошибки в принятом сообщении.
Возможность использования кодирования для уменьшения числа ошибок в канале была теоретически показана К. Шенноном в 1948 г. в его работе «Математическая теория связи». Теперь это утверждение принято именовать второй теоремой Шеннона (см. параграф 3.4).
- [1] Автор сюжета задачи — К. Кноп. (см. Кноп К. О разведчиках и кодах Хем-минга // Компьютера. 1997. № 6).
