0.1 Discrete fourier transform

Discrete fourier transform

The Discrete Fourier Transform, from now on DFT, of a finite length sequence $(x_0,...,x_{K-1})$ is defined as

$${\stackrel{}{\mathrm{x̂}}}_k=\sum _{n=0}^{K-1}{x}_n{e}^{-2\pi jk\frac{n}{K}}(k=0,...,K-1)$$

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

$$\sum _{n=0}^{K-1}f\left(\frac{nT}{K}\right)\frac{T}{K}\simeq {\int }_0^{T}f\left(t\right)dt$$

we find

$${\hat{x}}_k=\sum _{n=0}^{K-1}x\left(\frac{nT}{K}\right)e^{-2\pi j\frac{nT}{K}k/T}\simeq \frac{K}{T}{\int }_0^{T}x\left(t\right)e^{-2\pi jtk/T}dt=K{X}_k$$

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

$${({\hat{x}}_0,...,{\hat{x}}_{K-1})}^T=DF{T}_K·{(x_0,...,x_{K-1})}^T.$$

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

$${DFT}_1=\left(\begin{array}{c}1\end{array}\right){DFT}_2=\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right){DFT}_4=\left(\begin{array}{cccc}1& 1& 1& 1\\ 1& -j& -1& j\\ 1& -1& 1& -1\\ 1& j& -1& -j\end{array}\right)$$

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

$$x·y=x_1{y}_1^{*}+x_2{y}_2^{*}+...+x_K{y}_K^{*},$$

where $a^{*}$ is the conjugate complex of $a$ . Orthogonal means $x·y=0$ . to each other. Also, all rows have length Length is computed as $\left|\right|x\left|\right|=\sqrt{x·x}=\sqrt{x_1{x}_1^{*}+x_2{x}_2^{*}+...+x_K{x}_K^{*}}=\sqrt{|x_1{|}^2+|x_2{|}^2+...+{\left|x_K\right|}^2}$ . $\sqrt{K}$ . Finally, the matrices are symmetric (exchanging lines for rows does not change the matrix). So, the multiplying DFT with its conjugate complex matrix ${\left(DF{T}_K\right)}^{*}$ we get $K$ times the unit matrix (diagonal matrix with all diagonal elements equal to $K$ ).

Inverse DFT

From all this we conclude that the inverse matrix of $DF{T}_K$ is $IDF{T}_K=(1/K)·{\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 ${\hat{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, ${\hat{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, ${\hat{x}}_k$ is periodic: ${\hat{x}}_k={\hat{x}}_{k+K}$ . Thus, it makes sense to evaluate ${\hat{x}}_k$ for any $k$ . For instance, we can rewrite [link] as

Since ${\hat{x}}_k$ corresponds to the frequency $k/T$ , the period $K$ of ${\hat{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)$ .