Get in touch!
Raphael Assier
  • Home
  • Research
    • Research Interests >
      • Canonical Scattering Problems
      • Combustion Instability
    • Publications
    • Awards & Grants
    • Conferences
    • Events organisation
    • Students & PDRAs
    • Opportunities
  • Teaching
    • Courses Taught
    • Fourier Tutorial >
      • Section I
      • Section II
      • Section III
      • Section IV
      • Section V
      • Section VI
      • Section VII
  • Career
  • Contact

A Hitchhiker's Guide to the FFT

Section I
Section II
Section III
Section IV
Section V
Section VI
Section VII

II. Discrete Time Fourier Transform

II.1 Definitions

Given a vector \(f_v\), referred to as the discrete physical function, or sampled physical function and defined by: $$\begin{aligned} f_v : \mathbb{N} & \longrightarrow \mathbb{C}\\ n & \longrightarrow f_v [n], \end{aligned}$$ the Discrete Time Fourier Transform (DTFT) of \(f_v\), denoted \(F^{\text{DTFT}}\), is given by $$\begin{equation}\begin{aligned} F^{\text{DTFT}} (\omega) & = \sum_{n = - \infty}^{\infty} f_v [n] e^{- j \omega n} \label{eq:DTFT} \end{aligned}\end{equation}$$ The vector \(f_v\) is also related to \(F^{\text{DTFT}}\) via Inverse Discrete Time Fourier Transform: $$\begin{equation}\begin{aligned} f_v [n] & = \frac{1}{2 \pi} \int_{- \pi}^{\pi} F^{\text{DTFT}} (\omega) e^{j \omega n} \mathrm{d} \omega . \label{eq:IDTFT} \end{aligned}\end{equation}$$ Note that \(F^{\text{DTFT}}\) is a continuous, \(2 \pi\)-periodic function from \(\mathbb{R} \rightarrow \mathbb{C}\)

II.2 Example

Let us consider the vector \(f_v\) defined by $$\begin{aligned} f_v [n] & = \max (1 - | \eta (n) |, 0), \end{aligned}$$ where $$\begin{aligned} \eta (n) & = 2 n / N \end{aligned}$$ This can be implemented as follows:

N=16;
n=-N:N;
tt=2*n/N;
fvsampled=max(1-abs(tt),0);
stem(n,fvsampled,'b');
xlabel('n');
ylabel('f_v[n]');
axis([-N N -0.5 1.5]);


Figure 3. The vector \(f_v\) for \(N = 16\)

In this case, the DTFT can be computed easily and is given by $$\begin{aligned} F^{\text{DTFT}} (\omega) & = \sum_{n = - \infty}^{\infty} f_v [n] e^{- j \omega n}\\ & = \sum_{n = - N / 2}^{N / 2} (1 - 2| n| / N) e^{- j \omega n} \end{aligned}$$ This can be implemented as follows:

Per=1; % Number of periods one wants to plot
omega=linspace(-Per*pi,Per*pi,1000);
X=zeros(1,numel(omega));
for ii=-N/2:N/2
X=X+fvsampled(ii+N+1)*exp(-1i*omega*(ii));
end
omega_plot=omega/pi;
plot(omega_plot,real(X),'r',omega_plot,imag(X),'b');
title('Continuous analytic DTFT');
axis([-Per Per -2 N/2]); legend('real part','imaginary part');
xlabel('omega/pi'); ylabel('F^{DTFT}(omega)');


Figure 4. Plot of 4 periods (left) and one period (right) of the analytic DTFT of \(f_v\) for \(N=16\)


Powered by
✕