在前計算即時快速傅利葉之應用研究

The Study of the Application of Pre-calculation for Real-Time FFT

單啟瑋(Chi-Wei Shan)

指導教授 ： 嚴文方

國立臺北科技大學/機電學院/電腦與通訊研究所/碩士(2005年)

https://doi.org/10.6841/NTUT.2005.00043

摘要

快速傅立葉轉換在即時數位信號系統一直扮演極重要的角色。然而典型的FFT 演算法在完全收到資料後，CPU才開始做butterfly的計算。Real-time FFT演算法利用輸入資料可以先行運算的butterfly，改善原有FFT演算法的效益。但是最後一個取樣點到達後仍有相當大的運算量，進而也影響到取樣週期也因此而有所限制。
本論文中，利用以發展出的預先計算(pre-calculation)Real-time演算法(即最後一個輸入點不參與Butterfly計算)，再修改並發展提出更多的輸入點不參與Butterfly預先計算，以獲得較小的取樣週期進而提高其系統取樣頻率範圍。此外，本文也對輸入點數與計算量之分佈及如何分攤進行理論與模擬分析，以求得各參數間最佳的關係。

關鍵字

快速傅利葉轉換

並列摘要

Fast Fourier transform has been playing the key role in the subject of real-time signal processing. The computational process can normally be carried out when all the input data values are received of the conventional FFT algorithms. A method, real-time FFT, can proceed the butterfly computation upon receipt of the first data of the second half incoming input sequence. This can achieve the better time saving of arithmetic operation in general. However, a large number of butterfly computations still needed to be processed after the last input data is received. How to implement such a system working at a substantial small sampling period becomes an issue significantly to be discussed.
An already proposed method, pre-calculation real-time FFT, is applied and modified by moving out more input data from the pre-calculation process for minimizing the sampling period in this thesis. In addition, theoretical analysis and simulation works have been made relating to the appropriate number of moving out input data as well as the better ways of sharing the burden of computational tasks to other sampling period. Various conditions and equations for considering the optimal relationship among all the parameters concerning the maximum range of sampling frequency of a DSP system have also been studied in this thesis.

並列關鍵字

FFT

參考文獻

[1] J.W. Cooley, J.W. Tukey, “An algorithm for machine computation of complex Fourier series”, Mathematics Computation, April 1965, 19, pp. 297-301.

[2] Pei-chen Lo, Yu-yun Lee, “Real-time implementation of the split-radix FFT”, Elsevier Science, Signal Processing, 1998, 71, pp. 291-299.

[6] A.A. Yong, “A better FFT bit-reversal algorithm without table”, IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 39, no. 10, pp.2365-2367, Oct. 1991

[8] M.S. Mohammed, S. Lorenzo, “System implementation of look up table FFT”, Melecon conference, 1991.

[9] G. D. Bergland. A fast Fourier transform algorithm using base 8 iterations. Math. Comp., 22:275-279, 1968.