# Concatenating multiple FFTs

Im working on a small project and I'm using the DSP library from Texas Instruments. Working on an Hercules MCU. The library comes with RFFT and CFFT, implemented with a radix-4 algorithm. The library is limited to a buffer of length up to 2048 or 512 or 128 (the real one). And the complex support lengths of 16, 64, 256, 1024. The problem Im facing is that I have a buffer of 5120 (real). I tried to do two FFTs os 2048 and two of 512 and then concatenating them to get the bigger Fourier. The problem is that it obviously didn't work (I already realize that hehe)

the question here is How can I concatenate them correctly?? or should I modify the library to take the amount of data I need?

Thanks!!

• Why does your FFT length have to be the same as your buffer length? It's common to do FFTs either larger or smaller than the buffer that some hardware happens to hand off (FFT length chosen as required by your time locality and frequency resolution trade-offs or requirements) – hotpaw2 Jan 31 '17 at 1:07
• I need it to be at least the same size or a way to concatenate them on the way I exposed or a ten FFT of 512... Not necessarily the same size... but it would be easier... – Mike Jan 31 '17 at 3:25

It is not possible to simply concatenate FFTs to obtain a larger one (that would be a neat trick if it worked). It is possible to combine several smaller point FFT's to create a larger one. To see this, let's start with the original equation, $$X[k] = \sum_{n=0}^{N-1} x[n] \exp\left(-\frac{j 2 \pi k n}{N} \right).$$ Now, consider that we have used this formula on two sequences already to obtain two FFTs of length $\frac{N}{2}$, $$X_0[k] = \sum_{n=0}^{N/2-1} x[2 n] \exp\left(-\frac{j 2 \pi k n}{N/2} \right)$$ and $$X_1[k] = \sum_{n=0}^{N/2-1} x[2 n + 1] \exp\left(-\frac{j 2 \pi k n}{{N/2}} \right).$$ Now, we have two FFTs of length $\frac{N}{2}$, and we want to take the information contained in them to form a larger FFT. Specifically, we would like to form $$Y[k] = \sum_{n=0}^{N - 1} x[n] \exp\left(-\frac{j 2 \pi k n}{N} \right).$$ To see how to obtain this, we decompose the summation into two parts, one containing even terms and one containing odd terms, $$Y[k] = \sum_{n=0}^{N/2 - 1} x[2 n] \exp\left(-\frac{j 2 \pi k \left( 2 n\right)}{N} \right) + \sum_{n=0}^{N/2 - 1} x[2 n + 1] \exp\left(-\frac{j 2 \pi k \left(2 n + 1\right)}{N} \right).$$ Some simple transformations turn this into, $$Y[k] = \sum_{n=0}^{N/2 - 1} x[2 n] \exp\left(-\frac{j 2 \pi k n}{N/2} \right) + \exp\left(-\frac{j 2 \pi k}{N}\right) \sum_{n=0}^{N/2 - 1} x[2 n + 1] \exp\left(-\frac{j 2 \pi k n}{N/2} \right).$$ And this yields our answer. To obtain an FFT that is twice the length of two smaller FFTs, we simply apply a twiddle factor to the later samples and combine the two smaller FFTs via addition. Explicitly, based on the notations above, we can write $$Y[k] = X_0[k] + \exp\left(-\frac{j 2 \pi k}{N}\right) X_1[k]$$ where the index $k$ is taken modulo-$\frac{N}{2}$ or else $X_0[k]$ and $X_1[k]$ are considered periodic functions with period $\frac{N}{2}$.
Edit: If you are dead set on using $N=5120$ as your output FFT size, then you can use the following variation. First compute 5 FFTs of length 1024. You can compute these by taking every fifth number from the original sequence and applying the FFT from the library. For notational convenience, let's define these as $$X'_p[k] = \sum_{n=0}^{N/5-1} x[5n+p] \exp\left(-\frac{j 2 \pi k n}{N/5}\right) \:\: \mbox{for p = 0, 1, 2, 3, 4}.$$ Now, combine these components with the equation $$X[k] = \sum_{p=0}^{4} \exp\left( -\frac{j 2 \pi p k}{N} \right) X'_p[k].$$ Again, the indices should be considered modulo-$\frac{N}{5}$ in this case.