shift theorem

jim wrote:
> 
> "Peter K." wrote:
> 
>>jim wrote:
>>
>>
>>>I know that's what you are saying - that is what I have been saying
>>>you are saying.
>>>
>>
>>Say what?
> 
> 
> I give Robert a hard time, but to his credit I do believe he's the only
> one following.
> 
> If you recall this started because I said Robert assumes that the k in
> the y[n-k] of the shift theorem had to be an integer. In other words he
> defines k as an integer and Robert will not allow it to be defined as
> anything else. Now is there anything in the math of the shift theorem
> that will not work if k is a non-integer value? No there isn't, so there
> is nothing but a definition keeping it from being a non-integer.
> 	So what if we made k non-integer like say 0.5. You would then have a
> sequence y[n] whose indices look like [....-1.5,-.5,+.5,+1.5,+2.....].
> That wasn't all that difficult to define.  Now what does the shift
> theorem tell us about a frame of numbers ordered and enumerated as
> described above? What happens when those indices are used to perform a
> DFT on that sequence indexed in that manner?
> 	If k is restricted to an integer then we can assert that the DFT
> behaves as if y[n]=y[n-N] where N is the length of the DFT frame. That
> is the sequence can be periodically extended with a period of N. If k is
> not an integer that equality is no longer true.

I can sort of understand what a two-and-a-hafth anniversary is (even 
though the word strongly implies one-year intervals), but what about the 
two-and-a-hafth car in a train? Some things are whole and pointers to 
them are integers. Times when we can ignore that constraint are a bonus, 
but they don't mean the constraint isn't real.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Jerry Avins wrote:

> I can sort of understand what a two-and-a-hafth anniversary is (even
> though the word strongly implies one-year intervals), but what about
> the two-and-a-hafth car in a train?

I'll meet you on Platform 9-3/4!

> Some things are whole and pointers to
> them are integers. Times when we can ignore that constraint are a
> bonus, but they don't mean the constraint isn't real.

I haven't followed the thread but, as far as I can see, the only thing
wrong with trying to delay something by a fractional sample period is
that the LTI system that does this is non-causal (in discrete-time).
The frequency domain representation of the delay is straightforward.

I'll have to go back and read the thread...

Ciao,

Peter K.

in article 424b4965$1_1@127.0.0.1, jim at "N0sp"@m.sjedging@mwt.net wrote on
03/30/2005 19:50:

> If you recall this started because I said Robert assumes that the k in
> the y[n-k] of the shift theorem had to be an integer.

to be more precise, i say that anything that goes between the little square
brackets of y[..] or any other discrete-whatever sequence has to be an
integer.

> In other words he defines k as an integer and Robert will not allow it to
> be defined as anything else.

in the expression of y[n-k] (assuming n is an integer).

i never said that you can't multiply Y[m] = DFT{ y[n] } by
exp(-j*2*pi*k*m/N) and see what comes out when you inverse DFT.  i just said
that you have to be careful about what, exactly you mean.

for integer k, what comes out is y[mod(n-k,N)] if you insist that there is
no periodic extension of y[n] (but i say that mod() operator is precisely a
periodic extension of y[n]), or you can say it's simply y[n-k], but then you
have to understand that y[n] was periodically extended (except for k=0 which
is a trivial case).  if k is not an integer, you get another mess with the
dirichlet kernal in it which is also a periodic function with period N.

> Now is there anything in the math of the shift theorem
> that will not work if k is a non-integer value? No there isn't, so there
> is nothing but a definition keeping it from being a non-integer.
> So what if we made k non-integer like say 0.5. You would then have a
> sequence y[n] whose indices look like [....-1.5,-.5,+.5,+1.5,+2.....].

no, you have a sequence (i wouldn't call it y[n] because it does not, in
general, take on any of the values of y[n]) that has integer indices.
non-integer indices are non-sensical.  defining a continuous function that
equals y[n] for integers is fine, and that is a topic of interpolation.

> That wasn't all that difficult to define.  Now what does the shift
> theorem tell us about a frame of numbers ordered and enumerated as
> described above? What happens when those indices are used to perform a
> DFT on that sequence indexed in that manner?

you don't have those indices.  those indices are crap ... nonsense.

the real question is, given knowledge of what the original sequence, y[n],
what does multiplication of Y[m] by exp(-j*2*pi*k*m/N) do?  this is the
challenge you were emitting that supposedly says that y[n] is not
periodically extended by the DFT.  this has an answer, and it does nothing
to refute the inherent circular nature of the DFT.  in fact, it confirms it.

let     DFT{ w[n] }  =def   W[m] = Y[m] * exp(-j*2*pi*k*m/N)


the inverse DFT:

w[n] =

N-1
SUM{y[i]*exp(-j*pi*(n-k-i)*(N-1)/N)*sin(pi*(n-k-i))/(N*sin(pi*(n-k-i)/N))}
i=0

is a periodic function in n with period N.

in this expression, no values of y[i] are needed outside of 0 <= i < N .

but if you were to split your delay, k, into integer and fractional parts,
that mess above gets simpler, but ONLY if you understand y[i] to be periodic
with period N.  otherwise you will either have messy limits on the summation
or fill it up with mod(i,N) expressions everywhere (which just reconfirms
that y[n] has been periodically extended).  but in any case, even if you
choose not to simplify your life by periodically extending y[n], the integer
or fractionally delayed result, w[n] is periodic with period N.


     N-1
w[n]=SUM{y[n+i]*exp(-j*pi*(i+k)*(N-1)/N)*sin(pi*(i+k))/(N*sin(pi*(i+k)/N))}
     i=0


if you split k into integer (floor(k)) and fractional (k-floor(k)) parts,
you can put y[n-floor(k)+i] and replace the other occurrences of k with the
fractional part.  but this only works if y[n] is understood to be periodic
with period N.


> If k is restricted to an integer then we can assert that the DFT
> behaves as if y[n]=y[n-N] where N is the length of the DFT frame. That
> is the sequence can be periodically extended with a period of N. If k is
> not an integer that equality is no longer true.

the w[n] = y[n-k] equality isn't there (because, for fractional k, y[n-k]
does not exist), but the periodic nature continues to be there.  the result
is a sorta "convolution" of the original y[n] with that dirichlet thingie,
which is periodic with period N.  if you plug into k an integer, the same
result can be used and it will explicitly become y[mod(n-k,N)] which is the
circularly shifted y[n-k].  the inherent periodic is confirmed.

this fractional sample delay and the dirichlet thingie is smoke.  a red
herring.  maybe smoked red herring.  it speaks nothing to the issue at hand
(which, to remind everyone, is whether or not the DFT views the data
supplied to it as one period of a periodic sequence), and, as far as i can
see, only serves to distract from it.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

in article 1112238615.483528.312830@g14g2000cwa.googlegroups.com, Peter K.
at p.kootsookos@iolfree.ie wrote on 03/30/2005 22:10:

> I haven't followed the thread but, as far as I can see, the only thing
> wrong with trying to delay something by a fractional sample period is
> that the LTI system that does this is non-causal (in discrete-time).

also, even if the input data is real, the fractionally delayed data coming
out is complex unless you apply a different multiplication to the 2nd half
of the DFT data (that usually corresponds to negative frequencies in common
practice) and if N is even, then you gotta do something else to the Nyquist
term at N/2 (which changes the math from that dirichlet thingie to something
slightly different).  jim also objects to that or had in the past.

> The frequency domain representation of the delay is straightforward.

ugly (and even uglier if no inherent periodic extension of the DFT data),
but straightforward.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

Jerry Avins wrote:

> 
> I can sort of understand what a two-and-a-hafth anniversary is (even
> though the word strongly implies one-year intervals), but what about the
> two-and-a-hafth car in a train? Some things are whole and pointers to
> them are integers. Times when we can ignore that constraint are a bonus,
> but they don't mean the constraint isn't real.
> 

I don't think your analogies are germaine or useful to what is being
discussed. My point was never to discuss the merits of the definitions
and the assumptions that are held by convention. My point was simply
that the DFT is not the one making those assumptions. 

	But since everyone else seems to want to focus on the merits of the
assumptions - let's atleast be clear what we are talking about. The
issue at hand really just boils down to exactly where in relation to a
sequence of samples we place t=0. By convention most of the time (I say
most of the time because there are exceptions) we do not allow t=0 to
land between 2 samples. This is indeed a constraint. Is it realistic? 
No, its about as artificial as anything can be (that statement is not
intended as a criticism its just a fact). Is it useful? It certainly
makes lots of things a lot simpler - so yes that seems useful. Is the
convention likely to be changed? No not likely - altho from what I hear
the way they're designing trains in Europe and Japan its dificult to
tell where one train car begins and the next one ends - so you never
know how things will be defined in the future.

-jim

----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

jim wrote:
> 
> Jerry Avins wrote:
> 
> 
>>I can sort of understand what a two-and-a-hafth anniversary is (even
>>though the word strongly implies one-year intervals), but what about the
>>two-and-a-hafth car in a train? Some things are whole and pointers to
>>them are integers. Times when we can ignore that constraint are a bonus,
>>but they don't mean the constraint isn't real.
>>
> 
> 
> I don't think your analogies are germaine or useful to what is being
> discussed. My point was never to discuss the merits of the definitions
> and the assumptions that are held by convention. My point was simply
> that the DFT is not the one making those assumptions. 
> 
> 	But since everyone else seems to want to focus on the merits of the
> assumptions - let's atleast be clear what we are talking about. The
> issue at hand really just boils down to exactly where in relation to a
> sequence of samples we place t=0. By convention most of the time (I say
> most of the time because there are exceptions) we do not allow t=0 to
> land between 2 samples. This is indeed a constraint. Is it realistic? 
> No, its about as artificial as anything can be (that statement is not
> intended as a criticism its just a fact). Is it useful? It certainly
> makes lots of things a lot simpler - so yes that seems useful. Is the
> convention likely to be changed? No not likely - altho from what I hear
> the way they're designing trains in Europe and Japan its dificult to
> tell where one train car begins and the next one ends - so you never
> know how things will be defined in the future.
> 
> -jim

Whoa! I was addressing the periodicity issue. I read you as claiming 
that a DFT imposes periodic extension on the data only when one assumes 
that it does, and that the assumption of periodicity may be freely 
discarded. The analogy I put forth was intended to show that while 
periodicity (like the poor) is always with us, it can sometimes be 
ignored (like the poor).

The only assumptions involved in computing the amplitudes of the 
fundamental and odd-harmonic distortion components in a perfectly 
symmetric push-pull amplifier are that lower harmonics tell enough of 
the story, and that there is a solution in sines for 5 measured points 
plus one necessarily zero. The procedure I outlined amounts to a DFT (or 
the solution to 6 simultaneous transcendental equations), and works by 
turning the crank on 5 variables that represent five ordinates of a half 
cycle of the waveform. The result is a set of amplitudes for a set of 
sines of known frequency. The time information can be reconstructed with 
a classic IDFT or by summing the magnitudes of the various sines at any 
instant in question. Either method of reconstruction produces a periodic 
result without invoking any further assumption. (I suppose that the 
existence of a solution to the simultaneous equations outside the 
interval containing the measurements is an assumption, but I see that as 
the assumption that the math means what it says.)

It doesn't matter where the origin of time is unless, as in the simple 
analysis outlined above, we want all sines of some similar constraint. 
The labels don't needs to be integers, but intervals between specified 
instants do. The indices of elements in a sequence are also integers if 
the notation is to make sense. That doesn't prevent reference to an 
element corresponding to t=1.384.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Ok Jerry, your debating skills are better than mine

But let's cut to the chase.

Here's the shift theorem as presented by Robert. 

DFT{ y[n-k] }  =  exp(-j*2*pi*k*m/N) * Y[m]

Will you permit k to be a non-integer?
And if yes, will this DFT have a period of N when k is non-integer?

-jim 

Jerry Avins wrote:
> 
> jim wrote:
> >
> > Jerry Avins wrote:
> >
> >
> >>I can sort of understand what a two-and-a-hafth anniversary is (even
> >>though the word strongly implies one-year intervals), but what about the
> >>two-and-a-hafth car in a train? Some things are whole and pointers to
> >>them are integers. Times when we can ignore that constraint are a bonus,
> >>but they don't mean the constraint isn't real.
> >>
> >
> >
> > I don't think your analogies are germaine or useful to what is being
> > discussed. My point was never to discuss the merits of the definitions
> > and the assumptions that are held by convention. My point was simply
> > that the DFT is not the one making those assumptions.
> >
> >       But since everyone else seems to want to focus on the merits of the
> > assumptions - let's atleast be clear what we are talking about. The
> > issue at hand really just boils down to exactly where in relation to a
> > sequence of samples we place t=0. By convention most of the time (I say
> > most of the time because there are exceptions) we do not allow t=0 to
> > land between 2 samples. This is indeed a constraint. Is it realistic?
> > No, its about as artificial as anything can be (that statement is not
> > intended as a criticism its just a fact). Is it useful? It certainly
> > makes lots of things a lot simpler - so yes that seems useful. Is the
> > convention likely to be changed? No not likely - altho from what I hear
> > the way they're designing trains in Europe and Japan its dificult to
> > tell where one train car begins and the next one ends - so you never
> > know how things will be defined in the future.
> >
> > -jim
> 
> Whoa! I was addressing the periodicity issue. I read you as claiming
> that a DFT imposes periodic extension on the data only when one assumes
> that it does, and that the assumption of periodicity may be freely
> discarded. The analogy I put forth was intended to show that while
> periodicity (like the poor) is always with us, it can sometimes be
> ignored (like the poor).
> 
> The only assumptions involved in computing the amplitudes of the
> fundamental and odd-harmonic distortion components in a perfectly
> symmetric push-pull amplifier are that lower harmonics tell enough of
> the story, and that there is a solution in sines for 5 measured points
> plus one necessarily zero. The procedure I outlined amounts to a DFT (or
> the solution to 6 simultaneous transcendental equations), and works by
> turning the crank on 5 variables that represent five ordinates of a half
> cycle of the waveform. The result is a set of amplitudes for a set of
> sines of known frequency. The time information can be reconstructed with
> a classic IDFT or by summing the magnitudes of the various sines at any
> instant in question. Either method of reconstruction produces a periodic
> result without invoking any further assumption. (I suppose that the
> existence of a solution to the simultaneous equations outside the
> interval containing the measurements is an assumption, but I see that as
> the assumption that the math means what it says.)
> 
> It doesn't matter where the origin of time is unless, as in the simple
> analysis outlined above, we want all sines of some similar constraint.
> The labels don't needs to be integers, but intervals between specified
> instants do. The indices of elements in a sequence are also integers if
> the notation is to make sense. That doesn't prevent reference to an
> element corresponding to t=1.384.
> 
> Jerry
> --
> Engineering is the art of making what you want from things you can get.
> �����������������������������������������������������������������������

----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

"jim" <"N0sp"@m.sjedging@mwt.net> wrote in message 
news:424c297d$1_1@127.0.0.1...
> Ok Jerry, your debating skills are better than mine
>
> But let's cut to the chase.
>
> Here's the shift theorem as presented by Robert.
>
> DFT{ y[n-k] }  =  exp(-j*2*pi*k*m/N) * Y[m]
>
> Will you permit k to be a non-integer?
> And if yes, will this DFT have a period of N when k is non-integer?
>
> -jim
>

Hello Jim,

It depends which path you chose to follow. If you let k be nonintegral, you 
through out the completeness of the DFT's basis set. Or you are going to 
have to define an interesting basis set which is nonstandard.

I always recall a similar thing that arises in the Goertzel algo where 
someone wishes to use a non integral k. For some applications this may work, 
but Parseval's theorem which is often used when the Goertzel is used (I.e., 
DTMF decoding) is no longer strictly true. You end up with a fractional wave 
whose integral is not zero. The k being an integer or not in the Goertzel 
algo depends on the viewing of the algo as being derived from a filter or 
from the DFT. But if k is not an integer, some of the DFT's properties need 
to be modified.

To see these issues look at the normalization when you have a non integral k 
in the DFT.

Clay

> "jim" <"N0sp"@m.sjedging@mwt.net> wrote in message
> news:424c297d$1_1@127.0.0.1...
>> Ok Jerry, your debating skills are better than mine

his debating skills are good, but whether they are or not, it can't beat the
math.

>> Here's the shift theorem as presented by Robert.

and the textbooks (substitute "x" for "y" and "n0" for "k" and "k" for "m").

>> DFT{ y[n-k] }  =  exp(-j*2*pi*k*m/N) * Y[m]

cause is on the left and effect is on the right.

>> Will you permit k to be a non-integer?

be specific, Jim.  "k" where?  on the right of the = sign, there is some
meaning.  on the left there is no meaning for non-integer k.  so the
specific question to ask is what is the inverse DFT of the expression on the
right when k is non-integer?  will you answer that?  then we can argue about
your next question (when properly phrased):

>> And if yes, will this DFT have a period of N when k is non-integer?

the DFT is an operator, specifically what sequence do you mean?  (oh, hell,
they *all* have period N, but Jim should spell out precisely which sequence
or function he means when he asks the question.)
 
in article I3W2e.12789$f%4.8179@bignews1.bellsouth.net, Clay S. Turner at
Physics@Bellsouth.net wrote on 03/31/2005 12:09:

> 
> It depends which path you chose to follow. If you let k be nonintegral, you
> through out the completeness of the DFT's basis set.

trying to extrapolate ... do you mean "throw out"?  (i think i agree with
that.)


-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

jim wrote:
> Ok Jerry, your debating skills are better than mine

Not really. A story is in order. Back when stump speeches were often 
made by a candidate standing on a stump, one debater, finding no stump 
available, stood instead on a barrel head. In the midst of his speech, 
the head broke and he fell into the barrel. Unhurt, he climbed out and 
standing on the rim said, "You see, folks? the weight of my argument can 
always be depended upon to carry me through." But maybe he was all wet.

> But let's cut to the chase.
> 
> Here's the shift theorem as presented by Robert. 
> 
> DFT{ y[n-k] }  =  exp(-j*2*pi*k*m/N) * Y[m]
> 
> Will you permit k to be a non-integer?
> And if yes, will this DFT have a period of N when k is non-integer?

k can be a non integer. It is only necessary that n-k be an integer so a 
meaning could be assigned to it. y[n-k] specifies the (n-k)th y in a 
sequence of y's; which one?

   ...

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������