General FFT question

Hello,

while working daily with FFTs, I seem to have forgotten some of my 
theory :( 

Given:
- the "usual" FFT algorithm that turns N complex samples in time domain 
to N complex samples in frequency domain. 

- a real valued input signal (= some sampled data, sampling rate "fa").

If a is the result of the FFT, there are two "interesting" elements of a:

a[0] : This is the DC part of the signal. That much is clear. Its 
imaginary part is zero in our scenario.

a[1…N/2] : correspond to the multiples of Δf=fa/N. That's clear, too.

But... It seems that the element at a[N/2+1] is somehow "special", like
a[0]. Its imaginary part seems to be zero in this scenario. I don't know, 
but it seems it's not the first of the negative frequencies that make up 
the rest of the spectrum.

Am I wrong? Is a[N/2+1] a "special" value? How's it interpreted?

Thanks for your help,
Markus

On Wednesday, February 26, 2014 3:46:53 AM UTC-5, Markus Grunwald wrote:
> Hello,
> 
> 
> 
> while working daily with FFTs, I seem to have forgotten some of my 
> 
> theory :( 
> 
> 
> 
> Given:
> 
> - the "usual" FFT algorithm that turns N complex samples in time domain 
> 
> to N complex samples in frequency domain. 
> 
> 
> 
> - a real valued input signal (= some sampled data, sampling rate "fa").
> 
> 
> 
> If a is the result of the FFT, there are two "interesting" elements of a:
> 
> 
> 
> a[0] : This is the DC part of the signal. That much is clear. Its 
> 
> imaginary part is zero in our scenario.
> 
> 
> 
> a[1…N/2] : correspond to the multiples of Δf=fa/N. That's clear, too.
> 
> 
> 
> But... It seems that the element at a[N/2+1] is somehow "special", like
> 
> a[0]. Its imaginary part seems to be zero in this scenario. I don't know, 
> 
> but it seems it's not the first of the negative frequencies that make up 
> 
> the rest of the spectrum.
> 
> 
> 
> Am I wrong? Is a[N/2+1] a "special" value? How's it interpreted?
> 
> 
> 
> Thanks for your help,
> 
> Markus

Here is a tutorial on the DFT using interactive flash programs.  Perhaps it will help.

http://www.fourier-series.com/fourierseries2/DFT_tutorial.html

On Wednesday, February 26, 2014 3:46:53 AM UTC-5, Markus Grunwald wrote:
> Hello,
> 
> 
> 
> while working daily with FFTs, I seem to have forgotten some of my 
> 
> theory :( 
> 
> 
> 
> Given:
> 
> - the "usual" FFT algorithm that turns N complex samples in time domain 
> 
> to N complex samples in frequency domain. 
> 
> 
> 
> - a real valued input signal (= some sampled data, sampling rate "fa").
> 
> 
> 
> If a is the result of the FFT, there are two "interesting" elements of a:
> 
> 
> 
> a[0] : This is the DC part of the signal. That much is clear. Its 
> 
> imaginary part is zero in our scenario.
> 
> 
> 
> a[1…N/2] : correspond to the multiples of Δf=fa/N. That's clear, too.
> 
> 
> 
> But... It seems that the element at a[N/2+1] is somehow "special", like
> 
> a[0]. Its imaginary part seems to be zero in this scenario. I don't know, 
> 
> but it seems it's not the first of the negative frequencies that make up 
> 
> the rest of the spectrum.
> 
> 
> 
> Am I wrong? Is a[N/2+1] a "special" value? How's it interpreted?
> 
> 
> 
> Thanks for your help,
> 
> Markus

Markus,

The "middle" sample becomes special if the length of your FFT is even.

Why it becomes special, is because you are sampling on the zero crossings of a sine for the imaginary portion, which means you multiply everything by zero. Thus any info there is lost.

Think of sampling a cosine every multiple of 180 degrees. You get a sequence of

1, -1, 1, -1, etc.

Then sample a sine at every muliple of 180 degrees. Then your sequence is

0, 0, 0, 0, etc.

This is what happens for the middle sample.


And there are other ways to arrive at the "specialness" of the middle sample, such as looking at muliplying a signal by a sinusoid is the same as muliplying by two exponential functions[1] where viewed in the frequency domain one exponential function shifts the spectrum left and the other exponential shifts the spectrum right. Because of the spectra wraparound the middle point becomes special.

Clay

[1] Take Euler's identity exp(ix) = cos(x) + i*sin(x)

and with a little work arrive at:

sin(x) = (  exp(ix) - exp(-ix)  ) / 2i

cos(x) = (  exp(ix) + exp(-ix)  ) / 2

On Wed, 26 Feb 2014 08:46:53 +0000 (UTC), Markus Grunwald
<markus.grunwald@pruftechnik.com> wrote:

>Hello,
>
>while working daily with FFTs, I seem to have forgotten some of my 
>theory :( 
>
>Given:
>- the "usual" FFT algorithm that turns N complex samples in time domain 
>to N complex samples in frequency domain. 
>
>- a real valued input signal (= some sampled data, sampling rate "fa").
>
>If a is the result of the FFT, there are two "interesting" elements of a:
>
>a[0] : This is the DC part of the signal. That much is clear. Its 
>imaginary part is zero in our scenario.
>
>a[1&hellip;N/2] : correspond to the multiples of &Delta;f=fa/N. That's clear, too.
>
>But... It seems that the element at a[N/2+1] is somehow "special", like
>a[0]. Its imaginary part seems to be zero in this scenario. I don't know, 
>but it seems it's not the first of the negative frequencies that make up 
>the rest of the spectrum.
>
>Am I wrong? Is a[N/2+1] a "special" value? How's it interpreted?
>
>Thanks for your help,
>Markus

I think it's a little "special" in that, depending on your coefficient
numbering and quanitity of points (even), it is simultaneously the
highest and lowest output frequency sample of the transform.   It is
exactly the border of the repeating spectrum period.   This is
generally true for any input, real- or complex-valued.

For stritcly real-valued inputs as posed, see Clay's post.   ;)




Eric Jacobsen
Anchor Hill Communications
http://www.anchorhill.com

On Wed, 26 Feb 2014 08:46:53 +0000, Markus Grunwald wrote:

> Hello,
> 
> while working daily with FFTs, I seem to have forgotten some of my
> theory :(
> 
> Given:
> - the "usual" FFT algorithm that turns N complex samples in time domain
> to N complex samples in frequency domain.
> 
> - a real valued input signal (= some sampled data, sampling rate "fa").
> 
> If a is the result of the FFT, there are two "interesting" elements of
> a:
> 
> a[0] : This is the DC part of the signal. That much is clear. Its
> imaginary part is zero in our scenario.
> 
> a[1…N/2] : correspond to the multiples of Δf=fa/N. That's clear, too.
> 
> But... It seems that the element at a[N/2+1] is somehow "special", like
> a[0]. Its imaginary part seems to be zero in this scenario. I don't
> know,
> but it seems it's not the first of the negative frequencies that make up
> the rest of the spectrum.
> 
> Am I wrong? Is a[N/2+1] a "special" value? How's it interpreted?

What Clay and Eric said about your specific question.  It more or less 
falls out of the fact that the input is real and N is even.

Keep in mind that a[0 ... N/2] = a[N-1 ... N/2]*, where a* denotes the 
complex conjugate of a.  This (together with knowing that Im(a[0]) == Im(a
[N/2] == 0) reflects the fact that you only put in N non-zero points 
(because the N imaginary samples were zero), so you only get out N unique 
points.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Tim Wescott <tim@seemywebsite.really> wrote:
> On Wed, 26 Feb 2014 08:46:53 +0000, Markus Grunwald wrote:

(snip)
>> If a is the result of the FFT, there are two "interesting" elements of
>> a:

(snip)

>> But... It seems that the element at a[N/2+1] is somehow "special", like
>> a[0]. Its imaginary part seems to be zero in this scenario. 

(snip)
>> Am I wrong? Is a[N/2+1] a "special" value? How's it interpreted?
 
> What Clay and Eric said about your specific question.  It more or less 
> falls out of the fact that the input is real and N is even.
 
> Keep in mind that a[0 ... N/2] = a[N-1 ... N/2]*, where a* denotes the 
> complex conjugate of a.  This (together with knowing that Im(a[0]) == Im(a
> [N/2] == 0) reflects the fact that you only put in N non-zero points 
> (because the N imaginary samples were zero), so you only get out N unique 
> points.

That says why a[N/2] is special, but the OP asked about a[N/2+1].
(Where the first element is a[0].)

-- glen

On Wed, 26 Feb 2014 21:08:41 +0000, glen herrmannsfeldt wrote:

> Tim Wescott <tim@seemywebsite.really> wrote:
>> On Wed, 26 Feb 2014 08:46:53 +0000, Markus Grunwald wrote:
> 
> (snip)
>>> If a is the result of the FFT, there are two "interesting" elements of
>>> a:
> 
> (snip)
> 
>>> But... It seems that the element at a[N/2+1] is somehow "special",
>>> like a[0]. Its imaginary part seems to be zero in this scenario.
> 
> (snip)
>>> Am I wrong? Is a[N/2+1] a "special" value? How's it interpreted?
>  
>> What Clay and Eric said about your specific question.  It more or less
>> falls out of the fact that the input is real and N is even.
>  
>> Keep in mind that a[0 ... N/2] = a[N-1 ... N/2]*, where a* denotes the
>> complex conjugate of a.  This (together with knowing that Im(a[0]) ==
>> Im(a [N/2] == 0) reflects the fact that you only put in N non-zero
>> points (because the N imaginary samples were zero), so you only get out
>> N unique points.
> 
> That says why a[N/2] is special, but the OP asked about a[N/2+1].
> (Where the first element is a[0].)

We all missed that.

Hey!  OP!  You meant a[N/2].  Really.  a[N/2 + 1] is just the complex 
conjugate of a[N/2 - 1].  Or your indexing is off.  Or something.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

On Wed, 26 Feb 2014 08:46:53 +0000, Markus Grunwald wrote:

> Hello,
> 
> while working daily with FFTs, I seem to have forgotten some of my
> theory :(
> 
> Given:
> - the "usual" FFT algorithm that turns N complex samples in time domain
> to N complex samples in frequency domain.
> 
> - a real valued input signal (= some sampled data, sampling rate "fa").
> 
> If a is the result of the FFT, there are two "interesting" elements of
> a:
> 
> a[0] : This is the DC part of the signal. That much is clear. Its
> imaginary part is zero in our scenario.
> 
> a[1…N/2] : correspond to the multiples of Δf=fa/N. That's clear, too.
> 
> But... It seems that the element at a[N/2+1] is somehow "special", like
> a[0]. Its imaginary part seems to be zero in this scenario. I don't
> know,
> but it seems it's not the first of the negative frequencies that make up
> the rest of the spectrum.
> 
> Am I wrong? Is a[N/2+1] a "special" value? How's it interpreted?

Your indexing is off.  See my response to Glen Herrmannsfeldt's response 
to my response.  (Speaking of indexing).

If a's indexing starts at 0, then a[N/2] is special, with a zero 
imaginary part, and what Eric and Clay said holds.

If a's indexing starts at 0, then a[N/2 + 1] is only special in that with 
a real-valued input it equals the complex conjugate of a[N/2 - 1] -- but 
that holds for any pair a[N/2 + n] vs. a[N/2 - n], 0 <= n <= N/2.

If a's indexing starts at 1 (i.e., a[1] = DC), then a[N/2 + 1] is 
special, and what Eric and Clay said holds with appropriate adjustment of 
indexes.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

On Wed, 26 Feb 2014 16:07:15 -0600, Tim Wescott
<tim@seemywebsite.really> wrote:

>On Wed, 26 Feb 2014 21:08:41 +0000, glen herrmannsfeldt wrote:
>
>> Tim Wescott <tim@seemywebsite.really> wrote:
>>> On Wed, 26 Feb 2014 08:46:53 +0000, Markus Grunwald wrote:
>> 
>> (snip)
>>>> If a is the result of the FFT, there are two "interesting" elements of
>>>> a:
>> 
>> (snip)
>> 
>>>> But... It seems that the element at a[N/2+1] is somehow "special",
>>>> like a[0]. Its imaginary part seems to be zero in this scenario.
>> 
>> (snip)
>>>> Am I wrong? Is a[N/2+1] a "special" value? How's it interpreted?
>>  
>>> What Clay and Eric said about your specific question.  It more or less
>>> falls out of the fact that the input is real and N is even.
>>  
>>> Keep in mind that a[0 ... N/2] = a[N-1 ... N/2]*, where a* denotes the
>>> complex conjugate of a.  This (together with knowing that Im(a[0]) ==
>>> Im(a [N/2] == 0) reflects the fact that you only put in N non-zero
>>> points (because the N imaginary samples were zero), so you only get out
>>> N unique points.
>> 
>> That says why a[N/2] is special, but the OP asked about a[N/2+1].
>> (Where the first element is a[0].)
>
>We all missed that.
>
>Hey!  OP!  You meant a[N/2].  Really.  a[N/2 + 1] is just the complex 
>conjugate of a[N/2 - 1].  Or your indexing is off.  Or something.

I didn't miss it, I added the caveat about "depending on your
coefficient numbering".    I didn't point it out because I thought the
only candidate in the region for specialness is the symmetry point, so
I figured it was a typo or a numbering issue.

>-- 
>
>Tim Wescott
>Wescott Design Services
>http://www.wescottdesign.com
>

Eric Jacobsen
Anchor Hill Communications
http://www.anchorhill.com

Hello to all who answered :)

Thank you very much, your Answers were most helpful. The one that I 
understood easily was clay's "Think of sampling a cosine every multiple 
of 180 degrees." while the others helped to understand further.

And you're right, I got my indexing wrong.

cu
/me