**UPGRADE YOUR BROWSER**

We have detected your current browser version is not the latest one. Xilinx.com uses the latest web technologies to bring you the best online experience possible. Please upgrade to a Xilinx.com supported browser:Chrome, Firefox, Internet Explorer 11, Safari. Thank you!

Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- Community Forums
- :
- Forums
- :
- Hardware Development
- :
- AI Engine, DSP IP and Tools
- :
- Re: Get a N-FFT with two N/2-FFT already computed

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

thomas.l.m

Visitor

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-06-2015 04:10 PM

8,743 Views

Registered:
03-06-2015

Get a N-FFT with two N/2-FFT already computed

After somme researchs on the web, I don't find the answer of my problem (or I don't understand it) and I hope this post will succeed.

I'm working on a real-time FFT convolution algorithm (C++) which split the impulse response in several increasing size blocks (64/128/256/...).

To realise the convolution, I have to split the incoming signal in blocks of the same sizes (64/128/...) to compute its FFts (when there is enough input signal to do this).

My idea is to use the FFts already computed to save some CPU time : with 2 FFts of 64 samples, I want to simulate the result of a FFT of 128 samples, ...

During the 1st step, we usually compute the FFT (128 samples (64 input samples and 64 zeropadding samples)

During the 2nd step, we usually compute the FFT (128 samples), and we join the 2 128-FFTs to create the 256-FFT

During the 3rd step, we usually compute the FFT (128 samples)

During the 4th step, we usually compute the FFT (128 samples), and we join the 2 128-FFTs to create the 256-FFT, and we join the 2 256-FFTs to create the 512-FFT

... and so on.

Little example:

1) x1 = {a, b, c, d, 0, 0, 0, 0}

X1 = fft(x1)

2) x2 = {e, f, g, h, 0, 0, 0, 0}

X2 = fft(x2)

X = X1+X2 might be equal to : fft({a, b, c, d, e, f, g, h, 0, 0, 0, 0, 0, 0, 0, 0}

Is it even possible???

In my algorithm I use the AudioFFT library (https://github.com/HiFi-LoFi/AudioFFT) (Accelerate for Mac, FFTW for Windows and OouraFFT for Linux).

Its class return an array for the real part and an array for the imaginary part (the size of each array is N/2+1, where N is the FFT lenght).

For now, I succeeded to join the result of the two smalls FFT (FFT1, FFT2) to obtain the even bins of the large FFT (FFT0): FFT0[0] = FFT1[0] + FFT2[0]

FFT0[1] = FFT1[1] - FFT2[1]

FFT0[2] = FFT1[2] + FFT2[2]

FFT0[3] = FFT1[3] - FFT2[3]

...

But, how can I get the odd bins??????

Thank you in advance and I hope I was clear enough (despite my bad English).

Please, ask me for more details if necessary.

Thanks.

3 Replies

Highlighted
##

Little correction:

FFT0[0] = FFT1[0] + FFT2[0]

FFT0[2] = FFT1[1] - FFT2[1]

FFT0[4] = FFT1[2] + FFT2[2]

FFT0[6] = FFT1[3] - FFT2[3]

thomas.l.m

Visitor

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-07-2015 02:02 AM

8,723 Views

Registered:
03-06-2015

Re: Get a N-FFT with two N/2-FFT already computed

FFT0[0] = FFT1[0] + FFT2[0]

FFT0[2] = FFT1[1] - FFT2[1]

FFT0[4] = FFT1[2] + FFT2[2]

FFT0[6] = FFT1[3] - FFT2[3]

bwiec

Xilinx Employee

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-08-2015 07:28 PM

8,682 Views

Registered:
08-02-2011

Re: Get a N-FFT with two N/2-FFT already computed

Sounds like you're performing FFT-based convolution using overlap-add:

http://en.wikipedia.org/wiki/Overlap%E2%80%93add_method

www.xilinx.com

thomas.l.m

Visitor

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-12-2015 01:23 PM

8,617 Views

Registered:
03-06-2015

Re: Get a N-FFT with two N/2-FFT already computed