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

# Circular Convolution Riddle / Error?

Started by ●January 9, 2004

Reply by ●January 9, 20042004-01-09

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

Reply by ●January 9, 20042004-01-09

"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 atf=k> > and f=256-k. > > Inverse transform the result (with internal scaling of 1/256 as istypical> > 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

Reply by ●January 10, 20042004-01-10

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

Reply by ●January 10, 20042004-01-10

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

Reply by ●January 10, 20042004-01-10

Reply by ●January 10, 20042004-01-10

"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 weightedby> 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?

Reply by ●January 10, 20042004-01-10

"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

Reply by ●January 10, 20042004-01-10

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