Iterative IFFT

Started by stg November 10, 2014
Hello.

I have an application where I am using IFFT to generate a number of
precomputed tables each table[n] containing pow(2, n) frequency
components/bins.

The way this is done is by regular IFFT:

synthesize(fdomain)
for each(table:n) table[n] = IFFTreal(data:=fdomain, size:=pow(2, n)

As such, each table[n] is half the size of the next one, and also contains
only half the frequencies. Essentially mip-mapping (is there a better word
for this?) borrowing GPU rendering terminology.

Now, my question is - is there a way of doing IFFT so that each step can
utilize data from the previous calculation, or extracting each table at
various points throughout a single IFFT calculation on the full range of
frequency data?

	 

_____________________________		
Posted through www.DSPRelated.com
On 11/10/14 8:37 AM, stg wrote:
> Hello. > > I have an application where I am using IFFT to generate a number of > precomputed tables each table[n] containing pow(2, n) frequency > components/bins. > > The way this is done is by regular IFFT: > > synthesize(fdomain) > for each(table:n) table[n] = IFFTreal(data:=fdomain, size:=pow(2, n) >
boy, this is confusing. is "n" an index into a table of known size or is it the table size?
> As such, each table[n] is half the size of the next one, and also contains > only half the frequencies. Essentially mip-mapping (is there a better word > for this?) borrowing GPU rendering terminology. > > Now, my question is - is there a way of doing IFFT so that each step can > utilize data from the previous calculation,
yes, that is what the radix-2 FFT is about.
> or extracting each table at > various points throughout a single IFFT calculation on the full range of > frequency data? >
it depends of if it's "decimation in time" or "decimation in frequency". one computes cuts it up into the first half and the second half, the other cuts it up into the evens and the odds. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
>> synthesize(fdomain) >> for each(table:n) table[n] = IFFTreal(data:=fdomain, size:=pow(2, n)
>boy, this is confusing.
Sorry for the confusion. i can see how this would not be easy to understand as my code hides some details... Essentially I am generating the frequency content and putting this in fdomain. The content of fdomain is not typical for IFFT since it is real data only, no negative frequencies. This is understood by my current IFFTreal function. Essentially what the code does is generate several tables (table[n]), each containing a different number of samples. table[0] is 2 samples IFFT data from frequency bins 0 to 1 table[1] is 4 samples IFFT data from bins 0 to 3 table[2] is 8 samples IFFT data from bins 0 to 5 table[3] is 16 samples IFFT data from bins 0 to 7 This is performed by doing a full IFFT run for every table wanted. For anti-alias purposes I need all these tables and a table is selected while sampling the content so that it is ensured that the table will not contain frequencies that will alias. As mentioned, this is called mip-mapping in graphics, where filtering is typically used to generate smaller and smaller textures, each with only half the frequency content of the previous, so that you can always quickly access a texture level that will not have pronounced aliasing when drawn at a certain scale. Does this make better sense? _____________________________ Posted through www.DSPRelated.com