<<Предыдущая страница

Е.П. Емельченков, В.И. Мунерман, Т.А.Самойлова, В.Н.Федоров

Раздел 2.  Информация. Алгоритмы. Первые шаги программиста.

§ 2.3. Кодирование информации

     Итак, господа! - продолжал он торжественно, - Перед нами совершенно секретная информация, касающаяся новой системы шифровки полевых депеш.

Я. Гашек. "Похождения бравого солдата Швейка"

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

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

Такое представление информации называется шифровкой или кодированием.

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

Например, если из русского алфавита исключить букву Ё (допускается замена ее буквой Е), то он будет состоять из 32 =2⁵ букв. Тогда любую букву можно закодировать последовательностью из пяти нулей и единиц, и сообщение, составленное из одной буквы, содержит 5 битов информации. При таком кодировании, слово "мама" содержит 4´5 = 20 битов информации.

Рассмотрим на примере построение алфавита и вычисление количества информации, содержащегося в сообщении.

Пример 6. Пусть алфавит состоит из четырех знаков {a, b,+,´}. В таком алфавите каждому знаку будет соответствовать кодовая последовательность длины 2 (4 = 2²). Перечислим все возможные последовательности: {00, 01, 10, 11}, и поставим их в соответствие знаком нашего алфавита следующим образом:

ü       a - 00,

ü       b - 01,

ü       + - 10,

ü       ´ - 11.

Любое сообщение, состоящее из одного знака нашего алфавита, содержит 2 бита информации. Сообщения ab и a+ содержат по 4 бита информации, сообщения a´b, +ab и aaa - по 6 битов, а сообщение ааааа - 10 битов.

Для облегчения построения кодовых последовательностей можно использовать графический способ (рис. 31).  

Рис. 31.  Кодовые последовательности для алфавита из четырех знаков

Рисунок начинается с вертикальной линии, разветвляющейся в двух направлениях, также переходящих в вертикальные. Каждая новая вертикальная линия снова разветвляется. В результате мы получаем четыре вертикальных линии, под каждой из которых записывается один из знаков алфавита. В местах поворота записываются нули и единицы: 0 для левого, и 1 для правого поворота. Мы начинаем движение из верхней точки рисунка и, поворачивая на разветвлениях налево или направо, "собираем" встречающиеся нам по пути нули и единицы. Выбранный путь приводит нас к единственному знаку алфавита. Так путь "вниз-вправо-вниз-влево-вниз"

приведет нас к символу +, а "соберем" мы кодовую последовательность 10.

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

Рис. 32. Кодовая таблица для алфавита из примера 2.6

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

Мы можем пойти еще дальше, поставив в соответствие каждому коду целое число от нуля до 2^k-1. В нашем случае коду 00 соответствует число 0, 01 - 1, 10 - 2 и 11 - 3.  Тогда знакам алфавита из примера 3 соответствуют числа: a - 0, b - 1, + -, ´ - 3.

Поскольку в качестве байта избрана кодовая последовательность из восьми битов, принятый сегодня алфавит состоит из 256 символов. Каждому символу поставлено в соответствие число от 0 до 255.

Мы не будем приводить всю кодовую таблицу этого алфавита. Ее можно найти в любой книгу по программированию. Приведем лишь коды некоторых символов.

Рис.33

Название этого алфавита ASCII (от английского American Standard Code for Information Interchange).Для того, чтобы узнать код каждого символа достаточно посмотреть в таблицу. Все современные  языки  программирования, позволяют узнавать код символа при помощи специальной  функции. Другая функция позволяет по коду определить нужный символ.

Каждое сообщение, составленное из символов этого алфавита, содержит столько байтов информации, сколько знаков оно содержит. Слово мама закодированное в ASCII содержит 4 байта или 32 бита информации.

Мы познакомились с понятием информация, научились ее измерять и кодировать. Далее мы приступим к изучению основ программирования.

 следующая страница >>