(3.238.96.184) 您好!臺灣時間:2021/05/08 04:34
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:陳威宇
研究生(外文):Wei-Yu Chen
論文名稱:離散傅利葉轉換與哈特利轉換的快速演算法
論文名稱(外文):Fast Algorithms for Discrete Fourier Transformand Discrete Hartley Transform
指導教授:貝蘇章
指導教授(外文):Soo-Chang Pei
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電信工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:英文
論文頁數:103
中文關鍵詞:傅利葉轉換哈特利轉換快速演算法
外文關鍵詞:Fourier TransformFast AlgorithmHartley Trnasform
相關次數:
  • 被引用被引用:0
  • 點閱點閱:271
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
離散傅利葉轉換(DFT)與離散哈特利轉換(DHT)的快速演算法已經被研究了釵h年了,最近幾年,split-radix-2/8的快速傅利葉轉換演算法也被發表了,這種演算法的運算複雜度跟以往的split-radix-2/4快速傅利葉轉換的演算法一樣,但是卻可以省下25%的資料讀取與儲存的動作。
在這篇論文中,我們用split-radix-2/8的方式推導出了split vector-radix-2/8二維快速傅利葉轉換的演算法。我們發現跟一維的情況一樣可以省下25%的資料傳輸量,除此之外,跟split vector-radix-2/4二維快速傅利葉轉換相比,它可以省下14%的實數乘法,運算複雜度也低了釵h。
除了離散傅利葉轉換,我們也把split-radix-2/8的原理用在一維與二維的離散哈特利轉換,在兩種情況下,都可以省下25%的資料讀取與儲存的次數,在一維的情況下,split-radix-2/8快速哈特利轉換演算法的運算複雜度跟split-radix-2/4快速哈特利轉換一樣。另一方面,跟原本的split vector-radix-2/4快速哈特利轉換演算法比較,split vector-radix-2/8二維快速哈特利轉換省下了6%的實數乘法以及4.5%的實數加法。
在論文的最後一部分,我們介紹了一些可以得到非常精確的離散傅利葉轉換結果的演算法。隨著演算法的階數(order)越高,離散傅利葉轉換的結果就越接近該函數的連續傅利葉轉換,同時,演算法的複雜度也跟著增加,所以我們必須根據不同的應用選擇適合的演算法。
The fast algorithms for computing the discrete Fourier transform (DFT) and the discrete Hartley transform (DHT) have been studied for many years. The extended split-radix-2/8 fast Fourier transform algorithm has been proposed recently. This algorithm has the same arithmetic complexity as the conventional split-radix-2/4 fast Fourier transform algorithm, but it saves 25% of data loads and stores.
In this paper, we use the split-radix-2/8 method to develop a split vector-radix-2/8 2-D fast Fourier transform algorithm. We obtain that it could save 25% of data transfer, which is the same as the 1-D case. Moreover, it reduces 14% of real multiplications and has much lower computational complexity compared with the split vector-radix-2/4 fast Fourier transform algorithm.
In addition to the discrete Fourier transform, we applied the split-radix-2/8 method on the 1-D and 2-D discrete Hartley transform. In both cases, it saves 25% of data loads and stores compared with the split-radix-2/4 method. In the 1-D discrete Hartley transform case, the split-radix-2/8 fast Hartley transform algorithm has the same arithmetic complexity as the split-radix-2/4 fast Hartley transform. On the other hand, the split vector-radix-2/8 2-D fast Hartley transform algorithm saves 6% real multiplications and 4.5% real additions than the existing split vector-radix-2/4 2-D fast Hartley transform.
In the last part of this thesis, we introduce some algorithms which can provide high-accuracy result for discrete Fourier transform. As the order of the algorithms increases, the results of the discrete Fourier transform match the continuous Fourier transform of the input function better. In the mean while, the complexity increases, too. So we should choose the suitable algorithms on different applications.
Abstuact i
List of Figures ix
List of Tables xi
Chapter 1 Introduction 1
Chapter 2 Split-Radix-2/8 Fast Fourier Transform 5
2.1 Introduction 5
2.2 Split-Radix-2/8 Fast Fourier Transform 6
2.2.1 Fast Fourier Transform 6
2.2.2 Split-Radix-2/4 Fast Fourier Transform 7
2.2.3 Split-Radix-2/8 Fast Fourier Transform 9
2.3 Complexity Evaluation 11
2.3.1 Complexity of Split-Radix-2/8 Fast Fourier Transform 11
2.3.2 Comparisons 13
2.4 Conclusion 13
Chapter 3 Split Vector-Radix-2/8 2-D Fast Fourier Transform 15
3.1 Introduction 15
3.2 Split Vector-Radix-2/8 2-D Fast Fourier Transform 16
3.2.1 Vector-Radix 2-D Fast Fourier Transform 16
3.2.2 Split Vector-Radix-2/4 2-D Fast Fourier Transform 18
3.2.3 Split Vector-Radix-2/8 2-D Fast Fourier Transform 20
3.3 Complexity Evaluation 25
3.3.1 Complexity of Split Vector-Radix-2/8 2-D Fast Fourier Transform 25
3.3.2 Comparisons 28
3.4 Conclusion 29
Chapter 4 Split-Radix-2/8 Fast Hartley Transform 31
4.1 Introduction 31
4.2 Split-Radix-2/8 Fast Hartley Transform 32
4.2.1 Fast Hartley Transform 32
4.2.2 Split-Radix-2/4 Fast Hartley Transform 33
4.2.3 Split-Radix-2/8 Fast Hartley Transform 35
4.3 Complexity Evaluation 39
4.3.1 Complexity of Split-Radix-2/8 Fast Hartley Transform 39
4.3.2 Comparisons 40
4.4 Conclusion 41
Chapter 5 Split Vector-Radix-2/8 2-D Fast Hartley Transform 43
5.1 Introduction 43
5.2 Split Vector-Radix-2/8 2-D Fast Hartley Transform 44
5.2.1 Vector-Radix 2-D Fast Hartley Transform 44
5.2.2 Split Vector-Radix-2/4 2-D Fast Hartley Transform 46
5.2.3 Split Vector-Radix-2/8 2-D Fast Hartley Transform 50
5.3 Complexity Evaluation 56
5.3.1 Complexity of Split Vector-Radix-2/8 2-D Fast Hartley Transform 56
5.3.2 Comparisons 58
5.4 Conclusion 58
Chapter 6 High-Accuracy Method for Discrete Fourier Transform 59
6.1 Introduction 59
6.2 First Order Method for The Calculation of The Fourier Transform of Discrete Signals 60
6.2.1 Difference Between The Discrete Fourier Transform and The Continuous Fourier Transform 60
6.2.2 POLFFT Algorithm 64
6.3 Second Order Method for The Calculation of The Fourier Transform of Discrete Signals 68
6.3.1 POL2FT Algorithm 68
6.4 Nth Order Method for The Calculation of The Fourier Transform of Discrete Signals 72
6.4.1 A High-Accuracy Method for Fourier Transform 72
6.5 Simulation Result and Conclusion 80
Chapter 7 Conclusion and Future Works 83
7.1 Conclusion 83
7.2 Future Works 85
Reference 87
[1].Alan V. Oppenheim, Ronald W. Schafer, and John R. Buck, “Discrete-Time Signal Processing,” Sec. Edition, Prentice Hall International, Inc.
[2].J. W. Cooley and J. W. Tukey, “An Algorithm for the Machine Computation of Complex Fourier Series,” Math. Comput., vol. 19, pp. 297-301, Apr. 1965
[3].P. Duhamel and H. Hollmann, “Split-radix FFT algorithm,” Electron. Lett., vol. 20, pp. 14-16, Jan. 1984.
[4].M. Vetterli and P. Duhamel, “Split-radix algorithms for lengh- DFT’s,” IEEE Trans. Acoust,. Speech, Signal Processing, vol. 37, pp. 57-64, Jan. 1989.
[5].H. V. Sorensen, M. T. Heideman, and C. S. Burrus, “On computing the split-radix FFT.” IEEE Trans. Acoust,. Speech, Signal Processing, vol. ASSP-34, pp. 152-156, Feb. 1986.
[6].D. Takahashi, “An extended split-radix FFT algorithm,” IEEE Signal Processing Lett., vol. 8, pp. 145-147, May 2001.
[7].D. B. Harris and J. H. McClellan, “Vector-radix fast Fourier transform,” Proc, IEEE Int. Conf. Acoust., Speech, Signal Processing, May 1977, pp. 548-551.
[8].S. C. Pei and J. L. Wu, “Split vector-radix 2D fast Fourier transform,” IEEE Trans. Circuits and Syst., vol. CAS-34, Aug. 1987, pp. 978-980.
[9].Z. J. Mou and P. Duhamel, “In-place butterfly-style FFT of 2-D real sequences,” IEEE Trans. Acoust., Speech, Signal Processing, vol. 36, pp. 1642-1650, Oct. 1988.
[10].H. R. Wu and F. J. Paoloni, “On the two-dimensional vector-radix FFT algorithm,” IEEE Trans. Acoust., Speech, Signal Processing, vol. 37, pp. 1302-1304, Aug. 1989.
[11].S. C. Chan, “Fast transform algorithms and their applications,” Ph. D dissertation, the University of Hong Kong, 1992.
[12].S. C. Chan and K. L. Ho, “Split vector-radix fast Fourier transform,” IEEE Trans. Signal Processing, vol. 40, pp.2029-2039, Aug. 1992.
[13].R. N. Bracewell, “The fast Hartley transform,” Proc. IEEE, vol. 72, pp. 1010-1018, 1984.
[14].H. V. Sorensen, D. L. Jones, C. S. Burrus, and M. T. Heideman, “On computing the discrete Hartley transform,” IEEE Trans. Acoust., Speech, Signal Processing, vol. ASSP-33, pp.1231-1238, Oct. 1985.
[15].S. C. Pei and J. L. Wu, “ Split-radix fast Hartley transform,” Electron. Lett., vol. 22, no. 1, pp. 26-27, Jan. 1986.
[16].J. L. Wu and S. C. Pei, “The Vector Split-Radix Algorithm for 2-D DHT,” IEEE Trans. Signal Processing, vol. 41, no. 2, pp. 960-965, Feb. 1993.
[17].Guoan Bi, “Split-Radix Algorithm for 2-D Discrete Hartley Transform,” Signal Processing, vol. 63, pp. 45-53, 1997.
[18].Edmond A. Jonckheere and Chingwo Ma, “Split-Radix Fast Hartley Transform in One and Two Dimensions,” IEEE Trans. Signal Processing, vol. 39, no. 2, Feb. 1991.
[19].J. Schütte, “New fast Fourier transform algorithm for linear system analysis applied in molecular beam relaxation spectroscopy,” Rev. Sci. Instrum., vol. 52, pp. 400-404, Mar. 1981
[20].S. Mäkinen, “New algorithm for the calculation of the Fourier transform of the discrete signals,” Rev. Sci. Instrum., vol. 53, pp. 627-630. May 1982.
[21].S. Sorella and S. K. Ghosh, “Improved method for the discrete fast Fourier transform,” Rev. Sci. Instrum., vol. 55, pp. 1348-1352. Aug. 1984.
[22].N. Beaudoin, “A high-accuracy mathematical and numerical method for Fourier transform, integral, derivative, and polynomial splines of any order,” Can. J. Phys., vol. 76, no. 9, pp. 659-677, 1998.
[23].N. Beaudoin and S. S. Beauchemin, “An Accurate Discrete Fourier Transform for Image Processing,” International Conference on Pattern Recognition 2002. Proceeding 16th, vol. 3, pp. 935-939, Aug. 2002.
[24].N. Beaudoin and S. S. Beauchemin, “A new numerical Fourier transform in d-dimensions,” IEEE Trans. Signal Processing, vol. 51, pp. 1422-1430, May 2003.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔