A Hitchhiker's Guide to the FFT
III. Discrete Fourier Transform
III.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}$$ and an integer \(P\), the \(P\)-point Discrete Fourier Transform (\(P\)-DFT) of \(f_v\) is a vector \(F^{P \text{-} \text{DFT}}\) defined by $$\begin{equation}\begin{aligned} F^{P \text{-} \text{DFT}} : \left\{ 0, \ldots, P - 1 \right\} & \longrightarrow \mathbb{C} \\ k & \longrightarrow F^{P \text{-} \text{DFT}} [k] = F^{\text{DTFT}} \left( \frac{2 \pi k}{P} \right) \label{eq:PDFT} \end{aligned}\end{equation}$$ Hence the \(F^{P - \text{DFT}}\) is nothing else than the \(F^{\text{DTFT}}\) sampled over \([0, 2 \pi]\), with a sampling interval of \(T_s = \frac{2 \pi}{P}\) .
III.2 Example
Let us consider the same \(f_v\) as in the previous example and take its \(P\)-DFT for different values of \(P\). This can be implemented as follows
multi=4;
P=multi*N;
k_dft=(0:P-1);
X_dft=zeros(1,numel(k_dft));
for ii=-N/2:N/2
X_dft=X_dft+fvsampled(ii+N+1)*exp(-1i*omega_sampled*(ii));
end
stem(k_dft,real(X_dft),'r');
hold on
stem(k_dft,imag(X_dft),'b');
hold off
legend('real part','imaginary part'); axis([0 P-1 -2 N/2]);
title('P-DFT for P=N');
xlabel('k'); ylabel('F^{P-DFT}(k)');
Figure 5. \(P\)-DFT of \(f_v\) for \(P = N\) (left) and \(P = 2 N\) (right)
Figure 6. P-DFT of \(f_v\) for \(P = 4 N\)
The following figure illustrates the fact that the \(P\)-DFT is indeed a sample of the \(F^{\text{DTFT}}\) sampled over \([0, 2 \pi]\).
omega_sampled=k_dft*2*pi/P;
omega_sampled_plot=omega_sampled/pi;
plot(omega_plot,real(X),'b',omega_sampled_plot,real(X_dft),'or');
legend('analytic DTFT','P-DFT for P=4N');
axis([-2 2 -2 N/2]);
title('Sampled DTFT');
xlabel('omega/pi'); ylabel('X(omega)');
Figure 7. Illustration that the \(P\)-DFT is a sample of the DTFT