Chapter: Discrete Fourier Transform (DFT)

The basis for the discrete Fourier transform (DFT), also sometimes called finite Fourier transform or fast Fourier transform (FFT), are the properties of the n-th roots of unity. The DFT can be used to study any sequence of (real) numbers, which is the result of a sample of measurements of an unknown physical phenomenon, e.g. a signal.

The sequence is assumed to be periodical with a period $n$, if $n$ the number of measured values in the sample of a given "si. The theory of DFT, which will be described in this chapter, shows that this assumption does not really matter for the usefulness of DFT for sampling methods, i.e. even if the signal, in reality, is not periodical.

There are many ways to derive equivalent formulae for the DFT. The different formulae found in literature might differ from those introduced in this chapter by the sign of exponents, or the norming factor $\frac 1n$ of the so-called Fourier coefficients, but all of these formulae are equivalent forms of DFT and can be transformed to the forms introduced and derived in this chapter.

  1. Definition: Even Complex Sequence
  2. Definition: Odd Complex Sequence
  3. Definition: n-Periodical Complex Sequence
  4. Lemma: Sum of Roots Of Unity in Complete Residue Systems

Thank you to the contributors under CC BY-SA 4.0!