情報理論と符号の基礎
0と1からなる接頭符号を作っている。長さ2の符号語 00 と 01 をすでに使っているとき、接頭符号の条件を保ったまま追加できる、長さ3の符号語の最大の個数はどれか。
- A4個
- B6個
- C8個
答えと解説を見る
正解：A. 4個
長さ3のビット列は 2³ = 8 通りありますが、00 や 01 で始まる 000、001、010、011 の4つは使えません。残りの 100、101、110、111 の4つは、00 とも 01 とも先頭部分の関係にならないので、すべて追加できます。クラフトの不等式でも、2/4 + n/8 ≤ 1 から n ≤ 4 となります。
- A. 正しい。1で始まる長さ3のビット列4つが使えます。
- B. 6個は、長さ3のビット列8通りから、使った符号語の数2を引いた値です。00 と 01 はそれぞれ長さ3のビット列2つずつの先頭部分になるので、使えないのは4つです。
- C. 8個は長さ3のビット列のすべてで、00 や 01 で始まるものも含んでいます。