Braille-Oriented Solutions Hand-out
Using a Huffman code answers the question of how to minimize the
average cost of sending a message with 1 of several outcomes where
the outcomes are not equally likely.
Consider here a braille-oriented solution to the running example
of designing a minimum average cost message using the digits 1 or 0,
a cost of $10 per digit, and
a message with 8 possible outcomes
with the probability of each outcome given by the vector
[0.1918, 0.1918, 0.1615, 0.1615,
0.1065, 0.1065, 0.0402, 0.0402].
Let p_i be the probability of the Ith outcome.
Average cost = (cost per digit)*(sum over i)p_i *(# digits Ith outcome).
A graphical code design approach takes the probabilities a pair
at a time, iteratively forms a number of tree graphs, and lists
the code messages from the final tree graph.
A braille-oriented code design approach is compact, allows quick
referencing, and avoids drawing the tree graph entirely.
braille-oriented algorithm:
step 1: Repeatedly list the probabilities
in descending order replacing the smallest pair of probabilities
with their sum.
Give the labels s_i to the sum,
0 to the first probability of the pair,
and 1 to the second probability of the pair.
step 2: Stop when the partial list has 1 entry.
step 3: List the sequences of 0's and 1's in dictionary order that start
with the final partial sum and end with a digit labeled with
a probability.
These sequences are the transmitted messages for the outcomes with
the corresponding probabilities.
Example solution:
List p1:p8 [.1918*2, .1615*2, .1065*2, .0402*2].
p7(0)=.0402, p8(1)=.0402
*s1=.0804
List [p1:p5 p6(.1065) s1(.0804)].
p6(0)=.1065 s1(1)=.0804
*s2=.1869
List [p1:p2 s2(.18669) p3 p4(.1615) p5(.1065)].
p4(0)=.1615 p5(1)=.1065
*s3=.2680
List [s3(.2680) p1 p2 s2(.1869) p3(.1615)].
s2(0)=.1869 p3(1)=.1615
*s4=.3484
List [s4(.3484) s3(.2680) p1(.1918) p2(.1918)].
p1(0)=.1918 p2(1)=.1918
*s5=.3836
List [s5(.3836) s4(.3484) s3(.2680)].
s4(0)=.3484 s3(1)=.2680
*s6=.6164
List [s6(.6164) s5(.3836)].
s6(0)=.6164 s5(1)=.3836
*s7=1 stop
Code word Length Probability
0000 4 .1065
00010 5 .0402
00011 5 .0402
001 3 .1615
010 3 .1615
011 3 .1065
10 2 .1918
11 2 .1918
3 digits per message code: [000 001 010 011 100 101 110 111]
Cost of 3 digits per message code = $30.
Cost of Huffman code = $10*(2*(.1918*2)
+3*(.1615*2+.1065)+4*(.1065)+5*(.0402*2))
equals $28.84, a savings of $1.16 over the other scheme.
*******************************************************************
* John Miller *
* CMRR-0401 *
* University of California, San Diego *
* 9500 Gilman Drive *
* La Jolla, CA 92093-0401 *
* *
* phone: (858) 822-2326 *
* fax (858) 534-2720 *
* email: jmiller@ucsd.edu *
*******************************************************************
This archive was generated by hypermail 2b29 : Sat Mar 02 2002 - 01:40:43 PST