数字信号处理习题汇编 (3)

第三部分：离散傅里叶变换DFT

Discrete Fourier Transform

1. DFT

Given an N-point sequence x[n] defined for 0 ≤ n ≤ N-1, its N-point DFT X[k] is defined by

X[k]x[n]W------Remember!

knNn02NjN1where WNe

The inverse DFT is defined by x[n]1NN1X[k]Wk0knN------Remember!

Physical meaning:

DFT X[k] is an N-point sequence obtained by N-point equally-spaced sampling the DTFT X(ejω) over 0 ≤ ω ≤ 2π.

Time-domain aliasing (Emphasis!)

Remember the conclusion:

A time-domain sampling corresponds to a periodically extension in the frequency-domain, a frequency-domain sampling corresponds to a time-domain periodically extension with period N (N is the number of points in the frequency-domain).

This can be expressed using the formula:

 y[n]x[nmN] (Emphasis!)

mwhere, N is the number of points in the frequency-domain, y[n] is the inverse DFT of Y[k] obtained by sampling the DTFT of x[n] by N points.

From the conclusion, we can readily determine the inverse DFT. For example, given a sequence x[n]={1 1 1 1 1 1 1} with DTFT X(ejω), if we sample X(ejω) by 8 points to obtain an 8-point sequence Y[k], then the inverse DFT of Yk] is y[n]={1 1 1 1 1 1 1 0}. Otherwise, if we sample X(ejω) by 4 points to obtain a 4-point sequence Y[k], then the inverse DFT of Y[k] is y[n]={2 2 2 1}

2. Circular Shift and Circular Convolution

Given a length-N sequence g[n], its n0-point circular shifted version is defined by

gc[n]g[nn0N]

Note:

Comparing to the time-shift defined in the early, there are two differences: 1. The circular shifted version gc[n] is always kept in the range 0≤n≤N-1.

2. The circular shift includes a modulo operation.

Given two length-N sequences g[n] and h[n] defined for 0≤n≤N-1, their N-point circular convolution is defined by

yc[n]g[m]h[nm]----Remember!

Nm0N1Note:

Comparing to the linear convolution, there are two differences:

1. The length of the circular convolution gc[n] is identical to the length of g[n] and h[n]. 2. The circular convolution requires that g[n] and h[n] have the same length. 3. DFT properties

(a) Circular time-shifting g[nn0N]WNknG[k]

0(b) Frequency-shifting y[n]WNkng[n]Y[k]G[kk0N]

0(c) N-point circular convolution yc[n]g[n]h[n]Y[k]H[k]G[k]

(d) Modulation

(e) Symmetry properties of the DFT of a complex sequence

(f) Symmetry properties of the DFT of a real sequence (Emphasis) Requirement:

You must be able to develop the above properties. 4. DFT computation of real sequences (Emphasis)

Given two length-N real sequences g[n] and h[n], we can use an N-point DFT computation to obtain the N-point DFTs of g[n] and h[n] by using the following identities

G[k]12X[k]X*[Nk]12X[k]12jX*[kN]

H[k]12jX[k]X*[Nk]X[k]X*[kN]

where X[k] is the N-point DFT of x[n]=g[n]+jh[n].

Direction:Fill the best answer into the bracket for each of the following sentences.

1. Given a 16-point real sequence x[n], its 16-point DFT is denoted as X[k], it is known that X[13] = 2 + j3, then X*[3] = ( 2 + j3 ).

说明：DFT的性质。实序列的DFT的共轭对称性：X[k] ＝X*[N-k]，或X[N-k] ＝X*[k]。

2. The linear convolution of g[n] and h[n] is yL[n] = {1, 2, 3, 4, 5, 6}, The 4-point circular convolution of g[n] and h[n] is yC[n] = ( {6, 8, 3, 4} ). 说明：利用线性卷积与循环卷积之间的关系。

3. Given two N-point real sequences g[n] and h[n], we construct a complex sequence x[n] = g[n] + jh[n]. Assume that the N-point DFT of x[n] is known and denoted by X[k], then we can determine the N-point DFTs G[k] and H[k] from X[k], and G[k] = ( ).

说明：本题是关于如何提高DFT的运算效率的问题，也就是教材第三章的3.5节的3.5.1小节。

4. Let X[k] be the 8-point DFT of an 8-point real sequence x[n], and it is known thatX[0] = 12, X[1] = -1 +j3, X[2] = 3 + j4, X[3] = 1 – j5, X[4] = 4, X[5] = 1 + j5, X[7] = -1 – j3.then X[6] = ( 3 - j4 ).

说明：见第6题。

5. The linear convolution of g[n] and h[n] is yL[n] = {1, 1, 1, 1, 1, 1}, The 4-point circular convolution of g[n] and h[n] is yC[n] = ( ).

6. Given two N-point sequences x[n] and h[n], their linear convolution is identical to their L-point circular convolution if ( ).

Exercises:

1. Given a discrete-time sequence x[n] = u[n] – u[n-8] with its DTFT X(ej).

a. For the DFT sequence X1[k] obtained by sampling X(ej) at uniform intervals of π/5 starting from =0, determine the IDFT x1[n] of X1[k]. Can you recover x[n] from x1[n]? b. For the DFT sequence X2[k] obtained by sampling X(ej) at uniform intervals of π/3 starting from =0, determine the IDFT x2[n] of X2[k]. Can you recover x[n] from x2[n]?

2. Let x[n], 0≤n≤N-1, be a length-N real sequence with an N-point DFT X[k], 0≤k≤N-1.

a. Show that X[N-k] = X*[k].

b. Show that X[0] is real.

c. If N is even, show that X[N/2] is real.

3. A 316-point DFTX[k] of a real-valued sequence x[n] has the following DFT samples: X[0] = 3 + jα, X[17] = 1.5, X[k1] = j2.3, X[k2] = 4.2, X[110] = -j1.7, X[158] = 13 + jβ, X[k3] = γ + j1.7, X[179] = 4.2 + jδ, X[210] = ε – j2.3, and X[k4] = 1.5. Remaining DFT samples are assumed to be of zero value.

a. Determine the values of the indices k1, k2, k3, k4. b. Determine the values of α, β, γ, δ, and ε. c. What is the dc value of x[n]? Solution:

This problem will use the symmetry property of the DFT of a real sequence.

First, we assume that the DFT of x[n] is denoted as X[k], then X[k] must be the conjugate symmetric sequence, i.e., X[k] satisfies the relation

X[k] = X*[<-k>N] = X*[N-k]

or X*[k] = X [<-k>N] = X [N-k] where N = 316 Based on this, we have:

X [316-17] = X*[17] = X[299] = 1.5 Eq.(1) X[ k1] = j2.3 Eq.(2) X [316-k2] = X*[ k2] = 4.2 Eq.(3) X [316-110] = X*[110] = X[206] = j1.7 Eq.(4)

X [316-158] = X*[158] = X[158] =13+ jβ Eq.(5) X [ k3] = γ+j1.7 Eq.(6) X [316-179] = X*[179] = X[137] = 4.2+jδ Eq.(7) X [316-210] = X*[210] = X[116] = ε+j2.3 Eq.(8) X [ k4] = 1.5 Eq.(9) (a) and (b)

From Eq.(1) and (9), we see X[299] = X[ k4] = 1.5

So k4 = 299

From Eq.(2) and (8), we see

X[ k1] = j2.3, X[116] = ε+j2.3 we can conclude that k1 = 116 and ε = 0

From Eq.(3) and (7), we see

X[ k2] = 4.2 and X[137] = 4.2+jδ we can conclude that k2 = 137 and δ = 0

From Eq.(4) and (6), we see

X[206] = j1.7 and X[ k3] = γ+j1.7 we can conclude that k3 = 206 and γ = 0 From Eq.(5),

X*[158] = X[158] =13+ jβ, so β = 0 (c) What is the dc value of x[n]?

N1FromX[k]x[n]W, we have

knNn0N1X[0]x[n]3n0j

Because that x[n] is a real sequence, so α = 0, thus

N1x[n]3

n0The dc value of x[n] is then equal to

1NN1n0x[n]3316

This problem tells us, if x[n] is real-valued, then its DFT must be a conjugate symmetric sequence. In this case, if X[k] is not complete, maybe we can determine the unknown DFT samples of X[k] by the use of the conjugate symmetry property.

4. A sequence x[n] is generated by sampling a real continuous-time signal xa(t) with sampling frequency FT = 1000Hz. Its 16-point DFT X[k] is:

X[k] =[0 -j4 -j4 -j4 -j4 0 0 0 0 0 0 0 j4 j4 j4 j4]

k1,2,3,4j4,k12,13,14,15 Or expressed as X[k]j4,0,otherwiseAssume that the time-domain and the frequency-domain sampling processes have no

aliasing.

(1). Determine the IDFT x[n] of X[k].

(2). Determine the expression of the continuous-time signal xa(t).

5. Let xa(t) be a bandlimited periodic continuous-time signal with fundamental period T=2s. A discrete-time sequence x[n] is obtained by sampling xa(t) at FT = 10Hz with no aliasing. Let X[k] denote the DFT of x[n]. The plots of xa(t) and x[n] over one period are depicted in Figure a and b. Figure c shows the magnitude of DFT X[k].

a. How many sinusoidal frequency components are there in x[n]? What are the corresponding frequencies ?

b. How many sinusoidal frequency components are there in xa(t)? What are the corresponding frequencies ?

湛柏明 2012-12-7