Could we calculate FFT/IFFT for N samples based on N/2 samples?

Hi,

I am a newbie in DSP field. Now, I try to study by making small C code
based on the library. I have the following trouble.

Library I used supports calculating FFT for N/2 samples only (e.g:
1024 samples). Could I calculate FFT for N samples (e.g: 2048 samples)
just based on this library?

If you know, could you tell me the outline of implementing? I would
like to do it so that I can understand more about the FFT.

<karacomp@gmail.com> wrote in message 
news:1176003699.878560.66510@n76g2000hsh.googlegroups.com...
> Hi,
>
> I am a newbie in DSP field. Now, I try to study by making small C code
> based on the library. I have the following trouble.
>
> Library I used supports calculating FFT for N/2 samples only (e.g:
> 1024 samples). Could I calculate FFT for N samples (e.g: 2048 samples)
> just based on this library?
>
> If you know, could you tell me the outline of implementing? I would
> like to do it so that I can understand more about the FFT.

It's not clear what your problem is or the context of your question
How about defining N=4096 or ... ?
Then N/2 will be 2048 if that's what you need ... although it seems quite 
strange.

Perhaps the library is for a *real* FFT and doubles up the samples into real 
and imaginary array parts - thus N real samples go into N/2 complex samples?


Fred 

On 8 Apr, 05:41, "karac...@gmail.com" <karac...@gmail.com> wrote:
> Hi,
>
> I am a newbie in DSP field. Now, I try to study by making small C code
> based on the library. I have the following trouble.
>
> Library I used supports calculating FFT for N/2 samples only (e.g:
> 1024 samples). Could I calculate FFT for N samples (e.g: 2048 samples)
> just based on this library?

What FFT library do you use?

The one explanation I can think of that might explain such
behaviour is that you use an FFT library which compute
spectra for real-vaued sequences. It is common for such
routines to only return N/2 complex-valued coefficients.
This will be explained in the documetation for the FFT.

If this is *NOT* what you have, post an as elaborate
explanation as possible of the input data you use, how
you call the routine, and the format of the returned data.

Rune

On Apr 8, 6:23 am, "Rune Allnor" <all...@tele.ntnu.no> wrote:
> On 8 Apr, 05:41, "karac...@gmail.com" <karac...@gmail.com> wrote:
>
> > Hi,
>
> > I am a newbie in DSP field. Now, I try to study by making small C code
> > based on the library. I have the following trouble.
>
> > Library I used supports calculating FFT for N/2 samples only (e.g:
> > 1024 samples). Could I calculate FFT for N samples (e.g: 2048 samples)
> > just based on this library?
>
> What FFT library do you use?
>
> The one explanation I can think of that might explain such
> behaviour is that you use an FFT library which compute
> spectra for real-vaued sequences. It is common for such
> routines to only return N/2 complex-valued coefficients.
> This will be explained in the documetation for the FFT.
>
> If this is *NOT* what you have, post an as elaborate
> explanation as possible of the input data you use, how
> you call the routine, and the format of the returned data.
>
> Rune

Original Poster,

If you have what Fred and Rune are describing, and N/2 complex values
are returned for N real input values, be aware that the actual 0 bin
(DC) and N/2 (half the sample rate) bin are both real, but BOTH may be
packed into first complex value (usually real part is result for DC
(real), imaginary part is result (real) for half the sample rate (also
strictly real).

Dirk

On Apr 8, 4:31 pm, "dbell" <bellda2...@cox.net> wrote:
> On Apr 8, 6:23 am, "Rune Allnor" <all...@tele.ntnu.no> wrote:
>
>
>
> > On 8 Apr, 05:41, "karac...@gmail.com" <karac...@gmail.com> wrote:
>
> > > Hi,
>
> > > I am a newbie in DSP field. Now, I try to study by making small C code
> > > based on the library. I have the following trouble.
>
> > > Library I used supports calculating FFT for N/2 samples only (e.g:
> > > 1024 samples). Could I calculate FFT for N samples (e.g: 2048 samples)
> > > just based on this library?
>
> > What FFT library do you use?
>
> > The one explanation I can think of that might explain such
> > behaviour is that you use an FFT library which compute
> > spectra for real-vaued sequences. It is common for such
> > routines to only return N/2 complex-valued coefficients.
> > This will be explained in the documetation for the FFT.
>
> > If this is *NOT* what you have, post an as elaborate
> > explanation as possible of the input data you use, how
> > you call the routine, and the format of the returned data.
>
> > Rune
>
> Original Poster,
>
> If you have what Fred and Rune are describing, and N/2 complex values
> are returned for N real input values, be aware that the actual 0 bin
> (DC) and N/2 (half the sample rate) bin are both real, but BOTH may be
> packed into first complex value (usually real part is result for DC
> (real), imaginary part is result (real) for half the sample rate (also
> strictly real).
>
> Dirk

Hi Dirk (also Fred and Rune),

It might be that Fred and Rune are correct. I use library which is
written by former students at my university. I would like to use it to
solve my problem "calculate FFT for N samples". I work with 1-D array
of integer data.

Unfortunately, the author of the library might forget to leave any
document about their work. The problem is "I need to calculate FFT for
2048 samples while this library supports only 1024 FFT calculation".

When I ask my classmates about this problem, he answers it might be
possible. He lists the following steps I should follow:

1. I should apply FFT function twice for each half of array to get two
arrays of result. He means 2048 samples will produce 2 arrays which
each array has 1024 FFT coefficients. Suppose input array is A and
output arrays are B, C

2. After that I should apply additional FFT written by myself for each
combination ( one is from the first array - B - and one is from the
second array - C ). This step will produce the final array - D. The
problem here is I have to find the "weight" parameter by myself.

3. Find a way to re-arrange the elements of the array - D. He also
recommends that I have to find the rearrange approach by myself also.

My classmates are so busy with their own exercises. Therefore, they
can not help me further. At this time, I don't pay attention to the
format of output data. I just need one hint so that I could proceed
the remaining parts.

It is possible for me to use other library which supports full-
functions of FFT calculation. However, I think usage of that kind of
library will break down my effort of understanding FFT.

Could you help me to understand more about my friend's answer?
Especially what is "weight" parameter? How to find the way of
rearranging?

On Apr 9, 4:05 pm, "karac...@gmail.com" <karac...@gmail.com> wrote:
> On Apr 8, 4:31 pm, "dbell" <bellda2...@cox.net> wrote:
>
> Unfortunately, the author of the library might forget to leave any
> document about their work. The problem is "I need to calculate FFT for
> 2048 samples while this library supports only 1024 FFT calculation".
>
> When I ask my classmates about this problem, he answers it might be
> possible. He lists the following steps I should follow:
>
> 1. I should apply FFT function twice for each half of array to get two
> arrays of result. He means 2048 samples will produce 2 arrays which
> each array has 1024 FFT coefficients. Suppose input array is A and
> output arrays are B, C
>
> 2. After that I should apply additional FFT written by myself for each
> combination ( one is from the first array - B - and one is from the
> second array - C ). This step will produce the final array - D. The
> problem here is I have to find the "weight" parameter by myself.
>
> 3. Find a way to re-arrange the elements of the array - D. He also
> recommends that I have to find the rearrange approach by myself also.
>
> Could you help me to understand more about my friend's answer?
> Especially what is "weight" parameter? How to find the way of
> rearranging?


He/she is probably referring to the idea that a size-N FFT may be
decomposed into two size-N/2 FFTs using decimation-in-time or
decimation-in-frequency.  This process requires multiplying one half
of the inputs/outputs by FFT twiddle factors (probably the "weighting"
your friend refers to), and reordering of inputs or outputs to
function correctly.  See any good introductory book on DSP (e.g.
Oppenheim & Schafer), or Google for DIT FFT (or DIF FFT).


--
Oli

"Oli Charlesworth" <catch@olifilth.co.uk> wrote in message 
news:1176131828.600702.258690@e65g2000hsc.googlegroups.com...
> On Apr 9, 4:05 pm, "karac...@gmail.com" <karac...@gmail.com> wrote:
>> On Apr 8, 4:31 pm, "dbell" <bellda2...@cox.net> wrote:
>>
>> Unfortunately, the author of the library might forget to leave any
>> document about their work. The problem is "I need to calculate FFT for
>> 2048 samples while this library supports only 1024 FFT calculation".
>>
>> When I ask my classmates about this problem, he answers it might be
>> possible. He lists the following steps I should follow:
>>
>> 1. I should apply FFT function twice for each half of array to get two
>> arrays of result. He means 2048 samples will produce 2 arrays which
>> each array has 1024 FFT coefficients. Suppose input array is A and
>> output arrays are B, C
>>
>> 2. After that I should apply additional FFT written by myself for each
>> combination ( one is from the first array - B - and one is from the
>> second array - C ). This step will produce the final array - D. The
>> problem here is I have to find the "weight" parameter by myself.
>>
>> 3. Find a way to re-arrange the elements of the array - D. He also
>> recommends that I have to find the rearrange approach by myself also.
>>
>> Could you help me to understand more about my friend's answer?
>> Especially what is "weight" parameter? How to find the way of
>> rearranging?
>
>
> He/she is probably referring to the idea that a size-N FFT may be
> decomposed into two size-N/2 FFTs using decimation-in-time or
> decimation-in-frequency.  This process requires multiplying one half
> of the inputs/outputs by FFT twiddle factors (probably the "weighting"
> your friend refers to), and reordering of inputs or outputs to
> function correctly.  See any good introductory book on DSP (e.g.
> Oppenheim & Schafer), or Google for DIT FFT (or DIF FFT).

Not to discourage education but it sounds like you have a bigger objective - 
maybe not..... So, with caution I suggest:

Take a look at FFTW code.  http://www.fftw.org/

Fred 

On 9 Apr, 17:05, "karac...@gmail.com" <karac...@gmail.com> wrote:

> Unfortunately, the author of the library might forget to leave any
> document about their work. The problem is "I need to calculate FFT for
> 2048 samples while this library supports only 1024 FFT calculation".

Ah. So you use in-house code where the maximum FFT size is
hard-coded...

...
> It is possible for me to use other library which supports full-
> functions of FFT calculation. However, I think usage of that kind of
> library will break down my effort of understanding FFT.
>
> Could you help me to understand more about my friend's answer?
> Especially what is "weight" parameter? How to find the way of
> rearranging?- Skjul sitert tekst -

Depending on how much time you have available, either get
another FFT library or implement it yourself, with sufficient
flexibility to at least handle an FFT length of any power of 2.
There are plenty of FFT codes publicly available which you
can use as template (see e.g. "Numerical Recipies in C").

Proceeding with the current library is a waste of time and
will cause a lot more problems than it is worth.

Rune

On Apr 9, 8:17 am, "Oli Charlesworth" <c...@olifilth.co.uk> wrote:
> On Apr 9, 4:05 pm, "karac...@gmail.com" <karac...@gmail.com> wrote:
>
>
>
> > On Apr 8, 4:31 pm, "dbell" <bellda2...@cox.net> wrote:
>
> > Unfortunately, the author of the library might forget to leave any
> > document about their work. The problem is "I need to calculate FFT for
> > 2048 samples while this library supports only 1024 FFT calculation".
>
> > When I ask my classmates about this problem, he answers it might be
> > possible. He lists the following steps I should follow:
>
> > 1. I should apply FFT function twice for each half of array to get two
> > arrays of result. He means 2048 samples will produce 2 arrays which
> > each array has 1024 FFT coefficients. Suppose input array is A and
> > output arrays are B, C
>
> > 2. After that I should apply additional FFT written by myself for each
> > combination ( one is from the first array - B - and one is from the
> > second array - C ). This step will produce the final array - D. The
> > problem here is I have to find the "weight" parameter by myself.
>
> > 3. Find a way to re-arrange the elements of the array - D. He also
> > recommends that I have to find the rearrange approach by myself also.
>
> > Could you help me to understand more about my friend's answer?
> > Especially what is "weight" parameter? How to find the way of
> > rearranging?
>
> He/she is probably referring to the idea that a size-N FFT may be
> decomposed into two size-N/2 FFTs using decimation-in-time or
> decimation-in-frequency.  This process requires multiplying one half
> of the inputs/outputs by FFT twiddle factors (probably the "weighting"
> your friend refers to), and reordering of inputs or outputs to
> function correctly.  See any good introductory book on DSP (e.g.
> Oppenheim & Schafer), or Google for DIT FFT (or DIF FFT).
>
> --
> Oli

Hi Oil,

I have found the book. Everything is clear now. Thanks a lot for your
hint. The ball now is mine.

On Apr 9, 12:57 pm, "Fred Marshall" <fmarshallx@remove_the_x.acm.org>
wrote:
> "Oli Charlesworth" <c...@olifilth.co.uk> wrote in message
>
> news:1176131828.600702.258690@e65g2000hsc.googlegroups.com...
>
>
>
> > On Apr 9, 4:05 pm, "karac...@gmail.com" <karac...@gmail.com> wrote:
> >> On Apr 8, 4:31 pm, "dbell" <bellda2...@cox.net> wrote:
>
> >> Unfortunately, the author of the library might forget to leave any
> >> document about their work. The problem is "I need to calculate FFT for
> >> 2048 samples while this library supports only 1024 FFT calculation".
>
> >> When I ask my classmates about this problem, he answers it might be
> >> possible. He lists the following steps I should follow:
>
> >> 1. I should apply FFT function twice for each half of array to get two
> >> arrays of result. He means 2048 samples will produce 2 arrays which
> >> each array has 1024 FFT coefficients. Suppose input array is A and
> >> output arrays are B, C
>
> >> 2. After that I should apply additional FFT written by myself for each
> >> combination ( one is from the first array - B - and one is from the
> >> second array - C ). This step will produce the final array - D. The
> >> problem here is I have to find the "weight" parameter by myself.
>
> >> 3. Find a way to re-arrange the elements of the array - D. He also
> >> recommends that I have to find the rearrange approach by myself also.
>
> >> Could you help me to understand more about my friend's answer?
> >> Especially what is "weight" parameter? How to find the way of
> >> rearranging?
>
> > He/she is probably referring to the idea that a size-N FFT may be
> > decomposed into two size-N/2 FFTs using decimation-in-time or
> > decimation-in-frequency.  This process requires multiplying one half
> > of the inputs/outputs by FFT twiddle factors (probably the "weighting"
> > your friend refers to), and reordering of inputs or outputs to
> > function correctly.  See any good introductory book on DSP (e.g.
> > Oppenheim & Schafer), or Google for DIT FFT (or DIF FFT).
>
> Not to discourage education but it sounds like you have a bigger objective -
> maybe not..... So, with caution I suggest:
>
> Take a look at FFTW code.  http://www.fftw.org/
>
> Fred

Hi Fred,

FFTW is cute. I have tried. It works. However, with Oil's advice, I
can proceed my work. Thanks for your honest suggestion.