在數位訊號處理(DSP or digital signal processing)的領域中，離散傅立葉轉換(DFT or discrete Fourier transform)扮演著相當關鍵的角色，在目前某些通訊系統的規格中，DFT傳輸點數為非2的冪次方，因此需要提出可以適用於此種要求的設計。在本論文中，作者提出適合分散式運算的演算法與硬體架構來計算DFT，這是一種使用唯讀記憶體(ROM or read only memory)與移位累加器的設計，此種設計不需要使用乘法器，因此如何有效的去減小ROM size為主要的考量。作者分別針對質數點數(prime length)與非質數點數(non-prime length) DFT提出適用於分散式運算的演算法與硬體架構，相較於目前已經存在的方法，作者提出的計算質數點數與非質數點數DFT的方法，分別節省了66%、97% ROM size與50%、55%的加法器數量。此外，在硬體架構上，相較於其他的電路設計，在本論文中電路的關鍵路徑是最短的，可以預期的是電路可操作的速度為最快。

In digital signal processing (DSP), the discrete Fourier transform (DFT) is crucial. These days, the transform length of DFT is not power of two in some specification of communication system, so we need to find a way to meet this requirement. In this thesis, the author has proposed algorithm and hardware architecture suitable for DA to calculate DFT, this is the design using ROM and shift adder, but there is no multiplier. The author has proposed algorithm and hardware suitable for DA to calculate prime length DFT and non-prime length DFT. Compared with existing method, proposed method has improved by 66% and 97% in ROM size for prime length and non-prime length DFT, respectively; in addition, proposed method has improved by 50% and 55% in number of adder for prime length and non-prime length DFT, respectively. Moreover, the critical path of proposed circuit is minimum. Thus it can be expected that clock speed of proposed circuit is maximum.

[1] J. W. Cooley and J. W. Tukey, "An algorithm for the machine calculation of complex Fourier series," Math. Computation, vol. 19, pp. 297-301, 1965.
[2] Y. Zhi-Xing, et al., "Design of a 3780-point IFFT processor for TDS-OFDM," Broadcasting, IEEE Transactions on, vol. 48, pp. 57-61, 2002.
[3] Y. Xiaogang, et al., "Hardware design and implementation of 3780 points FFT based on FPGA in DTTB," in Application of Information and Communication Technologies (AICT), 2010 4th International Conference on, 2010, pp. 1-4.
[4] H. Chen-Fong, et al., "A Generalized Mixed-Radix Algorithm for Memory-Based FFT Processors," Circuits and Systems II: Express Briefs, IEEE Transactions on, vol. 57, pp. 26-30, 2010.
[5] J. Le and L. Lin, "A power-of-two FFT algorithm and structure for DRM receiver," Consumer Electronics, IEEE Transactions on, vol. 56, pp. 2061-2066, 2010.
[6] K. Dong-Sun, et al., "Design of a mixed prime factor FFT for portable digital radio mondiale receiver," Consumer Electronics, IEEE Transactions on, vol. 54, pp. 1590-1594, 2008.
[7] D. Kolba and T. Parks, "A prime factor FFT algorithm using high-speed convolution," Acoustics, Speech and Signal Processing, IEEE Transactions on, vol. 25, pp. 281-294, 1977.
[8] C. Shuni and C. Burrus, "A prime factor FTT algorithm using distributed arithmetic," Acoustics, Speech and Signal Processing, IEEE Transactions on, vol. 30, pp. 217-227, 1982.
[9] P. Chow, et al., "A Pipelined Distributed Arithmetic PFFT Processor," Computers, IEEE Transactions on, vol. C-32, pp. 1128-1136, 1983.
[10] P. K. Meher, "Efficient Systolic Implementation of DFT Using a Low-Complexity Convolution-Like Formulation," Circuits and Systems II: Express Briefs, IEEE Transactions on, vol. 53, pp. 702-706, 2006.
[11] C. Chao and K. K. Parhi, "Low-Cost Fast VLSI Algorithm for Discrete Fourier Transform," Circuits and Systems I: Regular Papers, IEEE Transactions on, vol. 54, pp. 791-806, 2007.
[12] W. C. Siu and C. F. Chen, "New realisation technique of high-speed discrete Fourier transform described by distributed arithmetic," Computers and Digital Techniques, IEE Proceedings E, vol. 130, pp. 177-182, 1983.
[13] J. I. Guo, et al., "The efficient memory-based VLSI array designs for DFT and DCT," Circuits and Systems II: Analog and Digital Signal Processing, IEEE Transactions on, vol. 39, pp. 723-733, 1992.
[14] H. C. Chen, et al., "Distributed arithmetic realisation of cyclic convolution and its DFT application," Circuits, Devices and Systems, IEE Proceedings -, pp. 615-629, 2005.
[15] A. Peled and L. Bede, "A new approach to the realization of nonrecursive digital filters," Audio and Electroacoustics, IEEE Transactions on, vol. 21, pp. 477-484, 1973.
[16] A. Peled and L. Bede, "A new hardware realization of digital filters," Acoustics, Speech and Signal Processing, IEEE Transactions on, vol. 22, pp. 456-462, 1974.
[17] C. Burrus, "Digital filter structures described by distributed arithmetic," Circuits and Systems, IEEE Transactions on, vol. 24, pp. 674-680, 1977.
[18] S. A. White, "Applications of distributed arithmetic to digital signal processing: a tutorial review," ASSP Magazine, IEEE, vol. 6, pp. 4-19, 1989.
[19] K. K. Parhi, VLSI Digital Signal Processing Systems: Design and Implementation. New York: Wiley, 1999.
[20] C. M. Rader, "Discrete Fourier transforms when the number of data samples is prime," Proceedings of the IEEE, vol. 56, pp. 1107-1108, 1968.
[21] S. Brown and Z. Vranesic, Fundamentals of Digital Logic with Verilog Design. New York: McGraw-Hill, 2008.
[22] N. H. E. WESTE and D. Harris, CMOS VLSI DESIGN:A Circuits and Systems Perspective. Boston: Addison Wesley, 2005.
[23] R. G. Lyons, Understanding Digital Signal Processing. New Jersey: Prentice Hall, 2004.
[24] C. Burrus, "Index mappings for multidimensional formulation of the DFT and convolution," Acoustics, Speech and Signal Processing, IEEE Transactions on, vol. 25, pp. 239-242, 1977.
[25] C. S. B. a. T. W. Parks, DFT/FFT and Convolution Algorithms. New York: Wiley, 1985.
[26] ETSI, "Digital Radio Mondiale(DRM); system specification," ed, 2009.
[27] ARM, "AMBA Specification (Rev 2.0)," ed, 1999.
[28] 邱俊傑, ARM Processor Design Kit. Hsinchu: CIC Training Manual, January, 2011.
[29] Xilinx, "Xilinx ISE Software Manuals," ed.
[30] ARM, "ARM Developer Suite version 1.2, CodeWarrior IDE Guide," ed: ARM Ltd, 2001.
[31] ARM, "ARM Developer Suite Version 1.2, AXD and armsd Debuggers Guide," ed, 2001.