Кодирование информации: условие Фано и объём данных
Префиксные коды, двоичное дерево кодов и расчёт объёма изображения и звука для заданий 4, 7 и 10.
Задания 4, 7 и 10 объединены общей идеей: информация дискретна, и её объём складывается из объёмов элементов. Различаются только элементы — символ, пиксель, звуковой отсчёт.
Условие Фано: никакое кодовое слово не является началом (префиксом) другого кодового слова. Обратное условие Фано: никакое кодовое слово не является окончанием другого. Выполнение любого из них гарантирует однозначное декодирование сообщения без разделителей.
Текст: I = K · i, где i = ⌈log₂ N⌉ бит на символ. Растровое изображение: I = ширина · высота · i, где i — глубина цвета в битах, N = 2^i — число цветов. Звук: I = частота (Гц) · время (с) · разрядность (бит) · число каналов.
Глубина цвета и палитра
| Число цветов N | Глубина i, бит | Байт на пиксель | Название |
|---|---|---|---|
| 2 | 1 | 0,125 | чёрно-белое |
| 16 | 4 | 0,5 | EGA |
| 256 | 8 | 1 | индексированная палитра |
| 65536 | 16 | 2 | High Color |
| 16777216 | 24 | 3 | True Color |
Условие: для кодирования букв А, Б, В, Г используются двоичные коды: А — 0, Б — 100, В — 101, Г — 110. Нужно закодировать ещё одну букву Д так, чтобы выполнялось условие Фано. Укажите кратчайшее возможное кодовое слово для Д. Если таких слов несколько, укажите то, которое имеет наименьшее числовое значение. Решение. 1) Проверим длину 1. Коды 0 и 1 не подходят: 0 уже занят буквой А, а 1 является началом кодов 100, 101, 110. 2) Длина 2. Варианты 00 и 01 начинаются с 0 — код А оказался бы их префиксом. Вариант 10 является префиксом кодов 100 и 101. Вариант 11 является префиксом кода 110. Не подходит ничего. 3) Длина 3. Перебираем: 000, 001, 010, 011 начинаются с 0 — не подходят. 100, 101, 110 заняты. Остаётся 111: код А (0) не является его префиксом, и 111 не является префиксом ни одного из существующих кодов. В бланк: 111
Условие: несжатое растровое изображение размером 1024 × 768 пикселей сохраняется в файл с использованием палитры из 65 536 цветов. Определите минимальный размер файла в Кбайт (служебной информацией пренебречь). Решение. 1) N = 65536 = 2^16, значит i = 16 бит = 2 байта на пиксель. 2) Число пикселей: 1024 · 768 = 786 432. 3) Объём в байтах: 786432 · 2 = 1 572 864 байт. 4) В Кбайт: 1572864 : 1024 = 1536. В бланк: 1536
Если число цветов не является степенью двойки (например, 100 цветов), то i = ⌈log₂100⌉ = 7 бит, а не 6,64: количество бит всегда целое и округляется вверх. То же с числом символов алфавита. Отдельно следите за формулировками «минимально возможный размер», «не менее», «наибольшее количество» — они определяют, вверх или вниз округлять итог. И помните: 1 Мбайт = 2^20 байт, а не 10^6.
- ✓Проверено условие Фано для всех пар кодов, а не только для соседних
- ✓Среди кодов минимальной длины выбран наименьший по числовому значению
- ✓Глубина цвета i округлена вверх до целого числа бит
- ✓Формула объёма не содержит лишних множителей (моно — один канал)
- ✓Перевод в Кбайт и Мбайт выполнен делением на 1024
- ✓Итог округлён в ту сторону, которую требует формулировка условия
- ✓В бланке одно число или двоичный код без пробелов