Skip to content

Discrete Fourier Transform

The Basics

Definition

"In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex-valued function of frequency."
-https://home.engineering.iastate.edu/~julied/classes/ee524/LectureNotes/l5.pdf

Equation
  • The DFT is the primary interval of the DFS, and is a sampling of the DTFT.
    $$

\begin{array}\\LARGE X_N[k]=\sum\limits_{n=0}{N-1}x[n]e{-j\frac{2\pi }{N} kn}\
\text{N-Point DFT}
\end{array}$$

  • Where:
  • N is the number of points in the DFT (you often choose this)
    • Zero-padding: In the case that \(x[n]\)'s non-zero range is smaller than N, we add on additional zeros to \(x[n]\). I.e. \(X_8\) would mean our input \(x[n]=\{4,3,2,1\}\) would turn into \(x[n]=\{4,3,2,1,0,0,0,0\}\) so that our DFT length could be found. MATLAB automatically assumes this is true when you try to calculate a DFT with more points than n values.
  • High-resolution vs. High Density: More points will produce a DFT that more closely resembles the DTFT (high-density), but does not reveal data that was not already in the DTFT. To get a high-resolution spectrum, you will need to get more samples from the original signal.
  • k is which point of the DFT we are calculating, such that \(\bf{0\leq k\leq (N-1)}\)
  • Evaluates the DTFT at discrete points, k, and calls each point \(X[k]\)
  • Unlike the DTFT, the DFT is not Continuous in Frequency, the DFT has N discrete values.
    Pasted image 20221230162558.png
Examples

Example Calculation

![[302 DFT Example.PNG]]

Zero-Padded DFT

![[302 Zero-padded DFT.png]]

Example (Analysis)
  • Building on the example from the DTFT page, let's find the 4 point and 8 point DFT of the sequence, \(x[n]=\{1,1,1,1\}\)
  • Insert maths here
  • Here's a MATLAB plot of the DTFT, aswell as the 4 point (Green Fill), and 8 point (Red Circle) DFT. As you can see, the DFT is a sampling of the DTFT in frequency.
    800
    ```
    f=0:0.01:1; % normalized freq

x=[1,1,1,1];
X=1+exp(-j2pif)+exp(-j2pif2)+exp(-j2pif*3); %DTFT of x
X4=fft(x,4);
f4=0:1/4:1-1/4;
X8=fft(x,8);
f8=0:1/8:1-1/8;
plot(f,abs(X),f4,abs(X4),'x',f8,abs(X8),'o');
xlabel("Normalized Frequency");
ylabel("Complex Magnitude of the Fourier Transform");

```

Happiness mainly comes from our own attitude, rather than from external factors.
— Dalai Lama