Main content

## Ancient information theory

Current time:0:00Total duration:5:57

# Source encoding

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