近年來，CPU的工作速度愈來愈快，但是受限於匯流排的頻寬，常常使的CPU無法執行快速而有效的運算。無論是電腦系統上的各種匯流排、有線網路或是無線網路等，都可利用無失真壓縮技術來減少資料的傳輸量，以增進整體系統的運作速度。產量(throughput)在高效能壓縮演算法中是非常重要的，然而，無失真壓縮方法常受限於連續搜尋字串的時間和編解變動長度編碼的時間，使得硬體實作上不易達到Giga bits/s以上的產量。

　　本論文中我們提出一個用於網路或匯流排兼具速度與壓縮率的無失真資料壓縮方法及其硬體架構。在編碼匹配型態(match type)和字典位址部分，我們使用適應性(adaptive)和預測(prediction)方法來減少壓縮率(輸出/輸入)；儲存字典則利用內容定址記憶體(CAM)來動態編碼匹配型態和字典位址。此外，我們也改良了字串匹配的演算法並使用管線(pipeline)技術增加系統產量、減少延遲並降低額外的消耗。模擬結果顯示，此VLSI電路的操作頻率可達153.8MHZ，並達到4.9Gbits/s的產量。

　　Although the working rate of CPU grows faster and faster, the whole system is not easy to utilize the full-power of CPU efficiently due to the limitation of bus bandwidth. No matter in the buses of computing system, wire network or wireless network, we can improve the working speed of whole system by using lossless data compression technique to reduce the data size for transmission. Throughput is very important issue for high-performance compression algorithms. However, most lossless data compression method cannot achieve Giga bits throughput because both the searching time and variable-length encoding time are quite long.

　　In this thesis, we propose a high speed and high compression ratio lossless data compressor for the applications of network and system bus. While encoding match type and dictionary address, we use an adaptive and predictive method to reduce the necessary bitstream. Besides, a Content Addressable Memory (CAM) is adopted for dictionary storage by storing the dynamic coding of match type and dictionary locations. For hardware implementation, we use the pipeline architecture to overcome the bottleneck of system throughput, reduce delay and reduce cost. In the simulation, it achieves 153.8 MHZ clock frequency and 4.9 Gbits/second throughput.

[1] Compression and coding algorithms, Alistair Moffat, Andrew Turpin, Kluwer Academic Publishers, 2002.
[2]A. Moffat, “Implementing the PPM data compression scheme,” IEEE Trans. Commun., vol. 38, pp. 1917–1921, 1990.
[3]J. Cleary and I. Witten,“Data compression using adaptive coding and Partial string matching,” IEEE Trans. Commun., vol. 32, pp. 396–402, 1984.
[4]G. V. Cormack and R. N. S. Horspool, “Data compression using dynamic Markov modeling,” Comput. J., vol. 30, no. 6, pp. 541–549, 1987.
[5]Solving the Problems of Context Modeling, C. Bloom.(1998).
[6]T. Bell, J. Cleary, and I. Witten, Text Compression. Englewood Cliffs, NJ:Prentice-Hall,1990.
[7]D. Huffman, “A method for the construction of minimum redundancy codes,” in Proc. I.R.E, 1958, pp. 1098–1101.
[8]G.Langdon,“An introduction to arithmetic coding,” IBMJ. Res. Develop., vol. 28, no. 2, pp. 135–149, Mar. 1984.
[9]A. Moffat,N. Sharman, I.Witten, and T.Bell, “An empirical evaluation Of coding methods for multi-symbol alphabets,” Inf. Process. Manage., vol.30, no.6, pp.791–804, 1994.
[10]M. Boo,J. D.Bruguera,andT.Lang,“A VLSI architecture for arithmetic coding of multilevel images,” IEEE Trans. Circuits Syst. II, vol.45, pp.163–168, Jan. 1998.
[11]J.Jiang,“A novel parallel design of a codec for black and white image compression,” Signal Process. Image Commun., vol. 8, no. 5, pp.465–474, 1996.
[12]W. B. Pennebaker etal., “An overview of the basic principles of the Q-coder adaptive binary arithmetic coder,” IBMJ. Res. Develop., vol.32, no.6, pp.717–725, Nov. 1988.
[13]J. JiangandS. Jones, “Parallel design of arithmetic coding,” Proc. Inst. Elect. Eng., pt. E, vol. 141, pp. 327–333, Nov. 1994.
[14]P.Elias, “Universal codeword sets and representations of the integers,” IEEE Trans. Inform. Theory, vol. 21, pp. 194–203, Mar. 1975.
[15]Y.Liu,“Design and hardware architectures for dynamic Huffman coding,” Proc. Inst. Elect. Eng. Comput. Digital Tech., vol. 142, no. 6, pp.411–418, Nov. 1995.
[16]ALDC1-40S-M, IBM Corporation, IBM Microelectronics Division, New York, 1994.
[17]J. M. Cheng and L. M. Duyanovich, “Fast and highly reliable IBM LZ1 Compression chip and algorithm for storage ,”in Proc. Hot Chips VII Symp., Aug. 14–15, 1995, pp. 155–165.
[18]9600 Data Compression Processor, Hi/fn Inc, Los Gatos, CA, 1999.
[19]HowLZSCompressionWorks,Hi/fnInc,LosGatos,CA,1996.
[20]陳培殷,”資料壓縮概論”,滄海書局,2001
[21]Jose Luis Nunez, Simom Jones “Gbit/s Lossless Data Compression Hardware,” IEEE Trans. VLSI System, vol. 11, NO. 3, June 2003