無記憶情報源のいかなる復号可能符号の平均符号長も、その情報源のエントロピー以下にすることはできないことは符号とエントロピーで説明しました。
では、復号可能な符号のなかで、
もっとも平均符号長の短い符号（もっともエントロピーに近い符号）を
どのようにして設計すればよいでしょうか？
その符号は、瞬時復号可能な符号の中から見つかり、ハフマン (David.A.Huffman, 1925-1999) がその設計法を示しました。
どの符号語も他の符号語の接頭語になっていない符号は瞬時的に復号可能です。 このような符号は、視覚的に分かりやすい構造をもっています。 下図のように、２本の枝分かれを繰り返す木グラフ（tree graph）を見てください。 左端の根っこから、２本の分枝に“０”と“１”のビットを割り付けてゆきます。 そして、図のように枝の先端（右端の行き止まり）に符号語を割り付けてみます。 符号語は、根っこからその先端まで、枝のビット（０ か１ ）を順々に読み取ったものです。 このような符号語の集まりは、互いに接頭語になっていません。 すなわち、かならず瞬時復号可能です。
先端の符号語は根っこに近ければ近いほど符号長が短いので、できるだけ根っこに近いところで符号を割り付ければ能率の良い（平均符号長の短い）符号が設計できます。 もう少し具体的な例を設計してみましょう。
４つのアルファベット（Ａ、Ｂ、Ｃ、Ｄ）を出力する無記憶情報源を考えてください。 それらの出現確率を
そして割り付けられた符号語の長さを 
とします。 すると、この符号の平均符号長は
で与えられます。 ハフマンは、アルファベットとその出現確率が与えられたとき、もっとも平均符号長の短い瞬時復号可能符号の設計法を見つけました。 その方法を８つのアルファベットを出力する無記憶情報源で説明します。 下図を参照しながら、アルゴリズムをたどってみてください。
- 確率の大きさの順にアルファベットを並べ替えます。
- もっとも確率の小さい二つのアルファベットを選び、それを２本の枝で合流させます。そしてその合流点に二つの確率の和を割り付けます。
- 上の合流点を一つのアルファベットとみなし、2 と同様に、もっとも小さい二つのアルファベットを選び、それらを合流させます。 そして、その合流点に二つの確率の和を割り付けます。
- 以上の １，２，３ を、合流がなくなるまで繰り返します。
- 右端の根っこから左方へ枝のビットを拾って行き、それを符号語として左先端のアルファベットに割り付けます。
この手順によって作られた符号は瞬時復号可能になっていますが、実は非瞬時・瞬時を意識しないでも、このようにして作った符号の平均符号長は最短になっていることがいえるのです。 一般に復号可能な最短の符号をコンパクトであるといいますが、ハフマン符号はコンパクトなのです。
その理由は以下のように考えてみれば、すぐに分かります。 二つのアルファベットを合流するということは、そのどちらが発生しても一つの新しいアルファベットとして読むということですから、アルファベットが一つ減り、符号長も１ビット減ります。 したがって、平均符号長はそれぞれのアルファベットの確率を
とすると、 
だけ減ることになります。 どのような順序で合流しても、最終段階の合流ではかならず平均符号長の減少量は
１ ですから、各段階での平均符号長の減少をトータルした値が合流前の平均符号長に等しくなっていなければなりません。 したがって、合流のたびに生ずる平均符号長の減少の総和がもっとも小さくなるように合流順序を選べばよいことが分かります。 ハフマン符号はこの合流順序を実現しますが、もう少し分かりやすい例で説明してみましょう。
上の例題を８つの会社を二つずつ合併してゆき、最後に一つの会社に統合する問題に置き換えて考えてみます。 合併によって合併損が生じ、全部を統合し終えたときに、合併損のトータルが最小になるようにしたいのです。 合併したときに出す損を確率の値とし、たとえばＡ社とＥ社を合併すると、それらの確率の和
０．５＋０．０５＝０．５５ なる損を発生するとします。 その結果、合併損 ０．５５
をもつ新会社と合併しなかった会社６つ、あわせて７つの会社が残ります。 これら７社から、また二つを選んで合併し、新会社を作ってゆきます。 どのような順序で合併しても、統合が終わるまでの合併の回数はちょうど７回です。 ただし、合併損のトータルは合併の順序によって異なります。下の例を見てください。
合併劇（１）
A+D=0.5+0.08=0.58
G+H =0.02+0.01=0.03
(A+D)+C =0.58+0.1=0.68
B+F =0.2+0.04=0.24
(B+F)+E =0.24+0.05=0.29
((A+D)+C)+(G+H) =0.68+0.03=0.71
(((A+D)+C)+(G+H))+((B+F)+E) =0.71+0.29=1.0
トータル合併損 =0.58+0.03+0.68+0.24+0.29+0.71+1.0= 3.53
合併劇（２）：ハフマンの手順にしたがった場合
H+G=0.02+0.01=0.03
(H+G)+F =0.03+0.04=0.07
((H+G)+F)+E =0.07+0.05=0.12
C+D =0.1+0.08=0.18
((((H+G)+F)+E)+(C+D) =0.12+0.18=0.3
((((H+G)+F)+E)+(C+D))+B=0.3+0.2=0.5
(((((H+G)+F)+E)+(C+D)+B)+A =0.5+0.5=1.0
トータル合併損＝0.03+0.07+0.12+0.18+0.3+0.5+1.0= 2.2
この例から分かるように、早めに合併損の小さな２社を選んで合併すれば、トータル合併損を最小にできます。 すなわち、A社に着目すると、A社が関わる合併の度にA社の確率がカウントされます。 したがって、A社の確率が大きいとき、A社が関わる合併の回数をできるだけ少なくする方が得策なわけです。 A社が関わる合併の回数はアルファベットA の符号長に相当しますから、合併劇のトータル合併損はまさに平均符号長に等しいわけです。
以上の符号化では、アルファベットごとにハフマン符号を割り付けました。 この平均符号長はまだエントロピーの限界に達していません。 上で得られたハフマン符号の平均符号長は 2.2 ビットです。 一方、この情報源のエントロピーは 2.17 ビットです。 両者の差は 0.03 ビットです。 この差をさらに縮めるには、情報源を拡大してハフマン符号を作ってゆきます。 たとえば、２次拡大情報源 （２文字綴りを出力すると見做す）のシンボルは、ＡＡ、ＡＢ，…、ＨＨ の全部で６４ 個です。 これら２文字綴りの出現確率はそれぞれ、
で計算されます。 このように拡大された情報源に対して、ハフマン符号を設計すると、その平均符号長はさらにエントロピーに近くなることがいえます。 そして、この拡大をどんどん行ってゆくと、最後にはエントロピーに無限に近い符号を作ることができます。 このことを保証する事実は、第１に、次の定理が成り立つこと、
定理
無記憶情報源について、平均符号長Ｌが
を満たす瞬時復号可能な２元（０と１）符号をみつけることができる。
注１： i
番目のアルファベットの生起確率を 
とする。 
の少数点以下を切り上げた整数を i 番目のアルファベットの符号長とする。 この結果はクラフトの不等式を満たすので瞬時復号可能な符号が必ず見つかる（符号とエントロピーを参照）。 そして、このような符号は上の定理を満たすことがいえる。
第２に、次の定理が成り立つこと、
定理
無記憶情報源のｎ次拡大を
で表すと、
ただし、単位は [ ビット／綴り ]。
注２： ０と１を出力する２元情報源を考える。 生起確率を
および 
とする。 この２次拡大は、００、０１、１０、１１の４つを出力し、これらの確率は
である。 このエントロピーが元の情報源のエントロピーの２倍、すなわち 
になることを確認してみよう。 一般的証明は、この計算を一般化して得られる。
から導くことができます。 すなわち、ｎ次拡大の平均符号長
が
を満たす瞬時復号可能な符号がかならず存在することがいえ、その中でハフマン符号がもっとも良い（コンパクトな）符号になっています。 このように、ｎ
を大きくしてハフマン符号を設計すれば、元の情報源の１アルファベット当りの平均符号長
をかぎりなく真のエントロピー 
に近づけることができるというわけです。
実際に２値無記憶情報源を拡大してハフマン符号を設計し、上の不等式を構成する３つの項をプロットしてみよう。 二つのシンボル”１”と”０”が出力されるとし、”０”の生起確率が
p=0.1 と p=0.2 の場合についてプロットしてみます。 黒が
、オレンジが
、紫が
を表しています。 横軸は拡大次数ですが、左端の n=1 は確率を考慮しない等長符号に相当します。 それぞれの図の下に、n=4
の場合のハフマン符号を示します。
注３： 上の図から分かるように、ハフマン符号の圧縮率（ビット／シンボル）は、情報源の拡大に対して単調減少とは限りません。