Prev: AQuA Powered Asterisk Voice Quality Monitoring Solution
Next: Fast, accurate frequency estimators
From: fisico32 on 3 May 2010 08:57
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
From: Rune Allnor on 3 May 2010 09:12
On 3 Mai, 14:57, "fisico32" <marcoscipioni1(a)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
From: dvsarwate on 3 May 2010 10:30
On May 3, 7:57 am, "fisico32" <marcoscipioni1(a)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


From: Rune Allnor on 3 May 2010 11:05
On 3 Mai, 16:30, dvsarwate <dvsarw...(a)gmail.com> wrote:
> On May 3, 7:57 am, "fisico32" <marcoscipioni1(a)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?

Because the DFT works on finite sequences of discrete data.
Changing the indexes only change the 'names' of the individual
samples, and have no effects on the samples themselves.
The only effect a change of indexes is to shift the phase reference,
which is confined to the matrix W.

Rune
From: dvsarwate on 3 May 2010 12:56
On May 3, 10:05 am, Rune Allnor <all...(a)tele.ntnu.no> claimed:

>
> Because the DFT works on finite sequences of discrete data.

I am sure there are those on this forum who will
dispute that claim and say that DFTs implicitly
assume periodic sequences, but let me ask with
respect to the specific point that I raised about
the OP's question. The OP asked

>> 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?

to which I responded in part that

> 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]

So, could you tell us what rule you are using
to ascribe values to x[-4], x[-3], x[-2], and x[-1]
so as to make x[-4] + x[-3] + x[-2] + x[-1] equal
x[2] + x[3]? And if you want to bring in phases
etc., I ask that you pick any k: 0, 1, 2, or 3
and explain how you get X[0] in one case to
equal bX[k] in the other where b is some complex
number of magnitude 1. Remember that X[0]
is no more and no less than x[0] + x[1] + x[2] + x[3]
in one sum envisioned by the OP, while the bX[k],
obtained via the other sum envisioned by the OP
involves the six numbers x[-4], ..., x[1] since his
index of summation runs from -N = -4 in this
simple case to (N/2) - 1 = 1 in this simple case.
Be sure to tell us what rule(s) you use to ascribe
values to x[-4] and x[-3] and x[-2] and x[-1]. I
ask this because I have finally after all these years
figured out summation notation but am still a bit
hazy about matrices.

--Dilip Sarwate



 |  Next  |  Last
Pages: 1 2 3
Prev: AQuA Powered Asterisk Voice Quality Monitoring Solution
Next: Fast, accurate frequency estimators