L1 DTFT

Download as pdf or txt
Download as pdf or txt
You are on page 1of 43

Discrete-time Fourier transform

Tan Lee

Department of Electronic Engineering


The Chinese University of Hong Kong
tanlee@ee.cuhk.edu.hk

2023
Discrete-time signals

Consider a discrete-time signal x[n] as follows. It has finite duration.

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

Consider the following signal that comprises 3 impulses,

x(t) = δ(t) + 2δ(t − T) + 3δ(t − 2T).

Taking CTFT,

X(jΩ) = 1 + 2e−jΩT + 3e−j2ΩT .

In general, if x(t) is composed of many equally spaced impulses,


∞ ∞
FT
X X
x(nT)δ(t − nT) ←→ x(nT)e−jnΩT .
n=−∞ n=−∞
CTFT of discrete impulses

Given a discrete-time signal x[n], we can construct a continuous-time signal x(t),


which comprises equally spaced pulses with the interval T = 1, i.e.,

x(t) = x[n]δ(t − n · 1).

Taking the CTFT of x(t),



X
X(jΩ) = x[n]e−jnΩ .
n=−∞

This gives the DTFT – Fourier transform of discrete-time signals.


Definition of DTFT

The formal definition of discrete-time Fourier transform (DTFT) of x[n] is:



X
X(ejω ) = x[n]e−jωn .
n=−∞

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ω ),

X(ejω ) = · · · + x[−2]ej2ω + x[−1]ejω + x[0] + x[1]e−jω + x[2]e−j2ω + · · ·


“Periodicity” of DTFT

X(ejω ) is the function of ω.


In X(ejω ), ω takes the real value from −∞ to ∞.
Note that ejω = ej(ω+2π) = ej(ω+4π) = . . ..
Thus

X(ejω ) = X(ej(ω+2π) ) = X(ej(ω+4π) ) = . . . = X(ej(ω+2kπ) ).

That is, X(ejω ) repeats itself on 2π interval.


If we know the value of X(ejω ) over any 2π interval, e.g. −π < ω ≤ π or
0 < ω ≤ 2π, we have the entire X(ejω ) for −∞ < ω < ∞.
Inverse DTFT

Multiplying ejωk on both sides of the DTFT equation,



X ∞
X
ejωk · X(ejω ) = ejωk · x[n]e−jωn = x[n]ejω(k−n)
n=−∞ n=−∞

Integrating over [0, 2π] (or any 2π interval of ω),


Z 2π ∞
X Z 2π
jω jωk
X(e )e dω = x[n] ejω(k−n) dω = x[k] · 2π
0 n=−∞ 0

R 2π
0 ejω(k−n) dω = 0, for all k 6= n

Thus we can derive x[k] from X(ejω ), i.e., inverse transform,


Z
1
x[k] = X(ejω )ejωk dω,
2π 2π
R
where 2π dω means integral over any 2π interval of ω.
Example

Find the Fourier transform of x[n] = 0.5δ[n] + δ[n − 1] + 0.5δ[n − 2].


Solutions:

X
X(ejω ) = x[n]e−jωn
n=−∞

= 0.5 + e−jω + 0.5e−j2ω


= e−jω (0.5ejω + 1 + 0.5e−jω )
= e−jω (1 + cos ω).

|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

Find the Fourier transform of the rectangular wave as shown.

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

x[n] = ejωn is a sinusoidal signal.


For ω = 0, ±2π, ±4π, · · · , x[n] = 1 for all n, i.e., x[n] is a DC signal.
Let us focus on the interval from ω = 0 to ω = 2π,
(1) as ω increases from 0 to π, ejωn tends to oscillate faster
High vs. low on ω-axis

(2) as ω further increases from π to 2π , the oscillation tends to be slower


(2) as Ω further increases from  to 2 , the oscillation tends to be slower

Back to the case


when  = 0

For a discrete-time signal, low-frequency part is represented by the values of


Foritsa discrete-time signal, around
Fourier transform Ω  0 part
low-frequency , Ωisrepresented
2π , etc.,by while
the values
the of
itshigh-frequency
Fourier transform is at Ω ω=
part around π ,0,Ωω =
3π2π,
, ...etc., while the high-frequency
part is at ω = ±π, ω = ±3π, . . . .

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

A discrete-time signal x[n] is periodic with fundamental period N if

x[n] = x[n + N]

where N is the smallest integer for which the equation holds.



ω0 = N
is referred to as the fundamental frequency.
Note that

I ω0 is an angle in radian, equal to a fraction of 2π;


I n · ω0 and (n + N) · ω0 are representing the same angle, such that
ejn·ω0 = ej(n+N)·ω0 ;
I N · ω0 = 2π, i.e., tthe same angle value as 0 · 2π.
Harmonic components of periodic DT signal

Recall that for a continuous-time periodic signal x(t) with period of T,


∞ ∞
X X 2π t
x(t) = ck ejkΩ0 t = ck ejk T

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

ω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 is a function of n. It represents a sinusoidal signal with the frequency of kω0 .


Since N · ω0 = 2π,

ejkω0 n = ej(k+N)ω0 n ,

there exist only N distinct harmonic components, which are

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

ej·N·ω0 n is the same as ej·0·ω0 n .


Definition of DTFS

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

Since ejkω0 n = ej(k+N)ω0 n , it can be shown that


X
x[n] = ak ejkω0 n ,
k=hNi

where hNi denotes any N successive integers, e.g., 0, 1, 2, · · · , N − 1, or


3, 4, 5, · · · , N + 2, or −100, −99, · · · , N − 101, etc.
The summation contains only the N distinct harmonic components, without repeating
any of them.
DTFS coefficients

ak is the harmonic component ejkω0 n .


Using the orthogonality property of ejkω0 n (with respect to k), we can derive (refer to
CTFT slides),
1 X
ak = x[n]e−jkω0 n .
N
n=hNi

Again, the summation contains only N distinct terms, because we have

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.,

x[n] = a1 φ1 [n] + a2 φ2 [n] + · · · + aN φN [n]


x[n] = a2 φ2 [n] + a3 φ3 [n] + · · · + aN+1 φN+1 [n].

Cancelling the common terms, we have a1 φ1 [n] = aN+1 φN+1 [n].


Since φ1 [n] = φN+1 [n], we can conclude a1 = aN+1 .
In general, we have ak = ak+N for any integer k.
Basis function

φk [n] = ejk(2π/N)n is a function of both k and n.


2π 2π ·2 2π ·3 2π ·(N−1)
It has N distinct values: 1, ej N , ej N , ej N , . . . , ej N

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


Derive the Fourier series representation for x[n] = sin N
n.
Solutions:

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

Given that ak ’s repeats with period N, we have


1
aN+1 = a2N+1 = a3N+1 = · · · =
2j
−1
aN−1 = a2N−1 = a3N−1 = ··· = .
2j
For the case of N = 5, the coefficients ak are plotted below.

N=5
Example

Find the Fourier series representation of the discrete-time square wave,

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

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

2N1+1 = 5 for the following cases

N = 10 N = 20

N = 40
Fourier transform of periodic signals

In the continuous-time case,



X ∞
X
x(t) = ak ejkΩ0 t ←→ 2πak δ(Ω − kΩ0 )
k=−∞ k=−∞

Similarly, for discrete-time signals,


X 2π n X 2π
x[n] = ak ejk N ←→ 2πak δ(ω − k )
N
k=hNi k=hNi

and

2πa0 = 2πa−N = 2πaN


2πa1 = 2πa−N+1 = 2πaN+1
2πa2 = 2πa−N+2 = 2πaN+2
···
DTFT of periodic signals

DC component a0

2π n
1st harmonic a1 ej N






DTFT for periodic signals


The complete spectrum 


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·π= -1 ej·0=1 ej·π= -1 ej·0=1


real real

ej·5π /4 ej·7π /4

ej·3π /2= -j ej·3π /2= -j


Example
The DTFS coefficients of ỹ[n] are:

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

|Z̃(ejω )| is plotted below.


0.8

0.6

× 2π 0.4

0.2

0
-2π 0 2π 4π
 (radian)
Summary: N to N

DTFS is a transformation from N time-domain samples to N frequency-domain


coefficients.
X 1 X
x[n] = ak ejkω0 n and ak = x[n]e−jkω0 n
N n=<N>
k=hNi

x[n] is periodic of N and ak is also periodic of N.


Typically x[n] is real, and ak is complex.
Without loss of generality:

{x[0], x[1], . . . , x[N − 1]} ↔ {a0 , a1 , . . . , aN−1 }


Summary: DTFS vs. DTFT

The DTFT is related to DTFS by


X 2π
X(ejω ) = 2πak δ(ω − k )
N
k=hNi


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].

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>

Computation over a finite interval in both time and frequency domains


First difference (in analogous to the differentiation in continuous-time)
FS 2π
x[n] − x[n − 1] ←→ (1 − e−jk N )ak
Common DTFS pairs
Summary of Fourier analysis techniques

You might also like