ГЛАВА 1. ПРОБЛЕМА КОДИРОВАНИЯ

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

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

1.1. Канал связи

Принципиальная схема цифровой системы связи изображена на рис. 1.1 [59]. Эта же самая модель описывает и систему хранения информации, если среду, в которой хранится информация, рассматривать как канал. Типичным каналом для передачи информации является телефонный канал. Типичным устройством для хранения информации является магнитофон, включая записывающую и считывающую головки.

Рис. 1.1. Блок-схема общей системы передачи или хранения информации.

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

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

Система, изображенная на рис. 1.1, является слишком общей для того, чтобы ею было удобно пользоваться при теоретическом анализе. Общая теория кодирования указывает, что канал связи обладает определенной пропускной способностью, что типичные источники обладают определенной скоростью создания информации и что в том случае, когда скорость создания информации источником меньше пропускной способности канала, можно осуществить кодирование и декодирование так, чтобы вероятность ошибочного декодирования была произвольно малой [36, 85, 87, 117, 119].

Рис. 1.2, Блок-схема типичной системы передачи или хранения информации.

Таким образом, хотя остается надежда на будущее, пока что теория дает не более чем смутные указания на то, как следует конструировать систему передачи информации.

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

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

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

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