Jeff.Miller@samba.acs.unc.edu (Jeff Miller) (12/02/90)
I have read a little, experimented a little with the FFT. And I have a question. This about sums my experience: I have a simple program I converted from BASIC to C which asks for the frequency, amplitude, and phase of four sine components, and then calculates them and sums them into an array. It then deos an FFT on them, analyzing at n/2 intervals where n is the number of samples. Now: if you enter sine values that "hit", which is to say are identical to those at which the program analyzes, the output is clean: a well defined line where it should be. But if the sine is just a little bit "off", the results are of course dissapointing and difficult to interpret. Can I "zoom in" on that frequency range, for better resolution, without increasing the sample rate or making any other changes which in the real world (if I applied this to CD audio for example) would be difficult? Don't ask me why I haven't tried by modifying my program... If I feed the output of this program into a reverse-FFT algorithm, will the original waveform be faithfully reproduced? I would think so. Should I perhaps be looking into the Fourier Transform proper? I hear it is a nightmare but is "continous", whatever that means...has a nice ring. Thanks for any input. If you don't feel like typing out an involved response send me your phone no. via e-mail and I'll call you.
BOYDJ@QUCDN.QueensU.CA (Jeff Boyd) (12/03/90)
If you use the "Fourier frequencies" in your spectrum calculation, the energy of the process is fully decomposed and represented. This means that, if the process has a frequency component which is NOT a Fourier frequency, its energy will nonetheless appear in your spectrum, projected onto nearby frequencies. There should be no difficulty in interpreting such a situation.
ruck@reef.cis.ufl.edu (John Ruckstuhl) (12/03/90)
In article <1811@beguine.UUCP> Jeff.Miller@samba.acs.unc.edu (Jeff Miller) writes: >Can I "zoom in" on that frequency range, for better resolution, without >increasing the sample rate or making any other changes which in the real >world (if I applied this to CD audio for example) would be difficult? >Don't ask me why I haven't tried by modifying my program... Consider the "Zoom FFT" suggested by Yip (1976), and discussed in modern textbooks of DSP. Hopefully, someone will post or email the title of a good reference -- else check Blahut's Fast Algorithms for DSP or Taylor's Digital Filter Design Handbook to see if they describe it. Regards, ruck. -- John R Ruckstuhl, Jr University of Florida ruck@cis.ufl.edu, uflorida!ruck
mcmahan@netcom.UUCP (Dave Mc Mahan) (12/03/90)
In a previous article, Jeff.Miller@samba.acs.unc.edu (Jeff Miller) writes: >I have read a little, experimented a little with the FFT. And I have >a question. > >This about sums my experience: I have a simple program I converted from >BASIC to C which asks for the frequency, amplitude, and phase of four >sine components, and then calculates them and sums them into an array. >It then does an FFT on them, analyzing at n/2 intervals where n is the >number of samples. > >Now: if you enter sine values that "hit", which is to say are identical >to those at which the program analyzes, the output is clean: a well defined >line where it should be. But if the sine is just a little bit "off", the >results are of course dissapointing and difficult to interpret. You are seeing a couple of things, I think. First, the FFT (and the DFT too) are only capable of looking at frequencies and resolving them correctly if if you have enough points in your data sample. That means you will resolve them only if you have specified the sample interval and frequencies such that an integer number of cycles exist in your data. You also get some discontinuity if your sample frequencies don't match up with your window exactly. This is because the FFT algorithm assumes that your sample window is replicated in time forever. Look at the following picture: | | . . . | | . . . . | . | | . . . . | . | | . . . . | . | |. . . . | . + . . . . |. | .| . . . . | . | . . . .| | . | . . . . | | . | . . . . | | . | . . | +----------------------------------------------------------- T1 T2 Note that if your sample window begins at T1 and ends at T2, you can just replicate the first sample window again and again for all time and you will get the triangle waveform repeated smoothly and without any glitches. Now, look at this picture: | | . . |. | | . . . . . | | . . . . .| | | . . . . . | | | . . . . . | + | . . . . . | | | . . . . . | | | . . . . . | | |. . . . . | | . . . . . | | .| . . | +----------------------------------------------------------- T1 T2 This is the same picture, I have just moved the sample intervals out to include more data samples. If you were to take the samples between T1 and T2 and replicate them again and again, you would have a big discontinuity where the previous sample period ended and the next one begins. If you FFT this, you will find that the frequency spectrum of the second sample period is radically different than the first, due to the discontinuity. To help correct this, you can 'window' your data so that it starts and ends at zero. This won't make the problem go away, but it may help. The best thing to do is either make your sample period become an integer multiple of the wave period, or make it much, much longer than the wave period so that the discontinuity isn't so apparent. >If I feed the output of this program into a reverse-FFT algorithm, will >the original waveform be faithfully reproduced? I would think so. It should be. -dave -- Dave McMahan mcmahan@netcom.uucp {apple,amdahl,claris}!netcom!mcmahan
mcmahan@netcom.UUCP (Dave Mc Mahan) (12/04/90)
The following article is being re-posted to this newsgroup at the request of the original author. He accidentally sent it to me as a reply when he really meant to post it in followup. --------------- Text of the re-post article -------------------- Date: Mon, 3 Dec 90 12:15:52 -0600 Subject: Re: Having messed with FFT programs, I have a few questions... Newsgroups: comp.dsp Wouldn't it be possible to rid yourself of the "glitch" problem by crossfading the section you are working with? They do this to get "clickless" loops in samplers, and it seems the technique might work here. Just make a copy of the section, reverse it, ramp the volume up like this: "/" Then, ramp the volume down of the original section like this: "\" And mix the two together. Then beat until smooth (just kidding). Then do your fft on that modified section. -- Dave McMahan mcmahan@netcom.uucp {apple,amdahl,claris}!netcom!mcmahan
mcmahan@netcom.UUCP (Dave Mc Mahan) (12/04/90)
In a previous article, By-Tor writes: >Wouldn't it be possible to rid yourself of the "glitch" problem by crossfading >the section you are working with? They do this to get "clickless" loops in >samplers, and it seems the technique might work here. Just make a copy of the >section, reverse it, ramp the volume up like this: "/" This is essentially what windowing does, but the window used is better at filtering out the bogus harmonics without introducing problems of it's own. Windowing requires the creation of the proper window and then multiplying it by the data samples. Instead of being a straight ramp, it is more of a smooth curve. Various windows are available, each with benefits and drawbacks of their own. Theoretically, it should give you better performance than just a straight ramp-up ramp-down technique. After all, you have to decide where to start the ramp for the downward tailoff and where to end the ramp for the initial ramp-up. The ramp technique really is a trapezoidal window and therefore introduces various types of distortion in the frequency domain. It does have the benefit of working well for mixing two signals together for sending to a speaker and being quite easy to implement, but it isn't the optimal choice for the task of looking at undistorted data in the frequency domain. If somebody wants me to, I'll look up a couple of different types of windows at work tomorrow and post the formulas used to this newsgroup. The functions can be easily plotted using a spreadsheet or other program and you can see for yourself just exactly how each window looks. -dave -- Dave McMahan mcmahan@netcom.uucp {apple,amdahl,claris}!netcom!mcmahan
markz@ssc.UUCP (Mark Zenier) (12/06/90)
In article <1811@beguine.UUCP>, Jeff.Miller@samba.acs.unc.edu (Jeff Miller) writes: > I have read a little, experimented a little with the FFT. And I have > a question. A good cookbook for the FFT is Intel application note AP-275, "An FFT Algorithm For MCS-96 Products Including Supporting Routines and Examples" It covers the bin side lobes, windowing and other strange stuff. (Its in the Embedded Contoller Handbook, Volume II, 16 bits) markz@ssc.uucp