Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!uunet!bloom-beacon!eru!luth!sunic!mcsun!cernvax!hjm From: hjm@cernvax.UUCP (Hubert Matthews) Newsgroups: comp.dsp Subject: Re: Real-time Fourier Transform Keywords: FFT DFT Message-ID: <1113@cernvax.UUCP> Date: 9 Oct 89 16:47:11 GMT References: <7899@microsoft.UUCP> Reply-To: hjm@cernvax.UUCP (Hubert Matthews) Organization: CERN European Laboratory for Particle Physics, CH-1211 Geneva, Switzerland Lines: 61 In article <7899@microsoft.UUCP> brianw@microsoft.UUCP (Brian Willoughby) writes: >Its been a while since I studied this in college, anyone care to describe >the DFT vs. FFT in layman's terms, or point to a text which does? I seem >to remember that the inverse FT is basically the same operation as the FT >from time- to frequency-domain... OK, here goes. First thing to do is to read Bracewell's book on the Fourier Transform. Then you might understand my rather poor explanations. It's a lot easier to explain if you can draw nice squiggly lines and diagrams, so bear with me please. Regarding the DFT and the FFT: they are one and the same thing. The discrete Fourier transform (DFT) is a truncated and sampled version of the continuous Fourier transform (FT) and is a computable approximation of the FT. The Fast Fourier Transform is merely a well-known, computationally efficient way to calculate the DFT if the number of samples is a power of 2. The DFT is characterised by two quantities: the number of points, N, and the sampling time, T. To derive the DFT from the FT requires three steps: sampling of the continuous time series, truncation of the now sampled series and making a continuous, periodic set of samples by placing the N sampled points end-to-end. This is achieved by multiplying by a comb function with separation T to sample the points, then by multiplying by a top-hat or pill-box gating pulse of length NT, and finally by convolving with a comb function with separation NT to form a signal with period NT. What does this look like in the frequency domain? The sampling stage (mult by comb(T)) causes the frequency spectrum to be replicated in frequency every 1/T (this explains why aliasing occurs if the freq spec extends beyond 1/2T), the truncation stage "smears" the data by convolving them with a sinc(1/NT) function, and the time-domain replication is what causes the freq spec to be periodic and *not* the sampling stage (an important and oft misunderstood point). Thus, the DFT is a derivative of the continuous FT, and this three-stage process can be used to predict and analyse the effect on the DFT or the time-domain of most operations. Just remember that T and 1/T, and that multiplication and convolution are transform pairs, and you won't go far wrong. As for the connection between the forward- and the backward-FTs, there is only a minus sign in the exponent of the kernel that changes. Whether you define the forward-version to be exp(-2*pi*j*f*t) or exp(2*pi*j*f*t) is just a matter of choice, but the backward-version must be of the opposite sign. >Brian Willoughby >UUCP: ...!{tikal, sun, uunet, elwood}!microsoft!brianw >InterNet: microsoft!brianw@uunet.UU.NET > or: microsoft!brianw@Sun.COM >Bitnet brianw@microsoft.UUCP -- Hubert Matthews ...helping make the world a quote-free zone... hjm@cernvax.cern.ch hjm@vxomeg.decnet.cern.ch ...!mcvax!cernvax!hjm