Project – Direct implementation versus FFT implementation of Discrete Fourier Transform (DFT)
Budget: $250 – $750 USD
Frequency domain transforms are extensively used in signals and systems applications. This
project involves a comparison of the direct implementation and FFT implementation of discrete
Fourier transform (DFT). As indicated by the DFT equation below, for the DFT computation, the
samples in a frame of length N are needed and not just a single sample. In other words, DFT/FFT
computation occurs in a frame-based manner. In frame processing, N samples are captured first
and then all of the N samples are needed to compute the DFT coefficients.
The DFT equation describing the frequency transformation is given by:
?[?] = ∑ ?[?] ∗ ??
??
?−1
?=0
, ? = 0,1, … , ? − 1
where WN=e-j2π/N. To compute a DFT term, N complex multiplications and N-1 complex additions
are required. For a frame consisting of N input signal samples, it takes N
2
complex multiplications
and N
2
-N complex additions. As a result, the direct DFT computation is computationally
inefficient, in particular when the size N increases or when long frames of signal samples are
considered.
To compute DFT in a time efficient manner, a fast algorithm named FFT (Fast Fourier Transform)
is used. FFT uses the symmetry properties of the frequency transformation to lower the numbers
of multiplications and additions. Note that FFT is not a transform but an algorithm which achieves
the DFT computation in a computationally efficient manner compared with the direct DFT
computation. The numbers of complex multiplications and additions in FFT are (N/2)log2N and
Nlog2N, respectively. The FFT algorithm provided in the project shell takes about 0.5ms to
transform one frame of signal samples for a frame length of 256 samples at 48kHz sampling
frequency (note: the smartphone hardware provides the lowest latency at this sampling frequency).
Since the duration of such a frame is about 5.3ms, this leads to achieving a real-time throughput
(i.e., no frames getting skipped)
project involves a comparison of the direct implementation and FFT implementation of discrete
Fourier transform (DFT). As indicated by the DFT equation below, for the DFT computation, the
samples in a frame of length N are needed and not just a single sample. In other words, DFT/FFT
computation occurs in a frame-based manner. In frame processing, N samples are captured first
and then all of the N samples are needed to compute the DFT coefficients.
The DFT equation describing the frequency transformation is given by:
?[?] = ∑ ?[?] ∗ ??
??
?−1
?=0
, ? = 0,1, … , ? − 1
where WN=e-j2π/N. To compute a DFT term, N complex multiplications and N-1 complex additions
are required. For a frame consisting of N input signal samples, it takes N
2
complex multiplications
and N
2
-N complex additions. As a result, the direct DFT computation is computationally
inefficient, in particular when the size N increases or when long frames of signal samples are
considered.
To compute DFT in a time efficient manner, a fast algorithm named FFT (Fast Fourier Transform)
is used. FFT uses the symmetry properties of the frequency transformation to lower the numbers
of multiplications and additions. Note that FFT is not a transform but an algorithm which achieves
the DFT computation in a computationally efficient manner compared with the direct DFT
computation. The numbers of complex multiplications and additions in FFT are (N/2)log2N and
Nlog2N, respectively. The FFT algorithm provided in the project shell takes about 0.5ms to
transform one frame of signal samples for a frame length of 256 samples at 48kHz sampling
frequency (note: the smartphone hardware provides the lowest latency at this sampling frequency).
Since the duration of such a frame is about 5.3ms, this leads to achieving a real-time throughput
(i.e., no frames getting skipped)