資訊理論與編碼基礎
想對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。若把0與1兩個都當作長度1的碼字，其他碼字一定會以其中之一開頭。