https://scholars.lib.ntu.edu.tw/handle/123456789/121894
標題: | 離散傅利葉轉換與哈特利轉換的快速演算法 Fast Algorithms for Discrete Fourier Transform and Discrete Hartley Transform |
作者: | 陳威宇 Chen, Wei-Yu |
關鍵字: | 傅利葉轉換;哈特利轉換;快速演算法;Fourier Transform;Fast Algorithm;Hartley Trnasform | 公開日期: | 2004 | 摘要: | 離散傅利葉轉換(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. |
URI: | http://ntur.lib.ntu.edu.tw//handle/246246/58683 | 其他識別: | en-US |
顯示於: | 電信工程學研究所 |
檔案 | 描述 | 大小 | 格式 | |
---|---|---|---|---|
ntu-93-R91942068-1.pdf | 23.31 kB | Adobe PDF | 檢視/開啟 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。