Return to Video

Source Encoding (Language of Coins: 4/9)

  • 0:04 - 0:20
    We begin with a problem.[Wind Blowing] Alice and Bob live in tree forts which are far apart with no line of sight between
  • 0:20 - 0:28
    Them. And they need to communicate. So they decide to run a wire between the two houses.
  • 0:28 - 0:36
    [wind still blowing]
  • 0:36 - 0:49
    [Alice grabs wire and takes to her tree fort]They pull the wire tight and attach a tin can at each end.
  • 0:49 - 0:52
    [Hear clinking of metal]
  • 0:52 - 1:02
    Allowing them to send the'r voices faintly along the wire.
  • 1:02 - 1:04
    [Hear "Hello" through wire]
  • 1:04 - 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 -
    However, there is a problem; Noise
  • Mh συγχρονισμένα
    Whenever there is a high wind, it becomes impossible to hear the signal over the noise.
  • Mh συγχρονισμένα
    So they need a way to increase the energy level of the signal to separate it from the noise.
  • Mh συγχρονισμένα
    This gives Bob an idea. They can simply pluck the wire, which is much earier to detect over the noise.
  • Mh συγχρονισμένα
    But this leads to a new problem: how do they encode their messages as plucks?
  • Mh συγχρονισμένα
    Well, since they want to play board games across a distance, they tackle the most common messages first.
  • Mh συγχρονισμένα
    The outcome of two dice rolls. In this case the messages they are sending can be thought of as a selection from a finite number of symbols.
  • Mh συγχρονισμένα
    In this case, the eleven possible numbers, which we call a discrete source.
  • Mh συγχρονισμένα
    At first, they decide to use the simplest method. They send the result as the number of plucks.
  • Mh συγχρονισμένα
    So, to send a three, they send three plucks.
  • Mh συγχρονισμένα
    Nine is nine plucks, and twelve is twelve plucks.
  • Mh συγχρονισμένα
    However, they soon realize that this takes much longer than it needs to. From practice, they find that their maximum pluck speed is
  • Mh συγχρονισμένα
    2 plucks per second. Any faster, and they will get confused. So two plucks per second can be thought of as the rate,
  • Mh συγχρονισμένα
    Or capacity for sending information in this way. [hear plucks]
  • Mh συγχρονισμένα
    And it turns out that the most common roll is a seven, so it takes 3.5 seconds to send the number seven [hear seven plucks]
  • Mh συγχρονισμένα
    Alice then realizes they can do much better if they change their coding strategy.
  • Mh συγχρονισμένα
    She realizes that the odds of each number being sent follows a simple pattern.
  • Mh συγχρονισμένα
    There is 1 way to roll a 2, 2 ways to roll a 3, 4 ways to roll a five,5 ways to roll a six, 6 ways to roll a seven, the most common, and 5 ways to roll a eight
  • Mh συγχρονισμένα
    4 ways for a nine and so on back to 1 way for a twelve. And this is a graph showing the number of ways each result can occur,
  • Mh συγχρονισμένα
    And the pattern is obvious. So now lets change the graph to number of plucks vs. each symbol.
  • Mh συγχρονισμένα
    She proceeds by mapping the most common number, 7 to the shortest signal, 1 pluck.[hear one pluck]
  • Mh συγχρονισμένα
    She then proceeds to the next most probable number, and if there is a tie, she picks one at random.
  • Mh συγχρονισμένα
    In this case, she selects 6 to be two plucks and then 8 to be three plucks, and then back to 5 to be four plucks, and 9 is five plucks, and back and forth until we reach 12,
  • Mh συγχρονισμένα
    which is assigned to 11 plucks. Now the most common number, seven, can be sent in less than a second, a huge improvement.
  • Mh συγχρονισμένα
    This simple change allows them to send more information in the same amount of time on average.
  • Mh συγχρονισμένα
    In fact, this coding strategy is optimal for this simple example in that it is impossible for you to come up with a shorter method
  • Mh συγχρονισμένα
    of sending two dice rolls using identical plucks. However, after playing with the wire for some time,
  • Mh συγχρονισμένα
    Bob hits on a new idea.
  • Mh συγχρονισμένα
    [no more 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