Chapter 5 The Discrete Time Fourier Transform In the previous chapter we used the time domain representation of the signal. Given any signal {x[n]}we can write it as linear combination of basic signals {δ[n − k]}. Another representation of signals that has been found very useful is frequency domain representation. In the mid 1960s an algorithm for calculation of the Fourier transform was discovered, known as the Fast-Fourier Transform (FFT) algorithm. This spurred the development of digital signal processing in many areas. The Fourier representation of signals derives its importance from the fact that exponential signals are eigenfunctions for the discrete time LTI systems. What we mean by this is that if {z n } is input signal to an LTI system then soutput is given by H(z){z n }. Let us consider an LTI system with impulse response {h[n]}. Then the FIGURE 1. output is given by y[n] = =
∞ k=−∞ ∞
h[k]x[n − k] h[k]z n−k
k=−∞ ∞ n
= z
h[k]z −k
k=−∞
= H(z)z n where H(z) =
∞
h[k]z −k assuming that the summation in right-hand
k=−∞
side converges. Thus output is same exponential sequence multiplied by a constant that depends on the value of z. The constant H(z) for a specified value of z is the eigenvalue associated with eigenfunction {z n }. In the analysis of LTI system, the usefulness of decomposing a more general signal in terms of eigenfunctions can be seen from the following example. Let {x[n]} correspond to a linear combination of two exponentials {x[n]} = a1 {z1n } + a2 {z2n }
1
From the eigenfunction property and superposition property the response {y[n]} is given by {y[n]} = a1 H(z1 ){z1n } + a2 H(z2 ){z2n } More generally if {x[n]} =
ak {zkn }
k
then {y[n]} =
an H(zn ){zkn }
k
Thus if input signal can be represented by a linear combination of exponential signals, the output can also be represented by a linear combination of same exponentials, moreover the coefficient of the linear combination in the output is obtained by multiplying,ak , the coefficient in the input representation by corresponding eigen value H(zk ). The procedure outlined above is useful if we can represent a large class of signals in terms of complex exponentials. In this chapter we will consider representation of aperiodic signals in terms of signals {ejωn }.
Representation of Aperiodic signals: The Discrete Time Fourier Transform (DTFT) Here we take the exponential signals to be {ejωn } where ω is a real number. The representation is motivated by the Harmonic analysis, but instead of following the historical development of the representation we give directly the defining equation. ∞ |x[n]| < ∞ that is {x[n]} Let {x[n]} be discrete time signal such that n=−∞
sequence is absolutely summable. The sequence {x[n]} can be represented by a Fourier integral of the form 1 x[n] = 2π where jω
x(e ) =
π X(ejω )ejωn dω
(5.1)
−π ∞
x[n]e−jωn
(5.2)
n=−∞
Equation (5.1) and (5.2) give the Fourier representation of the signal {x[n]}. Equation (5.1) is referred as synthesis equation or the inverse discrete time 2
Fourier transform (IDTFT) and equation (5.2)is Fourier transform in the analysis equation. Fourier transform of a signal in general is a complex valued function, we can write (5.3) X(ejω ) = XR (ejω ) + jXI (ejω ) where XR (eiω ) is the real part of X(ejω ) and XI (ejω ) is imaginary part of the function X(ejω ). We can also use a polar form jω )
X(ejω ) = |X(ejω )|eX(e
(5.4)
where |X(ejω )| is magnitude and X(ejω ) is the phase of X(ejω ). We also use the term Fourier spectrum or simply, the spectrum to refer to X(ejω ). Thus |X(ejω )| is called the magnitude spectrum and X(ejω ) is called the phase spectrum. Form equation (5.2) we can see that X(ejω ) is a periodic function with period 2π i.e. X(ejω+2π ) = X(ejω ). We can interpret (5.1) as Fourier coefficients in the representation of a perotic function X(ejω ). In the Fourier series analysis our attention is on the periodic function, here we are concerned with the representation of the signal {x[n]}. So the roles of the two equation are interchanged compared to the Fourier series analysis of periodic signals. Now we show that if we put equation (5.2) in equation (5.1) we indeed get the signal {x[n]}. Let π ∞ 1 x[m]e−jωm e+jωn dω xˆ[n] = 2π m=−∞ −π
where we have substituted X(ejω ) from (5.2) into equation (5.1) and called the result as xˆ[n]. Since we have used n as index on the left hand side we have used m as the index variable for the sum defining the Fourier transform. Under our assumption that {x[n]} sequence is absolutely summable we can interchange the order of integration and summation. Thus π ∞ 1 x[m] e+jω(n−m) dω (5.5) xˆ[n] = 2π m=−∞ −π
The integral with the parentheses can be evaluated as if m = n then ejω(n−m) = 1 π 1 and 1.dω = 1 2π −π
3
if m = n 1 2π
π −π
then ejω(n−m) = cos ω(n − m) + j sin ω(n − m) π j cos ω(n − m)dω + sin ω(n − m)dω 2π −π −π
π 1 sin ω(n − m)
π j cos ω(n − m)
=
2π (n − m) −π 2π n−m −π = 0
1 ejω(n−m) dω = 2π
π
Thus in equation (5.5) there is only one non-zero term in RHS, corresponding to m = n, and we get xˆ[n] = x[n]. This result is true for all values of n and so equation (5.1) is indeed a representation of signal {x[n]} in terms eigenfunctions {ejωn } In above demonstration we have assumed that {x[n]} is absolutely summable. Determining the class of signals which can be represented by equation (5.1) is equivalent to considering the convergence of the infinite sum in equation (5.2). If we fix a value of ω = ω0 then, RHS of equation (5.2) is a complex valued series, whose partial sum is given by jω0
XN (e
N
)=
x[n]e−jω0 n
n=−N
The limit as N → ∞ if the partial sum XN (ejω0 ) exists if the series is absolutely summable.
|XN (e
jω0
N
)| = |
x[n]e−jω0 n |
n=−N
≤
N
|x[n]e−jω0 n | by triangle inequality
n=−N
=
N
|x[n]|
n=−N
Since the limit N → ∞
N
|x[n]| exists by our assumption the limit
n=−N
N → ∞ XN (ejω0 ) exists for every ω = ω0 . Furthermore it can be shown that the series converges uniformly to a continuous function of ω. If a sequence has only finitely many non-zero terms then it is absolutely 4
summable and so the Fourier transform exists. Since a stable sequence is by definition, an absolutely summable sequence, its Fourier transform also exits. Example: Let {x[n]} = {an u[n]} Fourier transform of this sequence will exist if it is absolutely summable. We have ∞ ∞ |x[n]| = |a|n n=−∞
n=0
This is a geometric series and sum exists if |a| < 1, in that case
|a|n =
1 < +∞ 1 − |a|
Thus the Fourier transform of the sequence {an u[n]} exists if |a| < 1. The Fourier transform is jω
X(e ) = =
∞ n=0 ∞
e−jωn (ae−jω )n
n=0
=
1 1 − ae−jω
(5.6)
Where the last equality follows from sum of a geometric series, which exists if |ae−jωn | < 1 i.e. |a| < 1. Absolute summability is a sufficient condition for the existence of a Fourier transform. Fourier transform also exists for square summable sequence. ∞
|x[n]|2 < ∞
n=−∞
For such signals the convergence is not uniform. This has implications in the design of discrete system for filtering. We also deal with signals that are neither so absolutely summable nor square summable. To deal with some of these signals we allow impulse functions, which is not an ordinary function but a generalized function as a Fourier transform. The impulse function is defined by the following properties ∞ δ(ω)dω = 1 (a) (b)
−∞ ∞
−∞
X(ejω )δ(ω−ω0 )dω = X(ejω0 ) if X(ejω ) is continuous at ω = ω0 ;(shifting 5
or convolution property) (c) X(ejω )δ(ω) = X(ej0 )δ(ω) if X(ejω ) is continuous at ω = 0 Since X(ejω ) is a periodic function, let us consider jω
X(e ) =
∞
2πδ(ω + 2πk)
(5.7)
k=−∞
If we substitute this in equation (5.1) we get 1 x[n] = 2π π
π ∞
δ(ω + 2πh)ejωn dω
−π h=−∞
δ(ω)ejωn dω
= −π
Since there is only one impulse in the interval of integration x[n] = 1 Thus we can say that (5.7) represents Fourier transform of a signal such that x[n] = 1 for all n. As a generalization of the above example consider a sequence {x[n]} whose Fourier transform is jω
X(e ) =
∞
2π δ(ω − ω0 + 2πk), −π < ω0 ≤ π
k=−∞
substituting this in equation (5.1) we get 1 x[n] = 2π π
π ∞
2πδ(ω − ω0 + 2πh)ejωn dω
−π h=−∞
δ(ω − ω0 )ejωn dω
= −π
as only one term corresponding to k = 0 will be there in the interval of the integration x[n] = ejω0 n So the signal is {ejω0 n } when Fourier transform is given by (5.8). More generally if x[n] is sum of an arbitrary set if complex exponentials {x[n]} = a1 {ejω1 n } + a2 {ejω2 n } + ... + am {ejωm n } 6
5.8
Thus its Fourier transform is jω
X(e ) = a1
∞
2πδ(ω−ω1 +2πk)+a2
k=−∞
∞
∞
2πδ(ω−ω2 +2πk)+.....+am
k=−∞
k=−∞
(5.9) Thus X(e ) is a periodic impulse train, with impulses located at the frequencies ω1 , ω2 ...ωm of each of the complex exponentials and at all points that are multiples of 2π from these frequencies. An interval of 2π contains exactly one impulse from each of the summation in RHS of (5.9) Example: Let {x[n]} = {cos ω0 n} jω
1 1 x[n] = ejω0 n + e−jω0 n 2 2 Hence X(ejω ) =
∞
π[δ(ω − ω0 + 2πk) + δ(ω + ω0 + 2πk)]
k=−∞
Properties of the Discrete Time Fourier Transform: In this section we use the following notation. Let {x[n]} and {y[n]} be two signal, then their DTFT is denoted by X(ejω ) and Y (ejω ). The notation {x[n]} ↔ X(ejω ) is used to say that left hand side is the signal x[n] whose DTFT is X(ejω ) is given at right hand side.
1. Periodicity of the DTFT: As noted earlier that the DTFT X(ejω ) is a periodic function of ω with period 2π. This property is different from the continuous time Fourier transform of a signal. 2. Linearity of the DTFT: If {x[n]} ↔ X(ejω ) and {y[n]} ↔ Y (ejω ) then a{x[n]} + b{y[n]} ↔ aX(ejω ) + bY (ejω ) This follows easily from the defining equation (5.2).
7
2πδ(ω−ωm +2πk)
3. Conjugation of the signal: If {x[n]} ↔ X(ejω ) then {x∗ [n]} ↔ X ∗ (e−jω ) where * denotes the complex conjugate. We have DTFT of {x∗ [n]} ∞
∗
−jωn
x [n]e
∞
=
n=−∞
[x[n]ejωn ]∗
n=−∞
=
∞
∗ x[n]e−j(−ω)n
n=−∞ ∗ −jω
= X (e
)
4. Time Reversal {x[−n]} ↔ X(e−jω ) The DTFT of the time reversal sequence is ∞
x[−n]e−jωn
n=−∞
Let us change the index of summation as m = −n =
∞
x[m]ejωm = X(e−jω )
m=−∞
5. Symmetry properties of the Fourier Transform: If x[n] is real valued than X(ejω ) = X ∗ (e−jω ) This follows from property 3. If x[n] is real valued then x[n] = x∗ [n], so {x[n]} = {x∗ [n]} and hence X(ejω ) = X ∗ (e−jω ) expressing X(ejω ) in real and imaginary parts we see that XR (ejω ) + jXI (ejω ) = XR (e−jω ) − jXI (e−jω ) which implies
XR (ejω ) = XR (e−jω ) 8
and
XI (ejω ) = −XI (e−jω )
That is real part of the Fourier transform is an even function of ω and imaginary part is an odd function of ω. The magnitude spectrum is given by jω 2 jω 2 jω |X(e )| = XR (e ) + XI (e ) = XR2 (e−jω ) + XI2 (e−jω ) = |X(e−jω )| Hence magnitude spectrum of a real signal is an even function of ω. The phase spectrum is given by XI (ejω ) XR (ejω ) −XI (e−jω ) = tan−1 XR (e−jω ) XI (e−jω ) = −tan−1 XR (e−jω ) = −X(e−jω )
X(ejω ) = tan−1
Thus the phase spectrum is an odd function of ω. We denote the symmetric and antisymmetric part of a function by 1 1 {x[n]} + {x∗ [−n]} 2 2 1 1 Od({x[n]}) = {x[n]} − {x∗ [−n]} 2 2 1 1 Ev(X(ejω )) = X(ejω ) + X ∗ (e−jω ) 2 2 1 1 Od(X(ejω )) = X(ejω ) − X ∗ (e−jω ) 2 2 Ev({x[n]}) =
Then using property (2) and (3) we see that Ev({x[n]}) ↔ Re X(ejω ) Od({x[n]}) ↔ jIm X(ejω ) and using property (2) and (4) we can see that Re({x[n]}) ↔ Ev(X(ejω )) Im({x[n]}) ↔ Od(X(ejω )) 9
6. Time shifting and frequency shifting: {x[n − n0 ]} ↔ e−jωn0 X(ejω ) {ejω0 n x[n]} ↔ X(ej(ω−ω0 ) ) These can be proved very easily by direct substitution of x[n − n0 ] in equation(5.2) and X(ej(ω−ω0 ) ) in equation (5.1). 7. Differencing and summation: {x[n] − x[n − 1]} ↔ (1 − e−jω )X(ejω ) This follows directly from linearity property 2. Consider next the signal {y[n]} defined by y[n] =
n
x[m]
m=−∞
since y[n] − y[n − 1] = x[n], we are tempted to conclude that the DTFT of {y[n]} is DTFT of {x[n]} divided by (1 − e−jω ). This is not entirely true as it ignores the possibility of a dc or average term that can result from summation. The precise relationship is n ∞ 1 jω j0 x[m] ↔ X(e ) + πX(e ) δ(ω + 2πk) 1 − e−jω m=−∞ k=−∞ We omit the proof of this property. If we take {x[n]} = {δ[n]} then we get n
∞ 1 {u[n]} = { δ[n]} ↔ +π δ(ω + 2πk) 1 − e−jω m=−∞ k=−∞
8. Time and frequency scaling: For continuous time signals we know that the Fourier transform of x(at) is given by 1/|a|X( Ωa ). However if we define a signal {x[an]} we run into difficulty as the index an must be an integer. Thus if a is an integer say a = k > 0, then we get signal {x[kn]}. This consists of taking k th sample of the original signal. Thus the DTFT of this signal looks similar to the Fourier transform of a sampled signal. The result that resembles the continuous time signal is obtained if we define a signal {x(k) [n]} by
10
x[ n ], if n is multiple of k k x(k) [n] = 0, if n is not a multiple of k For example {x(2) [n]} is illustrated below FIGURE 2 The signal {x(h) [h]} is obtained by inserting (k − 1) zeroes between successive value if signal {x[n]}.
jω
X(k) (e ) = =
∞
x(k) [n]e−jωn
n=−∞ ∞
x[km]e−jωkm
m=−∞ jkω
= X(e
)
Here we can note the time frequency uncertainly. Since {x(k) [n]} is expanded sequence, the Fourier transform is compressed. 9. Diffentiation in frequency domain ejω
X(e
)
∞
x[n]e−jωn
n=−∞
Differentiating both sides with respect to ω, we obtain ∞ d jω −jnx[n]e−jωn X(e ) = dω n=−∞
multiplying both sides by j we obtain d X(ejω ) dω
{nx[n]} ↔ j 10. Passeval’s relation: ∞
1 |x[n]| = 2π n=−∞
∞
2
−∞
11
|X(ejω )|2 dω
We have ∞
|x[n]|2 =
n=−∞
∞
x[n]
n=−∞
1 2π
∞
∗ X(ejω )ejωn dω
−∞
interchanging summation and integration we get 1 = 2π =
=
1 2π 1 2π
π
∗
∞
jω
X (e ) −π π
−π π
x[n]e−jωn dω
n=−∞
X ∗ (ejω )X(ejω )dω
|X(ejω )|2 dω
−π
11. Convolution property: This is the eigenfunction property of the complex exponential mentioned in the beginning of the chapter. The fourier syntaxis equation (5.1) for the x[n] can be interpreted as a representation of {x[n]} in terms of linear combinations of complex exponential with amplitude proportional to X(ejω ). Each of these complex exponential is an eigenfunction of the LTI system and so the amplitude Y (ejω ) in the decomposition of {y[n]} will be X(ejω )H(ejω ), where H(ejω ) is the Fourier transform of the impulse response. We prove this formally. The output {y[n]} is given is terms of convolution sum, so jω
Y (e ) = =
∞
y[n]e−jωn
n=−∞ ∞
∞
k=−∞ h[k]x[n
− k] e−jωn
n=−∞
interchanging order of the summation =
∞ l=−∞
h[h]
∞ n=−∞
12
x[n − k]e−jωn
Let m = n − k then n = m + k and we get = =
∞ k=−∞ ∞
∞
h[k]
x[m]e−jω(m+k)
m=−∞ −jωk
h[k]e
k=−∞ jω
∞
x[m]e−jωm
m=−∞ jω
= H(e )X(e ) Thus if {y[n]} = {h[n]} {x[n]} then Y (ejω ) = H(ejω )X(ejω )
(5.20)
convolution in time domain becomes multiplication in the frequency domain. The fourier transform of the impulse response {h[n]} is known as frequency response of the system. 0.0.1
12. The Modulation or windowing property
Let us find the DTFT of product of two sequences {x[n]}{y[n]} = {x[n]y[n]} = {z[n]} ∞ Z(ejω ) = x[n]y[n]e−jωn n=−∞
Substituting for x[n] in terms of IDFT we get π ∞ 1 = X(ejα )ejαn dα y[n]e−jωn 2π n=−∞ −π
interchanging order of integration and summation
∞ π 1 = X(ejα ) y[n]e−j(ω−α)n dα 2π n=−∞ =
1 2π
−π π
X(ejα )Y (ej(ω−α) )dα −π
This looks like convolution of two functions, only the interval of integration is −π to π. X(ejω ) and Y (ejω ) one periodic functions, and equation (5.21) is called periodic convolution. This 13
1 X(ejω ) ⊗ Y (ejω ) 2π where ⊗ denotes periodic convolution. We summarize these properties in Table (5.1) {x[x[n]y[n]} ←→
Aperiodic signal {x[n]} {y[n]} a{x[n]} + b{y[n]} {x[n − n0 ]} {e−jωn0 x[n]} x∗ [n] x[−n] Table 5.1: Properties of Discrete time Fourier Transform {x[n]} ∗ {y[n]} {x[n]y[n]} {x[n] − x[n − 1]} ∞ { x[n]} k=−∞
{nx[n]} ∞ x[n]y ∗ [n] n=−∞
The frequency response of systems characterized by linear constant coefficient difference equation. As we have seen earlier, constant coefficient linear difference equation with zero initial condition can be used to describe some linear time invariant systems. The input-output {x[n]} and {y[n]} are related by 0
ak y[n − k] =
k=0
n
x[n − k]
(5.22)
k=0
We assume that Fourier transforms of {x[n]}, {y[n]}and{h[n]} ({h[h]} is the impulse response of the system) exist, then convolution property implies that Y (ejω ) H(ejω ) = X(ejω ) Taking fourier transform of both sides of equation (5.22) and using linearity and time shifting property of the Fourier transform we get N
−jωk
ak e
jω
Y (e ) =
k=0
M k=0
14
bk e−jωk X(ejω )
Discre
1 X(e−jω ) 1−e−jω
1 2π
+
or H(ejω ) = M
=
Y (ejω ) X(ejω )
bk e−jωk
k=0 N
(5.23) ak e−jωk
k=0
Thus we see that the frequency response is ratio of polynomials in the variable e−jω . The numerator coefficients are the coefficients of x[n − k] in equation (5.22) and denominator coefficients are the coefficients of y[n − k] in equation (5.22). Thus we can write the frequency response by inspection. Example 2: Consider an LTI system initially at rest described by the difference equation y[n] − ay[n − 1] = x[n], |a| < 1 The frequency response of the system is 1 1 − ae−jω We can use the inverse fourier transform to get the impulse response H(ejω ) =
h[n] = an u[n]
15