情報理論と符号の基礎
4つの記号A〜Dに、次の長さ(ビット数)の符号語を割り当てて、0と1からなる接頭符号を作りたい。作ることができる符号長の組み合わせはどれか。
- AA: 1、B: 2、C: 3、D: 3
- BA: 1、B: 2、C: 2、D: 3
- CA: 1、B: 1、C: 2、D: 3
答えと解説を見る
正解：A. A: 1、B: 2、C: 3、D: 3
符号長が l₁、l₂、… の接頭符号を作れるのは、クラフトの不等式 Σ 2^(−lᵢ) ≤ 1 が成り立つときです。1、2、3、3 では 1/2 + 1/4 + 1/8 + 1/8 = 1 なので作れ、例えば 0、10、110、111 になります。1、2、2、3 では 1/2 + 1/4 + 1/4 + 1/8 = 9/8、1、1、2、3 では 1/2 + 1/2 + 1/4 + 1/8 = 11/8 で、どちらも1を超えるので作れません。
- A. 正しい。2^(−l) の和がちょうど1で、0、10、110、111 のように作れます。
- B. 和が 9/8 で1を超えます。長さ1の0と長さ2の10、11で、ビット列の始まり方をすべて使い切るので、長さ3の符号語を置けません。
- C. 和が 11/8 で1を超えます。長さ1の符号語を0と1の2つ使うと、ほかの符号語はすべて、そのどちらかで始まってしまいます。