Appendix A: Types of Fourier Transforms

On Jan 15, 4:10&#4294967295;am, Rune Allnor <all...@tele.ntnu.no> wrote:
> On Jan 14, 10:11&#4294967295;am, Chris Bore <chris.b...@gmail.com> wrote:
>
>
>
> > On Jan 13, 7:31&#4294967295;pm, Fred Marshall <fmarshall_xremove_the...@xacm.org>
> > wrote:
>
> > > On 1/12/2011 6:13 PM, Rune Allnor wrote:
> > > ....snip.....
>
> > > >> 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.
>
> > > ***And so did I Rune. &#4294967295;I just gave Dale credit for illuminating that
> > > viewpoint.
>
> > > >> &#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.
>
> > > ***I'm disappointed to hear that there is only a single viewpoint or
> > > framework possible. &#4294967295;That seems too restrictive in human thought.
>
> > > >> 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.
>
> > > ***If I had not intended to discuss sampling then I guess I wouldn't
> > > have brought it up. &#4294967295;But I did. &#4294967295;It seems obvious to me. &#4294967295;Surely if we
> > > can discuss abstract mathematical relationships then we can discuss the
> > > conversion from a particular continuous function to a discrete sequence, no?
>
> > > >> OK. &#4294967295;So let's start out by sampling F'(w).
>
> > > > Keeping in tune with your 'practical' approach: How do
> > > > you 'sample' F(w)? What kinds of ADCs work in frequency
> > > > domain?
>
> > > ***Perhaps there is a flaw in the fabric.... &#4294967295;Well, let's see: &#4294967295;Dale
> > > mentions that he worked for companies who made spectrum analyzers. &#4294967295;Many
> > > of those devices generate the spectrum as a continuouss function. &#4294967295;And,
> > > I'll bet, that some of them either started with sampled data to generate
> > > that continuous function. &#4294967295;And, I will assert, that if I want to
> > > notionally sample that continuous function then I may do it in my head
> > > at least. &#4294967295;The *domain* really doesn't matter. &#4294967295;Let's not take the
> > > notion of being practical all the way to "it must be demonstrated to
> > > exist physically in order to discuss it".
>
> > > ***What should one conclude from this comment? &#4294967295;One can compute the FT
> > > of a continuous function/signal or of a discrete sequence. &#4294967295;The result
> > > is a continous function. &#4294967295;Are we to conclude that it is somehow
> > > unreasonable or improper to imagine sampling this continuous function?
> > > Whey is that any more unreasonable than imagining sampling a time
> > > function?
>
> > > > All you have achieved is to swap a quagmire for quick sand.
>
> > > ***I'll leave this to others to comment on.
>
> > > ***What I attempted to do was:
>
> > > 1) create a framework for *discussion* along the lines of something that
> > > makes a lot of sense to me. &#4294967295;The intent was to unify related thoughts
> > > and to point out possible differences on the way.
>
> > > 2) seek constructive comments regarding what I may have left out, jumped
> > > over, stated really incorrectly, etc.
> > > I *tried* to say when things were fuzzy in my mind and did ask for help.
>
> > > It appears that others have agreed by citing references of similar
> > > discussions. &#4294967295;So far, I've not seen comments about how to improve the
> > > discussion I presented. &#4294967295;It seems to me that this would be useful. &#4294967295;It's
> > > presented in a step-by-step fashion so that any step might be dismissed
> > > (with rationale I'd hope) or improved or embellished on.
>
> > > For example, it seems like you have tried to dismiss sampling a
> > > continuous function in frequency. &#4294967295;I welcome that. &#4294967295;But where's the
> > > rationale?
>
> > > Fred
> > >> 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.
>
> > Whilst I totally agree with this, I do think one can bear in mind that
> > 'signal' processing in many cases does intend to process a 'signal' -
> > which I interpret to be a real-w-rold thing.
>
> You might interpret that as you which, but once you do, you
> effectively limit yourself from exploiting efficient methods
> to extract information from data. Even data that originate
> in the Real World.
>
> I have more than once told the story of how I developed a
> passive sonar detector that worked orders of magnitude
> better than the usual stuff - my initial simulations
> indicated 10-12 dB better detection indexes - before
> doing any of the fancy or elaborate stuff.
>
> Of course, I had used *maths*, not *intuition* or *analogies*
> to arrive at my algorithms, which meant that none of those
> who ought to have had a huge interes in my results were
> anywhere near capable of understanding what I had done.
>
Were these detectors ever built or realized?

> But of ocurse, if you are content (proud, even...?) with
> passing on your own mediocricy, then there is little I or
> anyone else can do about it.
>
> Rune

On Jan 16, 8:20&#4294967295;pm, brent <buleg...@columbus.rr.com> wrote:
> On Jan 15, 4:10&#4294967295;am, Rune Allnor <all...@tele.ntnu.no> wrote:

> > I have more than once told the story of how I developed a
> > passive sonar detector that worked orders of magnitude
> > better than the usual stuff - my initial simulations
> > indicated 10-12 dB better detection indexes - before
> > doing any of the fancy or elaborate stuff.
>
> > Of course, I had used *maths*, not *intuition* or *analogies*
> > to arrive at my algorithms, which meant that none of those
> > who ought to have had a huge interes in my results were
> > anywhere near capable of understanding what I had done.
>
> Were these detectors ever built or realized?

Not other than the prototypes I made, no.

The reason I was able to come up with the ideas, was that I
cut through the 'intuitive', 'physical' 'easy' explanations
and interpretations of the formulae, and focused on the maths.

The people whom I needed to convince to get the prototype
off my desk and further investigated, were unable to think
abstractly. They wanted 'physical' models, preferably in
terms of RLC cirquits.

I left the job soon afterwards.

Rune

On 1/15/2011 1:10 AM, Rune Allnor wrote:

>
> But of ocurse, if you are content (proud, even...?) with
> passing on your own mediocricy, then there is little I or
> anyone else can do about it.
>
> Rune

Rune,

Perhaps you're put off by the *style* of the writing.
But, I've yet to hear from you any part that is *incorrect*.
[please see the errata I posted].
Could you please be more specific?  I surely don't want to promulgate 
notions that are mediocre or worse....

I had a similar experience to yours using what one must call "math" when 
helping a group of physicists do a faster time domain convolution by 
using frequency domain multiplication.  Their original complaint was 
that nobody used their model because it took too much computer time.  So 
I improved it by a factor of 10 and after a year or so they reported 
that it actually worked!  So, yes, things like that can happen whether 
temporarily or permanently....

Fred

wow, 5 days later and i finally notice this post, Clay.



On Jan 12, 12:59&#4294967295;pm, Clay <c...@claysturner.com> wrote:
> On Jan 11, 12:23&#4294967295;am, robert bristow-johnson
>
>
>
> <r...@audioimagination.com> wrote:
> > On Jan 10, 10:30&#4294967295;pm, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > > On Jan 10, 9:00&#4294967295;pm, Tim Wescott <t...@seemywebsite.com> wrote:
>
> > > > Just to inscribe this on the wall in cyberspace:
> > > > &#4294967295;From this you get the four possible combinations:
>
> > > > continuous-time infinite --> continuous-frequency infinite.
> > > > continuous-time cyclic --> discrete-frequency infinite.
> > > > discrete-time infinite --> continuous-frequency cyclic.
> > > > discrete-time cyclic --> discrete-frequency, cyclic.
>
> > > Almost correct, but crucially wrong: There is no suct thing as
> > > a 'cyclic' signal. Those signals are of infinite duration.
> > > You confuse the 'cyclic' signal with the 'finite duration'
> > > *function*.
>
> > sorry, Rune. &#4294967295;but it's you (and many others) that are crucially
> > wrong. &#4294967295;and i'm willing to take you on about it. &#4294967295;i've been doing this
> > multiple times since my very beginning here at comp.dsp in 1995 or 96.
>
> > > Your variants 2 and 4 are the FTs that work
> > > on finite-duration domains. For continuous time, that's
> > > the Fourier series; for discrete time that's the DFT.
>
> > 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.
>
> > periodic on one domain implies discrete (with dirac impulses) in the
> > other domain and vise-versa.
>
> > the converse is also true: &#4294967295;non-periodic on one domain implies
> > continuous in the other domain.
>
> > 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.
>
>
> Robert,
>
> 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.

well, to use that analogy, i would say that you know, from a logical
and "scientific" perspective (scientia, meaning "knowledge"), that the
cow is brown on the other side.  all of those basis functions have
meaning outside of that interval of interest.  they are all periodic
with a period that is the same length of the interval of interest.

in any theorem that involve shifting of the data in one domain (say,
to be most general, the convolution theorem) that data is shifted as
if it were periodically extended *or* we use modulo N arithmetic in
the indices to keep their values within the interval of interest.
whether you "assume" (as i claim the DFT "assumes") that the data was
periodically extended, or you don't assume that, but use the modulo N
indexing, it's the same thing.  the DFT effectively, essentially,
inherently, naturally, (whateverly) periodically extends the finite
set of data that is passed to it.

i don't understand why this is controversial.

r b-j

On Jan 17, 6:55&#4294967295;pm, Fred Marshall <fmarshall_xremove_the...@xacm.org>
wrote:
> On 1/15/2011 1:10 AM, Rune Allnor wrote:
>
>
>
> > But of ocurse, if you are content (proud, even...?) with
> > passing on your own mediocricy, then there is little I or
> > anyone else can do about it.
>
> > Rune
>
> Rune,
>
> Perhaps you're put off by the *style* of the writing.
> But, I've yet to hear from you any part that is *incorrect*.
> [please see the errata I posted].
> Could you please be more specific? &#4294967295;I surely don't want to promulgate
> notions that are mediocre or worse....

The comment on mediocricy was aimed at Chris, not you.
In retrospect I might have trimmed the post to be more
clear on that particular point.

Rune

On Jan 17, 7:21&#4294967295;pm, robert bristow-johnson <r...@audioimagination.com>
wrote:
>  ...&#4294967295;the DFT effectively, essentially,
> inherently, naturally, (whateverly) periodically extends the finite
> set of data that is passed to it.
>
> i don't understand why this is controversial.
>
> r b-j

It is not controversial. It is a simple characteristic of a subset of
the space of DFT applications. One little corner. Some people chose to
sit in that little corner and say that the DFT is like a little
corner. Some people make a practice of exploring the rest of the room
and suggesting that others learn to explore the room before they chose
a place to sit and learn to chose where to sit for different
applications. It is merely silly to say to one's self that the DFT is -
only- like a little corner. It is misleading to tell others that the
DFT is -only- like a little corner.

Dale B. Dalrymple

On Tue, 18 Jan 2011 12:30:31 -0800 (PST), dbd <dbd@ieee.org> wrote:

>On Jan 17, 7:21=A0pm, robert bristow-johnson <r...@audioimagination.com>
>wrote:
>>  ...=A0the DFT effectively, essentially,
>> inherently, naturally, (whateverly) periodically extends the finite
>> set of data that is passed to it.
>>
>> i don't understand why this is controversial.
>>
>> r b-j
>
>It is not controversial. It is a simple characteristic of a subset of
>the space of DFT applications. One little corner. Some people chose to
>sit in that little corner and say that the DFT is like a little
>corner. Some people make a practice of exploring the rest of the room
>and suggesting that others learn to explore the room before they chose
>a place to sit and learn to chose where to sit for different
>applications. It is merely silly to say to one's self that the DFT is -
>only- like a little corner. It is misleading to tell others that the
>DFT is -only- like a little corner.
>
>Dale B. Dalrymple

Perhaps another way to say that is that the output of a DFT of a
sequence X is the same whether X was a single period of a stream of
repeating sequences of X or whether the sequence X was a window of a
unique sequence within some other, non repeating sequence (or whatever
you desire the data outside the DFT aperture to be).

The output of the DFT will be indistinguishable between the two cases.
The "repeating sequences of X" case has some elegance and relevance to
analysis of the CTFT, but it is certainly not the only interpretation
of the output or the process that produced it.   There are an infinite
number of possible longer sequences from which X could be extracted,
but as long as X is the DFT input, the output will be consistent
regardless of what the rest of the sequence outside of the DFT
aperture looked like.

Interpreting the process to have a rectangular window applied to the
input aperture provides an interpretation that is valid for either
point of view, and is also consistent with the correletor/reference
function interpretation of each bin's output.

The repeating sequence point of view does provide some insights, and
is certainly valid, but is not the only way of looking at it.  One
doesn't really know what color the other side of the cow is if it
isn't observed.  For certain breeds (i.e., a restricted or narrowed
interpretation), like black angus or something, there's a high
probability that observing one side of the cow tells you about the
other side, but assuming it to be true for all cows would be
inappropriate.

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

Eric Jacobsen <eric.jacobsen@ieee.org> wrote:
(snip, someone wrote)

>>It is not controversial. It is a simple characteristic of a subset of
>>the space of DFT applications. One little corner. Some people chose to
>>sit in that little corner and say that the DFT is like a little
>>corner. 
(snip)

> Perhaps another way to say that is that the output of a DFT of a
> sequence X is the same whether X was a single period of a stream of
> repeating sequences of X or whether the sequence X was a window of a
> unique sequence within some other, non repeating sequence (or whatever
> you desire the data outside the DFT aperture to be).

This is true, but note the word period.  The DFT has periodic
boundary conditions, and it has them independent of what may
or may not have occurred before or after in the input data stream.

If you use it for convolution, you get a circular convolution
even if you didn't want that.  (But good if you did.)  If you
use it for filtering, especially as a low pass filter, you
will find that there is a surprising connection between the first
and last points.  
 
> The output of the DFT will be indistinguishable between the two cases.
> The "repeating sequences of X" case has some elegance and relevance to
> analysis of the CTFT, but it is certainly not the only interpretation
> of the output or the process that produced it.   There are an infinite
> number of possible longer sequences from which X could be extracted,
> but as long as X is the DFT input, the output will be consistent
> regardless of what the rest of the sequence outside of the DFT
> aperture looked like.

Yes, but now consider a low-pass filter.  You know that high
frequencies are required for any discontinuity (or fast
transitions) in the signal.  The DFT also requires high
frequency components for discontinuities between the end
and the beginning.
 
(snip)

> The repeating sequence point of view does provide some insights, and
> is certainly valid, but is not the only way of looking at it.  One
> doesn't really know what color the other side of the cow is if it
> isn't observed.  

Cows don't have periodic boundary conditions.

> For certain breeds (i.e., a restricted or narrowed
> interpretation), like black angus or something, there's a high
> probability that observing one side of the cow tells you about the
> other side, but assuming it to be true for all cows would be
> inappropriate.

Well, a cow could be burned, dyed, or otherwise changed on
one side, and you wouldn't know that from the other side.

-- glen

On Jan 18, 2:29&#4294967295;pm, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
> ...
>
> Yes, but now consider a low-pass filter. &#4294967295;You know that high
> frequencies are required for any discontinuity (or fast
> transitions) in the signal. &#4294967295;The DFT also requires high
> frequency components for discontinuities between the end
> and the beginning.
>

DFTs don't 'require' anything.I think that the anthropomorphic
language blurs the issues of what characteristics are part of the
signal, the transform and the user's application.

There is ambiguity about whether the discontinuity comes from the
signal being analyzed or the window inherent in the calculation of a
DFT As usual with the DFT, you can't tell from the information in the
vector operated on by the DFT or the vector output by the DFT. It's
all about specific applications, the signals and the assumptions of
the application. In the real world there are often opportunities to
perform additional DFTs using additional samples or even examining the
additional samples themselves to resolve ambiguity.

> (snip)
>
> > The repeating sequence point of view does provide some insights, and
> > is certainly valid, but is not the only way of looking at it. &#4294967295;One
> > doesn't really know what color the other side of the cow is if it
> > isn't observed. &#4294967295;
>
> Cows don't have periodic boundary conditions.
>

Don't mathematicians usually approach this issue by assuming a
spherical cow?

Dale B. Dalrymple

dbd <dbd@ieee.org> wrote:
(snip, I wrote)

>> Yes, but now consider a low-pass filter. &#4294967295;You know that high
>> frequencies are required for any discontinuity (or fast
>> transitions) in the signal. &#4294967295;The DFT also requires high
>> frequency components for discontinuities between the end
>> and the beginning.
 
> DFTs don't 'require' anything.I think that the anthropomorphic
> language blurs the issues of what characteristics are part of the
> signal, the transform and the user's application.

The DFT has periodic boundary conditions, it doesn't "require"
them.  Now, if one uses the transform-filter-inverse transform
method, then the inverse transform "requires" the high frequency
components to generate a discontinuity between the beginning
and the end.  That is the sense of "require" that I meant.
 
> There is ambiguity about whether the discontinuity comes from the
> signal being analyzed or the window inherent in the calculation of a
> DFT As usual with the DFT, you can't tell from the information in the
> vector operated on by the DFT or the vector output by the DFT. It's
> all about specific applications, the signals and the assumptions of
> the application. In the real world there are often opportunities to
> perform additional DFTs using additional samples or even examining the
> additional samples themselves to resolve ambiguity.

But note that this is specifically due to using the DFT.  The DCT,
which doesn't have periodic boundary conditions, doesn't have that.
 
(snip)

>> Cows don't have periodic boundary conditions.
 
> Don't mathematicians usually approach this issue by assuming a
> spherical cow?

Yes, but spherical cows also don't have periodic boundary conditions.

In the story I remember, it was the physicist that used the
spherical approximation to the cow.    As I previously mentioned,
solid-state physics does use periodic boundary conditions in
situations that aren't periodic.  For the inside of a crystal,
and not too close to the surface, it is a very good approximation.

The DFT can also be used in non-periodic problems, as long as one
stays away from the ends.  If you extend the signal on both ends,
slowly going toward zero, that removes much of the problem.


-- glen