## Source Encoding (Language of Coins: 4/9)

• 0:04 - 0:06
We begin with a problem.
• 0:15 - 0:17
Alice and Bob live in tree forts,
• 0:17 - 0:18
which are far apart,
• 0:18 - 0:21
with no line of sight between them.
• 0:21 - 0:23
And they need to communicate.
• 0:23 - 0:25
So they decide to run a wire
• 0:25 - 0:27
between the two houses.
• 0:40 - 0:42
They pull the wire tight
• 0:42 - 0:45
and attach a tin can to each end --
• 0:52 - 0:54
allowing them to send their voices
• 0:54 - 0:56
faintly along the wire.
• 0:59 - 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 just barely.
• 1:09 - 1:15
[ALICE] 1,2,3,4,5
• 1:15 - 1:21
However, there is a problem: noise.
• 1:21 - 1:22
Whenever there is a high wind,
• 1:22 - 1:24
it becomes impossible to hear
• 1:24 - 1:29
the signal over the noise.
• 1:29 - 1:30
So they need a way to increase
• 1:30 - 1:32
the energy level of the signal,
• 1:32 - 1:35
to separate it from the noise.
• 1:35 - 1:37
This gives Bob an idea.
• 1:41 - 1:43
They can simply pluck the wire,
• 1:43 - 1:47
which is much easier to detect over the noise.
• 1:47 - 1:49
But this leads to a new problem.
• 1:49 - 1:54
How do they encode their messages as plucks?
• 1:56 - 1:58
Well, since they want to play
• 1:58 - 2:00
board games across a distance,
• 2:00 - 2:04
they tackle the most common messages first --
• 2:04 - 2:06
the outcome of two dice rolls.
• 2:06 - 2:09
In this case the messages they are sending
• 2:09 - 2:11
can be thought of as a selection
• 2:11 - 2:14
from a finite number of symbols,
• 2:14 - 2:17
in this case, the eleven possible numbers,
• 2:17 - 2:24
which we call a discrete source.
• 2:24 - 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 3, they send three plucks.
• 2:34 - 2:38
9is nine plucks. And 12 is twelve plucks.
• 2:38 - 2:40
However, they soon realize that this takes
• 2:40 - 2:43
much longer than it needs to.
• 2:44 - 2:46
From practice, they find that
• 2:46 - 2:51
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:01
or capacity for sending information in this way.
• 3:01 - 3:06
[SOUND OF PLUCKING]
• 3:06 - 3:07
And it turns out that
• 3:07 - 3:10
the most common roll is a seven,
• 3:10 - 3:12
so it takes 3.5 seconds
• 3:12 - 3:14
to send the number 7.
• 3:14 - 3:22
[7 PLUCK SOUNDS]
• 3:22 - 3:25
Alice then realizes they can do much better
• 3:25 - 3:27
if they change their coding strategy.
• 3:27 - 3:30
She realizes that the odds of each number being sent
• 3:30 - 3:32
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:56
This is a graph showing the number of ways
• 3:56 - 3:58
each result can occur.
• 3:58 - 4:00
And the pattern is obvious.
• 4:00 - 4:02
So now lets change the graph
• 4:02 - 4:05
to number of plucks vs. each symbol.
• 4:05 - 4:07
She proceeds by mapping
• 4:07 - 4:09
the most common number --
• 4:09 - 4:14
7 -- to the shortest signal -- 1 pluck.
• 4:14 - 4:15
[SOUND OF 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,
• 4:20 - 4:22
she picks one at random.
• 4:22 - 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:30
and 9 is five plucks,
• 4:30 - 4:34
and back and forth until we reach 12,
• 4:34 - 4:37
which is assigned to 11 plucks.
• 4:37 - 4:39
Now the most common number, 7
• 4:39 - 4:42
can be sent in less than a second --
• 4:42 - 4:44
a huge improvement.
• 4:44 - 4:47
This simple change allows them to send
• 4:47 - 4:50
• 4:50 - 4:52
on average.
• 4:52 - 4:55
In fact, this coding strategy is optimal
• 4:55 - 4:56
for this simple example --
• 4:56 - 5:00
in that it is impossible for you
• 5:00 - 5:01
to come up with a shorter method
• 5:01 - 5:04
of sending two dice rolls using identical plucks.
• 5:04 - 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