List Archives >  Maple User Group List Archive >  Archive by date >  This Month By Date >  This Month By Topic

[MUG] FFT

Search email archive for  

[MUG] FFT
Author: Bastero De Eleizalde, Carlos    Posted: 12/10/2000 11:14:13 GDT
>> From: "Bastero de Eleizalde, Carlos" "cbastero" Hi, I would like to compute FFT of an array of 27 entries. Maple allows it only if you have a complex sequence of length 2^m. Thanking in advance your help Carlos Bastero Universidad de Navarra (Spain) www.esi.unav.es

[MUG] Re: FFT
Author: Maple Group    Posted: 18/10/2000 22:59:09 GDT
>> From: Maple Group "maple_gr" | >> From: "Bastero de Eleizalde, Carlos" "cbastero" | | Hi, | I would like to compute FFT of an array of 27 entries. Maple allows it only | if you have a complex sequence of length 2^m. -=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=- Date: Fri, 13 Oct 2000 15:41:05 -0400 (EDT) From: Denis Sevee "dsevee" To: "''" "maple-list" Subject: FFT Here are 2 possible solutions: 1) zero pad your data. i.e. add 5 zeros to bring it up to 32 entries. This is a standard procedure although it does have an effect on the results of the FFT. 2) Enter > w=evalf(exp(I*2*Pi/27)); > F:=matrix(27,27,(i,j)->w^-((i-1)*(j-1))): Then multiplying by F converts your data to the Fourier basis, and multiplying by inverse(F) has the effect of the inverse DFT. Denis Sevee -=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=- From: "Willard, Daniel Dr DUSA-OR" "Daniel.Willard" To: "''" "maple-list" Subject: FFT Date: Fri, 13 Oct 2000 15:57:54 -0400 One possible method is to add zeros to the list of entries until the 2^m critrion is met. There are others that do not take advantage of the 2^m logic and so are longer and more complicated but probably more accurate. -=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=- Date: Sat, 14 Oct 2000 12:21:20 -0700 Subject: FFT From: "William Kirkham" "wkirkha" To: "maple-list" A mathematical requirement of any Fast Fourier Transform (FFT) algorithm is that the sequence is a multiple of two. This is not a limit set by Maple. You can add entries to get a multiple of two, or use the standard Fourier transform. --Bill ----- William J. Kirkham, P.E. "wkirkha" -=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=- Date: Mon, 16 Oct 2000 08:29:13 -0500 From: Herman Jaramillo "herman.jaramillo" To: "maple-list" Subject: FFT You should pad with zeros at the end of your array (5 zeros). -- Herman Jaramillo phone: 713-689-6503 Research Geophysicist fax : 713-689-6100 Baker Hughes (Western Geophysical) email: "herman.jaramillo" 3600 Briarpark Drive (77042-5275) P.O. Box 2469 Houston, Texas 77252-2469 -=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=- From: "HOLMGREN" Date: Mon, 16 Oct 2000 12:13:33 -0500 (CDT) Subject: FFT To: "maple-list" Dr. Bastero, You can always "pad out" your array(s) with zeros to conform with the 2^m requirement. However, you have to be aware that this changes the sampling of the original signal, and hence changes the frequency sampling as well. Sincerely, David Holmgren Brandon University -=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=- From: "Wampfler, Hans" "uzwamp" To: "''" "maple-list" Subject: AW: FFT Date: Tue, 17 Oct 2000 10:59:26 +0200 Dear Carlos, you should use an array of 32 entries, center your data and simply fill the rest of the array at the beginning and at the end with zeros. Hans Wampfler "uzwamp"

[MUG] Re: FFT
Author: Maple Group    Posted: 23/10/2000 13:55:37 GDT
>> From: Maple Group "maple_gr" -=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=- Date: Thu, 19 Oct 2000 11:46:48 +0100 (GMT Daylight Time) From: John S Robinson "jsr1" To: "maple-list" Subject: FFT On Wed, 18 Oct 2000, Maple Group wrote: | A mathematical requirement of any Fast Fourier Transform (FFT) algorithm is | that the sequence is a multiple of two. This is not a limit set by Maple. | You can add entries to get a multiple of two, or use the standard Fourier | transform. Not really. The 'Fast'ness of the FFT depends on the factorization of N, the number of elements in the sequence. The NAG routine C06EAF will handle an arbitrary N, but is most efficient when N has many small factors - the limiting case is N = 2 ^n. I don't think the incorporation of NAG routines into Maple has got as far as this section. When N is prime the FFT is the same as a simple minded application of the sum, order N^2. -- John S Robinson Tel: +44-1904-433833 University of York Computing Service Fax: +44-1904-433740 Heslington, YORK. YO10 5DD email: "jsr1" www-users.york.ac.uk/~jsr1 - but I wouldn't bother if I were you -=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=- Date: Thu, 19 Oct 2000 04:10:10 -0400 From: Normand Beaudoin "normand-beaudoin" To: "maple-list" Subject: FFT Maple Group wrote: | >> From: "Bastero de Eleizalde, Carlos" "cbastero" | | Hi, | I would like to compute FFT of an array of 27 entries. Maple allows it only | if you have a complex sequence of length 2^m. Adding 5 zeroes after your 27 initial data points before applying the DFT (Discrete Fourier Transform) using a Fast Fourier Transform (FFT) algorithm on these 32 points is the so-called zero-padding technique. Adding these zeroes (in the "time" side) means that you increase the total length (time duration) of the initial signal, hence it will increase the density of the sampling on the transformed side (the DFT side, the frequency side). The result is correct in the sense that the obtained values are good but they will be at slightly different position on the frequency axis. (When I say that the result is correct I suppose that what you want is the DFT, but you must be aware of the fact that the DFT **is not** exactly the same thing as the Fourier Transform.) Note that for as few as 27 data points you even don't have to worry about using the FFT, just use "for... do" loops in Maple to compute the following which ist the DFT of h(j); H(k) = Sum on j (j=0..N-1) { h(j)*exp(-i*2*Pi*k*j / N) } In your case, N=27, the sequence h(j) (j=0..N-1) is your initial data and the sequence H(k) is the DFT of it. The FFT is "only" an efficient algorithm to compute the DFT. When N is a power of 2 the FFT is very efficient: O(NlnN). But you probably already know a lot about that so I stop here... Normand Beaudoin

Previous by date: [MUG] Re: nonlinear systems help,  William Kirkham
Next by date: [MUG] X-Error when starting xmaple 6.01 on AIX 4.3, Peter-Klaus Schilling
Previous thread: [MUG] Problem with LIBNAME,  Willard, Daniel Dr DUSA-OR
Next thread: [MUG] X-Error when starting xmaple 6.01 on AIX 4.3, Peter-Klaus Schilling