Кодирование источника
-
0:04 - 0:06Начнём с задачи.
-
0:06 - 0:08[дует ветер]
-
0:15 - 0:16Алиса и Боб живут в домиках на деревьях,
-
0:16 - 0:18которые находятся на большом расстоянии
-
0:18 - 0:21друг от друга без прямой видимости.
-
0:21 - 0:23И им нужно поддерживать связь.
-
0:23 - 0:25Поэтому они решили протянуть провод
-
0:25 - 0:27между двумя домиками.
-
0:40 - 0:42Они туго натягивают провод
-
0:42 - 0:45и прикрепляют жестяную банку на каждом конце,
-
0:52 - 0:54что позволяет им переправлять
-
0:54 - 0:56еле слышимый голос.
-
0:59 - 1:02[Боб, приглушённо] Алло?
-
1:02 - 1:06[Алиса, приглушённо] Алло? Тебя не слышно.
-
1:06 - 1:09[Боб, приглушённо] Я тебя едва слышу.
-
1:09 - 1:15[Алиса, приглушённо] 1. 2. 3. 4. 5.
-
1:15 - 1:18Однако, есть проблема:
-
1:18 - 1:21помехи.
-
1:21 - 1:22Каждый раз, когда поднимается ветер,
-
1:22 - 1:24становится невозможно услышать
-
1:24 - 1:27сигнал через помехи.
-
1:29 - 1:30Поэтому им нужен способ увеличить
-
1:30 - 1:32уровень сигнала,
-
1:32 - 1:35чтобы отделить его от помех.
-
1:35 - 1:37У Боба появляется идея.
-
1:40 - 1:43Они могут просто дёргать за провод,
-
1:43 - 1:47что намного проще распознать через помехи.
-
1:47 - 1:49Но здесь появляется новая задача.
-
1:49 - 1:53Как они будут кодировать свои сообщения щипками провода?
-
1:57 - 1:58Ну, так как они хотят играть
-
1:58 - 2:00в настольные игры на расстоянии,
-
2:00 - 2:03сначала они договариваются о самых простых сообщениях:
-
2:03 - 2:06исходах броска двух костей.
-
2:06 - 2:09В этом случае, посылаемые сообщения
-
2:09 - 2:11можно представить в виде отбора
-
2:11 - 2:14из конечной совокупности символов,
-
2:14 - 2:17которая в нашей ситуации -- это 11 возможных чисел.
-
2:17 - 2:20Назовём это "дискретным источником".
-
2:24 - 2:27Сначала они решают использовать самый простой способ.
-
2:27 - 2:31А именно отправлять результат числом щипков.
-
2:31 - 2:34То есть чтобы отправить "3", три раза дёргать за провод.
-
2:34 - 2:36Девять щипков -- это "9",
-
2:36 - 2:38а двенадцать щипков -- это "12".
-
2:38 - 2:41Однако, вскоре они поняли, что это занимает
-
2:41 - 2:43гораздо больше времени, чем нужно.
-
2:44 - 2:48На практике они выяснили, что их максимальная скорость дёрганья
-
2:48 - 2:51равна двум щипкам в секунду.
-
2:51 - 2:54Если дёргать быстрее, то они начинают путаться.
-
2:54 - 2:57Итак, два щипка в секунду можно считать "скоростью"
-
2:57 - 3:01или ёмкостью такого способа передачи информации.
-
3:01 - 3:06[звук щипка]
-
3:06 - 3:07Вышло так, что
-
3:07 - 3:10самый частый результат броска -- это "7",
-
3:10 - 3:14то есть нужно 3,5 секунды, чтобы отправить число семь.
-
3:14 - 3:20[звуки семи щипков]
-
3:22 - 3:24Алиса поняла, что можно сделать намного лучше,
-
3:24 - 3:27изменив подход к кодированию.
-
3:27 - 3:30Она поняла, что шансы каждого числа для отправки
-
3:30 - 3:32образуют простую закономерность.
-
3:32 - 3:34Есть один способ выбросить 2.
-
3:34 - 3:36Два способа выбросить 3.
-
3:36 - 3:38Три способа выбросить 4.
-
3:38 - 3:40Четыре способа выбросить 5.
-
3:40 - 3:43Пять сособов выбросить 6.
-
3:43 - 3:45И шесть способов выбросить 7,
-
3:45 - 3:46самый частый результат.
-
3:46 - 3:49Пять способов выбросить 8.
-
3:49 - 3:50Четыре способа для 9-ти.
-
3:50 - 3:54И так далее до одного способа выбросить 12.
-
3:54 - 3:55Вот график, изображающий
-
3:55 - 3:58количество способов получения каждого результата.
-
3:58 - 4:00Шаблон очевиден.
-
4:00 - 4:02Сейчас давайте изменим график на
-
4:02 - 4:05"количество щипков на каждый символ".
-
4:05 - 4:07Далее, она сопоставляет
-
4:07 - 4:08самое частое число, семь,
-
4:08 - 4:12самому короткому сигналу -- одному щипку.
-
4:12 - 4:14[звук одного щипка]
-
4:14 - 4:17Потом она переходит к следующему наиболее вероятному числу.
-
4:17 - 4:20Если встречаются равновероятные, то берётся любое из них.
-
4:20 - 4:23В данном случае, она выбрала 6 для кодирования двумя щипками,
-
4:23 - 4:25а 8 -- тремя.
-
4:25 - 4:28Для 5 будет четыре щипка,
-
4:28 - 4:30а для 9 -- пять щипков.
-
4:30 - 4:34И так дальше, пока она не дошла до 12,
-
4:34 - 4:36которое остаётся кодировать 11 щипками.
-
4:36 - 4:39Теперь самое частое число, семь,
-
4:39 - 4:42может быть отправлено менее, чем за секунду.
-
4:42 - 4:44Значительное улучшение.
-
4:44 - 4:46Это простое изменение позволило им отправлять
-
4:46 - 4:52в среднем больше информации за то же самое время.
-
4:52 - 4:54На самом деле этот способ кодирования оптимальный
-
4:54 - 4:56для данного простого примера.
-
4:56 - 4:58В том смысле, что невозможно
-
4:58 - 5:00найти более короткий метод отправки
-
5:00 - 5:05результата броска двух костей с помощью одинаковых щипков.
-
5:05 - 5:09Как бы то ни было, поигравшись с проводом какое-то время,
-
5:09 - 5:11Боб додумался до новой идеи.
-
5:11 - 5:13[звуки щипков проигрываются задом наперёд]
-
5:27 - 5:32[щипок показан замедленно и без звука]
- Title:
- Кодирование источника
- Description:
-
Введение в теорию кодирования (кодирование источника переменной длины) и задачи передачи без потерь. Упрощённая задача имеет дело с одинарными символами (рывками) для отправки отдельных символов.
Кодирование источника пытается сжать данные от источника для того, чтобы передавать их более эффективно. - Video Language:
- Japanese
- Duration:
- 05:57
Dmitry Pulin edited Russian subtitles for Source Encoding (Language of Coins: 4/9) | ||
Dmitry Pulin edited Russian subtitles for Source Encoding (Language of Coins: 4/9) | ||
Dmitry Pulin edited Russian subtitles for Source Encoding (Language of Coins: 4/9) | ||
Dmitry Pulin edited Russian subtitles for Source Encoding (Language of Coins: 4/9) |