臺灣博碩士論文加值系統

二維的離散餘弦轉換（two-dimensional discrete cosine transform, 2D DCT）廣泛的被認為是運用於影像壓縮上最有效的壓縮技術，尤其是在高速傳輸數位影像處理的應用上。硬體實現架構大致上可被分為兩類：一類為直接法（direct method）;另一類為間接法（indirect method），又被稱為行列法（row-column method）。由於直接法雖然會比較有效率，可是在硬體實現上的複雜度相對的增加不少，故一般均採用行列法。2D DCT的行列演算法是藉著先計算輸入區塊(8*8)在列（rows）或行（columns）的資料的一維離散餘弦轉換（one-dimensional DCT, 1D DCT），而得到一轉換矩陣，將其存入一暫存的轉換矩陣後，經過行列互換，再一次計算此轉置矩陣在行或列的資料之一維離散餘弦轉換。經過兩次的一維DCT轉換，兜成一個二維的轉換。
而在一維的DCT處理過程中:
(1)我們先將整個DCT行列式轉成兩個4乘4的矩陣，然後其中將非輸入值的係數，轉換成1的補數的型式，其中這些非輸入係數值的每一個bit，皆有其個別的加權。
(2)經過步驟(1)處理後的式子，整理出八個係數矩陣，根據這八個係數矩陣，我們可求得所有輸出DCT係數的部分積，而要組成這些部分積，在電路中只需要26個加法器。
(3)得到的這些部分積，我們可以利用add_shift電路或者4-2 compressor tree把這些部分積依各自加權做相加，即可得到1D DCT係數。
依照此方法，和2000年發表的New Distributed Arithmetic Architecture technique(NEDA)的架構相比，我們的1D DCT硬體架構可以在完全不改變執行速度的情況下，將加法器從35個減低到只需要26個。而且如果硬體設計成平行處理的情況下，速度將可達到最快，其最大的delay time只有4-2compressor tree和一個加法器的延遲。

The two dimensional discrete cosine transform (2D-DCT) is widely used in digital signal processing, particularly for digital image processing in high speed transmission. There are two classes to realize in hardware structure, including the direct method, and the indirect method which is also called row-column method. It is more efficient for using the direct method. However, due to the computational complexity, the row-column method still has been adopted in the hardware implementation.
In the indirect method, one dimensional of the rows or columns DCT coefficient are computed in advance. Then, a transpose matrix is obtained, and the elements of the transpose matrix are saved in a transpose matrix register. By the pivoting the elements of rows and columns, the one dimensional DCT of the transpose matrix is computed again. From performing twice one dimensional DCT transformations, then a two dimensional DCT has been formulated.
The processing steps of one dimensional DCT are as follows:
(1)Transform the DCT matrix into two 4*4 matrix. Then, change the elements of non-input data to 1’s complements. There 1’s complements have special weight individually.
(2)Eight coefficient matrices. Based on these eight coefficient matrices have been obtained by above processing step. The partial products of all DCT coefficient can be found out. In the implementation of the circuit, only 26 adders are needed.
(3)From this partial products, by means of adder_shift or 4-2 compressor tree circuit, we sum up all partial products by individual can be gained weight. Thus one dimensional DCT coefficients can be obtained.
Compare the architecture of this method with New Distributed Arithmetic Architecture technique(NEDA) structure published in 2000. Our adder s of 1D DCT needed can be reduced from 35 to 26 in the same bit rate. If the hardware is designed in pipelined processing, the speed will be more promoted. The delay time is only equal to the delay of 4-2 compressor tree and an adder.

目錄
項　　　目
中文摘要-------------------------------------------------------------------------i
英文摘要-------------------------------------------------------------------------ii
致謝-------------------------------------------------------------------------iv
目錄-------------------------------------------------------------------------v
表目錄-------------------------------------------------------------------------viii
壹、緒論----------------------------------------------1
1.1MPEG視訊標準-----------------------------------------------------1
1.2現場可程式邏輯閘陣列(FPGA)------------------------------------2
1.3DCT離散餘弦轉換--------------------------------------------3
1.4研究動機----------------------------------------3
1.5論文內容--------------------------------------------------4
貳、MPEG與FPGA--------------------------------------------5
2.1MPEG的崛起---------------------------------------------5
2.2影像壓縮基本理論----------------------------------------------------5
2.2.1資料在空間上的多餘（Spatial Redundancy）-----------------6
2.2.2資料在時間上的多餘（Temporal Redundancy）----------6
2.2.3資料在編碼時位元樣型的多餘（Bit Pattern Redundancy）6
2.3MPEG基本機制--------------------------------------------------------7
2.3.1色彩格式（Color Format）--------------------------7
2.3.2取樣格式（Sampling Formats）----------------------------8
2.3.3轉換-------------------------------------------8
2.3.4量化（Quantization）-------------------------------9
2.3.5Zig-zag掃瞄（Zig-zag Scan）-------------------------------10
2.3.6移動預估（Motion Estimation）---------------------11
2.3.7移動補償(Motion Compensation, MC)------------------------11
2.3.8跑長度編碼（Run Length Coding, RLC）----------------12
2.3.9可變長度編碼 （Variable Length Coding, VLC）------------12
2.3.10固定長度編碼（Fixed Length Coding, FLC）----------------12
2.4MPEG壓縮與解壓縮系統------------------------------------13
2.5FPGA的優點及種類---------------------------------------14
2.6FPGA內部硬體裝置--------------------------------16
2.7硬體描述語言Verilog-----------------------------17
參、DCT硬體電路架構------------------------------------18
3.1DCT轉換----------------------------------------------18
3.2直接法 （direct method）---------------------------19
3.3行列法（row-column method）------------------------------22
3.3.1蝴蝶結構(Butterfly structure)---------------------22
3.3.2乘加器架構(Multiplier Accumulator Arithmetic)------26
3.3.3分散式架構(Distributed Arithmetic)-----------------29
肆、NEDA架構及其改進------------------------------------------31
4.1NEDA架構-------------------------------------------------------31
4.2NEDA架構的數學推導-----------------------------------------31
4.3NEDA部分積的取得-------------------------------------------32
4.4NEDA的改進------------------------------------40
4.5改進架構的後處理動作-------------------------------------45
4.5.1後處理動作架構------------------------------------45
4.5.2壓縮樹(Compressor Tree)-------------------------46
伍、DCT電路的實現------------------------------------------------49
5.1軟體的模擬----------------------------------------49
5.2硬體描述語言的撰寫------------------------------50
5.3硬體描述語言的軟體模擬--------------------------53
5.4硬體描述語言的合成與實現------------------------54
陸、結論與展望---------------------------------------57
6.1結論-------------------------------------------57
6.2未來發展------------------------------------------58
參考文獻---------------------------------------------------------------59




表目錄
表 3.1式(3.12)相關矩陣對照乘法器和加法器數目--------- 25
表 3.2Booth乘法器3bits的編碼-----------------------28
表 4.1 的係數矩陣-------------------------------33
表 4.2 的係數矩陣------------------------------33
表 4.3 的係數矩陣-------------------------------35
表 4.4 的係數矩陣-------------------------------35
表 4.5 的係數矩陣-------------------------------35
表 4.6 的係數矩陣-------------------------------35
表 4.7 的係數矩陣-------------------------------36
表 4.8 的係數矩陣-------------------------------36
表 4.9一維DCT架構部分積的加減法器需求----------------39
表 4.10分解後 的係數矩陣-------------------------41
表 4.11分解後 的係數矩陣-------------------------41
表 4.12分解後 的係數矩陣------------------------41
表 4.13分解後 的係數矩陣------------------------41
表 4.14分解後 的係數矩陣------------------------42
表 4.15分解後 的係數矩陣------------------------42
表 4.16分解後 的係數矩陣------------------------42
表 4.17分解後 的係數矩陣------------------------42
表 4.18改進後一維DCT架構部分積的加減法器需要-------44
表 5.1Spartan-2 Family members---------------49
表 5.22D DCT內部子電路分析--------------------------55


圖目錄
圖 2.1連續影像8´8 DCT係數矩陣之頻率分佈關係------------------9
圖 2.2典型量化函數圖-----------------------------------------10
圖 2.3預設之框內量化矩陣-----------------------------------------10
圖 2.4預設之框間量化矩陣----------------------------------10
圖 2.5Zig-zag order ---------------------------------------11
圖 2.6MPEG編碼架構圖-----------------------------------13
圖 2.7MPEG解碼架構圖-----------------------------------------14
圖 2.8積體電路類型---------------------------------------15
圖 2.9FPGA內部整體架構----------------------------------------16
圖3.1Raja Neogi直接式二維離散餘弦轉換器的架構-------21
圖3.2子離散餘弦轉換單元------------------------------22
圖3.3由兩個一維DCT和轉換矩陣組成二維DCT-----------22
圖3.4蝴蝶結構的一維DCT ------------------------------------25
圖3.5DCT前處理電路------------------------------------------27
圖3.6利用乘法器組成的累加器電路---------------------------------27
圖3.7以ROM為基礎的分散式架構---------------------------------30
圖4.1實現 部分積的加法樹------------------------------------33
圖4.2實現 部分積的加法樹----------------------------34
圖4.3實現 部分積的加法樹-------------------------------36
圖4.4實現 部分積的加法樹------------------------------ 37
圖4.5實現 部分積的加法樹------------------------------37
圖4.6實現 部分積的加法樹------------------------------ 38
圖4.7實現 部分積的加法樹------------------------------ 38
圖4.8實現 部分積的加法樹---------------------------- 39
圖4.9改進後實現 部分積的加法樹--------------------------43
圖4.10改進後實現 部分積的加法樹-------------------43
圖4.11利用一個compressor tree做後處理動作-------------45
圖4.12多個compressor tree做管線化後處理動作-----------46
圖4.134-2compressor在8*8乘法器上的應用---------------47
圖4.14compressor tree的排列---------------------------47
圖4.15一個4-2compressor的內部設計例子-----------------48
圖5.1前一維DCT架構內部電路位元數---------------------49
圖5.2後一維DCT架構內部電路位元數------------------50
圖5.3一個DP RAM的模組接腳------------------------51
圖5.4DP RAM的寫入讀出順序-----------------------52
圖5.5完整二維DCT module-----------------------------52
圖5.6DCT module輸入情況------------------------------53
圖5.7DCT module輸出情況------------------------------53
圖5.8DCT module電路重置(reset)情況------------------53
圖5.9FPGA硬體Layout圖-------------------------------56

參考文獻[1]ISO/IEC 13818: Information Technology — Generic Coding of Moving Pictures and Associated Audio Information, ISO/IEC JTC1, Part2: Video, Draft International standard, 1994.[2]“Video Codec for Audiovisual Services at p*64 kbits,” ITU Recommendation H.261, 1990.[3]K. R. Rao, J. J. Hwang, Techniques and Standards for Image, Video, and Audio Coding, Prentice Hall PTR, 1996.[4]Ahmed, N. T. Natarajan, K. R. Rao, “Discrete Cosine Transform,” IEEE Trans. On Computers, vol. C-23, pp. 90-94, Jan, 1974.[5]T. Sikora, ”MPEG digital video-coding standards,” IEEE signal processing magazine, pp.82-100, 1997.[6]R. Neogi, “Real-time integrated video-compression architecture for broadcasting HDTV and multimedia applications,” IEEE Intl. ASIC Conf., Austin, TX, pp. 79-82, 1995.[7]B. G. Lee. “A New Algorithm to Compute the Discrete Cosine Transform,” IEEE Trans. Acoustic, Speech and Signal Processing, vol. ASSP-32. No. 6, pp. 1243-1245, 1984.[8]Ahmed Shams, Magdy. Bayoumi, “A 108 Gbps, 1.5 GHz 1D-DCT architecture,” IEEE International Conference, pp 163 —172, 2000.[9]Ahmed Shams, Wendi Pan, Magdy. Bayoumi, “A High-Performance 1D-DCT Architecture,” IEEE international symposium on circuit and systems, May, pp521-524, 2000.[10]Wendi Pan, Ahmed Shams, Magdy. Bayoumi, “NEDA: a new distributed arithmetic architecture and its application to one dimensional discrete cosine transform,” IEEE SiPS, October 1999, Taipei, Taiwan.[11]Peled, B. Liu, ”A New Approach to the Realization Nonrecursive Digital Filters,” IEEE Trans, Audio and Electroacoustics, vol. 21, no. 6, pp. 477-485, 1973.[12]Peled, B. Liu, ”A New Hardwire Realisation of Digital Filters,” IEEE Trans. On ASSP, 22(6), pp.456-462, 1974.[13]J. Mori, M. Nagamatsu, M. Hirano, S. Tanaka, M. Noda, Y. Toyoshima, K. Hashimoto, H. Hayashida, K. Maeguchi, “A 10 ns 54*54 b parallel structured full array multiplier with 0.5 mu m CMOS technology,” IEEE Journal of Solid-State Circuit, vol, 26, no. 4, pp. 600-606 1991.[14]P. Bonatto, V. G. Oklobdzija, “Evaluation of Booth''s algorithm for implementation in parallel multipliers,” IEEE Conference Record of the Twenty-Ninth Asilomar Conference, pp. 608-610, 1996.[15]Z. Mohd-Yusof, I. Suleiman, Z. Aspar,” Implementation of two dimensional forward DCT and inverse DCT using FPGA,” IEEE TENCON, vol. 3, pp. 242 —245, 2000.[16]Yuk Ying Chung, N. W. Bergmann, “Implementation of DCT for video compression with reconfigurable technology,” IEEE Region 10 Annual Conference. Speech and Image Technologies for Computing and Telecommunications, vol. 2 pp. 441-444, 1997.[17]Xilinx,“The Programmable Logic Data Book,”,Xilinx Inc , 2000.[18]朱明程, FPGA原理及應用設計, 電子工業出版社, 1994.[19]Samir Palnitkar, "Verilog HDL: A Guide to Digital Design and Synthesis", Prentice Hall, 1997[20]J. F. Cavanagh, Digital Computer Arithmetic, McGraw-Hill, 1983.[21]John Miano, Compressed Image File Format, ACM Press, 1999.[22]郭承岳, 以FPGA實現時信號處理之研究, 雲林科技大學電機工程系碩士論文, 1999.