Source Encoding (Language of Coins: 4/9)
-
0:04 - 0:06We begin with a problem.
-
0:06 - 0:08[WIND BLOWING]
-
0:15 - 0:16Alice and Bob live in tree forts,
-
0:16 - 0:18which are far apart,
-
0:18 - 0:21with no line of sight between them.
-
0:21 - 0:23And they need to communicate.
-
0:23 - 0:25So they decide to run a wire
-
0:25 - 0:27between the two houses.
-
0:40 - 0:42They pull the wire tight,
-
0:42 - 0:45and attach a tin can to each end –
-
0:52 - 0:54allowing them to send their voices
-
0:54 - 0:56faintly along the wire.
-
0:59 - 1:02[BOB - MUFFLED] "Hello?"
-
1:02 - 1:06[ALICE - MUFFLED] Hello? I can't hear you.
-
1:06 - 1:09[BOB - MUFFLED] I can hear you, but just barely.
-
1:09 - 1:15[ALICE - MUFFLED] 1. 2. 3. 4. 5.
-
1:15 - 1:18However, there is a problem:
-
1:18 - 1:21'noise.'
-
1:21 - 1:22Whenever there is a high wind,
-
1:22 - 1:24it becomes impossible to hear
-
1:24 - 1:27the signal over the noise.
-
1:29 - 1:30So they need a way to increase
-
1:30 - 1:32the energy level of the signal,
-
1:32 - 1:35to separate it from the noise.
-
1:35 - 1:37This gives Bob an idea.
-
1:40 - 1:43They can simply pluck the wire,
-
1:43 - 1:47which is much easier to detect over the noise.
-
1:47 - 1:49But this leads to a new problem.
-
1:49 - 1:53How do they encode their messages as plucks?
-
1:57 - 1:58Well, since they want to play
-
1:58 - 2:00board games across a distance,
-
2:00 - 2:03they tackle the most common messages first –
-
2:03 - 2:06the outcome of two dice rolls.
-
2:06 - 2:09In this case, the messages they are sending
-
2:09 - 2:11can be thought of as a selection
-
2:11 - 2:14from a finite number of 'symbols' –
-
2:14 - 2:17in this case, the eleven possible numbers,
-
2:17 - 2:20which we call a 'discrete source.'
-
2:24 - 2:27At first, they decide to use the simplest method.
-
2:27 - 2:31They send the result as the number of plucks.
-
2:31 - 2:34So, to send a '3,' they send three plucks.
-
2:34 - 2:36'9' is nine plucks.
-
2:36 - 2:38And '12' is twelve plucks.
-
2:38 - 2:41However, they soon realize that this takes
-
2:41 - 2:43much longer than it needs to.
-
2:44 - 2:48From practice, they find that their maximum pluck speed
-
2:48 - 2:51is two plucks per second.
-
2:51 - 2:54Any faster, and they will get confused.
-
2:54 - 2:57So two plucks per second can be thought of as the 'rate' –
-
2:57 - 3:01or 'capacity' – for sending information in this way.
-
3:01 - 3:06[SOUND OF PLUCKING]
-
3:06 - 3:07And it turns out that
-
3:07 - 3:10the most common roll is a 7 –
-
3:10 - 3:14so it takes 3.5 seconds to send the number 7.
-
3:14 - 3:20[THE SOUND OF 7 PLUCKS]
-
3:22 - 3:24Alice then realizes they can do much better
-
3:24 - 3:27if they change their coding strategy.
-
3:27 - 3:30She realizes that the odds of each number being sent
-
3:30 - 3:32[follow] a simple pattern.
-
3:32 - 3:34There is one way to roll a 2.
-
3:34 - 3:36[There are] two ways to roll a 3.
-
3:36 - 3:38Three ways to roll a 4.
-
3:38 - 3:40Four ways to roll a 5.
-
3:40 - 3:43Five ways to roll a 6.
-
3:43 - 3:45And six ways to roll a 7 –
-
3:45 - 3:46the most common [result].
-
3:46 - 3:49And five ways to roll an 8.
-
3:49 - 3:50Four ways for a 9 –
-
3:50 - 3:54and so on, back to one way for a 12.
-
3:54 - 3:55This is a graph showing
-
3:55 - 3:58the number of ways each result can occur.
-
3:58 - 4:00And the pattern is obvious.
-
4:00 - 4:02So now, let's change the graph to
-
4:02 - 4:05'number of plucks versus each symbol.'
-
4:05 - 4:07She proceeds by mapping
-
4:07 - 4:08the most common number –
-
4:08 - 4:127 – to the shortest signal – one pluck.
-
4:12 - 4:14[SOUND OF ONE PLUCK]
-
4:14 - 4:17She then proceeds to the next most probable number.
-
4:17 - 4:20And if there is a tie, she picks one at random.
-
4:20 - 4:23In this case, she selects 6 to be two plucks,
-
4:23 - 4:25and then 8 to be three plucks,
-
4:25 - 4:28and then back to 5 to be four plucks,
-
4:28 - 4:30and 9 is five plucks,
-
4:30 - 4:34and back and forth, until we reach 12,
-
4:34 - 4:36which is assigned to 11 plucks.
-
4:36 - 4:39Now, the most common number, 7,
-
4:39 - 4:42can be sent in less than a second –
-
4:42 - 4:44a huge improvement.
-
4:44 - 4:46This simple change allows them to send
-
4:46 - 4:52more information in the same amount of time, on average.
-
4:52 - 4:54In fact, this coding strategy is optimal
-
4:54 - 4:56for this simple example –
-
4:56 - 4:58in that it's impossible for you
-
4:58 - 5:00to come up with a shorter method
-
5:00 - 5:05of sending two dice rolls – using identical plucks.
-
5:05 - 5:09However, after playing with the wire for some time,
-
5:09 - 5:11Bob hits on a new idea.
-
5:11 - 5:13[PLUCKING SOUNDS BEING PLAYED BACKWARDS]
-
5:27 - 5:32[PLUCKS SHOWN IN SLOW MOTION – NO SOUND]
- Title:
- Source Encoding (Language of Coins: 4/9)
- Description:
-
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 English subtitles for Source Encoding (Language of Coins: 4/9) | ||
Mike Ridgway edited English subtitles for Source Encoding (Language of Coins: 4/9) | ||
Mike Ridgway edited English subtitles for Source Encoding (Language of Coins: 4/9) | ||
Mike Ridgway edited English subtitles for Source Encoding (Language of Coins: 4/9) | ||
Mike Ridgway edited English subtitles for Source Encoding (Language of Coins: 4/9) | ||
Mike Ridgway edited English subtitles for Source Encoding (Language of Coins: 4/9) | ||
Mike Ridgway edited English subtitles for Source Encoding (Language of Coins: 4/9) | ||
edojur2 edited English subtitles for Source Encoding (Language of Coins: 4/9) |