DFT symmetry

I've just discovered that the DFT is symmetrical about the N/2 value and 
does not include DC, something which the institution which is supposed to 
have told me this (the university I go to) had not!

Anyway, for an even N how can the DFT be symmetrical about the Im-axis 
when there is always going to be one extra bin in either the positive or 
negative frequency side? 

This means that the last bin on one of the sides has no twin on the other 
side. I always thought the negative frequency is a mirror image of the 
positive frequency but in the digital world with an even N this cannot 
happen, can it?

On Sep 15, 9:18&#4294967295;pm, Simeon <kotap...@yahoo.com> wrote:
> I've just discovered that the DFT is symmetrical about the N/2 value and
> does not include DC, something which the institution which is supposed to
> have told me this (the university I go to) had not!
>
> Anyway, for an even N how can the DFT be symmetrical about the Im-axis
> when there is always going to be one extra bin in either the positive or
> negative frequency side?
>
> This means that the last bin on one of the sides has no twin on the other
> side. I always thought the negative frequency is a mirror image of the
> positive frequency but in the digital world with an even N this cannot
> happen, can it?

you are almost  right but not quite correct.  Here is a website where
you can play with a 16 point DFT and see how it is developed.  (There
is a dc term and that dc term is not symetrical about n/2 + the
imginary component is inverse symetrical.  Plus all of these
assumptions are based upon a real only inuts)

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

the FFT knows nothing about frequencies etc. That's solely our
interpretation.

For even order, there is an alternating exp() term. If I think about it as
a rotating complex phasor, I can't tell which way it turns. All I see is
[-1, 1, -1, 1, ...].

-If- I know that it represents a real-valued signal in the time domain,
I've got additional knowledge that half of it is negative frequency, and
half of it positive: One phasor turns backwards, the other one forwards.
The imaginary parts cancel and the real part remains. 
But this is, as said, a matter of interpretation.

In applications, it's frequently a good idea to keep it zero, that is, use
some kind of oversampling.

On 9/16/11 3:52 AM, mnentwig wrote:
 > the FFT knows nothing about frequencies etc. That's solely our
 > interpretation.
 >

i can't agree with that.  the DFT knows about X[2], the value of what is 
in X[2] tells the DFT something about a *frequency* component in x[n]. 
that component has *frequency* of 2 cycles per N samples (where N is the 
DFT length).  the DFT doesn't know anything about *time*, but 
"frequency" is the frequency of occurrence of some quantity in *some* 
domain, but that domain does not have to be time.  but there is still 
frequency.

On 9/15/11 9:18 PM, Simeon wrote:
> I've just discovered that the DFT is symmetrical about the N/2 value and
> does not include DC,

i dunno if you mean the DCT (Discrete Cosine Transform), but what you 
just discovered is decidedly not true.

> something which the institution which is supposed to
> have told me this (the university I go to) had not!

damn them institutions.

if your institution didn't tell you that the Discrete Fourier Transform 
maps an arbitrary set of N (possibly complex) numbers to another set of 
N complex numbers, then that institution failed to tell you something.

and there is definitely a DC component to the DFT.  we call it "X[0]".

the DCT might be something like the DFT of what would be two periods of 
the input sequence, but with the latter repeated cycle flipped upside 
down. and in the DFT, you pick out only the X[k] for odd k.

another reality that some will dispute is that the DFT is most 
fundamentally mapping a periodic sequence x[n] of period N,

     x[n+N] = x[n]    for all n

to another periodic sequence X[k] with the same period,

     X[k+N] = X[k]    for all k .


DFT:
                    N-1
      X[k] =        SUM{ x[n] * e^(-j*2*pi*n*k/N) }
                    n=0

IDFT:
                    N-1
      x[n] =  1/N * SUM{ X[k] * e^(+j*2*pi*n*k/N) }
                    k=0

that's what the DFT does (things like where the 1/N goes is a matter of 
convention), and both X[k] and x[n] expressed as above are periodic with 
period N.

> Anyway, for an even N how can the DFT be symmetrical about the Im-axis
> when there is always going to be one extra bin in either the positive or
> negative frequency side?

probably another thing you might have halfway learned.  if the input to 
the DFT, x[n], is real, then there is this thing they used to call 
"Hermitian symmetry" applies to the DFT result.

     Im{ x[n] } = 0    ===>    X[N-k] = conj{ X[k]] }

> This means that the last bin on one of the sides has no twin on the other
> side.

that's true only if N is even.

it means that  X[N/2] = X[N - N/2] = conj{ X[N/2] }

and if any complex number is equal to its own conjugate, it must be 
real.  and because X[N/2] = X[N - N/2], that bin (it's in the middle of 
the DFT, but if you consider the periodicity noted above as fundamental, 
then you can pick any bin and call it a "side".

> I always thought the negative frequency is a mirror image of the
> positive frequency but in the digital world with an even N this cannot
> happen, can it?

usually, with a real input x[n], i think of the top half of X[k] (where 
N/2 <= k < N) to be at negative frequencies.  so if k > N/2, i don't 
consider X[k] but instead, the frequency is at N-k which is negative 
with abs value less than N/2.  the only bin left is X[N/2] and you can 
toss it on the left or on the right (or half of it on both sides if this 
mirror image is important to you).  usually, because of the sign 
convention of 2's compliment numbers, we put it on the left and call it 
X[-N/2].  for the purposes of evaluating a continuous and real x(t) out 
of the discrete x[n], then the mirror image property is important, and 
half of X[N/2] value should be at the negative frequency and half at the 
positive frequency.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

On 9/17/11 1:50 PM, robert bristow-johnson wrote:
>
> ...
> and there is definitely a DC component to the DFT. we call it "X[0]".
>
> the DCT might be something like the DFT of what would be two periods of
> the input sequence, but with the latter repeated cycle flipped upside
> down. and in the DFT, you pick out only the X[k] for odd k.

i meant to say that is the Discrete Sine Transform.  where N is even and

    x[N/2 + n] = -x[N/2-1 - n]    for   0 <= n < N/2

and after DFT, we consider only X[2*k + 1].  no DC component.

the DCT *does* have a DC component because first we say

    x[N/2 + n] = +x[N/2-1 - n]    for   0 <= n < N/2

and after the DFT, we consider only X[2*k].

i might have that wrong, but that's how i remember it.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

> > the FFT knows nothing about frequencies etc. That's solely our
> > interpretation.
> >

> i can't agree with that.

Well, I'm looking at it differently, intuitively:
The discrete FT is a projection on some basis. And for me, the "basis" is a
cloud of points, nothing more. 

Now I look at the "cloud of points", and the trained eye immediately spots
that it represents a 1 kHz sine wave. 
But, the eye can be deceived: What looks like a 1 kHz sine wave is actually
my 2 GHz carrier with bandpass sampling.  

One practical example is to use FFT for computing derivatives of a
_waveform_ (=> multiply with the bin index in the frequency domain):
When my rotating phasor spins forwards or backwards, the FFT-"cloud of
points" doesn't care, but the derivatives most certainly do! 
In other words, I'm using side information about frequencies to bridge the
gap between the FFT "cloud-of-points" and the continuous-time waveform.

But I'm not saying there's a "right" or a "wrong" way to look at it. 
Any "intuitive" view will have its flaws, and maybe engineering is all
about knowing where the dragons lurk in my corner of the woods...

On Sep 17, 1:50=A0pm, robert bristow-johnson <r...@audioimagination.com>
wrote:
<<<<snip>>>>
>
> and there is definitely a DC component to the DFT. =A0we call it "X[0]".
>

Ahhh..... but, Robert, simple-minded folks such as
myself count from 1, not 0, and so X[0] does not
exist for us.  Simeon is quite right; there is no DC
component in the DFT.  :-)

Dilip Beancounter

On 9/15/2011 6:18 PM, Simeon wrote:
> I've just discovered that the DFT is symmetrical about the N/2 value and
> does not include DC, something which the institution which is supposed to
> have told me this (the university I go to) had not!
>
> Anyway, for an even N how can the DFT be symmetrical about the Im-axis
> when there is always going to be one extra bin in either the positive or
> negative frequency side?
>
> This means that the last bin on one of the sides has no twin on the other
> side. I always thought the negative frequency is a mirror image of the
> positive frequency but in the digital world with an even N this cannot
> happen, can it?

Maybe it would be a good idea for you to think of the DFT result as one 
period of a periodic sequence.  Then the "DC" term repeats at the right 
places, etc.

Some people don't like this all that much but it helps *me*!

And, it shows that there isn't an "extra term" - simply one that's 
assumed at the other end.

Fred

OK so reading a bit more about the DFT here is what happens. The terms in 
the set [1,N/2-1] are the mirror image of the terms [N/2+1, N-1]. The 
terms X[0] and X[N/2] are independent. That's why you only ever need to 
compute N/2 + 1 terms to get the DFT.

Robert what you're talking about (Hermitian Symmetry) is in the DSP world 
more commonly referred to as "Conjugate Symmetry" where for a real input:

X[m] = X*[-m]

Combine that with the periodicity of the DFT and you get:

X[m] = X*[N-m]

etc.

For some reason our lectures on DFT and FFT (mainly FFT) had confused me 
but I have to go back to the horrible handouts they distribute.

On 9/18/11 8:55 PM, Simeon wrote:
> OK so reading a bit more about the DFT here is what happens. The terms in
> the set [1,N/2-1] are the mirror image of the terms [N/2+1, N-1].

only if the input to the DFT is purely real (or purely imaginary, which 
is less often the case).

> The terms X[0] and X[N/2] are independent. That's why you only ever need
> to compute N/2 + 1 terms to get the DFT.

no, in general, the input x[n] is complex and "to get the DFT" it is 
insufficient to compute N/2 + 1 terms.

>
> Robert what you're talking about (Hermitian Symmetry) is in the DSP world
> more commonly referred to as "Conjugate Symmetry" where for a real input:
>
> X[m] = X*[-m]

call it whatever you want.  i'm not sure that i had the right name for 
it:   http://en.wikipedia.org/wiki/Hermitian_function .  but the real 
input doesn't do anything to provide meaning to the negative index.

> Combine that with the periodicity of the DFT and you get:
>
> X[m] = X*[N-m]
>

no, *first* you have (assuming real input) X[N-k] = conj{ X[k] }, *then* 
when you add to the mix the inherent periodicity of the DFT, you get 
X[-k] = conj{ X[k] }.  otherwise, you have no meaning for the X[k] with 
k outside of the interval from 0 to N-1.

*or* you can start with the inherent periodicity of the DFT and you have 
X[k+N] = X[k] for all k (this gives you meaning for the negative 
indices).  *then* you toss in the symmetry property of the DFT (assuming 
real input) where X[-k] = conj{ X[k] } and you get what you have above.

> etc.
>
> For some reason our lectures on DFT and FFT (mainly FFT)

what's the difference?  is there any FFT that is not the DFT?

> had confused me
> but I have to go back to the horrible handouts they distribute.

just get a good book and read it.  O&S is still my recommendation.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."