How David Huffman found binary codes of minimum average length for symbols with known frequencies, with no code beginning another, after nearly abandoning a graduate paper

In 1951, David A. Huffman, a graduate student at the Massachusetts Institute of Technology, was given the choice of a final examination or a term paper. His assignment was to find the most efficient way to represent information with binary codes; Huffman chose the paper, and his answer became known as Huffman coding.

The assignment came from Robert M. Fano, who was teaching a graduate course in electrical engineering on the emerging discipline of information theory. Fano asked his students to solve what appeared to be a straightforward problem: given a set of letters, numbers, or symbols with known frequencies of occurrence, how can an engineer assign binary digits to each symbol so that the overall encoded message uses the smallest possible number of bits? Huffman later said he had not known that Fano and Claude E. Shannon—the founder of information theory—had also struggled with the problem.

The Trap of Fixed Lengths and Awkward Pauses

At first glance, transmitting digital text looks trivial. If a computer assigns every letter a fixed length of eight bits, decoding is effortless: every eight digits represent a single character. Yet that uniform simplicity wastes capacity. Common letters like E appear far more frequently than rare characters like Q, meaning a fixed-length code spends as many bits on rare symbols as on everyday ones.

About a century earlier, Samuel Morse and Alfred Vail had developed Morse code, which assigned a single dot to E and longer combinations of dots and dashes to rarer letters. But Morse code suffered from a fundamental flaw: because code lengths varied, a telegraph operator could not decode a message without pauses between letters. Without those spaces, a receiver could not distinguish between different character combinations that shared the same sequence of dots and dashes.

Fano understood that the solution required what mathematicians call a prefix-free code: an arrangement in which no code word forms the beginning of any other code word. If the letter S is assigned the code 01, no other symbol in the alphabet can begin with 01. Under this rule, a recipient can read a continuous binary stream from left to right, immediately identifying where each character ends without needing separating markers.

Building from the Top Down

To assign these prefix-free codes, Fano constructed binary trees, placing symbols at the ends of branches. He started from the top of the tree and worked downward, sorting the alphabet by frequency and attempting to divide it into two sub-groups with roughly equal total probability. If a branch split to the left, he added a zero; if it split to the right, he added a one.

While intuitive, this top-down balancing act was only an approximation. In an example such as encoding the word “schoolroom”—where the letter O appears four times and six other letters appear once each—Fano’s balancing heuristic produced a message requiring 27 bits. It was close to efficient, but Fano knew that a mathematically optimal construction had to exist.

The Wastebasket Breakthrough

For months, Huffman developed approaches to the problem, but he could not prove any of them most efficient. Eventually, he despaired of finding a solution and decided to start studying for the final exam.

The breakthrough arrived in a flash of clarity just as he was about to discard his notes. Huffman later recalled the moment to journalist Gary Stix for a 1991 profile in Scientific American: “It was the most singular moment of my life. There was the absolute lightning of sudden realization.”

Huffman reversed the direction Fano and Shannon had taken. Fano and Shannon had tried to build the tree from the root downward, guessing how to divide the whole probability space in half. Huffman realized that the only place where structure was mathematically certain was at the very bottom.

Starting with the Rarest Symbols

There is always an optimal binary prefix-free code in which the two least probable symbols have code words of maximum length and are siblings under a single parent node. Instead of splitting the whole alphabet from the top, Huffman started with the two rarest items.

He took the two lowest-frequency symbols, joined them into a single composite node, and added their probabilities together. That single step transformed a problem with N symbols into a simpler problem with N minus one symbols. Huffman then repeated the rule: inspect the remaining symbols alongside the new composite node, find the two lowest probabilities, and join them again.

Huffman repeated the pairing until one root node remained. As in Fano’s tree, a left branch contributed 0 and a right branch contributed 1; the path from the root to each symbol gave its code word. For the word “schoolroom,” Huffman’s bottom-up method shaved off a bit, requiring 26 bits instead of 27. When Huffman presented his findings to Fano, his professor looked at the elegant proof and exclaimed, “Is that all there is to it!”

Optimal Within Its Boundaries

In September 1952, Huffman published his discovery in the Proceedings of the Institute of Radio Engineers (IRE) under the title “A Method for the Construction of Minimum-Redundancy Codes.” The paper demonstrated that for any given set of symbol frequencies, his bottom-up algorithm produces a prefix-free code with the minimum possible average code length.

The guarantee, however, carries specific mathematical limits. Huffman coding is strictly optimal for encoding symbols one at a time based on a predetermined probability distribution. It cannot compress every arbitrary file, because counting arguments prove that no lossless algorithm can shrink all possible inputs without expanding others. Furthermore, because Huffman coding treats symbols independently, it does not detect multi-character patterns on its own, which is why compression formats like ZIP combine Huffman trees with string matching. Nor can Huffman coding make JPEG compression lossless: JPEG’s quantization step discards fine visual information before Huffman coding encodes the resulting values.

Huffman never sought a patent on his algorithm; Stix noted that his main reward was being excused from the final examination. His construction rests on a simple principle: combine the smallest cases, then apply the same rule to the smaller problem. His route out of the final examination began with the two rarest symbols.

Explore

Stay connected