研究生: |
張勇毅 Yung-yi Chang |
---|---|
論文名稱: |
資料壓縮/解壓縮智產架構設計與驗證 The Design and Verification of a Data Compression and Decompression IP Architecture |
指導教授: |
林銘波
Ming-Bo Lin |
口試委員: |
詹景裕
none 白英文 none 陳郁堂 Yie-Tarng Chen |
學位類別: |
碩士 Master |
系所名稱: |
電資學院 - 電子工程系 Department of Electronic and Computer Engineering |
論文出版年: | 2007 |
畢業學年度: | 95 |
語文別: | 中文 |
論文頁數: | 69 |
中文關鍵詞: | 資料壓縮 、LZW演算法 、霍夫曼演算法 |
外文關鍵詞: | data compression, LZW, huffman |
相關次數: | 點閱:166 下載:10 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
論文中採用二階層無失真資料壓縮/解壓縮演算法,它結合了PD-LZW演算法及近似動態霍夫曼演算法。第一層的PD-LZW演算法將字典使用靜態記憶體取代大部分CAM的架構以節省面積;第二層採用兩個靜態記憶體來實現符號出現機率的排序串列以代替動態霍夫曼演算法的樹狀架構。將壓縮與解壓縮硬體架構資源共用後,共使用112位元組的CAM、1048位元組的SRAM與29位元組的ROM。
最後,本論文將此架構以晶片實現。整個資料壓縮、解壓縮的硬體架構可細分成六級的管線,每級管線之間採用交握訊號來做為溝通。整體來說平均使用3個時脈週期完成一筆資料壓縮、解壓縮的動作,在FPGA模擬方面,透過Xilinx公司的Spartan3型FPGA,使用了4165個LUT,且操作頻率可達68 MHz;在元件庫設計方面,使用TSMC 0.35 μm Mixed-Signal 2P4M製程,晶片面積2.9 × 2.9 mm2,在工作頻率100 MHz下,消耗功率在壓縮時為394 mW,解壓縮時為333 mW;資料處理量為266 Mbits/sec ~ 1.33 Gbits/sec。
In this thesis, we study the implementation of a two-level lossless data compression architecture that combines the PD-LZW algorithm and an approximated adaptive Huffman algorithm. In the first level, we replace most of CAM dictionaries by SRAMs in order to reduce hardware resource; in the second level, an ordered list implemented by two SRAMs is used to simulate the tree-based adaptive Huffman algorithm. Hardware architecture in compression and decompression can also share a 112-byte CAM memory, a 1048-byte SRAM and a 29-byte ROM.
To demonstrate our proposed architecture, the design has been realized by using FPGA and a cell-based library. In the FPGA part, it takes 4165 LUTs and operates at the internal working frequency of 68 MHz. In the cell-based part, the resulting chip occupies 2.9 × 2.9 mm2 and dissipates 394 mW in compression operation, 333 mW in decompression operation. Throughput in compression and decompression is between 266 Mbits/sec and 1.3 Gbits/sec.
[1]D. A. Huffman, “A method for the construction of minimum redundancy codes,” Proceedings of IRE, Vol. 40, pp. 1098-1101, 1952.
[2]R. M. Fano, “The transmission of information,” Technical Report 65, Research Laboratory of Electronics, MIT, Cambridge, MA, 1949.
[3]I. H. Witten, R. Neal, and J.G. Cleary, “Arithmetic coding for data compression,” Communication of the Association for computing Machinery, Vol. 30, No. 6, pp. 520-540, Jun., 1987.
[4]J. Ziv and A. Lempel, “A universal algorithm for sequential data compression,” IEEE Trans. Information Theory, Vol. IT-23, No. 3, pp. 337-343, May, 1977.
[5]J. Ziv and A. Lempel, “Compression of individual sequences via variable-rate coding,” IEEE Trans. Information Theory, Vol. IT-24, No. 5, pp. 530-536, Sep., 1978.
[6]T. A. Welch, “A technique for high performance data compression,” IEEE Computer, Vol. 17, No. 6, pp. 8-20, 1984.
[7]G. Held, Data and Image Compression Tools and Technique, 4th ed., Chapter 9, 1996.
[8]R. B. Arps and T. K. Truong, “Comparison of international standard lossless still image Compression,” Proceedings of the IEEE, Vol. 82, No. 6, pp. 889-899, Jun., 1994.
[9]M. B. Lin, “A parallel VLSI architecture for the LZW data compression algorithm,” International Symposium on VLSI Technology, Systems, and Applications, Taiwan, pp. 98-101, 1997.
[10]M. B. Lin and Jiun-Woei Chen, “A Multilevel Hardware Architecture for Lossless Data Compression Applications,” 1999 National Computer Symposium, Dec. 20-21, 1999, Taiwan, pp.289-292.
[11]M. B. Lin, “A parallel VLSI architecture for the LZW data compression algorithm,” Journal of VLSI Signal Procedding, 2000.
[12]I. H. Witten, A. Moffat, and T. C. Bell, Managing Gigabytes: Compressing and Indexing Documents and Images, 2nd ed., Academic Press, pp. 36-51, 1999.
[13]D. E. Knuth, “Dynamic Huffman coding,” Journal of Algorithms, Vol. 6, pp. 163-180, 1985.
[14]R. G. Gallager, “Variation on a theme by Huffman,” IEEE Trans. on Information Theory, Vol. IT-24, pp. 668-674, 1978.
[15]B. W. Y. Wei, J. L. Chang, and V.D. Leong, “A Single-chip lossless data compressor,” Proceedings of International Symposium on VLSI Technology, Systems, and Applications, IEEE, Piscataway, NJ, USA., pp. 211-213, 1995.
[16]R. Arnold and T. C. Bell, “A corpus for the evaluation of lossless compression algorithms,” DCC ’97 Proceedings, pp. 201-210, 1997.
[17]T. C. Bell, J. G. Cleary, and I. H. Witten, Text Compression, Englewood Cliffs: N. J. Prentice Hall, 1990.
[18]M. B. Lin, “On the design of fast large fan-in CMOS multiplexers,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, Vol. 198, pp. 963-967, Aug. 2000.
[19]李張豐,多階層資料壓縮演算法設計與晶片製作,國立台灣科技大學,電子工程研究所,碩士論文,西元2000年6月.
[20]陳堯昌,多階層資料壓縮晶片架構設計與製作,國立台灣科技大學,電子工程研究所,碩士論文,西元2001年12月.
[21]陳均煒,多階層式資料壓縮晶片架構設計,國立台灣科技大學,電子工程研究所,碩士論文,西元1999年6月.
[22]林書彥,多階層資料壓縮/解壓縮智產架構設計與驗證,國立台灣科技大學,電子工程研究所,碩士論文,西元2004年6月.
[23]Kostas Pagiamtzis, Ali Sheikholeslami, “Content-Addressable Memory (CAM) Circuits andArchitectures: A Tutorial and Survey,” IEEE Journal of Solid-State Circuits, Vol. 41, pp. 712-727,No. 3, March 2006.
[24]M. B. Lin, J. F. Lee, and G. E. Jan, “A Lossless Data Compression and Decompression Algorithm and Its Hardware Architecture,” IEEE Trans. on Very Large Scale Interation (VLSI) Systems, Vol. 14, pp. 925-936, No. 9, Sept. 2006.