資訊理論與編碼基礎
正在製作由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開頭的4個長度3位元串都可以使用。
- B. 6個是長度3位元串的8種減去已使用的碼字數2的值。但 00 與 01 各自是2個長度3位元串的開頭部分，因此不能使用的是4個。
- C. 8個是長度3的所有位元串，也包含以 00 或 01 開頭的位元串。