Что такое кодирование информации и двоичное кодирование
Кодирование информации — это замена сообщения набором знаков по заранее известному правилу. Азбука Морзе, шифр Цезаря, номера букв в алфавите, штрихкод на упаковке — всё это коды. Обратная операция, когда по коду восстанавливают исходное сообщение, называется декодированием.
Компьютер хранит и передаёт любую информацию в двоичном коде: только 0 и 1. Одна такая цифра — это 1 бит. Набор из 8 бит — 1 байт. Дальше идут единицы покрупнее: 1 Кбайт = 1024 байта, 1 Мбайт = 1024 Кбайта. Подробнее о единицах и о том, как считать количество информации, написано в теме измерение информации.
Главная формула: если в коде каждый символ занимает i бит, то различных символов можно закодировать N = 2^i. Для 1 бита это 2 варианта, для 2 бит — 4, для 8 бит — 256. Нужно закодировать 20 разных символов — хватит 5 бит, потому что 2⁴ = 16 мало, а 2⁵ = 32 уже достаточно.
Кодирование текстовой информации, звука и изображения
Текст. Каждому символу присваивают число, а это число записывают в двоичном виде. Соответствие задаёт кодовая таблица. В ASCII 128 символов, в 8-битных кодировках вроде Windows-1251 их 256, и каждый символ занимает 1 байт. Заглавная и строчная буквы имеют разные коды: «И» и «и» в таблице стоят в разных местах. В Unicode символов гораздо больше, и там на символ может приходиться больше одного байта. Работу с текстом на уровне программ разбирает тема обработка текстов.
Изображение. Картинка делится на пиксели, цвет каждого хранится в виде числа. Глубина цвета i — это число бит на пиксель, количество цветов N = 2^i. Объём файла: I = ширина × высота × i. Если цвет задан в формате RGB по 8 бит на канал, на пиксель уходит 24 бита, а цветов получается 2²⁴ = 16 777 216. Ещё о картинках и видео — в теме графика и мультимедиа.
Звук. Сигнал измеряют много раз в секунду и записывают значения. Объём: I = f × i × t × k, где f — частота дискретизации в герцах, i — разрядность в битах, t — время в секундах, k — число каналов (моно — 1, стерео — 2). Результат получается в битах, его делят на 8 и дальше переводят в Кбайты или Мбайты.
Неравномерные коды и условие Фано
В равномерном коде все символы занимают одинаковое число бит, и его легко разрезать на буквы. В неравномерном длины разные, как в азбуке Морзе, и текст без разделителей можно прочитать несколькими способами.
Условие Фано: никакое кодовое слово не является началом другого кодового слова. Если оно выполнено, расшифровка однозначна: читаешь биты слева направо, и как только набралось слово из таблицы, это точно буква.
Пример. Буквы А, Б, В закодированы как 0, 10, 110. Какой код можно взять для Г: 1, 111, 00 или 11? Проверяем каждый вариант в обе стороны:
- 1 — начало слов 10 и 110, не подходит;
- 00 — начинается с 0, то есть с кода А, не подходит;
- 11 — начало слова 110, не подходит;
- 111 — не совпадает с началом ни одного из кодов, а сам не является началом чужого. Подходит.
Похожая логика нужна при разборе радиограмм азбукой Морзе и шифровок из номеров букв: там проверяют, на какие буквы можно разбить цепочку. Двоичные записи чисел и переводы между системами описаны в теме системы счисления.
Как найти объём изображения: разбор задания
Задача. Изображение размером 800×600 пикселей использует палитру из 16 цветов. Сжатия нет. Сколько Кбайт занимает файл?
Шаг 1. Глубина цвета. 16 = 2⁴, значит, на один пиксель нужно 4 бита.
Шаг 2. Число пикселей. 800 × 600 = 480 000.
Шаг 3. Объём в битах. 480 000 × 4 = 1 920 000 бит.
Шаг 4. Перевод в байты. 1 920 000 ÷ 8 = 240 000 байт.
Шаг 5. Перевод в Кбайты. 240 000 ÷ 1024 = 234,375 Кбайт, примерно 234 Кбайт.
Обратная задача решается так же, только в другую сторону. Например, известен предельный объём файла и размер картинки. Тогда объём переводят в биты, делят на число пикселей и получают глубину цвета i. Максимальное число цветов — это 2^i. Если i вышло дробным, берут целое число бит вниз: больше не поместится.
Где ошибаются чаще всего
- Путают биты и байты. Формулы дают результат в битах. Чтобы получить байты, нужно разделить на 8, и это легко забыть в конце длинного вычисления.
- Делят на 1000 вместо 1024. В школьной информатике 1 Кбайт = 1024 байта, если в условии не сказано иного.
- Подставляют число цветов вместо глубины. В формулу объёма идёт i (например, 8 бит), а не N (256 цветов). Связь между ними: N = 2^i.
- Забывают про стерео. В задачах про звук при двух каналах результат умножают на 2.
- Проверяют условие Фано в одну сторону. Нужно смотреть, не является ли новый код началом старого и не начинается ли старый с нового.
Какие задания по теме присылают ученики
Чаще всего приходят расчёты объёма: видеопамять, размер звукового файла, число цветов по ограничению на файл, сжатие изображения. Много заданий на расшифровку: кодовые таблицы, азбука Морзе, шифр Цезаря, номера букв и условие Фано. Есть задания на кодировку Windows-1251 и на различие между дискретными и непрерывными данными.
Посмотри список заданий выше и найди то, что похоже на твоё: у каждого есть полный ход решения. Если подходящего нет, сфотографируй своё задание и отправь на сайт, чтобы получить решение с ходом.