Начнём с задачи.
[дует ветер]
Алиса и Боб живут в домиках на деревьях,
которые находятся на большом расстоянии
друг от друга без прямой видимости.
И им нужно поддерживать связь.
Поэтому они решили протянуть провод
между двумя домиками.
Они туго натягивают провод
и прикрепляют жестяную банку на каждом конце,
что позволяет им переправлять
еле слышимый голос.
[Боб, приглушённо] Алло?
[Алиса, приглушённо] Алло? Тебя не слышно.
[Боб, приглушённо] Я тебя едва слышу.
[Алиса, приглушённо] 1. 2. 3. 4. 5.
Однако, есть проблема:
помехи.
Каждый раз, когда поднимается ветер,
становится невозможно услышать
сигнал через помехи.
Поэтому им нужен способ увеличить
уровень сигнала,
чтобы отделить его от помех.
У Боба появляется идея.
Они могут просто дёргать за провод,
что намного проще распознать через помехи.
Но здесь появляется новая задача.
Как они будут кодировать свои сообщения щипками провода?
Ну, так как они хотят играть
в настольные игры на расстоянии,
сначала они договариваются о самых простых сообщениях:
исходах броска двух костей.
В этом случае, посылаемые сообщения
можно представить в виде отбора
из конечной совокупности символов,
которая в нашей ситуации -- это 11 возможных чисел.
Назовём это "дискретным источником".
Сначала они решают использовать самый простой способ.
А именно отправлять результат числом щипков.
То есть чтобы отправить "3", три раза дёргать за провод.
Девять щипков -- это "9",
а двенадцать щипков -- это "12".
Однако, вскоре они поняли, что это занимает
гораздо больше времени, чем нужно.
На практике они выяснили, что их максимальная скорость дёрганья
равна двум щипкам в секунду.
Если дёргать быстрее, то они начинают путаться.
Итак, два щипка в секунду можно считать "скоростью"
или ёмкостью такого способа передачи информации.
[звук щипка]
Вышло так, что
самый частый результат броска -- это "7",
то есть нужно 3,5 секунды, чтобы отправить число семь.
[звуки семи щипков]
Алиса поняла, что можно сделать намного лучше,
изменив подход к кодированию.
Она поняла, что шансы каждого числа для отправки
образуют простую закономерность.
Есть один способ выбросить 2.
Два способа выбросить 3.
Три способа выбросить 4.
Четыре способа выбросить 5.
Пять сособов выбросить 6.
И шесть способов выбросить 7,
самый частый результат.
Пять способов выбросить 8.
Четыре способа для 9-ти.
И так далее до одного способа выбросить 12.
Вот график, изображающий
количество способов получения каждого результата.
Шаблон очевиден.
Сейчас давайте изменим график на
"количество щипков на каждый символ".
Далее, она сопоставляет
самое частое число, семь,
самому короткому сигналу -- одному щипку.
[звук одного щипка]
Потом она переходит к следующему наиболее вероятному числу.
Если встречаются равновероятные, то берётся любое из них.
В данном случае, она выбрала 6 для кодирования двумя щипками,
а 8 -- тремя.
Для 5 будет четыре щипка,
а для 9 -- пять щипков.
И так дальше, пока она не дошла до 12,
которое остаётся кодировать 11 щипками.
Теперь самое частое число, семь,
может быть отправлено менее, чем за секунду.
Значительное улучшение.
Это простое изменение позволило им отправлять
в среднем больше информации за то же самое время.
На самом деле этот способ кодирования оптимальный
для данного простого примера.
В том смысле, что невозможно
найти более короткий метод отправки
результата броска двух костей с помощью одинаковых щипков.
Как бы то ни было, поигравшись с проводом какое-то время,
Боб додумался до новой идеи.
[звуки щипков проигрываются задом наперёд]
[щипок показан замедленно и без звука]