What is the updated version of FFT that does not require 2^n data points?

In summary, the updated version of FFT (Fast Fourier Transform) that does not require 2^n data points is the Bluestein's algorithm. It uses the chirp-z transform to decompose the input signal into two shorter signals, allowing for non-power-of-two input sizes. This algorithm has become popular due to its versatility and efficiency in handling various input sizes.
  • #1
Dr.D
2,412
721
Back when I studied the FFT (many years ago), it was always described as transforming a sample based on 2^n data points. More recently, I have read that this restriction has been removed. Can anyone point me to a good reference on this newer form, preferably something available free on the 'net since I have very limited library access? Any comments on this will be much appreciated.
 
Technology news on Phys.org
  • #3
The 2^n restriction is for a specific algorithm. The fftw and the accelerated libraries like cufft they different algorithms now which allow a wide combination of prime integers. In general I try use only numbers which combinations of powers of only 2,3 and 5.
 
  • #4
Thank you, Dr Transport & Chris.
 
  • #5


The updated version of FFT that does not require 2^n data points is called the "Fast Fourier Transform with Arbitrary Data Size" or FFTW. It was developed in the late 1990s and has been widely adopted in various software packages and libraries. FFTW allows for efficient computation of Fourier transforms on any size of data, not just 2^n. It uses a highly optimized algorithm that takes advantage of the data's size and structure, resulting in faster and more accurate calculations.

There are many resources available online for learning about FFTW, including documentation and tutorials on the official FFTW website (http://www.fftw.org/). Additionally, there are many open-source software packages and libraries that use FFTW, such as MATLAB, Python's NumPy, and GNU Octave, which also have documentation and resources available online. These resources can provide a deeper understanding of how FFTW works and how to implement it in various applications.

In conclusion, FFTW is the updated version of FFT that does not require 2^n data points and has become the standard for efficient computation of Fourier transforms. With its widespread adoption and availability of resources online, it is easy to learn and implement in various applications.
 

Related to What is the updated version of FFT that does not require 2^n data points?

What is a "Non 2^n sample based FFT"?

A "Non 2^n sample based FFT" is a type of Fast Fourier Transform algorithm used for signal processing and data analysis. It is specifically designed to work with sample sizes that are not a power of 2, which is a common requirement for other FFT algorithms.

How does a "Non 2^n sample based FFT" differ from traditional FFT algorithms?

A "Non 2^n sample based FFT" uses a different method of calculating the discrete Fourier transform compared to traditional FFT algorithms. It is able to handle sample sizes that are not a power of 2, while traditional FFT algorithms require the sample size to be a power of 2.

What are the advantages of using a "Non 2^n sample based FFT"?

The main advantage of using a "Non 2^n sample based FFT" is that it can work with sample sizes that are not a power of 2, which is a common requirement in real-world data analysis. This makes it a more versatile and practical option for many applications.

In what situations would a "Non 2^n sample based FFT" be useful?

A "Non 2^n sample based FFT" would be useful in situations where the sample size is not a power of 2, such as in audio and video processing, medical imaging, and climate analysis. It can also be useful for processing data in real time, as it does not require the sample size to be padded with zeros.

Are there any limitations to using a "Non 2^n sample based FFT"?

One limitation of using a "Non 2^n sample based FFT" is that it may not be as efficient as traditional FFT algorithms for sample sizes that are a power of 2. Additionally, it may be more complex to implement compared to traditional FFT algorithms.

Similar threads

Modern Digital Audio: Understanding Dither and Oversampling in Hi-Res Age"
    • Computing and Technology
Replies
9
Views
2K
Java Android Studio: Accessing SQLite Data In RecyclerView
    • Programming and Computer Science
Replies
1
Views
3K
Requesting suggestions for languages, libraries, and architectures for parallel (and sometimes non parallel) numerical and scientific computations
    • Programming and Computer Science
Replies
8
Views
2K
DMD is better without Ergodic Theory and Koopman Operators
    • Topology and Analysis
Replies
2
Views
2K
Solving ODEs with Forward Euler & Sampled Data Systems
    • Calculus and Beyond Homework Help
Replies
6
Views
1K
ABC reference frame synchronous generator modelling in Ltspice
    • Electrical Engineering
Replies
1
Views
1K
I Two recent tests of loop quantum gravity theory
    • Beyond the Standard Models
Replies
9
Views
770
I don't understand kind of program the instructions want
    • Engineering and Comp Sci Homework Help
Replies
4
Views
2K
Programs How good is this applied math program?
    • STEM Academic Advising
Replies
13
Views
2K
Current and Future AI Threats to Humanity and the Human Response
    • Computing and Technology
Replies
10
Views
2K

Hot Threads

Recent Insights

Back
Top