Урок №5. Двоичное представление информации.
Чтобы описать непрерывные объекты и процессы с помощью дискретных данных, соответствующую информацию следует выразить с помощью символов какого-нибудь естественного или формального языка. Таких языков тысячи. Каждый язык имеет свой алфавит.
Алфавит — конечный набор отличных друг от друга символов (знаков), используемых для представления информации.
Мощность алфавита — это количество входящих в него символов (знаков).
Алфавит, содержащий два символа, называется двоичным алфавитом.
Рассмотрим в качестве символов двоичного алфавита цифры О и 1.
Словом, составленным из символов двоичного алфавита, будем считать любую последовательность 0 и 1.
С помощью двоичного алфавита можно записать всего два разных односимвольных слова: слово «О» и слово «1». Разных двухсимвольных слов можно записать уже четыре: 00, 01, 10 и 11.
Схема, представленная на рис. 1.7, позволяет быстро и безошибочно записывать в двоичном алфавите все слова требуемой длины.
Рис. 1.7. Схематическое представление получения двоичных кодов
Двоичные символы (0, 1) здесь берутся в заданном алфавитном порядке и размещаются слева направо. Двоичные слова читаются сверху вниз.
Слова из трёх двоичных символов получаются дополнением двухсимвольных слов справа символом 0 или 1. В итоге слов из трёх двоичных символов получается 8 — вдвое больше, чем слов из двух двоичных символов: ООО, 001, 010, 011, 100, 101, 110, 111. Соответственно, разных четырёхсимвольных слов можно записать 16, пятисимвольных — 32, шестисимвольных — 64 и т. д. (табл. 1.2).
Обратите внимание, что количество N всевозможных двоичных слов фиксированной длины i представляет собой произведение i двоек. Эту закономерность в общем виде можно записать так:
В математике такие произведения записывают в виде
N = 2i
Записи 24, 28, 2i читают так: «два в четвёртой степени», «два в восьмой степени», «два в степени и».
С точки зрения теории информации, сообщение — это любой набор знаков некоторого алфавита. Пусть мы хотим отправлять различные сообщения одинаковой длины, используя какой-то алфавит. Конечно, чем короче будет длина сообщений, тем быстрее можно будет их передать. Но вместе с тем если сообщения будут слишком короткими, то количество различных сообщений может оказаться недостаточным. Например, из двух двоичных цифр можно составить только четыре разных сообщения: 00, 01, 10 и 11 — больше, как ни комбинируй, не получится.
Рассмотрим алфавит из четырёх знаков: @#$%. Постройте все возможные сообщения из одного знака. Постройте все возможные сообщения из двух знаков, которые начинаются с буквы @ (вторая буква может быть любой).
Для алфавита @#$% в сообщении из двух знаков первый знак можно выбрать четырьмя способами, и для каждого из них есть 4 варианта выбора второго знака. Поэтому сообщений, состоящих из двух знаков, будет 42 = 16 (рис. 2.2).
Рис. 2.2
Для алфавита из четырёх знаков определите:
- количество сообщений из двух знаков;
- количество сообщений из трёх знаков;
- количество сообщений из четырёх знаков;
- количество сообщений из L знаков.
Для алфавита из М знаков определите:
- количество сообщений из двух знаков;
- количество сообщений из трёх знаков;
- количество сообщений из четырёх знаков;
- количество сообщений из L знаков.
Если алфавит языка состоит из М знаков (имеет мощность М), количество различных сообщений длиной L знаков вычисляется как
N = МL
Для двоичного алфавита (его мощность равна М = 2), получается:
N = 2L.
Алфавит языка содержит буквы «А» и «У». Определите, сколько сообщений из трёх знаков можно записать с помощью этого языка.
Алфавит языка содержит буквы «А», «О» и «У». Определите, сколько сообщений длиной не больше четырёх знаков можно записать с помощью этого языка.
Если длина сообщений может меняться (может быть равна L1, L2, LK), то для вычисления общего количества различных сообщений нужно сложить количества сообщений для каждой возможной длины:
N = N1 + N2 + … + NK.
В чём принципиальное различие между картиной, нарисованной красками, и мозаикой?
Давайте подумаем, что на самом деле происходит, когда мы записываем информацию с помощью какого-либо алфавита. При этом информация, существовавшая ранее у нас в сознании в виде мыслей, записывается в виде отдельных «кусочков», знаков. Так же и линия, нарисованная на бумаге, при сканировании представляется в памяти компьютера в виде отдельных элементов — пикселей. Такая процедура называется дискретизацией.
Дискретизацию мы используем и в жизни. Например, когда измеряют температуру воздуха, обычно округляют её до целых градусов, хотя температура изменяется непрерывно, а не скачками: она может быть равной и 18,25 °С, и 18,251 °С, и 18,2513 °С и т. д. Математики говорят, что множество дробных чисел непрерывно, потому что между двумя любыми дробными числами находится бесконечно много других дробных чисел. В то же время множество целых чисел дискретно, потому что между двумя целыми числами находится конечное число других целых чисел, и его легко подсчитать. Таким образом, при округлении мы выполняем дискретизацию данных.
Дискретизация — это представление непрерывного объекта в виде множества отдельных элементов.
Картина художника — это непрерывный объект, а мозаика, сделанная на её основе, — дискретный. Переход от наскальных рисунков к алфавитному письму — это тоже переход от непрерывного способа представления информации к дискретному.
Все приборы, которые показывают результаты измерений в цифровом виде, выполняют дискретизацию. Например, стрелка в обычном спидометре автомобиля может принимать любое положение, это непрерывный (или, как говорят физики, аналоговый) прибор. А цифровой спидометр показывает дискретные данные — скорость с округлением до 1 км/ч (рис. 2.4).
Рис. 2.4
Может ли цифровой спидометр показать скорость 110,231 км/ч? Почему?
Обратите внимание, что в результате дискретизации мы теряем информацию. Заменив картину художника мозаикой, мы сделали её более грубой, потеряли тонкие детали. Но часто потеря информации допустима. Например, при округлении температуры вместо 18,2513 °С мы получили 18 °С, но нам этого достаточно для решения бытовых задач.
Как вы знаете, все виды информации в компьютере представлены в двоичном коде, как цепочки нулей и единиц. Это не случайно, потому что для хранения каждого бита в компьютере используется электронный блок с двумя состояниями. Поэтому компьютер — это дискретное устройство.
Для того чтобы ввести данные в компьютер, нужно выполнить их дискретизацию, например представить текст как набор букв, а рисунок — как набор пикселей. Затем каждому элементу (букве, пикселю) нужно присвоить двоичный код — битовую цепочку. Как это делается и какие бывают коды, вы узнаете далее.