Source Encoding (Language of Coins: 4/9)

0:04  0:20We 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:28Them. 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:02Allowing 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.
 Video Language:
 Japanese
 Duration:
 05:57
Mike Ridgway edited Αγγλικά subtitles for Source Encoding (Language of Coins: 4/9)  
Mike Ridgway edited Αγγλικά subtitles for Source Encoding (Language of Coins: 4/9)  
Mike Ridgway edited Αγγλικά subtitles for Source Encoding (Language of Coins: 4/9)  
Mike Ridgway edited Αγγλικά subtitles for Source Encoding (Language of Coins: 4/9)  
Mike Ridgway edited Αγγλικά subtitles for Source Encoding (Language of Coins: 4/9)  
Mike Ridgway edited Αγγλικά subtitles for Source Encoding (Language of Coins: 4/9)  
Mike Ridgway edited Αγγλικά subtitles for Source Encoding (Language of Coins: 4/9)  
edojur2 edited Αγγλικά subtitles for Source Encoding (Language of Coins: 4/9) 