Appendix A: Types of Fourier Transforms

On Jan 10, 7:32&#4294967295;pm, robert bristow-johnson <r...@audioimagination.com>
wrote:
> On Jan 10, 6:39&#4294967295;pm, Greg Heath <he...@alumni.brown.edu> wrote:
>
>
>
> >http://12000.org/my_notes/transforms/transforms.png
>
> > Hope this helps.
>
> nice chart.
>
> one old issue that gets me into fights here is that i disagree with
> the mathematical factuality of this statement: "Finite x[n] length N,
> zero elsewhere".
>
> it's oft repeated, you see it in print, and it's wrong.
>

another problem with it is that it is sloppy with the notation
regarding X_a(omega) vs. X_a(f).  even though they are notated as the
same function, unless X_a() is a constant function, X_a(f) cannot be
the same as X_a(omega) with "f" substituted as the argument.

i know it's hard to be consistent, but i really dislike the "omega"
notation.  with the unitary "f" notation of the CFT, it's much easier
to remember theorems and relationships (like duality, convolution,
Parseval) and not have to worry about where you toss in 1/(2*pi) and
where you don't.

r b-j

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

> I'm pulling this from memory, but you can find it in books with titles
> like "Signals and Systems"; the one on my shelf is by Oppenheim, Willsky
> & Young.

The blunders and flaws you present above might, yes. But if
one wants to understand the properties of the various variants
of the FT one is better off consulting the maths literature,
e.g. on differential equations.

> There. &#4294967295;I'll put down my can of spray paint now.

Pick up a new one and spray base color over the blunders,
and try again.

Rune

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.  but it's you (and many others) that are crucially
wrong.  and i'm willing to take you on about it.  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.  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:  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.

r b-j

On Jan 11, 6: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.

So what? Do claim that your persistence of making an incorrect point
turns the blunder correct? That your seniority here matters?

We have had many slugfests over this issue in the past, your position
is as well known as it is flawed, so I will not engage in yet another
fight.

It's sad to see how you pull others down with you, though.

Rune

On Jan 11, 1:03&#4294967295;am, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> So what? Do claim that your persistence of making an incorrect point
> turns the blunder correct?

is the premise of your question supported?  of course persistence of
an incorrect point does not make it correct.  (except for the current
Republican Americans and the 1940 Nazis who are convinced that if they
repeat a falsehood often enough, somehow it evolves from outright lie
to plausible notion and eventually to gospel truth.)

> That your seniority here matters?

no, it's the math that matters.

i'm just saying i'm kinda well-practiced in this argument.  and it was
only since '95 or '96 that i had to make it.  before then, i had no
idea that it was controversial.  i guess i hadn't looked closely at
texts other than O&S about it, so i was sorta ignorant of the other
views.

> We have had many slugfests over this issue in the past, your position
> is as well known as it is flawed,

... yet showing the flaw is so elusive ...

BTW, i might agree with you a teeny-weeny bit in one sense; Tim
shouldn't have "infinte" vs. "cyclic".  it should be "non-cyclic" vs.
"cyclic", or i might say "non-periodic" vs. "periodic".  you're saying
it should be "infinite" vs. "finite" and i am saying that they all
have infinite support.

> so I will not engage in yet another fight.
>
> It's sad to see how you pull others down with you, though.

oh, Rune.  you're no fun anymore.

(can you watch Monty Python up there in the Arctic?)

r b-j

>On Jan 10, 9:00=A0pm, Tim Wescott <t...@seemywebsite.com> wrote:
>> Just to inscribe this on the wall in cyberspace:
>
>> =A0From 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*. 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.

It seems to be you confusing things. Of course cyclic signals exist. A pure
sine wave is a trivial example. They are, by implication, infinite in
length. If they were not, they wouldn't be truly cyclic. They would be the
product of a cyclic signal with a pulse of appropriate length.

Steve

On Jan 11, 8:03&#4294967295;am, "steveu" <steveu@n_o_s_p_a_m.coppice.org> wrote:
> >On Jan 10, 9:00=A0pm, Tim Wescott <t...@seemywebsite.com> wrote:
> >> Just to inscribe this on the wall in cyberspace:
>
> >> =A0From 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*. 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.
>
> It seems to be you confusing things. Of course cyclic signals exist. A pure
> sine wave is a trivial example. They are, by implication, infinite in
> length.

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

On Jan 11, 7:23&#4294967295;am, robert bristow-johnson <r...@audioimagination.com>
wrote:
> On Jan 11, 1:03&#4294967295;am, Rune Allnor <all...@tele.ntnu.no> wrote:

> > We have had many slugfests over this issue in the past, your position
> > is as well known as it is flawed,
>
> ... yet showing the flaw is so elusive ...
>
> BTW, i might agree with you a teeny-weeny bit in one sense; Tim
> shouldn't have "infinte" vs. "cyclic". &#4294967295;it should be "non-cyclic" vs.
> "cyclic", or i might say "non-periodic" vs. "periodic". &#4294967295;you're saying
> it should be "infinite" vs. "finite" and i am saying that they all
> have infinite support.

Ant *that* is where the elusive flaw is hidden! Why have two
different
types of analyses, mutually exclusive, of the same mathemathical
entity?

Both the periodic x(t)=sin(t) and aperiodic y(t)=sin(t)+sin(pi*t)
have
similar mathematical properties, *except* for x(t) being periodic
whereas y(t) is not. Why not subject the two to the same mathematical
tools? Which are supposed to be linear? What sense is there in a
*linear*
tool that works on f(t) = x(t) but not on g(t) = x(t) + y(t)?

Rune

On Jan 10, 4:32&#4294967295;pm, robert bristow-johnson <r...@audioimagination.com>
wrote:
> ...

> one old issue that gets me into fights here is that i disagree with
> the mathematical factuality of this statement: "Finite x[n] length N,
> zero elsewhere".
>
> it's oft repeated, you see it in print, and it's wrong.
>
> r b-j

This appears so often because it is the only information that the DFT
is given. There are many assumptions that can be made about the region
outside the "length N", but the consequences of  those assumptions are
properties of the assumptions and not properties of the DFT.

The output of the DFT is not a function of the values outside that
"length N" The set of all functions I can calculate the DFT on N
samples of is not limited to periodic functions.

It would certainly be convenient and elegant if all signals of which I
might come across a set of N samples had the characteristic that
contiguous blocks of the signal had identical samples. Some people
seem to have been so seduced by the convenience and elegance of a
universe limited to such signals that they decide that they should
live only in a world where that is true and they try to convince those
around them to live there. But there have been many stochastic or non-
stationary or even discrete frequency signals for which periodicity
does not hold despite the fact that I have sampled  and performed the
DFT on N of those samples.

Dale B. Dalrymple

On Jan 11, 2:44&#4294967295;am, Rune Allnor <all...@tele.ntnu.no> wrote:
> On Jan 11, 7:23&#4294967295;am, robert bristow-johnson <r...@audioimagination.com>
> wrote:
>
> > On Jan 11, 1:03&#4294967295;am, Rune Allnor <all...@tele.ntnu.no> wrote:
> > > We have had many slugfests over this issue in the past, your position
> > > is as well known as it is flawed,
>
> > ... yet showing the flaw is so elusive ...
>
> > BTW, i might agree with you a teeny-weeny bit in one sense; Tim
> > shouldn't have "infinte" vs. "cyclic". &#4294967295;it should be "non-cyclic" vs.
> > "cyclic", or i might say "non-periodic" vs. "periodic". &#4294967295;you're saying
> > it should be "infinite" vs. "finite" and i am saying that they all
> > have infinite support.
>
> And *that* is where the elusive flaw is hidden! Why have two
> different types of analyses, mutually exclusive, of the same
> mathematical entity?
>

well, there *is* a qualitative difference between discrete and
continuous mathematics.  with either axis.  could be the mathematics
of integers where both the argument and returned values of a function
are integers or it can be signals that are discrete-time sequences vs.
continuous-time functions.  regarding the latter, we have a tool for
relating the two domains and it is the Shannon/Nyquist Sampling (and
Reconstruction) Theorem.

now, _if_ you're willing to allow naked (that is, not always clothed
with an integral) dirac impulses to exist**, you connect the discrete
and continuous time (or frequency) domains by attaching dirac impulses
to the members (a.k.a. elements) of the discrete sequence and use the
continuous Fourier transform.  Ultimately it's all the C.F.T., but
there is no reason that one cannot use discrete tools (like the Z
Transform or the DFT) within a problem where only discrete data
exists.  that's what we do as DSP engineers.

**(so i'm not willing to divert this to the "the Dirac delta is not a
function but something else" discussion.)

but, if you want to establish a table of rules like:

>  continuous-time non-periodic <--> continuous-frequency non-periodic
>  continuous-time     periodic <-->   discrete-frequency non-periodic
>    discrete-time non-periodic <--> continuous-frequency     periodic
>    discrete-time     periodic <-->   discrete-frequency     periodic

... which are attached to (respectively) CFT, Fourier Series, DTFT,
and the DFT (or equivalently "DFS")...

then you convert your discrete-whatever to continuous-whatever by
attaching dirac impulses to the elements of the discrete sequences and
use the continuous Fourier transform.  but whenever you get an
integral in the CFT (or inverse CFT), it may become a summation
because the inside is a sum of uniformly-spaced dirac impulses.

so the "different types of analyses" are NOT "mutually exclusive".
they are related.  just as the Z transform is related to the Laplace
transform (operating on an dirac impulse train).


> Both the periodic x(t)=sin(t) and aperiodic y(t)=sin(t)+sin(pi*t)
> have similar mathematical properties, *except* for x(t) being
> periodic whereas y(t) is not.

so you deal with it with the CFT in both cases.  big deel.

> Why not subject the two to the same mathematical tools?

> Which are supposed to be linear? What sense is there in
> a *linear* tool that works on f(t) = x(t) but not on
> g(t) = x(t) + y(t)?

well, since both terms are pretty well bandlimited, there are two of
those tools that works on g(t) or g[n] (CFT or DTFT) where information
is not lost in the transform.  it turns out that in both cases, the
representation in at least one domain can be completely described with
a set of numbers that are countably infinite.

Rune, it depends on how anal-retentive (or OCD) the engineer is.  It's
not so much an issue of linearity but an issue of a sorta measure of
information.  In the continuous time/frequency case, you can go far
enough out so that the functions are clearly different, no matter how
many digits you give to pi.  but we use tools like the DFT to deal
with the finite sets of information that we are handed in real life.
so we never, in practical reality, ever have to deal with the
situation you bring up where, say, a million digits for pi ain't
enough.

so then, in reality, we limit the amount of information we have to
deal (to finite sets that a computer might be expected to be able to
deal with) with by truncating (a.k.a. "windowing") and sampling.  both
operations have a theory behind it.  so far we might not be
disagreeing.

but, i think, the point to which we *do* disagree is that i am saying
that when this finite set of numbers is passed to the DFT, it is as if
the DFT (anthropomorphically) "assumes" that it is one period of a
periodic sequence.  the DFT inherently periodically extends (to
infinity) the data that is passed to it.  this is because the DFT and
Discrete Fourier Series are one-and-the-same.

if you were to pass the original data (sampled and windowed in
whatever order) to the DTFT, no assumption of periodicity is made.  in
fact, you need to define those other samples (maybe their zero), for
the DTFT to know what you're talking about.  but the DFT and DTFT
(with numbers attached to dirac impulses) agree with each other about
what this periodically extended set of data is.  and you can think of
it as the continuous (but periodic) frequency-domain data of the DTFT
(of the zero-extended finite x[n]) being sampled at N uniformly-spaced
points between -pi and +pi.

and, if you're really anal, you can push the whole thing up to the CFT
and get equivalent maths.  it's all the same.

r b-j