臺灣博碩士論文加值系統

目前應用在影音訊號之壓縮標準，如JPEG、MPEG都會使用到赫夫曼解碼器。由於赫夫曼碼碼長不一的特性，赫夫曼碼解碼器設計不易。現今存在的赫夫曼解碼器，大部分皆以資料結構觀點進行赫夫曼解碼。本實驗室於去年針對赫夫曼解碼法提出另一看法，將赫夫曼碼看成一數值序列，然後以數值分析的方法來解碼，我們稱之為「數值赫夫曼解碼器」，此方法既可快速解碼而且記憶體需求小。本篇論文承襲上述的數值赫夫曼解碼理論，提出一硬體架構來實現此數值赫夫曼解碼器。本次實現的解碼器，可處理赫夫曼碼的長度最長為16位元，主要的運算單元為一個「加法器」和一個「位移暫存器」，再配合五個「多工器」與十二個「暫存器」即可實現。另外，我們依照「特殊應用積體電路的設計流程（ASIC Design Flow）」，對我們所設計的硬體架構進行模擬驗證。最後，我們並結合FPGA實驗板與電腦印表機傳輸埠來進行此解碼器的實體驗證。以證明我們所提出的數值赫夫曼解碼理論，其解碼功能正確且實現低複雜度的優點。

The compressing standard on audio and video signals, such as JPEG or MPEG, includes the function of Huffman decoder. Decoding Huffman code is difficult because of the inherent property of varying code length. Existing algorithms for Huffman decoder are developed based on the data structure of Huffman codes. Using a new perspective to treat the Huffman code as a numerical sequence, we have designed a new Huffman decoder, referred to as the numerical Huffman decoder, which, compared with existing algorithms, has a better performance on decoding speed and realization complexity. This thesis proposes a hardware architecture to realize the numerical Huffman decoder. We aims to develop a hardware Huffman decoder for Huffman codes of 16-bits maximum length. The major hardware includes an adder and a shift-register,
along with five multiplexers and twelve registers. Besides, we have followed the ASIC design flow to present an IC for the Huffman decoder.
Finally, the decoding function is verified by combining the hardware decoder with printer-port transmission in an FPGA board.

一、緒論
1.1 研究動機與目的
1.2 赫夫曼解碼技術回顧
1.3 論文架構
二、數值赫夫曼解碼方法
2.1 赫夫曼碼重組與解碼的觀念
2.2 數值方法
2.3 分段技術
三、實現數值赫夫曼解碼器
3.1 全系統架構
3.2 解碼器實現
3.3 EPP介面實現
3.4 設計與驗證流程
3.5 FPGA軟體模擬
3.6 工作站設計輔助工具
四、以FPGA實體驗證
4.1 系統實體照片
4.2 驗證流程
4.3 結果
五、結論

1. ISO/IEC International Standard IS 10918-1 (ITU-T T.81)
2. R. Hunter and A. H. Robinson, ``International Digital Facsimile Standard," Proc. IEEE, vol. 68, no. 7, pp. 854-867, 1980
3. A. Huffman, ``A Method for the Construction of Minimum Redundancy Codes," Proc. IRE, vol.
40, 1952.
4. C. T. Hsieh and S. P. Kim, ``A Concurrent Memory-Efficient Vlc Decoder for MPEG
Application," IEEE. Trans. Consumer Electronics, pp.
439-446, vol. 42, No. 3, Aug. 1996.
5. K. L. Chung and J. G. Wu, ``Level-Compressed Huffman Decoding," IEEE. Trans. Communication, pp. 1455-1457, vol. 47, No. 10, Oct. 1999.
6. H. C. Chen and Y. L. Wang and Y. F. Lan, ``A Memory-Efficient and Fast Huffman Decoding
Algorithm," Information Processing Letters 69, pp. 119-122,
1999.
7. R. Hashemian, ``Memory Efficient and High-Speed
Search Huffman Decoding," IEEE. Trans. Communication, pp.
2576-2581, Oct. 1995.
8. K. L. Chung and Y. K. Lin, ``A Novel Memory-Efficient Huffman Decoding
Algorithm and its Implementation," IEEE. Trans. Signal
Processing 62, pp. 207-213, 1997.
9. 林丕靜， 數值分析，儒林，1992。
10. 李俊顏， 使用年頓法之一快速有效的赫夫曼解碼器 ，
碩士論文，國立交通大學電機與控制工程學系， 2001。
11. 林傳生， 使用VHDL電路設計語言之數位電路設計，
儒林，1997。
12. K. C. Chang, Digital Systems Design
with VHDL and Synthesis:An Integrated Approach,
Computer Society, 1999.
13. P. H. Anderson,
[http://et.nmsu.edu/etti/fall96/computer/printer/printer.html]
14. 謝聿婷， IBM PC介面技術與週邊設備實習 ，
全欣， 1987。
15. 蔡明志， Turbo C/C++ Bible， 松崗， 1996。
16. M. John and S. Smith,
Application-Specific Integrated Circuits, Addison Wesley, 1997.
17. M. M. MANO, Digital Design, Prentice Hall, 1991.
18. D. A. Patterson and J. L. Hennessy,
Computer Organization and Design the Hardware/Software
Interface, Morgan Kaufmann, 2000.
19. V. K. Madisetti, VLSI Digital Signal
Processors (An Introduction to Rapid Prototyping and Design
Synthesis) , Butterworth Heinemann, 1995.
20. N. H. E. Weste and K. Eshraghian, Principles of CMOS VLSI
Design, Addison Wesley, 1994.
21. R. C. Gonzalez and R. E. Woods, Digital Image
Processing, pp. 349-351 , Addison Wesley, 1993.