The Fourier transform is very important to numerous applications in science and engineering. However, its usefulness is hampered by its computational expense. In this paper, in an attempt to develop a faster method fo...The Fourier transform is very important to numerous applications in science and engineering. However, its usefulness is hampered by its computational expense. In this paper, in an attempt to develop a faster method for computing Fourier transforms, the authors present parallel implementations of two new algorithms developed for the type IV Discrete Cosine Transform （DCT-IV） which support the new interleaved fast Fourier transform method. The authors discuss the realizations of their implementations using two paradigms. The first involved commodity equipment and the Message-Passing Interface （MPI） library. The second utilized the RapidMind development platform and the Cell Broadband Engine （BE） processor. These experiments indicate that the authors＇ rotation-based algorithm is preferable to their lifting-based algorithm on the platforms tested, with increased efficiency demonstrated by their MPI implementation for large data sets. Finally, the authors outline future work by discussing an architecture-oriented method for computing DCT-IVs which promises further optimization. The results indicate a promising fresh direction in the search for efficient ways to compute Fourier transforms.展开更多
该文介绍了离散时间傅里叶变换(Discrete Time Fourier Transform,DTFT)的一种等价定义式,分析了DTFT与线性调频Z变换(Chirp-Z transform)的联系与区别,推导出DTFT是一种特殊形式的Chirp-Z变换,具有频谱细化特性。设计了DTFT的快速算法...该文介绍了离散时间傅里叶变换(Discrete Time Fourier Transform,DTFT)的一种等价定义式,分析了DTFT与线性调频Z变换(Chirp-Z transform)的联系与区别,推导出DTFT是一种特殊形式的Chirp-Z变换,具有频谱细化特性。设计了DTFT的快速算法,给出了算法实现步骤。算法计算量分析表明:在相同频率分辨率下,DTFT快速算法的计算量比Chirp-Z变换快速算法小。仿真结果验证了理论推导的正确性和DTFT在频率估计方面的优越性。展开更多
Accurate frequency estimation in a wideband digital receiver using the FFT algorithm encounters challenges, such as spectral leakage resulting from the FFT’s assumption of signal periodicity. High-resolution FFTs pos...Accurate frequency estimation in a wideband digital receiver using the FFT algorithm encounters challenges, such as spectral leakage resulting from the FFT’s assumption of signal periodicity. High-resolution FFTs pose computational demands, and estimating non-integer multiples of frequency resolution proves exceptionally challenging. This paper introduces two novel methods for enhanced frequency precision: polynomial interpolation and array indexing, comparing their results with super-resolution and scalloping loss. Simulation results demonstrate the effectiveness of the proposed methods in contemporary radar systems, with array indexing providing the best frequency estimation despite utilizing maximum hardware resources. The paper demonstrates a trade-off between accurate frequency estimation and hardware resources when comparing polynomial interpolation and array indexing.展开更多
Starting from an index mapping for one to multi-dimensions, a general in-placeand in-order prime factor FFT algorithm is proposed in this paper. In comparing with existingprime factor FFT algorithms, this algorithm sa...Starting from an index mapping for one to multi-dimensions, a general in-placeand in-order prime factor FFT algorithm is proposed in this paper. In comparing with existingprime factor FFT algorithms, this algorithm saves about half of the required storage capacityand possesses a higher efficiency. In addition, this algorithm can easily implement the DFT andIDFT in a single subroutine,展开更多
By introducing a form of reorder for multidimensional data, we propose a unified fast algo-rithm that jointly employs one-dimensional W transform and multidimensional discrete polynomial trans-form to compute eleven t...By introducing a form of reorder for multidimensional data, we propose a unified fast algo-rithm that jointly employs one-dimensional W transform and multidimensional discrete polynomial trans-form to compute eleven types of multidimensional discrete orthogonal transforms, which contain three types of m-dimensional discrete cosine transforms ( m-D DCTs) ,four types of m-dimensional discrete W transforms ( m-D DWTs) ( m-dimensional Hartley transform as a special case), and four types of generalized discrete Fourier transforms ( m-D GDFTs). For real input, the number of multiplications for all eleven types of the m-D discrete orthogonal transforms needed by the proposed algorithm are only 1/m times that of the commonly used corresponding row-column methods, and for complex input, it is further reduced to 1/(2m) times. The number of additions required is also reduced considerably. Furthermore, the proposed algorithm has a simple computational structure and is also easy to be im-plemented on computer, and the numerical experiments show that the computational efficiency is con-sistent with the theoretic analysis.展开更多
文摘The Fourier transform is very important to numerous applications in science and engineering. However, its usefulness is hampered by its computational expense. In this paper, in an attempt to develop a faster method for computing Fourier transforms, the authors present parallel implementations of two new algorithms developed for the type IV Discrete Cosine Transform （DCT-IV） which support the new interleaved fast Fourier transform method. The authors discuss the realizations of their implementations using two paradigms. The first involved commodity equipment and the Message-Passing Interface （MPI） library. The second utilized the RapidMind development platform and the Cell Broadband Engine （BE） processor. These experiments indicate that the authors＇ rotation-based algorithm is preferable to their lifting-based algorithm on the platforms tested, with increased efficiency demonstrated by their MPI implementation for large data sets. Finally, the authors outline future work by discussing an architecture-oriented method for computing DCT-IVs which promises further optimization. The results indicate a promising fresh direction in the search for efficient ways to compute Fourier transforms.
文摘该文介绍了离散时间傅里叶变换(Discrete Time Fourier Transform,DTFT)的一种等价定义式,分析了DTFT与线性调频Z变换(Chirp-Z transform)的联系与区别,推导出DTFT是一种特殊形式的Chirp-Z变换,具有频谱细化特性。设计了DTFT的快速算法,给出了算法实现步骤。算法计算量分析表明:在相同频率分辨率下,DTFT快速算法的计算量比Chirp-Z变换快速算法小。仿真结果验证了理论推导的正确性和DTFT在频率估计方面的优越性。
文摘Accurate frequency estimation in a wideband digital receiver using the FFT algorithm encounters challenges, such as spectral leakage resulting from the FFT’s assumption of signal periodicity. High-resolution FFTs pose computational demands, and estimating non-integer multiples of frequency resolution proves exceptionally challenging. This paper introduces two novel methods for enhanced frequency precision: polynomial interpolation and array indexing, comparing their results with super-resolution and scalloping loss. Simulation results demonstrate the effectiveness of the proposed methods in contemporary radar systems, with array indexing providing the best frequency estimation despite utilizing maximum hardware resources. The paper demonstrates a trade-off between accurate frequency estimation and hardware resources when comparing polynomial interpolation and array indexing.
基金Supported by the National Natural Science Foundation of China
文摘Starting from an index mapping for one to multi-dimensions, a general in-placeand in-order prime factor FFT algorithm is proposed in this paper. In comparing with existingprime factor FFT algorithms, this algorithm saves about half of the required storage capacityand possesses a higher efficiency. In addition, this algorithm can easily implement the DFT andIDFT in a single subroutine,
基金This work was supported by the National Natural Science Foundation of China (Grant No. 69974041).
文摘By introducing a form of reorder for multidimensional data, we propose a unified fast algo-rithm that jointly employs one-dimensional W transform and multidimensional discrete polynomial trans-form to compute eleven types of multidimensional discrete orthogonal transforms, which contain three types of m-dimensional discrete cosine transforms ( m-D DCTs) ,four types of m-dimensional discrete W transforms ( m-D DWTs) ( m-dimensional Hartley transform as a special case), and four types of generalized discrete Fourier transforms ( m-D GDFTs). For real input, the number of multiplications for all eleven types of the m-D discrete orthogonal transforms needed by the proposed algorithm are only 1/m times that of the commonly used corresponding row-column methods, and for complex input, it is further reduced to 1/(2m) times. The number of additions required is also reduced considerably. Furthermore, the proposed algorithm has a simple computational structure and is also easy to be im-plemented on computer, and the numerical experiments show that the computational efficiency is con-sistent with the theoretic analysis.
