Учебная статья

Кодирование и передача информации: единицы измерения, системы счисления, условие Фано

Ты научишься вычислять объем и скорость передачи данных, переводить числа между системами счисления и проверять однозначность кодов.

Зачем на экзамене

Тема объединяет несколько способов представления информации. Тебе нужно работать с числами, текстом, изображениями, звуком и кодовыми словами. Эти знания связаны с заданиями 4, 7, 8, 11 и 14.

Главный навык: перевести условие на язык битов, кодов или цифр, а затем выполнить расчет без потери единиц.

Что нужно уметь

переводить биты в байты и более крупные единицы;
находить длину двоичного кода по мощности алфавита;
считать количество слов заданной длины;
переводить целые числа между системами счисления;
вычислять объем текста, изображения и звука;
находить время или скорость передачи данных;
проверять код по условию Фано.

База

Единицы информации

Бит принимает одно из двух значений: 0 или 1. Байт состоит из 8 бит. В школьных задачах обычно принимают 1 Кбайт равным 1024 байтам, 1 Мбайт равным 1024 Кбайтам и 1 Гбайт равным 1024 Мбайтам. Если в условии дано другое соотношение, используй именно его.

Единица	Соотношение	Перевод в биты
1 байт	8 бит	8 бит
1 Кбайт	1024 байта	8192 бита
1 Мбайт	1024 Кбайта	8 388 608 бит

При переходе от крупной единицы к мелкой умножай. При переходе от мелкой к крупной дели. Перед сложением, делением или сравнением приведи все величины к одной единице.

Мощность алфавита и длина кода

Алфавит содержит символы, из которых строятся сообщения. Число символов называется мощностью алфавита и обозначается N. Двоичный код длины i позволяет составить 2^i разных кодовых комбинаций.

Минимальная целая длина равномерного двоичного кода определяется формулой:

i = \lceil \log_2 N \rceil,\quad 2^i \ge N

Например, для алфавита из 17 символов четырех бит недостаточно: 2^4 = 16. Нужно 5 бит, потому что 2^5 = 32.

Если сообщение содержит K символов, а каждый символ занимает i бит, объем равен I = K * i бит. Для равновероятных символов количество информации можно записать так:

I = K \log_2 N

В задаче с равномерным целым кодом используй целое число бит на символ. Не округляй итог вместо длины одного кода.

Из алфавита мощности N можно составить N^K слов длины K, если символы могут повторяться и порядок важен. Если повторы запрещены или часть позиций зафиксирована, считай только допустимые варианты.

Системы счисления

В системе с основанием q используются цифры от 0 до q - 1. В шестнадцатеричной системе цифры A, B, C, D, E, F обозначают значения от 10 до 15.

Значение позиционной записи вычисляется по разрядам:

(a_n a_{n-1}\ldots a_0)_q = \sum_{k=0}^{n} a_k q^k

Чтобы перевести целое число из системы с основанием q в десятичную, умножь каждую цифру на соответствующую степень q и сложи результаты. Чтобы перевести десятичное число в систему с основанием q, дели его на q с остатком. Остатки читай снизу вверх.

Двоичную запись удобно переводить в восьмеричную группами по 3 бита, а в шестнадцатеричную группами по 4 бита. Группы выделяй справа. Неполную левую группу дополни нулями.

Объем данных

Перед расчетом определи, из каких одинаковых элементов состоит объект и сколько бит занимает один элемент.

Объект	Объем без сжатия	Что проверить
Текст	`K * i` бит	число символов и бит на символ
Растровое изображение	`W * H * i` бит	ширину, высоту и глубину цвета
Звук	`f * t * i * c` бит	частоту, время, глубину и число каналов
Передача	`I = v * t`	одинаковые единицы объема и скорости

Для изображения W и H задают размеры в пикселях. Глубина цвета i показывает число бит на пиксель. При палитре из N цветов минимальная глубина равна i = \lceil \log_2 N \rceil.

Для звука f означает число отсчетов в секунду, t задает длительность, i показывает число бит на один отсчет одного канала, а c задает число каналов. Для моно c = 1, для стерео c = 2.

Скорость передачи обычно измеряется в битах в секунду. Основное соотношение:

t = \frac{I}{v},\quad v = \frac{I}{t}

Здесь I и v должны использовать согласованные единицы. Служебные данные, сжатие и паузы учитывай только тогда, когда они указаны в условии.

Префиксные коды и условие Фано

Префиксный код устроен так, что ни одно кодовое слово не является началом другого кодового слова. Это условие Фано. Оно позволяет декодировать последовательность слева направо без разделителей и без ожидания следующих символов.

Код удобно изображать двоичным деревом. Переход по ребру 0 или 1 добавляет очередной бит. Готовые кодовые слова должны находиться в листьях. Если слово заканчивается во внутренней вершине, оно является префиксом более длинного слова и условие Фано нарушено.

Условие Фано достаточно для однозначного декодирования. При подборе нового слова нельзя продолжать уже готовое слово и нельзя выбирать слово, которое станет началом уже существующего.

Как решать

Задачи на объем и передачу

Выпиши, что кодируется: символы, пиксели, звуковые отсчеты или весь файл.
Найди число элементов. Для изображения перемножь стороны. Для звука умножь частоту на длительность и число каналов.
Определи число бит на один элемент. Если дана мощность алфавита или палитры, найди минимальное целое i.
Вычисли объем в битах. После этого переводи его в байты, Кбайты или Мбайты.
Для передачи приведи объем и скорость к согласованным единицам, затем используй t = I / v.
Округляй только там, где этого требует смысл. Например, число бит на символ и число целых байтов на запись не бывают дробными.

Перевод систем счисления

Проверь допустимость всех цифр для заданного основания.
При переводе в десятичную подпиши степени основания справа налево, начиная с нулевой.
При переводе из десятичной дели число на новое основание и записывай остатки.
Собери ответ из остатков в обратном порядке и проверь обратным переводом.

Проверка кода Фано

Сравни каждую пару кодовых слов.
Проверь, совпадает ли короткое слово с началом длинного.
Если такое совпадение есть, условие Фано нарушено.
Если нужно добавить слово, отмечай занятые листья и запрещенные продолжения в кодовом дереве.
После выбора снова проверь новое слово со всеми исходными словами.

Частые ошибки

Ошибка: смешивать биты и байты. Как избежать: подпиши единицу после каждого промежуточного результата и помни, что в байте 8 бит.
Ошибка: округлять log2 N вниз. Как избежать: выбери минимальное целое i, для которого 2^i не меньше N.
Ошибка: округлять общий объем записи, хотя память выделяется отдельно под каждый идентификатор. Как избежать: сначала найди целое число байтов на одну запись, затем умножай на число записей.
Ошибка: забывать число каналов звука. Как избежать: отдельно выпиши, используется моно или стерео.
Ошибка: читать остатки от деления сверху вниз. Как избежать: собирай запись нового числа от последнего ненулевого частного к первому остатку.
Ошибка: проверять только одинаковые кодовые слова. Как избежать: ищи совпадение короткого слова с началом каждого более длинного.

Проверь себя

Сколько бит нужно для равномерного кодирования алфавита из 33 символов?
Переведи число 3A из шестнадцатеричной системы в десятичную.
Сколько бит содержится в 2048 байтах?
Найди объем двух секунд монофонического звука с частотой 8000 Гц и глубиной 8 бит.
Выполняется ли условие Фано для кодов 00, 01, 1?

Ответы: 1) 6 бит; 2) 58; 3) 16 384 бита; 4) 128 000 бит, или 16 000 байт; 5) да.

Связь с заданиями

Задание 4 связано с кодовыми словами, однозначным декодированием и условием Фано. В задании 7 полезны формулы объема изображения, звука и передачи данных. Для задания 8 нужно считать слова и последовательности, составленные из заданного алфавита.

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