brianw@microsoft.UUCP (Brian Willoughby) (09/30/89)
In article <3441@abaa.UUCP> esker@abaa.UUCP (Lawrence Esker) writes: [...] >Yes, the sliding-FFT looked like a great design invention until you studied >it more closely and realized it was simply the original Discrete Fourier >Transform (DFT) restated in a different way. Since the FFT is an algorithmic >shortcut to the DFT, it made me chuckle to see the DFT used to perform the >FFT, albeit under a new name of sliding-FFT. You never stated whether you thought the DFT could be done in real time. The "sliding-FFT" (whatever you wish to call it) seemed simple enough (in terms of how many math computations per sample) for converting real-time audio into the frequency domain. But it does appear that computing an additional inverse FT under the same time constraints would not be possible. 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... One use for real-time FT would be a digital spectrum analyser with say 256 points instead of the usual 10 band versions available with analog units. Gotta have some blinky light algorithms for my DSP project board to execute :-) Brian Willoughby UUCP: ...!{tikal, sun, uunet, elwood}!microsoft!brianw InterNet: microsoft!brianw@uunet.UU.NET or: microsoft!brianw@Sun.COM Bitnet brianw@microsoft.UUCP
rob@raksha.eng.ohio-state.edu (Rob Carriere) (10/01/89)
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... 1) Inverse DFT differs from DFT by the sign of the exponent and (if you're not a mathematician) a factor of 1/N (assuming N data points) 2) FFT is simply a fast method for computing a bunch of DFT values. With DFT, you could compute the spectral value at any frequency you care, but it takes O(N) operations for each frequency. FFT gives you the spectral values at N equidistant frequencies for a total cost of O(N log N) (N has to be a power of 2), significantly cheaper than the O(N^2) sweat the regular DFT works up. SR
hjm@cernvax.UUCP (Hubert Matthews) (10/09/89)
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