本篇論文提出一個支援任意質數的快速高精準度遞迴式離散傅利葉轉換(Recursive Discrete Fourier Transform, RDFT)架構，並實現於Xilinx Virtex4xc4vlx160平台上做驗證。在此RDFT架構中，利用三角函數的週期性與對稱性以固定正弦、餘弦的係數運算，進而節省係數的需求量，同時可降低核心遞迴次數，另外此架構的資料吞吐量(Data Throughput, DTPT)為2，因此相較於現有文獻可大量的節省50%以上的運算週期，並且由於固定係數的推導，此架構不需耗費任何係數的記憶體儲存空間。另外，在固定係數推導的過程中，架構中各極點的距離會影響量化誤差的大小；當共軛極點間的距離過近時，易使得敏感度(Sensitivity)增大，造成精準度的下降。故引用可調式q因子的運算，將共軛極點距離調整成最佳化，進而提高固定係數架構的精準度。在通訊系統上如雙音多頻(Dual-Tone Multi-Frequency, DTMF)系統，實際應用的訊框長度為106/201/205/222/226，將其作質因數分解可得53/67/41/37/113的質數長度。本論文針對這些質數點數來模擬驗證所提出之架構，其結果可得實數乘法量較現有文獻少50%以上，而實數加法量亦減少約10%以上。
本篇論文透過圖形使用者介面(GUI)環境，將提出的硬體架構其參數可組態化，提供使用者一個設計環境來調整硬體規格，由Peak Signal-to-Noise Ratio(PSNR)數據，調整系統所需的規格及效能，以利於對應System-on-Chip (SoC)設計的便利性。

This paper proposed a support for any prime number of fast, high-precision recursive discrete Fourier transform (RDFT) architecture and implemented in Xilinx Virtex4xc4vlx160 platform to do verification. This RDFT architecture used the periodicity and the symmetry of trigonometric function to fix the sine, cosine coefficient, thereby saving the coefficient requirement and decreasing the times of recursive kernel, while the Data Throughput (DTPT) of this architecture is 2, thus compared with the existing literature, the proposed architecture can save more than 50% of computing cycles, moreover, it without costing any memory storage space as a result of the fixed-coefficient algorithm. In addition, in the derivation of the fixed-coefficient algorithm, the distance between the poles will affect the Value of the quantization error; when the distance between conjugate poles is too close, easy to make the sensitivity (Sensitivity) increases, resulting in a decline in accuracy. Therefore, we quoted an adjustable q factor operation; the conjugate poles will be adjusted to optimize distance, thereby increasing the accuracy of fixed-coefficient architecture. In communication systems such as DTMF (Dual-Tone Multi-Frequency, DTMF) system, the practical application of the frame length 106/201/205/222/226, to make available integer factorization 53/67/41/37/113 prime number length. This thesis will verify and simulate the proposed architecture with these prime number lengths, the results of the amount of the real multiplication less than 50% than the existing literature, and the amount of real addition decreased about 10%.
This paper through a graphical user interface (GUI) environment to make the parameters of present hardware architecture can be configured, thereby providing a design environment for the user to adjust the system required specifications and performance from the Peak Signal-to-Noise Ratio (PSNR) data, in order to facilitate the corresponding System-on-Chip (SoC) design convenience.

[1] J. W. Cooley and J. W. Tukey, "An algorithm for the machine calculation of complex Fourier series," Math. Comp., vol. 19, pp. 297--301, 1965.
[2] A. V. Oppenheim, R. W. Schafer, and J. R. Buck, Discrete-Time Sindal Processing. New Jersey: Prentice-Hall, Inc., 1989.
[3] ETSI ES 201 980 V3.1.1, "Digital radio mondiale; system specification," 2009.
[4] Q. W. Lu, X. A. Wang, and J. C. Niu, "A low-power variable-length FFT processor base on Radix-24 algorithm," in Microelectronics & Electronics, 2009. PrimeAsia 2009. Asia Pacific Conference on Postgraduate Research in, 2009, pp. 129-132.
[5] ITU Blue Book, "Recommendation Q. 23: Technical Features of Push-Button Telephone Sets ", 1988.
[6] ITU Blue Book, "Recommendation Q. 24: Multi-Frequency Push-Button Signal Reception," 1989.
[7] C. J. Chen, "Modified Goertzel Algorithm in DTMF Detection Using the TMS320C80," Texas Instruments Application Report, 1996.
[8] P. Mock, "Add DTMF generation and decoding to DSP microprocessor designs," Electron. Data News, vol. 30, pp. 205–220, 1985.
[9] G. Arslan, B. L. Evans, F. A. Sakarya, and J. L. Pino, "Performance evaluation and real-time implementation of subspace, adaptive and DFT algorithms for multi-tone detection," in Proc. IEEE Int. Conf. Telecommunications, 1996, pp. 884-887.
[10] S. C. Lai, S. F. Lei, W. H. Juang, and C. H. Luo, "A Low-Cost, Low-Complexity, and Memory-Free Architecture of Novel Recursive DFT and IDFT Algorithms for DTMF Application," Circuits and Systems II: Express Briefs, IEEE Transactions on, vol. 57, pp. 711-715, 2010.
[11] M. D. Felder, J. C. Mason, and B. L. Evans, "Efficient dual-tone multifrequency detection using the nonuniform discrete Fourier transform," Signal Processing Letters, IEEE, vol. 5, pp. 160-163, 1998.
[12] S. L. Gay, J. Hartung, and G. L. Smith, "Algorithms for multi-channel DTMF detection for the WE DSP32 family," in Acoustics, Speech, and Signal Processing, 1989. ICASSP-89., 1989 International Conference on, 1989, pp. 1134-1137 vol.2.
[13] S. Winograd, "On computing the discrete Fourier transform," Proceedings of the National Academy of Sciences of the United States of America, vol. 73, p. 1005, 1976.
[14] S. G. Johnson and M. Frigo, "A Modified Split-Radix FFT With Fewer Arithmetic Operations," Signal Processing, IEEE Transactions on, vol. 55, pp. 111-119, 2007.
[15] G. Goertzel, "An algorithm for the evaluation of finite trigonometric series," American mathematical monthly, pp. 34-35, 1958.
[16] J. F. Yang and F. K. Chen, "Recursive discrete Fourier transform with unified IIR filter structures," Elsevier Science B.V. Signal Process, vol. 82, pp. 31-41, 2002.
[17] C. P. Fan and G.A. Su, "Novel recursive discrete Fourier transform with compact architecture," in Circuits and Systems, 2004. Proceedings. The 2004 IEEE Asia-Pacific Conference on, 2004, pp. 1081-1084 vol.2.
[18] L. D. Van and C. C. Yang, "High-speed area-efficient recursive DFT/IDFT architectures," in Circuits and Systems, 2004. ISCAS '04. Proceedings of the 2004 International Symposium on, 2004, pp. III-357-60 Vol.3.
[19] L. D. Van, Y. C. Yu, C. M. Huang, and C. T. Lin, "Low computation cycle and high speed recursive DFT/IDFT: VLSI algorithm and architecture," in Signal Processing Systems Design and Implementation, 2005. IEEE Workshop on, 2005, pp. 579-584.
[20] L. D. Van, C. T. Lin, and Y. C. Yu, "VLSI Architecture for the Low-Computation Cycle and Power-Efficient Recursive DFT/IDFT Design," IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES E SERIES A, vol. 90, p. 1644, 2007.
[21] P. K. Meher, J. C. Patra, and A. P. Vinod, "Novel Recursive Solution for Area-Time Efficient Systolization of Discrete Fourier Transform," in Signals, Circuits and Systems, 2007. ISSCS 2007. International Symposium on, 2007, pp. 1-4.
[22] S. C. Lai, S. F. Lei, Chang. C. L., C. C. Lin, and C. H. Luo, "Low Computational Complexity, Low Power, and Low Area Design for the Implementation of Recursive DFT and IDFT Algorithms," Circuits and Systems II: Express Briefs, IEEE Transactions on, vol. 56, pp. 921-925, 2009.
[23] C. Marven, "General-Purpose Tone Decoding and DTMF Detection," Theory, Algorithms, and Implementations, Digital Signal Processing Applications with the TMS320 Family, vol. 2, literature number SPRA016, Texas Instruments 1990.
[24] G. L. Smith, "Dual-Tone Multifrequency Receiver Using the WE DSP16 Digital Signal Processor,," AT&T Application Note.
[25] Online, "DTMF(Dual Tone Multiple Frequency,電話撥號音)," Web page: http://eshare.stut.edu.tw/EshareFile/2010_12/2010_12_9daebbf6.pdf.
[26] Wikipedia, "Dual-tone multi-frequency signaling," [Online] http://en.wikipedia.org/wiki/Dual-tone_multi-frequency_signaling.
[27] "dsPIC DSC DTMF Detection Library User's Guide," Microchip Technology Inc., 2010.
[28] Y. C. Huang, "DSP Techniques for Telecommunication Systems." vol. Master's thesis: Northern Illinois University, August 1995.
[29] J. G. Proakis and D. G. Manolakis, Digital Signal Processing: Principles, Algorithms, and Applications, 2 ed. New York: Macmillan, 1992.
[30] T. E. Curtis and J. T. Wickenden, "Hardware-based Fourier transforms: algorithms and architectures," Communications, Radar and Signal Processing, IEE Proceedings F, vol. 130, pp. 423-432, 1983.
[31] Z. Y. Cheng, C. H. Chen, B. D. Liu, and J. F. Yang, "Unified selectable fixed-coefficient recursive structures for computing DCT, IMDCT and subband synthesis filtering," in Circuits and Systems, 2004. ISCAS '04. Proceedings of the 2004 International Symposium on, 2004, pp. III-557-60 Vol.3.
[32] 具再熙, "數位訊號處理，使用Matlab," 台灣: 儒林, 2007.
[33] H Li, P Li, and Y Wang, "An efficient hardware accelerator architecture for implementing fast IMDCT computation," Signal Processing, 2010.
[34] 張智星, "Matlab 程式設計【入門篇】," 鈦思科技, 2007.