高考申論題
114年
[電信工程] 通信與系統
第 八 題
霍夫曼訊源編碼（Huffman source coding）是一種無失真資料壓縮的熵（entropy）編碼演算法。考慮一個包含 12 個不同輸出、每一個出現機會均等（equally likely）的訊號源，請利用霍夫曼編碼對該訊號源進行編碼，並求編碼後的平均碼長（average word-length）。（10 分）
📝 此題為申論題
思路引導 VIP
看到這題先想：霍夫曼編碼的核心是每次挑選機率最小的兩個節點進行合併。由於 12 個訊號機率皆為 1/12，我們可以直接模擬貪婪合併過程，從 12 個 1/12 兩兩合併成 6 個 2/12，依此類推建構出二元樹，最後計算每個符號在樹狀圖中對應的深度，即為其編碼後的碼長，進而求得加權平均碼長。
🤖
AI 詳解
AI 專屬家教
【解題思路】利用霍夫曼編碼（Huffman coding）演算法，每次挑選機率最小的兩個節點進行合併以建構二元樹，最後依據樹的深度決定各符號的碼長並計算期望值。 【詳解】 已知：
▼ 還有更多解析內容
霍夫曼訊源編碼
💡 透過合併最小機率節點建構二元樹，實現平均碼長極小化的無失真壓縮。
🔗 霍夫曼編碼演算與計算流程
- 1 初始機率排序 — 列出所有符號及其出現機率，並由小到大排列。
- 2 二元樹合併 — 挑選機率最小的兩個節點合併成新節點，重複至剩下根節點。
- 3 路徑編碼分配 — 由根向葉出發，分支分別賦予 0 或 1，決定各符號碼長。
- 4 平均碼長計算 — 利用公式 E[L] = Σ (Pi * Li) 求出期望值。
↓
↓
↓
🔄 延伸學習：進一步可計算編碼效率 η = Entropy / Average Length
