Search

The algorithm of SFT (sparse Fourier transform) is firstly used for monochromatic light spectrum reconstruction in this paper. Due to the increasing amount of interference data, the operation efficiency of traditional algorithms is not satisfied with the demand of technology. We take advantage of SFT to achieve the goal of lower algorithm complexity and fewer operation time, instead of FFT (Fast Fourier Transform). In addition, two methods of the modern spectrum estimation, AR (Auto-Regressive) model and MUSIC (Multiple Signal Classification), which are considered as high resolution spectrum estimation algorithms, are used for discussion and comparison. The experiment result shows that the SFT gets excellent performance in runtime.

In this paper, we present new feedforward FFT hardware architectures based on rotator allocation. The rotator allocation approach consists in distributing the rotations of the FFT in such a way that the number of edges in the FFT that need rotators and the complexity of the rotators are reduced. Radix-2 and radix-2(k) feedforward architectures based on rotator allocation are presented in this paper. Experimental results show that the proposed architectures reduce the hardware cost significantly with respect to previous FFT architectures. Funding Agencies|Swedish ELLIIT Program

By viewing the nonuniform discrete Fourier transform (NUDFT) as a perturbed version of a uniform discrete Fourier transform, we propose a fast, stable, and simple algorithm for computing the NUDFT that costs $\mathcal{O}(N\log N\log(1/\epsilon)/\log\!\log(1/\epsilon))$ operations based on the fast Fourier transform, where $N$ is the size of the transform and $0, Comment: 18 pages

Reduced execution time and increased power efficiency are important objectives in the distributed execution of collaborative signal processing tasks over wireless sensor networks (WSNs). Meanwhile, Fourier transforms are among the most widely used frequency analysis tools in WSNs for studying the behavior of sensed phenomena. Several energy-efficient in-network Fourier transform computation algorithms have been proposed for WSNs. Most of these works assume that the sensors are equally spaced over a one-dimensional (1D) region. However, in practice, the sensors are usually randomly distributed over a two-dimensional (2D) plane. Consequently, the conventional 2D Fast Fourier Transform (FFT) designed for data sampled on a uniform grid is not applicable in such environments. We address this problem by designing a distributed hybrid structure consisting of local Non-equispaced Discrete Fourier Transform (NDFT) and global FFT computations. First, the NDFT method is applied within suitably selected clusters to obtain the initial uniform Fourier coefficients within allowable estimation error bounds. We investigate both classical linear and generalized interpolation methods for computing the NDFT coefficients within each cluster. Second, a separable 2D FFT is applied over all clusters using our proposed energy-efficient 1D FFT computation method, which reduces communication costs by employing a novel binary representation mapping strategy for data exchanges between sensors. The proposed techniques are implemented on the SIDnet-SWANS platform, and the tradeoffs between communication cost, execution time, and energy consumption are studied.

The efficiency of the recently developed algorithms for sparse Radon transforms depends heavily on the efficiency of the inverse transformation and its adjoint. In this paper, we propose a fast algorithm for the implementation of these canonical transforms, which runs in complexity O ( N f N log ⁡ N + N x N t log ⁡ N t ) for a signal of size N t × N x , as opposed to O ( N f N x N p + N x N t log ⁡ N t ) of the direct computation, where N depends on the maximum frequency and offset in the data set, the maximum curvature in the Radon space, and N p . These transforms are utilized within the split Bregman iteration to solve the sparse Radon transform as an l 2 / l 1 optimization problem. The computations involved in each iteration of the proposed algorithm, are carried out by a fast Fourier transform (FFT) algorithm. Furthermore, in the new algorithm, the amount of regularization is controlled by iteration number. We obtain a good estimate of predictive error via the generalized cross validation (GCV) analysis and automatically determine the optimum number of iterations at a negligible cost, thus leading to an automatic fast algorithm. This allows a time-domain sparse Radon transformation of large-scale data that are otherwise intractable. Numerical tests using simulated data confirm high efficiency of the proposed algorithm for processing large-scale seismic data.

This brief proposes a continuous-flow memory-based architecture for fast Fourier transform (FFT) computation for real-valued signals. The proposed architecture is based on a modified radix-2 algorithm, which removes redundant operations to reduce resource usage. A new data-flow graph and address mapping scheme are proposed that satisfy the requirement of continuous-flow operation and minimize the memory usage. The proposed processing element takes advantage of pipelined FFT architectures to avoid bank conflicts in each stage. Compared with prior works, the proposed design has the advantage of supporting continuous-flow operation and normal-order output while minimizing the resource usage.

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(MN2) to O(MNlogN), 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.

In this paper, a novel grouping scheme of the basis functions within the framework of the fast Fourier transform (FFT)-based method is proposed for creating a block-sparse structure for the near-matrix, and then FFT-based method with near-matrix compression is established for the efficient analysis of multiscale problems. For a multiscale problem, if an FFT-based method is required to maintain both higher efficiency and higher accuracy at calculating the far interactions, then the near-matrix will be inevitably very large. Compared with the traditional FFT-based method, the proposed method can significantly reduce the near-matrix memory requirement without increasing the time spent. Several numerical examples are provided to demonstrate the correctness and the efficiency of the proposed method.

The discrete Fourier transform (DFT) is the most widely used technique for determining the frequency spectra of digital signals. However, in the sliding transform scenario where the transform window is shifted one sample at a time and the transform process is repeated, the use of DFT becomes difficult due to its heavy computational burden. This paper proposes an optimal sliding DFT (oSDFT) algorithm that achieves both the lowest computational requirement and the highest computational accuracy among existing sliding DFT algorithms. The proposed oSDFT algorithm directly computes the DFT bins of the shifted window by simply adding (or subtracting) the bins of a previous window and an updating vector. We show that the updating vector can be efficiently computed with a low complexity in the sliding transform scenario. Our simulations demonstrate that the proposed algorithm outperforms the existing sliding DFT algorithms in terms of computational accuracy and processing time.

The simulation of non-stationary wind velocity field based on the spectral representation method often requires significant computational efforts due to the summation of trigonometric functions usually involved in the simulation procedure. Some techniques which make use of FFT algorithm have been developed but most of these techniques deal with seismic ground motions. Limited effort has been devoted to the simulation of non-stationary wind velocity. Therefore, in this paper, a spectral-representation-based technique which takes advantage of FFT algorithm is proposed by combining Cholesky decomposition and Taylor series expansion. The approach consists of locating and expanding the time and frequency non separable part of the decomposed evolutionary power spectral density function by mean of Taylor series expansion to allow the application of the FFT algorithm. Samples of non-stationary wind velocity can be then generated through multiple executions of the FFT algorithm once the Taylor series expansion is successful. The present approach, which is primarily developed for the simulation of non-stationary wind velocity on long-span cable supported bridges, is very efficient since the summation of the trigonometric functions can be carried out through FFT algorithm which is well known for its higher efficiency. The approach was further improved by reformulating the simulation formulas where the order in which the summation operations are executed is imposed.

In recent years, the Fourier domain representation of sparse signals has been very attractive. Sparse fast Fourier transform (or sparse FFT) is a new technique which computes the Fourier transform in a compressed way, using only a subset of the input data. Sparse FFT computes the desired transform in sublinear time, which means in an amount of time that is smaller than the size of data. In big data problems and medical imaging to reduce the time that patient spends in MRI machine, FFT algorithm is not ‘fast’ enough anymore; therefore, the concept of sparse FFT is very important. Similar to compressed sensing, sparse FFT algorithm computes just the important components in the frequency domain in sublinear time. In this work, sparse FFT algorithm is studied and implemented on MATLAB and its performance is compared with Ann Arbor FFT. A filter is used to hash the frequencies in the n dimensional frequency-sparse signal into B bins, where $$B=n/16$$ . The filter is used for analyzing an important fraction of the whole signal, and therefore, instead of computing n point FFT, B point FFT is computed, and this results in a faster Fourier transform. The probability of success of the implemented algorithm is investigated for noiseless and noisy signals. It is deduced that as the sparsity increases, the probability of perfect transform also increases. If the performances of the algorithm in both cases are compared, it is clearly seen that the performances degrade when there is noise. Therefore, it can be concluded that the algorithm should be improved especially for noisy considerations. The solvability boundary for a constant probability of error is deducted and added to give insight for future studies.

The discrete Fourier transform (DFT) is the standard tool for spectral analysis in digital signal processing, typically computed using the fast Fourier transform (FFT). However, for real-time applications that require recalculating the DFT at each sample or over only a subset of the N center frequencies of the DFT, the FFT is far from optimal.

The match-count problem on strings is a problem of counting the matches of characters for every possible gap of the starting positions between two strings. This problem for strings of lengths m and n ( m ≤ n ) over an alphabet of size σ is classically solved in O ( σ n log ⁡ m ) time using the algorithm based on the convolution theorem and a fast Fourier transform (FFT). This paper provides a method to reduce the number of computations of the FFT required in the FFT-based algorithm. The algorithm obtained by the proposed method still needs O ( σ n log ⁡ m ) time, but the number of required FFT computations is reduced from 3 σ to 2 σ + 1 . This practical improvement of the processing time is also applicable to other algorithms based on the convolution theorem, including algorithms for the weighted version of the match-count problem.

The Clifford Fourier transform (CFT) can be applied to both vector and scalar fields. However, due to problems with big data, CFT is not efficient, because the algorithm is calculated in each semaphore. The sparse fast Fourier transform (sFFT) theory deals with the big data problem by using input data selectively. This has inspired us to create a new algorithm called sparse fast CFT (SFCFT), which can greatly improve the computing performance in scalar and vector fields. The experiments are implemented using the scalar field and grayscale and color images, and the results are compared with those using FFT, CFT, and sFFT. The results demonstrate that SFCFT can effectively improve the performance of multivector signal processing.

We present a fast 3-D scattering center extraction algorithm using the shooting and bouncing ray technique. The proposed algorithm generates a 3-D inverse synthetic aperture radar image from which a set of 3-D scattering centers is then extracted using the CLEAN algorithm. In the conventional extraction algorithm, computation time is improved using the fast Fourier transform (FFT)-based scheme. However, the memory requirement is greatly increased because of the high oversampling required to mitigate the interpolation error. Evaluation of memory-time tradeoffs indicates that the conventional algorithm is still too time consuming given the constraints of practical memory. Thus, a modified FFT-based scheme is proposed to improve computation time without increasing the memory requirement. Through modifying the ray spread function, the distortion from the interpolation error is mitigated without the use of high oversampling. Implementation based on the proposed FFT-based scheme accelerates the image formation process significantly. Numerical simulations of realistic targets are presented to demonstrate the performance of the proposed algorithm.

This paper presents a frequency interleaving method to correct non-ideal characteristics of wideband signal generators. By effectively segmenting a discrete Fourier transform dataset into frequency-interleaving blocks, the proposed method is computationally more efficient than the conventional method based on Fast Fourier Transform (FFT). In cases the quality of frequency analysis can be improved by zero padding such as characterizing impulse responses, this method is effective because it is possible to interleave two or more FFT results to achieve better frequency resolution. To verify the proposed method, an arbitrary signal generator was tested with a 64 quadrature-amplitude-modulation waveform. Compared with the original signal quality, the proposed method improves the in-band signal-to-noise ratio by 9 dB, and the error-vector magnitude decreases from 2.1%rms to 0.78%rms. In all cases, the computation speed was faster than that of conventional FFT.

This paper presents the design and implementation of memory-based fast Fourier transform (FFT) processors with generalized efficient, conflict-free address schemes. We unified the conflict-free address schemes of three different FFT lengths, including the single-power points, the common nonsingle-power points, and the nonsingle-power points applied with a prime factor algorithm. Though the three cases differ in terms of decomposition, they are all compatible with memory-based architecture by the way of the proposed address schemes. Moreover, the decomposition algorithm utilizes a method, named high-radix–small-butterfly (HRSB), to decrease the computation cycles and eliminate the complexity of the processing engine. In addition, an efficient index generator, a simplified multipath delay commutator engine, and a unified Winograd Fourier transform algorithm butterfly core were also designed. We designed two FFT examples in long-term evolution system to verify the availability of the address scheme, including a 2n (128–2048)-point FFT unit and a 35 different point (12–1296) DFT unit. Compared with previous works with similar address schemes, this paper supports more generalized lengths and achieves more flexible throughput.

Multiple sequence alignment (MSA) is the most common task in bioinformatics. Multiple alignment fast Fourier transform (MAFFT) is the fastest MSA program among those the accuracy of the resulting alignments can be comparable with the most accurate MSA programs. In this paper, we modify the correlation computation scheme of the MAFFT for further efficiency improvement in three aspects. First, novel complex number based amino acid and nucleotide expressions are utilized in the modified correlation. Second, linear convolution with a limitation is proposed for computing the correlation of amino acid and nucleotide sequences. Third, we devise a fast Fourier transform (FFT) algorithm for computing linear convolution. The FFT algorithm is based on conjugate pair split-radix FFT and does not require the permutation of order, and it is new as only real parts of the final outputs are required. Simulation results show that the speed of the modified scheme is 107.58 to 365.74 percent faster than that of the original MAFFT for one execution of the function Falign() of MAFFT, indicating its faster realization.

Discrete Fourier transform (DFT) is the basic means of spectrum analysis in the field of digital signal processing, and the fast Fourier transform (FFT) has become the most popular algorithm which decreases the computational complexity from quadratical to linearithmic. However, engineers are often challenged to detect a single or just a few of the frequency components. For this kind of sparse spectrum analysis, the FFT no longer has advantage because it always computes all the frequency components. This paper proposes a recursive single-bin DFT (RSB-DFT) algorithm to compute one specific frequency spectrum, whose theoretical derivation is elaborated and implementation steps are given as a flow diagram. A 16-point RSB-DFT calculation example is also given to exhibit computation process of the algorithm. An application example for bioimpedance spectroscopy (BIS) measurement demonstrates that the proposed RSB-DFT algorithm can compute specific single spectral lines accurately. The computation efficiency of the proposed RSB-DFT algorithm is demonstrated as the highest compared with the DFT, FFT, Goertzel algorithm, which means that the RSB-DFT algorithm has the potential to become an alternative and efficient tool for sparse spectrum analysis.

For the discrete Fourier transform with respect to the system of characters of a local field with positive characteristic, we propose a fast algorithm. We find the complexity of the algorithm.

The modular multiplication operation is the most time-consuming operation for number-theoretic cryptographic algorithms involving large integers, such as RSA and Diffie-Hellman. Implementations reveal that more than 75 percent of the time is spent in the modular multiplication function within the RSA for more than 1,024-bit moduli. There are fast multiplier architectures to minimize the delay and increase the throughput using parallelism and pipelining. However such designs are large in terms of area and low in efficiency. In this paper, we integrate the fast Fourier transform (FFT) method into the McLaughlin’s framework, and present an improved FFT-based Montgomery modular multiplication (MMM) algorithm achieving high area-time efficiency. Compared to the previous FFT-based designs, we inhibit the zero-padding operation by computing the modular multiplication steps directly using cyclic and nega-cyclic convolutions. Thus, we reduce the convolution length by half. Furthermore, supported by the number-theoretic weighted transform, the FFT algorithm is used to provide fast convolution computation. We also introduce a general method for efficient parameter selection for the proposed algorithm. Architectures with single and double butterfly structures are designed obtaining low area-latency solutions, which we implemented on Xilinx Virtex-6 FPGAs. The results show that our work offers a better area-latency efficiency compared to the state-of-the-art FFT-based MMM architectures from and above 1,024-bit operand sizes. We have obtained area-latency efficiency improvements up to 50.9 percent for 1,024-bit, 41.9 percent for 2,048-bit, 37.8 percent for 4,096-bit and 103.2 percent for 7,680-bit operands. Furthermore, the operating latency is also outperformed with high clock frequency for length-64 transform and above.

This paper presents a high-throughput lowcomplexity 512-point eight-parallel mixed-radix multipath delay feedback (MDF) fast Fourier transform (FFT) processor architecture for orthogonal frequency division multiplexing (OFDM) applications. To decrease the number of twiddle factor (TF) multiplications, a mixed-radix 2 4 /2 3 FFT algorithm is adopted. Moreover, a dual-path shared canonical signed digit (CSD) complex constant multiplier using a multi-layer scheme is proposed for reducing the hardware complexity of the TF multiplication. The proposed FFT processor is implemented using TSMC 90-nm CMOS technology. The synthesis results demonstrate that the proposed FFT processor can lead to a 16% reduction in hardware complexity and higher throughput compared to conventional architectures.

In this paper, an optimal time-distributed fast Fourier transform algorithm and a time-distributed inverse fast Fourier transform (OTD-FFT/TD-IFFT) algorithm are proposed. This work is motivated by the need to implement FFT/IFFT online on general microprocessors (e.g., Intel’s x86 microprocessors) in control applications and signal processing, for example, online implementation of frequency domain iterative learning control (FD-ILC) techniques. In these applications, the conventional FFT algorithm executes all the calculations within one single sampling period, thereby, becoming the bottleneck in online implementations of signal processing and control algorithms. In the proposed OTD-FFT technique, the FFT computation of an online sampled data sequence is optimally distributed among all the sampling periods without increasing the total computational complexity, arriving at the minimal per-sampling-period computational complexity. As a result, the entire Fourier transformed sequence is obtained without latency. The proposed approach is extended to online IFFT computation, and then applied to online FD-ILC implementation. The computational complexity analysis shows that by using the proposed approach, the per-sampling-period computational complexity is substantially reduced. The efficacy of the proposed OTD-FFT/TD-FFT for online implementation of FD-ILC technique is demonstrated through experiments of high-speed trajectory tracking on a piezoelectric actuator.

In this letter, a hybrid algorithm based on the genetic algorithm (GA) and modified iterative Fourier transform (MIFT) technique called HGAMIFT is proposed for large thinned array synthesis. By employing a perturbation mechanism, the MIFT can achieve a better solution in terms of the peak sidelobe level when compared to the iterative Fourier transform technique. Moreover, a control factor to determine the proportion of individuals from GA and MIFT as well as the crossover and mutation rate is introduced to help the HGAMIFT maintain the diversity of population in the early phase while avoiding stagnation in the late phase. Thus, a resulting enhanced search ability and fast convergence velocity can be obtained simultaneously. Several thinned arrays that comprise different array sizes and aperture shapes have been synthesized, which validate the superior performance of the proposed algorithm.

Two-dimensional fast Fourier transform (FFT) for image processing and filtering is widely used in modern digital image processing systems. This paper concerns the possibility of using a modification of two-dimensional FFT with an analog of the Cooley---Tukey algorithm, which requires a smaller number of complex addition and multiplication operations than the standard method of calculation by rows and columns.

This note provides a self-contained introduction to Rader's fast Fourier transform (FFT). We start by explaining the need for an additional type of FFT. The properties of the multiplicative group o...

A multidimensional sparse fast Fourier transform algorithm is introduced via generalizations of key concepts used in the one-dimensional (1-D) sparse Fourier transform algorithm. It is shown that permutation parameters are of key importance and should not be chosen randomly but instead can be optimized. A connection is made between the sparse Fourier transform algorithm and lattice theory, thus establishing a rigorous understanding of the effect of the permutations on the algorithm performance. Lattice theory is then used to optimize the set of parameters to achieve a more robust and better performing algorithm. Other algorithms using pseudorandom spectrum permutation can also benefit from the methods developed in this paper. The contributions address the case of the exact $k$ -sparse Fourier transform but the underlying concepts can be applied to the general case of finding a $k$ -sparse approximation of the Fourier transform of an arbitrary signal. Simulations illustrate the efficiency and accuracy of the proposed algorithm. The optimizations of the parameters and the improved performance are shown in simulations for the 2-D case where worst case and average case peak signal-to-noise ratio (PSNR) improves by several decibels.

Discrete Fourier transform (DFT) is an important transformation technique in signal processing tasks. Due to its ultrahigh computing complexity as $O(\!N^{\!2}\!)$ , $N$ - point DFT is usually implemented in the format of fast Fourier transformation (FFT) with the complexity of $O(N\log N)$ . Despite this significant reduction in complexity, the hardware cost of the multiplication-intensive $N$ - point FFT is still very prohibitive, particularly for many large-scale applications that require large $N$ . This brief, for the first time , proposes high-accuracy low-complexity scaling-free stochastic DFT/FFT designs. With the use of the stochastic computing technique, the hardware complexity of the DFT/FFT designs is significantly reduced. More importantly, this brief presents the scaling-free stochastic adder and the random number generator sharing scheme, which enable a significant reduction in accuracy loss and hardware cost. Analysis results show that the proposed stochastic DFT/FFT designs achieve much better hardware performance and accuracy performance than state-of-the-art stochastic design.

Real-valued Fast Fourier Transform (FFT) plays an important role in today’s digital world because of the fact that most of the signals contain real values. The FFT computation of real signals using conventional techniques requires more hardware space with high power consumption, which is the most important task for a researcher while designing VLSI architectures. This can be eradicated by clearly analysing the symmetric property of the real-valued signals. In this paper, we have adopted the symmetric property and designed an efficient pipelined architecture for 16-point DIF FFT. The pipeline scheme reduce the processing time at the cost of some registers and in order to contribute efficiently for power reduction we have modified the complex multiplier with reduced internal real multipliers which are in turn replaced by an modified canonic signed digit multiplier (CSDM) with resource-sharing technique. The complete module is synthesised and simulated using Xilinx ISE 14.1 with the target device is ...

Fast Fourier transform (FFT) accelerator and Coordinate rotation digital computer (CORDIC) algorithm play important roles in signal processing. We propose a configurable floating-point FFT accelerator based on CORDIC rotation, in which twiddle direction prediction is presented to reduce hardware cost and twiddle angles are generated in real time to save memory. To finish CORDIC rotation efficiently, a novel approach in which segmented-parallel iteration and compress iteration based on CSA are presented and redundant CORDIC is used to reduce the latency of each iteration. To prove the efficiency of our FFT accelerator, four FFT accelerators are prototyped into a FPGA chip to perform a batch-FFT. Experimental results show that our structure, which is composed of four butterfly units and finishes FFT with the size ranging from 64 to 8192 points, occupies 33230(3%) REGs and 143006(30%) LUTs. The clock frequency can reach 122MHz. The resources of double-precision FFT is only about 2.5 times of single-precision while the theoretical value is 4. What's more, only 13331 cycles are required to implement 8192-points double-precision FFT with four butterfly units in parallel.

Hybrid fast Fourier transform Adaptive LINear Element (FFT-ADALINE) algorithm for fast and accurate estimation of harmonics is proposed in this study. The FFT method can perform fast conversion from time domain to frequency domain, but it cannot respond immediately to any change of the measured harmonics due to the utilisation of buffer. Meanwhile, ADALINE has better capability to respond immediately due to its learning ability, but its settling time is about two cycles of the measurement signal. In the proposed method, both of the aforementioned algorithms are combined for harmonic estimation where it is able to respond immediately to any change of the measured harmonics and the settling time is reduced to half cycle of the measurement signal. The theory of the proposed algorithm is the application of FFT with weights updating rule to reduce the error of ADALINE instantaneously. The robustness of the proposed method is simulated via MATLAB Simulink. The validity of the simulation work is further proven by the experimental work, which has been done with Chroma programmable AC source model 6590 and non-linear load operations. The proposed algorithm operates in good and accurate performance with the settling time is within half cycle.

In this communication, the computation of the perturbation-based electric field integral equation of the form ${R^{n-1},~n = 0, 1, 2, \ldots ,}$ is accelerated by using fast Fourier transform (FFT) technique. As an effective solution of the low-frequency problem, the perturbation method employs the Taylor expansion of the scalar Green’s function in free space. However, multiple impedance matrices have to be solved at different frequency orders, and the computational cost becomes extremely high, especially for large-scale problems. Since the perturbed kernels still satisfy Toeplitz property on the uniform Cartesian grid, the FFT based on Lagrange interpolation can be well incorporated to accelerate the multiple matrix vector products. Because of the nonsingularity property of high-order kernels when $n\geq 1$ , we do not need to do any near field amendment. Finally, the efficiency of the proposed method is validated in an iterative solver with numerical examples.

This brief presents a new type of fast Fourier transform (FFT) hardware architectures called serial commutator (SC) FFT. The SC FFT is characterized by the use of circuits for bit-dimension permutation of serial data. The proposed architectures are based on the observation that, in the radix-2 FFT algorithm, only half of the samples at each stage must be rotated. This fact, together with a proper data management, makes it possible to allocate rotations only every other clock cycle. This allows for simplifying the rotator, halving the complexity with respect to conventional serial FFT architectures. Likewise, the proposed approach halves the number of adders in the butterflies with respect to previous architectures. As a result, the proposed architectures use the minimum number of adders, rotators, and memory that are necessary for a pipelined FFT of serial data, with 100% utilization ratio. Funding Agencies|Swedish ELLIIT Program

A novel method is presented for fast convolution of a pair of probability mass functions defined on a finite lattice with guaranteed accuracy of all computed values. This method, called aFFT-C (accurate FFT convolution), utilizes the Fast Fourier Transform (FFT) for the gain in speed, but relying on a rigorous analysis of the propagation of roundoff error, it can detect and circumvent the accumulation of this numerical error that is otherwise inherent to the Fourier transform. In the worst case scenario aFFT-C's execution time is on par with the accurate naive convolution but in a typical application it is comparable with a direct FFT-based convolution (FFT-C). The properties of the proposed algorithm are demonstrated both theoretically and empirically.

The modern real time applications like orthogonal frequency division multiplexing and etc., demand high performance fast Fourier transform (FFT) design with less area and clock cycles. This paper proposes efficient FFT VLSI architectures using folded/parallel implementation. In the proposed folded FFT architecture, the number of cycles required to complete the operation is less than single path delay feedback (SDF)/multi-path delay commutator (MDC) architectures. In the proposed parallel FFT architecture, N-point FFT is implemented by using one N/2-point FFT without much extra hardware. Both the proposed architectures are implemented for radix-2, 22, and 4 using 45 nm technology library. The proposed parallel architecture achieves 56.7% and 40.6% of area reduction as compared with the existing parallel architecture based 16-point radix-2 and radix-22 DIF FFTs respectively. The proposed folded architecture achieves 65.5%, 51.1%, and 35.8% of worst path delay reduction as compared with the existing SDF based 16-point radix-2, radix-22, and radix-4 DIF FFTs respectively.

Discrete Fourier transform (DFT) finds various applications in signal processing, image processing, artificial intelligent, and fuzzy logic etc. DFT is often computed efficiently with Fast Fourier transform (FFT). The modified split radix FFT (MSRFFT) algorithm implements a length-N=2 m DFT achieving a reduction of arithmetic complexity compared to split-radix FFT (SRFFT). In this paper, a simplified algorithm is proposed for the MSRFFT algorithm, reducing the number of real coefficients evaluated from 5/8N − 2t o 15/32N − 2 and the number of groups of decomposition from 4 to 3. A implementation approach is also presented. The approach makes data-path of the MSRFFT regular similar to that of the radix-2 FFT algorithm. The experimental results show that (1) MSRFFT consumes less time on central processing units (CPUs) with sufficient cache than existing algorithms; (2) the proposed implementation method can save execution time on CPUs and general processing units (GPUs).

This paper presents a set of novel two-parallel pipelined fast Fourier transform architectures for discrete Fourier transform computation of real-valued signal. The previous approaches of designing real-valued fast Fourier transform (RFFT) architectures are the attempts made to make the data path real. Some of the previous designs have partial real data paths (only first two stages are real), whereas the other designs have complete real data-paths, but reordering registers are required to bring the real and imaginary parts in parallel. Hence, these approaches reduce the number of registers and butterflies only to some extent in the RFFT design. In the proposed designs, feedback-based scheduling structures are introduced, which reduce the number of registers to half in several stages when compared with the previously known designs. Therefore, the proposed designs require 30% less area and 31.5% less power than the prior designs.

An algorithm for constructing a model of the global geoid with zero-order approximation accuracy is considered. The algorithm is based on the one-dimensional spherical fast Fourier transform (FFT). It is 2.5 orders faster than those using the conventional discrete transform, and four orders, as compared with those using the numerical integration method. The algorithm was tested on the new Earth gravitational model EGM2008 published by the U.S. National Geospatial-Intelligence Agency (NGA).

A time-domain sequence is converted into an equivalent frequency-domain sequence using discrete Fourier transform. The reverse operation converts a frequency-domain sequence into an equivalent time- domain sequence using inverse discrete Fourier transform. Based on the discrete Fourier transform. Fast Fourier transform (FFT) is an effective algorithm with few computations. FFT is used in everything from broadband to 3G and Digital TV to radio LAN"s. To improve its architecture different efficient algorithms are developed. This paper gives an overview of the work done by a different FFT processor previously. The comparison of different architecture is also discussed.

Nowadays, many applications require simultaneous computation of multiple independent fast Fourier transform (FFT) operations with their outputs in natural order. Therefore, this brief presents a novel pipelined FFT processor for the FFT computation of two independent data streams. The proposed architecture is based on the multipath delay commutator FFT architecture. It has an $N/2$ -point decimation in time FFT and an $N/2$ -point decimation in frequency FFT to process the odd and even samples of two data streams separately. The main feature of the architecture is that the bit reversal operation is performed by the architecture itself, so the outputs are generated in normal order without any dedicated bit reversal circuit. The bit reversal operation is performed by the shift registers in the FFT architecture by interleaving the data. Therefore, the proposed architecture requires a lower number of registers and has high throughput.

A novel method for computing the discrete Fourier transform (DFT) over a finite field based on the Goertzel-Blahut algorithm is described. The novel method is currently the best one for computing the DFT over even extensions of the characteristic two finite field, in terms of multiplicative complexity.

This brief presents a hybrid structure to effectively compute the variable-length Fourier transform by employing the recursive and radix-22 fast algorithm. After applying a hardware-sharing scheme to both fast algorithms, the proposed method not only improves the drawback of higher hardware cost in implementation but also retains the regular and flexible nature of recursive discrete Fourier transform (RDFT). The proposed hardware accelerator only costs four real multipliers and ten real adders with a greater reduction (86.7% and 66.7%, respectively) than Kim et al. 's design. In addition, the number of multiplications and additions for 256-point DFT computations can be reduced by 38.6% and 70%, respectively, compared to Lai et al. 's recent approach. For accuracy analysis, the SNR value of the proposed design, at least, is 4 dB higher than the other RDFT designs. Considering a whole evaluation, a very-large-scale integration chip design was further fabricated using TSMC 0.18- $\mu\mbox{m}$ 1P6M CMOS process. The core size was only 660 × 660 $\mu\mbox{m}^2$ , and the measured power consumption was 8.8 mW @ 25 MHz. The result shows that the proposed chip included data memory is 1.38 times the computational efficiency per unit area of Lai et al. 's work. Therefore, it will be the state-of-the-art RDFT processor in the application of various variable-transform-length digital signal processing issues.

For synthetic aperture radar (SAR), most conventional algorithms provide a good performance in ground moving target imaging based on Fourier transform (FT). However, when multiple moving targets with the close centres exist, the conventional algorithms may suffer from the performance degradation since the spectra resolution of FT may be limited by the time samples. To address this issue, a super-resolution motion parameter estimation algorithm is proposed in this study. First, Keystone transform is applied to correct the linear range walk. Then the range curvature is compensated by the matched function with respect to the platform velocity. After performing the compensation of linear range walk and range curvature, the energy of a ground moving target is focused on one range cell, and then a first-order discrete polynomial-phase transform is applied to transform the quadratic phase signal into a single tone. After applying the smoothing technique to construct the covariance matrix of full rank, the multiple signal classification algorithm is utilised to estimate the target cross- and along-track velocities, which can significantly improve the motion parameter resolution performance compared with the FFT-based algorithms. The real SAR data processing results are used to validate the effectiveness and feasibility of the proposed algorithm.