Discrete Fourier Transform (DFT) Let {x(t)} = {x(0), x(1), ..., x(N-1)} = {x(t),0<=t<=N-1}} be a finite complex or real series, that is, a series of N complex or real numbers. Then the DFT (discrete Fourier transform) of {x(t)} is the finite complex series of length N {X<N>(k),0<=k<=N-1}, where X<N>(k) = sum(x(t)*exp(-i*2*PI*t*k/N),0<=t<=N-1), k = 0,1,...,N-1 In the argument to exp(), i = sqrt(-1) is a pure imaginary number. For any integer M > 0 we define X<M>(k) = sum(x(t)*exp(-i*2*PI*t*k/M),0<=t<=N-1), k = 0,1,...,M-1 When M > N, this can be viewed as the DFT of the series of length M obtained by "padding" {x(t),0<=t<=N-1} with M - N 0's. There are two aspects of this notation: The use of an upper case X for the Fourier transform of lower case x. The use of suffix <M> to specify that f = k/M is used in the complex exponential exp(-i*2*PI*t*f). The alternative notation DFT<M>{x}(k) = X<M>(k) is sometimes useful. The definition of x<M>(k) works for any integer k < 0 and k >= M. With this extension, x<M>(k) is periodic with period M, that is for any k x<M>(k+M) = x<M>(k-M) = x<M>(k). Note that in the definition of the DFT, indices start with 0 rather than 1 as is assumed in MacAnova. In working with Fourier transforms in MacAnova, this correspondence must be kept in mind. The first element in a series is always considered to be x(0) or X(0), but to access it you will need to use x[1]. Inversion formula If {X<N>(k)},k = 0, 1, ..., N-1 is the DFT of {x(t)},t = 0, 1, ..., N-1, then the following inversion formula holds: x(t) = (1/N)*sum(X<N>(t)*exp(+i*2*PI*t*k/N),0<=k<=N-1) = (1/N)*conj(DFT<N>{conj(DFT<N>{x})}(t)), t = 0, 1, ..., N-1, where conj(x) is the complex conjugate of the complex number z. More generally, when M > N x(t) = (1/M)*sum(X<M>(t)*exp(+i*2*PI*t*k/M),0<=k<=M-1) = (1/M)*conj(DFT<M>{conj(DFT<M>{x})}(t)), t = 0, 1, ..., N-1, For t = N,...,M-1, the sum is 0. Periodic Extensions When dealing with the DFT it is sometimes convenient to consider a finite complex or real series as being a segment of length N from a periodic infinite complex or real series {x<N>(t),-oo<t<oo} with period N: x<N>(t) = x(t), t = 0, 1, ..., N-1 x<N>(t) = x<N>(t-N), t = N, N+1, ... x<N>(t) = x<N>(t+N), t = -1, -2, ... More generally, we can define x<M>(t) as the periodic extension with period M of x(t) padded with M-N 0's: x<M>(t) = x(t), t = 0, 1, ..., N-1 x<M>(t) = 0, t = N,...,M-1 x<M>(t) = x<M>(t-M), t = M, M+1, ... x<M>(t) = x<M>(t+M), t = -1, -2, ... With this extended definition, for any integer t0 X<M>(k) = sum(x<M>(t)*exp(-i*2*PI*t*k/M),t0 <= t <= t0+M-1) that is, as a summation over an arbitrary complete period of x<M>(t). Continuous Fourier Transform (CFT) The continuous Fourier transform of a finite real or complex series {x(t),0<=t<=N-1} is the continuous function of the real variable f X^(f) = CFT{X}(f) = sum(x(t)*exp(-i*2*PI*t*f),0<=t<=N-1) The argument f is the frequency at which X^(f) is evaluated and is in units of cycles. X^(f) is a periodic function of f with period 1, that is X^(f) = X^(f+k) = X^(f-k) for any integer k. You can consider the DFT to be a "sampling" of the CFT, in the sense that X<M>(k) = X^(k/M). Because X<M>(k), k = 0, ..., M-1 is the DFT of x(t) "padded" with M - N 0's, by padding {x(t)} with enough additional zeros, you can use the DFT to compute the CFT at an arbitrarily dense set of frequencies. For purposes of computing spectra of a series of length N it is usually desirable to compute Fourier transforms at approximately M = 2*N frequencies. Function padto() is useful for adding zero rows to a vector or matrix. You can define the continuous Fourier transform of an infinite real or complex series {x(t), -oo < t < oo} in a similar manner as X^(f) = sum(x(t)*exp(-i*2*PI*t*f), -oo < t < oo) when the infinite sum converges as it always will if only x(t) != 0 for only a finite set of t's. In another terminology, {x(t), -oo < t < oo} are the Fourier coeficients of the periodic function X^(f).

Gary Oehlert 2003-01-15