龍華科技大學數位典藏論文

Transcription

1 龍 華 科 技 大 學 電 子 工 程 研 究 所 碩 士 學 位 論 文 使 用 FPGA 完 成 低 成 本 霍 夫 曼 碼 解 碼 器 Using FPGA Hardware Implementation of Huffman Decoder 研 究 生 : 周 文 正 指 導 教 授 : 吳 東 旭 博 士 中 華 民 國 九 十 九 年 七 月

2 摘 要 論 文 名 稱 : 使 用 FPGA 完 成 低 成 本 霍 夫 曼 碼 解 碼 器 頁 數 :48 校 所 別 : 龍 華 科 技 大 學 畢 業 時 間 : 九 十 八 學 年 度 第 二 學 期 研 究 生 : 周 文 正 研 究 所 : 電 子 工 程 研 究 所 學 位 : 碩 士 指 導 教 授 : 吳 東 旭 博 士 關 鍵 詞 : 霍 夫 曼 碼 在 場 效 可 程 式 化 邏 輯 陣 列 編 碼 字 長 度 可 變 長 度 編 碼 霍 夫 曼 編 碼 法 為 可 變 長 度 編 碼 中 最 為 著 名 的 一 種, 廣 泛 的 使 用 在 各 種 資 料 壓 縮 處 理 上 本 文 使 用 一 個 新 的 高 效 能 演 算 法, 將 要 處 理 的 符 號 建 立 成 一 顆 霍 夫 曼 樹, 再 將 此 二 元 樹 視 為 狀 態 圖, 並 將 狀 態 圖 轉 換 成 搜 尋 表, 以 有 限 狀 態 機 的 方 式 配 合 搜 尋 表 來 完 成 解 碼 的 動 作, 最 後 本 文 使 用 此 搜 尋 表 來 設 計 電 路, 以 FPGA 來 完 成 霍 夫 曼 解 碼 電 路 的 設 計 文 中 的 演 算 法, 將 所 編 碼 好 的 符 號 以 陣 列 的 方 式 儲 存, 並 視 為 搜 尋 表, 使 用 廣 度 優 先 搜 尋, 並 以 佇 列 來 協 助 產 生 搜 尋 表, 使 用 文 中 的 演 算 法 設 計 硬 體 電 路, 在 循 序 電 路 上 可 以 大 大 的 降 低 邏 輯 元 素 之 使 用 率 在 處 理 符 號 數 較 少 與 符 號 數 較 多 的 硬 體 解 碼 電 路 上, 本 文 的 方 法 與 其 他 方 法 比 較, 在 循 序 電 路 之 邏 輯 元 素 使 用 率 上 降 低 顯 著, 本 電 路 具 有 偵 錯 的 功 能, 能 偵 測 出 有 錯 誤 的 編 碼 i

3 ABSTRACT Title:Using FPGA Hardware Implementation of Huffman Decoder Pages:48 School:Lunghwa University of Science and Technology Department:Electrical Engineering Time:July, 2010 Researcher:Wen-Zheng Zhou Degree:Master Advisor:Dong-Shiuh Wu Keywords:Huffman code Field-Programmable Gate Arrays,FPGA Codeword Length Variable-length code Huffman coding is one of the well-know Variable-length coding (VLC) methods, VLC is widely used technique for data compression. In this paper, use a new high-performance algorithms, the symbols will have to deal with the establishment of a Huffman tree, then this binary tree as a state diagram. Translate the state diagram to a look-up table (LUT). We use finite state machine with the LUT to complete the decoding, the final table in this article use LUT to design circuits to FPGA to implement the design of Huffman decoding circuit. We use a two-dimensional array to store all of the symbols for encoding, and as a LUT. And use of breadth-first search to create this LUT. In hardware circuit use design the algorithm, in sequential logic circuits can reduce the use of elements. Regardless of the number of symbols, in hardware decoding circuits, the method is better than others, in the sequential logic circuit elements significantly lower utilization rates, the circuit with debugging capabilities to detect coding errors. ii

4 目 錄 摘 要... i ABSTRACT... ii 目 錄... iii 表 目 錄... v 圖 目 錄... vi 第 一 章 緒 論 研 究 動 機 與 目 的 研 究 方 法 霍 夫 曼 樹 霍 夫 曼 編 碼 相 關 研 究 及 文 獻 探 討 論 文 架 構... 7 第 二 章 樹 狀 結 構 樹 的 定 義 樹 的 記 憶 體 表 示 法 二 元 樹 二 元 樹 的 特 例 二 元 樹 的 記 憶 體 表 示 法 二 元 樹 的 尋 訪 第 三 章 壓 縮 霍 夫 曼 編 碼 表 資 料 儲 存 方 式 編 碼 長 度 演 算 法 霍 夫 曼 編 碼 演 算 法 壓 縮 結 果 壓 縮 霍 夫 曼 編 碼 之 記 憶 體 使 用 空 間 探 討 解 碼 過 程 與 例 題 解 碼 第 四 章 使 用 FPGA 完 成 霍 夫 曼 解 碼 器 循 序 電 路 架 構 多 工 器 電 路 架 構 電 路 模 擬 模 擬 軟 體 Quartus II 簡 介 循 序 電 路 模 擬 多 工 器 電 路 模 擬 結 果 與 比 較 第 五 章 使 用 高 效 能 記 憶 體 與 快 速 演 算 法 製 作 電 路 iii

5 5.1 建 立 霍 夫 曼 樹 建 立 LUT 搜 尋 表 解 碼 演 算 法 電 路 架 構 電 路 模 擬 與 結 果 第 六 章 實 作 結 果 與 比 較 壓 縮 霍 夫 曼 編 碼 表 之 解 碼 電 路 實 作 高 效 能 記 憶 體 與 快 速 的 霍 夫 曼 解 碼 演 算 法 之 解 碼 電 路 實 作 結 果 與 比 較 第 七 章 結 論 參 考 文 獻 iv

6 表 目 錄 表 個 符 號 的 霍 夫 曼 編 碼 表... 3 表 3.1 以 陣 列 儲 存 的 符 號 表 表 3.2 符 號 對 應 的 CL 表 3.3 各 CL 的 符 號 總 數 表 3.4 新 的 霍 夫 曼 編 碼 表 表 3.5 壓 縮 後 的 霍 夫 曼 編 碼 表 表 4.1 使 用 EP1S10F484C5 之 8 個 符 號 的 循 序 電 路 比 較 表 4.2 使 用 EP1S10F484C5 之 8 個 符 號 的 多 工 器 電 路 比 較 表 個 符 號 之 搜 尋 表 (LUT) 表 5.2 使 用 EP1S10F484C5 之 8 個 符 號 的 循 序 電 路 比 較 表 6.1 使 用 EP1S10F484C5 之 66 個 符 號 的 循 序 電 路 比 較 表 6.2 使 用 EP1S10F484C5 之 66 個 符 號 的 多 工 器 電 路 比 較 v

7 圖 目 錄 圖 1.1 霍 夫 曼 演 算 法 之 流 程 圖... 2 圖 1.2 取 出 兩 筆 頻 率 最 小 的 符 號, 合 併 成 一 顆 二 元 樹... 4 圖 1.3 將 符 號 S 5 /8 與 N 節 點 合 併 成 新 根 節 點 P... 4 圖 1.4 表 1.1 對 應 之 霍 夫 曼 樹... 5 圖 2.1 典 型 的 樹 狀 結 構... 8 圖 2.2 簡 單 的 樹 狀 結 構 說 明 圖... 9 圖 2.3 圖 2.2 之 鏈 結 表 示 法 圖 2.4 深 度 為 4, 共 有 個 節 點 之 完 滿 二 元 樹 圖 2.5 完 整 二 元 樹 圖 2.6 歪 斜 樹 圖 2.7 單 邊 成 長 樹 圖 2.8 鏈 結 串 列 表 示 法 之 節 點 結 構 圖 2.9 二 元 樹 的 鏈 結 表 示 法 圖 2.10 二 元 樹 的 陣 列 表 示 法 圖 2.11 運 算 式 二 元 樹 之 表 示 法 圖 3.1 以 表 1.1 為 例 之 表 3.2 對 應 的 霍 夫 曼 樹 圖 3.2 新 的 霍 夫 曼 編 碼 演 算 法 圖 3.3 建 立 LUT 表 演 算 法 圖 3.4 霍 夫 曼 碼 解 碼 演 算 法 圖 4.1 解 碼 符 號 S 0 之 循 序 電 路 架 構 圖 圖 4.3 Quartus II 軟 體 設 計 流 程 圖 4.4 Example 2 之 循 序 電 路 模 擬 圖 圖 4.5 Example 2 之 多 工 器 電 路 模 擬 波 形 圖 圖 個 符 號 之 狀 態 圖 圖 5.2 Example 3 之 連 續 3 個 符 號 解 碼 過 程 圖 5.3 解 碼 符 號 S 0 之 循 序 電 路 架 構 圖 圖 5.4 Example 3 之 循 序 電 路 模 擬 波 形 圖 圖 個 符 號 之 壓 縮 霍 夫 曼 表 循 序 電 路 模 擬 圖 圖 個 符 號 之 壓 縮 霍 夫 曼 表 多 工 器 電 路 模 擬 圖 圖 個 符 號 之 高 效 能 記 憶 體 與 快 速 的 霍 夫 曼 解 碼 演 算 法 循 序 電 路 模 擬 圖 vi

8 第 一 章 緒 論 1.1 研 究 動 機 與 目 的 隨 著 時 代 的 演 進, 圖 片 (JPEG) 高 清 晰 度 電 視 (HDTV) 影 音 多 媒 體 (MPEG-1, -2, -4) 等, 需 要 無 失 真 壓 縮 以 及 即 時 運 算 的 解 碼, 以 可 變 長 度 編 碼 (variable-length coding, VLC) 的 方 式 來 進 行 資 料 的 處 理, 可 以 有 效 率 的 完 成 編 碼 在 可 變 長 度 編 碼 上, 以 霍 夫 曼 在 1952 年 所 提 出 的 霍 夫 曼 編 碼 法 (Huffman s Encoding)[6] 為 最 著 名 的 一 種 編 碼 方 式, 他 的 特 點 是 根 據 每 一 個 符 號 出 現 的 機 率 不 同, 編 製 出 不 同 長 度 的 二 進 位 碼 霍 夫 曼 編 碼 法 是 根 據 各 個 資 料 中 所 出 現 的 符 號 之 頻 率 多 寡, 加 以 編 碼, 進 而 達 到 壓 縮 資 料 的 方 法, 其 原 理 是 先 統 計 所 要 處 理 的 資 料 中 各 個 符 號 之 頻 率 後, 再 依 照 頻 率 由 小 到 大 的 建 立 起 霍 夫 曼 樹 (Huffman tree) 霍 夫 曼 編 碼 是 依 符 號 出 現 的 頻 率 來 決 定 編 碼 的 長 度, 符 號 出 現 的 頻 率 越 高, 所 對 應 的 編 碼 越 短, 符 號 出 現 的 頻 率 越 低, 所 編 列 的 碼 越 長 霍 夫 曼 編 碼 法 已 經 廣 泛 的 使 用 在 圖 文 資 料 及 影 音 的 壓 縮 上, 透 過 這 一 項 技 術 能 夠 使 較 大 的 檔 案, 以 較 小 的 傳 輸 量 與 儲 存 空 間, 流 通 於 有 限 頻 寬 的 網 際 網 路 與 佔 據 記 憶 體 的 空 間 霍 夫 曼 編 碼 是 一 種 非 常 有 效 率 之 壓 縮 技 術, 也 很 容 易 的 以 軟 體 的 方 式 來 實 現, 根 據 其 解 碼 的 方 法, 文 中 使 用 硬 體 的 方 式 來 實 現 高 速 霍 夫 曼 解 碼 器, 以 達 到 更 好 的 解 碼 速 度 本 論 文 使 用 壓 縮 霍 夫 曼 表 演 算 法, 根 據 演 算 法 所 產 生 的 霍 夫 曼 碼, 以 區 間 的 方 式 規 劃 成 一 個 表 格, 再 將 此 表 格 視 為 搜 尋 表 來 完 成 解 碼, 最 後 分 別 以 循 序 電 路 與 多 工 器 電 路 來 完 成 霍 夫 曼 解 碼 器 的 組 合 電 路, 並 以 Altera 公 司 生 產 之 Stratix EP1S40F780C5 FPGA(Field-Programmable Gate Array) 來 實 作 實 作 模 擬 的 結 果 顯 示, 以 多 工 器 的 方 式 來 設 計 霍 夫 曼 解 碼 器 可 以 有 效 的 降 低 邏 輯 元 素 之 個 數, 且 工 作 的 速 度 較 循 序 電 路 快, 如 果 以 VLSI 技 術 來 實 現 我 們 的 演 算 法, 相 信 會 更 進 一 步 的 縮 小 整 體 面 積, 降 低 成 本 1

9 1.2 研 究 方 法 本 論 文 中, 根 據 霍 夫 曼 編 碼 法, 使 用 一 種 新 的 方 法, 不 用 建 立 霍 夫 曼 樹 就 可 以 取 得 各 個 符 號 的 編 碼 長 度, 首 先 將 需 要 處 理 的 符 號 用 陣 列 加 以 儲 存, 再 對 符 號 所 出 現 的 頻 率 大 小 進 行 排 序, 將 頻 率 最 小 的 兩 個 符 號, 存 放 至 新 的 陣 列, 將 兩 個 頻 率 的 值 加 總, 存 回 原 陣 列 重 新 排 序, 重 複 前 面 的 動 作 直 到 所 有 的 符 號 都 處 理 完 畢 然 後 給 予 新 的 陣 列 每 一 個 符 號 相 對 應 的 碼 長 度, 接 著 依 編 碼 的 長 度 重 新 編 碼, 使 得 具 相 同 編 碼 長 度 的 霍 夫 曼 編 碼, 其 二 進 位 值 可 以 連 續 最 後 將 新 的 霍 夫 曼 碼 表, 壓 縮 成 一 個 搜 尋 表 再 針 對 每 一 個 不 同 的 碼 長 度, 利 用 壓 縮 的 搜 尋 表 進 行 解 碼 文 中 使 用 此 搜 尋 表 來 設 計, 並 以 FPGA 實 現 霍 夫 曼 解 碼 器, 在 霍 夫 曼 解 碼 器 上, 本 文 中 分 別 使 用 循 序 電 路 以 及 多 工 器 電 路 來 完 成, 並 比 較 兩 者 模 擬 之 結 果, 在 本 章 節 中, 將 會 介 紹 霍 夫 曼 樹 以 及 霍 夫 曼 編 碼 與 相 關 的 研 究 述 論 流 程 開 始 將 資 料 元 素 遞 減 排 序 Yes 序 列 中 只 有 一 個 元 素? No 取 出 頻 率 最 小 的 兩 個 元 素, 合 併 成 一 顆 二 元 子 樹, 其 根 節 點 為 頻 率 之 和 將 此 根 節 點 新 增 至 序 列 中 結 束 圖 1.1 霍 夫 曼 演 算 法 之 流 程 圖 2

10 1.2.1 霍 夫 曼 樹 霍 夫 曼 樹 是 利 用 二 元 樹 的 方 式 完 成 之 資 料 壓 縮 演 算 法, 根 據 資 料 元 素 出 現 的 頻 率 多 寡 來 建 立 的 二 元 樹, 以 葉 節 點 來 儲 存 符 號 將 符 號 出 現 的 頻 率 遞 減 排 序, 取 出 頻 率 最 小 的 兩 個 符 號, 合 併 成 一 顆 二 元 子 樹, 符 號 為 二 元 子 樹 的 葉 節 點 (leaf node), 將 符 號 的 頻 率 相 加, 所 得 到 的 值 為 此 二 元 子 樹 的 根 節 點 (root node), 並 將 此 根 節 點 新 增 至 序 列 中, 同 樣 再 重 新 排 序 取 出 頻 率 最 小 的 兩 個 符 號 建 立 二 元 子 樹, 直 到 所 有 的 符 號 都 處 理 完 畢, 就 完 成 了 霍 夫 曼 樹, 如 圖 1.1 的 流 程 圖 所 示 霍 夫 曼 樹 是 一 種 二 元 樹 的 應 用, 可 以 用 來 進 行 編 碼 與 解 碼, 以 達 到 資 料 壓 縮 的 目 的, 霍 夫 曼 樹 根 據 每 一 個 符 號 所 出 現 的 頻 率, 建 立 起 相 對 應 的 二 元 樹, 並 將 符 號 置 於 葉 節 點, 而 且 每 一 個 符 號 的 編 碼 長 度 都 不 一 樣 藉 下 來 我 們 將 以 一 個 例 子 來 建 立 霍 夫 曼 樹 表 個 符 號 的 霍 夫 曼 編 碼 表 Symbol Frequency Huffman code S S S S S S S S 假 設 所 要 處 理 的 符 號 為 集 合 S,S={S 0, S 1, S 2, S 3, S 4, S 5, S 6, S 7 }, 每 一 個 符 號 對 應 出 現 的 頻 率 為 集 合 F,F={33, 22, 20, 16, 15, 8, 4, 2}, 如 表 1.1 所 示 首 先 將 符 號 按 照 頻 率 的 大 小 遞 減 排 序, 其 排 序 為 S 0 /33, S 1 /22, S 2 /20, S 3 /16, S 4 /15, S 5 /8, S 6 /4, S 7 /2 接 著 取 出 最 小 的 兩 筆 資 料 S 6 /4, S 7 /2, 將 這 兩 個 符 號 合 併 成 一 個 二 元 樹, 其 根 節 點 的 6 為 兩 個 頻 率 的 和, 如 圖 1.2 所 示 3

11 圖 1.2 取 出 兩 筆 頻 率 最 小 的 符 號, 合 併 成 一 顆 二 元 樹 接 下 來 將 合 併 後 的 二 元 樹 之 根 節 點 6, 從 新 放 回 序 列 中, 同 樣 再 次 遞 減 排 序, 其 順 序 變 為 S 0 /33, S 1 /22, S 2 /20, S 3 /16, S 4 /15, S 5 /8, N/6, 接 著 同 樣 取 出 兩 筆 最 小 頻 率 S 5 /8, N/6, 合 併 成 一 顆 新 的 的 節 點 P 為 根 的 二 元 樹, 如 圖 1.3 所 示 圖 1.3 將 符 號 S 5 /8 與 N 節 點 合 併 成 新 根 節 點 P 最 後, 同 樣 將 新 的 根 節 點 P 放 回 序 列 中, 重 新 進 行 遞 減 排 序, 接 著 取 出 兩 筆 最 小 頻 率 的 資 料, 再 將 資 料 合 併 成 一 顆 新 的 二 元 樹, 直 到 所 有 的 符 號 都 處 理 完 畢 為 止, 就 完 成 了 霍 夫 曼 樹, 如 圖 1.4 所 示, 其 中 只 要 保 留 二 元 樹 之 葉 節 點 的 符 號 即 可 4

12 圖 1.4 表 1.1 對 應 之 霍 夫 曼 樹 霍 夫 曼 編 碼 一 般 表 示 資 料 的 方 法 是 使 用 二 元 碼 (binary code), 這 種 編 碼 方 式 會 使 用 相 同 位 元 數 目 的 固 定 長 度 二 元 碼 (fixed-length binary code) 來 表 示 每 一 個 資 料 符 號 (data symbol) 若 每 一 個 資 料 符 號 的 出 現 機 率 已 知, 則 我 們 可 以 使 用 可 變 長 度 二 元 碼 (variable-length binary code) 來 獲 得 較 有 效 率 的 編 碼 霍 夫 曼 編 碼 的 基 本 觀 念 是 將 資 料 中 的 資 料 出 現 頻 率 較 多 次 的 用 較 短 的 代 碼 來 編 碼 ; 資 料 出 現 頻 率 較 少 次 的 用 較 長 的 代 碼 來 編 碼 如 表 1.1 為 一 個 簡 單 的 霍 夫 曼 編 碼 範 例 其 相 對 應 的 霍 夫 曼 樹 (Huffman tree) 如 圖 相 關 研 究 及 文 獻 探 討 霍 夫 曼 解 碼 的 方 法, 從 輸 入 的 二 進 位 串 流 中, 循 序 的 讀 取 二 進 位 串, 將 所 讀 取 到 的 二 元 值 遞 迴 追 蹤 所 建 立 的 霍 夫 曼 樹, 直 到 葉 節 點 如 果 以 陣 列 儲 存 霍 夫 曼 樹 所 需 要 的 空 間 可 能 高 達 O(2 h ),h 為 霍 夫 曼 樹 的 高, 解 碼 符 號 需 要 的 時 間 為 O(h), 霍 夫 曼 編 碼 在 符 號 數 較 多 及 符 號 出 現 頻 率 差 異 過 大 的 情 況 之 下, 會 導 致 單 邊 成 長 5

13 發 生 (single-side grown), 不 僅 儲 存 的 空 間 變 大, 在 解 碼 的 時 間 上 也 會 增 加 許 多, 因 此 有 許 多 論 文 [2], [3], [7] ~ [11] 都 提 出 解 決 的 方 法, 如 何 使 得 儲 存 的 記 憶 體 空 間 減 少 和 加 快 解 碼 時 間 Hashemian[7] 就 提 出 用 叢 集 的 方 式 來 解 碼, 在 叢 集 內 的 符 號 可 以 直 接 進 行 解 碼 出, 而 未 解 碼 出 的 符 號 經 由 S-Tree 對 映 到 下 一 個 叢 集, 再 繼 續 進 行 解 碼 動 作, 記 憶 體 空 間 複 雜 度 介 於 O(n) 到 O(2 h ) 之 間, n 為 符 號 個 數 另 在 [8] 也 提 出 將 所 有 未 滿 最 大 CL(Codeword Length) 長 度 的 編 碼, 將 不 足 的 碼 長 度 填 滿 0, 並 儲 存 於 陣 列, 解 碼 時 讀 取 最 大 CL 長 度 的 編 碼, 再 依 序 對 陣 列 作 比 較 的 動 作, 直 到 找 到 相 對 應 的 符 號, 所 需 要 的 記 憶 空 間 為 2n + 3l + 1, 解 碼 時 間 為 2 + (l - 1), 而 l 為 搜 尋 表 的 列 數,2 為 加 法 或 減 法 時 間 Wang et al. [9] 將 建 立 好 的 霍 夫 曼 碼 以 最 大 的 CL 填 滿, 設 定 起 始 位 置 及 結 束 位 置, 再 依 照 起 始 位 置 從 小 到 大 排 列, 而 每 次 解 碼 讀 取 最 大 長 度 的 CL, 比 對 在 相 符 n 合 的 區 間 即 為 對 應 的 符 號, 所 使 用 的 記 憶 體 空 間 為 hn + 1, 搜 尋 符 array size 號 所 需 要 的 時 間 為 O(log n ) Chen et al. [10] 使 用 陣 列 儲 存 符 號 與 頻 率, 並 將 頻 率 加 總 作 為 解 碼 的 依 據, 不 在 加 總 表 裡 的 編 碼, 表 示 錯 誤 代 碼, 所 需 要 的 記 憶 空 間 3 n 為 n + log n 2 Chung[11] 提 出 使 用 跳 躍 數 值 (jump values), 將 符 號 及 節 點 儲 存 在 陣 列 之 中, 由 跳 耀 數 值 來 比 對 找 尋 符 號, 所 需 求 的 空 間 在 (2n 3), 對 於 尋 找 符 號 的 時 間 複 雜 度 屬 於 O(h) [2] 將 狀 態 圖 作 為 搜 尋 表, 儲 存 於 陣 列, 所 花 費 的 空 間 為 (2n 2), 時 間 複 雜 度 在 O(h), 並 且 具 有 除 錯 的 功 能 [3] 以 壓 縮 霍 夫 曼 編 碼 的 方 式, 首 先 取 得 符 號 之 對 應 的 CL, 再 將 符 號 重 新 編 碼, 使 之 編 碼 二 進 位 值 可 以 連 續, 並 以 區 間 的 方 式, 將 相 同 CL 之 符 號 合 併, 取 其 區 間 之 最 大 編 碼 與 區 間 內 之 符 號 個 數 總 合, 最 後 壓 縮 成 搜 尋 表, 使 用 此 搜 尋 表 解 碼, 在 多 符 號 之 處 理 上 也 有 不 錯 的 成 效 6

14 1.3 論 文 架 構 本 論 文 研 究 內 容 分 為 七 個 章 節, 如 下 所 示 : 第 一 章 : 緒 論 此 章 節 說 明 本 論 文 之 研 究 動 機 與 目 的 研 究 的 方 法, 並 介 紹 霍 夫 曼 編 碼 之 相 關 概 念 及 相 關 研 究 與 本 論 文 內 架 構 第 二 章 : 樹 狀 結 構 第 三 章 : 壓 縮 霍 夫 曼 編 碼 表 第 四 章 : 使 用 FPGA 完 成 壓 縮 霍 夫 曼 編 碼 表 之 解 碼 電 路 實 作 ; 本 章 節 以 一 個 例 子 來 實 作 壓 縮 霍 夫 曼 編 碼 表 之 硬 體 解 碼 器, 分 別 使 用 循 序 電 路 與 多 工 器 電 路 來 實 作, 以 及 呈 現 各 個 電 路 的 模 擬 波 形 圖, 並 且 與 其 他 述 論 比 較 第 五 章 : 使 用 高 效 能 記 憶 體 與 快 速 演 算 法 製 作 電 路 ; 本 章 節 以 相 同 的 例 子 來 製 作 高 效 能 記 憶 體 與 快 速 演 算 法, 使 用 循 序 電 路 進 行 實 作, 呈 現 實 例 的 模 擬 波 形 圖, 並 與 其 他 述 論 比 較 第 六 章 : 實 作 的 結 果 與 比 較 ; 本 章 節 以 一 個 實 際 的 樣 本 來 實 作 霍 夫 曼 解 碼 器, 分 別 使 用 循 序 電 路 與 多 工 器 電 路 來 實 作 此 樣 本, 以 及 呈 現 各 個 電 路 的 模 擬 波 形 圖, 並 且 與 其 他 論 文 比 較 第 七 章 : 結 論 7

15 第 二 章 樹 狀 結 構 樹 狀 結 構 在 電 腦 應 用 上 是 一 個 非 常 重 要 的 結 構, 用 來 描 述 有 分 支 的 結 構, 樹 狀 結 構 的 層 次 分 明 有 條 理, 可 以 明 確 的 顯 示 出 資 料 間 的 從 屬 關 係, 因 此 經 常 被 用 來 整 理 資 料, 如 圖 2.1 就 是 一 個 樹 狀 結 構 樹 中 的 元 樹 以 節 點 (node) 來 表 示, 每 一 個 節 點 可 以 視 為 資 料 與 指 標 組 合 而 成 的 紀 錄, 節 點 之 間 可 以 用 樹 枝 相 連, 代 表 支 幹 (branch) 的 延 伸 節 點 可 以 分 為 : 樹 根 子 節 點 與 葉 節 點 葉 節 點 為 樹 的 終 端 點, 非 終 端 節 點 為 葉 節 點 和 樹 根 之 間 的 節 點 本 章 節 將 著 重 於 樹 狀 結 構 的 介 紹, 例 如 樹 的 表 示 法 二 元 樹 二 元 樹 的 追 蹤 圖 2.1 典 型 的 樹 狀 結 構 2.1 樹 的 定 義 樹 (tree) 是 一 個 節 點 或 許 多 節 點 所 組 合 而 成 的, 包 含 一 個 樹 根 節 點 (root), 其 餘 節 點 分 為 N 個 子 樹,N 0 每 一 個 節 點 所 分 出 來 的 子 樹 個 數 為 該 節 點 的 分 支 度 (degree) 樹 的 節 點 分 為 葉 節 點 或 稱 為 終 端 節 點 以 及 非 終 端 節 點 兩 種, 分 支 度 為 0 的 節 點 為 葉 節 點 8

16 樹 是 由 一 個 或 是 多 個 節 點 所 組 成 的 有 限 集 合, 且 具 有 兩 個 性 質 : 1. 相 連 性 (connected): 節 點 之 間 至 少 必 須 有 一 個 以 上 的 連 結 2. 非 迴 圈 性 (cycle-free): 節 點 與 節 點 之 間 不 能 形 成 無 出 口 的 迴 圈, 圖 2.2 為 簡 單 的 介 紹 圖 2.2 簡 單 的 樹 狀 結 構 說 明 圖 圖 2.2 為 分 支 度 3 的 樹, 樹 根 為 A, 葉 節 點 有 C F H I J K 等 6 個 節 點,B D E G 為 非 終 端 節 點,B D 的 父 節 點 為 A,B 的 子 節 點 有 E F 兩 個, 所 以 B 節 點 的 分 支 度 為 2, 且 E F 互 為 兄 弟 節 點, 此 樹 的 高 度 為 4,B C D 節 點 位 於 階 層 2,E F G H 位 於 階 層 3,I J K 位 於 階 層 4,I 的 祖 先 節 點 有 E B A 三 個 節 點 2.2 樹 的 記 憶 體 表 示 法 由 樹 的 定 義 中 知 道 每 一 個 節 點 的 分 支 度 0, 如 果 用 鏈 結 串 列 表 示, 由 於 每 一 個 節 點 分 支 度 不 一 樣, 因 此 節 點 必 須 有 不 等 數 目 的 欄 對 應 其 分 支 度 的 數 目, 如 圖 2.3 所 示 但 是 在 分 支 度 為 K 的 狀 況 之 下, 由 於 許 多 鏈 結 存 有 空 指 標, 容 易 造 成 空 間 9

17 的 浪 費 ( 圖 2.3 節 點 之 鏈 結 欄 為 0 的 部 份 ), 以 K 元 樹 且 有 N 個 節 點 來 看, 此 樹 狀 結 構 將 會 有 N*K 鏈 結 欄, 不 過 會 有 N*(K - 1) + 1 個 是 屬 於 空 鏈 結, 這 是 因 為 除 了 樹 根 之 外, 每 一 個 非 空 鏈 結 都 指 向 一 個 節 點, 因 此 在 N 個 節 點 中 包 含 了 N 1 個 非 空 節 點, 而 N 個 節 點 的 K 元 樹 鏈 結 欄 有 N*K 個, 所 以 空 鏈 結 個 數 為 NK N + 1 其 K 元 樹 的 浪 費 率 的 式 子 如 下 : N( K 1) + 1 K 元 樹 的 浪 費 率 = NK 以 五 元 樹 來 說 的 話, 其 浪 費 率 約 為 4/5, 以 二 元 樹 之 浪 費 率 約 為 1/2, 所 以 將 樹 改 用 以 二 元 樹 的 方 式 儲 存, 可 以 減 少 空 間 上 的 浪 費 圖 2.3 圖 2.2 之 鏈 結 表 示 法 2.3 二 元 樹 二 元 樹 是 一 顆 空 樹 或 是 由 一 個 樹 根 以 及 兩 個 相 互 分 離 的 二 元 樹 或 稱 為 左 子 樹 以 及 右 子 樹 所 構 成 的 因 為 子 樹 有 左 右 之 分, 所 以 二 元 樹 又 稱 為 有 序 樹 (ordered tree) 二 元 樹 可 以 是 空 集 合, 而 非 空 集 合 的 樹 至 少 要 有 一 個 樹 根, 在 分 支 度 上, 每 一 個 節 點 的 分 支 度 2 二 元 樹 的 特 性 如 下 : 1. 第 i 階 層 的 總 節 點 數 小 於 等 於 2 i-1,i 1 2. 二 元 樹 的 節 點 數 少 於 2 K,K 為 二 元 樹 的 深 度, K 1 10

18 3. 葉 節 點 總 數 等 於 分 支 度 為 2 的 節 點 總 數 加 二 元 樹 的 特 例 1. 完 滿 二 元 樹 : 一 顆 二 元 樹, 若 深 度 為 K 且 含 有 2 K 1 的 節 點, 稱 為 是 深 度 為 K 的 完 滿 二 元 樹 (full binary tree of depth K), 如 圖 2.4 所 示 圖 2.4 深 度 為 4, 共 有 個 節 點 之 完 滿 二 元 樹 2. 完 整 二 元 樹 : 一 顆 二 元 樹, 若 深 度 為 K 而 所 含 的 節 點 數 少 於 2 K 1 個, 但 是 其 節 點 的 編 號 順 序 與 完 滿 二 元 樹 相 同, 稱 為 完 整 二 元 樹, 如 圖 2.5 (a) 完 整 二 元 樹 圖 2.5 完 整 二 元 樹 (b) 非 完 整 二 元 樹 3. 歪 斜 樹 (skewed binary tree): 當 一 顆 二 元 樹, 所 有 的 節 點 都 沒 有 左 子 樹 或 11

19 是 右 子 樹 時, 稱 為 歪 斜 樹 又 可 以 分 為 左 歪 斜 樹 與 右 歪 斜 樹, 如 圖 2.6 所 示 (a) 左 歪 斜 樹 圖 2.6 歪 斜 樹 (b) 右 歪 斜 樹 4. 單 邊 成 長 樹 (single-side g rown tree): 若 二 元 樹 的 每 一 個 非 終 端 節 點 均 有 非 空 的 左 右 子 樹 時 稱 為 單 邊 成 長 樹, 或 是 稱 為 嚴 格 二 元 樹 (strictly binary tree), 如 圖 2.7 所 示 圖 2.7 單 邊 成 長 樹 12

20 2.3.2 二 元 樹 的 記 憶 體 表 示 法 二 元 樹 可 以 用 鏈 結 串 列 和 陣 列 來 表 示, 因 為 二 元 樹 的 一 些 限 制 使 得 製 作 時 較 一 般 的 樹 來 得 容 易 1. 鏈 結 串 列 表 示 法 : 每 一 個 節 點 的 鏈 結 結 構 如 圖 2.8, 分 為 左 子 樹 鏈 結 節 點 資 料 和 右 子 樹 鏈 結 三 個 欄 位 如 圖 2.9(a) 之 二 元 樹 可 以 表 示 成 圖 2.9(b) 鏈 結 串 列 表 示 法 的 優 點 在 於 節 點 的 增 加 或 是 刪 除 非 常 容 易, 只 需 要 安 排 節 點 的 鏈 結 指 標 即 可, 但 是 要 找 出 某 一 個 節 點 的 父 節 點 很 困 難 圖 2.8 鏈 結 串 列 表 示 法 之 節 點 結 構 (a) 二 元 樹 (b) 二 元 樹 (a) 之 鏈 結 表 示 法 圖 2.9 二 元 樹 的 鏈 結 表 示 法 2. 一 維 陣 列 表 示 法 : 二 元 樹 的 第 i 階 層 最 多 共 有 2 i-1 個 節 點 從 樹 根 開 始 的 每 一 階 層 之 節 點 個 數 多 為 , 因 此 很 容 易 算 出 某 一 節 點 在 陣 列 中 的 位 置 以 圖 2.4 來 看, 用 一 維 陣 列 來 表 示 的 話 如 圖 2.10 所 示 已 完 滿 二 元 樹 來 決 定 節 點 自 陣 列 中 的 位 置 是 因 為 其 節 點 個 數 最 多, 這 樣 再 其 他 的 二 元 13

21 樹 以 陣 列 來 表 示 也 都 沒 有 問 題 了 陣 列 表 示 法 的 優 點 在 完 滿 二 元 樹 的 狀 況 之 下 是 最 節 省 空 間 的, 且 非 常 容 易 的 找 出 相 關 父 子 結 點 之 位 置 缺 點 在 於 在 所 建 構 出 的 樹 越 歪 斜, 其 所 浪 費 的 空 間 越 多 與 在 處 理 節 點 的 插 入 和 刪 除 時 必 須 搬 動 大 量 資 料 圖 2.10 二 元 樹 的 陣 列 表 示 法 2.4 二 元 樹 的 尋 訪 在 樹 狀 結 構 上 可 以 執 行 許 多 種 運 算, 其 中 最 常 用 到 的 是 尋 訪 或 是 追 蹤 樹 狀 結 構, 也 就 是 將 整 顆 二 元 樹 的 資 料 讀 取 一 次 以 L D R 分 別 代 表 往 左 移 動 印 出 資 料 與 往 右 移 動, 這 樣 共 有 6 種 組 合, 而 二 元 樹 的 特 性 都 是 由 左 向 右, 所 以 只 剩 下 三 種 : 1. 中 序 (inorder) : 左 子 樹 樹 根 右 子 樹 (LDR) 2. 後 序 (postorder): 左 子 樹 右 子 樹 樹 根 (LRD) 3. 前 序 (preorder): 樹 根 左 子 樹 右 子 樹 (DLR) 我 們 簡 單 的 以 圖 2.11 運 算 式 二 元 樹 來 作 前 序 中 序 與 後 序 之 表 示 法 14

22 圖 2.11 運 算 式 二 元 樹 之 表 示 法 1. 中 序 式 尋 訪 若 樹 根 節 點 不 為 空 節 點, 則 執 行 下 列 步 驟, 其 虛 擬 碼 (pseudo-code) 如 下 所 示 : 1.1 走 訪 左 子 樹 1.2 走 訪 樹 根 1.3 走 訪 右 子 樹 2. 後 序 式 尋 訪 若 樹 根 節 點 不 為 空 節 點, 則 執 行 下 列 步 驟, 其 虛 擬 碼 (pseudo-code) 如 下 所 示 : 2.1 走 訪 左 子 樹 2.2 走 訪 右 子 樹 3.3 走 訪 樹 根 15

23 void inorder(nodetype, tree) { if (tree!= null) { postorder(tree.llink); postorder(tree.rlink); out_system.print(tree.data); } } 3. 前 序 式 尋 訪 若 樹 根 節 點 不 為 空 節 點, 則 執 行 下 列 步 驟, 其 虛 擬 碼 (pseudo-code) 如 下 所 示 : 3.1 走 訪 樹 根 3.2 走 訪 左 子 樹 3.3 走 訪 右 子 樹 void inorder(nodetype, tree) { if (tree!= null) { out_system.print(tree.data); postorder(tree.llink); postorder(tree.rlink); } } 16

24 第 三 章 壓 縮 霍 夫 曼 編 碼 表 在 本 章 節 中, 介 紹 本 文 使 用 的 方 法 來 完 成 霍 夫 曼 編 碼, 不 用 建 立 霍 夫 曼 樹, 即 可 得 到 每 一 個 符 號 對 應 的 碼 長 度, 接 著 依 照 碼 長 度 重 新 編 碼, 使 得 相 同 碼 長 度 的 霍 夫 曼 編 碼 之 編 碼 二 進 位 值 可 以 連 續, 接 著 將 相 同 的 編 碼 長 度 歸 納 為 同 一 個 區 間, 再 將 壓 縮 過 的 編 碼 霍 夫 曼 表, 視 為 一 個 搜 尋 表 [3] 在 後 續 的 章 節 中, 配 合 此 搜 尋 表 來 進 行 硬 體 解 碼 設 計 [4] 3.1 資 料 儲 存 方 式 如 表 1.1 所 示, 假 設 所 要 處 理 的 符 號 為 集 合 S,S={S 0, S 1, S 2, S 3, S 4, S 5, S 6, S 7 }, 每 一 個 符 號 對 應 出 現 的 頻 率 為 集 合 F,F={33, 22, 20, 16, 15, 8, 4, 2}, 本 論 文 所 使 用 的 編 碼 方 法, 不 用 建 立 霍 夫 曼 樹 即 可 產 生 每 一 個 符 號 的 霍 夫 曼 編 碼, 為 了 使 霍 夫 曼 碼 之 二 進 位 值 可 以 連 續, 將 所 有 的 霍 夫 曼 編 碼 加 以 重 新 編 排 首 先 將 表 1.1 依 照 頻 率 出 現 的 高 低 遞 減 排 序, 取 出 最 小 的 兩 個 符 號 S 6 與 S 7, 將 出 現 的 頻 率 分 別 為 4 與 2 相 加, 其 結 果 為 6, 且 命 名 為 A 1, 刪 除 表 1.1 中 的 S 6 與 S 7, 並 將 A 1 存 入 表 1.1 中,S 6 S 7 存 入 表 3.1 的 第 一 列 表 1.1 再 重 新 遞 減 排 序, 再 取 出 最 小 的 兩 個 符 號 S 5 與 A 1, 將 出 現 的 頻 率 相 加, 其 值 為 14, 命 名 為 A 2, 刪 除 表 1.1 的 S 5 與 A 1, 並 將 A 2 存 入 表 1.1 中, S 5 與 A 1 存 入 表 3.1 的 第 二 列 表 1.1 重 新 遞 減 排 序, 再 取 出 最 小 的 兩 個 符 號 S 4 A 2, 將 出 現 的 頻 率 相 加, 其 值 為 29, 命 名 為 A 3, 刪 除 表 1.1 的 S 4 A 2, 並 將 A3 存 入 表 1.1 中,S 4 A 2 存 入 表 3.1 的 第 三 列 表 1.1 重 新 遞 減 排 序, 再 取 出 最 小 的 兩 個 符 號 S 2 S 3, 將 出 現 的 頻 率 相 加, 其 值 為 36, 命 名 為 A 4, 刪 除 表 1.1 的 S 2 S 3, 並 將 A 4 存 入 表 1.1 中,S 2 S 3 存 入 表 3.1 的 第 四 列 表 1.1 重 新 遞 減 排 序, 取 出 最 小 的 兩 個 符 號 S 1 A 3, 將 出 現 的 頻 率 相 加, 其 值 為 51, 命 名 為 A 5, 刪 除 表 1.1 的 S 1 A 3, 並 將 A 5 存 入 表 1.1 中,S 1 A 3 存 入 表 3.1 的 第 五 列 表 1.1 再 重 新 遞 減 排 序, 取 出 最 小 的 兩 個 符 號 S 0 A 4, 將 17

25 出 現 的 頻 率 相 加, 其 值 為 69, 命 名 為 A 6, 刪 除 表 1.1 的 S 0 A 4, 並 將 A 6 存 入 表 1.1 中,S 0 A 4 存 入 表 3.1 的 第 六 列 表 1.1 再 重 新 遞 減 排 序, 最 後 將 表 1.1 剩 餘 的 兩 個 符 號 A A 存 入 表 3.1 的 第 七 列, 如 此 完 成 表 表 3.1 以 陣 列 儲 存 的 符 號 表 Column 1 Column 2 S 6 S 7 S 5 A 1 S 4 A 2 S 2 S 3 S 1 A 3 S 0 A 4 A A 編 碼 長 度 演 算 法 接 著 給 予 表 3.1 裡 每 一 個 符 號 CL 值, 將 所 有 A i 符 號 的 值 重 新 填 為 - i ( 如 表 3.2 所 示 ), 接 著 把 最 後 一 列 的 符 號 的 CL 值 設 定 為 1, 以 此 列 為 基 準 由 下 往 上 填 入 CL 值, 首 先 統 計 CL = 1 的 區 間 有 幾 個 負 數, 以 表 3.1 而 言,A 5 A 6 為 負 數, 所 以 CL = 1 的 區 間 共 有 兩 個 負 數 ; 對 應 到 圖 1.4 的 霍 夫 曼 樹 上, 表 示 其 子 節 點 (child node) 的 個 數, 相 同 層 的 子 節 點, 具 有 相 同 CL 值, 將 原 CL 累 加 1(CL 的 內 容 更 新 為 2), 並 填 入 往 上 兩 列 的 第 三 欄 中, 再 統 計 CL = 2 的 區 間 有 幾 個 負 數, 表 3.1 中 CL = 2 的 區 間,A 3 A 4 為 負 數, 所 以 CL = 2 的 區 間 共 有 兩 個 負 數, 將 原 CL 再 加 1(CL 更 改 為 3), 並 填 入 往 上 兩 列 的 第 三 欄 中, 再 統 計 CL = 3 的 區 間 有 幾 個 負 數, 以 表 3.1 來 看,CL = 3 的 區 間,A 2 為 負 數, 所 以 CL = 3 的 區 間 共 有 一 個 負 數, 將 原 CL 加 1(CL 變 成 4), 並 填 入 往 上 一 列 的 第 三 欄 中, 再 統 計 CL = 4 的 區 間 有 幾 個 負 數, CL = 4 的 區 間,A 1 為 負 數, 所 以 CL = 4 的 區 間 共 有 一 個 負 數, 將 原 CL 加 1(CL 設 定 為 5), 並 填 入 往 上 一 列 的 第 三 欄 中, 這 樣 就 完 成 了 所 有 符 號 的 CL 值, 如 表 3.3 第 三 欄 所 示 18

26 表 3.2 符 號 對 應 的 CL Symbol CL S 6 S 7 5 S 5-1 (A 1 ) 4 S 4-2 (A 2 ) 3 S 2 S 3 3 S 1-3 (A 3 ) 2 S 0-4 (A4) 2-5 (A 5 ) -6 (A 6 ) A 1 A A 1 4 S 0 A 3 S S 2 S 3 S S 5 A A S 6 S 7 圖 3.1 以 表 1.1 為 例 之 表 3.2 對 應 的 霍 夫 曼 樹 由 表 3.2 統 計 出 相 同 CL 的 區 間 有 幾 個 符 號, 在 CL = 2 有 兩 個 (S 0, S 1 ), 在 CL = 3 有 三 個 (S 2, S 3, S 4 ), 在 CL = 4 有 一 個 (S 5 ), 在 CL = 5 有 兩 個 (S 6, S 7 ), 如 表 3.3 所 示, 在 此 可 以 由 圖 3.1 發 現 到, 使 用 此 方 法 每 一 個 符 號 所 得 到 的 CL, 均 與 使 用 二 元 樹 建 立 霍 夫 曼 樹 的 方 式, 其 CL 相 同 表 3.3 各 CL 的 符 號 總 數 codeword length Number of Symbols Symbol 2 2 S 0, S S 2 ~ S S S 6, S 7 19

27 3.3 霍 夫 曼 編 碼 演 算 法 為 了 使 相 同 CL 的 霍 夫 曼 編 碼 之 二 進 位 值 可 以 連 續, 首 先 將 表 3.3 第 一 列 的 CL 區 間 的 第 一 個 符 號, 針 對 其 CL 的 長 度, 我 們 給 予 相 同 位 元 的 0, 為 其 霍 夫 曼 編 碼, 對 同 CL 的 符 號, 將 其 霍 夫 曼 編 碼 加 1, 完 成 了 第 一 列 後, 再 由 上 往 下 逐 一 編 碼, 當 上 下 列 CL 不 同 的 時 候, 所 以 先 對 上 一 列 的 最 後 一 個 符 號 的 編 碼 加 1, 再 計 算 兩 列 間 CL 的 差 值, 依 此 差 值 填 入 相 同 的 位 元 數 0 於 該 編 碼 的 右 邊, 就 完 成 了 霍 夫 曼 編 碼 表 [7] Huffman code recoding begin Huffman_code = old_cl = new_cl = 0; for ( every symbol ) begin new_huffman_code_table.symbol= codeword_length_table.symbol; new_huffman_code_table.cl= codeword_length_table.cl; new_huffman_code_table.huffman_code= Huffman_code; old_cl=codeword_length_table.cl; new_cl=get next codeword_length_table.cl; difference=new_cl - old_cl; H uffman_cod e++ ; Huffman_code=Huffman_code*2 difference end end 圖 3.2 新 的 霍 夫 曼 編 碼 演 算 法 在 圖 3.2 的 演 算 法 中, 取 一 個 索 引 值 來 當 作 搜 尋 表 的 指 標, 首 先 將 同 CL 的 符 號 做 統 計 並 取 出 在 CL 裡 最 大 的 編 碼 (Level Max Huffman code, 簡 稱 LMH) 做 為 索 引 (index), 由 於 在 相 同 CL 裡 的 霍 夫 曼 編 碼 是 有 連 續 性 的, 因 此 可 以 進 一 步 的 減 少 霍 夫 曼 編 碼 表 的 使 用 空 間, 之 後 在 進 行 解 碼 時 只 要 比 對 此 索 引 就 可 以 解 碼 出 相 對 應 的 符 號 20

28 Symbol 表 3.4 新 的 霍 夫 曼 編 碼 表 Huffman code Codeword length S S S S S S S S 再 此 說 明 表 3.4 之 CL 取 得 之 過 程, 表 3.3 的 第 一 列 之 CL 值 為 2, 第 一 個 符 號 為 (S 0 ), 給 予 相 同 位 元 的 0 (S = 00 ), 下 一 個 符 號 (S 1 ) 在 同 一 區 間 內, 因 此 符 號 0 (S 1 ) 的 編 碼 為 符 號 (S 0 ) 之 編 碼 加 1 ( S 1 = 01 ), 處 理 完 第 一 列 後, 再 往 下 處 理 第 二 列 接 著 下 一 個 符 號 (S 2 ) 在 第 二 列 CL 區 間 為 3 內, 且 為 區 間 內 第 一 個 符 號, 表 3.3 的 第 二 列 與 第 一 列 之 CL 值 差 1, 因 此 符 號 (S 2 ) 的 編 碼 為 符 號 (S 1 ) 之 編 碼 加 1 後, 編 碼 最 右 邊 填 入 一 個 0 為 (S 2 = 100 ), 符 號 (S 3 ) 符 號 (S 4 ) 與 符 號 (S 2 ) 是 相 同 CL 區 間, 因 此 符 號 (S 3 ) 之 編 碼 為 符 號 (S 2 ) 之 編 碼 加 1 (S 3 = 101 ), 符 號 (S 4 ) 之 編 碼 為 符 號 (S 3 ) 之 編 碼 加 1 (S 4 = 110 ), 處 理 完 第 二 列 後, 再 往 下 處 理 第 三 列 再 來 下 一 個 符 號 (S 5 ) 在 第 三 列 CL 區 間 為 4, 且 為 區 間 內 第 一 個 符 號, 表 3.3 的 第 三 列 與 第 二 列 之 CL 值 差 1, 因 此 符 號 (S 5 ) 的 編 碼 為 符 號 (S 4 ) 之 編 碼 加 1 後, 編 碼 最 右 邊 填 入 一 個 0 為 (S 5 = 1110 ), 處 理 完 第 三 列 後, 再 往 下 處 理 第 四 列 下 一 個 符 號 (S 6 ) 在 第 四 列 CL 區 間 為 5, 且 為 區 間 第 一 個 符 號, 表 3.3 的 第 四 列 與 第 三 列 之 CL 值 差 1, 因 此 符 號 (S 6 ) 的 編 碼 為 符 號 (S 5 ) 之 編 碼 加 1 後, 編 碼 最 右 邊 填 入 一 個 0 為 (S 6 = ), 最 後 一 個 符 號 (S 7 ) 在 同 一 區 間 內, 因 此 符 號 (S 7 ) 的 編 碼 為 符 號 (S 6 ) 之 編 碼 加 1 (S 7 = ), 這 樣 就 完 成 了 所 有 符 號 的 重 新 編 碼, 如 表 3.4 的 第 二 欄, 重 新 編 碼 後 的 霍 夫 曼 編 碼, 與 表 1.1 相 比 較 其 碼 長 度 仍 然 維 持 不 變 21

29 3.4 壓 縮 結 果 接 下 來 壓 縮 表 3. 4 之 霍 夫 曼 重 新 編 碼 表, 由 表 3.3 統 計 好 CL 的 個 數, 將 每 一 列 的 個 數 累 加 完 成 填 入 表 3.5 的 第 三 欄 (offset), 再 取 出 表 3.4 中 具 同 一 個 CL 區 間 之 最 大 霍 夫 曼 編 碼, 填 入 表 3. 5 的 第 一 欄, 由 於 經 過 重 新 編 碼 運 算, 因 此 表 3.4 的 霍 夫 曼 碼 具 有 連 續 的 性 質, 所 以 將 同 一 區 間 中 最 大 的 霍 夫 曼 編 碼 (LMH) 做 為 索 引 (index), 在 解 碼 時 只 要 與 LMH 比 對, 當 小 於 或 等 於 LMH, 代 表 解 碼 的 符 號 在 此 區 間, 只 要 與 offset 進 行 相 減 的 動 作, 表 示 已 找 到 相 對 應 的 符 號 表 3.5 壓 縮 後 的 霍 夫 曼 編 碼 表 LMH CL Offset 圖 3.3 的 演 算 法 中 HT(Huffman Table), 即 為 表 3.4, 利 用 表 3.3 和 表 3.4 建 立 表 3.5 壓 縮 的 霍 夫 曼 編 碼 表, 並 將 此 壓 縮 表 視 為 搜 尋 表 (Look Up Table, 簡 稱 LUT 表 ), 就 可 以 利 用 LUT 來 作 解 碼 的 動 作 在 解 碼 過 程 中, 對 每 一 個 符 號 的 解 碼 時 間 為 l + 1, 而 l 為 搜 尋 表 的 列 數,1 為 搜 尋 到 區 間 後 從 偏 移 量 找 到 對 應 符 號 所 需 的 1 次 減 法 時 間 22

30 Create LUT // create Look Up Table begin index = 0; for ( every symbol ) if ( (HT).CL == CL ) begin (Condensed_table).Number_of_symbol++; index++; end index = 0; for ( every CL level ) if ( (Condensed_table).Number_of_symbol > 0 ) begin index=(condensed_table). Number_of_symbol+ index; (Condensed_table).LMH=(HT).Huffman_code; (Condensed_table).Number_of_symbol=index; (Condensed_table).CL = (CL_Level); end end 圖 3.3 建 立 LUT 表 演 算 法 3.5 壓 縮 霍 夫 曼 編 碼 之 記 憶 體 使 用 空 間 探 討 本 文 所 使 用 的 方 法, 以 表 3.5 所 處 理 之 符 號 個 數 為 8 個 為 例, 所 佔 用 的 陣 列 空 間 為 12 個, 同 樣 以 8 個 符 號 之 完 滿 二 元 樹 為 例 之 壓 縮 表 為 最 小, 其 佔 用 的 陣 列 空 間 為 3 個, 以 8 個 符 號 之 單 邊 成 長 樹 之 壓 縮 表 最 大, 其 佔 用 的 陣 列 空 間 為 21 個, 所 以 壓 縮 霍 夫 曼 編 碼 表 其 使 用 空 間 為 3 ~ (3n 3),n 為 符 號 的 個 數, 其 空 間 複 雜 度 屬 於 O( n) 3.6 解 碼 過 程 與 例 題 解 碼 圖 3.4 為 解 碼 演 算 法, 解 碼 過 程 利 用 壓 縮 後 之 霍 夫 曼 表 ( 表 3.5), 從 第 一 列 由 上 往 下 作 比 對 的 動 作, 首 先 從 輸 入 位 元 串 取 得 最 小 的 碼 長 度 之 二 進 位 值 作 為 比 較, 之 後 每 增 加 一 列 再 取 不 足 的 位 元 數, 比 較 直 到 有 比 對 出 在 一 個 列 裡 的 碼 相 等 或 是 小 於 最 大 的 編 碼, 這 樣 就 是 找 到 了 相 對 應 的 符 號, 再 對 offset 作 減 法 的 動 作, 減 去 23

31 輸 入 碼 二 進 位 值 與 LMH 值 的 差, 即 可 得 到 相 對 應 的 符 號, 輸 出 符 號 後, 並 重 設 索 引 如 果 整 個 二 進 位 串 結 束 或 是 遇 到 結 束 符 號, 二 進 位 串 內 容 如 尚 有 數 個 位 元 未 完 成 解 碼, 代 表 此 二 元 串 錯 誤 在 此 我 們 對 每 一 個 符 號 的 最 大 解 碼 時 間 為 l + 1, 其 中 l 為 搜 尋 表 的 列 數 再 加 上 1 次 的 減 法 時 間, 從 表 3.5 來 看, 解 碼 在 CL 為 3 的 區 間 內 之 符 號 都 只 要 3 次 的 解 碼 時 間 就 可 以 完 成, 而 以 最 長 CL 的 編 碼 區 間 之 符 號 S 6 與 S 7 來 說, 最 多 需 要 5 次 的 解 碼 時 間 Example 1: 假 設 一 個 霍 夫 曼 碼 的 二 進 位 字 串 為 1110#, 其 中 # 表 示 二 進 位 字 串 的 結 束 以 表 3.5 來 看, 第 一 列 的 碼 長 度 是 2, 首 先 取 前 面 2-bit = 11, 比 較 與 第 一 列 的 LMH = 01, 11 大 於 01, 代 表 不 在 這 一 列, 然 後 往 第 二 列 作 比 較, 第 二 列 的 碼 長 度 是 3, 所 以 我 們 必 須 要 再 取 1-bit 來 做 比 較 111, 第 二 列 的 LMH = 110, 111 大 於 110, 所 以 也 不 在 這 一 列, 接 下 來 與 第 三 列 作 比 較, 第 三 列 的 碼 長 度 是 4, 111 不 足 1-bit, 所 以 再 取 1-bit 來 做 比 較 1110, 第 三 列 的 LMH = 1110, 1110 等 於 1110, 因 此 二 進 位 字 串 1110 在 第 三 列 裡, 接 下 來 將 LMH 與 輸 入 的 二 進 位 內 容 相 減 ( = 0), 代 表 碼 1110 差 第 三 列 LMH 零 個 符 號, 因 此 碼 1110 的 符 號 為 offset - 0 = 6-0 = 6 ( 表 示 第 六 個 符 號 ), 所 以 輸 出 二 進 位 字 串 1110 的 CL = 4, 符 號 為 S 5 ( 由 於 符 號 從 S 0 開 始, 所 以 第 六 個 符 號 為 S 5 ), 接 下 來 遇 到 結 束 符 號 # 就 完 成 了 解 碼 的 動 作 Example 2: 假 設 一 個 霍 夫 曼 碼 的 二 進 位 字 串 為 0010#, 其 中 # 表 示 二 進 位 串 的 結 束 以 表 3.5 來 看, 第 一 列 的 碼 長 度 是 2, 首 先 取 前 面 2-bit = 00, 比 較 小 於 第 一 列 的 LMH = 01, 接 下 來 將 LMH 與 輸 入 的 二 進 位 內 容 相 減 (01-00 = 1), 代 表 碼 00 差 第 一 列 LMH 一 個 符 號, 因 此 碼 00 的 符 號 為 offset - 1 = 2-1 = 1 ( 表 示 第 一 個 符 號 ), 因 此 輸 出 CL = 2 符 號 為 S 0 ( 由 於 符 號 從 S 0 開 始, 所 以 第 一 個 符 號 為 S 0 ), 接 著 因 為 已 找 到 符 號, 重 設 索 引, 二 進 位 碼 還 有 10 未 解 碼 完 成, 所 以 繼 續 24

32 解 碼, 同 樣 先 取 2-bit = 10, 比 較 大 於 第 一 列 的 LMH = 01, 代 表 不 在 這 一 列, 然 後 往 第 二 列 作 比 較, 第 二 列 的 碼 長 度 是 3, 所 以 我 們 必 須 要 再 取 1-bit 來 做 比 較, 但 是, 接 下 來 遇 到 結 束 符 號 # 解 碼 的 動 作 在 這 邊 有 出 現 問 題, 所 以 我 們 在 這 邊 發 現 最 後 這 2-bit 是 未 完 成 的 解 碼 程 序 的 編 碼, 代 表 此 4 個 位 元 之 二 進 位 字 串, 某 一 位 元 或 某 些 錯 誤 Decoding algorithm begin code = index = 0; current_cl = Condensed_table[0].CL; next_bit = get next bit from bit_stream; while (next_bit!= "#") begin for (i=1; i<= current_cl; i++) begin if (next_bit == 1 ) code = code * 2 + 1; else code = code * 2; next_bit = get next bit from bit_stream; e nd if (current_cl > length of spare_bit of bit_stream ) output " No Symbol bit is Error Code " else if ((code <= Condensed_table.LMH ) && (Condensed_table.CL == current_cl )) begin output symbol at Condensed_table.Number_of_symbol - (Condensed_table.LMH - code); code = index =0; current_cl = Condensed_table[0].CL; next_bit = get next bit from bit_stream; end else if ( current_cl == length of spare_bit of bit_stream ) output " No Symbol bit is Error Code "; else begin current_cl = Condensed_table[index +1].CL - Condensed_table[index].CL; index++; end end end 圖 3.4 霍 夫 曼 碼 解 碼 演 算 法 25

33 Example 3: 同 樣 以 表 3.5 作 為 例 子, 假 設 一 個 霍 夫 曼 碼 的 二 進 位 字 串 為 #, 其 中 #" 表 示 二 進 位 串 的 結 束 第 一 列 的 碼 長 度 是 2, 先 取 2-bit = 11 比 對 大 於 第 一 列 的 LMH, 再 取 出 1-bit = 111 比 對 大 於 第 二 列 的 LMH, 再 取 出 1-bit = 1111 比 對 大 於 第 三 列 的 LMH, 再 取 出 1-bit = 比 對 小 於 第 四 列 的 LMH, 因 此 表 示 找 到 符 號,offset 1 = 7 ( 表 示 第 七 個 符 號 ), 輸 出 CL = 3 符 號 為 S 6 ( 由 於 符 號 從 S 0 開 始, 所 以 第 七 個 符 號 為 S 6 ), 接 下 來 因 為 有 找 到 符 號, 所 以 重 設 索 引, 表 示 重 新 開 始, 取 2-bit = 11 比 對 大 於 第 一 列 的 LMH, 再 取 出 1-bit = 111 比 對 大 於 第 二 列 LMH, 再 取 出 1-bit = 1110 比 對, 等 於 第 三 列 LMH, 表 示 找 到 符 號,offset 0 = 6 ( 表 示 第 六 個 符 號 ), 並 輸 出 CL = 4 符 號 為 S 5 ( 由 於 符 號 從 S 0 開 始, 所 以 第 六 個 符 號 為 S 5 ), 接 下 來 重 設 索 引, 並 重 新 開 始, 取 2-bit = 00 比 對 等 於 第 一 列 的 LMH, 表 示 找 到 符 號,offset 1 = 1 ( 表 示 第 一 個 符 號 ), 並 輸 出 CL = 2 符 號 為 S 0 ( 由 於 符 號 從 S 0 開 始, 所 以 第 一 個 符 號 為 S 0 ), 接 下 來 遇 到 #, 結 束 整 個 解 碼 過 程 從 上 述 例 子 來 看, 可 以 發 現 到 論 文 中 的 演 算 法 不 同 於 其 他 演 算 法, 必 須 要 知 道 所 要 解 碼 之 符 號 的 CL, 或 是 在 兩 個 符 號 的 霍 夫 曼 碼 之 間 加 上 一 個 用 來 區 隔 兩 個 不 同 碼 的 分 隔 號 如 果 需 要 預 先 知 道 CL 必 須 在 編 碼 的 階 段 同 時 儲 存 這 些 編 碼 的 個 別 長 度 的 資 訊, 也 增 加 不 少 額 外 的 儲 存 空 間, 在 解 碼 上, 使 用 分 隔 符 號, 除 了 空 間 增 加 外, 在 解 碼 時 必 須 先 預 先 讀 取 此 筆 符 號 的 編 碼 再 對 此 編 碼 進 行 解 碼, 這 樣 會 使 得 解 碼 時 間 加 長 解 碼 過 程 中, 以 Example 1 來 說, 只 需 要 3 次 的 比 對 動 作 加 上 1 次 的 減 法 時 間, 就 可 以 找 到 相 對 應 的 符 號,Example 2 可 以 知 道 在 解 碼 過 程 中, 要 是 有 未 完 成 的 解 碼 或 是 二 進 位 串 內 容 有 錯 誤, 我 們 可 以 偵 測 出 來, 從 Examp le 3 來 看 我 們 以 一 串 連 續 的 二 進 位 字 串, 連 續 3 個 符 號 S6 S 5 S 0 來 做 解 碼 的 動 作, 其 符 號 的 解 碼 次 數 從 表 3.5 來 看 S 6 為 第 四 列, 解 碼 次 數 為 l + 1 = = 5,S 5 為 第 三 列, 解 碼 次 數 為 l + 1 = = 4,S 0 為 第 一 列, 解 碼 次 數 為 l + 1 = = 2, 連 續 三 個 符 號 的 26

34 總 解 碼 次 數 為 11 次, 所 以 對 於 每 一 個 符 號 之 解 碼 所 需 要 的 時 間 為 l + 1 在 解 碼 的 過 程 中 不 需 要 將 符 號 之 間 的 編 碼 做 間 隔 標 記, 即 可 達 到 連 續 解 碼 的 功 能, 而 且 解 碼 的 時 間 也 相 較 以 往 要 讀 取 最 長 的 CL 比 較 來 的 要 快 了 許 多 27

35 第 四 章 使 用 FPGA 完 成 霍 夫 曼 解 碼 器 在 本 章 節 中, 將 分 別 使 用 循 序 電 路 與 多 工 器 電 路 完 成 並 以 FPGA 來 實 現 霍 夫 曼 解 碼 器, 藉 由 第 一 章 的 例 子 與 第 三 章 所 完 成 的 搜 尋 表 (LUT) 來 設 計, 在 循 序 電 路 與 多 工 器 電 路 之 輸 入 端, 輸 入 霍 夫 曼 碼 來 進 行 解 碼, 電 路 輸 出 對 應 之 符 號, 以 及 霍 夫 曼 碼 的 碼 長 度 接 著 再 進 一 步 說 明 整 個 電 路 架 構, 以 模 擬 波 形 圖 來 顯 示 霍 夫 曼 解 碼 器 的 結 果, 並 比 較 循 序 電 路 與 多 工 器 電 路 的 解 碼 速 度 及 邏 輯 元 素 之 使 用 率, 最 後 由 模 擬 結 果 可 以 知 道, 以 多 工 器 來 製 作 解 碼 電 路, 其 解 碼 的 速 度 比 較 快 且 所 使 用 的 邏 輯 元 素 比 較 少 4.1 循 序 電 路 架 構 我 們 以 表 3.4 與 其 壓 縮 後 的 表 3.5 為 例, 並 製 作 如 圖 4.1 之 部 分 循 序 電 路 圖, 由 此 圖 來 解 釋 循 序 電 路 架 構, 從 位 元 流 串 (bit stream) 輸 入 之 二 進 位 值 00#, 經 過 編 碼 運 算 後, 與 表 3.5 之 LMH 進 行 比 對, 00 小 於 (LESS_THAN) 表 3.5 之 第 一 列 LMH, 表 示 二 進 位 值 00 在 CL 為 2 之 區 間 內, 將 暫 存 器 中 之 值 01 與 輸 入 之 二 進 位 值 00 相 減 得 到 1, 表 示 00 在 CL 為 2 之 區 間 內 偏 移 量 為 1, 對 應 的 符 號 為 (S 0 ), 輸 出 對 應 的 符 號 S 0, 接 下 來 遇 到 結 束 符 號 #, 結 束 解 碼 圖 4.1 之 部 分 循 序 電 路 圖, 其 運 作 方 式, 首 先 將 輸 入 之 二 進 位 值 經 過 編 碼 運 算, 接 著 與 暫 存 器 Code[30..0] 進 行 比 對, 以 上 述 解 碼 符 號 (S 0 ) 為 例, 輸 入 之 00 與 暫 存 器 Code[30..0], 比 對 結 果 為 小 於 (LESS_THAN), 最 後 觸 發 三 態 閘 (Symbol~0), 輸 出 其 對 應 符 號 由 於 使 用 循 序 電 路, 每 一 次 需 要 從 位 元 流 串 取 得 位 元, 需 要 一 個 時 脈 (clock) 的 時 間, 在 整 體 的 解 碼 時 間 上, 明 顯 的 增 加 許 多 且 在 邏 輯 元 素 使 用 量 上, 需 要 以 暫 存 器 儲 存 目 前 的 資 料, 所 以 整 個 電 路 會 加 大 許 多, 因 此 特 別 將 循 序 電 路 再 改 28

36 進 為 使 用 多 工 器 來 完 成 圖 4.1 解 碼 符 號 S 0 之 循 序 電 路 架 構 圖 4.2 多 工 器 電 路 架 構 同 樣 以 表 3.4 與 表 3.5 為 例, 使 用 多 工 器 來 完 成 的 部 份 電 路 架 構 如 圖 4.2 所 示, 由 於 使 用 多 工 器 需 要 取 最 長 CL 值 之 二 進 位 字 串, 在 此 必 須 以 5 位 元 來 做 輸 入, 以 輸 入 二 進 位 字 串 (bitstream = ) 為 例, 首 先 從 最 高 位 元 開 始 取 長 度 為 2(CL = 2) 的 兩 個 bits 00 (bitstream[4] 和 bitstream[3]) 進 行 比 對, 00 小 於 (LESS_THAN) 表 3.5 之 第 一 列 LMH, 表 示 二 進 位 字 串 在 CL 為 2 之 區 間 內, 因 此 將 暫 存 器 中 之 值 01 與 00 相 減 得 到 1, 表 示 在 CL 為 2 的 區 間 內 之 偏 移 量 1, 對 應 的 為 符 號 (S 0 ), 然 後 輸 出 符 號 S 0 圖 4.2 為 部 份 多 工 器 之 電 路 圖, 同 樣 以 解 碼 符 號 (S 0 ) 為 例, 所 輸 入 之 二 進 位 值 為 00000, 取 長 度 為 2 的 兩 個 bits 00 (bitstream[4] 和 bitstream[3]) 與 表 3.5 比 較, 29

37 比 較 結 果 為 小 於 (LESS_THAN) 表 3.5 第 一 列 之 LMH 值, 因 此 觸 發 三 態 閘 (Sym bol~0), 將 暫 存 器 (Symbol[2]~reg0) 之 值 輸 出 以 多 工 器 的 方 式 來 製 作 解 碼 電 路, 必 需 輸 入 最 大 CL 之 位 元 數, 所 以 在 解 碼 上 只 需 要 一 個 時 脈 的 時 間, 即 可 以 完 成 一 個 符 號 的 解 碼 動 作 圖 4.2 解 碼 符 號 S 0 之 多 工 器 電 路 架 構 圖 4.3 電 路 模 擬 接 著 以 FPGA 來 設 計 並 實 現 霍 夫 曼 解 碼 器, 以 表 1.1 的 符 號 及 對 應 的 頻 率 為 例, 經 過 第 三 章 的 演 算 法, 最 後 得 到 了 表 3.5 的 壓 縮 表, 將 此 壓 縮 表 視 為 一 搜 尋 表, 利 用 此 搜 尋 表 製 作 FPGA 電 路, 使 用 Altera 公 司 的 Quartus II 進 行 模 擬,Device: EP1S10F484C5 總 邏 輯 元 素 為 個, 在 本 節 中, 分 別 以 循 序 電 路 及 多 工 器 電 路 來 進 行 模 擬, 並 比 較 兩 者 之 間 的 差 異 30

38 4.3.1 模 擬 軟 體 Quartus II 簡 介 Altera 的 Quartus II 設 計 軟 體 提 供 一 個 非 常 容 易 設 計 的 軟 體 且 完 整 的 多 平 臺 設 計 環 境, 它 是 一 個 可 程 化 晶 片 系 統 (SOPC) 設 計 的 綜 合 性 環 境 Quartus II 軟 體 包 括 FPGA 和 CPLD設 計 所 有 階 段 的 解 決 方 案, 在 圖 4.3中 顯 示 Quartus II 的 設 計 流 程 使 用 Quartus II 軟 體 可 以 完 成 設 計 流 程 的 所 有 階 段, 是 一 種 完 整 且 容 易 使 用 的 獨 立 解 決 方 案 Quartus II 軟 體 為 設 計 流 程 的 每 個 階 段 提 供 圖 形 使 用 者 介 面 EDA 工 具 介 面 以 及 命 令 行 介 面 可 以 在 整 個 流 程 中 只 使 用 這 些 介 面 中 的 一 個, 也 可 以 在 設 計 流 程 的 不 同 階 段 使 用 不 同 介 面 圖 4.3 Quartus II 軟 體 設 計 流 程 31

39 4.3.2 循 序 電 路 模 擬 以 表 3.5 的 搜 尋 表 直 接 製 作 成 一 個 循 序 輸 入 的 電 路, 以 Altera FPGA 來 實 作 此 霍 夫 曼 解 碼 器, 其 總 邏 輯 元 素 使 用 率 是 1%, 在 個 邏 輯 元 素 上 使 用 138 個 邏 輯 元 素 使 用 Example 2 在 循 序 電 路 上, 一 個 時 脈 的 週 期 為 15 ns, 從 圖 4.4 來 看, 連 續 解 碼 三 個 符 號 S 6 S 5 與 S 0, 其 編 碼 字 的 長 度 分 別 為 5 4 與 2, 整 個 解 碼 時 間 為 11 個 時 脈 (clock), 總 時 間 為 165 ns 圖 4.4 Example 2 之 循 序 電 路 模 擬 圖 多 工 器 電 路 模 擬 再 來 使 用 多 工 器 的 方 式 實 作 霍 夫 曼 解 碼 器, 由 於 本 文 使 用 的 演 算 法, 使 得 所 編 好 的 碼, 具 有 連 續 的 特 性, 因 此 以 多 工 器 來 實 現 霍 夫 曼 解 碼 器, 會 使 電 路 變 得 較 為 簡 單 同 樣 使 用 Example 2 在 多 工 器 電 路 上, 其 總 邏 輯 元 素 使 用 率 < 1%, 在 個 邏 輯 元 素 上 使 用 7 個 邏 輯 元 素, 一 個 時 脈 的 週 期 為 8ns, 以 圖 4.5 而 言, 連 續 三 個 符 號 S 6 S 5 S 0, 每 一 個 符 號 只 須 一 個 時 脈, 整 個 解 碼 時 間 總 共 3 個 時 脈, 總 時 間 為 24ns 32

40 圖 4.5 Example 2 之 多 工 器 電 路 模 擬 波 形 圖 4.4 結 果 與 比 較 我 們 模 擬 的 結 果 與 [1] 的 結 果 進 行 比 較,[1] 使 用 多 工 器, 在 8 個 符 號 使 用 有 限 狀 態 機 實 現 硬 體 解 碼, 共 使 用 24 個 邏 輯 元 素, 本 文 的 演 算 法 以 循 序 電 路 製 作 後, 所 需 要 的 邏 輯 元 素 個 數 為 138, 解 碼 時 間 都 為 h 個 時 脈, 如 表 4.1 所 示 [1] 再 以 BDD 刪 除 重 複 的 節 點, 並 使 用 多 工 器 製 作 解 碼 電 路, 其 邏 輯 元 素 使 用 6 個, 解 碼 時 間 為 10 ns, 以 本 文 壓 縮 霍 夫 曼 表 演 算 法, 再 以 多 工 器 完 成 解 碼 電 路, 總 邏 輯 元 素 為 7 個, 解 碼 時 間 為 8 ns, 在 所 要 處 理 的 符 號 較 少 的 情 況 之 下,[1] 與 本 文 的 效 率 是 差 不 多, 如 表 4.1 所 示 表 4.1 使 用 EP1S10F484C5 之 8 個 符 號 的 循 序 電 路 比 較 邏 輯 使 用 率 邏 輯 個 數 解 碼 時 間 有 限 狀 態 機 之 霍 夫 h 一 個 時 脈 1% 24 曼 解 碼 器 [1] 的 時 間 h 一 個 時 脈 壓 縮 霍 夫 曼 表 * 1% 138 的 時 間 * 表 示 第 四 章 所 使 用 的 演 算 法 33

41 表 4.2 使 用 EP1S10F484C5 之 8 個 符 號 的 多 工 器 電 路 比 較 邏 輯 使 用 率 邏 輯 個 數 解 碼 時 間 BDD-based 霍 夫 曼 解 碼 器 [1] 1% 6 10 ns 壓 縮 霍 夫 曼 表 * 1% 7 8 ns * 表 示 第 四 章 所 使 用 的 演 算 法 34

42 第 五 章 使 用 高 效 能 記 憶 體 與 快 速 演 算 法 製 作 電 路 在 本 章 節 中 將 改 進 循 序 電 路 之 邏 輯 元 素 使 用 率 過 高 的 情 形, 使 用 一 種 高 效 能 記 憶 體 與 快 速 的 霍 夫 曼 解 碼 演 算 法 [2], 將 要 處 理 的 符 號 建 立 成 一 顆 霍 夫 曼 樹, 再 將 此 二 元 樹 視 為 狀 態 圖, 將 狀 態 圖 轉 換 成 搜 尋 表, 搜 尋 表 是 以 廣 度 優 先 搜 尋 (breadth first search) 配 合 佇 列 (Queue), 將 二 元 樹 中 的 非 葉 節 點 值, 從 根 節 點 開 始 重 新 從 0 編 號 替 代, 並 以 陣 列 的 方 式 儲 存 所 有 節 點 值 在 解 碼 上, 使 用 有 限 狀 態 機 的 方 式 配 合 搜 尋 表 來 完 成 解 碼 的 動 作, 使 用 此 搜 尋 表 完 成 在 FPGA 上 的 循 序 電 路 設 計, 實 現 霍 夫 曼 解 碼 器 5.1 建 立 霍 夫 曼 樹 圖 個 符 號 之 狀 態 圖 同 樣 以 表 1.1 為 例, 表 1.1 對 映 的 霍 夫 曼 樹 為 圖 1.4, 圖 1.4 中 所 有 往 左 走 訪 的 路 徑 標 示 為 0, 往 右 走 訪 的 路 徑 標 示 為 1, 所 有 的 符 號 均 在 葉 節 點 之 上, 其 符 號 的 霍 夫 曼 編 碼 就 是 從 根 節 點 走 訪, 路 徑 中 所 有 的 二 元 組 合 例 如 符 號 S 3, 首 先 由 35

43 根 節 點 往 左 走 訪 兩 次 (00), 再 往 右 走 訪 一 次 (001), 符 號 S3 的 霍 夫 曼 編 碼 為 001 從 表 1.1 中 可 以 發 現 到, 頻 率 最 高 的 符 號 S, 其 編 碼 最 短 為 01, 而 出 現 頻 率 最 低 的 S 7, 其 編 碼 最 長 為 在 此 將 圖 1.1 建 立 好 的 霍 夫 曼 樹 視 為 一 張 狀 態 圖, 並 將 所 有 非 葉 節 點 編 號, 根 節 點 為 0, 每 一 次 遞 增 1, 由 左 向 右 依 序 填 入 值, 當 同 一 層 非 葉 節 點 都 填 滿 時 再 往 下 一 層 由 左 向 右 依 序 填 入 值, 重 複 這 個 動 作, 直 到 所 有 非 葉 節 點 編 號 完 成 如 圖 5.1 所 示 在 圖 5.1 中, 根 節 點 為 起 始 狀 態 (starting state), 其 狀 態 值 為 0, 在 走 訪 到 葉 節 點 時, 也 就 是 找 到 符 號, 此 時 就 重 新 設 定 (reset) 狀 態 值 為 0, 繼 續 下 一 個 符 號 的 搜 尋 建 立 LUT 搜 尋 表 表 個 符 號 之 搜 尋 表 (LUT) Input bit Present State S S 1 3 S 2 S 3 4 S S S 6 S 7 接 著 以 圖 5.1 建 立 一 個 狀 態 表, 視 為 搜 尋 表 (LUT), 如 表 5.1 所 示 本 節 的 演 算 法, 使 用 廣 度 優 先 搜 尋, 針 對 圖 5.1 的 霍 夫 曼 樹 進 行 搜 尋, 使 用 一 個 佇 列, 協 助 進 行 廣 度 優 先 搜 尋, 佇 列 儲 存 的 內 容 為 各 個 節 點 的 起 始 位 址, 並 非 各 個 節 點 內 容 或 內 含 值 演 算 法 中, 使 用 一 個 變 數 記 錄 目 前 狀 態 值, 由 根 節 點 開 始, 其 值 為 0, 當 節 點 的 左 或 右 子 樹 非 葉 節 點 時, 先 將 此 變 數 遞 增 1, 並 且 將 變 數 的 值 存 入 該 節 點 36

44 的 左 或 右 子 樹 中, 並 將 左 子 樹 與 右 子 樹 的 起 始 位 址, 依 序 存 入 佇 列 中, 接 著 將 此 左 子 樹 與 右 子 樹 的 內 容, 以 列 為 主 由 左 至 右, 然 後 由 上 而 下, 填 入 到 表 5.1 中 在 此 LUT 所 需 要 的 儲 存 空 間 為 (n 1)*2, 所 以 其 使 用 空 間 的 複 雜 度 屬 於 O(n) 以 表 1.1 來 看, 所 處 理 的 符 號 的 個 數 為 8 個, 將 霍 夫 曼 樹 轉 換 成 狀 態 圖, 並 以 陣 列 的 方 式 儲 存 符 號, 這 樣 LUT 表 的 大 小 為 (8 1)*2 = 解 碼 演 算 法 第 三 節 的 解 碼 演 算 法, 使 用 表 5.1 的 搜 尋 表 (LUT) 來 進 行 解 碼 的 程 序, 將 符 號 以 霍 夫 曼 編 碼 的 二 進 位 值 傳 送, 搜 尋 表 上 的 二 進 位 串 (bit stream) 代 表 輸 入 之 霍 夫 曼 碼, 而 Present State 0 ~ 7 表 示 目 前 的 狀 態, 表 中 數 字 的 部 份 為 前 往 下 一 個 狀 態 之 狀 態 值, 非 數 值 的 部 份 為 對 應 的 解 碼 符 號, 當 解 碼 程 序 對 應 為 非 符 號 部 份, 代 表 解 碼 尚 未 完 成, 需 要 繼 續 進 行 解 碼, 直 到 解 碼 出 現 符 號 為 止, 或 是 輸 入 之 二 進 位 字 串 結 束, 當 二 進 位 串 處 理 結 束 時, 如 果 狀 態 未 重 設 回 到 0, 表 示 整 串 二 進 位 內 容 有 部 分 錯 誤, 所 以 以 文 中 的 演 算 法 所 製 作 出 的 硬 體 電 路 具 有 偵 測 錯 誤 的 能 力 Example 1: 一 個 霍 夫 曼 碼 的 二 進 位 字 串 為 100#, 其 中 # 表 示 二 進 位 字 串 的 結 束 在 表 5.1 中 由 狀 態 0 開 始 (Presen t State 0), 輸 入 為 0 時, 則 選 擇 表 5.1 中 0 的 欄 位, 輸 入 為 1 時, 則 選 擇 表 5.1 中 1 的 欄 位 首 先 輸 入 第 一 個 bit 為 1, 由 表 中 狀 態 第 0 列,1 的 欄 位 的 內 容 為 2, 表 示 下 一 個 狀 態 為 2 輸 入 的 第 二 個 bit 為 0, 由 表 中 狀 態 第 2 列,0 的 欄 位 的 內 容 為 4, 表 示 下 一 個 狀 態 為 4 輸 入 的 第 三 個 bit 為 0, 由 表 中 狀 態 第 4 列 左 邊 欄 位 的 內 容 為 S 4, 表 示 所 解 碼 的 符 號 為 S 4, 因 為 已 找 到 符 號, 重 設 狀 態 值 為 0, 緊 跟 著 為 #, 表 示 正 常 結 束 Example 2: 同 樣 以 表 5.1 為 例, 一 個 霍 夫 曼 碼 的 二 進 位 字 串 為 1011#, 其 中 #" 表 示 二 進 位 字 串 的 結 束 輸 入 第 一 個 bit 為 1, 由 表 中 狀 態 第 0 列,1 的 欄 位 的 內 37

45 容 為 2, 表 示 下 一 個 狀 態 為 2 輸 入 的 第 二 個 bit 為 0, 由 表 中 狀 態 第 2 列,0 的 欄 位 的 內 容 為 4, 表 示 下 一 個 狀 態 為 4 輸 入 的 第 三 個 bit 為 1, 由 表 中 狀 態 第 4 列, 1 的 欄 位 的 內 容 為 5, 表 示 下 一 個 狀 態 為 5 輸 入 的 第 四 個 bit 為 1, 由 表 中 狀 態 第 5 列,1 的 欄 位 的 內 容 為 6, 表 示 下 一 個 狀 態 為 6 最 後 為 #", 而 狀 態 值 並 未 回 到 狀 態 0, 表 示 未 解 碼 出 符 號, 也 意 味 此 4 個 位 元 之 二 進 位 字 串, 某 一 位 元 或 某 些 錯 誤 Example 3: 假 定 二 進 位 串 為 #, 其 中 # 表 示 二 進 位 串 的 結 束 同 樣 以 表 5.1 作 為 解 碼 範 例, 由 狀 態 0 開 始, 配 合 圖 5.2 的 解 說 處 理 一 串 霍 夫 曼 碼, 輸 出 符 號 依 序 為 :S 6, S 5, S 0 解 碼 完 最 後 一 個 符 號 S 0 後, 狀 態 值 重 設 為 0, 緊 跟 著 為 #, 表 示 解 碼 結 束 圖 5.2 Example 3 之 連 續 3 個 符 號 解 碼 過 程 從 上 述 的 三 個 例 子 來 看, 在 新 的 高 效 能 演 算 法 中, 其 解 碼 同 樣 不 需 要 在 兩 個 霍 夫 曼 碼 之 間 加 入 其 他 符 號, 即 可 進 行 連 續 解 碼, 而 對 於 每 一 個 符 號 所 需 要 的 解 碼 次 數 等 於 符 號 之 編 碼 長 度, 以 Example 1 來 看, 符 號 S 4 的 解 碼 次 數 為 3 次, 其 編 碼 長 度 也 同 為 3, 因 此 搜 尋 所 需 要 的 次 數 都 為 h, 所 以 演 算 法 的 解 碼 時 間 複 雜 度 屬 於 O(h) 在 Example 3 中, 連 續 針 對 三 個 符 號 S 6, S 5, S 0 解 碼, 其 霍 夫 曼 碼 的 編 碼 字 的 長 度 分 別 為 5, 4, 2, 兩 個 編 碼 之 間 也 不 必 置 放 任 何 分 隔 符 號, 連 續 三 個 符 號 解 碼 所 花 費 的 次 數 分 別 為 5, 4, 與 2, 共 11 次 38

46 5.4 電 路 架 構 圖 5.3 為 循 序 電 路 部 份 的 架 構 圖, 以 表 1.1 與 表 5.1 為 例, 由 此 圖 來 解 釋 循 序 電 路 架 構, 二 進 位 串 輸 入 之 二 進 位 值 01#, 狀 態 值 0 開 始 首 先 第 一 個 clock 輸 入 0, 致 能 多 工 器 之 後, 從 暫 存 器 輸 出 當 前 狀 態 之 對 應 值 或 符 號, 表 5.1 中 所 對 應 為 1, 將 此 狀 態 值 存 回 D 型 正 反 器 內, 以 作 為 下 一 次 的 狀 態 值 接 下 來, 下 一 個 clock 輸 入 為 1, 致 能 多 工 器 之 後, 從 暫 存 器 輸 出 之 對 應 值 或 符 號, 依 表 5.1 對 應 為 S 0, 表 示 符 號, 可 以 直 接 輸 出 由 於 解 碼 出 符 號, 因 此 將 狀 態 值 0 存 回 D 型 正 反 器 作 為 下 一 次 的 狀 態 值 每 解 碼 一 次 需 要 從 二 進 位 串 取 得 數 值 需 要 一 個 時 脈 (clock) 的 時 間, 每 一 個 符 號 需 要 h 個 時 脈 之 解 碼 時 間 圖 5.3 解 碼 符 號 S 0 之 循 序 電 路 架 構 圖 39

47 5.5 電 路 模 擬 與 結 果 在 本 節 中, 同 樣 使 用 FPGA 來 設 計 並 實 現 霍 夫 曼 解 碼 器, 以 表 1.1 的 符 號 及 對 應 的 頻 率 為 例, 經 過 第 二 節 的 演 算 法, 最 後 得 到 了 表 5.1 的 LUT, 利 用 此 LUT 製 作 FPGA 電 路, 使 用 Altera 公 司 的 Quartus II 進 行 模 擬,Device:EP1S10F484C5 總 邏 輯 元 素 為 個, 並 以 循 序 電 路 電 路 來 進 行 模 擬, 與 [1], [8] 相 互 比 較 之 以 表 5.1 的 LUT 直 接 製 作 成 一 個 循 序 輸 入 的 電 路, 以 Altera FPGA 來 實 作 此 霍 夫 曼 解 碼 器, 其 總 邏 輯 元 素 使 用 率 是 < 1%, 在 個 邏 輯 元 素 上 使 用 14 個 邏 輯 元 素 以 Example 3, 一 個 時 脈 的 週 期 為 10 ns, 從 圖 5.4 來 看, 連 續 解 碼 三 個 符 號 S 6 S 5 與 S 0, 編 碼 長 度 分 別 為 5 4 與 2, 其 解 碼 所 需 的 時 間 也 為 5, 4 與 2 個 時 間 時 脈, 整 個 解 碼 時 間 為 11 個 時 脈 (clock), 總 時 間 為 110 ns 圖 5.4 Example 3 之 循 序 電 路 模 擬 波 形 圖 模 擬 的 結 果 與 [1], [4] 的 結 果 進 行 比 較, 以 表 5.2 來 看,[1], [4] 都 以 循 序 電 路 製 作, 在 8 個 符 號 使 用 有 限 狀 態 機 實 現 硬 體 解 碼,[1] 共 使 用 24 個 邏 輯 元 素,[4] 使 用 了 138 個 邏 輯 元 素, 本 節 的 演 算 法 以 循 序 電 路 製 作, 在 8 個 符 號 上, 需 要 的 邏 輯 元 素 個 數 為 14, 解 碼 時 間 均 為 h 個 時 脈 因 此 本 節 的 方 法 較 [1], [4] 在 循 序 電 路 上, 40

48 減 少 了 更 多 邏 輯 元 素 之 使 用, 在 成 本 上 減 少 了 許 多 表 5.2 使 用 EP1S10F484C5 之 8 個 符 號 的 循 序 電 路 比 較 有 限 狀 態 機 之 霍 夫 曼 解 碼 器 [1] 邏 輯 使 用 率 邏 輯 個 數 1% 24 解 碼 時 間 h 一 個 時 脈 的 時 間 使 用 FPGA 完 成 低 成 本 霍 夫 曼 解 碼 器 [5] 1% 14 h 一 個 時 脈 的 時 間 使 用 FPGA 完 成 高 速 霍 夫 曼 解 碼 器 [4] 1% 138 h 一 個 時 脈 的 時 間 與 [1], [4] 相 比 較, 在 處 理 8 個 符 號 之 循 序 電 路 上, 減 少 了 41%( = (24-14)/24) [1] 與 90%( = (138-14)/138) [4] 的 邏 輯 元 素 使 用 率, 因 此 在 循 序 電 路 上, 以 第 五 章 之 高 效 能 記 憶 體 與 快 速 的 霍 夫 曼 解 碼 演 算 法 較 為 適 用, 明 顯 降 低 邏 輯 元 素 的 使 用 率 41

49 第 六 章 實 作 結 果 與 比 較 在 本 章 節 中, 本 文 將 以 一 個 實 際 的 樣 本 來 製 作 霍 夫 曼 解 碼 器, 以 第 三 章 與 第 五 章 之 演 算 法, 分 別 製 作 循 序 電 路 與 多 工 器 電 路, 並 與 其 他 方 法 比 較 在 實 際 的 樣 本 中, 以 循 序 電 路 的 實 作 上, 高 效 能 記 憶 體 與 快 速 的 霍 夫 曼 解 碼 演 算 法 在 解 碼 8 個 符 號 與 66 個 符 號 有 個 相 當 好 的 成 效 在 多 工 器 電 路 的 實 作 上, 使 用 壓 縮 霍 夫 曼 表 製 作 的 解 碼 電 路, 解 碼 的 時 間 較 為 快 速 6.1 壓 縮 霍 夫 曼 編 碼 表 之 解 碼 電 路 實 作 圖 6.1 為 使 用 壓 縮 霍 夫 曼 表 之 66 個 符 號 循 序 電 路 模 擬, 經 過 第 三 章 的 演 算 法, 最 短 的 CL= 3, 其 符 號 為 S 0, 編 碼 為 000, 最 長 的 CL = 12, 符 號 為 S 65, 編 碼 為 , 以 循 序 電 路 製 作 而 成 的 霍 夫 曼 解 碼 器, 其 總 邏 輯 元 素 使 用 率 是 3%, 在 個 邏 輯 元 素 上 使 用 313 個 邏 輯 元 素 從 圖 6.1 來 看, 使 用 一 個 時 脈 為 10 ns, 連 續 解 碼 S65 與 S0,S 65 其 CL 為 12, 需 要 花 費 12 個 時 脈,S 0 其 CL 是 3, 需 要 花 費 3 個 時 脈, 連 續 兩 個 符 號 解 碼 總 時 間 為 15 個 時 脈, 共 150 ns 由 此 例 可 以 知 道, 當 CL 為 h 時, 在 循 序 電 路 上, 其 解 碼 的 時 間 為 h 個 時 脈 圖 個 符 號 之 壓 縮 霍 夫 曼 表 循 序 電 路 模 擬 圖 42

50 而 使 用 多 工 器 來 完 成 66 個 符 號 的 霍 夫 曼 解 碼 器 如 圖 6.2 所 示, 其 總 邏 輯 元 素 使 用 率 是 1%, 在 個 邏 輯 元 素 上 使 用 140 個 邏 輯 元 素, 一 個 時 脈 為 8 ns, 由 於 多 工 器 只 需 要 一 次 時 脈 就 可 以 完 成 一 個 符 號 的 解 碼 動 作, 連 續 解 碼 S 個 符 號, 其 總 時 間 為 16 ns 與 S 兩 65 0 圖 個 符 號 之 壓 縮 霍 夫 曼 表 多 工 器 電 路 模 擬 圖 6.2 高 效 能 記 憶 體 與 快 速 的 霍 夫 曼 解 碼 演 算 法 之 解 碼 電 路 實 作 接 下 來 使 用 高 效 能 記 憶 體 與 快 速 的 霍 夫 曼 解 碼 演 算 法 進 行 解 碼 設 計, 同 樣 以 66 個 符 號 進 行 循 序 電 路 的 製 作 與 模 擬, 經 過 第 五 章 的 演 算 法, 在 此 取 最 短 的 編 碼 S 0, 霍 夫 曼 編 碼 為 000, 與 最 長 的 編 碼 S 65, 霍 夫 曼 編 碼 為 , 這 兩 個 符 號 進 行 解 碼 以 66 個 符 號 所 製 作 成 的 霍 夫 曼 解 碼 器, 用 循 序 電 路 完 成, 其 總 邏 輯 元 素 使 用 率 是 < 1%, 在 個 邏 輯 元 素 上 使 用 102 個 邏 輯 元 素 從 圖 6.3 來 看, 使 用 一 個 時 脈 為 10 ns, 連 續 解 碼 S 65 與 S 0,S 65 其 CL 為 12, 需 要 花 費 12 個 時 脈,S 0 其 CL 是 3, 需 要 花 費 3 個 時 脈, 連 續 兩 個 符 號 解 碼 總 時 間 為 15 個 時 43

51 脈, 共 150 ns 由 此 例 可 以 知 道, 當 CL 為 h 時, 在 循 序 電 路 上, 其 解 碼 的 時 間 為 h 個 時 脈 圖 個 符 號 之 高 效 能 記 憶 體 與 快 速 的 霍 夫 曼 解 碼 演 算 法 循 序 電 路 模 擬 圖 6.3 結 果 與 比 較 首 先 以 循 序 電 路 之 模 擬 的 結 果 進 行 比 較, 以 表 6.1 來 看,[1], [5], [4] 都 以 循 序 電 路 製 作, 在 66 個 符 號 上,[1] 以 BDD 刪 除 重 複 的 節 點, 並 使 用 循 序 電 路 製 作 解 碼 器, 其 邏 輯 元 素 使 用 639 個, 解 碼 時 間 為 10 ns [5] 將 霍 夫 曼 樹 轉 換 成 狀 態 表, 並 使 用 陣 列 的 方 式 儲 存 狀 態 表, 其 邏 輯 元 素 個 數 為 102 個, 解 碼 時 間 為 10 ns [4] 使 用 壓 縮 霍 夫 曼 表, 並 用 循 序 電 路 實 現, 其 邏 輯 元 素 個 數 為 138 個, 解 碼 時 間 為 10 ns 在 循 序 電 路 上, 以 使 用 FPGA 完 成 低 成 本 霍 夫 曼 解 碼 器 [5], 完 成 的 循 序 電 路, 總 邏 輯 元 素 為 102 個, 解 碼 時 間 為 10 ns, 其 方 法 較 [1], [4] 在 循 序 電 路 上, 減 少 了 更 多 邏 輯 元 素 之 使 用, 在 成 本 上 減 少 了 許 多 與 [1], [4] 相 比 較, 在 66 個 符 號 之 循 序 電 路 上, 更 是 降 低 了 84%( = ( )/639) [8] 與 67.4%( = ( )/313) [11] 的 邏 輯 使 用 率, 因 此 在 循 序 電 路 上, 44

52 高 效 能 記 憶 體 與 快 速 的 霍 夫 曼 解 碼 演 算 法 較 為 適 用, 明 顯 降 低 邏 輯 元 素 的 使 用 率 表 6.1 使 用 EP1S10F484C5 之 66 個 符 號 的 循 序 電 路 比 較 BDD-based 霍 夫 曼 解 碼 器 ( 1- 位 元 解 碼 器 共 7 組 ) [1] 使 用 FPGA 完 成 低 成 本 霍 夫 曼 解 碼 器 [5] 使 用 FPGA 完 成 高 速 霍 夫 曼 解 碼 器 [4] 邏 輯 使 用 率 邏 輯 個 數 解 碼 時 間 6% 639 1% 102 3% 313 h 一 個 時 脈 的 時 間 h 一 個 時 脈 的 時 間 h 一 個 時 脈 的 時 間 接 著 以 多 工 器 製 作 的 解 碼 電 路, 文 中 以 壓 縮 霍 夫 曼 編 碼 表 在 使 用 FPGA 製 作 成 的 多 工 器 電 路, 所 使 用 的 邏 輯 元 素 只 需 要 到 140 個 邏 輯 元 素, 即 可 完 成 電 路, 解 碼 時 間 在 8 ns, 而 [1] 需 要 141 的 邏 輯 元 素, 其 解 碼 時 間 為 10 ns, 在 解 碼 的 時 間 上, 以 壓 縮 霍 夫 曼 編 碼 表 的 方 法 更 適 合 處 理 多 個 符 號, 如 表 6.2 所 示 表 6.2 使 用 EP1S10F484C5 之 66 個 符 號 的 多 工 器 電 路 比 較 邏 輯 使 用 率 邏 輯 個 數 解 碼 時 間 BDD-based 霍 夫 曼 解 碼 器 [1] 1% ns 使 用 FPGA 完 成 高 速 霍 夫 曼 解 碼 1% ns 器 [4] 45

53 第 七 章 結 論 在 本 文 中, 首 先 以 陣 列 的 方 式 儲 存 符 號 及 頻 率, 再 針 對 此 陣 列 進 行 演 算 並 給 予 每 一 個 符 號 CL 值, 接 著 對 每 一 個 符 號 作 重 新 編 碼 的 動 作, 使 每 一 個 編 碼 具 有 連 續 的 性 質, 再 壓 縮 此 霍 夫 曼 表, 將 此 表 格 視 為 一 個 搜 尋 表 (L UT), 與 原 本 的 編 碼 表 來 看, 所 需 要 的 記 憶 體 空 間 的 減 少 至 3 ~ (3n - 3), 接 著 使 用 壓 縮 霍 夫 曼 表 以 FPGA 實 作 邏 輯 電 路, 邏 輯 電 路 都 使 用 Altera 公 司 的 EP1S10F48 4C5 進 行 模 擬 測 試, 在 66 個 符 號 上, 整 個 邏 輯 元 素 使 用 量 為 313 個 邏 輯 元 素, 每 一 個 時 脈 為 10 ns, 對 每 一 個 符 號 的 解 碼 時 間 為 h 個 時 脈 為 了 使 邏 輯 元 素 及 解 碼 時 間 進 一 步 降 低, 使 用 多 工 器 來 實 現, 與 循 序 電 路 比 較, 多 工 器 在 邏 輯 元 素 上, 減 少 了 55.3% 的 使 用 個 數, 與 [1] 相 比 較, 邏 輯 元 素 之 使 用 率 差 不 多, 在 解 碼 時 間 上, 本 文 的 解 碼 時 間 為 8 ns 較 為 快 速 為 了 進 一 步 降 低 在 循 序 電 路 上 的 邏 輯 元 素 使 用 率, 使 用 了 高 效 能 記 憶 體 與 快 速 的 霍 夫 曼 解 碼 演 算 法, 在 處 理 符 號 數 較 少 與 符 號 數 較 多 的 硬 體 解 碼 電 路 上, 與 [1], [4] 比 較, 循 序 電 路 的 邏 輯 元 素 使 用 率 上, 以 8 個 符 號 分 別 降 低 了 約 41% [1] 與 90% [4], 在 66 個 符 號 上 更 是 降 低 了 84% [1] 與 67.4% [4] 的 邏 輯 使 用 率, 而 且 本 電 路 具 有 偵 錯 的 功 能, 能 偵 測 出 有 錯 誤 的 編 碼 解 碼 霍 夫 曼 碼 需 要 將 每 一 個 編 碼 區 隔 避 免 解 碼 錯 誤, 具 避 免 錯 誤 擴 散 的 特 性, 是 以 軟 體 的 方 式 運 作, 論 文 中 所 使 用 的 演 算 法, 實 現 在 FPGA 上, 不 僅 可 以 達 到 連 續 解 碼, 解 碼 兩 個 符 號 之 間 不 需 要 區 隔 標 示 記 號, 並 能 偵 錯 ( 但 無 法 達 100% 偵 錯 率, 但 無 法 避 免 錯 誤 擴 散 ), 以 硬 體 的 方 式 解 碼 比 軟 體 的 方 式 更 快 更 有 效 率, 以 循 序 電 路 的 方 式 解 碼 每 一 個 符 號 之 霍 夫 曼 編 碼 只 需 要 h 個 時 脈 的 時 間, 換 成 使 用 多 工 器 的 方 式, 更 可 以 在 一 個 時 脈 的 時 間, 就 完 成 了 一 個 符 號 解 碼 46

54 參 考 文 獻 [1] 吳 其 政, 李 志 遠, 吳 家 榮, 邱 煌 森, 吳 東 旭, 以 低 成 本 FPGA 實 現 高 速 霍 夫 曼 解 碼 器, 第 三 屆 智 慧 生 活 科 技 研 討 會, 中 華 民 國 台 中, pp , [2] 吳 家 榮, 吳 其 政, 邱 煌 森, 一 個 高 效 能 記 憶 體 與 快 速 的 霍 夫 曼 解 碼 演 算 法, 第 二 屆 海 峽 兩 岸 科 技 與 人 文 教 育 暨 產 學 合 作 研 討 會, 中 華 民 國 台 中, pp , [3] 吳 家 榮, 吳 其 政, 邱 煌 森, 吳 東 旭, 周 文 正, 使 用 壓 縮 霍 夫 曼 表 之 高 效 率 霍 夫 曼 解 碼 演 算 法, 第 五 屆 網 際 網 路 暨 通 訊 科 技 研 討 會, 中 華 民 國 淡 水, pp , [4] 吳 家 榮 周 文 正 吳 其 政 邱 煌 森 吳 東 旭, 使 用 FPGA 完 成 高 速 霍 夫 曼 解 碼 器, 第 四 屆 智 慧 生 活 科 技 研 討 會, 中 華 民 國 台 中,, 2009 [5] 吳 家 榮 周 文 正 吳 東 旭 吳 其 政 邱 煌 森, 使 用 FPGA 完 成 低 成 本 霍 夫 曼 解 碼 器, 2009 資 訊 管 理 技 術 與 實 務 應 用 發 展 暨 資 訊 人 才 培 育 研 討 會, 中 華 民 國 淡 水, pp , [6] D. A. Huffman, A Method for construction of minimum redundancy codes, Proceedings of IRE, Vol. 40, no. 10. pp , September [7] R. Hashemian, Memory Efficient and high-speed search Huffman coding, IEEE trans. Communications, Vol. 43, pp , [8] R. Hashemian, Condensed Huffman coding, A New Efficient Decoding Technique, IEEE trans. Communications, vol. pp.i I-231, [9] P. C. Wang, Y. R. Yang, C. L. Lee, and H. Y. Chang, A Memory-efficient Huffman Decoding Algorithm, IEEE AINA'05, Tamkang University, pp , [10] H. C. Chen, Y. L. Wang, and Y. F. Lan, A Memory Efficient and fast Huffman decoding algorithm, Information Processing Letters, Vol.69, pp ,

55 [11] K. L. Chung, Efficient Huffman decoding, Information Processing Letters, Vol.61, pp.97-99, [12] V. Iyengar, and K. Chakrabarty, An Efficient Finite-State Machine implementation of Huffman decoders, Information Processing Letters, Vol.64, pp ,