臺灣博碩士論文加值系統

離散富利葉轉換（DFT）在通訊、語音處理、影像處理、雷達、聲納系統等領域上皆已廣大地被應用。而一般實現離散富利葉轉換的運算架構大致可分為兩大類，一是管線化的systolic 架構；另一為以記憶體為主體的單一處理元件架構。離散餘弦轉換（DCT）在許多不同版本的影像壓縮標準中已被廣泛地採用。而現場可規劃閘陣列（FPGA）已成為ASIC設計的一種新趨勢。因此，我們將以FPGA技術來實現。
本論文探討如何以FPGA技術來實現：（1）管線化的架構下，只需log2N個複數乘法器、2log2N個複數加法器、2log2N個多工器、N個延遲元件(D型正反器)，且在N個脈波週期完成N點的離散富利葉轉換運算。（2）以記憶體為主體架構的方式下，包括了三個雙埠的隨機存取記憶體，一個唯讀記憶體，一個複數乘法器，二個複數加法器及一個多工器。可在N(log2N)個脈波週期完成N點的離散富利葉轉換運算。（3）在增加少許硬體下，改良此一架構，使其執行時間減半，即N(log2N)/2個脈波週期，完成N點的離散富利葉轉換運算。（4）以（2）的一維離散富利葉轉換運算架構來實現二維離散富利葉轉換運算。（5）離散餘弦轉換運算及二維離散餘弦轉換運算。

The Discrete Fourier Transform（DFT）has been widely applied in communcation, speech processing, image processing, radar and sonar systems, etc. The architecture of DFT implement can be classified into two fields：（1）one is a pipelined systolic architecture,（2）the other is a memory-based architecture. Discrete Cosine Transform（DCT）has been commonly adopted in the various atandardsfor image compression while FPGA has become a new trend of ASIC design, so we will apply FPGA techinque to implement the DFT and the DCT.

This thesis deals with how to use FPGA techinque to implement： （1）the pipelined systolic array architecture that requires log2N complex multipliers, 2log2N complex adders, 2log2N multiplexers, N delay elements and is able to provide a throughput of one transform sample per clock cycle; （2）the memory-based architecture that consists of three two-port RAM’s, one ROM, one complex multiplier, two complex adders, one multiplexer, and has capability of computing one transform sample every log2N+1 clock cycles on average; （3）Improved architecture in（2）under increasing little hardware that spends half of run time, i.e.N(log2N)/2; （4）2D-DFT that use architecture in（2）of 1D-DFT; （5）DCT operation and 2D-DCT operation.

中文摘要...........................................................i
英文摘要..........................................................ii
誌謝..............................................................iii
目錄...............................................................iv
表目錄............................................................ix
圖目錄...........................................................xii

第一章　前言........................................1
1.1　研究背景與動機..........................................1
1.2　論文架構組織............................................3

第二章　Systolic 架構的離散富利葉轉換之設計與實現...7
2.1　離散富利葉轉換之演算法..................................7
2.2　Systolic架構的離散富利葉轉換之設計.....................12
2.3　Systolic架構的離散富利葉轉換之實現與模擬...............14

第三章　記憶體為架構主體的離散富利葉轉換之設計與實現.........................................22
3.1　記憶體為架構主的體離散富利葉轉換之設計.................22
3.2　記憶體為架構主體的離散富利葉轉換之實現與模擬...........23
3.3　改良式的記憶體為架構主體的離散富利葉轉換之設計.........30
3.4　改良式的記憶體為架構主體的離散富利葉轉換之實現與模擬...30

第四章　二維離散富利葉轉換之設計與實現.............37
4.1　二維離散富利葉轉換之介紹...............................37
4.2　二維離散富利葉轉換之設計...............................38
4.3　二維離散富利葉轉換之實現與模擬.........................41

第五章　離散餘弦轉換之設計與實現...................58
5.1　離散餘弦轉換之演算法...................................58
5.2　離散餘弦轉換之設計.....................................62
5.3　記憶體為架構主體的離散餘弦轉換之實現與模擬.............63

第六章　二維離散餘弦轉換之設計與實現...............70
6.1　二維離散餘弦轉換之介紹.................................70
6.2　二維離散餘弦轉換之設計.................................71
6.3　二維離散餘弦轉換之實現與模擬...........................72

第七章　結論.......................................80
7.1　結論...................................................80
7.2　未來展望...............................................82

參考文獻...........................................83

附錄　A............................................86
A.1　模擬的完整電路..............................................86
A.1.1　systolic架構下使用FPGA模擬16點DFT運算之電路圖..........86
A.1.2　systolic架構下基本單元P1(16)之電路圖.....................86
A.1.3　16-bit多工器之電路圖.....................................87
A.1.4　16-bit複數延遲8個脈波週期之電路圖........................87
A.1.5　16-bit 延遲8個脈波週期之電路圖...........................88
A.1.6　16-bit 延遲1個脈波週期之電路圖...........................88
A.1.7　16-bit複數加法器/減法器之電路圖..........................89
A.1.8　16-bit複數乘法器之電路圖.................................89
A.1.9　P1(16)之定址/控制信號產生器之電路圖.......................90
A.1.10　systolic架構下基本單元P2(8)之電路圖.....................90
A.1.11　16-bit複數延遲4個脈波週期之電路圖......................91
A.1.12　16-bit延遲4個脈波週期之電路圖..........................91
A.1.13　P2(8)之定址/控制信號產生器之電路圖.......................92
A.1.14　systolic架構下基本單元P4(4)之電路圖.....................92
A.1.15　16-bit複數延遲2個脈波週期之電路圖......................93
A.1.16　16-bit延遲2個脈波週期之電路圖...........................93
A.1.17　P4(4)之定址/控制信號產生器之電路圖.......................94
A.1.18　systolic架構下基本單元P8(2)之電路圖.....................94
A.1.19　16-bit複數延遲1個脈波週期之電路圖.......................95
A.1.20　16-bit延遲1個脈波週期之電路圖............................95
A.1.21　P8(2)之定址/控制信號產生器之電路圖.......................96
A.2　模擬的時序圖.........................................97

附錄　B............................................98
B.1　模擬的完整電路.......................................98
B.1.1　記憶體為主體架構下使用FPGA模擬16點DFT運算電路圖........98
B.1.2　定址/控制信號產生器之電路圖.............................99
B.1.3　控制信號產生器之電路圖（一）...............................99
B.1.4　控制信號產生器之電路圖（二）..............................100
B.1.5　讀取RAM1定址產生器之電路圖..............................100
B.1.6　讀取RAM2定址產生器之電路圖..............................101
B.1.7　讀取/寫入RAM3定址產生器之電路圖.........................101
B.1.8　讀取ROM定址產生器之電路圖...............................102
B.1.9　寫入RAM1 & RAM2定址產生器之電路圖........................102
B.1.10　DFT 運算單元之電路圖....................................103
B.1.11　記憶體RAM之電路圖......................................103
B.1.12　記憶體ROM之電路圖......................................104
B.1.13　16-bit複數加法器/減法器之電路圖........................104
B.1.14　16-bit複數乘法器之電路圖...............................105
B.1.15　16/32-bit多工器之電路圖................................105
B.2　模擬的時序圖........................................106

附錄　C...........................................107
C.1　模擬的完整電路.............................................107
C.1.1　改良式之記憶體為主體架構下使用FPGA模擬16點DFT運算之電路圖
...........................................................107
C.1.2　定址/控制信號產生器之電路圖............................107
C.1.3　控制信號產生器之電路圖（一）.............................108
C.1.4　控制信號產生器之電路圖（二）.............................109
C.1.5　讀取RAM1定址產生器之電路圖..............................109
C.1.6　讀取RAM2定址產生器之電路圖..............................109
C.1.7　讀取RAM3定址產生器之電路圖..............................110
C.1.8　讀取RAM4定址產生器之電路圖..............................110
C.1.9　讀取ROM定址產生器之電路圖...............................111
C.1.10　寫入RAM1 & RAM2定址產生器之電路圖.......................111
C.1.11　寫入RAM3 & RAM4定址產生器之電路圖.......................112
C.1.12　DFT 運算單元之電路圖....................................112
C.1.13　16-bit多工器之電路圖...................................113
C.2　模擬的時序圖........................................114

附錄　D...........................................115
D.1　模擬的完整電路......................................115
D.1.1　記憶體為主體架構下使用FPGA模擬16×16點2D-DFT運算之電路
..............................................................115
D.1.2　定址/控制信號產生器之電路圖.............................115
D.1.3　控制信號產生器之電路圖（一）..............................116
D.1.4　控制信號產生器之電路圖（二）..............................116
D.1.5　讀取RAM1定址產生器之電路圖（一）.........................117
D.1.6　讀取RAM1定址產生器之電路圖（二）.........................117
D.1.7　讀取RAM2定址產生器之電路圖（一）.........................118
D.1.8　讀取RAM2定址產生器之電路圖（二）.........................118
D.1.9　讀取ROM定址產生器之電路圖...............................119
D.1.10　寫入RAM1 & RAM2定址產生器之電路圖（一）..................119
D.1.11　寫入RAM1 & RAM2定址產生器之電路圖（二）.................120
D.1.12　寫入/讀取RAM3 定址產生器之電路圖........................120
D.1.13　DFT運算單元之電路圖....................................121
D.1.14　記憶體RAM之電路圖......................................121
D.2　模擬的時序圖........................................122

附錄　E...........................................127
E.1　模擬的完整電路......................................127
E.1.1　記憶體為主體架構下使用FPGA模擬8點DCT運算電路圖........127
E.1.2　定址/控制信號產生器之電路圖.............................127
E.1.3　控制信號產生器之電路圖（一）..............................128
E.1.4　控制信號產生器之電路圖（二）..............................128
E.1.5　讀取RAM1定址產生器之電路圖..............................129
E.1.6　讀取RAM2定址產生器之電路圖..............................129
E.1.7　讀取/寫入RAM3定址產生器之電路圖.........................130
E.1.8　讀取ROM定址產生器之電路圖...............................130
E.1.9　寫入RAM1 & RAM2定址產生器之電路圖........................131
E.1.10　DCT之KERNEL 運算單元之電路圖...........................131
E.1.11　16-bit加法器/減法器之電路圖............................132
E.1.12　POST處理單元之控制信號產生器之電路圖（一）...............132
E.1.13　POST處理單元之控制信號產生器之電路圖（二）...............133
E.1.14　POST處理單元之控制信號產生器之電路圖（三）...............133
E.1.15　延遲16個脈波週期之電路圖...............................134
E.1.16　延遲19個脈波週期之電路圖...............................134
E.1.17　POST處理單元之電路圖...................................135
E.1.18　POST1處理單元之電路圖..................................135
E.1.19　POST2處理單元之電路圖..................................136
E.1.20　16-bit延遲1個脈波週期之電路圖.........................136
E.2　模擬的時序圖........................................137

附錄　F...........................................138
F.1　模擬的完整電路.............................................138
F.1.1　記憶體為主體架構下使用FPGA模擬8×8點2D-DCT運算之電路
..............................................................138
F.1.2　定址/控制信號產生器之電路圖.............................138
F.1.3　控制信號產生器之電路圖（一）..............................139
F.1.4　控制信號產生器之電路圖（二）..............................139
F.1.5　讀取RAM1定址產生器之電路圖..............................140
F.1.6　讀取RAM2定址產生器之電路圖..............................140
F.1.7　讀取ROM定址產生器之電路圖...............................141
F.1.8　讀取/寫入RAM3定址產生器之電路圖.........................141
F.1.9　寫入RAM1 & RAM2定址產生器之電路圖（一）....................142
F.1.10　寫入RAM1 & RAM2定址產生器之電路圖（二）...................142
F.1.11　7-bit多工器之電路圖....................................143
F.1.12　7-bit 延遲3個脈波週期之電路圖.. ........................143
F.1.13　7-bit 延遲1個脈波週期之電路圖.. ........................144
F.1.14　DCT之KERNEL 運算單元之電路圖...........................144
F.2　模擬的時序圖........................................145

[1] A. V. Oppenheim, ”Applications of Digital Signal Processing.” Engle-wood Cliffs, NJ:Prentic-Hall, 1978.[2] ETS 300 401 “Radio broacasting system; Digital Audio Broadcasting(DAB) to mobile,portable and fixed receivers,”MAy 1997.[3] H. T. Kung, “Why systolic architectures?,” Computer, vol.15, pp.37-46, Jan. 1982.[4] L.-W Chang and M.-Y. Wu, “A new systolic array for discrete Fourier transform,” IEEE Trans. Acoust., Speech, Signal Processing, vol. 36, pp.1165—1167, Oct. 1988.[5] J. A. Beraldin, T. Aboulnasr, and W. Steenaart, “Efficient one-dimensional systolic array realization of discrete Fourier transform,” IEEE Trans. Circuits Syst., vol. 36, pp. 95—100, Jan. 1989.[6] N. R. Murphy and M. N. S. Swamy, “On the real-time computation of DFT and DCT through systolic architecture,” IEEE Trans. Signal Processing, vol. 42, pp. 988—991, Apr. 1993.[7] J. Choi and V.Boriakoff, “A new linear systolic array for FFT computation,”IEEE Trans. Circuits Syst. II, vol. 39, pp.236—239, Apr. 1992.[8] V.Boriakoff, “FFT computation with systolic arrays,a new architecture,” IEEE Trans. Circuits Syst. II, vol. 41, pp. 278—284, Apr.1994.[9] E.Bidet,D. Castelain,C. Joanblang, and P. Senn, “A fast single-chip implementation of 8192 complex point FFT,” IEEE Journal of Solid-State Circuits, Vol. 30,No.3,pp.300-305,March 1995.[10] S. He and M. Torkelson, “Design and implementation of a 1024-point pipeline FFT processor,” in Proc. IEEE Custom Intergrated Circuits Conference,pp.131-134,1998[11] S.R.Malladi, S.R. Myneni, P.V. Pothana, and M.A.Bayoumi, ”A High Speed Pipelined FFT Processor,” in Proc. International Conference on Acoustics,Speech,and Signal Processing, Vol 3 ,pp.1609-1612,1991.[12] S. F. Hsiao and C. Y. Yen, “Power, speed and area comparison of several new DFT architectures,”in Proc. IEEE Int. Symp. Circuits Syst., Hong Kong, June 1997, pp. 2577—2580.[13] B.M. Bass, ”A 9.5mW 330usec 1024-point FFT Processor,” in Proc. IEEE Custom Intergrated Circuits Conference, pp.127-130,1998.[14] C. Ediz,M.Richard,and C.S. Kale, ”A integrated 256-point complexFFT processor for real-time specturm analysis and measurement, ” in Proc.IEEE Instrumentation and Measurement Technology Conference, pp.96-101,1997.[15] Chang Ching-Hsien,Wang Chin-Liang,and Chang Yu-Tai, "Efficient VLSI Architectutres for Fast Computation of the Discrete Fourier Transform and Its Inverse," IEEE Trans on Signal Processing, vol. 48, NO.11, pp.3206-3216, Nov. 2000[16] N. Ahmed, T. Natarajan, and K. R. Rao, “Discrete cosine transform,” IEEE Trans. Comput., vol. C-23, pp. 90-93, Jan. 1974.[17] H. S. Hou, “A fast recursive algorithm for computing the discrete consine transform,” IEEE Trans. Acoust., Speech,Signal Processing, vol. ASSP35, pp.1455-1461,Mar. 1987.[18] Cvetkovic Z. and Popovic M. V., “New Fast Recursive Algorithm for Computation of Discrete Consine and Sine Transforms, ”IEEE Trans.Signal Processing, vol.40, No.5, pp.2083-2086, Aug. 1992.[19] Hsiao S.F.,Shiue W. R.and Tseng J.M., ”Design and implementationof a novel linear-array DCT/IDCT processor with complexity of order log2 N,” IEE Proceedings-Vision, Image and Signal Processing, vol.147, No.5, pp.400-408,Oct 2000. [20] Agostini, L.V.; Silva, I.S.; Bampi, S. “Pipelined fast 2D DCT architecture for JPEG image compression,” IEEE Ingegrated Circuits and Systems Design, pp.226-231, 2001 [21] Wolter, S.; Birreck, D.; Laur, R. ”Classification for 2D-DCTs and a new architecture with distributed arithmetic,” IEEE Circuits and Systems, vol.4, pp.2204-2207,1991.[22] Wolter, S.; Birreck, D.; Heine, M.; Laur, R. ”Parallel architectures for 8*8 discrete cosine transforms,” IEEE Circuits and Systems, vol.1, pp.149-152,1992.[23] Mohd-Yusof, Z.; Suleiman, I.; Aspar, Z.”Implementation of two dimensional forward DCT and inverse DCT using FPGA,” IEEE TENCON 2000. Proceedings, pp.242-245, vol.3,2000 [24] Hyesook Lim; Swartzlander, E.E., Jr. “A systolic array for 2-D DFT and 2-D DCT,“ IEEE Application Specific Array Processors, 1994. Proceedings. International Conference on ,pp.123-131,1994