Return to Video

Source Encoding (Language of Coins: 4/9)

  • 0:04 - 0:06
    We begin with a problem.
  • 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: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
    [muffled "Hello" through wire]
  • 1:02 - 1:06
    [ALICE] I can't hear you.
  • 1:06 - 1:09
    [BOB] I can hear you, but just barely.
  • 1:09 - 1:15
    [ALICE] 1,2,3,4,5
  • 1:15 - 1:21
    However, there is a problem: noise.
  • 1:21 - 1:22
    Whenever there is a high wind,
  • 1:22 - 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:37
    This gives Bob an idea.
  • 1:41 - 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:54
    How do they encode their messages as plucks?
  • 1:56 - 1:58
    Well, since they want to play
  • 1:58 - 2:00
    board games across a distance,
  • 2:00 - 2:04
    they tackle the most common messages first --
  • 2:04 - 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:28
    At first, they decide to use the simplest method.
  • 2:28 - 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
    9is nine plucks. And 12 is twelve plucks.
  • 2:38 - 2:40
    However, they soon realize that this takes
  • 2:40 - 2:43
    much longer than it needs to.
  • 2:44 - 2:46
    From practice, they find that
  • 2:46 - 2:51
    their maximum pluck speed is 2 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: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 seven,
  • 3:10 - 3:12
    so it takes 3.5 seconds
  • 3:12 - 3:14
    to send the number 7.
  • 3:14 - 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 1 way to roll a 2,
  • 3:34 - 3:36
    2 ways to roll a 3,
  • 3:36 - 3:38
    3 ways to roll a 4,
  • 3:38 - 3:40
    4 ways to roll a 5,
  • 3:40 - 3:43
    5 ways to roll a six,
  • 3:43 - 3:47
    6 ways to roll a seven, the most common,
  • 3:47 - 3:50
    and 5 ways to roll an eight, 4 ways for a nine
  • 3:50 - 3:54
    and so on back to one way for a twelve.
  • 3:54 - 3:56
    This is a graph showing the number of 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:05
    to number of plucks vs. each symbol.
  • 4:05 - 4:07
    She proceeds by mapping
  • 4:07 - 4:09
    the most common number --
  • 4:09 - 4:14
    7 -- to the shortest signal -- 1 pluck.
  • 4:14 - 4:15
    [SOUND OF ONE PLUCK]
  • 4:15 - 4:18
    She then proceeds to the next most probable number.
  • 4:18 - 4:20
    and if there is a tie,
  • 4:20 - 4:22
    she picks one at random.
  • 4:22 - 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:30
    and 9 is five plucks,
  • 4:30 - 4:34
    and back and forth until we reach 12,
  • 4:34 - 4:37
    which is assigned to 11 plucks.
  • 4:37 - 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:47
    This simple change allows them to send
  • 4:47 - 4:50
    more information in the same amount of time
  • 4:50 - 4:52
    on average.
  • 4:52 - 4:55
    In fact, this coding strategy is optimal
  • 4:55 - 4:56
    for this simple example --
  • 4:56 - 5:00
    in that it is impossible for you
  • 5:00 - 5:01
    to come up with a shorter method
  • 5:01 - 5:04
    of sending two dice rolls using identical plucks.
  • 5:04 - 5:09
    However, after playing with the wire for some time,
  • 5:09 - 5:12
    Bob hits on a new idea.
  • 5:12 - 5:22
    [PLUCKING SOUNDS RUNNING BACKWARD]
  • 5:22 - 5:24
    [all sound stops]
  • 5:24 - 5:50
    [silence]
  • 5:50 - 5:55
    [one last low rumbling pluck]
Τίτλος:
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