貝蘇章臺灣大學：電信工程學研究所陳威宇Chen, Wei-YuWei-YuChen2007-11-272018-07-052007-11-272018-07-052004http://ntur.lib.ntu.edu.tw//handle/246246/58683離散傅利葉轉換(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 871003349 bytesapplication/pdfen-US傅利葉轉換哈特利轉換快速演算法Fourier TransformFast AlgorithmHartley Trnasformthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/58683/1/ntu-93-R91942068-1.pdf