臺灣博碩士論文加值系統

本文主要目的是將快速傅氏轉換（FFT）及快速哈氏轉換（FHT）的數種不同演算法，在數位信號處理機(DSP)上實現，並比較其程式執行的效率。主要探討的演算法包括：FFT中的direct CFFT、packing CFFT、radix-4 CFFT、split-radix CFFT及RFFT。以及FHT中的radix-2 FHT、radix-4 FHT、split-radix FHT。採用的DSP為德州儀器（TI）公司所研發的16位元定點式DSP：TMS320 C50晶片。本文將上述的各種演算法改寫成DSP專用的低階組合語言，並實際統計每一個程式執行所需要的週期數（cycles），繼而進行效率的比較。這樣的效率比較方式與傳統的比較計算複雜度，結果有相當大的差異。顯示在真正的使用場合上，選擇FFT演算法不能只單獨考慮計算複雜度。

The main purposes of this paper are to implement various algorithms of fast Fourier Transforms and fast Hartley Transform on a digital signal processor (DSP), and then to compare their executing efficiencies. The FFT algorithms studied in this paper include direct CFFT, packing CFFT, radix-4 CFFT, split-radix CFFT and RFFT. For the FHT algorithms, the radix-2 FHT, radix-4 FHT, split-radix FHT are studied. The DSP used in this paper is a TI’s TMS320C50, which is a 16-bit fixed point DSP. In this paper, the real computing cycles of algorithms mentioned above are counted instead of the theoretical computation-complexity, which used by most of the published papers. The counts of computing cycles show a different executing efficiency rank with that of obtained from counting computation-complexity. This result suggests that in real situation the computation-complexity can’t be used as the only index of choosing FFT algorithms.

摘要………………………………………………………………I
英文摘要…………………………………………………………III
誌謝………………………………………………………………IV
目錄………………………………………………………………V
表目錄……………………………………………………………IX
圖目錄……………………………………………………………X
第一章 緒論………………………………………………………1
1.1 研究動機……………………………………………1
1.2 研究目的……………………………………………3
1.3 研究的重要性………………………………………4
1.4 文獻回顧……………………………………………5
1.5 全文概述……………………………………………10
第二章 研究設備………………………………………………12
2.1 實現FFT演算法之硬體……………………………12
2.1.1 overflow的產生……………………………12
2.1.2 overflow的處理……………………………14
2.2 驗證測試的平台……………………………………16
第三章 快速傅氏轉換演算法…………………………………21
3.1 Cooley-Tukey CFFT演算法………………………21
3.1.1 高階語言程式架構…………………………21
3.1.2 程式的最佳化………………………………23
3.1.3 結果討論……………………………………24
3.2 Packing CFFT演算法……………………………25
3.3 Radix-4 CFFT演算法……………………………28
3.4 Split-radix CFFT演算法…………………………32
3.5 RFFT演算法………………………………………33
第四章 快速哈式轉換演算法…………………………………37
4.1 執行Loop I之判斷時機...………………………38
4.2 將FHT合成為FFT………………………………40
第五章 各種演算法之效率比較………………………………42
5.1 packing前後之CFFT與RFFT之比較……………42
5.2 FFT與FHT之比較………………………………44
5.3 實際執行時間與計算複雜度之比較……………45
第六章 結論與建議……………………………………………47
6.1 結論…………………………………………………47
6.2 建議…………………………………………………48
參考文獻…………………………………………………………50
附錄A 各演算法之高階語言程式……………………………52
A-1 Cooley-Tukey CFFT………………………………52
A-2 Cooley-Tukey CFFT（Ver.5）……………………54
A-3 Packing CFFT……………………………………57
A-4 Radix-4 CFFT……………………………………59
A-5 Split-radix CFFT…………………………………62
A-6 Real-valued FFT…………………………………65
A-7 Radix-2 FHT………………………………………67
A-8 Radix-4 FHT………………………………………70
A-9 Split-Radix FHT…………………………………74
附錄B 各演算法之組合語言程式………………………………77
B-1 Cooley-Tukey CFFT………………………………77
B-2 Cooley-Tukey CFFT（Ver.5）……………………81
B-3 Packing CFFT……………………………………86
B-4 Radix-4 CFFT……………………………………91
B-5 Split-radix CFFT…………………………………99
B-6 Real-valued FFT………………………………105
B-7 Radix-2 FHT……………………………………111
B-8 Radix-4 FHT……………………………………117
B-9 Split-Radix FHT………………………………123

[1]熊京民、王柏村、巫崧佑、林志祥、陳建豪，2000，「風扇噪音之嵌入式品質檢測器」，中國機械工程學會第17屆全國學術研討會論文集，第809-816頁。
[2]Bracewell, R. N., 1983, “Discrete Hartley Transform,” Journal of Optical Society of America, Vol.73, No.12, pp.1832-1835.
[3]Bracewell, R. N., 1984, “The Fast Hartley Transform,” Proceeding of the IEEE, Vol.72, No.8, pp.1010-1018.
[4]Burrus, C. S., and Eschenbacher, P. W., 1981, “An In-Place, In-Order, Prime Factor FFT Algorithms,” IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol.ASSP-29, No.4, pp.806-816.
[5]Burrus, C. S., and Parks, T. W., 1984, DFT/FFT and Convolution Algorithms, John Wiely & Sons.
[6]Chapra, S. C., and Canale, R. P., 1988, Numerical Methods for Engineers, McGRAW-Hill.
[7]Cheng, Y. T., 2000, “Autoscaling Radix-4 FFT for TMS320- C6000,” Application Report of Texas Instruments.
[8]Dubois, E., and Venetsanopoulos, A. N., 1978, “A New Algorithm for Radix-3 FFT,” IEEE Transaction on Acoustics, Speech, and Signal Processing, Vol.ASSP-26, No.3, pp.222-225
[9]Duhamel, P., and Hollmann, H., 1984,“Split-Radix FFT Algorithm,” Electronic Letters, Vol.20, No.1, pp.14-16.
[10]Duhamel, P., 1986, “Implementation of Split-Radix FFT Algorithms for Complex, Real, and Real-Symmetric Data,” IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol.ASSP-34, No.2, pp.285-295.
[11]Hartley, R. V. L., 1942, “A More Symmetrical Fourier Analysis Applied to Transmission Problems,” Proceeding of the I.R.E., pp.144-149.
[12]Liu, J. C., and Lin, T. P., 1988, “Running DHT and Real-Time DHT Analyser,” Electronic Letters, Vol.24, No.12, pp.762-763.
[13]Malvar, H. S., 1987, “Fast Computation of Discrete Cosine Transform and Discrete Hartley Transform,” IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol.ASSP-35, No.10, pp.1484-1485.
[14]O’Nell, M. A., 1988, “Faster Then Fast Fourier,” BYTE, pp.293-300
[15]Phillips, C. L. and Parr, J. M., 1995, Signals, System and Transforms, Prentice-Hall.
[16]Smith, S. W., 1997, The Scientist and Engineer’s Guide to Digital Signal Processing, California Technical Publishing.
[17]Sorense, H. V., Jones, D. L., Burrus, C. S., and Heideman, M. T., 1985, “On Computing the Discrete Hartely Transform,” IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol.ASSP-33, No.4, pp.1231-1238.
[18]Sorense, H. V., Heideman, M. T., and Burrus, C. S., 1986, “On Computing the Split-Radix FFT,” IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol.ASSP-34, No.1, pp.152-156.
[19]Sorense, H. V., Jones, D. L., Heideman, M. T., and Burrus, C. S., 1985, “Real-Valued Fast Fourier Transform Algorithms,” IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol.ASSP-35, No.6, pp.849-863.
[20]Suzuki, Y., Sone, T., and Kido, K., 1986, “A New FFT Algorithms of Radix 3, 6, and 12,” IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol.ASSP-34, No.2, pp.380-383.