Как любая информация превращается в нули и единицы — и почему одни коды короче других.
10 класс, урок 7. Информация и данные · равномерный код · неравномерный код · условие Фано.
Сведения, которые что-то сообщают. Одно и то же сообщение для одного — новость, для другого — ничего нового.
Информация, записанная знаками так, чтобы её можно было хранить, передавать и обрабатывать: текст, таблица, файл.
Информация, которую человек понял, проверил и умеет применять.
Компьютер хранит данные, а не знания: расписание поездов в памяти телефона — данные; умение по нему добраться до дома — знание.
| что | как разбить на знаки |
|---|---|
| текст | буквы, цифры, пробелы — по одной |
| изображение | сетка точек (пикселей), у каждой — номер цвета |
| звук | громкость, измеренная через равные малые промежутки |
| число | цифры в какой-то системе счисления |
Это универсальность дискретного представления: всё, что угодно, — последовательность знаков из конечного набора. А раз так, хватит и двух знаков.
Два состояния техника различает надёжнее всего. Один двоичный знак — бит.
Кодирование — замена каждого знака сообщения
кодовым словом из нулей и единиц: А → 00,
Б → 01, …
| длина i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| слов 2i | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 |
На каждом месте 0 или 1 — два варианта; мест i — значит, слов 2 · 2 · … · 2 = 2i.
Для N знаков: наименьшее i, при котором 2i ≥ N. 33 буквы: 25 = 32 — мало, 26 = 64 — хватит, 6 знаков.
Сообщение режут подряд кусками по i знаков — разделители не нужны: 01|11|00.
Азбука из точек и тире, в сигнале от 1 до 4 знаков. Сколько разных сигналов?
| длина | 1 | 2 | 3 | 4 | всего |
|---|---|---|---|---|---|
| сигналов | 2 | 4 | 8 | 16 | 30 |
Каждую длину — отдельно, потом сложить. Ловушки: 24 = 16 (забыли короткие), 2 · 4 = 8 (умножили вместо степени).
АБРАКАДАБРА: 11 букв, 5 разных. А — 5 раз, Б и Р — по 2, К и Д — по 1.
5 букв → 3 знака на букву (23 = 8 ≥ 5).
11 · 3 = 33 знака
А – 0, Б – 10, Р – 110,
К – 1110, Д – 1111
5·1 + 2·2 + 2·3 + 1·4 + 1·4 = 23 знака
А – 0, Б – 01, В – 10.
Пришло сообщение 010. Что это?
0 | 10 — это АВ01 | 0 — это БА
Получатель не поймёт, что прислали.
Беда: 0 (А) — начало 01 (Б).
На дереве А стоит на пути к Б.
Никакое кодовое слово не является началом другого кодового слова.
Дерево кода: 0 — влево, 1 — вправо, слово — путь от корня. Фано выполняется, когда каждая буква — лист, ниже неё ничего не растёт.
Тогда расшифровка однозначна: читаем слева и отрезаем кусок, как только он совпал с кодом буквы, — другой буквы с таким началом нет.
DV-.