DFT - Discrete (Fast) Fourier Transform

Calculates the discrete fast Fourier transformation for amplitude and phase.

Syntax

X

is the univariate time series data (one-dimensional array of cells (e.g., rows or columns)).

Order

is the time order in the data series (i.e., the first data point's corresponding date (earliest date=1 (default), latest date=0)).

Order	Description
1	ascending (the first data point corresponds to the earliest date) (default)
0	descending (the first data point corresponds to the latest date)

Component

is the input frequency component order. If missing, component 0 is assumed. If negative, an array of all components is assumed.

Return_type

is a number that determines the return value type: 1 (or missing) = Amplitude, 2 = Phase.

RETURN_TYPE	NUMBER RETURNED
1 or omitted	Amplitude
2	Phase

Remarks

1. The input time series may include missing values (e.g., #N/A, #VALUE!, #NUM!, empty cell) at either end, but they will not be included in the calculations.
2. The input time series must be homogeneous or equally spaced.
3. If the component value is negative, the DFT function returns an array of amplitude (or phase) values for all components in the sample data.
4. The first value in the input time series must correspond to the earliest observation.
5. The frequency component order, $k$, must be a positive number less than $N$, or the error (#VALUE!) is returned.
6. The DFT returns the phase angle in radians, i.e., $0 \lt \phi \lt 2 \times \pi$.
7. The discrete Fourier transformation (DFT) is defined as follows:
   
   $$ X_k = \sum_{j=0}^{N-1} x_j e^{-\frac{2\pi i}{N} j k} $$
   
   Where:
   
   • $k$ is the frequency component
   • $x_0,...,x_{N-1}$ are the values of the input time series
   • $N$ is the number of non-missing values in the input time series
8. A fast Fourier transform (FFT) is a highly optimized implementation of the discrete Fourier transform (DFT), which converts discrete signals from the time domain to the frequency domain.
9. The most commonly used FFT algorithm is the Cooley-Tukey algorithm, which reduces a large DFT into smaller DFTs to increase computation speed and reduce complexity.
10. A radix-2 decimation-in-time (DIT) FFT is the simplest and most common form of the Cooley–Tukey algorithm that divides a DFT of size N into two overlapping DFTs of size $\frac{N}{2}$ at each of its stages using the following formula:
    
    $$ X_{k} = \begin{cases} E_k + \alpha \cdot O_k & \text{ if } k \lt \dfrac{N}{2} \\ E_{\left (k-\frac{N}{2} \right )} - \ \alpha \cdot O_{\left (k-\frac{N}{2} \right )} & \text{ if } k \geq \dfrac{N}{2} \end{cases} $$
    Where:
    
    • $E_k$ is the DFT of the even-indices values of the input time series, $x_{2m} \left(x_0, x_2, \ldots, x_{N-2}\right)$
    • $O_k$ is the DFT of the odd-indices values of the input time series, $x_{2m+1} \left(x_1, x_3, \ldots, x_{N-2}\right)$
    • $\alpha = e^{ \left (-2 \pi i k /N \right )}$,
    • $N$ is the number of non-missing values in the time series data.
11. The unit frequency of the DFT is $\frac{2\pi}{N}$, where $N$ is the number of non-missing observations.

Files Examples

Related Links

• Wikipedia - Fast Fourier Transform
• Wikipedia - Cooley-Tukey FFT algorithm

References

• Hamilton, J .D.. Time Series Analysis. Princeton University Press. (1994). ISBN 0-691-04289-6
• Tsay, Ruey S.. Analysis of Financial Time Series . John Wiley & SONS. (2005). ISBN 0-471-690740