# Lab 5: Discrete Fourier Transform

DFT is a tool that is widely used in many areas. Yet, it is often taken for granted without proper understanding. In this assignment, we are going to develop a deeper understanding of DFT.

# Ринат, привет!

## Content
[TOC]

## Fourier Transform

### DTFT

The spectrum of the discrete signal is evaluated with the help of a discrete-time Fourier transform (DTFT).

Unfortunately, DTFT is not a practical transformation. First, the signal is fully specified only when DTFT is computed for all frequencies in the range , which includes an infinite number
of points.

### DFT

Discrete Fourier Transform allows overcoming some practical problems that arise from using DTFT. The core idea of DFT is to take a signal of finite length and introduce a periodic extension of this signal.


DTFT of a time-limited signal results in the signal with an unbounded spectrum. Periodic extension of the signal that takes place in DFT allows reducing the number of non-zero components in the spectrum.


### FFT

Suppose, we separated the Fourier Transform into even and odd indexed sub-sequences.


After performing a bit of algebra, we end up with the summation of two terms. The advantage of this approach lies in the fact that the even and odd indexed sub-sequences can be computed concurrently.


| Column 1 | Column 2 | Column 3 |
| -------- | -------- | -------- |
| Text | Text | Text |

Suppose, `N = 8` , to visualize the flow of data with time, we can make use of a butterfly diagram. We compute the Discrete Fourier Transform for the even and odd terms simultaneously. Then, we calculate `x[k]` using the formula from above.


Notice how we were able to cut the time taken to compute the Fourier Transform by a factor of 2. We can further improve the algorithm by applying the divide-and-conquer approach, halving the computational cost each time.

We can express the gains in terms of Big O Notation


## Exploring DFT

### Spectral leakage

If we build a simple single-frequency wave, as shown in the figure below, the transformation will result in non-zero magnitude values at the correct frequencies. We get such a good result because the sampling frequency matches peaks and valleys.

The signal has a single frequency spectrum under the condition that the ratio of the number of samples in the sequence $N$ by the number of samples in a single period of the signal $N_T$ is an integer:

$$\frac{N}{N_T} = k; k \in 0..N-1$$

This comes from the fact that when these conditions are met, the periodic extension of the signal results in an uninterrupted sinusoidal function. If we change the frequency of the cosine wave such that this number is rational, spectral leakage is observed.

The result of the transformation will show the presence of other frequencies


Here we can see 4 signals in time domain`(first column)` and frequency domain `(second column)` and all of them are sampled in the same $N = 40$ timestamps and $\Delta t = 0.01$. We can compute $N_T = (1 / freq) / \Delta t$

- sin with $freq = 5$.
$N / N_T = \frac{40}{(\frac{0.2}{0.01})} = 2$ - is integer
- sin with $freq = 21$.
$N / N_T = \frac{40}{\frac{(\frac{1}{21})}{0.01}}$ - is not integer
- sin with $freq = 37$.
$N / N_T = \frac{40}{\frac{(\frac{1}{37})}{0.01}}$ - is not integer

So we understand that only first signal has no a leakage. Also , it is correct in the frequency domain of last signal (sum of all)

Increasing/decreasing of amplitude can change only magnitude of frequency in frequency domain but not the frequency itself.

### Zero Padding and Spectral Interpolation

In the example above, we have observed that the DFT spectrum is not always what we think.

Remember that DFT approaches DTFT when $N \rightarrow \infty$ . This is equivalent to padding our signal with an infinite number of zeros. Let's try to apply this trick to our signals.


We can see that for our signals (and for time-limited signals), taking the DFT of the entire non-zero portion of extended by zeros yields exact interpolation [not an approximation] of the complex spectrum.

Spectrums are not the same. Peaks smoothed out and microwaves appeared

## Aliasing

### Nyquist sampling theorem

The Nyquist sampling theorem (Kotelnikov theorem) provides a prescription for the nominal sampling interval required to avoid aliasing. It may be stated simply as follows: The sampling frequency should be at least twice the highest frequency contained in the signal.

$$f_s \geq 2f_c$$

### Aliasing Effect

Let's consider aliasing effect on real example.

We will plot 2 signals in time range 0.5 sec.
First one is cosine with frequency 190 Hz and amplitude 0.5
Second one is cosine with frequency 10 Hz and amplitude 2

Let's check it with two different sampling rates
- 200
- 500


For first row two signals with `different frequencies` share `one` peak and it is not good. ($f_s = 200 < 2f_c = 2 * 190 = 380$)
The person receiving these samples, without any previous knowledge of the original signals, may well be misled into thinking that the signals has quite a different form

For second row two signals with `different frequencies` have `different peaks` and it is what we want. ($f_s = 500 > 2f_c = 2 * 190 = 380$)

## DFT basis orthogonality

The vectors

form an orthogonal basis over the set of N-dimensional complex vectors.

Proof


Where $\delta_{kk'}$ is the Kronecker delta. (In the last step, the summation is trivial if $k=k'$, where it is $1+1+⋅⋅⋅=N$, and otherwise is a geometric series that can be explicitly summed to obtain zero.)

(Also showed in the code)

## Self-check questions

1. What is the difference between DFT and FFT algorithms?
FFT (Fast Fourier Transform) is particular implementation of DFT (Discrete Fourier Transform) and has computational complexity of `O(N log(N))`, which is so far the best of all proposed Fourier transformations for discrete data. Most algorithms for DFT are`O(N^2)`.
Also FFT can applied only to signal with length which is not the power of 2.

2. What is the cause of spectral leakage?

$$\frac{N}{N_T} = k; k \notin 0..N-1$$

3. How to make an ideal interpolation in the frequency domain?
Padding our signal with an infinite number of zeros.

4. How can ideal interpolation clarify the frequency value in the case of spectral leakage?
Increasing number of samples increases coverage in frequency domain too. It allows to highlight the peak and clerify correct frequency

5. What may occur if the sampling rate is incorrectly selected?
`Different frequencies` will share `one` peak.
The person receiving these samples, without any previous knowledge of the original signals, may well be misled into thinking that the signals has quite a different form
We are not only losing information, but we are getting the wrong information
about the signal