Information Theory and Coding - Codes: The Guide to Secrecy from Ancient to Modern Times - page 432

11.3 Huffman Codes

A promise made is a debt unpaid, and the trail has its own stern code.
Robert W. Service (1874-1958), Canadian Poet
— From The Cremation of Sam McGee (1907)

This section deals with another focus that motivated Shannon. Todaywe
would call it message compression, but he saw it as the problem of finding
the optimal method for representing data in the most compact form. This
will bring together the relationship between entropyand compression, so the
material studied in the previous section will be a valuable tool. We now look
at formalizing this notion with an eye to finding an optimal encoding for all
possible messages in the message source. First we look at the man behind the
idea we present herein.

Huffman David A. Huffman (1925-1999) obtained his B.Sc. in electrical
engineering from Ohio State Universitywhen he was eighteen. He then served
as a radar maintenance oLcer on a destroyer, which served to clear mines in
Japanese and Chinese waters following World War II. After returning to Ohio
State Universitywhere he obtained his M.Sc., he went to MIT for his graduate
work. While there, he developed his ideas, under the supervision of Robert
Fano, and presented them in a term paper. The ideas were published in 1952. He
received the Louis E. LevyMedal from the Franklin Institute for his Ph.D. thesis
on sequential switching circuits. Ohio State Universityalso later granted him
their Distinguished Alumnus Award. Huffman's ideas on compression eclipsed
the ideas put forth byhis supervisor and Shannon, which were called Shannon-
Fano codes .
He served on the facultyat MIT from 1953, but in 1967 he moved to Califor-
nia to take a position at the Universityof California at Santa Cruz. He founded
the Computer Science Department there, and almost single-handedlydeveloped
the department, serving as its head from 1970-1973. He retired in 1994, but for
a couple of years continued to teach Information Theory and other courses such
as signal analysis.
Huffman received manyawards, among them the Golden Jubilee Award for
Technological Innovation from the IEEE Information TheorySocietyin 1988;
the Computer Pioneer Award from the IEEE Computer Society; and the 1999
Richard W. Hamming Medal from the IEEE in recognition of his outstanding
contributions to the general scope of information sciences. He died on October
7, 1999, and is survived byhis wife, a son, and two daughters.
Huffman codes can be used in a vast arrayof compression areas, albeit
newer approaches have taken over. Nevertheless, the ideas are seminal in the
compression arena, so we will devote some time to understanding them.

Encoding If S is a message source, we maydefine an injective function

f : is the set of all bitstrings of finite length. This is called

an encoding of messages from

S → B , where B

S . We denote the bitlength of the image f ( s )by