Iterative IFFT

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