Fourier for dummies - under construction

prof_brainoprof_braino Posts: 4,312
edited 2012-02-25 - 11:02:56 in Propeller 1
Bean gave us CODRIC for dummies

http://forums.parallax.com/showthread.php?t=127241&page=2

and discussion arose of the need for Fourier for dummies.

Rather than punish Bean for his good work, it was suggested (by me) that the rest of us work together to create something using Bean as inspiration.

Heater can't see this working (blind leading the blind and all), so now it is a challenge, and the result will be decided by whether he or I or anybody else can claim to have gained an understanding of Fourier when work stops.

If somebody that already has a clear understanding of Fourier
could point out when we've gone wrong, that would be appreciated.

Otherwise, any interested party can post/contribute.

Bean's format looks like this to me:

a) one sentence high level explanation

b) first basic concept

c) example of first basic concept

d) next concept

e) example combining concepts

f) mostly integers

g) long strings of float only used when we are showing how we get rid of them:

"So what angle would give us Tan(Angle) = 0.500.
It turns out to be 26.56505118.
Now this isn’t exactly half of 45, but it doesn’t really matter.
As long as it is smaller than 45 and larger than or equal to 22.5 it will work."

I believe this last is the "magic".

So let's get started. There are a couple different places to start:

The whole idea is that a periodic function might be broken down into simpler components. Is this correct?
For example, a violin note might broken into constituent triangle and saw-tooth waves of different frequencies; Or a voice might be broken into constituent wave forms and the composition changes over time.

Edit: The goal - to understand this Fourier thing and how to use it on the prop.
«134567

Comments

  • Heater.Heater. Posts: 21,233
    edited 2010-11-20 - 10:43:39
    I make the observation that Bean pulled off his CORDIC explanation without the use of matrix notation or other heavy weight mathematical notation that you normally see in documents claiming to introduce the CORDIC algorithm(s). For example see the wiki entry on CORDIC http://en.wikipedia.org/wiki/CORDIC

    As I said on the CORDIC for dummies thread, this confirms my belief that there are some beautiful, simple, elegant ideas in mathematics that almost anyone could understand if they could be explained without all the usual mathematical baggage. That is to say, the essence of the idea does not need all that confusing and mysterious symbology (is there such a word?)

    So with Fourier analysis/transform and the DFT top marks to anyone who can explain the essential concepts the core of the idea without:

    1) Complex numbers.
    2) Integral signs.

    I make another observation:

    When you perform the Young's Slits experiment, as many here will have done at school at least, the pattern of light observed on the screen is the Fourier Transform of the geometry of the slits that the light travelled through. Perhaps they did not tell you that at school as in my case.

    Anyway in that experiment the result appears on the screen, the light "does the trick" without any "imaginary" things going on.

    Similarly when I calculate a Fourier Transform on my computer for sure there are no imaginary numbers in use. An x86 CPU for example does not have such a type.

    My philosophical conclusion is that it is possible to make an exposition of the Fourier Transform and the discrete FFT without the use of imaginary numbers. And therefore the essence of the idea should be understandable by the mathematically unsophisticated.

    Get rid of the integrals and exponentials and we are onto a winner.
  • Heater.Heater. Posts: 21,233
    edited 2010-11-20 - 10:59:37
    By the way, is the Propeller Chip forum the correct place for such a general thread?
  • potatoheadpotatohead Posts: 9,995
    edited 2010-11-20 - 11:58:45
    IMHO, YES!

    I enjoyed the Cordic material very much. I am one of those mathematically unsophisticated people.

    The higher level concepts are easy to visualize for me, but not so easy to abstract into the higher level math forms. Early on in my education, I made the observation that computers do only a few things:

    Add, copy numbers around, and operate on them logically. That's it!

    Bean's explanation is powerful because it hits home at that level, and it's very enlightening, and relevant to the Prop because of where it is at math wise.

    There are lots of basic math shortcuts, all leveraging numerical compliments, modulo, and other core things seen in computers regularly, but not in ordinary math as I see taught.

    Getting to that level with more complex ideas is very useful, not just to programmer types, but to ordinary people too. I would vote to encourage this kind of thing here, because of that.

    Recently, I was having a math discussion with a Stanford grad working with us. This guy knows his higher math, and often teaches me things I missed out on, largely because I got side tracked on manufacturing and computers at that time in my life. He went into materials science and the physics of that as related to people and the world they live and play in. (they engineer things like sports wear, boat hulls that move through water more efficiently, wake and snow boards, etc...)

    Just the other day, both of us were talking about kids and how to show them math concepts. Simple things like: -5x+x-6x for example. What's going on here? To me, it's just a few adds. (-5x) + (+x) + (-6x). We were discussing "combine terms", and just what "combine" means, and it means ADD, just by way of one example to highlight what I'm talking about. The same is true for something like 3-5=-2 It's just (+3)+(-5), and when only adding, young people can get the sign rules right away, where if subtract is also done, they have to remember two sets and get that right! (worked wonders with my kids)

    Anyway, we've been working with some powerful simulation software that I regularly use, support and demonstrate to people. I don't get all the math behind that software, and he does. It's been very interesting to break the core things down to what the computers really do. That is very, very different from the higher order math used to derive what to do in the first place. We met because I've modeled many of the things he does over the years, which I do well, and he's crunched the numbers by hand, vetting simulations on computer.

    We ended up with "math purists" and "math geeks", vs, ordinary people and practical, applied math discussion, and the difference between the purists and the engineers. The purists build tools, which the engineers then apply to get stuff done. Very different things, both necessary things. Ordinary people work more like the engineers do, when they have the tools expressed in ways they can grapple with.

    We have a solid population of ordinary people here, which speaks to the relevance.

    IMHO, this kind of thing is just as important as the higher order constructs are, so that we can merge theory, our understanding of the physics, and realize applications and engineering and computation on that to our mutual benefit.

    Sorry for being wordy, the core message here is "please do", and I just thought a moment talking about why made sense. Scroll me, if you need to.

    :)

    Edit: I have a idea for breaking down complex sounds into components floating around in my head for years. One day, I would like to code on it, apply some pattern matching ideas, and explore how we break down complex, combined sounds, and a better understanding of Fourier would help. Deffo interested. Props might not compute fast enough for it to be useful in real time, or on large datasets, but would be a good prototyping place to begin.
  • SapiehaSapieha Posts: 2,964
    edited 2010-11-20 - 13:48:32
    Hi Heater.

    I say same as potatohead ---- IMHO, YES!. --> But maybe add some extra comments.

    If possible Give some example code that can run in SPIN for Beginners.


    Ps. That can give Beginners good info how to start mathematic calculations in SPIN on Propeller
    Heater. wrote: »
    By the way, is the Propeller Chip forum the correct place for such a general thread?
  • Heater.Heater. Posts: 21,233
    edited 2010-11-21 - 00:11:58
    Here is a guy who has done a lot of work on this already.http://www.katjaas.nl/home/home.html

    OK he goes head first into the complex plane and I have no idea how understandable it is yet but it all looks very beautiful.
  • ErNaErNa Posts: 1,344
    edited 2010-11-21 - 07:29:34
    This is a very interesting challenge, because there is a basic operation: "butterfly" in the FFT and is not clear to me, why this, when repeated, shifted, ... creates a frequency spectrum from a spacial or time function.

    OK, anyway, there is a discussion if Fourier needs matrices or better to use complex numbers. I do not like complex numbers very much, because there is the "imaginary" part, that is somehow frightening . I prefer the vector approach.

    With an infinite number of dimensions, of course.
  • prof_brainoprof_braino Posts: 4,312
    edited 2010-11-21 - 08:05:09
    Heater. wrote: »
    Here is a guy who has done a lot of work on this already.http://www.katjaas.nl/home/home.html

    OK he goes head first into the complex plane and I have no idea how understandable it is yet but it all looks very beautiful.

    Whoa! THERE'S a guy who cares!
  • prof_brainoprof_braino Posts: 4,312
    edited 2010-11-21 - 08:09:17
    ErNa wrote: »
    OK, anyway, there is a discussion if Fourier needs matrices or better to use complex numbers.

    I do not like complex numbers very much, because there is the "imaginary" part, that is somehow frightening .

    This is good information.

    If there it is easier to without imaginary parts, then the choice is easy.

    However, I like the imaginary route, BECAUSE it is scary.
  • ErNaErNa Posts: 1,344
    edited 2010-11-21 - 08:48:32
    To me the key to fourier transform is vector algebra. We know: if there are two vectors and the scalar product is zero, then these vectors are orthogonal. If the scalar product of a vector with himself is 1, then this vector is called to be normalized, his length is one. The fascinating thing is: we all have problem to imagine vectors with more then three dimensions in space, but why do we care? We have an array of lets say 40 elements, a second one, we multiply component for component and sum up, if the result is zero, these two arrays can be seen as representing 40-dimensional vectors, which are perpendicular. That is just a convention and the question is, is there an application.

    Now we can easily verify by just sketching a sinus and cosine of the same frequency, that they can be seen as orthogonal vectors. Because when you multiply sin*cos from left and from right, one of the products will be positive, the other one negative, but have same value, so there sum is zero and this is true for all values from the left or the right to the middle. q.e.d.
  • potatoheadpotatohead Posts: 9,995
    edited 2010-11-21 - 10:47:01
    Heater. wrote: »
    Here is a guy who has done a lot of work on this already.http://www.katjaas.nl/home/home.html

    OK he goes head first into the complex plane and I have no idea how understandable it is yet but it all looks very beautiful.

    That site is beautiful. I've read through some of his "beginner" work to help people understand DSP related concepts. It's excellent! I have a lot of trouble at that level, and found his explanations of matrices and complex numbers as rotations understandable. Love the style. Personification is always fun, and I'm a fan of it personally.

    Thanks for linking that diversion.

    One rather profound bit of insight gleaned from his pages is curvature = frequency. There is a photo where he's got a decaying resonator detailed, with scope plots, and it's very clear that radius on the X-Y plot = amplitude, and curvature equals frequency, with rotation being time. Never understood that, or what "negative frequencies" were, until spending more time on that site last night than I care to admit.
  • BRBR Posts: 92
    edited 2010-11-21 - 17:21:30
    FFTs (and DSP in general) are a fascinating topic.

    If you're interested in a simple, clear explanation of FFT that focuses on concepts and not math, I highly recommend Steven W. Smith's book (available online for free):
    http://www.dspguide.com

    Chapter 12 covers FFT.

    Also, I have cataloged all the prop-based FFT solutions that I'm aware of in this thread.
  • ErNaErNa Posts: 1,344
    edited 2010-11-21 - 23:20:21
    One remark about complex numbers:

    Just: there is no complex number. If you know this, there is no need to know, what "complex number" means.

    But if you are thinking about fourier transform, you should be aware, that you are always working with pairs of numbers.

    Let us use different words and you may understand, what I mean: All man are created equal, but there are men and women. Complexity comes from being married, therefor: complex number.

    "Normal" numbers can be seen as singles, but they are just pairs of numbers where the second half is 0 and always zero and therefore is not written down, just to save time.

    If you have a time depending signal, that is, just an array of numbers, and lets say: 512 of them, then you must input into the fourier transform a second array, where all element are equal 0. That does not mean, that they do not exist. So the input consists of 1024 value.

    The output again is 1024 values. But you can not have nothing from nothing. So, how can you make 1024 output values from 512 different input values?

    The point is: you do not get 1024 independent values, but 512 * 2 values, every value comes twice, the spectrum is symmetrical.

    What you have to understand in doing the FT is not the algorithm, this is just mechanic. It is the meaning, the "philosophical" background.

    Someone said: the greatest miracle is not, that there is math, but that math is related to real things. A FT allows you to see, if there is something repeatedly happening. As I have showed above, the scalar product of sin and cos in the range of 0 - 2pi is zero, because of the symmetry. The same is true for the scalar product <sinus|constant>. If you multiply a sinusoidal by a constant and you add together all the values (equidistant, no matter how many), you will always have a result 0, independent of the frequency of the sinusoidal, if only the range is a multiple of 2Pi. That is, if you have a fundamental frequency in a range of 2Pi and any number of harmonics, then the scalar product between these and a constant will always be 0: a DC-Voltage has no frequency spectrum. Or, as we say, to be consistent: The frequency is ZERO ;-)
  • Beau SchwabeBeau Schwabe Posts: 6,420
    edited 2010-11-26 - 22:09:51
    If you can follow it, here is a good You-Tube video reference to FFT ...


    Reference:
    Part1 http://www.youtube.com/watch?v=ObklYbQaX24
    Part2 http://www.youtube.com/watch?v=QO3kgwYzpZg&NR=1
    Part3 http://www.youtube.com/watch?v=6-llh6WJo1U&NR=1
  • ErNaErNa Posts: 1,344
    edited 2010-11-27 - 02:07:54
    I did not follow the video to the end, because already the first after a short time presents this equation
    (voice: another way to represent the signal is by the sum)

    f (t) = SUM (f (tn) * delta(t-tn) )

    and already here I see an error:

    f (t) = SUM (f (t) * delta(t-tn) )

    because it is the delta-function, which cut the value f(tn) from the function f(t)

    And there is a short way from some to integral form, what in reality is a complex mathematical transaction.

    So to me it seems not useful do watch the whole presentation.

    By the way "for dummies" and political correctness: If I explicitly present something to "dummies", I want to show, that I found a way to have others take part in something fascinating. If my intention is, to keep them in the dummy state, I would just give a lecture on a very high, foggy level, everybody will be impressed and no one will have learned something.
    I only read books for dummies. But I have problems to write them ;-(
  • prof_brainoprof_braino Posts: 4,312
    edited 2010-11-27 - 09:10:27
    This thread is now one week old. It has attracted several participants, and many watchers.

    Some have no idea about Fourier, what its used for, or how it works.
    Some have a working knowledge of how to use it, but don't understand it.
    Some have a very detailed understanding, but can't explain it very well to the target audience.

    I suggest that Fourier for Dummies is not the simplest topic this forum has addressed, but we are making excellent progress. Already we see an issue between the references (thanks Beau!) and actual users that understand it (thanks ErNa!). Such issues would totally derail a new person, so it is essential to identify and resolve such issues.

    Fourier is four concepts I guess, based on what I found in wiki:

    1) Fourier the dead guy - who was known for checking out heat transfer and vibrations

    2) Fourier series - decomposing a complex periodic function into its simple component functions.

    In audio this is something like breaking a violin note into a sawtooth wave of the base frequency, and a bunch of sine wave at higher multiples tof that frequency. The cool part is the mixture of the higher frequencies (harmonics) makes a noise become a violin.

    3) Fourier transform is the method to decompose a signal into it's component frequencies

    4) Fourier analysis is breaking the complex signal into its components in terms of the sums of simple trigonometric functions

    - - - - - -

    So, that is a first stab at the first step of Fourier for dummies. Could someone correct or simplify the above? How do we change it to fit Bean's format for "for dummies"?

    - - - - - -


    a) one sentence high level explanation

    b) first basic concept
    c) example of first basic concept
    d) next concept
    e) example combining concepts
    f) mostly integers
    g) long strings of float only used when we are showing how we get rid of them
  • ErNaErNa Posts: 1,344
    edited 2010-11-27 - 10:34:51
    The transform is hard to explain, because there is a basic understanding at start and this hinders getting the concept.

    The key hurdle is: complex numbers and imaginary part. Introducing complex numbers eases calculation, but complicates understanding.

    How to come around complex numbers?

    We have to know, that whenever we add a sinusoidal function to another sinusoidal function, the result is a sinusoidal. And: a co-sinusoidal function is a sinusoidal function shifted in X-axis by 1/4 of the period, independent what X designates, time, space, temperature, wellness. 1/4 of the period is synonymous to 90° or pi/2. Nothing else.

    Now, as we add to sinusoids the resulting function is a sinusoid, but with different amplitude and different phase (in general), depending on phase shift and amplitude of the original functions.

    Further we have to know: if there is a given sinusoid with amplitude and phase shift, that is, the raising slope crossing x-axis (that is: y = 0) not at x=0 or n*2Pi, then we can always find a sinusoid with phase shift 0 and a sinusoid with phase shift 90° (which we call co-sinusoid for simplicity) with given amplitude, that in sum form just this first shifted sinusoid.

    So, that is the reason, why we introduce pairs of numbers to express a shifted sinusoid: we decompose this to two sinusoids with special properties: the first is not shifted in phase, the second by 90°. From this we get some advantage in calculation, but not in understanding. Understanding gets more complicated.

    Now, why complex numbers? First we only have pairs of numbers, the amplitudes of the two components sinusoid and co-sinusoid. But, as we know, that the x- and y-axes of a every point of a circle can be determined by sinusoid and co-sinusoid of a given angle with leg length equal to the circles radius, we inversely can express every point of this circle by an x- and y-value. We now omit the x and y and replace x by nothing and y by i.

    So, what we do is: we have an original function of sinusoidal form with a given phase shift and express this function by a sinusoid of a given amplitude (with phase shift 0) and a co-sinusoid of a given amplitude (also with phase shift 0, but this is a sinusoid with phase shift 90°) and just because there is some advantage in calculation, we write the to numbers not as a vector (x,y) (that is a modern interpretation of having pair of numbers), but as to numbers separated by a + sign and to discrimitate y form x, we place a signature "i" to the y-value. Thats it, and there is nothing "imaginary"
  • Heater.Heater. Posts: 21,233
    edited 2010-11-27 - 10:57:27
    Prof_Braino,

    Below is the text of a post I wrote yesterday and was a bit nervous about actually posting because I can see it's going to require some serious effort and I'm not sure I have the writing and organizational skill to pull it off. But given you last post, here goes...

    Here are my criteria for "Fourier For Dummies":

    0) The reader has a basic idea of signals, samples, analog to digital conversions some programming, typical basic electronics/micro controller stuff.
    1) The reader has heard of this magical Fourier Transform that can tell you what frequencies are in a signal but cannot begin to make headway on understanding the usual explanations and accompanying maths. Similarly any code he has seen that does a Four Transform is baffling.
    2) The reader has a grasp of basic high school maths, sin, cos, pythagoras, averages etc.
    3) The reader has little or no idea about higher maths, integrals, series summation, exponentials, complex numbers...
    4) Fourier For Dummies will not use integrals, exponentials or complex numbers.
    5) We may never get to the Fast Fourier Transform unless someone comes up with a simple way to continue the story.

    Yesterdays thoughts...

    Over on the CORDIC for dummies thread prof_braino came up with the idea of Fourier For Dummies (The FFD:)) and made this comment:
    Any takers? I nominate Heater, he says he knows the Fourier part.

    Well, thanks a lot Braino. With that single statement you have crashed my brain for a week:) Pondering how to go about creating such an essay, to the exclusion of everything else I'm supposed to be thinking about from time to time.

    Well, the result is I think I have dreamt up a way to introduce the Fourier transform for sampled signals in such a way that the mathematically naive can get to an understanding of the core concept without any integrals, sigmas, exponentials, imaginary numbers or even pi. A high school understanding of cos and sin will do.

    I'm not sure about what to do for example code. Doing this in Spin will be messy as Spin has no floating point. Perhaps C would do or just pseudo code. Or perhaps something like Python makes a good pseudo code for this.

    If no one else has started on such a document yet I will make a stab at it. Probably dribbling out in small parts with an invitation for comments.
  • Beau SchwabeBeau Schwabe Posts: 6,420
    edited 2010-11-27 - 11:50:37
    That's unfortunate, I thought the video, especially the last one bought things together. It's more of a reference anyway. :-(


    I'm not claiming a vast understanding of FFT but I believe I understand the concept.

    We live in the time domain... everything we do we understand as a reference of time. We eat, sleep, etc. at regular intervals that are periodic in nature. If you were to 'stack' all of the periodic events that happen throughout a day it would become a mess and difficult to see all of the superimposed waveforms. So we need another way to quantify this data. One answer is FFT. FFT represents the frequency domain of the same data. Which means that a range of frequencies are represented from LEFT to RIGHT rather than a time interval. Since in FFT the period can be from +infinity to -infinity, you typically set a window or a sweep of frequencies and apply each period that represents the swept frequency to the entire data sample. These are the values that you SUM together and are represented vertically, while the next frequency in the sweep is applied to the data all over again and incremented horizontally. How you divide up the Period of the particular frequency that you are sweeping is up to you but be aware that the sample frequency (The rate at which the original data was sampled) will have a beat frequency against the rate at which the period was divided that will most likely show up as a component int he FFT output.
  • ErNaErNa Posts: 1,344
    edited 2010-11-27 - 12:40:04
    To gain a deeper understanding of fourier transform the first step is: forget what you know. Start from the very beginning.

    Fourier transform has nothing to do with sinusoids. There is no time domain or frequency domain. Nothing.

    Now define an EVENT. Something happens. To have an event, there is a precondition: the event is not. Then it is. Then it is not again. For something to happen, we need the concept of time. I am not willing to tell, what time is ;-) . But I can tell a property of time: time allows things to change.

    If we use the word "then" we automatically think in terms of time. But that is not necessarily the case.

    Let me make an example:
    you are walking a road and fall into a pit. You can describe this from view of time: there is no pit, there is a pit, there is no pit. But also from the point of space: the road is ok, there is a pit, the road is ok.

    Have mercy: I do not find another example.

    The same scenario, but a row of people is going side by side down the road, only one falls in the pit: this single pit can be seen in space and time: In space: only one of the man "finds" the pit, in time: it doesn't happen always, only at a given moment.

    Now we have a single "event" arranged in space and time.

    If now the row is walking down the road and a man falls into a pit more than once, we say: the event is repeated in time. If in one moment more than one man falls into a pit, we have an event repeated in space. And we can have this in a regular or stochastic way.

    The fourier transform gives us numbers, which describe the existence of the pits in time and space.

    Now, let us have a linear row of pits crossing the street. A row of men walking down the street will see a event in space, because they all reach the pits at one moment, but a number of them falls into the pits.
    The same row of men crossing the street will find a event in time, because only one will fall into the pits, all the others will go left and right.

    So, in this simple example I wanted to introduce the concept of space and time and we also see, that space and time may be swapped, as the environment is detected by experience.

    So often people discuss the 4 dimensional space time. This is to me misleading. We are existing in time and space and time allows us to change our state, for example, we are able to learn, and space allows us to be not alone, because two objects can not exist in the same place and if there is no space, then there only one object possible.
    Why does it make sense to have only one dimension in time: You can not change a state in two ways and be still one. See Jekyll&Hide. If time had more than one dimension, you would just deliquesce. But if space would have only one dimension, you just could not pass along the street. Event two dimensions are a little insufficient, because you have no chance to gain potential energy. The third dimension solves this problem, and some others too: you can build a town and lay in your bed alone.

    This contribution doesn't use imaginary numbers, but some imagination, so: it is persistant in time and space and can be read in time and space.

    By the way, there is a story: a famous, old director from the cologne G
  • prof_brainoprof_braino Posts: 4,312
    edited 2010-11-27 - 14:24:42
    You guys are excellent!

    @heater - thank you very much. I did not intend to saddle you with writing the entire document, although the rest of us surely benefit if it works out that way. I'm hoping your "first stab" is a step towards a community effort, you of course have other fun projects to tend to.

    @Beau and ErNa - this is really good: two perspectives, one from the math, one from the application of the concepts (I think) :) . In any case, they need not be viewed as contradictory; the task is to determine how both fit into the discussion to benefit the explorer. This is the really tough part, determining what will make the light go on in the reader's mind.

    At the moment I can't understand either set of explanations, nor most of the explanations on the web. I'm sure many of the rest of the folks watching feel the same way. If folks could respond noting when "the light switches on", that will be extraordinary benefit.

    This is a really cool experiment!
  • ErNaErNa Posts: 1,344
    edited 2010-11-28 - 05:45:09
    I will give an example for a fourier transform.

    Imagine, you have a delta distribution, often called delta function. Why the two words? In a mathematically exact sense, there is a difference, because a function somehow is well defined, while a distribution just has some properties.

    Imagine you have a gaussian function, this function starts from -infinity, but the y value is very very very small (indeed, no function decays faster than the exponential e^-x, and the gaussian is this function squared, so reaches a value of 1 for e^0 and decays to the + and - values, the point of inflection is reached at +- standard deviation.

    This function is well defined, and also well known. So, if we modify the equation to have a variable standard deviation, and if the standard deviation goes to zero, than the function becomes much higher and narrows the way, that the area under the graph stays constant. In the end, at zero width, the graph reaches infinity as a value. But this is not a valid situation in (normal) math.

    Now the distribution comes to the scene: The distribution doesn't have a discrete shape, but a property. The property is: the y-value of the distribution is zero, except in the place A. In this place the value is not defined, but somehow infinite. The property is: whenever you are determining the integral of this distribution is calculated, starting from - infinity, the value stays 0 until the x-value A is crossed. That very moment the integral raises to 1 and stays at 1 even when integrating up to +infinity. That is what is called a property:
    Whenever you come across A, the integral becomes 1, no matter where before A you start and where behind A you stop. Even if this distance is infinitely small.

    Now imagine: if you multiply a given function with this distribution, you run into a problem! How to do this?
    The solution is: we talked about the gaussian, which doesn't change the integral, independend on width. So if you are doing the limit transition to a with of zero, the gaussion shows the same property, a delta-distribution has. (and a delta distribution is, what I described above). So we substitute the distribution by gaussian with standard deviations -> 0

    Now we multiply a function with the gaussian and integrate and what we get as a result is just the y-value of the function at the place A. The gaussian is just a cutting knife. Sometimes called a Sampler. The physical equivalent is the sample-and-hold in front of an ADC.

    I think, this is another building block to understand fourier transform.
  • ErNaErNa Posts: 1,344
    edited 2010-11-28 - 22:32:27
    Now with such a "cutting knife" available, we can do this experiment:

    Let us say. we place the knife at x=0 and we take as a function to inspect a sinusoid. As sin (0) = 0, the knife will always return 0. Independent of the sinusoids frequency. If we take a co-sinusoid, the result will be 1.

    If we now move the knife slowly to positive x values, we will see, that the first output grows, while the second decreases. But as we may know (google for "as we may think"), the sum of the square of sin(x) and cos(x) is a constant and so is the square root, we call both numbers, which are related, with a new word. Two words are common: complex number or 2-dimensional vector.

    Again I point to this: as we do this, we "imagine". Thinking, doing math, etc always creates only a picture or model of reality. It never is real.
  • ErNaErNa Posts: 1,344
    edited 2010-11-29 - 00:54:15
    Now we find a solution for the equation 1 = 1

    Seems to be a silly doing, but isn't. It is pure science ;-)


    Let there be an interval on the x-axis, from start to end. And let us separate this interval into a number of chunks, lets say 1024. Or whatever.
    Now we create us 1024 delta distributions that way, that they cover the interval. The first is
    1, 0, 0, ... the second 0, 1, 0, ... , the last 0, ... , 0, 1

    Let there be an array of 1024 numbers, representing the graph of a function.

    If now we multiply the first delta distribution with the function the way, that we multiply chunk for chunk and add ( this is called a multiply-Accumulate or MAC-operation) we get as a result the first value of the function.
    If we multiply with the second delta distribution, the result is the second value of the function, and so on.

    In doing this we create 1 number from 2048 numbers!
    Is there any question why 2048 and not just 1024?
  • BeanBean Posts: 8,085
    edited 2010-11-29 - 06:02:17
    I have heard your cries...
    I am working on a Fourier for dummies tutorial.

    Give me a couple days and I'll post something to get us started.

    Bean
  • BeanBean Posts: 8,085
    edited 2010-11-29 - 08:37:30
    Take a look at this starting tutorial and let me know if it makes sense.

    Please comment, together we can make this a great tutorial.

    Bean
  • Beau SchwabeBeau Schwabe Posts: 6,420
    edited 2010-11-29 - 09:18:51
    Bean,

    This is nice. This is a very similar to the approach that I would take.

    It should probably pointed out that there are many distinct FFT algorithms involving a wide range of mathematics. The type that is used in the example here is DFT (discrete Fourier transform) which decomposes a sequence of values into components of different frequencies.

    The example quickly becomes more complex when there are several frequencies involved. The attached graph below represents : 2500kHz, 3250kHz, 3750kHz, and 4500kHz ... The 'Blue' represents the data you would be looking at which is the SUM of the frequencies mentioned above.
    1101 x 779 - 91K
  • ErNaErNa Posts: 1,344
    edited 2010-11-29 - 10:13:14
    It surely is different from the way, I try to go, but in the end it makes sense to come to a place from different directions.
    My experience is: the moment you understand the math, you are satisfied and later, when some border condition become relevant, the algorithm doesn't show the expected results and now it is difficult to find the reasons.

    There are a lot of tools in the net with allow to do the math, some for free, some expensive. I propose to download switcher Cad for LT, a spice version, free and easy to use, in my opinion. Allow schematic entry. This spice version can do and display FFT and so someone could create an example and share it.
  • Dave HeinDave Hein Posts: 6,006
    edited 2010-11-29 - 10:14:40
    It should probably pointed out that there are many distinct FFT algorithms involving a wide range of mathematics. The type that is used in the example here is DFT (discrete Fourier transform) which decomposes a sequence of values into components of different frequencies.

    The example quickly becomes more complex when there are several frequencies involved. The attached graph below represents : 2500kHz, 3250kHz, 3750kHz, and 4500kHz ... The 'Blue' represents the data you would be looking at which is the SUM of the frequencies mentioned above.
    Beau,

    All FFT algorithms are mathematically equivalent to the DFT -- They're just faster ways to implement the DFT. The basis vectors can be either viewed as a complex number pair or a 2-D quadrature pair, but in either case they are sines and cosines of different frequencies.

    Dave
  • ErNaErNa Posts: 1,344
    edited 2010-11-29 - 11:06:14
    There is a little difference, as a FFT runs only with powers of two and calculates the complete spectrum, a DFT sometimes is applied with some advantage, as this allows to search for a given frequency and the number of samples per period is free.
    There also is a way based on prime numbers, that algorithm I learned to know when using transputers, but do not remember what the reason was to use this method.

    But I want to make one additional remark:

    It is said, a fourier transform determines the frequency spectrum of a signal. This is not truth at all. OOOOO

    Imagine you have in interval in time or space and you have a defined signal, lets say: exactly one "oscillation" of a sinusoid. You determine the frequency spectrum of this signal to : amplitude 0 of all harmonics, and 1 for the fundamental.

    Now you change the interval a little bit without changing the signal and you determine the frequency again. Now the fundamental frequency of the spectrum is a little bit different from the original, so the original frequency doesn't exist any longer. But you didn't change the signal. oooooo
  • Dave HeinDave Hein Posts: 6,006
    edited 2010-11-29 - 12:46:32
    I think the prime number algortihm is considered to be an FFT also (Fast Fourier Transform).

    The DFT can be used to compute the power spectrum of a signal, but the signal must follow the assumptions of the DFT. The N samples of a data vector are assumed to repeat over and over to +/- infinity.

    A single oscillation of a sinusoid in N samples actually represents that sinusoid oscillating from -infinity to +infinity. If the interval is changed slightly it now represents a different signal with discontinuities at the block boundaries. This will have a different spectrum.
Sign In or Register to comment.