ator that gets excited by our input waveform. If the input has a partial at the frequency we're e the amplitude of the resonance with the reference sine wave. Since our reference wave is a direct measure of the actual amplitude of the partial at that frequency. Since a
resonator r, the transform can (admittedly under somewhat relaxed conditions) be seen as a having narrow band pass filters that are centered around the frequencies we're evaluating. This helps e
Fourier transform provides an efficient tool for performing filtering of signals.
Just for the sake of completeness: of course, the above routine is invertible, our signal can rical precision) be perfectly reconstructed when we know its partial sine waves, by simply is is left as an exercise to the reader. The same routine can be changed to work with cosine e simply need to change the sin(arg) term to cos(arg) to obtain the direct realization of the Discrete T).
Now, as we have discussed in the very first paragraph of this article, in practice we have no inus-like function as sine wave or cosine wave. Instead we are always measuring
ransform are of no great use when we are applying them in practice, except for some special ion where each image might have features that are well modelled by a cosine or sine basis of the same color that are well represented by the cosine basis function). A sinusoid is a bit r cosine wave in that it can start at an arbitrary position in its period. We remember that the at zero, while the cosine wave starts out at one. When we take the sine wave as reference, 1/4th later in its period. It is common to measure this offset in degree or radians
conjunction with trigonometric functions. One complete period equals 360° (pron. degree) h pi pronounced like the word pie. is a Greek symbol for the number 3.14159265358979323846... nificance in trigonometry). The cosine wave thus has an offset of 90° or /2. This offset is d, so looking at our cosine wave we see that it is a sinusoid with a phase offset of 90
So what's this phase business all about. As we can't restrict our signal to start out at zero e (since we are just observing a signal which might be beyond our control) it is of interest }
}
一天征服傅里叶变换[英] 页码，6/11
http://www.31ic.com/Article_Print.asp?ArticleID=619 2004-10-18 PDF created with pdfFactory trial version www.pdffactory.com
plitude and phase to uniquely describe it at any one time instant. With the sine or cosine transform, ero phase or 90° phase and any
sinusoid that has an arbitrary phase will cause adjacent eaks (since they try to 'help' the analysis to force-fit the measured signal to a sum of zero a bit like trying to fit a round stone into a square hole: you
need smaller round stones to fill d even more even smaller stones to fill out the space that is still left empty, and so on. So hat is general in that it can deal with signals that are built of sinusoids of arbitrary phase.
Step 6: The Discrete Fourier transform.
The step from the sine transform to the Fourier transform is simple, making it in a way more en using a sine wave for each frequency we measure in the sine transform, we use both a Fourier transform. That is, for any frequency we are looking at we 'compare' (or 'resonate') h a cosine and a sine wave of the same frequency. If our signal looks much like a sine wave, form will have a large amplitude. If it looks like a cosine wave, the cosine part of our transform de. If it looks like the opposite of a sine wave, that is, it starts out at zero but drops to e portion will have a large negative amplitude. It can be shown that the + and - sign
hase can represent any sinusoid at the given frequency2.
We're still left with the problem of how to get something useful out of the Fourier Transform. efit of the Fourier transform over the Sine and Cosine transform is that we are working with n't see any sinusoids yet, there are still only sines and cosines. Well, this requires an additional Listing 1.2: The direct realization of the Discrete Fourier Transform
#define M_PI 3.14159265358979323846 long bin, k;
double arg, sign = -1.; /* sign = -1 -> FFT, 1 -> iFFT */ for (bin = 0; bin <= transformLength/2; bin++) { cosPart[bin] = (sinPart[bin] = 0.); for (k = 0; k < transformLength; k++) {
arg = 2.*(float)bin*M_PI*(float)k/(float)transformLength; sinPart[bin] += inputData[k] * sign * sin(arg); cosPart[bin] += inputData[k] * cos(arg); } }
一天征服傅里叶变换[英] 页码，7/11
http://www.31ic.com/Article_Print.asp?ArticleID=619 2004-10-18 PDF created with pdfFactory trial version www.pdffactory.com
After running the code fragment shown in Listing 1.3 on our DFT output, we end up with a nal as a sum of sinusoid waves. The k-th sinusoid is described by frequency[k], magnitude[k]
periods per seconds), dB (Decibel) and ° (Degree). Please note that after the post
s the sine and cosine parts into a single sinusoid, we name the amplitude of the k
it will now always be a positive value. We could say that an amplitude of -1.0 corresponds hase of either + or -180°. In the literature, the
array magnitude[] is called the Magnitude Spectrum
l, the array phase[] is called the Phase Spectrum of the measured signal at the time where As a reference for measuring the bin magnitude in decibels, our input wave is expected to ge [-1.0, 1.0), which
corresponds to a magnitude of 0dB digital full scale (DFS). As an interesting listing 1.3 can, for example, be used to write a spectrum analyzer based on the Discrete Fourier Conclusion
As we have seen, the Fourier transform and its 'relatives', the discrete sine and cosine transform decompose a signal into a bunch of partial waves. These are either sine or cosine waves, or mbination of sine and cosine waves). The advantage of using both the sine and cosine wave r transform is that we are thus able to introduce the concept of phase which makes the transform e can use it to efficiently and clearly
analyze sinusoids that are neither a pure sine or cosine gnals as well. The Fourier transform is independent of the signal under examination in that it requires the o matter if the signal we are analyzing is one single sinusoid or something else more complicated. the Discrete Fourier transform is called a nonparametric transform, meaning that it is not gent' analysis of a signal is needed (in the case where we are examining a signal that we know efer just getting information about its phase, frequency and magnitude instead of a bunch Listing 1.3: Getting sinusoid frequency, magnitude and phase from the Discrete Fourier #define M_PI 3.14159265358979323846
long bin;
for (bin = 0; bin <= transformLength/2; bin++) { /* frequency */
frequency[bin] = (float)bin * sampleRate / (float)transformLength; /* magnitude */
magnitude[bin] = 20. * log10( 2. * sqrt(sinPart[bin]*sinPart[bin] + cosPart[bin]*cosPart[bin]) / /* phase */
phase[bin] = 180.*atan2(sinPart[bin], cosPart[bin]) / M_PI - 90.; }
一天征服傅里叶变换[英] 页码，8/11
http://www.31ic.com/Article_Print.asp?ArticleID=619 2004-10-18 PDF created with pdfFactory trial version www.pdffactory.com me predefined frequencies).
We now also know that we are evaluating our input signal at a fixed frequency grid (our
do with the actual frequencies present in our input signal. Since we choose our reference sine according to taste with regard to their frequency, the grid we impose on our analysis is artificial. mediately clear that one will easily encounter a scenario where the measured signal's frequencies en the frequencies of our transform bins.
Consequently, a sinusoid that has a frequency that frequency 'bins'
will not be well represented in our transform. Adjacent bins that
surround our input wave will try to 'correct' the deviation in frequency and thus the energy of the input several neighbouring bins. This is also the main reason why the Fourier transform will not rn with its fundamental and harmonics (and this is also why we call the sine and cosine waves s, or overtones).
Simply speaking, without further post-processing, the DFT is little more than a bank of narrow, pass filters ('channels') with additional phase information for each channel. It is useful for g and applying some other neat tricks (changing the pitch of a signal without changing its in a different article on DSPdimension.com), but it
requires additional post processing for be seen as a special case of a family of transforms that use basis functions other than the ing the concept in this direction is beyond the scope of this article. Finally, it is important to mention that there is a more efficient
implementation of the DFT, e Fast Fourier Transform (FFT) which was originally conceived by Cooley and Tukey in 1969 the work of Gauss and others). The FFT is just an efficient algorithm that calculates the DFT forward approach given above, it is otherwise identical with regard to its results. However, emented in the Cooley/Tukey
algorithm it requires that the transform length be a power of table constraint for most applications. The available literature on different FFT implementations y that there are many different FFT implementations, some of which do not have the power
ical FFT. An implementation of the FFT is given by the routine smbFft() in Listing 1.4 below.
Listing 1.4: The Discrete Fast Fourier Transform (FFT):
#define M_PI 3.14159265358979323846
void smbFft(float *fftBuffer, long fftFrameSize, long sign) /*
FFT routine, (C)1996 S.M.Bernsee. Sign = -1 is FFT, 1 is iFFT (in verse)
Fills fftBuffer[0...2*fftFrameSize-1] with the Fourier transform of the time domain data in fftBuffer[0...2*fftFrameSize-1]. The F FT array takes and returns the cosine and sine parts in an interl eaved manner, ie. fftBuffer[0] = cosPart[0], fftBuffer[1] = sinPa rt[0], asf. fftFrameSize must be a power of 2. It expects a compl ex input signal (see footnote 2), ie. when working with 'common' audio signals our input signal has to be passed as {in[0],0.,in
一天征服傅里叶变换[英] 页码，9/11
http://www.31ic.com/Article_Print.asp?ArticleID=619 2004-10-18 PDF created with pdfFactory trial version www.pdffactory.com
[1],0.,in[2],0.,...} asf. In that case, the transform of the freq
uencies of interest is in fftBuffer[0...fftFrameSize]. */ {
float wr, wi, arg, *p1, *p2, temp; float tr, ti, ur, ui, *p1r, *p1i, *p2r, *p2i; long i, bitm, j, le, le2, k;
for (i = 2; i < 2*fftFrameSize-2; i += 2) {
for (bitm = 2, j = 0; bitm < 2*fftFrameSize; bitm <<= 1) {
if (i & bitm) j++; j <<= 1; } if (i < j) {
p1 = fftBuffer+i; p2 = fftBuffer+j; temp = *p1; *(p1++) = *p2; *(p2++) = temp; temp = *p1; *p1 = *p2; *p2 = temp; } }
for (k = 0, le = 2; k < (long)(log(fftFrameSize)/log(2.)); k++) { le <<= 1; le2 = le>>1; ur = 1.0; ui = 0.0;
arg = M_PI / (le2>>1); wr = cos(arg); wi = sign*sin(arg); for (j = 0; j < le2; j += 2) { p1r = fftBuffer+j; p1i = p1r+1; p2r = p1r+le2; p2i = p2r+1; for (i = j; i < 2*fftFrameSize; i += le) {
tr = *p2r * ur - *p2i * ui; ti = *p2r * ui + *p2i * ur;
一天征服傅里叶变换[英] 页码，10/11
http://www.31ic.com/Article_Print.asp?ArticleID=619 2004-10-18 PDF created with pdfFactory trial version www.pdffactory.com
*p2r = *p1r - tr; *p2i = *p1i - ti;
*p1r += tr; *p1i += ti; p1r += le; p1i += le; p2r += le; p2i += le; }
tr = ur*wr - ui*wi;
ui = ur*wi + ui*wr; ur = tr; } } } 1
simply speaking, trigonometric functions are functions that are used to calculate the angles in a triangle (tri
rom the length of its sides, namely sinus, cosinus, tangent and the arcus tangent. The sinus and cosinus functions as the tangent and arcus tangent can be obtained from sinus and cosinus relationships alone. 2
Note that in the literature, due to a generalization that is made for the Fourier transform to work with another plex signal' (complex in this context refers to a certain type of numbers rather than to an input signal that has u will encounter the sine and cosine part under the name 'real' (for the cosine part) and 'imaginary' part (for 3
if you're already acquainted with the DFT you may have noted that this is actually an implementation of the it uses only real numbers as input and does not deal with negative frequencies: in the real DFT positive and and thus redundant. This is why we're calculating only almost half as many bins than in the sine transform (e highest frequency, for symmetry reasons).
Last change: 29.11.1999, .1999 S. M. Bernsee, all rights reserved. Content subject to change without notice. mer. Graphs made using Algebra Graph, MathPad, sonicWORX and other software. Care has been taken to describe rate as possible. If you find errors, typos and ambiguous descriptions in this article, please notify me Special thanks to Richard Dobson for providing immensely useful suggestions and corrections to my incomplete e.
一天征服傅里叶变换[英] 页码，11/11
http://www.31ic.com/Article_Print.asp?ArticleID=619 2004-10-18 PDF created with pdfFactory trial version www.pdffactory.com
一天征服傅里叶变换+英文版
