David Albert Huffman

☆ Save On Wikipedia ↗
David A. Huffman
Born
David Albert Huffman

(1925-08-09)August 9, 1925
Alliance, Ohio, U.S.[1]
DiedOctober 7, 1999(1999-10-07) (aged 74)
Santa Cruz, California, U.S.
Education
Known forHuffman coding
AwardsIEEE Richard W. Hamming Medal (1999)
Scientific career
FieldsInformation theory, coding theory, switching circuits, mathematical origami
ThesisThe Synthesis of Sequential Switching Circuits (1953)
Samuel H. Caldwell

David Albert Huffman (August 9, 1925 – October 7, 1999) was an American pioneer in computer science, known for developing the technique now named in his honor as Huffman coding, a provably optimal design for a variable-length code for prefix coding in lossless data compression.[2][3] He was also known for the design of sequential switching circuits and was one of the pioneers in the field of mathematical origami.[4]

Education

Huffman earned his bachelor's degree in electrical engineering from Ohio State University in 1944. He then served two years as an officer in the United States Navy. He returned to Ohio State to earn a master's degree in electrical engineering in 1949. In 1953, he received a Doctor of Science in electrical engineering at the Massachusetts Institute of Technology (MIT), with the thesis The Synthesis of Sequential Switching Circuits, advised by Samuel H. Caldwell.[2][3][5]

Career

Huffman is best known for Huffman coding, which he came up with at age 25[2] and published while a doctoral student at MIT in 1952. Huffman coding provides a provably optimal prefix code for any alphabet of input symbols with a known probability mass function (PMF), and it is commonly used for lossless data compression. A Huffman code is very simple to design and has a data redundancy rate of less than one bit (or n-ary coded symbol if the coding is not binary) per source input symbol that is represented by each variable-length string of coded output symbols.

Huffman came up with the algorithm for the design of optimal codes when Professor Robert Fano of MIT offered his students in a graduate-level course on information theory to either take a traditional final exam or write a term paper on the most efficient design for a variable-length binary code.[2] Fano himself and Claude Shannon had worked on the problem and Fano had published a paper on a near-optimal design for such codes, but he did not tell his students that the problem was unsolved.[2][6] After extensively studying the problem and becoming so frustrated that he was ready to throw away his notes in the trash, the solution came to him in a sudden burst of realization.[2] He realized that such codes should be designed from the bottom up, starting from the leaf nodes, rather than from the top down starting at the root, as Shannon–Fano codes had been designed. He later downplayed his own importance and attributed his development of the technique partly to luck, saying "It was my luck to be there at the right time and also not have my professor discourage me by telling me that other good people had struggled with this problem."[2]

Although he was best known for his code design, Huffman reportedly was more proud of his work on the design of sequential switching circuits,[2] which was the topic of his 1953 MIT thesis (an abridged version of which was published in the Journal of the Franklin Institute in 1954[7]). An article in Scientific American said his circuit design work "may be the first formal methodology for devising asynchronous sequential switching circuits, an important type of computer logic".[2]

Huffman joined the faculty at MIT in 1953. In 1967, he joined the faculty of University of California, Santa Cruz, and helped found its Computer Science Department, where he served as chair from 1970 to 1973. He retired in 1994.[3]

Awards and honors

See also

References

  1. Proceedings of the Symposium on Circuit Analysis. University of Illinois. 1955. p. 18-2.
  2. Stix, Gary (September 1991). "Profile: Information Theorist David A. Huffman". Scientific American. Vol. 265, no. 3. Nature Publishing Group. pp. 54–58. Retrieved July 13, 2011.
  3. Stephens, Tim; Burns, Jim (October 11, 1999). "Eminent UCSC Computer Scientist David Huffman Dies at Age 74". Currents Online. University of California, Santa Cruz. Archived from the original on July 16, 2011.
  4. Lang, Robert (December 10, 2015). "Origami Science Links".
  5. David Albert Huffman at the Mathematics Genealogy Project
  6. Lichtman, Elliot. "Data Compression Drives the Internet. Here's How It Works." Quanta Magazine.
  7. Huffman, David A. (March–April 1954). "The Synthesis of Sequential Switching Circuits". Journal of the Franklin Institute. 257 (3): 160–191, 275–303.
  8. "Franklin Laureate Database – Louis E. Levy Medal Laureates". Franklin Institute. Archived from the original on June 29, 2011. Retrieved July 12, 2011.
  9. "Past recipients for W. Wallace McDowell Award". IEEE Computer Society. Archived from the original on February 17, 2012. Retrieved July 13, 2011.
  10. "Computer Pioneer Charter Recipients". IEEE Computer Society. Archived from the original on September 6, 2013. Retrieved July 13, 2011.
  11. "Golden Jubilee Awards for Technological Innovation". IEEE Information Theory Society. Retrieved July 14, 2011.
  12. "IEEE Richard W. Hamming Medal Recipients" (PDF). IEEE. Archived from the original (PDF) on June 20, 2010. Retrieved July 12, 2011.

Further reading