跳到主要內容

臺灣博碩士論文加值系統

(44.210.21.70) 您好!臺灣時間:2022/08/15 09:27
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:陳建豪
論文名稱:以DSP實現快速傅氏轉換與快速哈氏轉換演算法及效率比較
論文名稱(外文):Implementation and Efficiency Comparison of FFT and FHT Algorithms on DSP
指導教授:熊京民
指導教授(外文):Hsiung Chin-Min
學位類別:碩士
校院名稱:國立屏東科技大學
系所名稱:機械工程系
學門:工程學門
學類:機械工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
中文關鍵詞:數位信號處理器快速傅立葉轉換快速哈氏轉換計算效率計算週期
外文關鍵詞:DSPFFTFHTcomputation efficiencycomputation cycle
相關次數:
  • 被引用被引用:1
  • 點閱點閱:458
  • 評分評分:
  • 下載下載:65
  • 收藏至我的研究室書目清單書目收藏:1
本文主要目的是將快速傅氏轉換(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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
1. 5. 金仁初,1993,CCD電荷藕合元件偵測器簡介,科儀新知,第三期第十五卷。
2. 3. 李盈壕、江德明,1998,ICP-OES的新發展-固態電荷轉換式偵測器,科儀新知,第二十卷三期。
3. 金繼春(1986)學齡白血病患童所感受的壓力源及其應變策略‧高雄醫學科學雜誌,2(1),688-693。
4. 林達雄(2001)‧遺傳代謝異常─苯酮尿症‧媽媽寶寶‧227-229。
5. 王文玲(1992)‧與慢性病共存─慢性病患者家庭的需要‧護理雜誌,39(1),25-30。
6. 毛家舲、高麗蘭(1996)‧慢性疾病患者及其家屬的壓力與調適‧醫學繼續教育,2(5),805-812。
7. 林達雄(1999)‧被限制飲食的孩子─苯酮尿症‧育兒生活‧142-144。
8. 白瑞生、黃愛娟(1991)‧慢性疾病對家庭的影響‧榮總護理,8(1),32-39。
9. 6. 邱紀良,1993,紫外光可見光光譜儀的組件-一個使用者的剖析,科儀新知,第十四卷第四期。
10. 8. 陳有鋒,2000,淺談光電檢測介面技術-USB標準與技術,量測資訊,第76期。
11. 9. 黃志德,1994,光偵測器之量測標準與追溯,量測資訊,第39期。
12. 12. 羅蘇秦、張世英,1999,近紅外光譜儀之分析技術及其應用,科儀新知,第二十五卷第五期。
13. 13. 陳世銘、張文宏、謝廣文,1998,果汁糖度檢測模式之研究,農業機械學刊,第七卷第三期,第41∼60頁。
14. 15. 謝宗儒,1993,矽晶光偵測器之研製,光電資訊,積體光電元件技術專輯第17期。