Задание 7: кодирование, декодирование и объём графики и звука

Считаем объём картинок и звука и разбираемся с кодированием — это задание №7.

Кодирование — это представление информации набором символов/битов по правилу; декодирование — обратное восстановление сообщения по коду.

Что проверяет задание 7

Задание 7 объединяет несколько похожих сюжетов: посчитать объём растрового изображения, объём звукозаписи, либо декодировать сообщение по таблице кодов / проверить условие однозначного декодирования. Всё это — снова арифметика на степенях двойки, плюс пара специальных формул.

Объём растрового изображения

Растровая картинка — это сетка пикселей. Каждый пиксель хранит цвет, на который тратится i бит. Если в палитре N цветов, то N = 2^i — та же формула, что и для символов.

Формула объёма: I = W · H · i, где W — ширина в пикселях, H — высота, i — бит на пиксель.

Пример: изображение 64×32 пикселя, палитра 16 цветов. Найти объём в байтах.

16 цветов → i = 4 бита (16 = 2⁴). Объём: 64 · 32 · 4 = 8192 бит = 1024 байта.

width, height = 64, 32
colors = 16
bits_per_pixel = 4          # 16 = 2**4
total_bits = width * height * bits_per_pixel
print("Бит:", total_bits)
print("Байт:", total_bits // 8)

Вывод:

Бит: 8192
Байт: 1024

Объём звукозаписи

Звук кодируют, измеряя громкость много раз в секунду. Параметры:

Частота дискретизации f (Гц) — сколько замеров в секунду.
Глубина кодирования i (бит) — сколько бит на один замер.
Время t (с) и число каналов (1 — моно, 2 — стерео).

Формула: I = f · i · t · каналы (в битах).

Пример: 10 секунд стереозвука, частота 8000 Гц, глубина 8 бит. Найти объём в Кбайтах.

freq = 8000        # Гц
bits_per_sample = 8
seconds = 10
channels = 2       # стерео
size = freq * bits_per_sample * seconds * channels
print("Бит:", size)
print("КБайт:", size / 8 / 1024)

Вывод:

Бит: 1280000
КБайт: 156.25

Декодирование по таблице кодов

Второй тип задания 7 — про двоичные коды символов. Иногда дают таблицу: А=00, Б=01, В=10 и т.п., и просят декодировать строку битов. Главное правило — читать код слева направо, выбирая подходящий префикс.

Особый случай — условие Фано (однозначное декодирование): если ни один код не является началом другого, сообщение читается однозначно. Часто просят подобрать кратчайший код для символа, чтобы декодирование оставалось однозначным.

codes = {"А": "0", "Б": "10", "В": "110", "Г": "111"}
# Проверим условие Фано: ни один код не префикс другого
words = list(codes.values())
ok = True
for a in words:
    for b in words:
        if a != b and b.startswith(a):
            ok = False
print("Код префиксный (Фано выполнено):", ok)

# Декодируем строку
decode = {v: k for k, v in codes.items()}
bits = "0101110"
buf, result = "", ""
for ch in bits:
    buf += ch
    if buf in decode:
        result += decode[buf]
        buf = ""
print("Декодировано:", result)

Вывод:

Код префиксный (Фано выполнено): True
Декодировано: АБГА

Проследим, как читается строка 0101110 слева направо: 0 → А, затем 10 → Б, затем 111 → Г, и снова 0 → А. Получилось «АБГА». Поскольку код префиксный (ни один не является началом другого), на каждом шаге подходит ровно один вариант — двусмысленности не возникает.

Сравнение двух вариантов кодировки

Любимый сюжет задания 7 — «во сколько раз изменится объём, если...». Например: изображение хранили с палитрой 256 цветов, а перевели в палитру 16 цветов. Во сколько раз уменьшится объём? Ответ зависит только от бит на пиксель: было 8, стало 4, значит объём уменьшится ровно в 2 раза. Размеры картинки сокращаются — они одинаковы в обоих случаях.

width, height = 100, 100
i_old = 8     # 256 цветов
i_new = 4     # 16 цветов
old = width * height * i_old
new = width * height * i_new
print("Было, байт:", old // 8)
print("Стало, байт:", new // 8)
print("Уменьшилось в", old // new, "раза")

Вывод:

Было, байт: 10000
Стало, байт: 5000
Уменьшилось в 2 раза

Вывод-памятка: при сравнении объёмов одного и того же изображения достаточно сравнить биты на пиксель — остальные множители (ширина и высота) одинаковы и сокращаются. То же и со звуком: если вдвое уменьшить частоту дискретизации, объём уменьшится вдвое.

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

Забывают умножить звук на число каналов (для стерео — ×2).
Берут i не по таблице степеней: палитра 256 цветов — это 8 бит, а не «256 бит».
Путают Кбайт/Мбайт: делят на 1000 вместо 1024.
При декодировании читают код не слева направо или игнорируют префиксы.

Итог

Изображение: I = W · H · i, где N = 2^i — число цветов.
Звук: I = f · i · t · каналы.
Декодирование: читаем биты слева направо; условие Фано даёт однозначность.
Везде помним: байт = 8 бит, Кбайт = 1024 байта.