Глава 1. КОДИРОВАНИЕ И СВЯЗЬ

1. Введение

Структура человеческого языка достаточно сложна и позволяет поэтому вести разговор, не взирая на большое количество шумов и искажений. Осмысленная передача информации может продолжаться даже тогда, когда утеряна значительная часть слогов. В этом смысле языки можно считать примерами высоко эффективных исправляющих ошибки кодов, оказавшихся в результате эволюции хорошо приспособленными к нуждам человека.

С другой стороны, когда непереработанная информация передается непосредственно от машины к машине без вмешательства человека, ошибочный прием одного-единственного элемента сигнала может полностью изменить смысл сообщения. Поскольку в электрических цепях всегда присутствует шум, оказывается необходимым искусственный язык, т. е. код. В идеале коды должны позволять вести эффективную передачу информации с любой требуемой степенью надежности. И, конечно, способы их реализации должны согласовываться с возможностями кодирования и декодирования при помощи существующих математических устройств.

Что коды, удовлетворяющие первому требованию, существуют, было известно со времени появления основополагающей работы Шеннона [18]; не были ясны способы реального проведения такого кодирования. В настоящей монографии исследуется концепция, которая поможет разрешить эту проблему во многих практически важных ситуациях.

Эта концепция, называемая последовательным декодированием, отличается от концепций большинства работ по теории кодирования тем, что в своей основе носит вероятностный, а не алгебраический характер. Хотя

оба эти подхода допускают обобщения на дискретные коды с возможными символами по многим причинам кажется, что вероятностный подход в случае непрерывных каналов имеет преимущества.

Для того чтобы упростить математические построения, мы развиваем здесь подробно концепцию последовательного декодирования лишь для случая двоичного симметричного канала. Во многих отношениях этот канал является простейшей нетривиальной моделью реальных физических каналов. Более точные модели кратко рассматриваются в последней главе.