臺灣博碩士論文加值系統

離散正弦轉換（DST）可以根據特性應用於不同的方面，在訊號處理、數位濾波、影像編碼等領域中，都可以發揮作用。
本研究之目的為實現一組二維離散正弦轉換電路之設計，採用行列分解法（row-column method）完成電路設計，降低電路成本。在架構中，採用遞迴式演算法來實現離散正弦轉換，該方式將一組高點數之DST分解為兩組相似的低點數之DST，降低電路複雜度。該演算法採用遞迴式的運算架構，使用的乘法器與加法器數量較少。

The Discrete sine transforms (DST) can be applied to different fields according to the characteristic, in signal processing, digital filtering, image coding.
This paper adopt row-column method for 2-D discrete sine transform implementation. The purpose of this method can reduce the implement cost. In this structure, We use a recursive algorithm to implement one-dimensional discrete sine transform (1-D DST), this algorithm decomposition to separate higher order DST into two low order DST, In order to reduce the circuit complexity, the algorithm propose a computing structure of recursive structure, which requires fewer multipliers and adders.

中文摘要 i
英文摘要 ii
誌謝 iii
目錄 iv
表目錄 vi
圖目錄 vii
第一章 緒論 1
1.1 研究動機 1
1.2 研究目的 2
1.3 論文大綱 3
第二章 相關原理 4
2.1 離散傅立葉轉換 4
2.2 快速傅立葉轉換 5
2.2.1 分頻快速傅立葉轉換（DIF FFT） 5
2.2.2 分時快速傅立葉轉換（DIT FFT） 8
2.2.3 庫利-塔基演算法 10
2.2.4 哥茲柔演算法 14
2.3 FPGA簡介 17
2.4 硬體電路描述語言（HDL） 19
第三章 離散正弦轉換 20
3.1 前言 20
3.2 離散正弦轉換 20
3.3 相關研究 21
3.3.1 直接法 22
3.3.2 行列分解法 22
3.4 離散正弦轉換之運算架構 23
3.4.1 蝴蝶架構 23
3.4.2 乘加器架構 25
3.4.3 遞迴式架構 26
3.5 離散正弦轉換之誤差分析 33
3.5.1 有限字元長度效應 33
3.5.2 離散正弦轉換架構之誤差分析 35
第四章 硬體電路實現及結果 38
4.1 前言 38
4.2 一維轉換電路架構 38
4.3 轉置用記憶體 41
4.4 二維轉換電路架構 42
4.5 電路模擬 43
4.5.1 一維轉換電路 43
4.5.2 二維轉換電路 47
第五章 結論與未來展望 51
5.1 結論 51
5.2 未來展望 52
參考文獻 53
附錄 離散正弦轉換在適應性濾波器之應用 56
作者簡介 59

[1] Wayne Wolf, “FPGA-based System Design,” Prentice Hall, 2004.
[2] 余清華，許書務 編譯，”ASIC邏輯電路設計”，全華科技圖書股份有限公司，民國七十九年。
[3] Loring Wirbel, “FPGA survey sees sunset for gate arrays, continued dominance by Xilinx, Altera,” EE Times, 2008.
[4] Dylan McGrath, “Gartner: ASIC design starts to fall by 22% in '09”, EE Times, 2009.
[5] Roger Do & Mentor Graphics, “How to improve FPGA-based ASIC prototyping with System Verilog,” EE Times, 2009.
[6] 賈證主 著， ”VHDL數位系統設計與應用”，台科大圖書股份有限公司，民國九十三年。
[7] C. H. Roth, “Digital system Design using VHDL,” PWS Oub, 1998.
[8] 陳慶逸，林柏辰 編著，“VHDL數位電路實習與專題設計”，文魁資訊股份有限公司，民國九十二年。
[9] Wang, Z., and Wang , L., “Interpolation using the fast discrete sine transform, ” Signal processing, vol.26, Jan.1992,pp. 131-137.
[10] Hou, H. S., “A fast recursive algorithm for computing the discrete cosine transform, ” IEEE Trans. Acoust. Speech, Signal Processing, vol.ASSP-35 ,no.10.Oct.1987, pp.1455-1461.
[11] Gupta , A., and Rao, K. R.,“A fast recursive algorithm for the discrete sine transform,” IEEE Trans, ASSP-38,1990, pp. 553-557.
[12] Shen-Fu Hsiao, Jian-Ming Tseng “Direct implementation of 2-D DCT on a low-cost linear-array architecture without intermediate transpose memory,” Signal Processing Systems, 1999, On page(s): 90-99.

[13] Liang-Gee Chen, Juing-Ying Jiu; Hao-Chieh Chang; Yung-Pin Lee; Chung-Wei Ku, “A low power 2D DCT chip design using direct 2D algorithm,” Design Automation Conference 1998, Page(s):145 – 150.
[14] Vladimir Britanak, Patrick C. Yip, K.R. Rao,” Discrete cosine and sine transforms : general properties, fast algorithms and integer approximations,” Trans, ASSP-32, 1984, pp.803-816.
[15] Aggoun, A., Jalloh, I “Two-dimensional DCT/IDCT architecture,” Computers and Digital Techniques, IEE Proceedings, Volume 150, Issue 1, 20 Jan. 2003, Page(s):2 – 10.
[16] Britanak, V.; Rao, R.” Two-dimensional DCT/DST universal computational structure for 2m×2n block sizes” Signal Processing, IEEE Transactions Vol 48, Issue 11, Nov. 2000, Page(s):3250 – 3255.
[17] Pei Zong Lee, Fang-Yu Huang, “Restructured Recursive DCT and DST Algorithms,” Signal Processing, IEEE Transactions Volume 42, Issue 7, July, 1994, Page(s):1600 – 1609.
[18] P. YIP AND K. R. RAO,” A Fast Computational Algorithm for the Discrete Sine Transform,” IEEE Transactionson Communication,1980.
[19] Che-Hong Chen, Bin-Da Liu, Jar-Ferr Yang, “Direct Recursive Structures for Computing Radix-r Two-Dimensional DCT/IDCT/DST/IDST” IEEE Transactions on Circuits and Systems, VOL. 51, NO. 10, OCTOBER 2004.
[20] Vladimir Britanak and K. R. Rao “Two-Dimensional DCT/DST Universal Computational Structure for Block Sizes” IEEE Transactions on Signal Processing, VOL. 48, NO. 11, NOVEMBER 2000.
[21] Jose A. Tierno and Prabhakar Kudva, “Asynchronous transpose-matrix architectures,” in Proc. IEEE Computer Design Conf. (ICCD '97), 1997, pp. 423-428.
[22] 林佑成， “離散正弦轉換快速遞迴演算法” ，明新科技大學電機研究所，碩士論文，民國九十五年。
[23] Stasinski, R., “On pruning the discrete cosine and sine transforms. ”,IEEE Melecon 2004, May 12-15, 2004, pp. 269-271.
[24] Kober, V., “ Fast recursive algorithm for sliding discrete sine transform.” , Electronic Letters, Vol.38, No.25, 5th Dec 2002 , pp. 1747-1748.
[25] Oppenheim, Schafer, Buck, 曾建誠、陳常侃、王鵬華、丁建均，“離散時間訊號處理”，全華科技圖書股份有限公司，民國八十九年。
[26] 姚瑞祺，“離散弦式轉換快速演算法之比較研究”，中正理工學院國防科學研究所,博士學位論文，民國八十二年。