Short Notes: DFT (Discrete Fourier Transform)

 Page 1


Discrete F ourier T ransform
The Discrete F ourier T ransform (DFT) is a fundamen tal to ol in signal pro cessing that transforms a
finite sequence of discrete-time samples in to a sequence of frequency-domain comp onen ts. It is widely
used in applications suc h as audio pro cessing, image analysis, and telecomm unications to analyze the
frequency con ten t of discrete signals.
1. In t ro d uction to DFT
The DFT con v erts a sequence ofN discrete-time samplesx[n] , wheren = 0,1,...,N-1 , in to a sequence
ofN complex-v alued frequency comp onen tsX[k] , w herek = 0,1,...,N-1 . These comp onen ts represen t
the signal’s amplitude and phase at discrete frequencies. The DFT is a discrete coun terpart to the
con tin uous F ourier T ransform, tailored for finite-length signals.
2. Mat hematical Definition
The DFT of a discrete-time signal x[n] is defined as:
X[k] =
N-1
?
n=0
x[n]e
-j
2p
N
kn
, k = 0,1,...,N -1
where:
• X[k] is the k -th frequency comp onen t,
• x[n] is the n -th time-domain sample ,
• N is the length of the sequence,
• e
-j
2p
N
kn
is the complex exp onen tial (or t widdle factor),
• j =
v
-1 is the imaginary unit.
The in v erse DFT (IDFT) reconstructs the original signal x[n] from X[k] :
x[n] =
1
N
N-1
?
k=0
X[k]e
j
2p
N
kn
, n = 0,1,...,N -1
3. F requency In terpretation
The DFT pro vides the frequency sp ectrum of the signal at discrete frequencies:
f
k
=
kf
s
N
, k = 0,1,...,N -1
where f
s
is the sampling frequency . The frequency resolution is:
?f =
f
s
N
Eac h X[k] corresp o nds to the amplitude and phase of the signal at frequency f
k
. The comp onen ts for
k >N/2 corresp ond to negativ e frequencies due to the p erio dicit y of the DFT.
1
Page 2


Discrete F ourier T ransform
The Discrete F ourier T ransform (DFT) is a fundamen tal to ol in signal pro cessing that transforms a
finite sequence of discrete-time samples in to a sequence of frequency-domain comp onen ts. It is widely
used in applications suc h as audio pro cessing, image analysis, and telecomm unications to analyze the
frequency con ten t of discrete signals.
1. In t ro d uction to DFT
The DFT con v erts a sequence ofN discrete-time samplesx[n] , wheren = 0,1,...,N-1 , in to a sequence
ofN complex-v alued frequency comp onen tsX[k] , w herek = 0,1,...,N-1 . These comp onen ts represen t
the signal’s amplitude and phase at discrete frequencies. The DFT is a discrete coun terpart to the
con tin uous F ourier T ransform, tailored for finite-length signals.
2. Mat hematical Definition
The DFT of a discrete-time signal x[n] is defined as:
X[k] =
N-1
?
n=0
x[n]e
-j
2p
N
kn
, k = 0,1,...,N -1
where:
• X[k] is the k -th frequency comp onen t,
• x[n] is the n -th time-domain sample ,
• N is the length of the sequence,
• e
-j
2p
N
kn
is the complex exp onen tial (or t widdle factor),
• j =
v
-1 is the imaginary unit.
The in v erse DFT (IDFT) reconstructs the original signal x[n] from X[k] :
x[n] =
1
N
N-1
?
k=0
X[k]e
j
2p
N
kn
, n = 0,1,...,N -1
3. F requency In terpretation
The DFT pro vides the frequency sp ectrum of the signal at discrete frequencies:
f
k
=
kf
s
N
, k = 0,1,...,N -1
where f
s
is the sampling frequency . The frequency resolution is:
?f =
f
s
N
Eac h X[k] corresp o nds to the amplitude and phase of the signal at frequency f
k
. The comp onen ts for
k >N/2 corresp ond to negativ e frequencies due to the p erio dicit y of the DFT.
1
4. Prop erties of the DFT
The DFT exhibits sev eral imp ortan t prop erties:
1. Linearit y : F or signals x
1
[n] and x
2
[n] , and scalars a and b :
DFT{ax
1
[n]+bx
2
[n]} =aX
1
[k]+bX
2
[k]
2. P erio dicit y : The DFT sequence X[k] is p erio dic with p erio d N :
X[k +N] =X[k]
3. Time Shift : A shift in the time domain b y m samples causes a phase shift in the frequency
domain:
DFT{x[n-m]} =X[k]e
-j
2p
N
km
4. Conjugate Symmetry : F or real-v alued signals x[n] , the DFT satisfies:
X[N -k] =X
*
[k]
where X
*
[k] is the complex conjugate of X[k] .
5. F ast F ourier T ransform (FFT)
The DFT is computationally in tensiv e with a complexit y of O(N
2
) . The F ast F ourier T ransform (FFT)
is an e?icien t algorithm to compute the DFT with a complexit y of O(N logN) . The FFT exploits
symmetries in the DFT, suc h as the p erio dicit y of the t widdle factors, and is widely used in practical
implemen tations.
6. Applications of the DFT
The DFT is used in v arious domains:
• Signal Analysis : T o iden tify frequency comp onen ts in audio, sp eec h, or v ibration signals.
• Digital Filtering : Con v olution in the time domain corresp onds to m ultiplication in the frequency
domain, enabling e?icien t filter design.
• Image Pro cessing : The 2D DFT is used for tasks lik e image compression (e.g., JPEG) and
filtering.
• Comm unications : F or mo dulation, demo dulation, and sp ectrum analysis in systems lik e OFDM.
7. Limitations
• Finite Length : The DFT assumes the input signal is p erio dic with p erio d N . Non-p erio dic
signals ma y in tro duce sp ectral leakage, whic h can b e mitigated us ing windo wing tec hniques.
• F requency Resolution : The resolution ?f =
fs
N
dep ends on N . Longer sequences impro v e
resolution but increase computational cost.
• Real-Time Pro cessing : The DFT pro cesses a fixed blo c k of samples, whic h ma y in tro duce
latency in real-time applications.
2
Page 3


Discrete F ourier T ransform
The Discrete F ourier T ransform (DFT) is a fundamen tal to ol in signal pro cessing that transforms a
finite sequence of discrete-time samples in to a sequence of frequency-domain comp onen ts. It is widely
used in applications suc h as audio pro cessing, image analysis, and telecomm unications to analyze the
frequency con ten t of discrete signals.
1. In t ro d uction to DFT
The DFT con v erts a sequence ofN discrete-time samplesx[n] , wheren = 0,1,...,N-1 , in to a sequence
ofN complex-v alued frequency comp onen tsX[k] , w herek = 0,1,...,N-1 . These comp onen ts represen t
the signal’s amplitude and phase at discrete frequencies. The DFT is a discrete coun terpart to the
con tin uous F ourier T ransform, tailored for finite-length signals.
2. Mat hematical Definition
The DFT of a discrete-time signal x[n] is defined as:
X[k] =
N-1
?
n=0
x[n]e
-j
2p
N
kn
, k = 0,1,...,N -1
where:
• X[k] is the k -th frequency comp onen t,
• x[n] is the n -th time-domain sample ,
• N is the length of the sequence,
• e
-j
2p
N
kn
is the complex exp onen tial (or t widdle factor),
• j =
v
-1 is the imaginary unit.
The in v erse DFT (IDFT) reconstructs the original signal x[n] from X[k] :
x[n] =
1
N
N-1
?
k=0
X[k]e
j
2p
N
kn
, n = 0,1,...,N -1
3. F requency In terpretation
The DFT pro vides the frequency sp ectrum of the signal at discrete frequencies:
f
k
=
kf
s
N
, k = 0,1,...,N -1
where f
s
is the sampling frequency . The frequency resolution is:
?f =
f
s
N
Eac h X[k] corresp o nds to the amplitude and phase of the signal at frequency f
k
. The comp onen ts for
k >N/2 corresp ond to negativ e frequencies due to the p erio dicit y of the DFT.
1
4. Prop erties of the DFT
The DFT exhibits sev eral imp ortan t prop erties:
1. Linearit y : F or signals x
1
[n] and x
2
[n] , and scalars a and b :
DFT{ax
1
[n]+bx
2
[n]} =aX
1
[k]+bX
2
[k]
2. P erio dicit y : The DFT sequence X[k] is p erio dic with p erio d N :
X[k +N] =X[k]
3. Time Shift : A shift in the time domain b y m samples causes a phase shift in the frequency
domain:
DFT{x[n-m]} =X[k]e
-j
2p
N
km
4. Conjugate Symmetry : F or real-v alued signals x[n] , the DFT satisfies:
X[N -k] =X
*
[k]
where X
*
[k] is the complex conjugate of X[k] .
5. F ast F ourier T ransform (FFT)
The DFT is computationally in tensiv e with a complexit y of O(N
2
) . The F ast F ourier T ransform (FFT)
is an e?icien t algorithm to compute the DFT with a complexit y of O(N logN) . The FFT exploits
symmetries in the DFT, suc h as the p erio dicit y of the t widdle factors, and is widely used in practical
implemen tations.
6. Applications of the DFT
The DFT is used in v arious domains:
• Signal Analysis : T o iden tify frequency comp onen ts in audio, sp eec h, or v ibration signals.
• Digital Filtering : Con v olution in the time domain corresp onds to m ultiplication in the frequency
domain, enabling e?icien t filter design.
• Image Pro cessing : The 2D DFT is used for tasks lik e image compression (e.g., JPEG) and
filtering.
• Comm unications : F or mo dulation, demo dulation, and sp ectrum analysis in systems lik e OFDM.
7. Limitations
• Finite Length : The DFT assumes the input signal is p erio dic with p erio d N . Non-p erio dic
signals ma y in tro duce sp ectral leakage, whic h can b e mitigated us ing windo wing tec hniques.
• F requency Resolution : The resolution ?f =
fs
N
dep ends on N . Longer sequences impro v e
resolution but increase computational cost.
• Real-Time Pro cessing : The DFT pro cesses a fixed blo c k of samples, whic h ma y in tro duce
latency in real-time applications.
2
8. Practical Considerations
• Windo wing : T o reduce sp ectral leakage, a windo w function (e.g., Hamming or Hanning) is applied
to the signal b efore computing the DFT.
• Zero-P adding : A dding zeros to the signal increases the n um b er of frequency p oin ts, impro ving
the visual resolution of the sp ectrum without adding new information.
• Normalization : The factor
1
N
in the IDFT ensures energy preserv ation, but some implemen tations
include it in the DFT for symmetry .
9. Conclusion
The Discrete F ourier T ransform is a p o w erful to ol for analyzing and pro cessing discrete-time signals in
the frequency domain. By transforming time-domain samples in to frequency comp onen ts, it enables
a wide range of applications in signal pro cessing and comm unications. The FFT further enhances its
practicalit y b y reducing computational complexit y , making the DFT indisp ensable in mo dern digital
systems.
3