Return to Video

情報源符号化(コインの言語: 4/9)

  • 0:04 - 0:06
    ある問題に取り掛かろう。
  • 0:06 - 0:08
    [風が吹く音]
  • 0:15 - 0:16
    アリスとボブは樹上に家を構えて住んでいる。
  • 0:16 - 0:18
    2人の家は遠く離れているため、
  • 0:18 - 0:21
    互いを目視することはできないが、
  • 0:21 - 0:23
    意思疎通を行いたい。
  • 0:23 - 0:25
    そこで2つの家の間に、
  • 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
    最もありがちなメッセージの1つであるー
  • 2:03 - 2:06
    サイコロ2つを振った数値の送信に取り組んだ。
  • 2:06 - 2:09
    ここで送信するメッセージは、
  • 2:09 - 2:11
    有限個の記号、
  • 2:11 - 2:14
    この場合11通りの数値から、
  • 2:14 - 2:17
    1つを選択したものとみなせる。
  • 2:17 - 2:20
    これを「離散情報源」という。
  • 2:24 - 2:27
    最初、彼らは最もシンプルな方法を採用した。
  • 2:27 - 2:31
    はじく回数で結果を送信するのだ。
  • 2:31 - 2:34
    つまり「3」を送信するためには3回はじく。
  • 2:34 - 2:36
    「9」なら9回はじき、
  • 2:36 - 2:38
    「12」なら12回はじく。
  • 2:38 - 2:41
    しかし、これでは必要以上に時間がかかるとー
  • 2:41 - 2:43
    すぐに気付いた。
  • 2:44 - 2:48
    経験から、はじくスピードは最大でー
  • 2:48 - 2:51
    毎秒2回だと分かった。
  • 2:51 - 2:54
    これ以上だと信号が混ざってしまう。
  • 2:54 - 2:57
    つまり、毎秒2回弾きが、
  • 2:57 - 3:01
    この通信手段の「通信路容量」とみなせる。
  • 3:01 - 3:06
    [弾く音]
  • 3:06 - 3:07
    それから、最もー
  • 3:07 - 3:10
    出やすい目は7だと分かった。
  • 3:10 - 3:14
    さて、7を送信するには3.5秒かかる。
  • 3:14 - 3:20
    [7回弾く音]
  • 3:22 - 3:24
    ここでアリスは、符号化の方法を変えることで、
  • 3:24 - 3:27
    ずっと良くできることに気付いた。
  • 3:27 - 3:30
    彼女は、それぞれの目が出る確率に、
  • 3:30 - 3:32
    簡単な規則がある事に目をつけた。
  • 3:32 - 3:34
    2が出るのは1通り。
  • 3:34 - 3:36
    3が出るのは2通り。
  • 3:36 - 3:38
    4が出るのは3通り。
  • 3:38 - 3:40
    5が出るのは4通り。
  • 3:40 - 3:43
    6が出るのは5通り。
  • 3:43 - 3:45
    7が出るのは6通りで、
  • 3:45 - 3:46
    これが最も出やすい。
  • 3:46 - 3:49
    8が出るのは5通り。
  • 3:49 - 3:50
    9には4通り。
  • 3:50 - 3:54
    以下続いて、12では1通りに戻る。
  • 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
    7を、
  • 4:08 - 4:12
    最も短い信号である1回はじきに割り当てた。
  • 4:12 - 4:14
    [1回弾く音]
  • 4:14 - 4:17
    それからその次に出やすい数を割り当てた。
  • 4:17 - 4:20
    同確率の時は、ランダムに選んだ。
  • 4:20 - 4:23
    今回は6を2回に、
  • 4:23 - 4:25
    8を3回に、
  • 4:25 - 4:28
    戻って5を4回に、
  • 4:28 - 4:30
    それから9を5回、
  • 4:30 - 4:34
    次に5を…と割り当て、最後の12には
  • 4:34 - 4:36
    11回はじきを割り当てた。
  • 4:36 - 4:39
    すると、最も出やすい7をー
  • 4:39 - 4:42
    1秒とかからずに送ることができる。
  • 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
    サイコロ2つの結果を送る、
  • 5:00 - 5:05
    もっと速い方法を思いついたなら話は別だ。
  • 5:05 - 5:09
    さて、針金で何度か遊んだ後、
  • 5:09 - 5:11
    ボブに新たなアイデアが閃いた。
Τίτλος:
情報源符号化(コインの言語: 4/9)
Περιγραφή:

無駄のない圧縮方法を考えることで、符号理論 (可変長の符号化) への入門とする。 この簡略化された問題では、1つの記号(はじくこと)の通信を通して、他の記号を伝える方法を扱う。情報源符号化により、情報源をデータに圧縮して効率的に通信することを試みる。

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

Japanese subtitles

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