"Matt Timmermans" <mt0000@sympatico.nospam-remove.ca> wrote in message
news:99VLb.113215$BA6.2630168@news20.bellglobal.com...
>
> "Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message
> news:w92dnTRJZfxuXWKi4p2dnA@centurytel.net...
> > I guess the simple way to say it is that we're multiplying together two
> > functions which, if inverse transformed separately would each be
weighted
> by
> > 1/N.  So, if we multiply them together first and inverse transform, the
> > scaling must be 1/N^2.
>
> It's tempting to try something like that, but such interpretations aren't
> helpful.  The FFT scaling factors just confuse the issue.  You're saying
> "multiplying" above instead of "circularly convolving", as if those terms
> were significantly equivalent in this situation.  They are not.  Did you
> notice how the extra downscaling is always on the convolution side, not on
> the multiplication side, even in the balanced case?
>
>

Matt, you did a good job of showing how the FFT scaling conventions affect
the relationships .... I agree they confuse the issue as long as we stick
with the typical convention of 1/N with IFFT.

I did say "multiplying" ... instead of "circularly convolving" - a slip.

....always on the convolution side.  OK, that's clear now.  Thanks!

Fred

"Rick Lyons" <r.lyons@REMOVE.ieee.org> wrote in message
news:40000701.14266718@news.west.earthlink.net...
>
> Hi Fred
>    Matt's post sure sounded right to me.

Rick,

I was just trying to parrot it back in my own terms to see if I'm getting
it.  Apparently not yet from Matt's next post.

Fred

"Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message
news:w92dnTRJZfxuXWKi4p2dnA@centurytel.net...
> I guess the simple way to say it is that we're multiplying together two
> functions which, if inverse transformed separately would each be weighted
by
> 1/N.  So, if we multiply them together first and inverse transform, the
> scaling must be 1/N^2.

It's tempting to try something like that, but such interpretations aren't
helpful.  The FFT scaling factors just confuse the issue.  You're saying
"multiplying" above instead of "circularly convolving", as if those terms
were significantly equivalent in this situation.  They are not.  Did you
notice how the extra downscaling is always on the convolution side, not on
the multiplication side, even in the balanced case?

Hi Fred
   Matt's post sure sounded right to me.


[-Rick-]

  (snipped)

"Matt Timmermans" <mt0000@sympatico.nospam-remove.ca> wrote in message
news:mYLLb.112520$BA6.2383101@news20.bellglobal.com...
> The DFT is not exactly a Fourier transform.
>
> There is a discrete convolution theorem for discrete signals,  DFTs, and
> circular convolutions that is analogous to the continuous convolution
> theorem, but it includes a scaling factor that depends on the number of
> points involved.
>
> If your FFT/IFFT implementation is like yours is -- the FFT is unscaled,
but
> the IFFT has a 1/N scaling, then it is indeed true that f*g <-> FG. (* is
> convolution and adjacency is pointwise multiplication), so a naively
> implemented overlap-add FFT FIR will work as expected, but fg <-> F*G/N,
as
> you've discovered.
>
> If you put all the scaling in the FFT instead of the IFFT, then it works
the
> other way.  If you put a balanced 1/sqrt(N) in both the FFT and IFFT, so
> that they are energy preserving, then  f*g/sqrt(N) <-> FG and fg <->
> F*G/sqrt(N).

Matt,

Thanks.  Somehow I'd missed that point along the way although I know I've
compensated for it in practice.

I guess the simple way to say it is that we're multiplying together two
functions which, if inverse transformed separately would each be weighted by
1/N.  So, if we multiply them together first and inverse transform, the
scaling must be 1/N^2.

F{g(t)}->NxG(w)  F^-1{NxG(w)}/N->g(t) where G(w) has been defined to have
the scaling shown
F{p(t)}->NxP(w)  F^-1{NxP(w)/N->p(t)  wjere P(w) has been defined to have
the scaling shown
then
F{g(t)xF{p(t)=N^2xG(w)xP(w)
F^-1{N^2xG(w)xP(w)/N2->g(t)*p(t)
So, for each multiplication in frequency, there's an additional scaling of
1/N necessary - using the typical FFT scaling convention (i.e. scaling by
1/N in the IFFT).

Fred

The DFT is not exactly a Fourier transform.

There is a discrete convolution theorem for discrete signals,  DFTs, and
circular convolutions that is analogous to the continuous convolution
theorem, but it includes a scaling factor that depends on the number of
points involved.

If your FFT/IFFT implementation is like yours is -- the FFT is unscaled, but
the IFFT has a 1/N scaling, then it is indeed true that f*g <-> FG. (* is
convolution and adjacency is pointwise multiplication), so a naively
implemented overlap-add FFT FIR will work as expected, but fg <-> F*G/N, as
you've discovered.

If you put all the scaling in the FFT instead of the IFFT, then it works the
other way.  If you put a balanced 1/sqrt(N) in both the FFT and IFFT, so
that they are energy preserving, then  f*g/sqrt(N) <-> FG and fg <->
F*G/sqrt(N).

"Tak-Shing Chan" <es728@city.ac.uk> wrote in message
news:Pine.GSO.4.33.0401092257470.24418-100000@swindon...
> On Fri, 9 Jan 2004, Fred Marshall wrote:
>
> > You get a pair of real samples with amplitude 128*256 = 32768 located at
f=k
> > and f=256-k.
> > Inverse transform the result (with internal scaling of 1/256 as is
typical
> > in an IFFT).
> > You get a cosine of amplitude 256=N which isn't what I expected!!
>
>      Are you using FFTW?
>
> Tak-Shing
>

Tak-Shing,

No.  But it's a good observation!  If I had been, then the comment about
what is typical ifft scaling would not have been correct.

Fred

On Fri, 9 Jan 2004, Fred Marshall wrote:

> You get a pair of real samples with amplitude 128*256 = 32768 located at f=k
> and f=256-k.
> Inverse transform the result (with internal scaling of 1/256 as is typical
> in an IFFT).
> You get a cosine of amplitude 256=N which isn't what I expected!!

     Are you using FFTW?

Tak-Shing

I've got myself befuddled here.....

Start with a temporal cosine of peak amplitude 1.0 with an integral number
of cycles in 256 seconds- period of some integer multiple "k" of 1/256Hz
like 10/256.
Window it (multiply it) with a rectangular window of length 256 and
amplitude 1.0 - from t=0 to t=255.
This does nothing to the original samples within that time span.
So, we have multiplied in time with no spectral aliasing involved that I can
imagine.

Also, let's sample the result with a sample rate of 1 second starting at
t=0.  So, we now have 256 (generally) nonzero samples that vary between +1.0
and -1.0  - well, OK there are some zeros in the span but that's not
important to the discussion.

Now, let's do the corresponding dual operation in the frequency domain.

FFT the window with N=256.  You get a single sample at index 1 (f=0) with
amplitude 256.
FFT the cosine with N=256.  You get a pair of samples at indices 11 and 247
with amplitudes of 128 each.

Frequency domain convolution is the dual of time domain multiplication; so:

Circularly convolve the window transform with the cosine transform. No
aliasing occurs because of the functions we chose.

You get a pair of real samples with amplitude 128*256 = 32768 located at f=k
and f=256-k.
Inverse transform the result (with internal scaling of 1/256 as is typical
in an IFFT).
You get a cosine of amplitude 256=N which isn't what I expected!!

Alternately, we could look at it like this:
The FFT of the window should have an amplitude of 1.0 and not 256 so that
when the convolution is done, the transform of the cosine isn't changed.
This means that the window must have temporal weights of 1/256.  But then
the multiplication in time wouldn't come out right.

I must be making some dumb mistake.  What is it?

Fred