Кодирование информации
Создание: 06.03.2013
Коль из города выйдут британцы сегодня По суше иль морем, он другу сказал, Повесишь фонарь на верху колокольни Северной церкви, как особый сигнал,. Один, если сушей, и два, если морем.

С этого стихотворения Генри Уодсворт Лонгфелло, я начинаю со своими учениками тему «Кодирование информации». Оно взято из замечательной книги Ч. Петцольд «Код. Тайный язык информатики»/ В стихотворении говорится о передаче информации в закодированном виде.

Если у системы есть только два состояния, например, готов к уроку/не готов, пришел вовремя/опоздал, болен/здоров и т.п. достаточно одного «фонаря». Нам достаточно договориться о том что означает сигнал «свет есть» и «света нет».  

В случае если количество вариантов больше двух, как, например, в стихотворении:

  • британцы идут морей
  • британцы идут сушей
  • британцы остались в городе

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

Проанализируем закономерность сколько состояний системы можно закодировать, используя N фонарей:

кол-во фонарей кол-во комбинаций
1 2 (0,1)
2 4 (00, 01, 10, 11)
3 8 (000, 001, 010, 011, 100, 101, 110, 111)

Как правило, при перечислении всех возможных вариантов для трех фонарей ученики не строят последовательно все возможные комбинации, так как связи между «кодированием» и двоичной системой счисления они пока не видят. Мы подробно рисуем все возможные варианты, пытаемся понять, можно ли нарисовать еще какую-нибудь последовательность и находим простое доказательство утверждения:

«При увеличении количества фонарей на один, количество вариантов возрастает в два раза».

Из этого утверждения следует основной закон:

А = 2n

Где А – количество вариантов, n – количество фонарей. Отсюда до битов – рукой подать.

Этот принцип кодирования:

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

мы будем использовать на всем протяжении курса. Даже при обсуждении вероятностного подхода при определении количества информации становится ясно, что «вероятностный» подход это не противопоставление «алфавитному» подходу, это – суть одно. Но об этом в другой раз.

Примеры:

Задача: В классе 25 человек, сколько фонарей (бит) необходимо для кодирования каждого ученика?
Решение: 4 бит не хватит, 24=16, а вот пяти бит – вполне. Пять бит могут вместить 32 различные комбинации.

Задача: сколько бит необходимо для кодирования одного символа текста?
Решение: Подсчитаем сколько символов мы используем при письме:

33 русских строчных,
33 русских прописных
26 латинских строчных
26 латинских прописных
10 цифр
~ 20 знаков препинания

Итого: 148 символа. 7 бит не хватит, 27=128, а вот восемь бит – хватит. восемь бит могут вместить 256 различных комбинаций.

Задача: Сколько цветов может содержать картинка 10х10 пикселей, размером 50 байт.
Решение: 50 байт = 400 бит. На один пиксель приходится 4 бита, следовательно палитра такого изображения может состоять не более чем из 24=16 цветов.

Задача: Сколько минут длится мелодия, чей файл размером в 10 560 000 байт имеет следующие параметры: частота дискретизации 44 КГц, глубина звука 16 бит (используется на CD), стерео.

Решение: размер файла = время * частота дескретизации * глубина звука * количество каналов
10 560 000(байт) = t(секунды) * 44000(Гц) * 2(байт) * 2(стерео)
t = 60 секунд

и т.д, и т.п.