Return to Video

Source Encoding (Language of Coins: 4/9)

  • 0:04 - 0:10
    We begin with a problem.
  • 0:10 - 0:15
    [WIND BLOWING]
  • 0:15 - 0:17
    Alice and Bob live in tree forts,
  • 0:17 - 0:18
    which are far apart,
  • 0:18 - 0:21
    with no line of sight between them.
  • 0:21 - 0:24
    And they need to communicate.
  • 0:24 - 0:25
    So they decide to run a wire
  • 0:25 - 0:26
    between the two houses.
  • 0:26 - 0:31
    They pull the wire tight,
  • 0:31 - 0:38
    and attach a tin can to each end --
  • 0:52 - 0:54
    allowing them to send their voices
  • 0:54 - 0:57
    faintly along the wire.
  • 0:57 - 1:00
    [MUFFLED "Hello?" THROUGH WIRE]
  • 1:00 - 1:05
    [ALICE - MUFFLED] I can't hear you.
  • 1:05 - 1:12
    [BOB - MUFFLED] I can hear you, but just barely.
  • 1:12 - 1:14
    [ALICE - MUFFLED] 1. 2. 3. 4. 5.
  • 1:14 - 1:21
    However, there is a problem: 'noise.'
  • 1:21 - 1:23
    Whenever there is a high wind,
  • 1:23 - 1:24
    it becomes impossible to hear
  • 1:24 - 1:29
    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:41
    This gives Bob an idea.
  • 1:41 - 1:43
    They can simply pluck the wire,
  • 1:43 - 1:46
    which is much easier to detect over the noise.
  • 1:46 - 1:49
    But this leads to a new problem.
  • 1:49 - 1:54
    How do they encode their messages as plucks?
  • 1:54 - 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:24
    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:38
    '9' is nine plucks. And '12' is twelve plucks.
  • 2:38 - 2:41
    However, they soon realize that this takes
  • 2:41 - 2:45
    much longer than it needs to.
  • 2:45 - 2:46
    From practice, they find that
  • 2:46 - 2:51
    their maximum pluck speed is two plucks per second.
  • 2:51 - 2:54
    Any faster, and they will get confused.
  • 2:54 - 2:58
    So two plucks per second can be thought of as the 'rate,'
  • 2:58 - 3:02
    or 'capacity' for sending information in this way.
  • 3:02 - 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:13
    so it takes 3.5 seconds
  • 3:13 - 3:16
    to send the number 7.
  • 3:16 - 3:22
    [7 PLUCK SOUNDS]
  • 3:22 - 3:25
    Alice then realizes they can do much better
  • 3:25 - 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
    follows a simple pattern.
  • 3:32 - 3:34
    There is one way to roll a 2.
  • 3:34 - 3:35
    [There are] two ways to roll a 3.
  • 3:35 - 3:38
    Three ways to roll a 4.
  • 3:38 - 3:41
    Four ways to roll a 5.
  • 3:41 - 3:43
    Five ways to roll a 6.
  • 3:43 - 3:47
    Six ways to roll a seven -- the most common [result].
  • 3:47 - 3:49
    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:56
    This is a graph showing the ways
  • 3:56 - 3:58
    each result can occur.
  • 3:58 - 4:00
    And the pattern is obvious.
  • 4:00 - 4:02
    So now lets change the graph
  • 4:02 - 4:06
    to number of plucks versus each symbol.
  • 4:06 - 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:15
    [SOUND OF ONE PLUCK]
  • 4:15 - 4:17
    She then proceeds to the next most probable number.
  • 4:17 - 4:18
    and if there is a tie,
  • 4:18 - 4:20
    she picks one at random.
  • 4:20 - 4:23
    In this case, she selects 6 to be two plucks,
  • 4:23 - 4:26
    and then 8 to be three plucks,
  • 4:26 - 4:29
    and then back to 5 to be four plucks,
  • 4:29 - 4:31
    and 9 is five plucks,
  • 4:31 - 4:34
    and back and forth until we reach 12,
  • 4:34 - 4:37
    which is assigned to 11 plucks.
  • 4:37 - 4:40
    Now the most common number, 7,
  • 4:40 - 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:51
    more information in the same amount of time -- on average.
  • 4:51 - 4:54
    In fact, this coding strategy is optimal
  • 4:54 - 4:56
    for this simple example --
  • 4:56 - 4:58
    in that it is 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:10
    Bob hits on a new idea.
  • 5:10 - 5:10
    [PLUCKING SOUNDS PLAYED BACKWARDS]
Τίτλος:
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