Dft definition and properties

Dft

The discrete Fourier transform (DFT) is the primary transform used for numerical computation in digital signal processing. It is very widely used for spectrum analysis , fast convolution , and many other applications. The DFT transforms $N$ discrete-time samples to the same number of discrete frequency samples, and is defined as

Idft

The inverse DFT (IDFT) transforms $N$ discrete-frequency samples to the same number of discrete-time samples. The IDFT has a form very similar to the DFT,

Dft and idft properties

Periodicity

Due to the $N$ -sample periodicity of the complex exponential basis functions $e^{i\frac{2\pi nk}{N}}$ in the DFT and IDFT, the resulting transforms are also periodic with $N$ samples.

$$X(k+N)=X(k)$$ $$x(n)=x(n+N)$$

Circular shift

A shift in time corresponds to a phase shift that is linear in frequency. Because of the periodicity induced by the DFT and IDFT, the shift is circular , or modulo $N$ samples.

$$(x((n-m)\mod N), X(k)e^{-(i\frac{2\pi km}{N})})$$ The modulus operator $p\mod N$ means the remainder of $p$ when divided by $N$ . For example, $$9\mod 5=4$$ and $$-1\mod 5=4$$

Time reversal

$$(x(-n\mod N)=x((N-n)\mod N), X((N-k)\mod N)=X(-k\mod N))$$ Note: time-reversal maps $(0, 0)$ , $(1, N-1)$ , $(2, N-2)$ , etc. as illustrated in the figure below.

Complex conjugate

$$(\overline{x(n)}, \overline{X(-k\mod N)})$$

Circular convolution property

Circular convolution is defined as $$\doteq ((x(n), h(n)), \sum_{m=0}^{N-1} x(m)x((n-m)\mod N))$$

Circular convolution of two discrete-time signals corresponds to multiplication of their DFTs: $$((x(n), h(n)), X(k)H(k))$$

Multiplication property

A similar property relates multiplication in time to circular convolution in frequency. $$(x(n)h(n), \frac{1}{N}(X(k), H(k)))$$

Parseval's theorem

Parseval's theorem relates the energy of a length- $N$ discrete-time signal (or one period) to the energy of its DFT. $$\sum_{n=0}^{N-1} \left|x(n)\right|^2=\frac{1}{N}\sum_{k=0}^{N-1} \left|X(k)\right|^2$$

Symmetry

The continuous-time Fourier transform , the DTFT , and DFT are all defined as transforms of complex-valueddata to complex-valued spectra. However, in practice signals are often real-valued.The DFT of a real-valued discrete-time signal has a special symmetry, in which the real part of the transform values are DFT even symmetric and the imaginary part is DFT odd symmetric , as illustrated in the equation and figure below.

$x(n)$ real  $X(k)=\overline{X((N-k)\mod N)}$ (This implies $X(0)$ , $X(\frac{N}{2})$ are real-valued.)