Kraftの不等式 (Kraft's inequality)

有限個のアルファベット \(x_1,\ldots,x_n\) を符号化する場合に, アルファベット \(x_i\) を符号化したときの符号長を \(L(x_i)\) とする. この符号は,符号語列を復号して,元のアルファベット列を復元できる一意に復号可能な符号 (uniquely decodable code) であるとする. ここで,符号が語頭符号となるには,次のKraftの不等式が成立ことが必要十分条件: \[\sum_{i=1}^n 2^{-L(x_i)}\le 1\] ここで,\(P(x_i)=2^{-L(x_i)}\) とすると,\(P(x_i)\) は劣確率分布となる.

-- しましま

関連項目

リンク集

関連文献


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:11:08 (2490d)