L1 DTFT
L1 DTFT
L1 DTFT
Tan Lee
2023
Discrete-time signals
Since n takes only integer values, the continuous-time Fourier transform (CTFT) can
not be applied.
Can we turn x[n] into a continuous-time signal and apply CTFT ? How ?
CTFT of discrete impulses
Taking CTFT,
The notation ω is used to represent the frequency variable for discrete-time signal, in
order to differentiate from Ω in CTFT.
Question: What is the relation between ω and Ω ?
The transform takes the form of a power series (power of e−jω ),
R 2π
0 ejω(k−n) dω = 0, for all k 6= n
|X(ejω )| = 1 + cos ω
∠X(ejω ) = −ω.
Example
Find the Fourier transform of x[n] = an u[n], where a is real and |a| < 1.
Solutions:
∞ ∞
X X 1
X(ejω ) = an u[n]e−jωn = an e−jωn =
n=−∞ n=0
1 − ae−jω
1
|X(ejω )| =
1 − a cos ω + j · a sin ω
1 1
= p = √
(1 − a cos ω) + (a sin ω)
2 2 1 − 2a cos ω + a2
a sin ω
∠X(ejω ) = − arctan( ).
1 − a cos ω
Example
a>0 a<0
Example
Solutions:
1, |n| ≤ N1
x[n] = N1 = 2
0, |n| > N1
N1
x(ejω ) = e−jωn
P
n=−N1
sin(N1 +1/2)ω
=e jωN1
(1 + e−jω + e−j2ω + · · · + e−j2N1 ω ) = sin(ω/2)
DTFT versus CTFT
Z ∞
X(jΩ) = x(t)e−jΩt dt
−∞
X∞
X(ejω ) = x[n]e−jωn
n=−∞
Z ∞
1
x(t) = X(jΩ)ejΩt dΩ
2π −∞
Z
1
x[n] = X(ejω )ejωn dω
2π 2π
Understanding X(ejω )
I The time interval between two successive samples in x[n] is equal to 1. One
may relate DTFT with CTFT of a sequence of impulses with inter-pulse
interval of 1.
I X(ejω ) repeats itself over 2π interval. Hence the Fourier integral can be taken
over any 2π interval.
I X(ejω ) is a complex function in general. It consists of the magnitude |X(ejω )|
and the phase ∠X(ejω )
I The principal value ∠X(ejω ) is limited to the range between −π and π. Adding
any integer multiples of 2π to it does not affect the result of computation.
I The Fourier transform converges, i.e., |X(ejω )| < ∞ for all ω, if
P∞
n=−∞ |x[n]| < ∞
High vs. low on ω-axis
Tan Lee, CUHK, Copyright 2014 ENGG 2030 Signals & Systems – Discrete-time Fourier transform: Page 7/32
High vs. low on ω-axis
Discrete-time periodic signal
x[n] = x[n + N]
k=−∞ k=−∞
That is, x(t) can be expressed as the summation of harmonic components ejkΩ0 t .
With k = 0, ±1, . . ., there are infinitely many different harmonic components and
their frequencies could go infinitely high.
Consider a discrete-time periodic signal x[n] with period of N. The fundamental
frequency is
2π
ω0 = ,
N
In analogy with CTFS, the harmonic components of x[n] should take the form of
ejkω0 n .
Understanding ejkω0 n
ejkω0 n = ej(k+N)ω0 n ,
k = 0, ej·0·ω0 n
k = 1, ej·1·ω0 n
... ...
j·(N−2)·ω0 n
k = N − 2, e
k = N − 1, ej·(N−1)·ω0 n
Like for continuous-time signals, x[n] can be expressed as Fourier series, which is the
summation of all the harmonic components, i.e.,
N−1
X
x[n] = ak ejkω0 n .
k=0
x[n] = x[n + N]
e−jkω0 n = e−jkω0 (n+N)
x[n]e−jkω0 n = x[n + N]e−jkω0 (n+N) .
Basis function of DTFS
φk [n] = ejk(2π/N)n are referred as the basis functions to compose a Fourier series.
Being the “bases”, they can be used to form any arbitrary periodic signal,
X
x[n] = ak φk [n]
k=hNi
It has been shown that there exist only N distinct basis functions, and
φk [n] = φk+N [n] = φk+2N [n] = . . . = φk+rN [n] for any integer r.
Consider two possible summation intervals: hNi = 1, 2, · · · , N and
hNi = 2, 3, · · · , N + 1. They should lead to the same x[n], i.e.,
imaginary
Complex plane
ej3·(2π /N)
Taking k as a constant and n
ej2·(2π /N)
as the variable, ej(2πk/N)n is a
ej(2π /N)
2π /N
sinusoidal function of n.
jN·(2π /N)
2π /N 1=e
real P
x[n] = ak φk [n] means
ej(N-1)·(2π /N) k=hNi
that x[n] is made up of N
different sinusoidals at frequency
1 2 3 N−1
0, N
· 2π, N
· 2π, N
· 2π, . . . , N
· 2π
Example
2π
Derive the Fourier series representation for x[n] = sin N
n.
Solutions:
2π
x[n] is periodic with period N and the fundamental frequency ω0 = N
.
The samples of x[n] can be obtained by sampling the continuous-signal sin 2πt at
interval of 1/N second.
1 j 2π 1 2π
x[n] =e N n − e−j N n
2j 2j
1 1
= ejω0 n − e−jω0 n
2j 2j
ak ejkω0 n , we have
P
Making correspondence to x[n] =
k=hNi
1 −1
a1 = , a−1 = .
2j 2j
Example
N=5
Example
Solutions:
Computing ak over any interval covering −N1 ≤ n ≤ N1 ,
N1
1 X 1 X −jk( 2π
ak = x[n]e−jkω0 n = e N
)n
N N n=−N
n=hNi 1
Example
Let m = n + N1 ,
2N1
1 X −jk( 2π )(m−N1 )
ak = e N
N m=0
2π
1 jk( 2π 1 − e−jk( N )(2N1 +1)
= e N )N1 ( 2π )
N 1 − e−jk( N )
2π 2π 2π
1 e−jk( 2N ) (ejk N (N1 +1/2) − e−jk N (N1 +1/2) )
= · 2π 2π 2π
N e−jk( 2N ) (ejk( 2N ) − e−jk( 2N ) )
( 2N1 +1
N
, k = 0, ±N, ±2N, · · ·
= 1 sin[ 2kπ (N1 +1/2)]
N
· N
sin( kπ )
, elsewhere
N
Example
N = 10 N = 20
N = 40
Fourier transform of periodic signals
and
DC component a0
2π n
1st harmonic a1 ej N
Example
Consider the following finite-duration sequence x[n].
x[n]
1
-2 -1 0 1 2 3 4 5 6 n
Let ỹ[n] be a periodic sequence formed by repeating the non-zero values of x[n] with the period
of N = 4, and z̃[n] be a periodic sequence with N = 8.
For the computation of DTFS of ỹ[n] and z̃[n], the basis functions are illustrated as follows
imaginary imaginary
j·π /2
e =j ej·π /2=j
j·3π /4
e ej·π /4
ej·5π /4 ej·7π /4
3
1 X −jk( 2π )n πk 3πk
bk = e 4 = 1 + e−j( 2 ) + e−jπk + e−j( 2 )
4 n=0
∴ b0 = 1, b1 = 0, b2 = 0, b3 = 0.
0.8
and bk+4r = bk . The DTFT of ỹ[n] is therefore
0.6
× 2π 0.4 3
X 2π
Ỹ(ejω ) = 2πbk δ(ω − k ).
0.2
k=0
4
0
-2π 0 2π 4π
The magnitude spectrum |Ỹ(ejω )| is given as (radian)
× 2π
0.5
0
-2π 0 2π 4π
(radian)
Example
For z̃[n],
3
1 X −jk( 2π )n πk πk 3πk
ck = e 8 = 1 + e−j( 4 ) + e−j( 2 ) + e−j( 4 )
8 n=0
1 1
∴ c0 = 0.5, c1 = (1 − 2.414j), c2 = 0, c3 = (1 − 0.414j)
8 8
1 1
and c4 = 0, c5 = (1 + 0.414j), c6 = 0, c7 = (1 + 2.414j).
8 8
and ck+8r = ck . The DTFT of z̃[n] is
7
X 2π
Z̃(ejω ) = 2πck δ(ω − k ).
k=0
8
0.6
× 2π 0.4
0.2
0
-2π 0 2π 4π
(radian)
Summary: N to N
jω
ak is also periodic of N, while X(e ) is periodic of 2π.
The N DTFS coefficients span exactly an interval of 2π and correspond to N
harmonic components of x[n].
2π
The harmonic components in frequency are spaced by N
radian.
Properties of DTFT
Commonly used DTFT pairs
Properties of DTFS
Parseval’s Relation
1 X X
|x[n]|2 = |ak |2
N n=<N> k=<N>