simple questions about the DFT and its limits of integration

Hello Forum,

given a discrete signal x[n] of N samples, the DFT X[k] will also have N
samples. The limits of the summation of the DFT can be for k that goes from
-N to (N/2)-1 or from 0 to N-1, correct? DOes it give the same result?

More generally, I guess we can pick any arbitrary integer n0, and make the
limits go from n0+N to ( ((-n0+N)/2)-1 ). IF n0=-N, then the limits become
0 and N-1....
 
Why can we do that? Does it matter if the signal x[n] is real or complex?

thanks
fisico32

On 3 Mai, 14:57, "fisico32" <marcoscipioni1@n_o_s_p_a_m.gmail.com>
wrote:
> Hello Forum,
>
> given a discrete signal x[n] of N samples, the DFT X[k] will also have N
> samples. The limits of the summation of the DFT can be for k that goes from
> -N to (N/2)-1 or from 0 to N-1, correct? DOes it give the same result?

It depends on whether the complex exponentials are also shifted.
Apart from that, the order of summation might have an effect on
numerical approximation errors in the end result.

> More generally, I guess we can pick any arbitrary integer n0, and make the
> limits go from n0+N to ( ((-n0+N)/2)-1 ). IF n0=-N, then the limits become
> 0 and N-1....
>
> Why can we do that? Does it matter if the signal x[n] is real or complex?

The exact answer depends on what you do to the exponentials
when you change the summation index.

Either way, the DFT is nothing but a vector-matrix product,

X = Wx

where X and x are N-by-1 vectors and W is an N-by-N matrix
that contains the exponential terms.

Reminding in passing about a 1/N scaling constant that needs to
be included in suitable ways, you will find that W'W = WW' = I
independent of any mutual exponential factors. You can see this
by shifting the exponentials by a (possibly non-integer) amount
k to find

W_k = exp(k)W
W_k'W_k = exp(-k)W'exp(k)W = exp(-k)exp(k)W'W = 1*W'W = I

and so on.

Rune

On May 3, 7:57&#4294967295;am, "fisico32" <marcoscipioni1@n_o_s_p_a_m.gmail.com>
demanded:

> given a discrete signal x[n] of N samples, the DFT X[k] will also have N
> samples. The limits of the summation of the DFT can be for k that goes from
> -N to (N/2)-1 or from 0 to N-1, correct? DOes it give the same result?

Simple answer: NO unless you put some
constraints on the samples.  For example,
with N = 4, one calculation gives

X[0] = x[0] + x[1] + x[2] + x[3]

while the other gives

X[0] = x[-4] + x[-3] + x[-2] + x[-1] + x[0] + x[1]

Why on earth would anyone believe that the two
quantities above are the same?

--Dilip Sarwate

On May 3, 8:57&#4294967295;am, "fisico32" <marcoscipioni1@n_o_s_p_a_m.gmail.com>
wrote:
>
> given a discrete signal x[n] of N samples, the DFT X[k] will also have N
> samples. The limits of the summation of the DFT can be for k that goes from
> -N to (N/2)-1 or from 0 to N-1, correct?

i think you made a typo error here.  didn't you mean to say that k
goes from
-N/2 to (N/2)-1 or from 0 to N-1?  if that is what you meant to say, i
would say you are "correct".

> Does it give the same result?
>
> More generally, I guess we can pick any arbitrary integer n0, and make the
> limits go from n0+N to ( ((-n0+N)/2)-1 ). IF n0=-N, then the limits become
> 0 and N-1....

again, fixing your typo, you can make the limits go from n0 to n0+N-1
for any integer n0.


DFT:

                 n0+N-1
    X[k] =       SUM{ x[n] * exp(-j*2*pi*n*k/N }
                 n0

for   k0 <= k < k0+N



iDFT:

                 k0+N-1
    x[n] = (1/N) SUM{ X[k] * exp(+j*2*pi*n*k/N }
                 k0

for   n0 <= n < n0+N


for either the DFT or iDFT definitions, n0 and k0 can be whatever
integers your heart desires.  this is because there is no mathematical
difference between the DFT and the DFS ("Discrete Fourier Series").
they are just two different names or labels for the exact same
operation.  whether it's DFT/iDFT or DFS/iDFS, either map a discrete
and periodic sequence of period N to another discrete and periodic
sequence of the same period.  that is the DFT and iDFT (or DFS/iDFS)
assume a periodic extension of the data input to it:


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

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


in practice, because your computer memory does not go on forever, you
might have to use modulo arithmetic to impose this periodicity
explicitly in the indices of your x[n] or X[k] sequences.  you would
replace every n with

    n  <--  mod(n,N) = n - N*floor(n/N)

and every k with

    k  <--  mod(k,N) = k - N*floor(k/N)

where floor(u) is the largest integer no greater than u.  if you do
that, you need not concede the inherent periodic extension that the
DFT and iDFT imposes.  but, in my opinion, the above modulo operations
explicitly impose such a periodic extension anyway.  for me it's just
easier to say x[n+N]=x[n] and X[k+N]=X[k].

and the mapping is invertible.  really the DFT and iDFT are sorta the
same thing because they can be redefined to be "unitary" by adjusting
the constant in front of the summation:

DFT:

                     n0+N-1
    X[k] = sqrt(1/N) SUM{ x[n] * exp(-j*2*pi*n*k/N }
                     n0

for   k0 <= k < k0+N



iDFT:

                     k0+N-1
    x[n] = sqrt(1/N) SUM{ X[k] * exp(+j*2*pi*n*k/N }
                     k0

for   n0 <= n < n0+N


and +j and -j are qualitatively the same thing.  both have equal claim
to be the sqrt(-1). again n0 and k0 can be whatever integer you like.


> Does it matter if the signal x[n] is real or complex?

no.  but if x[n] is purely real you will get conjugate symmetry a.k.a
"Hermitian symmetry" in X[k], which may or may not be a useful
property.

r b-j

On May 3, 1:09&#4294967295;pm, robert bristow-johnson <r...@audioimagination.com>
wrote:
...
>
> and the mapping is invertible. &#4294967295;really the DFT and iDFT are sorta the
> same thing because they can be redefined to be "unitary" by adjusting
> the constant in front of the summation:
...
>
> and +j and -j are qualitatively the same thing. &#4294967295;both have equal claim
> to be the sqrt(-1). again n0 and k0 can be whatever integer you like.
>
...
> r b-j

It isn't clear to me from what you have posted: Do you intend the
concepts of "sorta the same thing" and "qualitatively the same thing"
to apply to items that are functions of terms that are the square
roots of any real number or only the square roots of the same negative
real numbers? (I couldn't find either term in wikipedia or in the new
or old testaments of O&S.)

Dale B. Dalrymple

robert bristow-johnson <rbj@audioimagination.com> wrote:
(snip)
 
> and +j and -j are qualitatively the same thing.  both have equal claim
> to be the sqrt(-1). again n0 and k0 can be whatever integer you like.

I have seen claims that the EE j is equivalent to -i in physics.

This comes out from the use of exp(jwt) in places where physics
uses exp(-iwt).  The distinction comes from looking at a time
and space varying signal at different times and one place, or
at different places and one time.  Or consider an oscilloscope
display and a chart recorder.

You can change all +j to -j, but some is not enough.

-- glen

On May 3, 5:09&#4294967295;pm, dbd <d...@ieee.org> wrote:
> On May 3, 1:09&#4294967295;pm, robert bristow-johnson <r...@audioimagination.com>
> wrote:
> ...
>
>
>
> > and the mapping is invertible. &#4294967295;really the DFT and iDFT are sorta the
> > same thing because they can be redefined to be "unitary" by adjusting
> > the constant in front of the summation:
> ...
>
> > and +j and -j are qualitatively the same thing. &#4294967295;both have equal claim
> > to be the sqrt(-1). again n0 and k0 can be whatever integer you like.
>
> ...
> > r b-j
>
> It isn't clear to me from what you have posted: Do you intend the
> concepts of "sorta the same thing" and "qualitatively the same thing"
> to apply to items that are functions of terms that are the square
> roots of any real number or only the square roots of the same negative
> real numbers? (I couldn't find either term in wikipedia or in the new
> or old testaments of O&S.)

this is what i mean in Wikipedia:

 http://en.wikipedia.org/wiki/Imaginary_unit#i_and_.E2.88.92i

+j and -j are qualitatively the same thing.  everything you say about
+j is something you can say about -j.  but they are quantitatively
*not* the same thing.  they are non-zero and are negatives of each
other.  they are not the same number.  but their roles can be
interchanged.  this qualitative equivalence is not true for the real
unit +1 and its negative -1.  this is why imaginary numbers are more
different than real numbers than just a matter of convention (the real
axis is qualitatively different than the imaginary axis).  but the
difference between +j and -j is merely one of convention.  and that
means that (with scaling made so that the transforms are "unitary")
the only difference between the forward and inverse Fourier Transform
(and the DFT vs. iDFT) is merely a matter of convention.


On May 3, 6:54 pm, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
> robert bristow-johnson <r...@audioimagination.com> wrote:
>
> (snip)
>
> > and +j and -j are qualitatively the same thing.  both have equal claim
> > to be the sqrt(-1).
>
...
>
> You can change all +j to -j, but some is not enough.

yup.  if all textbooks and literature in math, physics, EE or whatever
science or discipline, where changed so that +j and -j  (and +i and -
i) were switched, every fact and theorem would continue to be just as
valid.

r b-j

robert bristow-johnson <rbj@audioimagination.com> wrote:
(snip, I wrote)

>> You can change all +j to -j, but some is not enough.
 
> yup.  if all textbooks and literature in math, physics, EE or whatever
> science or discipline, where changed so that +j and -j  (and +i and -
> i) were switched, every fact and theorem would continue to be just as
> valid.

That is what they said about parity conservation before 1957.

-- glen

On May 4, 8:25&#4294967295;pm, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
> robert bristow-johnson <r...@audioimagination.com> wrote:
>
> (snip, I wrote)
>
> >> You can change all +j to -j, but some is not enough.
> > yup. &#4294967295;if all textbooks and literature in math, physics, EE or whatever
> > science or discipline, where changed so that +j and -j &#4294967295;(and +i and
> > -i) were switched, every fact and theorem would continue to be just
> > as valid.

that's a *mathematical* or conceptual equivalence (or non-preference)
of spin.

>
> That is what they said about parity conservation before 1957.
>

isn't that really a *physical* preference of spin?

for others'es information, a good reference i found is
http://physics.nist.gov/GenInt/Parity/parity.html .  so, it seems that
our universe somehow made a "choice" about which direction of rotation
is preferred.  but, suppose you woke up tomorrow in Mirror World where
everything was switched (you wrote with the other hand, the two sides
of your brain switched roles, your heart was more on what used to be
called your "right" side, etc.).  would you know the difference?

the comparison to this +j/-j thing is if *everything* in reality were
switched, not just some things.  isn't that right, Glen?

i dunno.  this atomic physics stuff is too hard for my brain.  but i
understand that if you spin some tiny atomic generator in some sense
around the z-axis and electrons fly out the bottom, you can't expect
(in the same world) to spin it in the opposite sense and see electrons
continue to fly out the same bottom.  isn't it similar to assigning a
sign to the electron charge?  once we decide (by convention) that the
electrons are negatively charged, it would be a wildly different world
if we came upon atoms that had these little particles flying about in
the atom's outside shells that were oppositely charged, no?  maybe in
such a world, the opposite spin parity would be the case, no?  (i
really don't know.  just speculating.)

r b-j

robert bristow-johnson <rbj@audioimagination.com> wrote:
 
> that's a *mathematical* or conceptual equivalence 
> (or non-preference) of spin.

(and I wrote)
>> That is what they said about parity conservation before 1957.
 
> isn't that really a *physical* preference of spin?
 
> for others'es information, a good reference i found is
> http://physics.nist.gov/GenInt/Parity/parity.html .  so, it seems that
> our universe somehow made a "choice" about which direction of rotation
> is preferred.  but, suppose you woke up tomorrow in Mirror World where
> everything was switched (you wrote with the other hand, the two sides
> of your brain switched roles, your heart was more on what used to be
> called your "right" side, etc.).  would you know the difference?

The last chapter of "Feynman's Lectures on Physics" volumne 1 is
also a nice reference, and pretty readable even if you don't
understand all the physics.
 
> the comparison to this +j/-j thing is if *everything* in reality 
> were switched, not just some things.  isn't that right, Glen?
 
> i dunno.  this atomic physics stuff is too hard for my brain.  but i
> understand that if you spin some tiny atomic generator in some sense
> around the z-axis and electrons fly out the bottom, you can't expect
> (in the same world) to spin it in the opposite sense and see electrons
> continue to fly out the same bottom.  

The Feynman explanation goes on with how to explain to a martian
which side is left.  That explanation goes indirectly through the
"right hand rule."  If you compare a physics experiment to a mirror
image of that experiment, the physics should be the same.  
Another way to say it is that if you use a "left hand rule"
instead of a "right hand rule" the physics should be the same.

The distinction comes from the cross product, and axial vector
quantities such as angular momentum (spin) should not correlate 
with normal (polar) vector quantities such as velocity.  

As for your spin explanation, if you spin it in one sense, and
more electrons come out the bottom than the top, you already have
a parity violation.  Conserved parity would require the same 
probability for electrons to come out the top as the bottom.

> isn't it similar to assigning a
> sign to the electron charge?  once we decide (by convention) that the
> electrons are negatively charged, it would be a wildly different world
> if we came upon atoms that had these little particles flying about in
> the atom's outside shells that were oppositely charged, no?  maybe in
> such a world, the opposite spin parity would be the case, no?  (i
> really don't know.  just speculating.)

After parity violation was found in 1957, it was expected that CP
would be conserved.  That is, that antimatter would have exactly
the opposite properties.  It turns out that CP is also not conserved,
but only slightly.  It seems that symmetry operations guarantee
that CPT is conserved.  That is, if you take a mirror coordinate
system, change matter to antimatter, and invert the direction of
time, it is required that the physics be the same.  I don't know
it well enough to explain that one, though.

-- glen