Fast Algorithms for Discrete Fourier Transform and Discrete Hartley Transform
Date Issued
2004
Date
2004
Author(s)
Chen, Wei-Yu
DOI
en-US
Abstract
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.
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.
Subjects
傅利葉轉換
哈特利轉換
快速演算法
Fourier Transform
Fast Algorithm
Hartley Trnasform
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-93-R91942068-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):8228b42612e0c4bdf70bd92b4f250de7