Search

For front-end wireless applications in small battery-powered devices, discrete Fourier transform (DFT) is a critical processing method for discrete time signals. Advanced radix structures are created to reduce the impact of transistor malfunction. To develop DFT, with radix sizes 4, 8, etc., is a complex and tricky issue for algorithm designers. The main reason for this is that the butterfly algorithm's lower-radix-level equations were manually estimated. This requires the selection of a new design process. As a result of fewer calculations and smaller memory requirements for computationally intensive scientific applications, this research focuses on the radix-4 fast Fourier-transform (FFT) technique. A new 64-point DFT method based on radix-4 FFT and multi-stage strategy to solve DFT-related issues is presented in this paper. Based on the results of simulations with Xilinx ISE, it can be concluded that the algorithm developed is faster than conventional approaches, with an 18.963 ns delay and 12.68 mW of power consumption. It was found that the computed picture compression drop ratios of 0.10, 0.31, 0.61 and 0.83 had a direct relationship to the varied tolerances tested, 0.0007625, 0.003246, 0.013075 and 0.03924. Fast reconstruction techniques, wireless medical devices and other applications benefit from this FFT's low power consumption, small storage requirements, and high processing speed. [ABSTRACT FROM AUTHOR]

The proliferation of renewable-based distributed generators poses protection challenges for the overcurrent relays due to the intermittent nature and control schemes. Converters present in the AC side restrict the fault current up to two per unit. Therefore, the overcurrent relay present in the AC microgrid maloperates during the fault. The proposed technique is based on the corresponding sum of the current samples obtained after every half-cycle (Ts/2), computed for each phase, and utilized to derive an index to detect the fault. The index thus derived is robust to noises, load variations, and other transients in the system. However, the technique requires removing transients and other noises before comparing the threshold for fault detection, which is resolved using the fast Fourier transform (FFT). Further, the magnitude of decaying DC (as another index) present in the signal is calculated using the least square technique for detecting the three-phase fault. The proposed algorithm is tested on an IEEE 14-bus system and a Real-Time Digital Simulator microgrid model. The fault detection technique is accurate for different faults under different operating conditions like noise, CT saturation, sudden load change, etc. [ABSTRACT FROM AUTHOR]

We use the well-known observation that the solutions of Jacobi's differential equation can be represented via the non-oscillatory phase and amplitude functions to develop a fast algorithm for computing multi-dimensional Jacobi polynomial transforms. More explicitly, it follows from this observation that the matrix corresponding to the discrete Jacobi transform is the Hadamard product of a numerically low-rank matrix and a multi-dimensional discrete Fourier transform (DFT) matrix. The application of the Hadamard product can be carried out via r d fast Fourier transforms (FFTs), where r = O (log ⁡ n log ⁡ log ⁡ n) and d is the dimension, resulting in a nearly optimal algorithm to compute the multidimensional Jacobi polynomial transform. [ABSTRACT FROM AUTHOR]

In the sparse polynomial multiplication problem, one is asked to multiply two sparse polynomials $f$ and $g$ in time that is proportional to the size of the input plus the size of the output. The polynomials are given via lists, $F$ and $G$ , of their coefficients. Cole and Hariharan (STOC 02) have given a nearly optimal algorithm when the coefficients are positive, and Arnold and Roche (ISSAC 15) devised an algorithm running in time proportional to the “structural sparsity” of the product, i.e. the set $\mathrm {supp}(F) + \mathrm {supp}(G)$. The latter algorithm is particularly efficient when there are not “too many cancellations” of coefficients in the product. In this work we give a clean, nearly optimal algorithm for the sparse polynomial multiplication problem. [ABSTRACT FROM AUTHOR]

The fast Fourier transform-moving average (FFT-MA) is an efficient method for the generation of geostatistical simulations. The method relies on the calculation of a filter operator based on the covariance function of interest and the convolution of the filter with a white noise, to generate multiple realizations of spatially correlated variables. In this work, a revisited mathematical formulation of the FFT-MA method, with the exact expression of the filter, is presented. The proposed derivation of the filter is based on the Wiener–Khinchin theorem and the application of the Fourier transform in a discrete domain. In the specific case of white noise, the proposed formulation leads to the same expression of the traditional algorithm. However, the method can be applied to other types of noise. The proposed technique allows the calculation of a specific filter that imposes an exact covariance function on the noise. Therefore, the experimental covariance function is exactly equal to the theoretical one, which is not the case for many common simulation techniques due to the limited sample size. Applications of the FFT-MA method to synthetic and real data sets, including exact interpolation, hard data conditioning and correlated simulations from cross-correlated noises, are also presented. [ABSTRACT FROM AUTHOR]

This paper introduces the notion of numerical basis for a numerical space and uses it to establish a relation between a fast algorithm for computing a discrete linear transform and the problem of expanding a given finite set of matrices as a linear combination of rank-1 matrices. It is shown that the number of multiplications of the algorithm is given by the number of rank-1 matrices in the expansion. Applying this approach, an algorithm for computing three components of the nine-point discrete Fourier transform (DFT) and an algorithm to compute the seven-point DFT with the least possible number of multiplications are shown. [ABSTRACT FROM AUTHOR]

We present a new algorithm for the 2D sliding window discrete Fourier transform. Our algorithm avoids repeating calculations in overlapping windows by storing them in a tree data-structure based on the ideas of the Cooley-Tukey fast Fourier transform. For an N0 × N1 array and n0 × n1 windows, our algorithm takes O(N0 N1 n0 n1) operations. We provide a C implementation of our algorithm for the Radix-2 case, compare ours to existing algorithms, and show how our algorithm easily extends to higher dimensions. [ABSTRACT FROM AUTHOR]

Adaptive Fourier decomposition (AFD) has been found to be among the most effective greedy algorithms. AFD shows an outstanding performance in signal analysis and system identification. As compensation of effectiveness, the computation complexity is great, that is especially due to maximal selections of the parameters. In this paper, we explore the discretization of the 1-D AFD integration via with discrete Fourier transform (DFT), incorporating fast Fourier transform (FFT). We show that the new algorithm, called FFT-AFD, reduces the computational complexity from O ( M N 2 ) to O ( M N log N ) , the latter being the same as FFT. Through experiments, we verify the effectiveness, accuracy, and robustness of the proposed algorithm. The proposed FFT-based algorithm for AFD lays a foundation for its practical applications. [ABSTRACT FROM AUTHOR]

Owing to its simplicity radix-2 is a popular algorithm to implement fast fourier transform. Radix-2palgorithms have the same order of computational complexity as higher radices algorithms, but still retain the simplicity of radix-2. By defining a new concept, twiddle factor template, in this paper, we propose a method for exact calculation of multiplicative complexity for radix-2p algorithms. The methodology is described for radix-2, radix-22 and radix-22 algorithms. Results show that radix-22 and radix-23 have significantly less computational complexity compared with radix-2. Another interesting result is that while the number of complex multiplications in radix-23 algorithm is slightly more than radix-22, the number of real multiplications for radix-23 is less than radix-22. This is because of the twiddle factors in the form of W(2k+1)N/8 which need less number of real multiplications and are more frequent in radix-23 algorithm. [ABSTRACT FROM AUTHOR]