In Memory of David Huffman
by Kevin Fu
Professor David Huffman passed away on October 7, 1999 after a 10-month battle with cancer. Throughout his life, Huffman made significant contributions to the study of finite state machines, switching circuits, synthesis procedures, and signal designs. However, David Huffman is best known for his legendary Huffman code, an optimal compression scheme for lossless variable length encoding.
In a fixed length encoding scheme, all characters have the same length. For instance, each ASCII character consumes 7 bits. On the other hand, the Huffman code uses a variable length encoding in which the most frequently used character is represented by the fewest bits. A message is thereby described in the most compact form. In fact, no other scheme can produce a shorter representation of a message in the general case.
The genesis of this algorithm is as fascinating as the algorithm itself. In 1950, Huffman enrolled in a graduate class in information theory and coding at MIT. The instructor, Professor Robert Fano, gave students the option of taking a final exam or solving one of several interesting problems. Huffman opted for the latter because he ``decided it might be easier to solve a seemingly easy problem than it would be to face a final exam.'' About a week before the final exam, Huffman threw a stack of unsuccessful, attempted solutions into the trash. This action somehow caused Huffman to realize the solution and write the term paper.
After completing his graduate studies, Huffman joined the faculty at MIT. In 1967, he left MIT to become the founding faculty member of the Computer Science Department at the University of California ,Santa Cruz. There he played a major role in the development of the department's academic program and taught courses in signal analysis and information theory.
The Huffman code appears in many applications such as fax machines, video compression, and computer security. Huffman never tried to patent an invention from his work. Instead, he concentrated his efforts on education. In Huffman's own words, ``My products are my students.''
References:
- 1
- "In Memoriam," UC Santa Cruz Currents Online, October 18, 1999.
- 2
- E. Sapwater. "Digital Compression: Putting the Squeeze of Imaging," Photo Electronic Imaging, 1994.
- 3
- Gary Stix. "Profile: David Huffman," Scientific American, September 1991.