Return to Video

Source Encoding (Language of Coins: 4/9)

  • 0:04 - 0:07
    We begin with a problem.
  • 0:07 - 0:15
    [WIND BLOWING]
  • 0:15 - 0:18
    Alice and Bob live in tree forts 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:28
    So they decide to run a wire between the two houses.
  • 0:28 - 0:41
    [wind still blowing]
  • 0:41 - 0:49
    They pull the wire tight and attach a tin can to each end...
  • 0:49 - 0:52
    [clinking of metal]
  • 0:52 - 0:58
    ...allowing them to send their voices faintly along the wire.
  • 0:58 - 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 barely
  • 1:09 - 1:15
    [Alice]: 1,2,3,4,5
  • 1:15 - 1:21
    However, there is a problem: Noise
  • 1:21 - 1:23
    Whenever there is a high wind,
  • 1:23 - 1:29
    it becomes impossible to hear the signal over the noise.
  • 1:29 - 1:33
    So they need a way to increase the energy level of the signal
  • 1:33 - 1:35
    to separate it from the noise.
  • 1:35 - 1:41
    This gives Bob an idea.
  • 1:41 - 1:47
    They can simply pluck the wire, which is much easier to detect over the noise.
  • 1:47 - 1:49
    But this leads to a new problem:
  • 1:49 - 1:57
    how do they encode their messages as plucks?
  • 1:57 - 2:04
    Well, since they want to play board games across a distance, they tackle the most common messages first:
  • 2:04 - 2:07
    the outcome of two dice rolls.
  • 2:07 - 2:09
    In this case the messages they are sending
  • 2:09 - 2:14
    can be thought of as a selection from a finite number of symbols,
  • 2:14 - 2:17
    in this case, the eleven possible numbers,
  • 2:17 - 2:25
    which we call a discrete source.
  • 2:25 - 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 three, they send three plucks.
  • 2:34 - 2:39
    Nine is nine plucks, and twelve is twelve plucks.
  • 2:39 - 2:45
    However, they soon realize that this takes much longer than it needs to.
  • 2:45 - 2:51
    From practice, they find that 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:02
    or capacity for sending information in this way.
  • 3:02 - 3:06
    [sound of plucking]
  • 3:06 - 3:10
    And it turns out that the most common roll is a seven,
  • 3:10 - 3:15
    so it takes 3.5 seconds to send the number seven
  • 3:15 - 3:22
    [7 plucks sound]
  • 3:22 - 3:28
    Alice then realizes they can do much better if they change their coding strategy.
  • 3:28 - 3:32
    She realizes that the odds of each number being sent 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:58
    This is a graph showing the number of ways each result can occur,
  • 3:58 - 4:01
    and the pattern is obvious.
  • 4:01 - 4:06
    So now lets change the graph to number of plucks vs. each symbol.
  • 4:06 - 4:13
    She proceeds by mapping the most common number, 7 to the shortest signal, 1 pluck.
  • 4:13 - 4:15
    [hear 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, 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:34
    and 9 is five plucks, and back and forth until we reach 12,
  • 4:34 - 4:37
    which is assigned to 11 plucks.
  • 4:37 - 4:44
    Now the most common number, seven, can be sent in less than a second, a huge improvement.
  • 4:44 - 4:48
    This simple change allows them to send more information
  • 4:48 - 4:52
    in the same amount of time on average.
  • 4:52 - 4:56
    In fact, this coding strategy is optimal for this simple example
  • 4:56 - 5:00
    in that it is impossible for you 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: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