We have donut eating contests to see who has the best legs. We paint our pigs. We argue about which time zone we are in. About 400,000 of us gather together to watch cars go around in a circle. We also build robots.Yep, our cultural norm is a bit different. - Andy Baker [more]
 Chief Delphi Fourier Transforms
 User Name Remember Me? Password
 CD-Media CD-Spy
 portal register members calendar search Today's Posts Mark Forums Read FAQ rules

#1
11-24-2004, 02:38 PM
 phrontist Proto-Engineer AKA: Bjorn Westergard FRC #1418 (Vae Victus) Team Role: College Student Join Date: Feb 2004 Rookie Year: 2004 Location: Falls Church, VA Posts: 828
Fourier Transforms

I'm really intrigued with Fourier Transforms, and was wondering if someone could clarify a few points for me:

1) Is there only one possible decomposition of any given transform into sine waves?
2) Knowing what a Fourier Transform does, I've concocted the following algorithm (which I'm aware would be useless in real life) and I'm curious if it would work:
• Input Data Points
• Execute sinusoidal regression
• calculate output of resultant sinusoidal function for the x values of given data points
• Subtract, yeilding new data points
• Jump back to step 2 using new data points unless data points are more or less linear at this point

(If question number two didn't make any sense to you, the basic idea is to do sinusoidal regression on the data points, "subtract" the resultant function, and repeat, yeilding a bunch of sinusoidal functions comprising the output of the Fourier transform)

3) Can you explain to someone (whose highest level of math education is roughly Calculus AB) how a FFT or DFT works?
__________________

University of Kentucky - Radio Free Lexington

"I would rather have a really big success or a really spectacular crash and failure then live out the warm eventual death of mediocrity" - Dean Kamen
#2
11-24-2004, 05:05 PM
 Mike Betts Electrical Engineer no team Team Role: Engineer Join Date: Dec 2001 Rookie Year: 1995 Location: Homosassa, FL Posts: 1,442
Re: Fourier Transforms

I'm not at home right now, so I'll defer answering until I get back to my "library" (in about a week).

From my increasingly faulty memory, the FT and IFT (Inverse FT) are unique whereas the FFT (Fast FT) and IFFT (inverse FFT) may not be.

The algorithm you have outlined will probably not work. Nice try though...

The FFT uses a "butterfly" algorithm which lends itself well to computers.

I'm not sure how to attack the DFT (discrete FT) without talking about continuous and discrete domains... This gets messy fast...

Like I said, I'll get back to you next week. I have a lot of references at home and don't want to say the wrong thing here...
__________________
Mike Betts

Alumnus, Team 3518, Panthrobots, 2011
Alumnus, Team 177, Bobcat Robotics, 1995 - 2010
LRI, Connecticut Regional, 2007-2010
LRI, WPI Regional, 2009 - 2010
RI, South Florida Regional, 2012 - 2013

As easy as 355/113...
#3
11-24-2004, 07:57 PM
 Kevin Sevcik (Insert witty comment here) FRC #0057 (The Leopards) Team Role: Mentor Join Date: Jun 2001 Rookie Year: 1998 Location: Houston, Texas Posts: 3,559
Re: Fourier Transforms

So it's probably not at all helpful, but I'm preparing to stuff myself with turkey tomorrow and it's been long enough that I don't remember FTs and FFTs in detail, but yeah. A FT is unique for a particular function. A FFT is unique for a given function and frequency division thing. I don't remember about DFTs either and yeah, there's allsorts of discretization issues there. Now, to melt your brain, here's a site that can eventually answer all sort questions:

Mathworld: Fourier Transform
__________________
The difficult we do today; the impossible we do tomorrow. Miracles by appointment only.

Lone Star Regional Troubleshooter
#4
11-25-2004, 10:08 AM
 Rickertsen2 Umm Errr... None #1139 (Chamblee Gear Grinders) Team Role: Alumni Join Date: Dec 2002 Rookie Year: 2002 Location: ATL Posts: 1,421
Re: Fourier Transforms

I have been Puzzled by FTs and FFTs etc for a while too. I don't have much of a math background. I am currently taking precal. I have learned a bit on my own. I am reasonably comfortable with integrals, derivitaves, limits etc. Is there any hope in me trying to understand this stuff with my level of education? I am looking to understand HOW/WHY they work. There is plenty of information on how to implement them, but but not how they work.
__________________
1139 Alumni

Last edited by Rickertsen2 : 11-25-2004 at 10:13 AM.
#5
11-25-2004, 11:16 AM
 phrontist Proto-Engineer AKA: Bjorn Westergard FRC #1418 (Vae Victus) Team Role: College Student Join Date: Feb 2004 Rookie Year: 2004 Location: Falls Church, VA Posts: 828
Re: Fourier Transforms

Quote:
 Originally Posted by Rickertsen2 I have been Puzzled by FTs and FFTs etc for a while too. I don't have much of a math background. I am currently taking precal. I have learned a bit on my own. I am reasonably comfortable with integrals, derivitaves, limits etc. Is there any hope in me trying to understand this stuff with my level of education? I am looking to understand HOW/WHY they work. There is plenty of information on how to implement them, but but not how they work.
Same here, math education wise. I know exactly how you feel, having spent a lot of time googling to similar results.

*bites lower lip* <Clinton>I feel your pain</Clinton>
__________________

University of Kentucky - Radio Free Lexington

"I would rather have a really big success or a really spectacular crash and failure then live out the warm eventual death of mediocrity" - Dean Kamen
#6
11-25-2004, 01:55 PM
 Venkatesh Registered User FRC #0030 Join Date: Jan 2003 Rookie Year: 2002 Location: USA Posts: 260
Re: Fourier Transforms

There is an excellent book, "Music, Physics, and Engineering", in which fourier analysis and basic transforms are explored. You don't need much beyond Precalc to understand their explanations.

However the book only has Fourier analysis as a tiny element (roughly 15-20 pages in the whole thing) and does not talk about Fast fourier transforms or the like, so its not worth buying if you are only interested in Fourier. Its an old book, and should be in many libraries.
__________________
-- vs, me@acm.jhu.edu
Mentor, Team 1719, 2007
Team 30, 2002-2005
#7
11-25-2004, 02:03 PM
 eugenebrooks Team Role: Engineer AKA: Dr. Brooks no team (WRRF) Join Date: Jan 2004 Rookie Year: 2001 Location: Livermore, CA Posts: 601
Re: Fourier Transforms

Quote:
 Originally Posted by phrontist I'm really intrigued with Fourier Transforms, and was wondering if someone could clarify a few points for me: 1) Is there only one possible decomposition of any given transform into sine waves? 2) Knowing what a Fourier Transform does, I've concocted the following algorithm (which I'm aware would be useless in real life) and I'm curious if it would work: Input Data PointsExecute sinusoidal regressioncalculate output of resultant sinusoidal function for the x values of given data pointsSubtract, yeilding new data pointsJump back to step 2 using new data points unless data points are more or less linear at this point (If question number two didn't make any sense to you, the basic idea is to do sinusoidal regression on the data points, "subtract" the resultant function, and repeat, yeilding a bunch of sinusoidal functions comprising the output of the Fourier transform) 3) Can you explain to someone (whose highest level of math education is roughly Calculus AB) how a FFT or DFT works?
If you define a function on the interval [0,2PI] (you can scale and offset to take care of any other interval) and the function is periodic outside of it, you can represent the function as:
A0 + S1 sin(x) + C1 cos(x) + S2 sin(2x) + C2 cos(2x) + ...

A0 is just the average of the function in the interval, evaluated by integrating it. If your "regression" fit delivers the same answer,
you are in.

The other coefficients are obtained by integrating against the appropriate function, sin(x) in order to get S1, for instance, normalizing by dividing by the integral of sin^2(x). This works because the functions are orthogonal on the interval, that is the integral of sin(x) cos(x) is zero, for instance.

The discrete DFT is just a discrete version of all of the integration that is required, and the FFT is a factored form of the DFT matrix that is much more efficient to compute.

Now, back to your idea. If your "regression" fit of a flat line would deliver the same result as the average, A0, subtracting it would not disturb the coefficients of C# and S#. The question, then, is whether the presense of higher order terms in the data would distrub your "regression" fits of cos(x) and sin(x), and so forth. If the regression fit of a lower order term is not disturbed by the presense of a higher order term, your idea would work, but you would not want to do it that way, at least due to the build up of errors due to the subractions.

Your basic subtraction scheme, however, is used in order to produce a set of orthogonal functions from a set that is not orthogonal, and is therefore valid and quite useful in other circumstances.

Last edited by eugenebrooks : 11-25-2004 at 05:27 PM.
#8
11-25-2004, 03:50 PM
 Kevin Watson La Cañada High School FRC #2429 Team Role: Mentor Join Date: Jan 2002 Rookie Year: 2001 Location: La Cañada, California Posts: 1,334
Re: Fourier Transforms

Quote:
 Originally Posted by Venkatesh There is an excellent book, "Music, Physics, and Engineering", in which fourier analysis and basic transforms are explored. You don't need much beyond Precalc to understand their explanations.
I too had a great interest in the magical Fourier transform when I was young(er). If you have an interest in pursuing the more hard-engineering fields, like EE & ME, I cannot stress enough how important it is to master the ideas behind the FT. As an EE myself, I can use these ideas to solve some really tough problems just by thinking about what's happening in "Fourier space". As an example, I'm working on a new class of spacecraft avionics that use distributed computational nodes that are interconnected via a gigabit-class network. Trying to figure out why I'm getting transmission errors between those nodes by examining the network signals in the time domain is next to impossible. But, if you can imagine what's happening in Fourier or frequency space, the problem just might become easier to solve. There are also instruments that will do this for you as well, like a spectrum analyzer (like the one that comes with winamp). More sophisticated instruments, like a network analyzer, can also show you what's happening in other cool spaces like modulation and phase space.

You don't need sophisticated instruments to investigate the magic that is the Fourier transform, you can do it with a copy of Matlab, Mathematica, Igor Pro or even Excel (yes, Excel!). Start by creating a table that represents a series of samples of your waveform. Using a discrete time version of the Fourier transform, known as the Fast Fourier Transform (FFT), you can convert this waveform into a table of its frequency components. Start with something simple like a pure sine wave and work yourself up to more complex waveforms like a triangle wave. A really cool waveform to use is a square wave. By modifying the resulting frequency components of the square wave and then converting back to time space, you can see how the square wave can be distorted by attenuating the higher frequency components. Square wave fidelity is important in high speed digital signals, like the network I mentioned above. For the more adventurous, you can also write the c code that does the above. Try googling on something like "FFT example source code" for some examples.

-Kevin
__________________
Kevin Watson
Engineer at Velodyne LiDAR
http://kevin.org

Last edited by Kevin Watson : 11-25-2004 at 04:43 PM. Reason: Added Google link.
#9
11-26-2004, 10:21 AM
 phrontist Proto-Engineer AKA: Bjorn Westergard FRC #1418 (Vae Victus) Team Role: College Student Join Date: Feb 2004 Rookie Year: 2004 Location: Falls Church, VA Posts: 828
Re: Fourier Transforms

Quote:
 Originally Posted by Venkatesh There is an excellent book, "Music, Physics, and Engineering", in which fourier analysis and basic transforms are explored. You don't need much beyond Precalc to understand their explanations. However the book only has Fourier analysis as a tiny element (roughly 15-20 pages in the whole thing) and does not talk about Fast fourier transforms or the like, so its not worth buying if you are only interested in Fourier. Its an old book, and should be in many libraries.
Actually, that sounds bloody fantastic! Thanks!
__________________

University of Kentucky - Radio Free Lexington

"I would rather have a really big success or a really spectacular crash and failure then live out the warm eventual death of mediocrity" - Dean Kamen
#10
11-26-2004, 07:22 PM
 Rich Wong NYC FIRST Planning Committee Member no team (NYC FIRST) Team Role: Mentor Join Date: Jan 2002 Rookie Year: 1999 Location: Brooklyn, NY Posts: 1,674
Re: Fourier Transforms

Quote:
 Originally Posted by Mike Betts From my increasingly faulty memory, the FT and IFT (Inverse FT) are unique whereas the FFT (Fast FT) and IFFT (inverse FFT) may not be. The algorithm you have outlined will probably not work. Nice try though... The FFT uses a "butterfly" algorithm which lends itself well to computers. I'm not sure how to attack the DFT (discrete FT) without talking about continuous and discrete domains... This gets messy fast...
FFT are easy to implement with DSP ICs or programming. One of my pass engineering job was to used the these ICs to execute 10x10 FFT for a spread spectrum project. We choose hardware because of the "Need for Speed!"
It was the most fun I ever had with engineering, programming and math.
__________________
popularis de ob instinctus agnitionis scientia technologia
Home website: www.nycnjfirst.org
Member of NEMO & e^(i*pi)+1 Fraternity.
Member of Friends of Robots
Member of NYCFIRST Planning Committee

Last edited by Rich Wong : 11-26-2004 at 08:36 PM.
#11
11-28-2004, 05:11 PM
 Chris Hibner Eschewing Obfuscation Since 1990 AKA: Lars Kamen's Roadie FRC #0051 (Wings of Fire) Team Role: Engineer Join Date: May 2001 Rookie Year: 1997 Location: Canton, MI Posts: 1,483
Re: Fourier Transforms

Quote:
 Originally Posted by Rickertsen2 I have been Puzzled by FTs and FFTs etc for a while too. I don't have much of a math background. I am currently taking precal. I have learned a bit on my own. I am reasonably comfortable with integrals, derivitaves, limits etc. Is there any hope in me trying to understand this stuff with my level of education? I am looking to understand HOW/WHY they work. There is plenty of information on how to implement them, but but not how they work.
Fourier Transforms are very interesting, and they seem almost magical to most people that don't fully understand the math behind them. Once you realize what mathematical concept is behind them, they are actually quite easy to understand.

The basis of the Fourier Transform is simple Linear Algebra. If you don't know anything about linear algebra, I apologize, but I'll try to make this as simple to understand as possible.

There are two simple principles of Linear Algebra that the Fourier Transform uses:

1) Any vector in n-dimensional space can be written as a linear combination of n linearly independent vectors. For example, in 3-dimensional space, let vector X = 1i + 0j + 0k; let Y = 0i + 1j + 0k; let Z = 0i + 0j + 1k. Then, the vector W = 3i + 4j + 5k can be written as: W = 3*X + 4*Y + 5*Z (i.e., W can be written as a linear combination of the 3 linearly independent vectors X,Y, and Z).

2) Any vector can be projected onto another vector that is not orthogonal (perpendicular) to that vector. This is like saying that any vector will cast a shadow on another vector. For example, assume that there is a vector along the ground pointing due north. Then assume you have another vector that is also pointing due north, but also a little bit up in the air (in other words, the vector is pointing diagonally north and up). Now assume you have a light bulb directly above where the two vectors intersect. The diagonal vector would cast a shadow onto the vector on the ground. This shadow is called the "vector projection onto" the vector on the ground. In the example in part 1) above, If we projected vector W onto vector X, the projection would be 3i+0j+0k (or 3X). You can also say that "the X component of W is 3".

Okay, now you ask, "what on earth does this have to do with Fourier Transforms". I guess I forgot to mention one other principle of linear algebra: a function can act exactly like a vector, and a set of functions can act exactly like a set of vectors.

What does this mean? It means that any function can be written as a linear combination of other linearly independent functions (i.e., principle (1) above).

Okay, so now we know that we can write any function using a bunch of sine waves. How do we know what you multiply each of the waves by? That is simple: use principle (2). You simply project your desired function onto each of the sine waves to get the component of each sine wave for your desired function.

Of course, this sounds fairly simple and the details are a little more difficult, but not much, really. Once you have a little linear algebra under your belt, making projections of vectors onto other vectors is fairly easy. Making projections of functions onto other functions is just a simple extension. Once you understand these principles, Fourier Transforms are not that magical or mysterious, but just make a lot of sense. Also, one you understand these principles, there isn't much need to memorize the Fourier Transform formulas.
__________________
-
An ounce of perception is worth a pound of obscure.

Last edited by Chris Hibner : 11-29-2004 at 12:37 PM.
#12
11-29-2004, 04:49 PM
 Manoel Registered User FRC #0383 (Brazilian Machine) Team Role: Mentor Join Date: Jun 2001 Rookie Year: 2000 Location: Porto Alegre, RS, Brazil Posts: 608
Re: Fourier Transforms

Quite a coincidence this thread came up; I'm currently studying Fourier Transforms in my Applied Math course, and I have to hand in a paper detailing one of its uses in my future field (Electrical Engineering).
So, I'd like to ask some suggestions to the engineers who use them in their day job - I'm particular interested in Controls applications (I think Chris Hibner can help me on this one, right? )
__________________
Manoel Flores da Cunha
Mentor
Brazilian Machine
Team # 383
#13
11-30-2004, 08:11 AM
 Chris Hibner Eschewing Obfuscation Since 1990 AKA: Lars Kamen's Roadie FRC #0051 (Wings of Fire) Team Role: Engineer Join Date: May 2001 Rookie Year: 1997 Location: Canton, MI Posts: 1,483
Re: Fourier Transforms

Quote:
 Originally Posted by Manoel Quite a coincidence this thread came up; I'm currently studying Fourier Transforms in my Applied Math course, and I have to hand in a paper detailing one of its uses in my future field (Electrical Engineering). So, I'd like to ask some suggestions to the engineers who use them in their day job - I'm particular interested in Controls applications (I think Chris Hibner can help me on this one, right? )
Here is how I've used Fourier Transforms at my job:

1) To determine frequency content of a set of data that we collected. This helps us to understand how we might want to filter the data. It also helps us to see if there are any unusual characteristics of the data in the frequency domain.

2) To remove unwanted frequency content. We were looking at some data we collected and noticed something strange. In the frequency domain we noticed a huge spike at a certain frequency. We went back to the test setup and noticed that one piece of data acquisition equipment radiated a lot of energy at that frequency and that created the large spike at that frequency. In order to remove the frequency, we took the FFT of the data, removed the spike by setting the frequency domain data to that of the average value of the data surrounding the spike, then took the inverse FFT.

3) Creating complex transfer function models. If we can identify the frequency response of a system emperically (like by using a sine sweep), we can use Fourier convolution to model the behavior of a signal through that system. This can get tricky, though.

One thing to keep in mind when using FFTs: The process of taking a Fourier Transform of a finite-time set of data will introduce false content into the frequency domain (and vice versa when you take the inverse). If you take a straight-up FFT of a time history of data, you are actually superimposing a square wave on top of the data, which becomes a sinc function in the frequency domain. If you understand the effect you can take some care to minimize how it affects your data. Just be sure you don't blindly use Fourier methods without doing a few experiments and looking at the results closely. Once you take the inverse FFT, be sure to look at the beginning of the time-domain data for windowing effects.
__________________
-
An ounce of perception is worth a pound of obscure.
#14
11-30-2004, 08:22 AM
 Chris Hibner Eschewing Obfuscation Since 1990 AKA: Lars Kamen's Roadie FRC #0051 (Wings of Fire) Team Role: Engineer Join Date: May 2001 Rookie Year: 1997 Location: Canton, MI Posts: 1,483
Re: Fourier Transforms

I wanted to make this a separate post, just so it doesn't get lost in the above post.

The concept that I pointed out in my first post (about writing a function as a linear combination of other functions) is a very powerful concept. In fact, it is the basis of virtually all approximation methods.

If you've ever heard of Wavelet Transforms, Spline Functions, Finite Element Methods, Element-Free Methods, etc.; these are all applications of using a set of functions like vectors. All of these methods try to approximate complex functions as linear combinations of simpler functions. And they also all use the concept of projecting a function onto these simpler basis functions.

If you're going into a masters program involving control or computational engineering of any sort (i.e. any sort of computer simulation), you should take a good theoretical linear algebra class and a linear systems class. After this, your other classes will make a lot more sense and will be much easier to understand. My Finite Elelment Methods course (the course in which we had to write our own finite element solvers in Matlab and compare the results to commercially available solvers like Nastran and Abaqus), the drop-out rate was over 50%. Since I had a good understanding of the math, I thought the class wasn't too bad. I have my boss at work (a PhD) for giving me the advice to take the other classes first - it helped a lot.
__________________
-
An ounce of perception is worth a pound of obscure.
#15
11-30-2004, 09:24 AM
 Al Skierkiewicz Broadcast Eng/Chief Robot Inspector AKA: Big Al WFFA 2005 FRC #0111 (WildStang) Team Role: Engineer Join Date: Jun 2001 Rookie Year: 1996 Location: Wheeling, IL Posts: 10,745
Re: Fourier Transforms

Manoel,
I use two pieces of equipment that actually are using FFT to make acoustic measurements in situ, i.e. in the room of interest. By using FFT and sweeping the room you can easily see the effects on frequency response as a function of reflections or by adjusting the parameters you can close down the sample cycle so that you can actually sweep the room while you are talking without affecting the measurement. The instrument also allows a manipulation to take a look at phase vs. frequency. The instrument I use most is called TEF (Time Energy Frequency) and it was originally designed and built by Crown International. You can now see the product line at http://www.gold-line.com/tef/tef.htm. This instrument allows us to quantify anomalies that we hear but could not measure. It has made great advances in acoustic design and treatment. We now know for instance that your ear shape has significant effect on how you hear. We also know that there is a delay after you hear a sound while you ear processes the data called the Hass Effect. By far the biggest effect in an acoustic environment revolves around reflections and the time it takes to arrive at your ears. In mixing rooms, for instance, reflections from the audio console face can cause severe notches in the frequency response. In electrical terms, two signals, in phase and equal in level, will only add to +6dB. The same two signals, 180 degrees out of phase, will produce a notch of infinite depth. What is more surprising is that there are rapid phase changes when sweeping across the notch. Rapidly changing phase plays havoc with human hearing as phase (one ear compared with the other ear) is what helps give us directional clues as to the source of the sound. Additionally, significant reflections will be in phase at some frequencies and out of phase at others, causing what is known as a comb filter. This type of filter will have frequency related notches in response throughout the audible spectrum.
In typical Catholic churches, particularly in the US, sound system designers have installed two speakers, one on each side of the altar. In this design, the only people who will hear without interference are those who are walking down the center of the center aisle. All others will experience some form of notched response due to the time misalignment of sound arriving at their ears at two different times.
__________________
Good Luck All. Learn something new, everyday!
Al
WB9UVJ
www.wildstang.org
________________________
Storming the Tower since 1996.

Last edited by Al Skierkiewicz : 11-30-2004 at 09:27 AM.

 Thread Tools Display Modes Rate This Thread Linear Mode Rate This Thread: 5 : Excellent 4 : Good 3 : Average 2 : Bad 1 : Terrible

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts vB code is On Smilies are On [IMG] code is On HTML code is Off
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Announcements     User Announcements FIRST     General Forum         FIRST E-Mail Blast Archive     Rumor Mill     Career     Robot Showcase Technical     Technical Discussion     Robotics Education and Curriculum     Motors     Electrical         CAN     Programming         NI LabVIEW         C/C++         Java         Python     Control System         FRC Control System         Sensors     Pneumatics     Kit & Additional Hardware     CAD         Inventor         SolidWorks         Pro ENGINEER / Creo     IT / Communications         3D Animation and Competition         Website Design/Showcase         Videography and Photography         Computer Graphics     National Instruments LabVIEW and Data Acquisition         LabView and Data Acquisition Competition     Awards         Chairman's Award     Rules/Strategy         Scouting         You Make The Call     Team Organization         Fundraising         Starting New Teams         Finding A Team         College Teams     Championship Event     Regional Competitions     District Events     Off-Season Events     Thanks and/or Congrats     FRC Game Design     OCCRA         OCCRA Q&A         OCCRA Programming Other     Unsung FIRST Heroes     Chit-Chat         Games/Trivia             Fantasy FIRST     Car Nack's Corner     College & University Education     Dean Kamen's Inventions     FIRST-related Organizations         Western Region Robotics Forum         Robot Chicks Union (RCU)         Southern California Regional Robotics Forum         FIRST Interactive Rural SupporT         FIRST Scouting Network         FloridaFIRST         FIRSTwiki         The Blue Alliance             Video Archives     FIRST Historians     FIRST In the News...     FIRST Lego League         Lego Mindstorm Discussion     FIRST Tech Challenge     VEX         VEX Robotics Competition         VEX IQ     Televised Robotics     Math and Science         NASA Discussion ChiefDelphi.com Website     CD Forum Support     Extra Discussion Old Forum Archives     1999     2000     2001

All times are GMT -5. The time now is 08:19 AM.

The Chief Delphi Forums are sponsored by Innovation First International, Inc.

 -- English (12 hour) -- English (24 hour) Contact Us - Chief Delphi - Rules - Archive - Top