Return to Video

Source Encoding (Language of Coins: 4/9)

  • 0:04 - 0:06
    We begin with a problem.
  • 0:06 - 0:08
    [WIND BLOWING]
  • 0:15 - 0:16
    Alice and Bob live in tree forts,
  • 0:16 - 0:18
    which are far apart,
  • 0:18 - 0:21
    with no line of sight between them.
  • 0:21 - 0:23
    And they need to communicate.
  • 0:23 - 0:25
    So they decide to run a wire
  • 0:25 - 0:27
    between the two houses.
  • 0:40 - 0:42
    They pull the wire tight,
  • 0:42 - 0:45
    and attach a tin can to each end –
  • 0:52 - 0:54
    allowing them to send their voices
  • 0:54 - 0:56
    faintly along the wire.
  • 0:59 - 1:02
    [BOB - MUFFLED] "Hello?"
  • 1:02 - 1:06
    [ALICE - MUFFLED] Hello? I can't hear you.
  • 1:06 - 1:09
    [BOB - MUFFLED] I can hear you, but just barely.
  • 1:09 - 1:15
    [ALICE - MUFFLED] 1. 2. 3. 4. 5.
  • 1:15 - 1:18
    However, there is a problem:
  • 1:18 - 1:21
    'noise.'
  • 1:21 - 1:22
    Whenever there is a high wind,
  • 1:22 - 1:24
    it becomes impossible to hear
  • 1:24 - 1:27
    the signal over the noise.
  • 1:29 - 1:30
    So they need a way to increase
  • 1:30 - 1:32
    the energy level of the signal,
  • 1:32 - 1:35
    to separate it from the noise.
  • 1:35 - 1:37
    This gives Bob an idea.
  • 1:40 - 1:43
    They can simply pluck the wire,
  • 1:43 - 1:47
    which is much easier to detect over the noise.
  • 1:47 - 1:49
    But this leads to a new problem.
  • 1:49 - 1:53
    How do they encode their messages as plucks?
  • 1:57 - 1:58
    Well, since they want to play
  • 1:58 - 2:00
    board games across a distance,
  • 2:00 - 2:03
    they tackle the most common messages first –
  • 2:03 - 2:06
    the outcome of two dice rolls.
  • 2:06 - 2:09
    In this case, the messages they are sending
  • 2:09 - 2:11
    can be thought of as a selection
  • 2:11 - 2:14
    from a finite number of 'symbols' –
  • 2:14 - 2:17
    in this case, the eleven possible numbers,
  • 2:17 - 2:20
    which we call a 'discrete source.'
  • 2:24 - 2:27
    At first, they decide to use the simplest method.
  • 2:27 - 2:31
    They send the result as the number of plucks.
  • 2:31 - 2:34
    So, to send a '3,' they send three plucks.
  • 2:34 - 2:36
    '9' is nine plucks.
  • 2:36 - 2:38
    And '12' is twelve plucks.
  • 2:38 - 2:41
    However, they soon realize that this takes
  • 2:41 - 2:43
    much longer than it needs to.
  • 2:44 - 2:48
    From practice, they find that their maximum pluck speed
  • 2:48 - 2:51
    is two plucks per second.
  • 2:51 - 2:54
    Any faster, and they will get confused.
  • 2:54 - 2:57
    So two plucks per second can be thought of as the 'rate' –
  • 2:57 - 3:01
    or 'capacity' – for sending information in this way.
  • 3:01 - 3:06
    [SOUND OF PLUCKING]
  • 3:06 - 3:07
    And it turns out that
  • 3:07 - 3:10
    the most common roll is a 7 –
  • 3:10 - 3:14
    so it takes 3.5 seconds to send the number 7.
  • 3:14 - 3:20
    [THE SOUND OF 7 PLUCKS]
  • 3:22 - 3:24
    Alice then realizes they can do much better
  • 3:24 - 3:27
    if they change their coding strategy.
  • 3:27 - 3:30
    She realizes that the odds of each number being sent
  • 3:30 - 3:32
    [follow] a simple pattern.
  • 3:32 - 3:34
    There is one way to roll a 2.
  • 3:34 - 3:36
    [There are] two ways to roll a 3.
  • 3:36 - 3:38
    Three ways to roll a 4.
  • 3:38 - 3:40
    Four ways to roll a 5.
  • 3:40 - 3:43
    Five ways to roll a 6.
  • 3:43 - 3:45
    And six ways to roll a 7 –
  • 3:45 - 3:46
    the most common [result].
  • 3:46 - 3:49
    And five ways to roll an 8.
  • 3:49 - 3:50
    Four ways for a 9 –
  • 3:50 - 3:54
    and so on, back to one way for a 12.
  • 3:54 - 3:55
    This is a graph showing
  • 3:55 - 3:58
    the number of ways each result can occur.
  • 3:58 - 4:00
    And the pattern is obvious.
  • 4:00 - 4:02
    So now, let's change the graph to
  • 4:02 - 4:05
    'number of plucks versus each symbol.'
  • 4:05 - 4:07
    She proceeds by mapping
  • 4:07 - 4:08
    the most common number –
  • 4:08 - 4:12
    7 – to the shortest signal – one pluck.
  • 4:12 - 4:14
    [SOUND OF ONE PLUCK]
  • 4:14 - 4:17
    She then proceeds to the next most probable number.
  • 4:17 - 4:20
    And if there is a tie, she picks one at random.
  • 4:20 - 4:23
    In this case, she selects 6 to be two plucks,
  • 4:23 - 4:25
    and then 8 to be three plucks,
  • 4:25 - 4:28
    and then back to 5 to be four plucks,
  • 4:28 - 4:30
    and 9 is five plucks,
  • 4:30 - 4:34
    and back and forth, until we reach 12,
  • 4:34 - 4:36
    which is assigned to 11 plucks.
  • 4:36 - 4:39
    Now, the most common number, 7,
  • 4:39 - 4:42
    can be sent in less than a second –
  • 4:42 - 4:44
    a huge improvement.
  • 4:44 - 4:46
    This simple change allows them to send
  • 4:46 - 4:52
    more information in the same amount of time, on average.
  • 4:52 - 4:54
    In fact, this coding strategy is optimal
  • 4:54 - 4:56
    for this simple example –
  • 4:56 - 4:58
    in that it's impossible for you
  • 4:58 - 5:00
    to come up with a shorter method
  • 5:00 - 5:05
    of sending two dice rolls – using identical plucks.
  • 5:05 - 5:09
    However, after playing with the wire for some time,
  • 5:09 - 5:11
    Bob hits on a new idea.
  • 5:11 - 5:13
    [PLUCKING SOUNDS BEING PLAYED BACKWARDS]
  • 5:27 - 5:32
    [PLUCKS SHOWN IN SLOW MOTION – NO SOUND]
Τίτλος:
Source Encoding (Language of Coins: 4/9)
Περιγραφή:

Introduction to coding theory (variable length source coding) with a lossless compression problem. This simplified problem only deals with sending unary symbols (plucks) to send single symbols. Source encoding attempts to compress the data from a source in order to transmit it more efficiently.

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

English subtitles

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