Matteo Frigo <athena@fftw.org> wrote:
> FFTW uses this ontology also as an implementation principle.
> Specifically, FFTW comes with a special-purpose compiler that generates
> C code for complex FFTs, real FFTs, even/odd/whetever FFTs.  This
> compiler does not know anything about the special cases.  It only knows
> about the complex FFT and a few algebraic rules of the form 0+x=x and
> similar high-school algebra.  

glen herrmannsfeldt <gah@ugcs.caltech.edu> wrote:
> Can it do mixed boundary conditions?  Or where the boundary is other
> than on or half way between sample points?

I have never tried mixed boundary conditions, but there is no reason why
they should not work as expected.

Regards,
MF

robert bristow-johnson <rbj@audioimagination.com> wrote:

(snip)
> dunno what the "physicists' viewpoint" is, but is it the one that sorta 
> deprecates the "Dirac delta is not a function" point of view?  can the 
> physicists abide with a Dirac delta expressed as a limit of "nascent 
> deltas" all with unit area, as they get squeezed in the domain of the 
> independent variable (time, freq, whatever).

When I heard it, that was the mathematicians.  Story is that someone
rewrote a quantum mechanics book removing all deltas.  Physicists
don't mind them, though.

-- glen

On 10/3/11 8:17 PM, Matteo Frigo wrote:
> spope33@speedymail.org (Steve Pope) writes:
>
>> I've discussed this in the past, offering the viewpoint that (for example)
>> you can evaluate a cosine transform at any frequency f where f is on
>> the real line, whereas for a DCT (or DFT, or FFT) f must be a discrete
>> frequency.  I recall when I've said this, there have been responses
>> that, if you manipulate it a little, the discrete transform can come
>> up with the all of the same results.
>
> Your viewpoint is perfectly legitimate.  The way I see it (largely
> inspired by Oppenheim and Schafer) is this:
>
> 1) there exists a (complex) Fourier transform of continuous time into
>     continuous frequencies.  If you listen to mathematicians then this
>     transform is not defined even for simple functions like constants and
>     polynomials, and these guys generated a lot of noise trying to make
>     the Fourier integral converge when it doesn't (see Cesaro sums and
>     similar hacks).  Because the FT is too important not to be defined
>     for simple functions, the physicists ignored this nonsense and
>     invented the Dirac delta function so that FT is well-defined in all
>     impoerant cases.  I fully agree with the physicists' viewpoint.
>

dunno what the "physicists' viewpoint" is, but is it the one that sorta 
deprecates the "Dirac delta is not a function" point of view?  can the 
physicists abide with a Dirac delta expressed as a limit of "nascent 
deltas" all with unit area, as they get squeezed in the domain of the 
independent variable (time, freq, whatever).

> 2) You can consider functions of discrete time that are *not* periodic
>     in time.  This leads to what O&S call the "discrete-time Fourier
>     transform" (DTFT).  Here frequencies are continuous and the frequency
>     spectrum is periodic.  This is a perfectly legitimate setup.

and it's exactly the same as the continuous FT of the dirac sampled 
function.  the Laplace transform is to the continuous FT as the Z 
transform is to the DTFT.

>
> 3) You can consider periodic functions of discrete time; this leads to
>     the "discrete Fourier transform".

look at that, Eric or Dale (and whoever other deniers of the equivalence 
of the DFS and DFT).  he said "discrete Fourier transform", not 
"discrete Fourier series" ...

>  Here frequencies are discrete and
>     the spectrum is still periodic.

... we fight about that a lot here at comp.dsp, Matteo.  but you're on 
the right side of the issue.

even though some here disagree, i make it pretty simple: the DFT and the 
DFS (as described by O&S) are one and the same.  the DFT maps a periodic 
and discrete sequence of length N in one domain (say, "time) into 
another periodic and discrete sequence of length N in the reciprocal 
domain (that would be 1/time or "frequency").  the DFT inherently 
periodically extends the N discrete samples supplied to it (that coulda 
come from anywhere, an aperiodic source or not), into such a periodic 
sequence and transforms it.  and there are deniers of this same simple fact.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

spope33@speedymail.org (Steve Pope) writes:

> I've discussed this in the past, offering the viewpoint that (for example)
> you can evaluate a cosine transform at any frequency f where f is on
> the real line, whereas for a DCT (or DFT, or FFT) f must be a discrete 
> frequency.  I recall when I've said this, there have been responses
> that, if you manipulate it a little, the discrete transform can come
> up with the all of the same results.

Your viewpoint is perfectly legitimate.  The way I see it (largely
inspired by Oppenheim and Schafer) is this:

1) there exists a (complex) Fourier transform of continuous time into
   continuous frequencies.  If you listen to mathematicians then this
   transform is not defined even for simple functions like constants and
   polynomials, and these guys generated a lot of noise trying to make
   the Fourier integral converge when it doesn't (see Cesaro sums and
   similar hacks).  Because the FT is too important not to be defined
   for simple functions, the physicists ignored this nonsense and
   invented the Dirac delta function so that FT is well-defined in all
   impoerant cases.  I fully agree with the physicists' viewpoint.

2) You can consider functions of discrete time that are *not* periodic
   in time.  This leads to what O&S call the "discrete-time Fourier
   transform" (DTFT).  Here frequencies are continuous and the frequency
   spectrum is periodic.  This is a perfectly legitimate setup.

3) You can consider periodic functions of discrete time; this leads to
   the "discrete Fourier transform".  Here frequencies are discrete and
   the spectrum is still periodic.
   
The "interesting" case computationally is 3, which is the one I was
talking about.  (A "dual-2" case of periodic continuous time exists as
well.)

I do maintain that in all three cases the various
real/sine/cosine/Hartley transforms have no independent ontological
status, and they are best introduced as special cases of the
corresponding complex Fourier transform.  Any attempt to introduce them
independently and tweaking the constants to make them orthogonal is a
waste of time and an infinite source of confusion.

> But I still think it's intuitive to understand that for any arbitrary
> frequency that is real-valued, you can have the value of a transform
> at that frequency that might represent something meaningful, such as 
> power spectral density, but with a discrete transform you do not get the 
> same meaning, that it is not defined for all real frequencies, at least not 
> very directly.

Yes.  See DTFT in O&S.  At the end of the day no "periodic" signal
exists (at least in the DSP domain), so all of DSP is an attempt to
approximate case 2 using computational tools from case 3.

Regards,
Matteo Frigo

Matteo Frigo  <athena@fftw.org> wrote:

>spope33@speedymail.org (Steve Pope) writes:

>> Hopefully there's a word "discrete" missing from the above.  "Among
>> the zoo of Fourier-related discrete transforms..."
>
>Yes, I meant "discrete", sorry about that.  (But this is comp.dsp after
>all.)
>
>However, I fail to see why the continous case should be any different.
>Do you have a specific example in mind of where the continuity makes a
>difference?

I've discussed this in the past, offering the viewpoint that (for example)
you can evaluate a cosine transform at any frequency f where f is on
the real line, whereas for a DCT (or DFT, or FFT) f must be a discrete 
frequency.  I recall when I've said this, there have been responses
that, if you manipulate it a little, the discrete transform can come
up with the all of the same results.

But I still think it's intuitive to understand that for any arbitrary
frequency that is real-valued, you can have the value of a transform
at that frequency that might represent something meaningful, such as 
power spectral density, but with a discrete transform you do not get the 
same meaning, that it is not defined for all real frequencies, at least not 
very directly.

Steve

On Sep 26, 3:55=A0pm, Jerry Avins <j...@ieee.org> wrote:
> On 9/26/2011 11:15 AM, Raeldor wrote:
>
> > You Again?
>
> > You know, I feel a little sorry for you. =A0It's obvious you've been
> > bullied or abused at some point and now feel like you need to prove
> > yourself by name-calling people who are taking an interest in a
> > subject you know something about. =A0It doesn't make you look any
> > smarter, it just makes you look like someone who needs help. =A0I've me=
t
> > people like you before. =A0You might know a lot, and you might even be
> > smart, but you will never be content until you start treating people
> > with respect, because no matter how much you know or how clever you
> > are they'll never respect YOU until you do.
>
> Vlad, like me, he has little patience for those who ask here before
> looking for elementary answers in likely places. We differ mostly in my
> ignoring lazy questioners and his berating them.
>
> "Is DCT basically the same as an FFT that operates on real numbers?" is
> a classic stupid question. It is stupid as a question to others because
> it can be easily answered by looking up (say, in MathWorld or Wikipedia)
> what DCT and FFT are. Asking others to do your scut work is a sign of
> disrespect. You don't get respect without showing respect.

Wiki used to be pretty good, over the years though many topics have
been refined by various experts to the point that every intuitive
explanation is removed because it isn't precisely correct. Technically
it is hard to argue that evolution. But what survives is a listing of
spaghetti equations using non standard formats. Technical writing by
committee doesn't work very well.Just read some of the discussions.

spope33@speedymail.org (Steve Pope) writes:

> Hopefully there's a word "discrete" missing from the above.  "Among
> the zoo of Fourier-related distrete transforms..."

Yes, I meant "discrete", sorry about that.  (But this is comp.dsp after
all.)

However, I fail to see why the continous case should be any different.
Do you have a specific example in mind of where the continuity makes a
difference?

And just to be clear, I consider the Fourier-, real Fourier-, sine- and
cosine-, and the Hartley transforms to be "Fourier-related".  I do not
consider the Hankel transform to be Fourier-related, although it can be
reduced to a FT if one tries hard enough.  I.e., for Fourier-related
transforms the basis is some solution of the Poisson equation on a
N-dimensional rectangular region, as opposed to cylindrical regions or
whatever.

Matteo Frigo  <athena@fftw.org> wrote:

>FFTW takes the position that, among the zoo of Fourier-related
>transforms, the complex transform is the only fundamental one and all
>the other ones are just special cases of the (complex) FFT.  

Hopefully there's a word "discrete" missing from the above.  "Among
the zoo of Fourier-related distrete transforms..."


Steve

glen herrmannsfeldt <gah@ugcs.caltech.edu> writes:

> The derivative of sine at zero is never zero, so that is a 
> sufficient condition to remove the sine terms.

The premise is true.  The conclusion is false.  A bunch of nonzero sine
coefficients can add up to zero in multiple ways---the coefficients
don't have to be all zero.  E.g., the DFT of f(x)=x^3 (an odd function
such that f'(0)=0) has no cosine terms (since the function is odd), and
therefore some sine term must be nonzero (or else the DFT of f is
identically zero, which is absurd).

> Or, more generally, an odd function must be zero at zero,
> and an even function must have a derivative zero at zero.

Yes, this is what precisely I am saying: "f is even" implies "f'(0)=0",
but the converse is not true.  To cancel the sine terms you need "f is
even".  "f'(0)=0" is not sufficient.  

That is, the even/odd symmetry is the important thing, and the boundary
condition by itself is irrelevant.  Saying that "the DCT can be used
with any function f such that f'(0)=0" is wrong, as the f(x)=x^3 example
demonstrates. The DCT can only be used for even functions (which then
necessarily have f'(0)=0).

This is why I am saying that talking about the DCT in the first place is
a bad idea---it just confuses the essence of a pretty simple matter.

Matteo Frigo <athena@fftw.org> wrote:

(snip)
> Your very post shows an instance of this confusion, because you were
> under the impression that f'=0 at the boundary is a sufficient condition
> for the DCT-I (it is not; the function must be even or else the sine
> components do not cancel out).

The derivative of sine at zero is never zero, so that is a 
sufficient condition to remove the sine terms.

Or, more generally, an odd function must be zero at zero,
and an even function must have a derivative zero at zero.

I suppose in the general data processing sense it makes some
sense to do a generalized transform routine.  In the DSP case,
where everything is very specific, such as the N=8 DCT commonly
used in image transforms, there is no need for the generalization.

-- glen