<< Chapter < Page | Chapter >> Page > |
The Discrete Fourier Transform, from now on DFT, of a finite length sequence $({x}_{0},...,{x}_{K-1})$ is defined as
To motivate this transform think of ${x}_{n}$ as equally spaced samples of a $T$ -periodic signal $x\left(t\right)$ over a period, e.g., ${x}_{n}=x(nT/K)$ . Then, using the Riemann Sum as an approximation of an integral, i.e.,
we find
Note that the approximation is better, the larger the sample size $K$ is.
Remark on why the factor $K$ in [link] : recall that ${X}_{k}$ is an average while ${\widehat{x}}_{k}$ is a sum. Take for instance $k=0$ : ${X}_{0}$ is the average of the signal while ${\widehat{x}}_{0}$ is the sum of the samples.
From the above we may hope that a development similar to the Fourier series [link] should also exist in the discrete case. To this end, we note first that the DFT is a linear transform and can berepresented by a matrix multiplication (the “exponent” $T$ means transpose):
The matrix ${DFT}_{\mathrm{K}}$ possesses $K$ lines and $K$ rows; the entry in line $k$ row $n$ is ${e}^{-2\pi jkn/K}$ . A few examples are
The rows are orthogonal The scalar product for complex vectors $x=({x}_{1},{x}_{2},...,{x}_{K})$ and $y=({y}_{1},{y}_{2},...,{y}_{K})$ is computed as
Inverse DFT
From all this we conclude that the inverse matrix of $DF{T}_{K}$ is $IDF{T}_{K}=(1/K)\xb7{\left(DF{T}_{K}\right)}^{*}$ . Since ${\left({e}^{-\alpha}\right)}^{*}={e}^{\alpha}$ we find
Spectral interpretation, symmetries, periodicity
Combining [link] and [link] we may now interpret ${\stackrel{\u02c6}{x}}_{k}$ as the coefficient of the complex harmonic with frequency $k/T$ in a decomposition of the discrete signal ${x}_{n}$ ; its absolute value provides the amplitude of the harmonic and its argument the phase difference.
If $x$ is even, ${\stackrel{\u02c6}{x}}_{k}$ is real for all $k$ and all harmonics are in phase.
Using the periodicity of ${e}^{2\pi jt}$ we obtain ${x}_{n}={x}_{n+K}$ when evaluating [link] for arbitrary $n$ . Short, we can consider ${x}_{n}$ as equally-spaced samples of the $T$ -periodic signal $x\left(t\right)$ over any interval of length $T$ :
Similarly, ${\stackrel{\u02c6}{x}}_{k}$ is periodic: ${\stackrel{\u02c6}{x}}_{k}={\stackrel{\u02c6}{x}}_{k+K}$ . Thus, it makes sense to evaluate ${\stackrel{\u02c6}{x}}_{k}$ for any $k$ . For instance, we can rewrite [link] as
Since ${\stackrel{\u02c6}{x}}_{k}$ corresponds to the frequency $k/T$ , the period $K$ of ${\stackrel{\u02c6}{x}}_{k}$ corresponds to a period of $K/T$ in actual frequency. This is exactly the sampling frequency (or sampling rate) of the original signal( $K$ samples per $T$ time units). Compare to the spectral repetitions.
However, the period $T$ of the original signal $x$ is nowhere present in the formulas of the DFT (cpre. [link] and [link] ). Thus, if nothing is known about $T$ , it is assumed that the sampling rate is 1 (1 sample per time unit), meaning that $K=T$ .
FFT
The Fast Fourier Transform (FFT) is a clever algorithm which implements the DFT in only $Klog\left(K\right)$ operations. Note that the matrix multiplication would require ${K}^{2}$ operations.
Matlab implements the FFT with the command
fft(x)
where
$x$ is the input vector.
Note that in Matlab the indices start always with 1! This means that the first entry ofthe Matlab vector
$x$ , i.e.
$x\left(1\right)$ is the sample point
${x}_{0}=x\left(0\right)$ . Similar, the last entry of the Matlab vector
$x$ is, i.e.
$x\left(K\right)$ is the sample point
${x}_{K-1}=x((K-1)T/K)=x(T-T/K)$ .
Notification Switch
Would you like to follow the 'Sampling rate conversion' conversation and receive update notifications?