第 一 題

看到求資訊熵(entropy)，立刻聯想 Shannon Entropy 的定義公式 H = -∑ p_i log₂(p_i)。題目特別標註「列出算式即可」，因此只需寫出嚴謹的定義式並將五個機率值正確代入，標明單位 (bits/symbol) 即可拿滿分。

霍夫曼編碼（Huffman Coding）的核心原則是「由下而上，貪婪合併」。解題時，先將符號依發生機率由大至小排列，每次挑選機率最小的兩個節點合併，直到所有節點合併成機率為 1 的根節點。最後再由根節點往下分配二元碼（如左分支為0、右分支為1），即可得到最佳變動長度編碼。

看到求「平均碼長」的題型且已知各符號機率，若無指定編碼方式，應立即聯想使用霍夫曼編碼（Huffman Coding）來建構最佳編碼樹。透過將最小機率逐步合併找出各符號的最佳碼長（$l_i$），再代入平均碼長定義公式 $L = \sum p_i l_i$ 進行求解。

首先需建立霍夫曼樹（Huffman Tree），將各符號依機率由大到小排列，每次挑選兩個最小的機率相加合併成新節點，並重新排序，重複此步驟直到總和為1。接著對分支分配位元（如：大機率給0、小機率給1），求出每個符號的霍夫曼編碼，最後再將待傳輸的序列依序替換為對應的編碼即可。