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.展开更多
This paper revisits the characteristics of windowing techniques with various window functions involved,and successively investigates spectral leakage mitigation utilizing the Welch method.The discrete Fourier transfor...This paper revisits the characteristics of windowing techniques with various window functions involved,and successively investigates spectral leakage mitigation utilizing the Welch method.The discrete Fourier transform(DFT)is ubiquitous in digital signal processing(DSP)for the spectrum analysis and can be efciently realized by the fast Fourier transform(FFT).The sampling signal will result in distortion and thus may cause unpredictable spectral leakage in discrete spectrum when the DFT is employed.Windowing is implemented by multiplying the input signal with a window function and windowing amplitude modulates the input signal so that the spectral leakage is evened out.Therefore,windowing processing reduces the amplitude of the samples at the beginning and end of the window.In addition to selecting appropriate window functions,a pretreatment method,such as the Welch method,is effective to mitigate the spectral leakage.Due to the noise caused by imperfect,nite data,the noise reduction from Welch’s method is a desired treatment.The nonparametric Welch method is an improvement on the periodogram spectrum estimation method where the signal-to-noise ratio(SNR)is high and mitigates noise in the estimated power spectra in exchange for frequency resolution reduction.The periodogram technique based on Welch method is capable of providing good resolution if data length samples are appropriately selected.The design of nite impulse response(FIR)digital lter using the window technique is rstly addressed.The inuence of various window functions on the Fourier transform spectrum of the signals is discussed.Comparison on spectral resolution based on the traditional power spectrum estimation and various window-function-based Welch power spectrum estimations is presented.展开更多
A scheme for designing one-dimensional (1-D) convolution window of the circularly symmetric Gabor filter which is directly obtained from frequency domain is proposed. This scheme avoids the problem of choosing the sam...A scheme for designing one-dimensional (1-D) convolution window of the circularly symmetric Gabor filter which is directly obtained from frequency domain is proposed. This scheme avoids the problem of choosing the sampling frequency in the spatial domain, or the sampling frequency must be determined when the window data is obtained by means of sampling the Gabor function, the impulse response of the Gabor filter. In this scheme, the discrete Fourier transform of the Gabor function is obtained by discretizing its Fourier transform. The window data can be derived by minimizing the sums of the squares of the complex magnitudes of difference between its discrete Fourier transform and the Gabor function's discrete Fourier transform. Not only the full description of this scheme but also its application to fabric defect detection are given in this paper. Experimental results show that the 1-D convolution windows can be used to significantly reduce computational cost and greatly ensure the quality of the Gabor filters. So this scheme can be used in some real-time processing systems.展开更多
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,展开更多
In this paper, we have proved that the lower bound of the number of real multiplications for computing a length 2(t) real GFT(a,b) (a = +/-1/2, b = 0 or b = +/-1/2, a = 0) is 2(t+1) - 2t - 2 and that for computing a l...In this paper, we have proved that the lower bound of the number of real multiplications for computing a length 2(t) real GFT(a,b) (a = +/-1/2, b = 0 or b = +/-1/2, a = 0) is 2(t+1) - 2t - 2 and that for computing a length 2t real GFT(a,b)(a = +/-1/2, b = +/-1/2) is 2(t+1) - 2. Practical algorithms which meet the lower bounds of multiplications are given.展开更多
文摘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.
基金supported by the Ministry of Science and Technology,Taiwan[Grant Numbers MOST 104-2221-E-019-026-MY2 and MOST 108-2221-E019-013].
文摘This paper revisits the characteristics of windowing techniques with various window functions involved,and successively investigates spectral leakage mitigation utilizing the Welch method.The discrete Fourier transform(DFT)is ubiquitous in digital signal processing(DSP)for the spectrum analysis and can be efciently realized by the fast Fourier transform(FFT).The sampling signal will result in distortion and thus may cause unpredictable spectral leakage in discrete spectrum when the DFT is employed.Windowing is implemented by multiplying the input signal with a window function and windowing amplitude modulates the input signal so that the spectral leakage is evened out.Therefore,windowing processing reduces the amplitude of the samples at the beginning and end of the window.In addition to selecting appropriate window functions,a pretreatment method,such as the Welch method,is effective to mitigate the spectral leakage.Due to the noise caused by imperfect,nite data,the noise reduction from Welch’s method is a desired treatment.The nonparametric Welch method is an improvement on the periodogram spectrum estimation method where the signal-to-noise ratio(SNR)is high and mitigates noise in the estimated power spectra in exchange for frequency resolution reduction.The periodogram technique based on Welch method is capable of providing good resolution if data length samples are appropriately selected.The design of nite impulse response(FIR)digital lter using the window technique is rstly addressed.The inuence of various window functions on the Fourier transform spectrum of the signals is discussed.Comparison on spectral resolution based on the traditional power spectrum estimation and various window-function-based Welch power spectrum estimations is presented.
基金Scientific and Technological Development Project of Beijing Municipal Education Commission (No KM200510012002)
文摘A scheme for designing one-dimensional (1-D) convolution window of the circularly symmetric Gabor filter which is directly obtained from frequency domain is proposed. This scheme avoids the problem of choosing the sampling frequency in the spatial domain, or the sampling frequency must be determined when the window data is obtained by means of sampling the Gabor function, the impulse response of the Gabor filter. In this scheme, the discrete Fourier transform of the Gabor function is obtained by discretizing its Fourier transform. The window data can be derived by minimizing the sums of the squares of the complex magnitudes of difference between its discrete Fourier transform and the Gabor function's discrete Fourier transform. Not only the full description of this scheme but also its application to fabric defect detection are given in this paper. Experimental results show that the 1-D convolution windows can be used to significantly reduce computational cost and greatly ensure the quality of the Gabor filters. So this scheme can be used in some real-time processing systems.
基金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,
文摘In this paper, we have proved that the lower bound of the number of real multiplications for computing a length 2(t) real GFT(a,b) (a = +/-1/2, b = 0 or b = +/-1/2, a = 0) is 2(t+1) - 2t - 2 and that for computing a length 2t real GFT(a,b)(a = +/-1/2, b = +/-1/2) is 2(t+1) - 2. Practical algorithms which meet the lower bounds of multiplications are given.
