Path: utzoo!attcan!utgpu!news-server.csri.toronto.edu!rutgers!apple!netcom!mcmahan From: mcmahan@netcom.UUCP (Dave Mc Mahan) Newsgroups: comp.dsp Subject: Re: Having messed with FFT programs, I have a few questions... Message-ID: <17926@netcom.UUCP> Date: 2 Dec 90 19:50:33 GMT References: <1811@beguine.UUCP> Organization: Dave McMahan @ NetCom Services Lines: 83 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 Brought to you by Super Global Mega Corp .com