Source encoding

we begin with a problem Alice and Bob live 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 the wire tight and attach a 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 plug 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 eleven 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 three they send three plucks nine is nine plucks and twelve 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 - plucks per second any faster and they will get confused so - 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 role is a seven 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 follows a simple pattern there is one way to roll a to two ways to roll a three three ways to roll a four four ways to roll a five five ways to roll a six and six ways to roll a seven the most common and five ways to roll an eight four ways for a nine 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 perceives 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 is five bucks and back and forth until we reach twelve which is assigned to eleven plucks now the most common number seven can be sent in less than a second a huge improvement this simple 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's impossible for you to come up with a shorter method of sending to dice rolls using identical plucks however after playing with the wire for some time Bob hits on a new idea you