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