Return to Video

Кодирование источника

  • 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
    [щипок показан замедленно и без звука]
Τίτλος:
Кодирование источника
Περιγραφή:

Введение в теорию кодирования (кодирование источника переменной длины) и задачи передачи без потерь. Упрощённая задача имеет дело с одинарными символами (рывками) для отправки отдельных символов.
Кодирование источника пытается сжать данные от источника для того, чтобы передавать их более эффективно.

more » « less
Video Language:
Japanese
Duration:
05:57

Russian subtitles

Αναθεωρήσεις Compare revisions