5
$\begingroup$

Suppose the input signal has 1024 samples, and I want to take a 1024-point FFT.

Can I instead take the 8-point FFT of the first 8 input samples then another 8 samples and continue this till the end?

Sorry I've just started with DSP.

$\endgroup$
1
  • $\begingroup$ Some intuition about why combining the results is not trivial: the "naïve" non-discrete FT "slides" over the entire signal, so would "consider" points [0..7], [1..8] and so on, and you are dropping many of those out. DTF has some nice properties allowing you to reduce the computational cost (Cooley–Tukey algorithm is probably the most popular implementation of FFT, but they use interleaving instead), but that is not trivial. Consider what happens if all 8-point segments perfectly match a sinusoid of a given frequency each, but all have different phases. $\endgroup$
    – Lodinn
    Jan 7, 2023 at 3:52

4 Answers 4

7
$\begingroup$

There are ways to compute large FFTs by combining smaller FFT computations. Have a look at my blog post to see how this is done.

As others imply, the problem is that this is much less efficient than just taking the FFT of the original signal as shown in the plot below (taken from the blog post).

Plot of computational complexity of approach vs signal length.

$\endgroup$
1
  • 2
    $\begingroup$ Rick, I've taken the liberty of expanding your answer a bit and including the plot from your blog post. Ping me if this is out of order. $\endgroup$
    – Peter K.
    Jan 5, 2023 at 15:57
6
$\begingroup$

Not really.

You can take DFTs (Discrete Fourier Transform) of shorter segments but this will give a you different results. The results of the shorter DFTs can be combined to create the result of the larger one, but it's not trivial.

In fact, the FFT (which is a specific algorithm to implement the DFT) uses that property of the DFT.

$\endgroup$
3
  • $\begingroup$ So if I divide the 1024 input samples into a total of 128 samples of 8-input points and use the DIT FFT algorithm to compute the 8-point FFT of each sample one by one. Should I be able to get the 1024-FFT after combining them all together? $\endgroup$
    – electroro
    Jan 5, 2023 at 14:09
  • 4
    $\begingroup$ Yes, but you need to combine them the correct way. which isn't simple. In essence you have to do 8 128-point DFTs to combine the results. A direct 1024 will be simpler and faster. $\endgroup$
    – Hilmar
    Jan 5, 2023 at 14:40
  • 4
    $\begingroup$ @electroro If you look at how the FFT works: the 1024-FFT does two 512-FFTs and then does some math to combine them. And the 512-FFT does two 256-FFTs and then does some math to combine them, and so on. Combining them is not just stacking them together. $\endgroup$
    – user253751
    Jan 5, 2023 at 21:03
6
$\begingroup$

You can, but these two operations are not equivalent.

  • In one case you're taking a length $N = 1024$ $\tt{FFT}$ of a length $N_0=1024$ input signal: $$x[n] \xrightarrow{\texttt{FFT}} X[k]$$

    $k=0, \dots, 1023 \quad n = 0, \dots, 1023$

    so in the frequency domain, $X[k]$ will be of length $N = 1024$ and will contain the values of the signal components at frequencies $k \cdot f_s/1024$, $f_s$ being the sampling frequency.
    The ratio $f_s/N$ is called the frequency resolution.

  • In the other case, you're taking successive length $N = 8$ $\tt{FFTs}$ of a length $N_0=1024$ input signal: $$x[n] \xrightarrow{\texttt{FFT}} X[k]$$

    $k = 0, \dots, 7 \quad n = [0,\dots,7], [8,\dots,15], \dots, [1016,\dots,1023] $

    so in the frequency domain, $X[k]$ will be of length $N = 8$ and will contain the values of the signal components at frequencies $k \cdot f_s/8$.
    You can do this for successive segments and average the results; that's called a periodogram, and it will be an average of all your length-$8$ $\texttt{FFTs}$ with frequency resolution $f_s/8$, or you can look at the successive segments in 2 dimensions (time-frequency); that's called a spectrogram.

To answer your question, you can combine these successive length-$8$ $\texttt{FFTs}$ to get a length-$1024$ $\texttt{FFT}$ but it's neither trivial nor is it as efficient as taking the longer $\texttt{FFT}$.

$\endgroup$
5
$\begingroup$

Your proposal of first computing length-8 DFTs of every aligned block of 8 samples doesn't seem to help the larger goal of computing a length-1024 DFT efficiently.

Yes, the Cooley-Tukey radix-2 FFT relies on computing sub-FFTs of half size, quarter size, and so on. But no, the order of operations doesn't match what you're doing.

If you go the decimation in time (DIT) route, then your sub-FFTs need to grab time-domain elements that are far away due to the bit-reversed indexing. For example, you first need to compute a length-2 DFT for (x[0], x[512]) and (x[256], x[768]). The fact that you computed a length-8 DFT for (x[0], ..., x[7]) goes against this goal. See diagrams like this: https://www.quora.com/What-is-the-difference-between-decimation-in-time-and-decimation-in-frequency/answer/Jose-Soares-Augusto?share=1

If you go the decimation in frequency (DIF) route, then you first need to butterfly-combine time-domain elements that are far away, then perform sub-FFTs. For example, you first need to combine (x[0], x[512]) to produce new (x'[0], x'[512]). You also can't do this after computing the length-8 DFTs. See diagrams like this: http://site.iugaza.edu.ps/ahdrouss/files/2010/02/decimation_in_frequency.pdf#page=3

Hence, if you want a length-1024 FFT, you will have to buffer all 1024 samples and then transform the entire block all at once.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.