shift theorem

in article 1112178235.951796.102270@o13g2000cwo.googlegroups.com, Andor at
an2or@mailcircuit.com wrote on 03/30/2005 05:23:

> Ah robert, to be honest, I'm at issue with both of your points. Jim
> mentioned non-integer indeces, and you mention negative indices. If you
> take the linear algebra view (after all, the DFT is just another
> unitary transform, as I wrote above), then a vector has indices ranging
> from 1 to N (or 0 to N-1 :-), all other indices are not applicable.
> 
> One very nice property of the DFT is that it diagonlizes the shift
> operator (which cyclically rotates the elements in a vector) --- no
> periodic sequences are required to state the shift theorem.

when you say:

         DFT{ x[mod(n-d, N)] }  =  exp(-j*2*pi*k*d/N) * X[k]

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

    and floor(v) is the largest integer no greater than v.

that is an expression of your cyclical rotation.  it is also one and the
same to periodically extending x[n].

> However, a periodic extension of a vector into an infinite sequence
> holds exactly the same information as the view of cyclically rotating
> its elements, therefore it is a valid view, albeit one that requires
> introducing new objects (infinitely long periodic sequences)

but it removes the mod() operator.  that is why it is more elegant or
compact in its expression.

> which are not ammenable to linear algebra,

dunno why that would be.

> in contrast to introducing the shift operator.

you mean the _circular_ shift operator.

> I prefer to work with vectors in a vector space. It seems you
> prefer periodic sequences.

call them vectors, sequences, infinite sequences, functions of
discrete-time, sampled signals, whatever, i don't care.  i just prefer to
look at these signals in the most fundamental manner to keep me from goofing
things up.  fundamentally, when you pass N samples (however you call it) to
a DFT or iDFT operator, again to anthropomorhize a little, the DFT
understands those N samples to be taken from a periodic discrete-time signal
of period N (even if it was taken from some other stream of samples).  that
is what i mean when i say that "the DFT inherently periodically extends the
data passed to it."  keep that in mind, and you won't have to conceptually
worry about the mod() operator for shifting of convolution.

> It doesn't matter.

except that my position is "mind-numbingly stupid".


-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

robert bristow-johnson wrote:
> Andor wrote:
>
> > Ah robert, to be honest, I'm at issue with both of your points. Jim
> > mentioned non-integer indeces, and you mention negative indices. If
you
> > take the linear algebra view (after all, the DFT is just another
> > unitary transform, as I wrote above), then a vector has indices
ranging
> > from 1 to N (or 0 to N-1 :-), all other indices are not applicable.
> >
> > One very nice property of the DFT is that it diagonlizes the shift
> > operator (which cyclically rotates the elements in a vector) --- no
> > periodic sequences are required to state the shift theorem.
>
> when you say:
>
>          DFT{ x[mod(n-d, N)] }  =  exp(-j*2*pi*k*d/N) * X[k]
>
> where mod(n, N)  =   n - N*floor(n/N)
>
>     and floor(v) is the largest integer no greater than v.
>
> that is an expression of your cyclical rotation.  it is also one and
the
> same to periodically extending x[n].

Of course. My next paragraph shows I agree with that:

> > However, a periodic extension of a vector into an infinite sequence
> > holds exactly the same information as the view of cyclically
rotating
> > its elements, therefore it is a valid view, albeit one that
requires
> > introducing new objects (infinitely long periodic sequences)
>
> but it removes the mod() operator.  that is why it is more elegant or
> compact in its expression.

I'm of the opposite oppinion, see below.

> > which are not ammenable to linear algebra,
>
> dunno why that would be.

Because it's more elegant --- all the properties of the DFT (such as
said diagonalization property of left and right shift operators) can be
viewed in context with more general class of operators with similar
properties [1]. The language of linear algebra allows a more fruitful
approach than ad hoc interpretations such as the periodic extension of
a vector.

> > in contrast to introducing the shift operator.
>
> you mean the _circular_ shift operator.

Call it what you want.

>
> > I prefer to work with vectors in a vector space. It seems you
> > prefer periodic sequences.
>
> call them vectors, sequences, infinite sequences, functions of
> discrete-time, sampled signals, whatever, i don't care.  i just
prefer to
> look at these signals in the most fundamental manner to keep me from
goofing
> things up.

It seems you and I disagree on what the most fundamental manner is.

>  fundamentally, when you pass N samples (however you call it) to
> a DFT or iDFT operator, again to anthropomorhize a little, the DFT
> understands those N samples to be taken from a periodic discrete-time
signal
> of period N (even if it was taken from some other stream of samples).
 that
> is what i mean when i say that "the DFT inherently periodically
extends the
> data passed to it."  keep that in mind, and you won't have to
conceptually
> worry about the mod() operator for shifting of convolution.

I don't worry about it. It comes naturally :-).

>
> > It doesn't matter.
>
> except that my position is "mind-numbingly stupid".

Stop sulking :-).

Regards,
Andor

[1] See eg. the first paper on this page:
http://www.ece.cmu.edu/~smart/papers/autgen.html

The reference [1] does not seem exactly what I wanted, perhaps this (by
the same authors) is a little less algebraic and more aimed towards
signal processing:

Sebastian Egner and Markus P=FCschel:
"Automatic Generation of Fast Discrete Signal Transforms"
IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 49, NO. 9, SEPTEMBER 2001

Andor wrote:
> robert bristow-johnson wrote:
> 
>>>Andor wrote:
>>>
>>>>Let v be a vector in a n-dimensional Hilbert space V.  Assume
> 
> {e_1, ...
> 
>>>>, e_n} is a basis for V, and {v_1, ... , v_n} be the
> 
> representation of
> 
>>>>v in that basis. Now let D be a unitary map from V to itself, and
> 
> w :=
> 
>>>>D v = {w_1, ... , w_n} be the image of v under D.
>>>>
>>>>Where on earth do you get the idea that anything such as w_k for k
> 
> not
> 
>>>>in {1,2,...,n} should be defined?
> 
> 
> ...
> 
> 
>>it's an interpretation (a valid one, IMO) of what Jim is saying.
> 
> 
> [snipping DFT formalisms]
> 
> Ah robert, to be honest, I'm at issue with both of your points. Jim
> mentioned non-integer indeces, and you mention negative indeces. If you
> take the linear algebra view (after all, the DFT is just another
> unitary transform, as I wrote above), then a vector has indeces ranging
> from 1 to n (or 0 to n-1 :-), all other indeces are not applicable.
> 
> One very nice property of the DFT is that it diagonlizes the shift
> operator (which cyclically rotates the elements in a vector) --- no
> periodic sequences are required to state the shift theorem.
> 
> However, a periodic extension of a vector into an infinite sequence
> holds exactly the same information as the view of cyclically rotating
> its elements, therefore it is a valid view, albeit one that requires
> introducing new objects (infinitely long periodic sequences) which are
> not ammenable to linear algebra, in contrast to introducing the shift
> operator. I prefer to work with vectors in a vector space. It seems you
> prefer periodic sequences. It doesn't matter.
> 
> Regards,
> Andor

Andor,

I'm sitting here and smirking in my ignorance at the way that everybody 
seems to be obscuring the issue with mathematics.

My introduction to discrete Fourier transforms (although I couldn't put 
a name to it) came with the design of Class B audio amplifiers. Using 
the characteristic curves, it is possible to plot the output wave shape 
that results from an input sine wave. Assuming +/- symmetry (i.e. the 
absence of odd harmonics), only a half cycle is needed. Pick off the 
values at 15, 30, 45, 60. and 75 degrees -- neither 0 nor 90 are 
interesting: this is really a sine transform -- plug them into a formula 
(someone else figured the twiddle factors) -- and compute harmonics up 
to the 11th. (If the even ones aren't attributable to round-off, you 
goofed.) If the results don't meet spec, pick a different bias and try 
again. Negative feedback ended the need for all that. Gott sei dank!

The point is, the amplitudes of a bunch of sine waves come out of that 
analysis. Plotting their sum instead of inspecting their magnitudes 
recreates the original waveform. Not just for the half cycle you 
measured, but for ever and ever, wave without end, Amen. Just what does 
"periodic" mean, anyway?

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

in article 1112203814.542593.236940@l41g2000cwc.googlegroups.com, Andor at
an2or@mailcircuit.com wrote on 03/30/2005 12:30:

> robert bristow-johnson wrote:
>> Andor wrote:
>> 
>>> Ah robert, to be honest, I'm at issue with both of your points. Jim
>>> mentioned non-integer indeces, and you mention negative indices. If you
>>> take the linear algebra view (after all, the DFT is just another
>>> unitary transform, as I wrote above), then a vector has indices ranging
>>> from 1 to N (or 0 to N-1 :-), all other indices are not applicable.
>>> 
>>> One very nice property of the DFT is that it diagonlizes the shift
>>> operator (which cyclically rotates the elements in a vector) --- no
>>> periodic sequences are required to state the shift theorem.
>> 
>> when you say:
>> 
>> DFT{ x[mod(n-d, N)] }  =  exp(-j*2*pi*k*d/N) * X[k]
>> 
>> where mod(n, N)  =   n - N*floor(n/N)
>> 
>> and floor(v) is the largest integer no greater than v.
>> 
>> that is an expression of your cyclical rotation.  it is also one and the
>> same to periodically extending x[n].
> 
> Of course. My next paragraph shows I agree with that:

careful.  that might make you (or your position) mind-numbingly stupid, too.

>>> However, a periodic extension of a vector into an infinite sequence
>>> holds exactly the same information as the view of cyclically rotating
>>> its elements, therefore it is a valid view, albeit one that requires
>>> introducing new objects (infinitely long periodic sequences)
>> 
>> but it removes the mod() operator.  that is why it is more elegant or
>> compact in its expression.
> 
> I'm of the opposite oppinion, see below.
> 
>>> which are not ammenable to linear algebra,
>> 
>> dunno why that would be.
> 
> Because it's more elegant --- all the properties of the DFT (such as
> said diagonalization property of left and right shift operators) can be
> viewed in context with more general class of operators with similar
> properties [1].

i'll look at an on-line reference, when you get one that you like, but i'm
not buying a book (or an IEEE paper) at the moment.

> The language of linear algebra allows a more fruitful approach than
> ad hoc interpretations such as the periodic extension of a vector.

how is it "ad hoc"?

>>> in contrast to introducing the shift operator.
>> 
>> you mean the _circular_ shift operator.
> 
> Call it what you want.

how 'bout if i call it the _linear_ shift operator?  can you live with that?
(i don't think so.)

>>> I prefer to work with vectors in a vector space. It seems you
>>> prefer periodic sequences.
>> 
>> call them vectors, sequences, infinite sequences, functions of
>> discrete-time, sampled signals, whatever, i don't care.  i just prefer to
>> look at these signals in the most fundamental manner to keep me from goofing
>> things up.
> 
> It seems you and I disagree on what the most fundamental manner is.

you either say "mod(n-d, N)" and i say "n-d" or you must say that "the
circular indexing of x[n]" is implied and i say that "x[n] is periodically
extended".  it has to be one or the other, i think.

>> fundamentally, when you pass N samples (however you call it) to
>> a DFT or iDFT operator, again to anthropomorhize a little, the DFT
>> understands those N samples to be taken from a periodic discrete-time signal
>> of period N (even if it was taken from some other stream of samples).  that
>> is what i mean when i say that "the DFT inherently periodically extends the
>> data passed to it."  keep that in mind, and you won't have to conceptually
>> worry about the mod() operator for shifting of convolution.
> 
> I don't worry about it. It comes naturally :-).

no.  you gotta say *something* to define n-d unless 0 <= n-d < N.

which is more natural or elegant to say:

    DFT{ x[mod(n-d, N)] }  =  exp(-j*2*pi*k*d/N) * X[k]
or 
    DFT{ x[n-d] }          =  exp(-j*2*pi*k*d/N) * X[k]
?

at least we can say that one expression takes more ink or more keystrokes.
if you say that the modulo operator is implied (which is fine, but you gotta
lay that out at the outset), then i say an implied modulo address of the
elements of the length N vector are precisely the same as periodic extension
of the N samples of x[n] supplied to the DFT.

>>> It doesn't matter.
>> 
>> except that my position is "mind-numbingly stupid".
> 
> Stop sulking :-).

boo-hoo.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

in article 3u-dnd-UNdd6cNffRVn-2w@rcn.net, Jerry Avins at jya@ieee.org wrote
on 03/30/2005 13:20:

> but for ever and ever, wave without end, Amen.

:-)

sounds like Jerry's been to church.

(in the beginning was the wave ...)

string theorists might like it.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

robert bristow-johnson wrote:

...
> > Because it's more elegant --- all the properties of the DFT (such
as
> > said diagonalization property of left and right shift operators)
can be
> > viewed in context with more general class of operators with similar
> > properties [1].
>
> i'll look at an on-line reference, when you get one that you like,
but i'm
> not buying a book (or an IEEE paper) at the moment.

The link I gave has the second paper I posted (the one from the IEEE
transactions) at the third position (maybe I should check the links I
give more thoroughly :-). Try that.

> > The language of linear algebra allows a more fruitful approach than
> > ad hoc interpretations such as the periodic extension of a vector.
>
> how is it "ad hoc"?

It's not embedded in a comprehensive theory, such as linear algebra.
While a valid interpretation, it stands alone and cannot be used to
gain further insight.

> >>> in contrast to introducing the shift operator.
> >>
> >> you mean the _circular_ shift operator.
> >
> > Call it what you want.
>
> how 'bout if i call it the _linear_ shift operator?  can you live
with that?
> (i don't think so.)

Ok, I get what you mean. Yes, I mean the invertible cyclic/circular
shift operator.

> you either say "mod(n-d, N)" and i say "n-d" or you must say that
"the
> circular indexing of x[n]" is implied and i say that "x[n] is
periodically
> extended".  it has to be one or the other, i think.

We agreed on that already above. The point of mod or period is not
important, the important part is that the linear algebra point of view
(which knows no periodic sequences, just vectors and linear maps) gives
us more insight.

I don't think there is much more to say about the pros/cons on this
issue without repeating myself.

Regards,
Andor Bariska-Furcas
(I married too!)

Jerry,

I think Gauss used, or rather invented the DFT much in the same way
that you used it, to compute harmonics of a periodic function.

It's just that since the 200 years since its discovery (hey, an
anniversary!), the DFT has been embedded in a rich theory that gives
fascinating insight into other topics (some are mentioned in that link
I posted). Admittedly, sometimes this blurs the essentials at hand.
Specially on usenet, where posts are usually more qualitative than
quantitative :-).

Regards,
Andor

robert bristow-johnson wrote:
> in article 3u-dnd-UNdd6cNffRVn-2w@rcn.net, Jerry Avins at jya@ieee.org wrote
> on 03/30/2005 13:20:
> 
> 
>>but for ever and ever, wave without end, Amen.
> 
> 
> :-)
> 
> sounds like Jerry's been to church.

As it happens, both yesterday and on Good Friday. Funerals.

> (in the beginning was the wave ...)
> 
> string theorists might like it.

:-)

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

"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.

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