Source Encoding

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