1
$\begingroup$

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!!

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – hotpaw2 Jan 31 '17 at 1:07
  • $\begingroup$ 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... $\endgroup$ – Mike Jan 31 '17 at 3:25
3
$\begingroup$

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}$.

You can arrive at a similar formula through a decimation in frequency approach. I leave the details for that to you or someone else.

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.

$\endgroup$
  • $\begingroup$ The problem here is that the library is limited to 2048 and I have 5120 data... I can't just process half the data and then add them like you said... which.... btw I can't figure out how to implement it with the library... I have been trying to modify the library... but so far thats all $\endgroup$ – Mike Jan 31 '17 at 3:20
  • $\begingroup$ You can take 3 FFTs of size 2048 and apply the equation on two levels. If you want me to write more in the answer I can, but most of the information is already there. $\endgroup$ – hops Jan 31 '17 at 3:59
  • $\begingroup$ Is there some reason that zero padding is not acceptable? So, instead of 5120, you could use 8192 (as alluded to in my last comment)? If zero padding is unacceptable then you will need to use a radix-5 stage somewhere. The combination is basically the same as the case described here. I will add it in explicitly if you'd like. Are there real-time constraints? $\endgroup$ – hops Jan 31 '17 at 4:08
  • $\begingroup$ according to the EDIT part of your answer, ammm the library is like a black box to me... I have been trying to modify it and didn't work so far. You are telling me that instead of using the N/2, to change the 2 for a 5, but then, I would have to do a lot of modifications to it... a lot. But.. what happens if I fill the arrays every 3rd data, using the size of 2048? Second: I decided to use 5120 because the ADC works at 52.734kHz so I decided to subsample the data to get 1 second of info and tried to couple the data to the library sizes. I could increment the data yes. 1/2 $\endgroup$ – Mike Jan 31 '17 at 15:49
  • $\begingroup$ The problem is that the library is already optimized for the MCU and I have also a FIR in there, so I would like to keep the library (unless I see that another library could give me less trouble) and the library doesn't have a radix-5 on it... So lets say I process the 6144 data without problem, taking a little bit more than a second of information and the combine them... The 'problem' with the 1024 data FFT is that is for complex data, not for real but.... can it work if I put all the real data there?? because thats another way... or get 10 FFTs of 512, which I already program 2/2 $\endgroup$ – Mike Jan 31 '17 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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