Кодирование двоичного сообщения
Двоичное сообщение состоит из нулей и единиц. В задачах важно различать длину сообщения в битах, число символов исходного текста и объём информации в байтах или килобайтах.
Основные понятия
Бит — минимальная единица количества информации. Один бит может хранить одно из двух значений: 0 или 1. Последовательность битов образует двоичное сообщение, или двоичный код.
Длина двоичного сообщения — это количество записанных в нём двоичных разрядов, то есть нулей и единиц. Если сообщение содержит 25 знаков 0 или 1, его длина равна 25 битам.
Информационный вес символа — количество бит, используемых для кодирования одного символа. При равномерном двоичном коде каждый символ получает код одинаковой длины.
Если на один символ отводится \(i\) бит, то код одного символа имеет длину \(i\) бит. Если сообщение содержит \(K\) символов, а каждый символ кодируется одинаково, общая длина сообщения находится умножением \(K\) на \(i\).
Здесь \(L\) — длина двоичного сообщения в битах, \(K\) — число символов, \(i\) — длина кода одного символа в битах. Из этой формулы можно выразить любую величину.
Как связаны число символов и длина кода
Количество различных кодов длины \(i\) равно \(2^i\): на каждой позиции можно выбрать 0 или 1, поэтому число вариантов перемножается \(i\) раз.
Если требуется закодировать алфавит из \(N\) различных символов одинаковыми двоичными кодами, минимальная длина кода определяется условием \(2^i \ge N\). Следовательно, нужно найти наименьшее целое \(i\), для которого это неравенство выполняется.
Для кодирования \(N\) различных символов равномерным двоичным кодом достаточно \(i\) бит на символ, если \(2^i \ge N\). Если \(N=2^i\), все возможные коды используются полностью. Если \(N\) не является степенью двойки, часть кодов может остаться неиспользованной.
Например, 3 бита дают \(2^3=8\) разных комбинаций: 000, 001, 010, 011, 100, 101, 110 и 111. Поэтому ими можно закодировать не более 8 различных символов. Для 10 символов уже нужны 4 бита, потому что \(2^3<10\), а \(2^4\ge10\).
| Длина кода, бит | Число кодов |
|---|---|
| 1 | 2 |
| 2 | 4 |
| 3 | 8 |
| 4 | 16 |
| 5 | 32 |
| 8 | 256 |
Сколько различных символов можно закодировать двоичными кодами длины 5 бит?
Объём информации и перевод единиц
В задачах слово «объём» может означать длину сообщения в битах или тот же объём, выраженный в байтах, килобайтах и других единицах. Поэтому сначала нужно определить единицу измерения в условии и только затем выполнять перевод.
Чтобы перевести биты в байты, нужно разделить число бит на 8. Чтобы перевести байты в биты, число байтов умножают на 8. В школьных задачах для информационных единиц обычно используется двоичный множитель 1024, а не 1000.
Бит обозначают «бит» или «b», байт — «байт» или «B». Не путайте их: 1 байт содержит 8 бит. Поэтому 64 бита — это 8 байт, а не 64 байта.
Разобранный пример
Сообщение записано символами алфавита из 32 знаков. Каждый знак кодируется двоичным кодом одинаковой длины. Сколько бит занимает сообщение из 120 символов? Ответ выразите также в байтах.
Сначала определяем длину кода одного символа по размеру алфавита. Затем умножаем её на число символов и переводим результат из битов в байты.
Ответ: сообщение занимает 600 бит, или 75 байт. Обратите внимание: сначала вычисляется длина кода символа, а не объём всего сообщения.
Алгоритм решения задач
- Выпишите, что дано: число символов, размер алфавита, длина одного кода или общий объём.
- Если известен алфавит, найдите длину одного кода: подберите минимальное \(i\), для которого \(2^i\ge N\).
- Если длина кода одного символа уже дана, этот шаг пропустите.
- Используйте формулу \(L=K\cdot i\) или выразите из неё неизвестную величину.
- Переведите ответ в требуемые единицы: 8 бит = 1 байт, 1024 байта = 1 Кбайт.
- Проверьте здравый смысл ответа: сообщение из нескольких символов не может иметь меньшую длину, чем код одного символа.
В некоторых задачах встречается количество символов в тексте. Пробелы, знаки препинания и переходы строки нужно учитывать, если это прямо следует из условия: каждый такой знак также может быть символом.
1. Умножают число символов на размер алфавита, хотя нужно умножать на число бит на символ. 2. Берут \(i=\log_2N\) без округления вверх, если \(N\) не является степенью двойки. 3. Путают биты и байты. 4. Делят на 1024 при переводе битов сразу в килобайты, забывая сначала учесть 8 бит в байте. 5. Не считают пробелы и знаки препинания, когда они входят в сообщение.
Особые случаи и проверка ответа
Если в условии сказано, что используются коды переменной длины, простое умножение \(K\cdot i\) применять нельзя: у разных символов разные длины. Для таких задач нужна переменная длина кода, а общий объём получают сложением длин кодов всех символов.
Если требуется сохранить исходное сообщение без изменения, речь обычно идёт о кодировании без потерь. При удалении части данных используется кодирование с потерями, но формулы для равномерного двоичного сообщения всё равно применяются только при соответствующих условиях задачи.
Запишите единицы измерения прямо в вычислениях: \(120\ \text{символов}\cdot5\ \text{бит/символ}=600\ \text{бит}\). Сокращение «символов» показывает, что получен именно объём сообщения в битах.
Итоговая проверка
Главное
- Длина сообщения при равномерном коде: \(L=K\cdot i\).
- Число кодов длины \(i\): \(N=2^i\). Для алфавита из \(N\) символов выбирают минимальное \(i\), при котором \(2^i\ge N\).
- 8 бит = 1 байт; 1024 байта = 1 Кбайт.
- Пробелы и знаки препинания считаются символами, если входят в сообщение.
- При переменной длине кодов объём находят сложением длин отдельных кодов, а не простым умножением.