## 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
• 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
 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)

• Mike Ridgway
• Mike Ridgway
• Mike Ridgway
• Mike Ridgway
• Mike Ridgway
• Mike Ridgway
• edojur2
• skyecolin22