1.5. Кодирование алфавита источника

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

В качестве названий этих двух состояний принято использовать символы 0 и 1, однако годятся любые два различных символа (знака), например, крестик и нолик. Иногда полезно рассматривать 0 и 1 не как числа, а как пару произвольных символов.

Рассмотрим сначала задачу представления различных символов алфавита источника. Если дана пара двоичных (с двумя состояниями) устройств (цифр), их можно представить четырьмя различными состояниями: 00, 01, 10, 11. Для трех двоичных цифр

получаем различных состояний: Для системы, имеющей двоичных цифр, обычно называемых битами, общее число различных состояний равно это легко получить, применив элементарные комбинаторные рассуждения. Вообще, если есть различных устройств, первое из которых имеет состояний, второе состояний, состояний, то общее число состояний, очевидно, равно произведению Если, например, то можно представить различных объектов (состояний). Это число равно числу различных символов источника, которые можно представить, если интересоваться только числом различных состояний. В гл. 4 указывается, как принимать во внимание вероятности появления различных символов. Сейчас рассматривается только число различных состояний — это эквивалентно тому, что вероятности появления всех символов считаются равными.

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

Люди часто приписывают последовательностям из нулей и единиц некоторый смысл, например в коде ASCII (см. табл. 1.7.1). Однако ЭВМ (или система передачи сигналов) рассматривает их лишь как последовательности из нулей и единиц. Цифровая вычислительная машина обрабатывает двоичные последовательности символов; смысл этим последовательностям придает пользователь (или, быть может, устройства ввода и вывода). ЭВМ просто комбинирует нули и единицы в соответствии со своей конструкцией и введенной в нее программой. Логические схемы ЭВМ не чувствительны к смыслу, который приписывается символам; это же справедливо для системы передачи сигналов.

Именно поэтому теория информации не рассматривает смысла сообщений, и это дает ей возможность понять, как аппаратура преобразует сообщения; теория дает метод исследования обработки информации.

В типичных случаях, как показано в гл. 2 и 3, кодирование сообщений для передачи по каналу увеличивает избыточность (точные определения даются в дальнейшем). Кодирование для источника (оно упоминалось в конце разд. 1.3) обычно уменьшает избыточность, что показано в гл. 4 и 5.

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

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

Задачи

1.5.1. Найдите число различных автомобильных номеров вида «цифра, цифра, цифра, буква, буква, буква».

1.5.2. Сколько команд может быть у ЭВМ, если каждая команда состоит из 8 двоичных символов.