DSP Flashcards
FFT
Fast Fourier Transform
DFT
Discrete Fourier Transform
It is a DFT, but is much faster for
calculations. The whole point of the FFT
is speed in calculating a DFT.
FFT
are given credit for
bringing the FFT to the world in their paper: “An
algorithm for the machine calculation of
complex Fourier Series,” Mathematics
Computation, Vol. 19, 1965, pp 297-301.
J.W. Cooley and J.W. Tukey
The great German mathematician ______ had used the method more
than a century earlier. This early work was
largely forgotten because it lacked the tool to
make it practical: the digital computer.
Karl Friedrich
Gauss (1777-1855)
are honored because they
discovered the FFT at the right time, the
beginning of the computer revolution.
Cooley and Tukey
Proposed Fast Fourier
Transform in 1965.
Cooley and Tukey
is a highly efficient
procedure for computing DFT of a finite series
and requires less number of computations than
that of direct evaluation of DFT.
The fast fourier transform
is based on decomposition and breaking
the transform and combining them to get the
total transform.
FFT
There are basically two types of FFT
algorithm
- Decimation in Time
- Decimation in Frequency
is used to calculate the DFT of
an N-point sequence.
DIT
breaks the 16 point signal into two signals
each consisting of 8 points.
first stage
decomposes the data into four signals of
4 points. This pattern continues until there are N signals
composed of a single point.
second stage
is used each time a signal is broken in two, that is, the
signal is separated into its even and odd numbered
samples
interlaced decomposition
The FFT time
domain decomposition is usually carried out by a
bit reversal sorting
algorithm.
builds on the Danielson-Lanczos
Lemma and the twiddle factor to create an efficient
algorithm.
Butterfly Diagram
It’s the basic unit,
consisting of just two inputs and two outputs.
simplest butterfly
the input is bit – reversed order and
the output is natural order
DIT-FFT
the input is natural order and the
output is bit-reversed order
DIF-FFT
is a system that performs
mathematical operations on a discrete and
sampled time signal, so as to enhance or
reduce certain aspects of that particular signal
as may be necessary.
digital filter
There are two fundamental types of digital
filters:
finite impulse response (FIR) and
infinite impulse response (IIR)
is the appropriate
selection of the filter coefficients and the number of taps
to realize the desired transfer function H(f).
FIR filter design
commonly used for
audio and video processing, communications
systems, and transform analysis to name a few.
Multirate systems
The two basic
operations in a multirate system are decreasing
_____ and increasing ______ the
sampling-rate of a signal.
(decimation) and (interpolation)
