可変長符号
情報源の各シンボルが異なる符号語に写像される場合、すなわち、情報源シンボルから符号語への写像が単射である場合、符号が非特異(non-singular)であるという。
例えば、写像 M 1 = { a ↦ 0 , b ↦ 0 , c ↦ 1 } {\displaystyle M_{1}=\{\,a\mapsto 0,b\mapsto 0,c\mapsto 1\,\}} は、"a"と"b"の両方が同じビット列"0"に写像されるため、非特異ではない(特異(singular)である)。この写像を拡張すると、非可逆符号になる。このような特異符号は、情報の損失が許容可能である場合(音声や映像の圧縮など)には有用である。
写像 M 2 = { a ↦ 1 , b ↦ 011 , c ↦ 01110 , d ↦ 1110 , e ↦ 10011 , f ↦ 0 } {\displaystyle M_{2}=\{\,a\mapsto 1,b\mapsto 011,c\mapsto 01110,d\mapsto 1110,e\mapsto 10011,f\mapsto 0\}} は非特異である。その拡張は可逆圧縮となり、一般的なデータ送信に有用である(ただし、この機能は必ずしも必要ではない)。非特異符号は情報源よりも必ずしも小さくなる必要はない。多くの応用において、符号長が長くなることが有用な場合もある。例えば、符号化や伝送時の誤りを検出・復旧するため、セキュリティアプリケーションでは検出不能な改竄から情報を保護するためなどである。
可変長符号の利点は、あまり出現しない情報源シンボルには長い符号語を、よく出現する情報源シンボルには短い符号語を割り当てることができ、それによって符号長の期待値が短くなることである。前節の接頭符号の例で、(a, b, c, d) の出現確率が ( 1 2 , 1 4 , 1 8 , 1 8 ) {\displaystyle \textstyle \left({\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{8}}\right)} であったとき、情報源シンボルを表すのに必要な符号文字列の符号長の期待値は、次のようになる。
1 × 1 2 + 2 × 1 4 + 3 × 1 8 + 3 × 1 8 = 7 4 {\displaystyle 1\times {\frac {1}{2}}+2\times {\frac {1}{4}}+3\times {\frac {1}{8}}+3\times {\frac {1}{8}}={\frac {7}{4}}} .
この情報源のエントロピーは1シンボル当たり1.7500ビットであるので、この符号は情報源を誤りなしで復号できるように情報源を可能な限り圧縮する。