Discrete Fourier Transform

$$X[k]=\sum _{n=0}^{N-1}x[n]\cdot {\omega }_N^{nk}$$

• where ${\omega }_N=\exp \left(-\frac{2i\pi }{N}\right)$, called the “Nth root of unity”
  • Nth roots of unity is the related concept of the complex unit circle being split up equally into $N$ sectors, where integer powers of ${\omega }_N$ walk the circle
  • ${\omega }_N^{2a}={\omega }_{N/2}^a,a\in \mathbb{N}$
• where $N$ is the number of samples in the DT signal $x$
• where $k$ is the $k^{\text{th}}$ frequency bin, representing an area of frequencies in the frequency domain centered around $\frac{k{f}_s}{N}$, where $f_s$ is the Sampling Frequency
  • the spacing between bins is $\Delta f=\frac{f_s}{N}$, called the bin width
• where $X$ is a Complex Number
• where the input is assumed to be periodic with period $N$

Time Complexity

The Time Complexity of calculating the Discrete Fourier Transform as a Matrix product or by equivalently calculating each Dot Product per $k$ without matrices is $O(n^2)$, where the DFT Matrix $W$ is a Square Matrix

Use Cases of DFT

• FFT is most commonly used
• Approximate Derivatives $\to$ Solve PDEs
• Denoise Data
• Data Analysis
• Compression
  • Audio Compression
  • Image Compression
  • Wavelet Transform

Matrix Discrete Fourier Transform

$$\left[\begin{array}{c}X[0]\\ X[1]\\ X[2]\\ ⋮\\ X[N-1]\end{array}\right]=\left[\begin{array}{ccccc}1& 1& 1& \cdots & 1\\ 1& {\omega }_N& {\omega }_N^2& \cdots & {\omega }_N^{N-1}\\ 1& {\omega }_N^2& {\omega }_N^4& \cdots & {\omega }_N^{2(N-1)}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& {\omega }_N^{N-1}& {\omega }_N^{2(N-1)}& \cdots & {\omega }_N^{(N-1{)}^2}\end{array}\right]\left[\begin{array}{c}x[0]\\ x[1]\\ x[2]\\ ⋮\\ x[N-1]\end{array}\right]$$ $$\begin{array}{rl}\text{Let }W& \in {\mathbb{C}}^{N\times N}s.t.W_{i,j}={\omega }_N^{ij}\\ \vec{X}& =W\vec{x}\end{array}$$

• where $W$ is called the “DFT Matrix”

Inverse Discrete Fourier Transform

$$x[n]=\frac{1}{N}\sum _{k=0}^{N-1}X[k]\cdot {\omega }_N^{-nk}$$

Power Spectrum

Power Spectrum

The power spectrum is the distribution of Signal Power across frequency, computed by taking the squared magnitude of each DFT bin $k$:

$$P[k]=|X[k]{|}^2=I[k{]}^2+Q[k{]}^2$$

It discards phase information and retains only energy per frequency bin. The primary domain for signal detection; bins whose power exceeds the local noise floor are declared detections.

Link to original

FFT Shift

FFT Shift

The FFT Shift post-processes the output frequency graph of the FFT and centers 0 in the middle of the array, rather than at the beginning, making it easier to interpret. By default frequencies of zero are on the left, then positives, then negatives.

$$[k_0,{\vec{k}}_{+},{\vec{k}}_{-}]\to [{\vec{k}}_{-},k_0,{\vec{k}}_{+}]$$Link to original