DSPRelated.com
Forums

Appendix A: Types of Fourier Transforms

Started by Tim Wescott January 10, 2011
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