From this website, <http://www.sccon.ca/sccon/fft/fft3.htm>, it says "the Fourier transform for an input of 8 samples of an impulse signal, should give the output as shown below." They indicate it's a dft. "The Fourier transform of an impulse at the origin is a constant in the transform domain. In discrete form, the impulse is a non-zero sample at REAL[0]." Test Input Data: The test program computes the discrete Fourier transform of an 8-element vector consisting of a real impulse at the origin. REAL[0]= 1.000, IMAG[0]= 0.000 REAL[1]= 0.000, IMAG[1]= 0.000 REAL[2]= 0.000, IMAG[2]= 0.000 REAL[3]= 0.000, IMAG[3]= 0.000 REAL[4]= 0.000, IMAG[4]= 0.000 REAL[5]= 0.000, IMAG[5]= 0.000 REAL[6]= 0.000, IMAG[6]= 0.000 REAL[7]= 0.000, IMAG[7]= 0.000 dft output: The result should be a constant in the transform domain; in this case, eight real values, all equal to 0.125 REAL[0]= 0.125, IMAG[0]= 0.000 REAL[1]= 0.125, IMAG[1]= 0.000 REAL[2]= 0.125, IMAG[2]= 0.000 REAL[3]= 0.125, IMAG[3]= 0.000 REAL[4]= 0.125, IMAG[4]= 0.000 REAL[5]= 0.125, IMAG[5]= 0.000 REAL[6]= 0.125, IMAG[6]= 0.000 REAL[7]= 0.125, IMAG[7]= 0.000 However, this website, <http://www.cse.illinois.edu/iem/fft/rcrsvfft>, has an interactive fft calculator, and says: "This module illustrates a recursive fast Fourier transform (FFT) algorithm for computing the discrete Fourier transform of a complex vector." When I run the impulse data on their recursive FFT calculator, it gives me: REAL[0]= 1.000, IMAG[0]= 0.000 REAL[1]= 1.000, IMAG[1]= 0.000 REAL[2]= 1.000, IMAG[2]= 0.000 REAL[3]= 1.000, IMAG[3]= 0.000 REAL[4]= 1.000, IMAG[4]= 0.000 REAL[5]= 1.000, IMAG[5]= 0.000 REAL[6]= 1.000, IMAG[6]= 0.000 REAL[7]= 1.000, IMAG[7]= 0.000 But, when I run a version of the DFT I have from <http://paulbourke.net/miscellaneous/dft>, it gives me an output which matches the expected output from above: REAL[0]= 0.125, IMAG[0]= 0.000 REAL[1]= 0.125, IMAG[1]= 0.000 REAL[2]= 0.125, IMAG[2]= 0.000 REAL[3]= 0.125, IMAG[3]= 0.000 REAL[4]= 0.125, IMAG[4]= 0.000 REAL[5]= 0.125, IMAG[5]= 0.000 REAL[6]= 0.125, IMAG[6]= 0.000 REAL[7]= 0.125, IMAG[7]= 0.000 Although, when I run another version of the FFT I have, which does two steps, 1. Calculate two (N/2)-point DFT's 2. Combine the two (N/2)-point DFT's into one N-point DFT I get this output: REAL[0]= 1.000, IMAG[0]= 0.000 REAL[1]= 1.000, IMAG[1]= 0.000 REAL[2]= 1.000, IMAG[2]= 0.000 REAL[3]= 1.000, IMAG[3]= 0.000 REAL[4]= 1.000, IMAG[4]= 0.000 REAL[5]= 1.000, IMAG[5]= 0.000 REAL[6]= 1.000, IMAG[6]= 0.000 REAL[7]= 1.000, IMAG[7]= 0.000 What I want to do is get the FFT for a small slice of a wave file (e.g. 1024 samples,) compare it with another small slice of a wave file and be able to determine if they would sound similar. Which calculation should I use?
difference between fft, dft, and rfft???
Started by ●March 9, 2011
Reply by ●March 9, 20112011-03-09
On Mar 9, 5:58�am, "almo6914" <almo6914@n_o_s_p_a_m.yahoo.com> wrote:> From this website, <http://www.sccon.ca/sccon/fft/fft3.htm>, it says "the > Fourier transform for an input of 8 samples of an impulse signal, should > give the output as shown below." �They indicate it's a dft. > > "The Fourier transform of an impulse at the origin is a constant in the > transform domain. In discrete form, the impulse is a non-zero sample at > REAL[0]." > > Test Input Data: > > The test program computes the discrete Fourier transform of an 8-element > vector consisting of a real impulse at the origin. > > � � � REAL[0]= �1.000, � IMAG[0]= �0.000 > � � � REAL[1]= �0.000, � IMAG[1]= �0.000 > � � � REAL[2]= �0.000, � IMAG[2]= �0.000 > � � � REAL[3]= �0.000, � IMAG[3]= �0.000 > � � � REAL[4]= �0.000, � IMAG[4]= �0.000 > � � � REAL[5]= �0.000, � IMAG[5]= �0.000 > � � � REAL[6]= �0.000, � IMAG[6]= �0.000 > � � � REAL[7]= �0.000, � IMAG[7]= �0.000 > > dft output: > The result should be a constant in the transform domain; in this case, > eight real values, all equal to 0.125 > > � � � REAL[0]= �0.125, � IMAG[0]= �0.000 > � � � REAL[1]= �0.125, � IMAG[1]= �0.000 > � � � REAL[2]= �0.125, � IMAG[2]= �0.000 > � � � REAL[3]= �0.125, � IMAG[3]= �0.000 > � � � REAL[4]= �0.125, � IMAG[4]= �0.000 > � � � REAL[5]= �0.125, � IMAG[5]= �0.000 > � � � REAL[6]= �0.125, � IMAG[6]= �0.000 > � � � REAL[7]= �0.125, � IMAG[7]= �0.000 > > However, this website, <http://www.cse.illinois.edu/iem/fft/rcrsvfft>, has > an interactive fft calculator, and says: "This module illustrates a > recursive fast Fourier transform (FFT) algorithm for computing the discrete > Fourier transform of a complex vector." > > When I run the impulse data on their recursive FFT calculator, it gives > me: > > � � � REAL[0]= �1.000, � IMAG[0]= �0.000 > � � � REAL[1]= �1.000, � IMAG[1]= �0.000 > � � � REAL[2]= �1.000, � IMAG[2]= �0.000 > � � � REAL[3]= �1.000, � IMAG[3]= �0.000 > � � � REAL[4]= �1.000, � IMAG[4]= �0.000 > � � � REAL[5]= �1.000, � IMAG[5]= �0.000 > � � � REAL[6]= �1.000, � IMAG[6]= �0.000 > � � � REAL[7]= �1.000, � IMAG[7]= �0.000 > > But, when I run a version of the DFT I have from > <http://paulbourke.net/miscellaneous/dft>, it gives me an output which > matches the expected output from above: > > � � � REAL[0]= �0.125, � IMAG[0]= �0.000 > � � � REAL[1]= �0.125, � IMAG[1]= �0.000 > � � � REAL[2]= �0.125, � IMAG[2]= �0.000 > � � � REAL[3]= �0.125, � IMAG[3]= �0.000 > � � � REAL[4]= �0.125, � IMAG[4]= �0.000 > � � � REAL[5]= �0.125, � IMAG[5]= �0.000 > � � � REAL[6]= �0.125, � IMAG[6]= �0.000 > � � � REAL[7]= �0.125, � IMAG[7]= �0.000 > > Although, when I run another version of the FFT I have, which does two > steps, > > � 1. Calculate two (N/2)-point DFT's > � 2. Combine the two (N/2)-point DFT's into one N-point DFT > > I get this output: > > � � � REAL[0]= �1.000, � IMAG[0]= �0.000 > � � � REAL[1]= �1.000, � IMAG[1]= �0.000 > � � � REAL[2]= �1.000, � IMAG[2]= �0.000 > � � � REAL[3]= �1.000, � IMAG[3]= �0.000 > � � � REAL[4]= �1.000, � IMAG[4]= �0.000 > � � � REAL[5]= �1.000, � IMAG[5]= �0.000 > � � � REAL[6]= �1.000, � IMAG[6]= �0.000 > � � � REAL[7]= �1.000, � IMAG[7]= �0.000 > > What I want to do is get the FFT for a small slice of a wave file (e.g. > 1024 samples,) compare it with another small slice of a wave file and be > able to determine if they would sound similar. �Which calculation should I > use?Think about it for just a minute (or less) -- what would you have to change to make these consistent? And look at the equation that expresses the DFT. Hope that helps...
Reply by ●March 9, 20112011-03-09
The problem is not everyone defines the DFT and IDFT the same, there is a normalization factor of 1 and 1/N and the sign of the exponent, they are both "right" as long as they are consistent, (use either 1 and 1/N or 1/N an 1 for the DFT and IDFT) the exponents just need to be different signs. When you use different tools to try to get the same result you need to look into how they define the DFT.
Reply by ●March 9, 20112011-03-09
On 03/09/2011 05:58 AM, almo6914 wrote:> From this website,<http://www.sccon.ca/sccon/fft/fft3.htm>, it says "the > Fourier transform for an input of 8 samples of an impulse signal, should > give the output as shown below." They indicate it's a dft. > > "The Fourier transform of an impulse at the origin is a constant in the > transform domain. In discrete form, the impulse is a non-zero sample at > REAL[0]." > > Test Input Data: > > The test program computes the discrete Fourier transform of an 8-element > vector consisting of a real impulse at the origin. > > REAL[0]= 1.000, IMAG[0]= 0.000 > REAL[1]= 0.000, IMAG[1]= 0.000 > REAL[2]= 0.000, IMAG[2]= 0.000 > REAL[3]= 0.000, IMAG[3]= 0.000 > REAL[4]= 0.000, IMAG[4]= 0.000 > REAL[5]= 0.000, IMAG[5]= 0.000 > REAL[6]= 0.000, IMAG[6]= 0.000 > REAL[7]= 0.000, IMAG[7]= 0.000 > > > dft output: > The result should be a constant in the transform domain; in this case, > eight real values, all equal to 0.125 > > REAL[0]= 0.125, IMAG[0]= 0.000 > REAL[1]= 0.125, IMAG[1]= 0.000 > REAL[2]= 0.125, IMAG[2]= 0.000 > REAL[3]= 0.125, IMAG[3]= 0.000 > REAL[4]= 0.125, IMAG[4]= 0.000 > REAL[5]= 0.125, IMAG[5]= 0.000 > REAL[6]= 0.125, IMAG[6]= 0.000 > REAL[7]= 0.125, IMAG[7]= 0.000 > > > However, this website,<http://www.cse.illinois.edu/iem/fft/rcrsvfft>, has > an interactive fft calculator, and says: "This module illustrates a > recursive fast Fourier transform (FFT) algorithm for computing the discrete > Fourier transform of a complex vector." > > When I run the impulse data on their recursive FFT calculator, it gives > me: > > REAL[0]= 1.000, IMAG[0]= 0.000 > REAL[1]= 1.000, IMAG[1]= 0.000 > REAL[2]= 1.000, IMAG[2]= 0.000 > REAL[3]= 1.000, IMAG[3]= 0.000 > REAL[4]= 1.000, IMAG[4]= 0.000 > REAL[5]= 1.000, IMAG[5]= 0.000 > REAL[6]= 1.000, IMAG[6]= 0.000 > REAL[7]= 1.000, IMAG[7]= 0.000 > > > But, when I run a version of the DFT I have from > <http://paulbourke.net/miscellaneous/dft>, it gives me an output which > matches the expected output from above: > > REAL[0]= 0.125, IMAG[0]= 0.000 > REAL[1]= 0.125, IMAG[1]= 0.000 > REAL[2]= 0.125, IMAG[2]= 0.000 > REAL[3]= 0.125, IMAG[3]= 0.000 > REAL[4]= 0.125, IMAG[4]= 0.000 > REAL[5]= 0.125, IMAG[5]= 0.000 > REAL[6]= 0.125, IMAG[6]= 0.000 > REAL[7]= 0.125, IMAG[7]= 0.000 > > Although, when I run another version of the FFT I have, which does two > steps, > > 1. Calculate two (N/2)-point DFT's > 2. Combine the two (N/2)-point DFT's into one N-point DFT > > I get this output: > > REAL[0]= 1.000, IMAG[0]= 0.000 > REAL[1]= 1.000, IMAG[1]= 0.000 > REAL[2]= 1.000, IMAG[2]= 0.000 > REAL[3]= 1.000, IMAG[3]= 0.000 > REAL[4]= 1.000, IMAG[4]= 0.000 > REAL[5]= 1.000, IMAG[5]= 0.000 > REAL[6]= 1.000, IMAG[6]= 0.000 > REAL[7]= 1.000, IMAG[7]= 0.000 > > > What I want to do is get the FFT for a small slice of a wave file (e.g. > 1024 samples,) compare it with another small slice of a wave file and be > able to determine if they would sound similar. Which calculation should I > use?The fast Fourier transform is just a special algorithm to implement the digital Fourier transform efficiently -- so "FFT" and "DFT" is only different in the implementation details. But everyone implements their DFT with different conventions, generally resulting in a different scale factor and nothing else. For any algorithm, you need to figure out what convention _that algorithm_ uses, and roll with it. The only important thing is that any FFT/IFFT pair should evaluate back to the original (less round-off error): norm(x - ifft(fft(x))) should be way small. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com Do you need to implement control loops in software? "Applied Control Theory for Embedded Systems" was written for you. See details at http://www.wescottdesign.com/actfes/actfes.html
Reply by ●March 12, 20112011-03-12
On Mar 10, 7:35�am, Tim Wescott <t...@seemywebsite.com> wrote:> On 03/09/2011 05:58 AM, almo6914 wrote: > > > > > �From this website,<http://www.sccon.ca/sccon/fft/fft3.htm>, it says "the > > Fourier transform for an input of 8 samples of an impulse signal, should > > give the output as shown below." �They indicate it's a dft. > > > "The Fourier transform of an impulse at the origin is a constant in the > > transform domain. In discrete form, the impulse is a non-zero sample at > > REAL[0]." > > > Test Input Data: > > > The test program computes the discrete Fourier transform of an 8-element > > vector consisting of a real impulse at the origin. > > > � � � �REAL[0]= �1.000, � IMAG[0]= �0.000 > > � � � �REAL[1]= �0.000, � IMAG[1]= �0.000 > > � � � �REAL[2]= �0.000, � IMAG[2]= �0.000 > > � � � �REAL[3]= �0.000, � IMAG[3]= �0.000 > > � � � �REAL[4]= �0.000, � IMAG[4]= �0.000 > > � � � �REAL[5]= �0.000, � IMAG[5]= �0.000 > > � � � �REAL[6]= �0.000, � IMAG[6]= �0.000 > > � � � �REAL[7]= �0.000, � IMAG[7]= �0.000 > > > dft output: > > The result should be a constant in the transform domain; in this case, > > eight real values, all equal to 0.125 > > > � � � �REAL[0]= �0.125, � IMAG[0]= �0.000 > > � � � �REAL[1]= �0.125, � IMAG[1]= �0.000 > > � � � �REAL[2]= �0.125, � IMAG[2]= �0.000 > > � � � �REAL[3]= �0.125, � IMAG[3]= �0.000 > > � � � �REAL[4]= �0.125, � IMAG[4]= �0.000 > > � � � �REAL[5]= �0.125, � IMAG[5]= �0.000 > > � � � �REAL[6]= �0.125, � IMAG[6]= �0.000 > > � � � �REAL[7]= �0.125, � IMAG[7]= �0.000 > > > However, this website,<http://www.cse.illinois.edu/iem/fft/rcrsvfft>, has > > an interactive fft calculator, and says: "This module illustrates a > > recursive fast Fourier transform (FFT) algorithm for computing the discrete > > Fourier transform of a complex vector." > > > When I run the impulse data on their recursive FFT calculator, it gives > > me: > > > � � � �REAL[0]= �1.000, � IMAG[0]= �0.000 > > � � � �REAL[1]= �1.000, � IMAG[1]= �0.000 > > � � � �REAL[2]= �1.000, � IMAG[2]= �0.000 > > � � � �REAL[3]= �1.000, � IMAG[3]= �0.000 > > � � � �REAL[4]= �1.000, � IMAG[4]= �0.000 > > � � � �REAL[5]= �1.000, � IMAG[5]= �0.000 > > � � � �REAL[6]= �1.000, � IMAG[6]= �0.000 > > � � � �REAL[7]= �1.000, � IMAG[7]= �0.000 > > > But, when I run a version of the DFT I have from > > <http://paulbourke.net/miscellaneous/dft>, it gives me an output which > > matches the expected output from above: > > > � � � �REAL[0]= �0.125, � IMAG[0]= �0.000 > > � � � �REAL[1]= �0.125, � IMAG[1]= �0.000 > > � � � �REAL[2]= �0.125, � IMAG[2]= �0.000 > > � � � �REAL[3]= �0.125, � IMAG[3]= �0.000 > > � � � �REAL[4]= �0.125, � IMAG[4]= �0.000 > > � � � �REAL[5]= �0.125, � IMAG[5]= �0.000 > > � � � �REAL[6]= �0.125, � IMAG[6]= �0.000 > > � � � �REAL[7]= �0.125, � IMAG[7]= �0.000 > > > Although, when I run another version of the FFT I have, which does two > > steps, > > > � �1. Calculate two (N/2)-point DFT's > > � �2. Combine the two (N/2)-point DFT's into one N-point DFT > > > I get this output: > > > � � � �REAL[0]= �1.000, � IMAG[0]= �0.000 > > � � � �REAL[1]= �1.000, � IMAG[1]= �0.000 > > � � � �REAL[2]= �1.000, � IMAG[2]= �0.000 > > � � � �REAL[3]= �1.000, � IMAG[3]= �0.000 > > � � � �REAL[4]= �1.000, � IMAG[4]= �0.000 > > � � � �REAL[5]= �1.000, � IMAG[5]= �0.000 > > � � � �REAL[6]= �1.000, � IMAG[6]= �0.000 > > � � � �REAL[7]= �1.000, � IMAG[7]= �0.000 > > > What I want to do is get the FFT for a small slice of a wave file (e.g. > > 1024 samples,) compare it with another small slice of a wave file and be > > able to determine if they would sound similar. �Which calculation should I > > use? > > The fast Fourier transform is just a special algorithm to implement the > digital Fourier transform efficiently -- so "FFT" and "DFT" is only > different in the implementation details. > > But everyone implements their DFT with different conventions, generally > resulting in a different scale factor and nothing else. �For any > algorithm, you need to figure out what convention _that algorithm_ uses, > and roll with it. �The only important thing is that any FFT/IFFT pair > should evaluate back to the original (less round-off error): > > norm(x - ifft(fft(x))) should be way small. > > -- > > Tim Wescott > Wescott Design Serviceshttp://www.wescottdesign.com > > Do you need to implement control loops in software? > "Applied Control Theory for Embedded Systems" was written for you. > See details athttp://www.wescottdesign.com/actfes/actfes.htmlAn FFT should have a 1/N outside. It's the only version that makes any sense at all. DC or mean must divide by N. Hardy
Reply by ●March 12, 20112011-03-12
HardySpicer wrote:> An FFT should have a 1/N outside. It's the only version that makes any > sense at all. DC or mean must divide by N.If I use the DFT to implement convolution, then I don't want the 1/N on the forward transform. It just makes sense to put it on the inverse transform in terms of validity, simplicity and efficiency. For example, if I'm convolving 3 signals of lengths 8, 13, and 17, the result is length 8+13+17-2 = 36. So I need a minimum of 36 points in each DFT via zero padding. If I normalized on the forward transform by 8, 13, and 17 to get the proper DC value, as you propose, I wouldn't get a valid convolution. I need to normalize by 36, but only once on the inverse transform because it's the complex exponentials on the inverse transform that are evaluated at all 36 points around the unit circle.
Reply by ●March 12, 20112011-03-12
HardySpicer wrote:> An FFT should have a 1/N outside. It's the only version that makes any > sense at all. DC or mean must divide by N.If I use the DFT to implement convolution, then I don't want the 1/N on the forward transform. For example, if I'm convolving 3 signals of lengths 8, 13, and 17, the result is length 8+13+17-2 = 36. So I need a minimum of 36 points in each DFT via zero padding. What's the 'mean' of each signal in this context? Moreover, the window will grow with each additional convolved signal, and thus the 'mean' will continue to shrink. In the limit of the DTFT, a windowed signal would have infinitesimal mean. For the DTFT, the inverse transform is an integral over continuous frequency, or angular frequency where df => dw/(2pi), which yields a sum of an infinite number of infinitesimal quantities for each sample. In this case it becomes obvious that the DFT's 1/N properly goes with the inverse transform such that the summation becomes a Riemann sum, which in the limit is equivalent to the inverse DTFT integral. Additionally, as you convolve more signals in the frequency domain it's extra work to scale M DFTs separately by 1/N and then still have to scale the inverse by N^(M-1). For example, if I'm linearly convolving 3 DC signals of magnitude 1 and length 4, I get the length 10 result [1,3,6,10,12,12,10,6,3,1], which has a mean of 32/5. Just multiplying the individual means, i.e. (2/5)^3, yields the incorrect value of 8/125, which has to be scaled by multiplying by 10^(3-1) => 8/125*100 = 32/5. It's simpler and more efficient to just multiply 4*4*4 = 64 and then divide by 10 in the inverse transform. -- EOF
Reply by ●March 12, 20112011-03-12
On Mar 12, 10:09�pm, "eryksun ()" <eryk...@gmail.com> wrote:> HardySpicer wrote: > > An FFT should have a 1/N outside. It's the only version that makes any > > sense at all. DC or mean must divide by N. > > If I use the DFT to implement convolution, then I don't want the 1/N on the forward transform. For example, if I'm convolving 3 signals of lengths 8, 13, and 17, the result is length 8+13+17-2 = 36. So I need a minimum of 36 points in each DFT via zero padding. What's the 'mean' of each signal in this context? Moreover, the window will grow with each additional convolved signal, and thus the 'mean' will continue to shrink. In the limit of the DTFT, a windowed signal would have infinitesimal mean. > > For the DTFT, the inverse transform is an integral over continuous frequency, or angular frequency where df => dw/(2pi), which yields a sum of an infinite number of infinitesimal quantities for each sample. In this case it becomes obvious that the DFT's 1/N properly goes with the inverse transform such that the summation becomes a Riemann sum, which in the limit is equivalent to the inverse DTFT integral. > > Additionally, as you convolve more signals in the frequency domain it's extra work to scale M DFTs separately by 1/N and then still have to scale the inverse by N^(M-1). For example, if I'm linearly convolving 3 DC signals of magnitude 1 and length 4, I get the length 10 result [1,3,6,10,12,12,10,6,3,1], which has a mean of 32/5. Just multiplying the individual means, i.e. (2/5)^3, yields the incorrect value of 8/125, which has to be scaled by multiplying by 10^(3-1) => 8/125*100 = 32/5. It's simpler and more efficient to just multiply 4*4*4 = 64 and then divide by 10 in the inverse transform. > > -- > EOFUsed to be in the old text books that they put 1/N for the forward transform and nothing for the inverse. Now they pout it the other way around with no explanation. Hardy
Reply by ●March 12, 20112011-03-12
On Mar 9, 8:58�am, "almo6914" <almo6914@n_o_s_p_a_m.yahoo.com> wrote:> From this website, <http://www.sccon.ca/sccon/fft/fft3.htm>, it says "the > Fourier transform for an input of 8 samples of an impulse signal, should > give the output as shown below." �They indicate it's a dft. > > "The Fourier transform of an impulse at the origin is a constant in the > transform domain. In discrete form, the impulse is a non-zero sample at > REAL[0]." > > Test Input Data: > > The test program computes the discrete Fourier transform of an 8-element > vector consisting of a real impulse at the origin. > > � � � REAL[0]= �1.000, � IMAG[0]= �0.000 > � � � REAL[1]= �0.000, � IMAG[1]= �0.000 > � � � REAL[2]= �0.000, � IMAG[2]= �0.000 > � � � REAL[3]= �0.000, � IMAG[3]= �0.000 > � � � REAL[4]= �0.000, � IMAG[4]= �0.000 > � � � REAL[5]= �0.000, � IMAG[5]= �0.000 > � � � REAL[6]= �0.000, � IMAG[6]= �0.000 > � � � REAL[7]= �0.000, � IMAG[7]= �0.000 > > dft output: > The result should be a constant in the transform domain; in this case, > eight real values, all equal to 0.125 > > � � � REAL[0]= �0.125, � IMAG[0]= �0.000 > � � � REAL[1]= �0.125, � IMAG[1]= �0.000 > � � � REAL[2]= �0.125, � IMAG[2]= �0.000 > � � � REAL[3]= �0.125, � IMAG[3]= �0.000 > � � � REAL[4]= �0.125, � IMAG[4]= �0.000 > � � � REAL[5]= �0.125, � IMAG[5]= �0.000 > � � � REAL[6]= �0.125, � IMAG[6]= �0.000 > � � � REAL[7]= �0.125, � IMAG[7]= �0.000 > > However, this website, <http://www.cse.illinois.edu/iem/fft/rcrsvfft>, has > an interactive fft calculator, and says: "This module illustrates a > recursive fast Fourier transform (FFT) algorithm for computing the discrete > Fourier transform of a complex vector." > > When I run the impulse data on their recursive FFT calculator, it gives > me: > > � � � REAL[0]= �1.000, � IMAG[0]= �0.000 > � � � REAL[1]= �1.000, � IMAG[1]= �0.000 > � � � REAL[2]= �1.000, � IMAG[2]= �0.000 > � � � REAL[3]= �1.000, � IMAG[3]= �0.000 > � � � REAL[4]= �1.000, � IMAG[4]= �0.000 > � � � REAL[5]= �1.000, � IMAG[5]= �0.000 > � � � REAL[6]= �1.000, � IMAG[6]= �0.000 > � � � REAL[7]= �1.000, � IMAG[7]= �0.000 > > But, when I run a version of the DFT I have from > <http://paulbourke.net/miscellaneous/dft>, it gives me an output which > matches the expected output from above: > > � � � REAL[0]= �0.125, � IMAG[0]= �0.000 > � � � REAL[1]= �0.125, � IMAG[1]= �0.000 > � � � REAL[2]= �0.125, � IMAG[2]= �0.000 > � � � REAL[3]= �0.125, � IMAG[3]= �0.000 > � � � REAL[4]= �0.125, � IMAG[4]= �0.000 > � � � REAL[5]= �0.125, � IMAG[5]= �0.000 > � � � REAL[6]= �0.125, � IMAG[6]= �0.000 > � � � REAL[7]= �0.125, � IMAG[7]= �0.000 > > Although, when I run another version of the FFT I have, which does two > steps, > > � 1. Calculate two (N/2)-point DFT's > � 2. Combine the two (N/2)-point DFT's into one N-point DFT > > I get this output: > > � � � REAL[0]= �1.000, � IMAG[0]= �0.000 > � � � REAL[1]= �1.000, � IMAG[1]= �0.000 > � � � REAL[2]= �1.000, � IMAG[2]= �0.000 > � � � REAL[3]= �1.000, � IMAG[3]= �0.000 > � � � REAL[4]= �1.000, � IMAG[4]= �0.000 > � � � REAL[5]= �1.000, � IMAG[5]= �0.000 > � � � REAL[6]= �1.000, � IMAG[6]= �0.000 > � � � REAL[7]= �1.000, � IMAG[7]= �0.000 > > What I want to do is get the FFT for a small slice of a wave file (e.g. > 1024 samples,) compare it with another small slice of a wave file and be > able to determine if they would sound similar. �Which calculation should I > use?FFT/IFFT is just a fast implementation of DFT/IFT. Both use multipliers of {1,1/N}, {1/sqrt(N),1/sqrt{N}, or (1/N,1}. You can use any of them. Just make sure that max(abs(x-ifft(fft(x)))) = 0 to roundoff. I tend to like the last version which yields two amplitude spikes of height 0.5 for sin and cos. Hope this helps. Greg
Reply by ●March 13, 20112011-03-13
On Mar 12, 10:40�am, HardySpicer <gyansor...@gmail.com> wrote:> Used to be in the old text books that they put 1/N for the forward > transform and nothing for the inverse. Now they pout it the other way > around with no explanation.Could you please give a reference to an older text that uses "1/N for the forward transform and nothing for the inverse" and to a newer text that "pout it the other way around"? If both are texts that are commonly used in electrical engineering, it would be very interesting, while if a physics text and an engineering text (of whatever vintage) used different conventions, your assertion would be less profound. It would be particularly interesting if the 1st through n-th editions of a text used the first convention but switched to the second convention (with or without explanation) from the (n+1)-th edition onwards. --Dilip Sarwate
