Discrete Fourier Transform (Forward) |
This page contains a utility that computes the Fourier coefficients of a real periodic sequence (Fourier analysis.).
References:
The utility posted on this page is a Javascript translation of the FORTRAN routine EZFFTF.FOR, by Paul N. Swarztrauber, National Center for Atmospheric Research, Boulder, CO, which is posted on the FFTPACK site as EZFFTF. Although all care has been taken to ensure that the sub-routines were translated accurately, some errors may have crept into the translation. These errors are mine; the original FORTRAN routines have been thoroughly tested and work properly. Please report any errors to the webmaster.
When data comes from an underlying phenomenon that is periodic, that data can have a Fourier Transform applied to it to determine if it can be represented by a combination of simpler cyclical functions (i.e. - sines and cosines.) If the data is generated from a function,
(i) a Fourier integral transform could be used to convert it into a pair of real functions, or
(ii) a Fourier transform could be used to convert it to a sequence of Fourier series coefficients.
If the data comes from discrete samples taken at specific time intervals, a Discrete Fourier Transform (DFT) may be used to convert the data sequence into another. That is what the program posted on this page does.
For example, say we have collected the following data points:
| t | g | |
| 0.0 | 0.0 | |
| 0.142857142857143 | 0.994136590118259 | |
| 0.285714285714286 | 0.709424724603715 | |
| 0.428571428571429 | 0.249769560964132 | |
| 0.571428571428571 | -0.249769560964131 | |
| 0.714285714285714 | -0.709424724603715 | |
| 0.857142857142857 | -0.994136590118259 | |
| 1.0 | 0.0 |
Note:
i) N = 8 (the number of data points).
ii) The data has been sampled at uniform time intervals (every 1/7 time unit). The program posted on this page assumes the data entered corresponds to a uniform sampling rate.
iii) The first point was sampled at t = 0. If the first point did not correspond to t = 0, the program still works, but the output would have to be adjusted appropriately.
If the user has control over the number of data points that are going to be analyzed via this DFT (perhaps data is generated by a user-written computer program), it is recommended--but not required--that N be a power of 2:
22 = 4
23 = 8
24 = 16
25 = 32
etc.
When N is a power of 2, certain processes in the program can run more quickly.
The program posted on this page accepts only the gi values as input:
| g0 | = | 0.0 |
| g1 | = | 0.994136590118259 |
| g2 | = | 0.709424724603715 |
| g3 | = | 0.249769560964132 |
| g4 | = | -0.249769560964131 |
| g5 | = | -0.709424724603715 |
| g6 | = | -0.994136590118259 |
| g7 | = | 0.0 |
The corresponding time values should not be entered.
The DFT program then computes Fourier coefficients such that the data can be expressed in the following form:
where the upper summation limit [N/2] refers to the largest integer in N. In other words,
if N is even, [N/2] refers to N/2,
if N is odd, [N/2] refers to (N - 1)/2.
The ak and bk values are computed as follows.
If N is odd, the next two equations apply over the range 1 ≤ k ≤ [N/2].
If N is even, these two equations apply over the range 1 ≤ k < [N/2] (does not include k = N/2).
and
If N is even, the values for k = N/2 are found as follows:
bN/2 = 0
HOW TO USE THIS UTILITY
In the "Discrete Data Sequence" box below, enter the data sequence (real numbers.) Enter the ordinate values one per line--nothing else. No commas, periods, brackets, etc. (Also note that numbers in scientific notation are NOT recognized).
Continuing with the sample data above, the following numbers would be entered:
0.0
0.994136590118259
0.709424724603715
0.249769560964132
-0.249769560964131
-0.709424724603715
-0.994136590118259
0.0
Once you click the "Perform DFT" button, this utility will compute and output the Fourier coefficients (the ak and bk values.) If the data just above is entered, the following results should be output:
The ak values follow:
azero = 0
0.319438892119846
0.00873557613760324
-0.194554111637781
-0.133620356619669
The bk values follow:
0.771193705705169
0.00873557613760299
-0.0805869516558179
0.0
For more information about this program, please see the associated blog post: Discrete Fourier Transform Blog Post