The Discrete Fourier Transform
Frequency-Domain Sampling and Reconstruction of Discrete-Time Signals
An aperiodic discrete-time signal x(n) with Fourier transform
X ( )
n
x( n) e j n (1)
Let us consider the sample X(ω) periodically in frequency at a spacing of δω radians
between successive samples.
Since X(ω) is periodic with period 2π.
The samples in the fundamental frequency range are necessary.
We take N equidistant samples in the interval 0 ≤ ω ≤ 2π with spacing δω = 2π/N, as
shown in Figure 1.
Figure 1: Frequency-domain sampling of the Fourier transform.
12/15/2022 1:57:01 PM 1
Frequency-Domain Sampling and Reconstruction of Discrete-Time Signals
If we evaluate Eq. (1) at ω = 2πk/N, then we obtain
2
X k x ( n) e j 2 kn / N [k 0, 1, 2, , N 1] (2)
N n
The summation in Eq. (2) can be subdivided into an infinite number of summations,
where each sum contains N terms.
Thus
2
1 N 1 2 N 1
X k
N
n N
x(n) e j 2 kn / N
x(n) e
n0
j 2 kn / N
n N
x (n) e j 2 kn / N
lN N 1
l n lN
x ( n) e j 2 kn / N
If we change the index in the inner summation from n to n - lN and interchange
the order of the summation, we obtain the result
2
N 1
j 2 kn / N
X k
N
x(n l N ) e
n 0 l
[ k = 0, 1, 2 ......... N - 1. ] (3)
12/15/2022 1:57:01 PM 2
Frequency-Domain Sampling and Reconstruction of Discrete-Time Signals
The signal
x p (n) x(n l N )
l
(4)
obtained by the periodic repetition of x(n) every N samples, it is clearly periodic with
fundamental period N.
Consequently, the signal xp(n) can be expanded in a Fourier series as
N 1
x p (n) k
c e
k 0
j 2 kn / N
n 0, 1, 2, , N 1 (5)
The Fourier coefficients
N 1
1
ck
N
x
n 0
p (n) e j 2 kn / N k 0, 1, 2, , N 1 (6)
2
N 1
j 2 kn / N
Comparing Eq.(3) with Eq.(6), we conclude that X k x ( n l N ) e
N n 0 l
1 2
ck X k k 0, 1, 2, , N 1 (7)
N N
12/15/2022 1:57:01 PM 3
Frequency-Domain Sampling and Reconstruction of Discrete-Time Signals
1 2 N 1
Therefore, Eq.(5) can be rewrite as ck X
N N
k x p (n) c e
k 0
k
j 2 kn / N
1 N 1
2 j 2 kn / N
x p (n)
N
k 0
X k e
N
n 0, 1, 2, , N 1 (8)
The relationship in Eq.(8) provides
the reconstruction of the periodic
signal xp(n) from the samples of the
spectrum X(ω).
Since, xp(n) is the periodic extension
of x(n) as given by Eq. (4).
It is clear that x(n) can be recovered
from xp(n).
If there is no aliasing in the time
domain.
If x(n) is time-limited to less than the
period N of xp(n). Figure 2: Aperiodic sequence x(n) of length L and
its periodic extension for N > L (no aliasing) and N
This situation is illustrated in Fig. 2. < L (aliasing).
12/15/2022 1:57:01 PM 4
Frequency-Domain Sampling and Reconstruction of Discrete-Time Signals
We consider a finite-duration sequence x(n), which is nonzero in the interval 0 ≤ n ≤ L-1.
We observe that when N ≥ L,
x ( n ) x p ( n) 0 n N 1
so that x(n) can be recovered from xp(n).
If N < L, it is not possible to recover from its periodic extension due to time domain
aliasing.
Thus, we conclude that the spectrum of an aperiodic discrete-time signal with finite
duration L, can be exactly recovered from its samples at frequencies ωk = 2πk/N, if N ≥ L.
The procedure is to compute xp(n) from Eq. (8), then
x (n ), 0 n N 1
x(n) p (9)
0, elsewhere
and X(ω) can be computed from Eq. (1).
In the continuous-time signals, it is possible to express the spectrum X(ω) directly in
terms of its samples X(2πnk/N), where k = 0, 1, ......., N - 1.
12/15/2022 1:57:01 PM 5
Frequency-Domain Sampling and Reconstruction of Discrete-Time Signals
To derive such an interpolation formula for X(ω), we assume that N > L and begin
with Eq. (8).
X ( ) x ( n) e j n
Since x(n) = xp(n) for 0 ≤ n ≤ N – 1, n
1 N 1
2 j 2 kn / N
x p (n)
N
k 0
X k e
N
0 n N 1 (10)
If we use Eq. (1) and substitute for x(n), we obtain
N 11 N 1
2 j 2 kn / N j n
X ( ) X k e e
n 0 N k 0 N (11)
2 1 N 1 j ( 2 k / N ) n
N 1
X k e
k 0 N N
n0
The inner summation term in the brackets of Eq. (11) represents the basic interpolation
function shifted by 2πk/N in frequency.
We define
1 N 1
1 1 e j N 1 sin( N / 2) j ( N 1) / 2
P ( )
N
e
n 0
j n
N 1 e j
N sin( / 2)
e (12)
12/15/2022 1:57:01 PM 6
Frequency-Domain Sampling and Reconstruction of Discrete-Time Signals
Then Eq. (11) can be expressed as
N 1
2 2
X ( ) X k P k NL (13)
k 0 N N
The interpolation function P(ω) is not the familiar (sinθ)/θ.
But it is a periodic counterpart of it, and it is due to the periodic nature of X(ω).
The phase shift in Eq. (12) reflects the fact that the signal x(n) is a causal, finite-
duration sequence of length N.
The function sin(ωN/2)/(Nsin(ω/2)) is plotted in
Fig. 3 for N = 5.
We observe that the function P(ω) has the property
2 1, k 0
P k (14)
N 0, k 1, 2, , N 1
The interpolation formula in Eq.(13) gives exactly
the sample values X(2πk/N) for ω = 2πk/N. Figure 3: Plot of the function
[sin(ωN/2)]/[N sin(ω/2)].
12/15/2022 1:57:01 PM 7
Discrete Fourier Transform (DFT)
The equally spaced frequency samples X(2nk/N), k = 0, 1, ….. , N - 1, do not uniquely
represent the original sequence x(n), when x(n) has infinite duration.
The frequency samples X(2nk/N), k = 0, 1, ......, N - I, correspond to a periodic sequence
xp (n) of period N, where xp (n) is an aliased version of x(n), that is
x p (n ) x( n lN ) (15)
l
When the sequence x(n) has a finite duration of length L N, then xp(n) is simply a
periodic repetition of x(n), where xp(n) over a single period is given as
x ( n), 0 n L 1
x p (n) (16)
0, L n N 1
Consequently, the frequency samples X(2πk/N), k = 0, 1, ...., N - 1, uniquely represent
the finite-duration sequence x(n).
A finite-duration sequence x(n) of length L [i.e., x(n) = 0 for n < 0 and n ≥ L ] has a
Fourier transform
L 1
X ( ) x ( n) e j n 0 2 (17)
n 0
where the upper and lower indices in the summation reflect the fact that x(n) = 0
outside the range 0 ≤ n < L - 1.
12/15/2022 1:57:01 PM 8
Discrete Fourier Transform (DFT)
When the sample X(ω) at equally spaced frequencies ωk = 2πk/N, k = 0, 1, 2, ......., N - 1,
where N ≥ L, the resultant samples are
2 k L 1
X (k ) X
N
x ( n) e
j 2 kn / N
n 0
(18)
N 1
X (k ) x( n) e
n 0
j 2 kn / N
k 0, 1, 2, , N 1
where for convenience, the upper index in the sum has been increased from L - 1 to
N - 1 since x(n) = 0 for n L.
The frequency samples are obtained by evaluating the Fourier transform X(ω) at a set
of N discrete frequencies.
The relation in Eq. (18) is called the discrete Fourier transform (DFT) of x(n).
The relation given by Eq. (10), which allows us to recover the sequence x(n) from the
frequency samples
1 N 1
x ( n) X ( k ) e j 2 kn / N n 0, 1, 2, , N 1 (19)
N k 0
This is called the inverse discrete Fourier transform (IDFT).
Clearly, when x(n) has length L < N, the N-point IDFT yields x(n) = 0 for L < n < N – 1.
12/15/2022 1:57:01 PM 9
Discrete Fourier Transform (DFT)
To summarize, the formulas for the DFT and IDFT are
N 1
DFT, X (k ) x (n) e
n 0
j 2 kn / N
k 0, 1, 2, , N 1 (20)
N 1
1 (21)
IDFT, x(n)
N
X (k ) e
k 0
j 2 kn / N
n 0, 1, 2, , N 1
The formulas for the DFT and IDFT given by Eq.(18) and Eq. (19) may be expressed as
N 1
X (k ) x ( n) W
n 0
kn
N k 0, 1, 2, , N 1 (22)
N 1
1
x ( n)
N
X (k ) W
k 0
kn
N n 0, 1, 2, , N 1 (23)
where, by definition,
WN e j 2 / N (24)
The computation of each point of the DFT can be accomplished by N complex
multiplications and (N - 1) complex additions.
Hence, the N-point DFT values can be computed in a total of N2 complex multiplications
and N(N - 1) complex additions.
The DFT and IDFT as linear transformations on sequences {x(n)} and {X(k)} respectively.
12/15/2022 1:57:01 PM 10
The DFT as a Linear Transformation
Let us define an N-point vector xN of the signal sequence x(n), an N-point vector XN of
frequency samples, and an N x N matrix WN as
1 1 1 1
x(0) X (0) 1 W
x(1) X (1) N W N
2
WN N 1
xN ; XN ; WN 1 WN 2 WN 4 WN 2( N 1) (25)
x ( N 1)
X ( N 1)
1 WN N 1 WN 2( N 1) ( N 1)( N 1)
WN
The N-point DFT may be expressed in matrix form as
X N WN x N (26)
where WN is the matrix of the linear transformation.
We observe that WN is a symmetric matrix.
We assume that the inverse of WN exists, then Eq. (26) can be inverted by pre-
multiplying both sides by WN-1.
Thus, we obtain
x N WN 1X N (27)
This is an expression for the IDFT.
12/15/2022 1:57:01 PM 11
N 1
1
The DFT as a Linear Transformation
x ( n)
N
X (k )W
k 0
kn
N
The IDFT as given by Eq. (23), can be expressed in matrix form as
1
x N WN X N (28)
N
where WN* denotes the complex conjugate of the matrix WN.
Comparison of Eq. (27) with (28) leads us to conclude that
1
WN-1 = WN (29)
N
WN WN = N I N (30)
where IN is an N x N identity matrix.
The matrix WN in the transformation is an orthogonal (unitary) matrix.
Its inverse exists and is given as WN*/N.
The existence of the inverse of WN was established previously from the derivation of the
IDFT.
The DFT and IDFT are computational tools that play a very important role in many
digital signal processing applications, such as frequency analysis of signals, power
spectrum estimation, and linear filtering.
12/15/2022 1:57:01 PM 12
12/15/2022 1:57:01 PM 13
