§ 1.4. Двоичное представление данных

Термометр за окном показывает температуру, которая меняется плавно, без скачков. А в дневник наблюдений мы вписываем её цифрами — отдельными знаками. Так приходится поступать всякий раз, когда непрерывное нужно передать дискретными данными: сведения выражают символами какого-нибудь языка, естественного или формального. Языков на Земле тысячи, и у каждого есть свой набор знаков.

Алфавит и его мощность

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

Определение. Мощность алфавита — это число символов, которые в него входят. Её находят простым пересчётом. У набора десятичных цифр мощность равна десяти: цифр от 0 до 9 ровно десять, и каждая выглядит по-своему.

Если символов всего два, алфавит называют двоичным. Сами символы могут быть какими угодно — точка и тире, плюс и минус, горящая и погасшая лампа, — но мы договоримся обозначать их цифрами 0 и 1.

Двоичные слова

Словом в двоичном алфавите будем считать любую цепочку из нулей и единиц: 1, 10, 0110, 111000 — всё это слова. Число символов в слове называют его длиной. Слова 01 и 10 состоят из одних и тех же символов, но это разные слова: важен ещё и порядок, в котором символы стоят.

Слов из одного символа всего два: «0» и «1». Слов из двух символов уже четыре: 00, 01, 10 и 11. Чтобы ни одного не пропустить, удобно рисовать дерево, как на рис. 1. Из начальной точки выходят две ветви: по левой к слову дописывают 0, по правой — 1. От каждого полученного слова снова отходят две ветви, и так до нужной длины. Символы ставятся слева направо в порядке «сначала 0, потом 1», а готовое слово читается по пути от начала вниз.

Посмотри на нижний ряд рис. 1. Каждое слово из двух символов дало два слова из трёх: к нему справа приписали сначала 0, потом 1. Поэтому слов длиной три вдвое больше, чем слов длиной два: 000, 001, 010, 011, 100, 101, 110, 111 — их восемь. Каждый следующий символ снова удваивает количество слов.