14. Двоичное кодирование ------------------------------------------------------------

Определения и обозначения

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

Двоичный алфавит — набор из двух символов, используемых при двоичном кодировании. В привычной записи это цифры 0 и 1, но важен сам факт, что символов только два. Алфавит задаёт, какие знаки можно использовать в коде. Благодаря этому из тех же двух знаков можно строить последовательности разной длины.

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

Бит — единица измерения информации; один бит соответствует выбору одного из двух вариантов. Например, ответ «да» или «нет» можно представить одним двоичным разрядом. Бит показывает, сколько двоичных разрядов используется для записи данных. Чем больше разрядов, тем больше вариантов можно закодировать.

Как это устроено

Для записи информации достаточно двух символов, потому что устройства могут различать два состояния. Например, электрический сигнал может быть выше или ниже заданного уровня, а ячейка памяти — находиться в одном из двух устойчивых состояний. Эти состояния условно обозначают 1 и 0. Такая пара удобна: устройству не нужно точно различать множество уровней, поэтому запись получается проще и надёжнее.

Последовательность нулей и единиц становится кодом только после того, как каждому допустимому сочетанию сопоставили объект или значение. Это похоже на условный язык: без словаря набор знаков не подсказывает, что он означает. Например, если договориться, что 00 обозначает круг, а 01 — квадрат, эти сочетания смогут передавать сведения о фигурах. Получатель должен пользоваться тем же правилом, иначе он истолкует запись иначе.

У каждого двоичного разряда есть два возможных значения: 0 или 1. Если добавить новый разряд, к каждой уже имеющейся комбинации можно приписать либо 0, либо 1. Значит, каждый новый разряд удваивает число вариантов: один разряд даёт 2 комбинации, два — 4, три — 8. Число разрядов растёт постепенно, а число доступных сочетаний увеличивается вдвое на каждом шаге.

Для кода фиксированной длины n число комбинаций равно 2ⁿ. Запись 2ⁿ означает, что число 2 нужно умножить само на себя n раз: два выбора есть в каждом из n разрядов. Например, для трёх разрядов получаем 2 × 2 × 2 = 8 комбинаций. Если кодами нужно обозначить столько же или меньше объектов, каждому объекту можно назначить отдельное сочетание.

Чтобы выбрать длину кода для заданного количества объектов, сравнивают число объектов с последовательными степенями двойки. Нужно найти наименьшее n, при котором 2ⁿ не меньше количества объектов: тогда комбинаций хватит, а более короткий код не справится. Например, для 10 объектов проверяем 2³ = 8 и 2⁴ = 16. Восемь комбинаций недостаточно, поэтому выбирают длину четыре разряда.

Длина двоичного кода и число комбинаций

Чтобы найти число вариантов для заданной длины, выбери строку с нужным количеством битов или вычисли 2ⁿ. Примеры показывают начало списка, а многоточие означает, что между приведёнными комбинациями есть другие. Для кодирования объектов сравни число комбинаций с числом объектов.

Разбор задач

Задача 1. Сколько различных комбинаций можно составить из двух двоичных разрядов? Нужно учесть все варианты для первого и второго разрядов, не пропуская сочетаний. Можно перечислить их или воспользоваться правилом 2ⁿ. Здесь длина кода равна двум разрядам.

1. В первом разряде возможны 0 и 1.
2. Для каждого из этих значений во втором разряде тоже возможны 0 и 1, поэтому получаем 00, 01, 10 и 11.
3. Проверяем подсчёт по формуле: 2² = 2 × 2 = 4.

Ответ: 4 комбинации.

Задача 2. Сколько двоичных разрядов достаточно, чтобы закодировать 10 разных символов кодами одинаковой длины? Подбираем длину так, чтобы разных комбинаций было не меньше десяти. Если комбинаций меньше, назначить отдельный код каждому символу невозможно. Поэтому проверяем соседние степени двойки.

1. Для трёх разрядов получается 2³ = 8 комбинаций, а этого меньше, чем 10.
2. Для четырёх разрядов получается 2⁴ = 16 комбинаций, этого уже достаточно.
3. Выбираем четыре, потому что три разряда не подходят, а длина кода должна быть наименьшей возможной.

Ответ: достаточно 4 разрядов.

Задача 3. Даны коды 00, 01, 10 и 11 для четырёх предметов. Нужно закодировать последовательность предметов и расшифровать полученную строку по таблице соответствия. Допустим, таблица задаёт соответствия: круг — 00, квадрат — 01, треугольник — 10, звезда — 11. Последовательность «круг, звезда, квадрат» кодируем, а затем проверяем, как читать полученную запись.

1. Заменяем каждый предмет кодом из таблицы: круг — 00, звезда — 11, квадрат — 01.
2. Записываем кодовые слова подряд: 00 11 01, то есть 001101.
3. При расшифровке делим строку на группы по два разряда: 00, 11, 01.
4. По таблице находим соответствующие предметы: круг, звезда, квадрат.

Ответ: последовательность кодируется строкой 001101 и расшифровывается как «круг, звезда, квадрат».

Типичные ошибки

Ошибка: считать, что n разрядов дают n комбинаций. Так рассуждают, если не учитывают, что каждый разряд может принимать оба значения и сочетаться с вариантами остальных разрядов. На самом деле новый разряд удваивает число комбинаций, поэтому используется 2ⁿ. Проверить себя можно на двух разрядах: их не два, а четыре — 00, 01, 10 и 11.

Ошибка: путать количество символов исходного алфавита с числом разрядов кода. Например, для десяти символов не обязательно нужно десять битов: один код из нескольких разрядов обозначает один символ. Чтобы проверить длину, вычисли 2ⁿ и сравни результат с количеством объектов. Выбирай минимальное n, при котором комбинаций хватает.

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

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

Связь с другими темами

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

Эта тема пригодится при изучении измерения объёма информации: количество двоичных разрядов связано с числом возможных вариантов. На том же принципе основано кодирование текста, когда символам назначают числовые последовательности. Двоичное представление лежит и в основе хранения данных в компьютере.

Что запомнить

• Двоичный алфавит состоит из двух символов: 0 и 1.
• Смысл двоичного кода определяется правилом кодирования.
• Один двоичный разряд может принимать два значения.
• Из n двоичных разрядов можно составить 2ⁿ комбинаций.
• Для кодирования N объектов одинаковыми по длине кодами выбирают наименьшее n, для которого 2ⁿ ≥ N.
• Начальные нули сохраняют, если они входят в код фиксированной длины.