一天征服傅里叶变换[英]
作者：Stephan M. Bernsee 转贴自：internet 点击数：169 您要打印的文件是：一天征服傅里叶变换[英]
The DFT à Pied:
Mastering The Fourier Transform in One Day
by Stephan M. Bernsee, http://www.dspdimension.com, . 1999 all rights reserved*
If you're into signal processing, you will no doubt say that the
headline is a very tall claim. you can't learn all the bells and whistles of the Fourier transform in one day without practising lly delving into the maths. However, this online course will provide you with the basic knowledge form works, why it works and why it can be very simple to comprehend when we're using proach.The important part: you will learn the basics of the Fourier transform completely without ond adding and multiplying numbers! I will try to explain the Fourier transform in its practical processing in no more than six paragraphs below.
Step 1: Some simple prerequisites
What you need to understand the following paragraphs are essentially four things: how to and divide them and what a sine, a cosine and a sinusoid is and how they look. Obviously, nd just explain a bit the last one. You probably remember from your days at school the
'trigonometric re somehow mysteriously used in conjunction with triangles to calculate the length of its sides ice versa. We don't need all these things here, we just need to know how the two most
important s, the sine and cosine look like. This is quite simple: they look like very simple waves with stretch out to infinity to the left and the right of the observer.
As you can see, both waves are periodic, which means that after a certain time, the
o, both waves look alike, but the cosine wave appears to start at its maximum, while the sine practice, how can we tell whether a wave we observe at a given time started out at its maximum, on: we can't. There's no way to discern a sine wave and a cosine wave in practice, thus we sine or cosine wave a sinusoid, which is Greek and translates to sinus-like. An important property y, which tells us how many peaks and valleys we can count in a given period of time. High The sine wave
The cosine wave
一天征服傅里叶变换[英] 页码，1/11
http://www.31ic.com/Article_Print.asp?ArticleID=619 2004-10-18 PDF created with pdfFactory trial version www.pdffactory.com and valleys, low frequency means few peaks and valleys: Step 2: Understanding the Fourier Theorem
Jean-Baptiste Joseph Fourier was one of those children parents are either proud or ashamed ghly complicated mathematical terms at them at the age of fourteen. Although he did a lot ifetime, the probably most significant thing he discovered had to do with the conduction of with an equation that described how the heat would travel in a certain medium, and solved series of trigonometric
functions (the sines and cosines we have discussed above). Basically, at Fourier discovered boils down to the general rule that every signal, however complex, can sinusoid functions that are individually mixed. An example of this:
What you see here is our original signal, and how it can be
approximated by a mixture of s) that are mixed together in a certain relationship (a 'recipe'). We will talk about that recipe more sines we use the more accurately does the result resemble our original
waveform. In are continuous, ie. you can measure them in infinitely small intervals at an accuracy that is ment equipment, you would need infinitely many sines to perfectly build any given signal. ot living in such a world. Rather, we are dealing with samples of such
'realworld' signals that ervals and only with finite precision. Thus, we don't need infinitely many sines, we just need that 'how much is a lot' later on. For the moment, it is important that you can imagine that r computer can be put together from simple sine waves, after some cooking recipe.
Step 3: How much is a lot
Low frequency sinusoid Middle frequen cy sinusoid High frequency sinusoid This is our origi nal
One sine Two sines
Four sines Seven sines Fourteen sines
一天征服傅里叶变换[英] 页码，2/11
http://www.31ic.com/Article_Print.asp?ArticleID=619 2004-10-18 PDF created with pdfFactory trial version www.pdffactory.com
As we have seen, complex shaped waveforms can be built from a mixture of sine waves. We m are needed to build any given signal on our computer. Well, of course, this may be as few vided we know how the signal we are dealing with is made up. In most cases, we are dealing might have a very complex structure, so we do not know in advance how many 'partial' waves In this case, it is very reassuring to know that if we don't know how many sine waves constitute is an
upper limit to how many we will need. Still, this leaves us with the question of how many y to approach this intuitively: assume we have 1000 samples of a signal. The sine wave with most peaks and valleys in it) that can be present has alternating peaks and valleys for every with the highest frequency has 500 peaks and 500 valleys in our 1000 samples, with every he black dots in the following diagram denote our samples, so the sine wave with the highest Now let's look how low the lowest frequency sine wave can be. If we are given only one single we be able to measure peaks and valleys of a sine wave that goes
through this point? We waves of different periods that go through this point.
So, a single data point is not enough to tell us anything about
frequency. Now, if we were d be the lowest frequency sine wave that goes through these two points? In this case, it is ry low frequency sine wave that goes through the two points. It looks like this:
Imagine the two leftmost points being two nails with a string spanned between them (the nts as the sine wave is periodic, but we really only need the leftmost two to tell its frequency). can see is the string swinging back and forth between the two nails, like our sine wave does two points to the left. If we have 1000 samples, the two 'nails' would be the first and the last The highest frequency
sine wave
Many sine waves go through o ne single point, so one point d oesn't tell us about frequency The lowest frequency sine w ave
一天征服傅里叶变换[英] 页码，3/11
http://www.31ic.com/Article_Print.asp?ArticleID=619 2004-10-18 PDF created with pdfFactory trial version www.pdffactory.com
1 and sample number 1000. We know from our experience with musical instruments that down when its length increases. So we would expect that our lowest sine wave gets lower ur nails farther away from each other. If we choose 2000 samples, for instance, the lowest since our 'nails' are now sample number 1 and sample number 2000. In fact, it will be twice ow twice as far away as in the 1000 samples. Thus, if we have more samples, we can discern ency since their zero crossings (our 'nails') will move farther away. This is very important explanations.
As we can also see, after two 'nails' our wave starts to repeat with the ascending slope (the entical). This means that any two adjacent nails embrace exactly one half of the complete ther one peak or one valley, or 1/2 period.
Summarizing what we have just learned, we see that the upper
frequency of a sampled sine being a peak and a valley and the lower frequency bound is half a period of the sine wave ber of samples we are looking at. But wait - wouldn't this mean that while the upper frequency frequency would drop when we have more samples? Exactly! The result of this is that we will n we want to put together longer signals of unknown content, since we start out at a lower All well and good, but still we don't know how many of these sine waves we finally need. As upper frequency any partial sine wave can have, we can calculate how many of them fit in e we have nailed our lowest partial sine wave down to the leftmost and rightmost samples, waves use these nails as well (why should we treat them differently? All sine waves are created sine waves were strings on a guitar attached to two fixed points. They can only swing between break), just like our sine waves below. This leads to the relationship that our lowest partial second partial (2) fits in with 1 period, the third partial (3) fits in with 1 1/2 period asf. into king at. Graphically, this looks like this:
Now if we count how many sine waves fit in our 1000 samples that way, we will find that we es added together to represent the 1000 samples. In fact, we will always find that we need d samples.
The first 4 partial sine waves (cl ick to enlarge)
一天征服傅里叶变换[英] 页码，4/11
http://www.31ic.com/Article_Print.asp?ArticleID=619 2004-10-18 PDF created with pdfFactory trial version www.pdffactory.com Step 4: About cooking recipes
In the previous paragraph we have seen that any given signal on a computer can be built We have considered their frequency and what frequency the lowest and highest sine waves onstruct any signal we analyze. We have seen that the number of samples we are looking the lowest partial sine wave that is needed, but we have not yet discussed how the actual o yield a certain result. To make up any given signal by adding sine waves, we need to measure them. As a matter of fact, frequency is not the only thing we need to know. We also need ne waves, ie. how much of each sine wave we need to mix together to reproduce our input eight of the peaks of a sine wave, ie. the distance between the peak and our zero line. The der it will sound when we listen to it. So, if you have a signal that has lots of bass in it you e must be a greater portion of lower frequency sine waves in the mix than there are higher nerally, the low frequency sine waves in a bassy sound will have a higher amplitude than the In our analysis, we will need to determine the amplitude of each partial sine wave to complete Step 5: About apples and oranges
If you are still with me, we have almost completed our journey towards the Fourier transform. y sine waves we need, that this
number depends on the number of samples we are looking upper frequency boundary and that we somehow need to determine the amplitude of the plete our recipe. We're still not clear, however, on how we can determine the actual recipe we would say that we could find the amplitudes of the sine waves somehow by comparing
y to the samples we have measured and find out how 'equal' they are. If they are exactly ave must be present at the same amplitude, if we find our signal to not match our reference xpect this frequency not to be present. Still, how could we effectively compare a known sine al? Fortunately, DSPers have already figured out how to do this for you. In fact, this is as numbers - we take the 'reference' sine wave of known frequency and unit amplitude (this tude of 1, which is exactly what we get back from the sin() function on our pocket calculator y it with our signal samples. After adding the result of the multiplication together, we will tial sine wave at the frequency we are looking at. To illustrate this, here's a simple C code Listing 1.1: The direct realization of the Discrete Sine Transform (DST):
#define M_PI 3.14159265358979323846 long bin,k; double arg;
for (bin = 0; bin < transformLength; bin++) { transformData[bin] = 0.;
for (k = 0; k < transformLength; k++) {
arg = (float)bin * M_PI *(float)k / (float)transformLength; transformData[bin] += inputData[k] * sin(arg);
一天征服傅里叶变换[英] 页码，5/11
http://www.31ic.com/Article_Print.asp?ArticleID=619 2004-10-18 PDF created with pdfFactory trial version www.pdffactory.com
This code segment transforms our measured sample points that are stored in inputData[0...transformLength
amplitudes of its partial sine waves transformData[0...transformLength-1]. According to common terminology, ncy steps of our reference sine wave bins, which means that they can be thought of as being the amplitude of any of the partial waves we evaluate. The Discrete Sine Transform (DST) sumes we have no idea what our signal looks like, otherwise we could use a more efficient mplitudes of the partial sine waves (if we, for example, know beforehand that our signal is
equency we could directly check for its amplitude without calculating the whole range of sine h for doing this based on the Fourier theory can be found in the literature under the name For those of you who insist on an explanation for why we calculate the sine transform that ach to why we multiply with a sine wave of known frequency, imagine that this corresponds al world happens when a 'resonance' at a given frequency takes place in a system. The
一天征服傅里叶变换+英文版
