Appendix A: Types of Fourier Transforms

Clay <clay@claysturner.com> wrote:
(snip, someone wrote)

>> fundamentally, the DFT is nothing other than the DFS. &#4294967295;the DFT maps a
>> discrete and periodic function in one domain (we'll call it the "time
>> domain") to another discrete and periodic function in the reciprocal
>> domain (we'll call it the "frequency domain").

>> that's what the DFT does.

(snip)
>> just because a function can be fully described by a finite-length
>> segment of that function, does not mean that the function is itself
>> finite in duration.
(snip)

> This reminds of a story about three guys looking out a window. The 1st
> remarks there is a cow outside eating grass. The 2nd remarks there is
> a brown cow outside eating grass. Finally the mathematician says there
> is a cow outside eating grass and the side that I can see is brown.
 
> If you approach DFTs from a linear algebra approach where your finite
> length of data gets expanded into a linear combination of finite
> length basis vectors. You can see nothing is stated about what the
> function to be analyzed or the basis functions do outside of the
> interval of interest. I don't know the color of the other side of the
> cow.

The DFT has periodic boundary conditions.  That doesn't set
any requirements on the points outside the transform, but it does
mean that the last point has more of a connection to the first 
point than you would otherwise expect.

It is easier to see in contrast to DST and DCT that don't have
periodic boundary conditions, even though the basis functions
are periodic.  I like the explanation in "Numerical Recipes," though
some people seem to have questions about the actual code given.

If you use the DFT as part of a filter, attenuating high frequencies,
you will find that the last point and first point will tend to
approach each other in a way that you otherwise wouldn't expect.
Again, DST and DCT don't have that property, and note that DCT
is commonly used in DSP filtering applications such as image
processing.  

-- glen

On Jan 12, 5:31&#4294967295;pm, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
> Clay <c...@claysturner.com> wrote:
>
> (snip, someone wrote)
>
> >> fundamentally, the DFT is nothing other than the DFS. &#4294967295;the DFT maps a
> >> discrete and periodic function in one domain (we'll call it the "time
> >> domain") to another discrete and periodic function in the reciprocal
> >> domain (we'll call it the "frequency domain").
> >> that's what the DFT does.
>
> (snip)>> just because a function can be fully described by a finite-length
> >> segment of that function, does not mean that the function is itself
> >> finite in duration.
>
> (snip)
>
> > This reminds of a story about three guys looking out a window. The 1st
> > remarks there is a cow outside eating grass. The 2nd remarks there is
> > a brown cow outside eating grass. Finally the mathematician says there
> > is a cow outside eating grass and the side that I can see is brown.
> > If you approach DFTs from a linear algebra approach where your finite
> > length of data gets expanded into a linear combination of finite
> > length basis vectors. You can see nothing is stated about what the
> > function to be analyzed or the basis functions do outside of the
> > interval of interest. I don't know the color of the other side of the
> > cow.
>
> The DFT has periodic boundary conditions. &#4294967295;That doesn't set
> any requirements on the points outside the transform, but it does
> mean that the last point has more of a connection to the first
> point than you would otherwise expect.
>
> It is easier to see in contrast to DST and DCT that don't have
> periodic boundary conditions, even though the basis functions
> are periodic. &#4294967295;I like the explanation in "Numerical Recipes," though
> some people seem to have questions about the actual code given.
>
> If you use the DFT as part of a filter, attenuating high frequencies,
> you will find that the last point and first point will tend to
> approach each other in a way that you otherwise wouldn't expect.
> Again, DST and DCT don't have that property, and note that DCT
> is commonly used in DSP filtering applications such as image
> processing. &#4294967295;
>
> -- glen

But here you are not talking about one DFT, but rather a series of
DFTs. Sure in some limiting cases, one expects a DFT to relate to the
DFS. But I thought we are talking about a single DFT.

Clay

On Jan 12, 12:57&#4294967295;pm, Clay <c...@claysturner.com> wrote:
> ...
> Maybe this is my mathematician background coming through, but oh well.
> ...
>
> Clay

I appreciate the convenience and comfort of having a digital method
that can produce a Fourier Transform. For a special signal space, the
linear combinations of the independent basis vectors, that abstract
mapping DFT thingie Dale talks about does just that. We should teach
that, but not leave out explaining the signal space restrictions.

My motivation does not come from a mathematical background. The
companies I have worked for (and many others) have sold digital
spectrum analyzers to customers who don't limit themselves to that
special sparse signal space. They want DFTs on stochastic data and non-
stationary data as well as periodic data and they know that their
periodic data have components of non-commensurate periods. Not a one
of them wants to see a 2D plot of perfectly periodic data. This is
real world, every day, in the field, instrumentation not mathematical
abstraction. I don't care that some people aren't comfortable going
honestly there.

Teaching that "the DFT calculates the Fourier Transform" and "anything
I calculate a DFT of is periodic" is harmful. Whether these have been
intentional in all cases or not, they are what is often getting
across. We get these amazing questions from DSP beginners (and not so
beginners) who have computed the FFT on some sequence and want to know
why their (widely used) FFT library routine doesn't work. Then there
are the "my white noise is lumpy" broken FFT questions. And the "FFT
can't be a set of filters, it's a Fourier Transform". We get those
questions and responses because they have been miss-taught.

And Clay, in your earlier post, which one of us were you saying is the
cow? :)

Dale B. Dalrymple

On Wed, 12 Jan 2011 15:15:01 -0800 (PST), dbd <dbd@ieee.org> wrote:

>On Jan 12, 12:57=A0pm, Clay <c...@claysturner.com> wrote:
>> ...
>> Maybe this is my mathematician background coming through, but oh well.
>> ...
>>
>> Clay
>
>I appreciate the convenience and comfort of having a digital method
>that can produce a Fourier Transform. For a special signal space, the
>linear combinations of the independent basis vectors, that abstract
>mapping DFT thingie Dale talks about does just that. We should teach
>that, but not leave out explaining the signal space restrictions.
>
>My motivation does not come from a mathematical background. The
>companies I have worked for (and many others) have sold digital
>spectrum analyzers to customers who don't limit themselves to that
>special sparse signal space. They want DFTs on stochastic data and non-
>stationary data as well as periodic data and they know that their
>periodic data have components of non-commensurate periods. Not a one
>of them wants to see a 2D plot of perfectly periodic data. This is
>real world, every day, in the field, instrumentation not mathematical
>abstraction. I don't care that some people aren't comfortable going
>honestly there.
>
>Teaching that "the DFT calculates the Fourier Transform" and "anything
>I calculate a DFT of is periodic" is harmful. Whether these have been
>intentional in all cases or not, they are what is often getting
>across. We get these amazing questions from DSP beginners (and not so
>beginners) who have computed the FFT on some sequence and want to know
>why their (widely used) FFT library routine doesn't work. Then there
>are the "my white noise is lumpy" broken FFT questions. And the "FFT
>can't be a set of filters, it's a Fourier Transform". We get those
>questions and responses because they have been miss-taught.
>
>And Clay, in your earlier post, which one of us were you saying is the
>cow? :)
>
>Dale B. Dalrymple

I don't think there's a problem teaching the "DFT is periodic" point
of view, or that the "FT" in "DFT" is still "Fourier Transform", but
when the limitations in that point of view aren't discussed then the
student is, IMHO, short-changed.

This harkens strongly back to the "inherent windowing" discussions
from way back when, and I think it boils down to the same issue.

Not everybody thinks of things the same way, and for some the
"periodic" point of view provides a good foundational basis for
understanding things if that point of view clicks with them the best.
Much is well explained within this point of view, and there is a lot
of consistency with the CTFT behavior and theory.

But, as mentioned, there are limitations, and there is another point
of view.

As you've mentioned and as Clay and others have pointed out, the DFT
is a mapping of an input sequence to an output sequence, a linear
algebra process with an input and output, or, my personal favorite, a
type of FT with an inherent window function.   I like the window
function point of view, because it is also a good foundational basis
understanding how things work and is also nicely consistent with other
process behavior and signal theory.   It also makes window function
behavior a lot more intuitive (well, for me, anyway).

From the "inherent window" point of view, it doesn't matter what is
outside the aperture of the DFT;  it can be periodic, aperiodic,
stochastic, or zero.   The application of the window function explains
much of the behavior of the transform including the bin sinx/x
response, ICI, etc., etc.  

I don't think it is all that important which point of view a person
takes, as long as the limitations and nuances are understood.   If one
can understand and appreciate both points of view, and others as well,
then I think it maximizes an individual's potential understanding, and
also makes it easier to talk to folks of any specific point of view.


Eric Jacobsen
Minister of Algorithms
Abineau Communications
http://www.abineau.com

On Jan 12, 1:49&#4294967295;am, "steveu" <steveu@n_o_s_p_a_m.coppice.org> wrote:

> That would imply that the validity of the answer from the DFT is not
> dependant on the values outside the length N, which is clearly not the
> case.

With the caveat that it's 3AM, I've pushing 24 hrs, haven't
cleaned my glasses for days and English is not my native
language:

Are you really suggesting that the computed result of the DFT
depends on numbers that never enter the computations?

Rune

On Jan 12, 8:36&#4294967295;pm, Fred Marshall <fmarshall_xremove_the...@xacm.org>
wrote:
> On 1/10/2011 11:38 PM, Rune Allnor wrote:
>
>
>
>
>
>
>
> > And that's where the problem occurs: The condition for the
> > FT of a function x(t) to exist (CT infinite domain) is that
>
> > integral |x(t)|^2 dt< &#4294967295;infinite
>
> > With x(t) = sin(t) that breaks down. Note that this has nothing
> > to do with the sine being periodic, it has to do with it having
> > infinite energy. (Try the same excercise with y(t) = sin(t)+sin(pi*t)
> > to see why.)
>
> > To get out of that embarrasment, engineers (*not* mathematicians)
> > came up with the ad hoc solution to express the periodic sine as
> > a sequence of periods, repeated ad infinitum, and compute the
> > Fourier series of one period.
>
> > It has no mathematical meaning, as the rather essential property
> > of linearity of the FT breaks down (again, use the y(t) above to
> > see why).
>
> > Again, this is totally trivial.
>
> > Rune
>
> I guess mathematicians over time have thus had a lot of fun using stuff
> that engineers came up with.... &#4294967295;I fail to acknowledge a fundamental
> difference between the two sets of folks where stuff like this is
> concerned. &#4294967295;Obviously each have their areas of expertise that go beyond.
>
> Dale repeats his point about the DFT being (in my terms) an abstract
> thingy that is simply a mapping of N points - having nothing whatsoever
> to do with any imagined or real samples which may exist outside the
> sample regions.

I garee with Dale on this.

>&#4294967295;This is a surely a valid perspective of the FT as a
> *mapping* but I've not reconciled how it fits in my own perspectives.

It's the *only* perspective of the FT, in any of its
shades, shapes or forms.


> If one takes an infinite continuous function and samples it then...

Why do you bring sampling into this? We were discussing
the FT up till this point, not sampling.

> OK. &#4294967295;So let's start out by sampling F'(w). &#4294967295;

Keeping in tune with your 'practical' approach: How do
you 'sample' F(w)? What kinds of ADCs work in frequency
domain?

All you have achieved is to swap a quagmire for quick sand.

Rune

On Jan 12, 8:36=A0pm, Fred Marshall <fmarshall_xremove_the...@xacm.org>
wrote:
> On 1/10/2011 11:38 PM, Rune Allnor wrote:
>
>
>
>
>
>
>
> > And that's where the problem occurs: The condition for the
> > FT of a function x(t) to exist (CT infinite domain) is that
>
> > integral |x(t)|^2 dt< =A0infinite
>
> > With x(t) =3D sin(t) that breaks down. Note that this has nothing
> > to do with the sine being periodic, it has to do with it having
> > infinite energy. (Try the same excercise with y(t) =3D sin(t)+sin(pi*t)
> > to see why.)
>
> > To get out of that embarrasment, engineers (*not* mathematicians)
> > came up with the ad hoc solution to express the periodic sine as
> > a sequence of periods, repeated ad infinitum, and compute the
> > Fourier series of one period.
>
> > It has no mathematical meaning, as the rather essential property
> > of linearity of the FT breaks down (again, use the y(t) above to
> > see why).
>
> > Again, this is totally trivial.
>
> > Rune
>
> I guess mathematicians over time have thus had a lot of fun using stuff
> that engineers came up with.... =A0I fail to acknowledge a fundamental
> difference between the two sets of folks where stuff like this is
> concerned. =A0Obviously each have their areas of expertise that go beyond=
.
>
> Dale repeats his point about the DFT being (in my terms) an abstract
> thingy that is simply a mapping of N points - having nothing whatsoever
> to do with any imagined or real samples which may exist outside the
> sample regions.

I garee with Dale on this.

>=A0This is a surely a valid perspective of the FT as a
> *mapping* but I've not reconciled how it fits in my own perspectives.

It's the *only* perspective of the FT, in any of its
shades, shapes or forms.


> If one takes an infinite continuous function and samples it then...

Why do you bring sampling into this? We were discussing
the FT up till this point, not sampling.

> OK. =A0So let's start out by sampling F'(w). =A0

Keeping in tune with your 'practical' approach: How do
you 'sample' F(w)? What kinds of ADCs work in frequency
domain?

All you have achieved is to swap a quagmire for quick sand.

Rune

On Jan 12, 8:36=A0pm, Fred Marshall <fmarshall_xremove_the...@xacm.org>
wrote:
> On 1/10/2011 11:38 PM, Rune Allnor wrote:
>
>
>
>
>
>
>
> > And that's where the problem occurs: The condition for the
> > FT of a function x(t) to exist (CT infinite domain) is that
>
> > integral |x(t)|^2 dt< =A0infinite
>
> > With x(t) =3D sin(t) that breaks down. Note that this has nothing
> > to do with the sine being periodic, it has to do with it having
> > infinite energy. (Try the same excercise with y(t) =3D sin(t)+sin(pi*t)
> > to see why.)
>
> > To get out of that embarrasment, engineers (*not* mathematicians)
> > came up with the ad hoc solution to express the periodic sine as
> > a sequence of periods, repeated ad infinitum, and compute the
> > Fourier series of one period.
>
> > It has no mathematical meaning, as the rather essential property
> > of linearity of the FT breaks down (again, use the y(t) above to
> > see why).
>
> > Again, this is totally trivial.
>
> > Rune
>
> I guess mathematicians over time have thus had a lot of fun using stuff
> that engineers came up with.... =A0I fail to acknowledge a fundamental
> difference between the two sets of folks where stuff like this is
> concerned. =A0Obviously each have their areas of expertise that go beyond=
.
>
> Dale repeats his point about the DFT being (in my terms) an abstract
> thingy that is simply a mapping of N points - having nothing whatsoever
> to do with any imagined or real samples which may exist outside the
> sample regions.

I garee with Dale on this.

>=A0This is a surely a valid perspective of the FT as a
> *mapping* but I've not reconciled how it fits in my own perspectives.

It's the *only* perspective of the FT, in any of its
shades, shapes or forms.


> If one takes an infinite continuous function and samples it then...

Why do you bring sampling into this? We were discussing
the FT up till this point, not sampling.

> OK. =A0So let's start out by sampling F'(w). =A0

Keeping in tune with your 'practical' approach: How do
you 'sample' F(w)? What kinds of ADCs work in frequency
domain?

All you have achieved is to swap a quagmire for quick sand.

Rune

On Jan 12, 8:36=A0pm, Fred Marshall <fmarshall_xremove_the...@xacm.org>
wrote:
> On 1/10/2011 11:38 PM, Rune Allnor wrote:
>
>
>
>
>
>
>
> > And that's where the problem occurs: The condition for the
> > FT of a function x(t) to exist (CT infinite domain) is that
>
> > integral |x(t)|^2 dt< =A0infinite
>
> > With x(t) =3D sin(t) that breaks down. Note that this has nothing
> > to do with the sine being periodic, it has to do with it having
> > infinite energy. (Try the same excercise with y(t) =3D sin(t)+sin(pi*t)
> > to see why.)
>
> > To get out of that embarrasment, engineers (*not* mathematicians)
> > came up with the ad hoc solution to express the periodic sine as
> > a sequence of periods, repeated ad infinitum, and compute the
> > Fourier series of one period.
>
> > It has no mathematical meaning, as the rather essential property
> > of linearity of the FT breaks down (again, use the y(t) above to
> > see why).
>
> > Again, this is totally trivial.
>
> > Rune
>
> I guess mathematicians over time have thus had a lot of fun using stuff
> that engineers came up with.... =A0I fail to acknowledge a fundamental
> difference between the two sets of folks where stuff like this is
> concerned. =A0Obviously each have their areas of expertise that go beyond=
.
>
> Dale repeats his point about the DFT being (in my terms) an abstract
> thingy that is simply a mapping of N points - having nothing whatsoever
> to do with any imagined or real samples which may exist outside the
> sample regions.

I garee with Dale on this.

>=A0This is a surely a valid perspective of the FT as a
> *mapping* but I've not reconciled how it fits in my own perspectives.

It's the *only* perspective of the FT, in any of its
shades, shapes or forms.


> If one takes an infinite continuous function and samples it then...

Why do you bring sampling into this? We were discussing
the FT up till this point, not sampling.

> OK. =A0So let's start out by sampling F'(w). =A0

Keeping in tune with your 'practical' approach: How do
you 'sample' F(w)? What kinds of ADCs work in frequency
domain?

All you have achieved is to swap a quagmire for quick sand.

Rune

On Jan 12, 8:36=A0pm, Fred Marshall <fmarshall_xremove_the...@xacm.org>
wrote:
> On 1/10/2011 11:38 PM, Rune Allnor wrote:
>
>
>
>
>
>
>
> > And that's where the problem occurs: The condition for the
> > FT of a function x(t) to exist (CT infinite domain) is that
>
> > integral |x(t)|^2 dt< =A0infinite
>
> > With x(t) =3D sin(t) that breaks down. Note that this has nothing
> > to do with the sine being periodic, it has to do with it having
> > infinite energy. (Try the same excercise with y(t) =3D sin(t)+sin(pi*t)
> > to see why.)
>
> > To get out of that embarrasment, engineers (*not* mathematicians)
> > came up with the ad hoc solution to express the periodic sine as
> > a sequence of periods, repeated ad infinitum, and compute the
> > Fourier series of one period.
>
> > It has no mathematical meaning, as the rather essential property
> > of linearity of the FT breaks down (again, use the y(t) above to
> > see why).
>
> > Again, this is totally trivial.
>
> > Rune
>
> I guess mathematicians over time have thus had a lot of fun using stuff
> that engineers came up with.... =A0I fail to acknowledge a fundamental
> difference between the two sets of folks where stuff like this is
> concerned. =A0Obviously each have their areas of expertise that go beyond=
.
>
> Dale repeats his point about the DFT being (in my terms) an abstract
> thingy that is simply a mapping of N points - having nothing whatsoever
> to do with any imagined or real samples which may exist outside the
> sample regions.

I garee with Dale on this.

>=A0This is a surely a valid perspective of the FT as a
> *mapping* but I've not reconciled how it fits in my own perspectives.

It's the *only* perspective of the FT, in any of its
shades, shapes or forms.


> If one takes an infinite continuous function and samples it then...

Why do you bring sampling into this? We were discussing
the FT up till this point, not sampling.

> OK. =A0So let's start out by sampling F'(w). =A0

Keeping in tune with your 'practical' approach: How do
you 'sample' F(w)? What kinds of ADCs work in frequency
domain?

All you have achieved is to swap a quagmire for quick sand.

Rune