fourier transform - time domain to frequency domain and vice versa

On Tue, 9 Oct 2012 02:25:03 +0000 (UTC), glen herrmannsfeldt
<gah@ugcs.caltech.edu> wrote:

>Eric Jacobsen <eric.jacobsen@ieee.org> wrote:
>
>(snip)
>
>> It is a misconception that the derivation or understanding of the
>> DFT/FFT "assumes" or requires that the input vector repeats
>> continuously, i.e.,  (x[i] = x[i+N])
>
>OK, not assumes, but it is based on the solutions to a
>differential equation with periodic boundary conditions.
>
>> I know you may disagree and I'm inclined to ignore any attempt to drag
>> this into yet another discussion on the topic.   Your views are well
>> known.
>
>
>-- glen

You've mentioned that before, but I'm not directly familiar with that
treatment. There are some common approaches that assume periodicity in
order to simplify the analysis and I think these are what lead people
to believe that it is a property or requirement when using a DFT/FFT.

It is not necessary to make that assumption, and one can do so without
a loss of generality:

http://www.dsprelated.com/showarticle/175.php


Eric Jacobsen
Anchor Hill Communications
www.anchorhill.com

Eric Jacobsen <eric.jacobsen@ieee.org> wrote:

(snip)
>>> It is a misconception that the derivation or understanding of the
>>> DFT/FFT "assumes" or requires that the input vector repeats
>>> continuously, i.e.,  (x[i] = x[i+N])

(snip, then I wrote)
>>OK, not assumes, but it is based on the solutions to a
>>differential equation with periodic boundary conditions.

(snip)

> You've mentioned that before, but I'm not directly familiar with that
> treatment. There are some common approaches that assume periodicity in
> order to simplify the analysis and I think these are what lead people
> to believe that it is a property or requirement when using a DFT/FFT.

I especially remember it as some years ago I was trying to understand
why the DCT was so popular. That is, what the DCT does that DFT and DST
don't to. Maybe it was obvious to everyone else, but I finally
found it in "Numerical Recipes."

The answer is that the DFT has periodic boundary conditions, 
the DST has the boundary go to zero, and the DCT the derivative
at the boundary goes to zero.

> It is not necessary to make that assumption, and one can do so without
> a loss of generality:

> http://www.dsprelated.com/showarticle/175.php

Many tools can be used in ways different than they were designed
to be used. As the old saying goes, if I remember it right,
if you have a hammer every problem looks like a nail.

If you don't have a hammer, sometimes a wrench will work.

There is a method for solving differential equations where
you write the solution as a sum of coefficients multiplied
by basis functions that form a complete basis, then solve
for the coefficients. Often the basis is powers of x, such
that the result is a polynomial. Sometimes a set of orthogonal
polynomials, which are themselves known for the differential
equation that they are the solution for. 

Bessel functions are the solutions to Bessel's equation, which
comes out in many problems involving cylindrical symmetry
(including the normal modes of drum heads).

Sines and cosines are solutions to the simplest non-trivial
second order differential equation, and so come up often.
(That is, y''+ay=0, for positive a.)  Solutions to such 
equations naturally come out as a sum of sines and cosines.
If the problem has boundary conditions, those limit the 
solutions to the appropriate combinations of sines and
cosines that satisfy the boundary.

-- glen

In article <qIGdnRceQ-ni_e7NnZ2dnUVZ_rCdnZ2d@web-ster.com>,
 Tim Wescott <tim@seemywebsite.com> wrote:

> And, in fact, if you were to express the DFT in linear algebra terms, 
> where y = A * x and the coefficients of A were all the various sinusoids, 
> you would find that A is always an invertable matrix, and not only that, 
> you would find that A^-1 defines the inverse DFT to get all your x back 
> from y.

True... and equivalent to the statement that A is just a change of basis.

rip

-- 
email address is r i p 1 AT c o m c a s t DOT n e t

On Tue, 9 Oct 2012 18:34:06 +0000 (UTC), glen herrmannsfeldt
<gah@ugcs.caltech.edu> wrote:

>Eric Jacobsen <eric.jacobsen@ieee.org> wrote:
>
>(snip)
>>>> It is a misconception that the derivation or understanding of the
>>>> DFT/FFT "assumes" or requires that the input vector repeats
>>>> continuously, i.e.,  (x[i] = x[i+N])
>
>(snip, then I wrote)
>>>OK, not assumes, but it is based on the solutions to a
>>>differential equation with periodic boundary conditions.
>
>(snip)
>
>> You've mentioned that before, but I'm not directly familiar with that
>> treatment. There are some common approaches that assume periodicity in
>> order to simplify the analysis and I think these are what lead people
>> to believe that it is a property or requirement when using a DFT/FFT.
>
>I especially remember it as some years ago I was trying to understand
>why the DCT was so popular. That is, what the DCT does that DFT and DST
>don't to. Maybe it was obvious to everyone else, but I finally
>found it in "Numerical Recipes."
>
>The answer is that the DFT has periodic boundary conditions, 
>the DST has the boundary go to zero, and the DCT the derivative
>at the boundary goes to zero.
>
>> It is not necessary to make that assumption, and one can do so without
>> a loss of generality:
>
>> http://www.dsprelated.com/showarticle/175.php
>
>Many tools can be used in ways different than they were designed
>to be used. As the old saying goes, if I remember it right,
>if you have a hammer every problem looks like a nail.
>
>If you don't have a hammer, sometimes a wrench will work.
>
>There is a method for solving differential equations where
>you write the solution as a sum of coefficients multiplied
>by basis functions that form a complete basis, then solve
>for the coefficients. Often the basis is powers of x, such
>that the result is a polynomial. Sometimes a set of orthogonal
>polynomials, which are themselves known for the differential
>equation that they are the solution for. 
>
>Bessel functions are the solutions to Bessel's equation, which
>comes out in many problems involving cylindrical symmetry
>(including the normal modes of drum heads).
>
>Sines and cosines are solutions to the simplest non-trivial
>second order differential equation, and so come up often.
>(That is, y''+ay=0, for positive a.)  Solutions to such 
>equations naturally come out as a sum of sines and cosines.
>If the problem has boundary conditions, those limit the 
>solutions to the appropriate combinations of sines and
>cosines that satisfy the boundary.
>
>-- glen

Regardless there is basis for developing, deriving and understanding
the DFT/FFT that does not require a periodic input sequence or loss of
generality.  This provides consistency with other points of view, many
of which have been discussed here periodically in the past.


Eric Jacobsen
Anchor Hill Communications
www.anchorhill.com

On 10/9/12 8:24 PM, Eric Jacobsen wrote:
>
...
>
> Regardless there is basis for developing, deriving and understanding
> the DFT/FFT that does not require a periodic input sequence or loss of
> generality.

does "require a periodic input sequence" mean the same as "periodically 
extends the input sequence"?


-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

On Tue, 09 Oct 2012 16:30:13 -0700, richard i pelletier wrote:

> In article <qIGdnRceQ-ni_e7NnZ2dnUVZ_rCdnZ2d@web-ster.com>,
>  Tim Wescott <tim@seemywebsite.com> wrote:
> 
>> And, in fact, if you were to express the DFT in linear algebra terms,
>> where y = A * x and the coefficients of A were all the various
>> sinusoids, you would find that A is always an invertable matrix, and
>> not only that, you would find that A^-1 defines the inverse DFT to get
>> all your x back from y.
> 
> True... and equivalent to the statement that A is just a change of
> basis.

I'm not fully up on my linear algebra terms, but A is an orthonormal 
matrix, whose eigenvalues are all of equal magnitude.

-- 
My liberal friends think I'm a conservative kook.
My conservative friends think I'm a liberal kook.
Why am I not happy that they have found common ground?

Tim Wescott, Communications, Control, Circuits & Software
http://www.wescottdesign.com

On Tuesday, October 9, 2012 9:22:46 PM UTC-4, Tim Wescott wrote:
> On Tue, 09 Oct 2012 16:30:13 -0700, richard i pelletier wrote:
> 
> 
> 
> 
> > 
> 
> >> And, in fact, if you were to express the DFT in linear algebra terms,
> 
> >> where y = A * x and the coefficients of A were all the various
> 
> >> sinusoids, you would find that A is always an invertable matrix, and
> 
> >> not only that, you would find that A^-1 defines the inverse DFT to get
> 
> >> all your x back from y.
> 
> > 
> 
> > True... and equivalent to the statement that A is just a change of
> 
> > basis.
> 
> 
> 
> I'm not fully up on my linear algebra terms, but A is an orthonormal 
> 
> matrix, whose eigenvalues are all of equal magnitude.
> 
> 
> 
> -- 
> 
> My liberal friends think I'm a conservative kook.
> 
> My conservative friends think I'm a liberal kook.
> 
> Why am I not happy that they have found common ground?
> 
> 
> 
> Tim Wescott, Communications, Control, Circuits & Software
> 
> http://www.wescottdesign.com

Since the matrices contain complex values, it is more appropriate to use the terms unitary and hermitian rather than orthogonal and orthonormal. Which way you go in terms of being unitary or just hermitian depends on how you handle the normalization factor. I.e., do you multiply by (1/N) on just the inverse transform or do you split the factor (1/sqrt(N)) across both the direct and inverse transforms.

Clay

eric.jacobsen@ieee.org (Eric Jacobsen) writes:
> [...]
> many of which have been discussed here periodically in the past.

Oh puhlease! :)
-- 
Randy Yates
Digital Signal Labs
http://www.digitalsignallabs.com

On 10/9/2012 8:24 PM, Eric Jacobsen wrote:

   ...

 > Regardless there is basis for developing, deriving and understanding
> the DFT/FFT that does not require a periodic input sequence or loss of
> generality.  This provides consistency with other points of view, many
> of which have been discussed here periodically in the past.

Periodically, eh?

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

On 10/10/12 12:19 AM, Jerry Avins wrote:
> On 10/9/2012 8:24 PM, Eric Jacobsen wrote:
>
> ...
>
>> Regardless there is basis for developing, deriving and understanding
>> the DFT/FFT that does not require a periodic input sequence or loss of
>> generality. This provides consistency with other points of view, many
>> of which have been discussed here periodically in the past.
>
> Periodically, eh?
>

hey, it's not periodic if they don't recognize it as periodic.  it's 
like the current political mess: reality is whatever i say it is.


-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."