If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

### Course: Computer science theory>Unit 3

Lesson 1: Ancient information theory

# Source encoding

Introduction to coding theory! Created by Brit Cruise.

## Want to join the conversation?

• So... what's Bob's new idea??
• Two distinct plucks, a short one, and a long one... leading to Morse Code...
• Why does the tin can and the wire work? Why does it transmit sound?
• I have the perfect answer for this. This is a wire that they can pluck and hear from the other side or at least feel the vibrations. This means you can at least move the wire a little. So the way they have it set up allows for the most common rolls to be plucked easiest. The best way to revise this is to partally keep the system you are currently using but alter it to allwo for the uncommons. The best way I can think to do this is to keep the six most common numbers as plucks, but set up a simmilar system of slight pulls for the 6 less common. This will leave you touching the string at the most only six times, which is only half as many as the max for the previous way. Also there will be no chance of strings hitting or getting crossed and tangled. This will also requier no extra matereals.

with a new coding system you could come up with 12 combos easy....

Wires A and B
pluck A = 1
pluck B = 2
A then B = 3
B then A = 4
A twice = 5
B twice = 6
Simultaneous = 7
Simultaneous x2 = 8
A twice, then B = 9
B twice then A = 10
Simultan. then A = 11
Simult. then B = 12

there are a million more ways to do it. I maxed out at 3 plucks for any combo.
• This idea did occur in history, however two wires is not needed (and more expensive to implement).
• does this tin can over a wire communication really works?
does the sound really propel?
for how long of a wire??
and is it affected by the material used in wiring?
• Yes try it out at home! you can even use paper cups and a string. Sound takes the form of vibrations which are sent along the wire. The materials will affect the amount of noise in the signal...I suggest you try it out
• Is bob's idea morse coding?
or somthing else?
• That could certainly be! After doing a little research, I found that the most frequent letters such as E, T, and A have the shortest morse code representations ( •, –, and • – respectively)
In contrast, the least frequent letters like X, Q, and Z have the longest morse code representations (– • • –, – – • –, and – – • •)
Note: This is international morse code.
• I read the comments and thought that the binary idea was quite good however I was not sure how to convey the 1's and 0's.
I pondered for some time and had an idea that they could install another wire and then a pluck on the first wire would mean a 0 and a pluck on the second wire would mean a 1.
This way they could send any roll in just 2 seconds( 12 just needs 4 binary digits and they can send two plucks per second).
If we find the total amount of plucks to send all the numbers from 2 to 12 we get 66. If we use binary we only need to send 36 plucks to send all these numbers across.

Will this be a good way to send the dice rolls?
• While your idea would improve the speed, it would also double the resources needed to implement it. Technically, it would be fastest to simply have eleven wires with a single value assigned to each, but that isn't a very efficient method of information transfer. At the end of the video, Bob was shown "muting" the wire when he plucked it, which provides another method of representing binary digits -- Short and long plucks. This way, there is no change to the setup they already have installed and the speed of information transfer is improved as you described binary representation would.
• Is there a speed limit to information transfer?
• Muhammed,

Ultimately, the speed of light would be the fastest that any signal can travel. Of course, the signal has to take some value for a particular amount of time, and it takes some time to encode and decode it, but those times are getting faster as technology improves.

For example, suppose you decide to encode a "1" with one frequency of a radio wave, and a "0" using another frequency, the radio wave would still have to "sit" on the frequency for some amount of time for whatever sensing equipment to register the fact that the frequency has changed. And then, it would take some amount of time for the computer to detect and record the "1" or the "0".

So even though the radio wave moves at the speed of light from the sender to the receiver, it's going to take some extra time to encode and decode the message.
• Short of something more evolved like Morse code or binary that would be hard to invent on the spot (though obviously Morse could be translated by a skilled operator), couldn't Bob simply insert a pause in the signal as a modifier?

For example, no pause could indicate an increase, so per the graph steady plucks would be 7, 8, 9, ..., 12, but were he to include a single half-second pause after the first pluck, the plucks would then be 7, 6, 5, ..., 1.
• Why don't they just move the two buildings closer together?
Maybe that's Bob's amazing new idea.
• They could, but remember that this is an example and not the real thing. Instead of accessing this website from your computer, why not move to the Khan Academy servers and offices and learn stuff there?
• I think Bob is using different kinds of plucks!
• You could make a new code consisting of doubles. 1-6 *2 = 8-12, with 7 having its own unique pluck. Without changing the method of plucking, it might be difficult to determine the difference based on pluck frequency.

Ideas include:
the varying degree of strength applied to the pluck, making each pluck with a different amplitude. Not sure yet how this would affect the timing of plucks per sec.

Questions:
Does frequency or amplitude make the transmission speed from one end to the other faster?

Any insight or add ons would be appreciated.
(1 vote)

## Video transcript

we begin with a problem Alice and Bob leave in tree forts which are far apart with no line of sight between them and they need to communicate so they decide to run a wire between the two houses they pull a wire tight and attach it tin can to each end allowing them to send their voices faintly along the wire however there is a problem noise whenever there is a high wind it becomes impossible to hear the signal over the noise so they need a way to increase the energy level of the signal to separate it from the noise this gives bob an idea they can simply pluck the wire which is much easier to detect over the noise but this leads to a new problem how do they encode their messages as plucks? well since they want to play board games across a distance they tackle the most common messages first 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 in this case the 11 possible numbers which we call a discrete source at first they decide to use the simplest method they send the result as the number of plucks so to send a 3 they send three plucks 9 is nine plucks and 12 is twelve plucks however they soon realize that this takes much longer than it needs to from practice they find that their maximum plucks speed is two plucks per second any faster and they will get confused so two plucks per second can be thought of as the rate or capacity for sending information in this way and it turns out that the most common roll is a 7 so it takes 3.5 seconds to send the number seven Alice then realizes they can do much better if they change their coding strategy she realizes that the odds of each number being sent follow a simple pattern there is one way to roll a 2, two ways to roll a 3 three ways to roll a 4, four ways to roll a 5 five ways to roll a 6 and six ways to roll a 7, the most common and five ways to roll an 8 four ways for a 9 and so on back to one way for a twelve and this is the graph showing the number of ways each result can occur and the pattern is obvious so now let's change the graph to number of plucks versus each symbol she proceeds by mapping the most common number, seven to the shortest signal one pluck she then proceeds to the next most probable number and if there is a tie she picks one at random in this case she selects six to be two plucks and then eight to be three plucks and then back to five to be four plucks and nine as five plucks and back and forth until we reach 12 which is assigned to 11 plucks now the most common number seven can be sent in less than a second a huge improvement this symbol change allows them to send more information in the same amount of time on average in fact this coding strategy is optimal for this simple example in that it impossible for you to come up with a shorter method of sending two dice rolls using identical plucks however after playing with the wire for some time Bob hit on a new idea