くらふとのふとうしき
0と1からなる符号で、符号長が l₁, l₂, …, lₙ の接頭符号を作れるための必要十分条件 Σ 2^(−lᵢ) ≤ 1 を表す不等式。長さlの符号語を1つ使うと、それで始まるビット列がすべて使えなくなり、全体の 2^(−l) を占めると考えると分かりやすい。例えば長さ1、2、3、3では和がちょうど1になり、0、10、110、111 のように作れる。1通りに復号できるどのような符号もこの不等式を満たす(マクミランの定理)ので、符号長を決めるときは、接頭符号の中から選べば十分である。
「クラフトの不等式」は、1分野の2問の練習問題に出てきます(情報理論と符号の基礎など)。
この用語の分野: 情報理論と符号の基礎
正解：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 となります。
符号長が l₁、l₂、… の接頭符号を作れるのは、クラフトの不等式 Σ 2^(−lᵢ) ≤ 1 が成り立つときです。
4つの記号A〜Dに、次の長さ(ビット数)の符号語を割り当てて、0と1からなる接頭符号を作りたい。作ることができる符号長…クラフトの不等式でも、2/4 + n/8 ≤ 1 から n ≤ 4 となります。
0と1からなる接頭符号を作っている。長さ2の符号語 00 と 01 をすでに使っているとき、接頭符号の条件を保ったまま…Amazonの検索結果へのリンクです。Amazonのアソシエイトとして、半導体教室は適格販売により収入を得ています。
接頭符号 可逆圧縮 情報エントロピー 情報量 前方誤り訂正(FEC) 相互情報量 二元対称通信路 ハフマン符号 ハミング距離 ハミング符号