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?
DFT symmetry
Started by ●September 15, 2011
Reply by ●September 15, 20112011-09-15
On Sep 15, 9:18�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
Reply by ●September 16, 20112011-09-16
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.
Reply by ●September 17, 20112011-09-17
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."
Reply by ●September 17, 20112011-09-17
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."
Reply by ●September 17, 20112011-09-17
> > 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...
Reply by ●September 17, 20112011-09-17
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
Reply by ●September 18, 20112011-09-18
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
Reply by ●September 18, 20112011-09-18
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.
Reply by ●September 19, 20112011-09-19
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."