Кодирование информации и количество информации — теория для ЕГЭ

Коротко о главном

Информация измеряется в битах и байтах. Существует два подхода к подсчёту количества информации: содержательный (формула Хартли — для равновероятных исходов) и вероятностный (формула Шеннона — для неравновероятных исходов). Кодирование — это сопоставление символов алфавита кодовым словам (последовательностям бит). Чтобы код можно было однозначно декодировать без разделителей, он должен удовлетворять условию Фано. Объём любого сообщения или файла считается по общей схеме: вес одного элемента × количество элементов.

Определения и формулы/правила

Понятие	Формула / правило	Пояснение
Бит	—	минимальная единица информации, ответ на вопрос «да/нет»
Байт	$1\text{ байт} = 8\text{ бит}$	стандартная единица хранения
Кратные единицы	$1\text{ Кбайт}=2^{10}\text{ байт}$, $1\text{ Мбайт}=2^{20}\text{ байт}$, $1\text{ Гбайт}=2^{30}\text{ байт}$	в ЕГЭ используется степень 2, а не 1000
Формула Хартли	$N=2^{i}$, откуда $i=\log_2 N$	$N$ — число равновероятных исходов (символов алфавита), $i$ — количество бит
Округление	$i=\lceil \log_2 N \rceil$	если $N$ не является степенью двойки, округляем вверх
Формула Шеннона	$I=-\sum_{k=1}^{N} p_k \log_2 p_k$	для неравновероятных исходов с вероятностями $p_k$
Объём сообщения	$V=i\cdot L$	$i$ — вес одного символа (бит), $L$ — длина сообщения (символов)
Скорость передачи	$V=v\cdot t$	$v$ — скорость (бит/с), $t$ — время
Условие Фано	ни одно кодовое слово не является началом (префиксом) другого	гарантирует однозначное декодирование без разделителей
Неравенство Крафта	$\sum 2^{-l_k}\le 1$	условие существования префиксного кода с длинами слов $l_k$
Растровое изображение	$V=W\cdot H\cdot i$, $K=2^{i}$	$W,H$ — размеры в пикселях, $i$ — глубина цвета (бит/пиксель), $K$ — число цветов
Звук	$V=f\cdot t\cdot i\cdot c$	$f$ — частота дискретизации (Гц), $t$ — время (с), $i$ — глубина кодирования (бит), $c$ — число каналов

Как применять

Пример 1 (задание 4). Сколько бит нужно для кодирования одного из 100 равновероятных сообщений?

$2^6=64<100\le128=2^7$, значит $i=\lceil\log_2100\rceil=7$ бит.

Пример 2 (задание 7). Алфавит из 4 букв закодирован кодами: А — 0, Б — 10, В — 110, Г — 111. Проверим условие Фано: код А (0) не совпадает с началом кодов Б, В, Г; код Б (10) не является началом кодов В, Г и наоборот — условие выполнено, декодирование однозначно. Декодируем сообщение 0110111:

• 0 → А
• 110 → В
• 111 → Г

Итог: АВГ.

Пример 3 (задание 11). Найти объём звукозаписи длительностью 2 минуты (120 с), частота дискретизации 22050 Гц, глубина кодирования 16 бит, запись стерео (2 канала).

$V=22050\cdot120\cdot16\cdot2=84\,672\,000$ бит.

Переводим в байты: $84\,672\,000/8=10\,584\,000$ байт $\approx 10\,336$ Кбайт $\approx 10{,}1$ Мбайт.

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

• Использование дробного значения $\log_2 N$ без округления вверх (округлять нужно всегда в большую сторону, если $N$ не степень 2).
• Путаница между 1000 и 1024 при переводе байт в Кбайт/Мбайт/Гбайт — на ЕГЭ строго степени двойки.
• Применение формулы Хартли к неравновероятным событиям вместо формулы Шеннона (и наоборот — усложнение простой задачи).
• Забывают домножить объём в битах на количество каналов звука или на глубину цвета изображения.
• Проверка условия Фано «на глаз» без сравнения каждого кода с каждым — приводит к ошибкам при декодировании многозначных сообщений.
• Смешивание единиц: подсчёт скорости в битах, а объёма — в байтах без перевода.

Где встречается на экзамене

• Задание 4 — базовые вычисления с единицами измерения информации: перевод бит↔байт↔Кбайт и т.д., применение формулы Хартли, определение минимального числа бит для алфавита, вычисление объёма сообщения или скорости передачи данных.
• Задание 7 — кодирование и декодирование сообщений, работа с кодами переменной длины, проверка и применение условия Фано, определение минимальной длины кода для алфавита с учётом однозначной расшифровки.
• Задание 11 — практический расчёт объёма информации в файлах (текст, растровое изображение, звук), часто в связке с темами архивации, хранения данных или передачи по каналу связи; требует последовательного применения нескольких формул.