Contents

fourier

Keywords: frequency domain, fourier transforms, complex numbers

                    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).