Parallel FFT Algorithm on Computer Clusters

DFT is widely applied in the field of signal process and others. Most present rapid ways of calculation are either based on paralleled computers connected by such particular systems like butterfly network, hypercube etc; or based on the assumption of instant transportation, non-conflict communication, complete connection of paralleled processors and unlimited usable processors. However, the delay of communication in the system of information transmission cannot be ignored. This paper works on the following aspects： instant transmission, dispatching missions, and the path of information through the communication link in the computer cluster systems; layout of the dynamic FFT algorithm under the different structures of computer clusters.

A Precise Algorithm for Non-Integer Harmonics Analysis Based on FFT and Neural Network

By means of an arificial neural network (ANN) model, higher measurement accuracy of integer harmonics can be obtained. Combining the windowed fast Fourier transform (FFT) algorithm with the improved ANN model, we present a new precise algorithm for non-integer harmonics analysis. According to the result obtained from the Hanning-windowed FFT algorithm, we choose the initial values of orders of harmonics for the neural network. Through such processing, the time of iterations is shortened and the convergence rate of neural network is raised thereby. The simulation results show that close non-integer harmonics can be separated from a signal with higher accuracy and better real-time by using the algorithm presented in the paper. Key words fast Fourier transform (FFT) - artificial neural network (ANN) - Hanning-window - harmonics analysis CLC number TM 935 Foundation item: Supported by the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of China (2001-182) and the Science Foundation of Naval University of Engineering(HGDJJ03001).Biography: WANG Gong-bao (1962-), male, Professor, research direction: artificial neural network, wavelet analysis and their applications to signal processing in electric power systems.

A GENERAL IN-PLACE AND IN-ORDER PRIME FACTOR FFT ALGORITHM

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,

Computational Performances of OFDM Using Different FFT Algorithms

In this paper, an intuitive comparison of the computational performance of orthogonal frequency division multiplexing (OFDM) system has been made in terms of complex calculations required using different Fourier transform techniques. The different transform techniques are introduced such as discrete Fourier transform (DFT) and various types of fast Fourier transform (FFT) as 2-radix FFT, 4-radix FFT etc. and the very recent very fast Fourier transform (VFFT). With intuitive mathematical analysis, it has been shown that with the reduced complexity that VFFT can offer, OFDM performance can be greatly improved in terms of calculations needed.

Enhanced Wideband Frequency Estimation via FFT: Leveraging Polynomial Interpolation and Array Indexing

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.

An Accurate FFT-Based Algorithm for Bermudan Barrier Option Pricing

An efficient and accurate numerical method, which is called the CONV method, was proposed by Lord et al in [1] to price Bermudan options. In this paper, this method is applied to price Bermudan barrier options in which the monitored dates may be many times more than the exercise dates. The corresponding algorithm is presented to practical option pricing. Numerical experiments show that this algorithm works very well for different exponential Lévy asset models.

Combining Cubic Spline Interpolation and Fast Fourier Transform to Extend Measuring Range of Reflectometry

The reflectometry is a common method used to measure the thickness of thin films. Using a conventional method,its measurable range is limited due to the low resolution of the current spectrometer embedded in the reflectometer.We present a simple method, using cubic spline interpolation to resample the spectrum with a high resolution,to extend the measurable transparent film thickness. A large measuring range up to 385 m in optical thickness is achieved with the commonly used system. The numerical calculation and experimental results demonstrate that using the FFT method combined with cubic spline interpolation resampling in reflectrometry, a simple,easy-to-operate, economic measuring system can be achieved with high measuring accuracy and replicability.

Cardiac arrhythmias detection in an ECG beat signal using fast fourier transform and artificial neural network

Cardiac Arrhythmias shows a condition of abnor-mal electrical activity in the heart which is a threat to humans. This paper presents a method to analyze electrocardiogram (ECG) signal, extract the fea-tures, for the classification of heart beats according to different arrhythmias. Data were obtained from 40 records of the MIT-BIH arrhythmia database (only one lead). Cardiac arrhythmias which are found are Tachycardia, Bradycardia, Supraventricular Tachycardia, Incomplete Bundle Branch Block, Bundle Branch Block, Ventricular Tachycardia. A learning dataset for the neural network was obtained from a twenty records set which were manually classified using MIT-BIH Arrhythmia Database Directory and docu- mentation, taking advantage of the professional experience of a cardiologist. Fast Fourier transforms are used to identify the peaks in the ECG signal and then Neural Networks are applied to identify the diseases. Levenberg Marquardt Back-Propagation algorithm is used to train the network. The results obtained have better efficiency then the previously proposed methods.

A fast acquisition method of DSSS signals using differential decoding and fast Fourier transform

In low earth orbit (LEO) satellite or missile communication scenarios, signals may experience extremely large Doppler shifts and have short visual time. Thus, direct sequence spread spectrum (DSSS) systems should be able to achieve acquisition in a very short time in spite of large Doppler frequencies. However, the traditional methods cannot solve it well. This work describes a new method that uses a differential decoding technique for Doppler mitigation and a batch process of FFT (fast Fourier transform) and IFFT (invert FFT) for the purpose of parallel code phase search by frequency domain correlation. After the code phase is estimated, another FFT process is carried out to search the Doppler frequency. Since both code phase and Doppler frequency domains are searched in parallel, this architecture can provide acquisition fifty times faster than conventional FFT methods. The performance in terms of the probability of detection and false alarm are also analyzed and simulated, showing that a signal-to-noise ratio (SNR) loss of 3 dB is introduced by the differential decoding. The proposed method is an efficient way to shorten the acquisition time with slightly hardware increasing.

Fast Fourier Transform of Multi-Assets Options under Economic Recession Induced Uncertainties

A Fast Fourier transform approach has been presented by Carr & Madan (2009) on a single underlying asset. In this current research paper, we present fast Fourier transform algorithm for the valuation of Multi-asset Options under Economic Recession Induced Uncertainties. The issue of multi-dimension in both finite and infinite case of Options is part of the focus of this research. The notion of economic recession was incorporated. An intuition behind the introduction of recession induced volatility uncertainty is revealed by huge volatility variation during the period of economic recession compared to the period of recession-free. Nigeria economic recession outbreak in 2016 and its effects on the uncertainty of the payoffs of Nigeria Stocks Exchange (NSE) among other investments was among the motivating factors for proposing economic recession induced volatility in options pricing. The application of the proposed Fast Fourier Transform algorithm in handling multi-assets options was shown. A new result on options pricing was achieved and capable of yielding efficient option prices during and out of recession. Numerical results were presented on assets in 3-dimensions as an illustration taking Black Scholes prices as a bench mark for method effectiveness comparison. The key findings of this research paper among other crucial contributions could be seen in computational procedure of options valuation in multi-dimensions and uncertainties in options payoffs under the exposure of economic recession.

Two-dimensional self-adapting fast Fourier transform algorithm for nanoparticle sizing by ultrafast image-based dynamic light scattering

In nanoparticle sizing using the ultrafast image-based dynamic light scattering (UIDLS)method,larger impurities and dark noise from the complementary metal-oxide-semiconductor (CMOS)detector affect measurement accuracy.To solve this problem,a two-dimensional self-adapting fast Fourier transform (2D-SAFFT)algorithm is proposed for UIDLS.Dynamic light scattering images of nanoparticles are processed using 2D fast Fourier transforms,and a high-frequency threshold and a low-frequency threshold are then set using the self-adapting algorithm to eliminate the effects of the dark noise of the CMOS detector and the impurities.The signals caused by the dark noise of the CMOS detector and the impurities are cut off using the high-frequency threshold and the low-frequency threshold.The signals without the high- and low-frequency components are then processed again using an inverse Fourier transform to obtain new images without the dark noise and impurities signals.The mean diameters of the measured nanoparticles can be obtained from images obtained using UIDLS.Five standard latex nanoparticles (46,100, 203,508,994nm)and commercial nanoparticles (antimony-doped tin oxide,indium tin oxide,TWEEN- 80,nano-Fe,and nano-Al2O3)were measured using this new method.Results show that 2D-SAFFT can effectively eliminate the effects of dark noise from the CMOS detector and the impurities.

Performance of Continuous Wavelet Transform over Fourier Transform in Features Resolutions

This study presents a comparative analysis of two image enhancement techniques, Continuous Wavelet Transform (CWT) and Fast Fourier Transform (FFT), in the context of improving the clarity of high-quality 3D seismic data obtained from the Tano Basin in West Africa, Ghana. The research focuses on a comparative analysis of image clarity in seismic attribute analysis to facilitate the identification of reservoir features within the subsurface structures. The findings of the study indicate that CWT has a significant advantage over FFT in terms of image quality and identifying subsurface structures. The results demonstrate the superior performance of CWT in providing a better representation, making it more effective for seismic attribute analysis. The study highlights the importance of choosing the appropriate image enhancement technique based on the specific application needs and the broader context of the study. While CWT provides high-quality images and superior performance in identifying subsurface structures, the selection between these methods should be made judiciously, taking into account the objectives of the study and the characteristics of the signals being analyzed. The research provides valuable insights into the decision-making process for selecting image enhancement techniques in seismic data analysis, helping researchers and practitioners make informed choices that cater to the unique requirements of their studies. Ultimately, this study contributes to the advancement of the field of subsurface imaging and geological feature identification.

NOVEL HIGH-SPEED FPGA-BASED FFT PROCESSOR

A novel architecture for computing the fast Fourier transform ( FFT ) on programmable devices is presented.To improve the system operation speed , a hybrid parallel FFT algorithm is used.Results indicate that the use of an 8×8parallel structure for realizing the 64-point FFT leads to a 8times higher processing speed compared with its counterparts employing other series of techniques.

使用特殊复数系统的基-6 FFT算法

使用非直角坐标系下特殊形式的复数系统 ,给出了一种基 6快速傅里叶变换算法 .其中 6点离散傅里叶变换不需要实数乘法 .最后 ,将其运算量与直角坐标系下的标准基 6、素因子基 6、标准基 3、Dubois等给出的新基 3算法和基 2、基

流水并行1-D FFT地址映射算法

讨论了2个流水蝶形单元并行的地址映射算法.由于FFT级间数据读写关系复杂,实现每次并行执行2个蝶式运算的地址产生非常复杂.通过对基2数据流图的改造,将存储器分为2个存储体,各级每个蝶式运算的1对操作数位于同一存储体,并行执行的2对操作数位于不同存储体相同地址,计算结果按原址写回,同时每次计算所需的2个旋转因子地址间存在一定关系,因而可用1个地址产生单元,实现2条流水线并行所需的操作数及旋转因子的并行访问.本地址产生单元易于实现,资源需求少、延时较小,且可使蝶式计算循环次数减少一半.

ASIC Design of Floating-Point FFT Processor

An application specific integrated circuit (ASIC) design of a 1024 points floating-point fast Fourier transform(FFT) processor is presented. It can satisfy the requirement of high accuracy FFT result in related fields. Several novel design techniques for floating-point adder and multiplier are introduced in detail to enhance the speed of the system. At the same time, the power consumption is decreased. The hardware area is effectively reduced as an improved butterfly processor is developed. There is a substantial increase in the performance of the design since a pipelined architecture is adopted, and very large scale integrated (VLSI) is easy to realize due to the regularity. A result of validation using field programmable gate array (FPGA) is shown at the end. When the system clock is set to 50 MHz, 204.8 μs is needed to complete the operation of FFT computation.

Fine Doppler shift acquisition algorithm for BeiDou software receiver by a look-up table

The BeiDou software receiver uses the fast Fourier transform(FFT)to perform the acquisition.The Doppler shift estimation accuracy should be less than 500 Hz to ensure satellite signals to enter a locked state in the tracking loop.Since the frequency step is usually 500 Hz or larger,the Doppler shift estimation accuracy cannot guarantee that satellite signals are brought into a stable tracking state.The straightforward solutions consist in increasing the sampling time and using zero-padding to improve the frequency resolution of the FFT.However,these solutions intensify the complexity and amount of computation.The contradiction between the acquisition accuracy and the computational load leads us to research for a more simple and effective algorithm,which achieves fine acquisition by a look-up table.After coarse acquisition using the parallel frequency acquisition(PFA)algorithm,the proposed algorithm optimizes the Doppler shift estimation through the look-up table method based on the FFT results to improve the acquisition accuracy of the Doppler shift with a minimal additional computing load.When the Doppler shift is within the queryable range of the table,the proposed algorithm can improve the Doppler shift estimation accuracy to 50 Hz for the BeiDou B1I signal.

基于FPGA的4k点基-16 FFT模块的实现

针对高速实时处理的要求,提出了4096点快速傅立叶变换(FFT)模块在现场可编程门阵列(FPGA)中的设计和实现。在运算模块中,基于按频率抽取基-4算法提出了一种新型的基-16蝶型算法,并采用八级流水结构和四路转换器来实现。本文采用块浮点和循环存储结构,避免了溢出和节省了大量的硬件资源。实验结果表明,该方法在保证了运算精度和实现复杂度的同时,使运算速度相对于基-4算法提高了1倍。

AN FFT-BASED SELF-SIMILAR TRAFFIC GENERATOR

The self similarity of the network traffic has great influences on the performance. But there are few analytical or even numerical solutions for such a model. So simulation becomes the most efficient method for research. Fractal Gaussian noise (FGN) is the most popularly used self similar model. This paper presented an FGN generator based on fast Fourier transform (FFT). The study indicates that this algorithm is fairly fast and accurate.

Use of FFT in Protein Sequence Comparison under Their Binary Representations

The paper considers Voss type representation of amino acids and uses FFT on the represented binary sequences to get the spectrum in the frequency domain. Based on the analysis of this spectrum by using the method of inter coefficient difference (ICD), it compares protein sequences of ND5 and ND6 category. Results obtained agree with the standard ones. The purpose of the paper is to extend the ICD method of comparison of DNA sequences to comparison of protein sequences. The topic of discussion is to develop a novel method of comparing protein sequences. The main achievements of the work are that the method applied is completely new of its kind, so far as protein sequence comparison is concerned and moreover the results of comparison agree with the previous results obtained by other methods for the same category of protein sequences.