什麼是克拉夫特不等式

表示由0與1構成之碼中,能做成碼長為 l₁, l₂, …, lₙ 之前綴碼的充要條件 Σ 2^(−lᵢ) ≤ 1 的不等式。使用1個長度l的碼字後,以它開頭的位元串全部不能再用,相當於占去全體的 2^(−l),這樣想就容易理解。例如長度1、2、3、3的和恰好為1,可以做成 0、10、110、111。任何能唯一解碼的碼都滿足此不等式(麥克米倫定理),因此決定碼長時,只要從前綴碼中選擇就足夠了。

日文名稱: クラフトの不等式

「克拉夫特不等式」出現在1領域的2道練習題中(資訊理論與編碼基礎等)。

這個名詞所屬的領域: 資訊理論與編碼基礎

練習克拉夫特不等式的題目

想對4個符號A~D分配下列長度(位元數)的碼字,做成由0與1構成的前綴碼。能做成前綴碼的碼長組合為下列何者?

  1. AA: 1、B: 2、C: 3、D: 3
  2. BA: 1、B: 2、C: 2、D: 3
  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,因此無法做成。

正在製作由0與1構成的前綴碼,已經使用了長度2的碼字 00 與 01。在維持前綴碼條件下,可以追加之長度3碼字的最大個數為下列何者?

  1. A4個
  2. B6個
  3. 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。

解析中的「克拉夫特不等式」

出現「克拉夫特不等式」的題目(2題)

  1. 想對4個符號A~D分配下列長度(位元數)的碼字,做成由0與1構成的前綴碼。能做成前綴碼的碼長組合為下列何者?
  2. 正在製作由0與1構成的前綴碼,已經使用了長度2的碼字 00 與 01。在維持前綴碼條件下,可以追加之長度3碼字的最大個數為下列何者?

相關名詞

前綴碼 二元對稱通道 互資訊 平均碼長 同位位元 有失真壓縮 行程長度編碼(RLE) 前向錯誤更正(FEC) 無失真壓縮 資訊量

前往名詞解釋列表