$$dft$$ -ч

This document describes the Discrete Fourier Transform (DFT), that is, a Fourier

Transform as applied to a discrete complex valued series. The mathematics will

be given and source code (written in the C programming language) is provided in

For a continuous function of one variable f(t), the Fourier Transform F(f) will

where j is the square root of -1 and e denotes the natural exponent

Consider a complex series x(k) with N samples of the form

Further, assume that that the series outside the range 0, N-1 is extended

N-periodic, that is, x k = x k+N for all k.

The FT of this series will be denoted X(k), it will also have N samples.

The forward transform will be defined as

source