A. Basics of Discrete Fourier Transform
A.1. Definition of Discrete Fourier Transform (8.5)
A.2. Properties of Discrete Fourier Transform (8.6)
A.3. Spectral Analysis of Continuous-Time Signals Using
Discrete Fourier Transform (10.1, 10.2)
A.4. Convolution Using Discrete Fourier Transform (8.6, 8.7)
A.5. Sampling of Discrete-Time Fourier Transform (8.4, 8.5)
A.1. Definition of Discrete Fourier Transform
Let x(n) be a finite-length sequence over 0nN1. The discrete
Fourier transform of x(n) is defined as
(A.2) is called the inverse discrete Fourier transform.
A.1.1. Derivation of Inverse Discrete Fourier Transform
Let us derive (A.2) from (A.1). (A.1) is rewritten as
.1Nn0, kn
N
2
jexpX(k)
N
1
x(n)
1N
0k
.1Nk0, kn
N
2
jexpx(n)X(k)
1N
0n
Note that X(k) is a finite-length sequence over 0kN1.
x(n) can be reconstructed from X(k), i.e.,
(A.1)
(A.2)
1.Nk0 ,km
N
2
jexp)m(x)k(X
1N
0m
(A.3)
.)mn(k
N
2
jexp)m(xkn
N
2
jexp)k(X
1N
0k
1N
0m
1N
0k
Multiplying both the sides of (A.3) by exp(j2kn/N), 0nN1, and
then summing both the sides with respect to k, we obtain
(A.4)
Changing the order of the two summations on the right side of (A.4),
we obtain
.)mn(k
N
2
jexp)m(xkn
N
2
jexp)k(X
1N
0m
1N
0k
1N
0k
(A.5)
Since
,
nm 0,
nm ,N
)mn(k
N
2
jexp
1N
0k
(A.6)
.N)n(xkn
N
2
jexp)k(X
1N
0k
(A.7)
(A.2), the inverse discrete Fourier transform, is derived by dividing
both the sides of (A.7) by N.
A.1.2. Relation of Discrete Fourier Transform to Discrete-Time
Fourier Series
Let us assume that X(k) is the discrete Fourier transform of x(n),
x(n) is x(n) extended with period N, and X(k) is the discrete-time
Fourier series coefficient of x(n). Then, X(k) is equal to X(k) over
period 0kN1 multiplied by N, i.e.,
X(k)=NX(k), 0kN1. (A.8)
Figure A.1 illustrates this relation.
we obtain
……
n
x(n)
n
x(n)
k
X(k)
k
X(k)
……
Figure A.1. Relation to Discrete-Time Fourier Series.
0 0
0 0
A
NA
A.1.3. Relation of Discrete Fourier Transform to Discrete-Time
Fourier Transform
We assume that X(k) and X() are the discrete Fourier transform
and the discrete-time Fourier transform of x(n), respectively. Then,
X(k) equals the samples of X() over period [0, 2) at interval 2/N,
i.e.,
.1Nk0, k
N
2
XX(k)
(A.9)
Figure A.2 illustrates this relation.
n
x(n)
X()
…
Figure A.2. Relation to Discrete-Time Fourier Transform.
k
X(k)
…
0 2
0
0
If N is too small, X(k) may not reflect X() well.
Example. Assume
x(n)=1, 0nM1. (A.10)
(1) Find X(k), the N-point discrete Fourier transform of x(n), where
NM.
(2) Find X(), the discrete-time Fourier transform of x(n). If N=M,
does X(k) reflect X() well?
Example. The sampling interval of x(n) is 2·104 second. Find the
length range of the discrete Fourier transform such that the sampling
interval of X(k) is 20 radians/second at the most.
A.2. Properties of Discrete Fourier Transform
A.2.1. Linearity
If x1(n)X1(k) and x2(n)X2(k), then
a1x1(n)+a2x2(n)a1X1(k)+a2X2(k), (A.11)
where a1 and a2 are two arbitrary constants. (A.11) holds when x1(n)
and x2(n) have the same length initially or after zero padding.
A.2.2. Circular Shift
Assume that x(n) is a finite-length sequence over 0nN1. The
circular shift of x(n) by n0 is defined as
x(nn0)=x(nn0), 0nN1, (A.12)
where x(n) is x(n) extended with period N.
The circular shift can be carried out in the following steps (figure
A.3).
(1) Extend x(n) with period N to obtain x(n).
(2) Shift x(n) by n0 to obtain x(nn0).
(3) Limit x(nn0) to period 0nN1 to obtain x(nn0).
m0 1 2
x(n)
3
… …
m0 1 2
x(n)
3
m0 1 2 3
… …
m0 1 2
x(n2)
3 4
m0 1 2 3
Figure A.3. Circular Shift.
x(n2)
x(n2)
The circular shift can also be carried out by shifting and wrapping
m0 1 2 3
x(n2)
5
x(n) (figure A.3).
If x(n)X(k), then
,kn
N
2
jexp)k(X)nn(x 00
(A.13)
where n0 is an arbitrary integer.
If x(n)X(k), then
),kk(Xnk
N
2
jexp)n(x 00
(A.14)
where k0 is an arbitrary integer.
A.2.3. Reversal
If x(n)X(k), then
x(n), 0nN1X(k), 0kN1, (A.15)
where x(n) and X(k) are, respectively, x(n) and X(k) extended with
period N.
A.2.4. Conjugation
If x(n)X(k), then
x*(n)X(k)*, 0kN1, (A.16)
where X(k) is X(k) extended with period N.
From (A.16), the following conclusions can be drawn:
(1) Im[x(n)]=0 X(k)=X(k)*, 0kN1.
(2) Re[x(n)]=0 X(k)=X(k)*, 0kN1.
If x(n)X(k), then
x(n)*, 0nN1X*(k), (A.17)
where x(n) is x(n) extended with period N.
From (A.17), the following conclusions can be drawn:
(1) Im[X(k)]=0 x(n)=x(n)*, 0nN1.
(2) Re[X(k)]=0 x(n)=x(n)*, 0nN1.
Example. X(k) is the 512-point discrete Fourier transform of x(n).
X(11)=2000(1+j). Find X(501).
(1) x(n) is real.
(2) x(n) is purely imaginary or 0.
A.2.5. Symmetry
If x(n)X(k), then
X(n)Nx(k), 0kN1, (A.18)
where x(n) is x(n) extended with period N.
If x(n)X(k), then
X(n)/N, 0nN1x(k), (A.19)
where X(k) is X(k) extended with period N.
A.2.6. Circular Convolution (Section A.4)
A.2.7. Parseval’s Equation
If x(n)X(k), then
.)k(X
N
1
)n(x
1N
0k
2
1N
0n
2
(A.20)
A.3. Spectral Analysis of Continuous-Time Signals Using Discrete
Fourier Transform
A.3.1. Frame
The discrete Fourier transform can be used in the spectral analysis
of a continuous-time signal (figure A.4).
xc(t)
C/D DFT
x(n) y(n)
w(n)
Figure A.4. Spectral Analysis of a Continuous-
Time Signal Using Discrete Fourier Transform.
Y(k)
Each step is discussed as follows (figure A.5).
(1) Sampling. Let Xc() be the continuous-time Fourier transform
of xc(t), X() be the discrete-time Fourier transform of x(n) and T be
the sampling interval. Then, X() equals Xc() extended with period
2/T, divided by T and then expressed in terms of , i.e.,
.
T
m2
X
T
1
X
m
c
(A.21)
Xc()
0
A
X()
……
0 2
A/T
Y()
……
0 2
k
Y(k)
N10
Figure A.5. Illustration of Xc(), X(), Y() and Y(k).
(2) Windowing. Assume that W() and Y() are the discrete-time
Fourier transforms of w(n) and y(n), respectively. Then, Y() equals
the periodic convolution of X() and W() divided by 2, i.e.,
.d)(W)(X
2
1
)(Y
2
(A.22)
(3) Discrete Fourier Transform. Assume that Y(k) is the N-point
discrete Fourier transform of y(n). Then, Y(k) equals the samples of
Y() over period [0, 2) at interval 2/ N, i.e.,
.1Nk0, k
N
2
Y(k)Y
(A.23)
A.3.2. Effects of Windowing
Let us investigate the effects of the above windowing further.
Let xi(n)=Aiexp(jin) be a frequency component of x(n). Then, the
discrete-time Fourier transform of xi(n) is
(A.24).)m2(A2)(X
m
iii
Assume that yi(n) is the component of y(n) obtained by windowing
xi(n), i.e., yi(n)=xi(n)w(n). Then, yi(n) has the discrete-time Fourier
transform
Yi()=AiW(i). (A.25)
That is, Yi() equals W() shifted by i and multiplied by Ai.
From (A.24) and (A.25), we see that compared with Xi(), Yi()
has the following features (figure A.6).
1. Yi() has a distribution band. (1) The width of the distribution
band equals the width of the main lobe of W(). In order for Yi() to
have a narrow distribution band, W() should have a narrow main
lobe. (2) The width of the main lobe of W() depends on the shape
and the length of w(n). A longer w(n) results in a narrower main lobe.
Xi()
n
xi(n)
w(n)
W()
n
yi(n)
n
Figure A.6. Differences between Xi() and Yi().
Yi()
i i i+
i i+
E
Ai
AiE
i
…
……
…
… …
2Ai
… …
2. Yi() has leakages. (1) The relative amplitudes of the leakages
equal the relative amplitudes of the side lobes of W(). For Yi() to
have leakages of small relative amplitudes, W() should have side
lobes of small relative amplitudes. (2) The relative amplitudes of the
side lobes of W() depend on the shape of w(n) only.
A.3.3. Windows
The rectangular window is defined as
.
otherwise ,0
1Nn0 ,1
)n(w
(A.26)
The Bartlett window is defined as
.
otherwise ,0
1Nn1)/2(N ),1N/(n22
2/)1N(n0 ),1N/(n2
)n(w
(A.27)
The Hann window is defined as
.
otherwise ,0
1Nn0 ,
1N
n2
cos5.05.0
)n(w
(A.28)
The Hamming window is defined as
.
otherwise ,0
1Nn0 ,
1N
n2
cos46.054.0
)n(w
(A.29)
.
otherwise ,0
1Nn0 ,
1N
n4
cos08.0
1N
n2
cos5.042.0
)n(w
(A.30)
The above windows are illustrated in figure A.7.
The Blackman window is defined as
Figure A.7. Shapes of Commonly Used Windows.
Table A.1. Features of Commonly Used Windows.
Shape of
Window
Width of
Distribution Band
Peak Relative
Amplitude of Leakages
Rectangular 4/N 13 dB
Bartlett 8/(N1) 25 dB
Hann 8/(N1) 31 dB
Hamming 8/(N1) 41 dB
Blackman 12/(N1) 57 dB
Table A.1 gives the features of these windows. It can be seen that
when the length of the window is fixed, a narrow distribution band
corresponds to leakages of large relative amplitudes, and therefore
there exists a tradeoff between the width of the distribution band and
the relative amplitudes of the leakages.
The Kaiser window is defined as
.
otherwise 0,
1Nn0 ,
)(I
1
1N
n2
1I
)n(w
0
2
0
(A.31)
Here I0(·) is the zero-order modified Bessel function of the first kind
and is a shape parameter.
A.4. Convolution Using Discrete Fourier Transform
A.4.1. Definition of Circular Convolution
Suppose that x1(n) and x2(n) are two finite-length sequences over
0nN1, and x1(n) and x2(n) are x1(n) and x2(n) extended with
period N, respectively. The circular convolution of x1(n) and x2(n) is
defined as the periodic convolution of x1(n) and x2(n) over a period
0nN1, i.e.,
1,Nn0 ,m)(nx(m)x(n)x(n)x
Nm
2121
(A.32)
which is also written as
1.Nn0 ,m)(nx(m)x(n)x(n)x
1N
0m
2121
(A.33)
Several points should be noted about the circular convolution:
(1) x1(n) and x2(n) should have the same length initially or after
zero padding to carry out the circular convolution.
(2) The circular convolution possesses the commutative property,
the associative property and the distributive property.
The circular convolution can be carried out in the following steps.
(1) Extend x2(m) with period N to obtain x2(m).
(2) Reflect x2(m) about the origin to obtain x2(m).
(3) Shift x2(m) by n to obtain x2(nm). This is equivalent to the
shifting and the wrapping of x2(m), 0mN1.
(4) Calculate the circular convolution at n.
Example. Find the circular convolution of the two sequences in the
following table.
n 0 1 2 otherwise
x1(n) 0 1 0 0
x2(n) 3 2 1 0
A.4.2. Circular Convolution Using Discrete Fourier Transform
If x1(n)X1(k) and x2(n)X2(k), then
).k(X)k(X)n(x)n(x 2121
(A.34)
).k(X)k(X
N
1
)n(x)n(x 2121
(A.35)
If x1(n)X1(k) and x2(n)X2(k), then
Figure A.8. Circular Convolution Using Discrete Fourier Transform.
DFT
IDFT
x1(n)
DFTx2(n)
)n(x)n(x 21
(A.34) shows that the circular convolution can be carried out using
the discrete Fourier transform (figure A.8).
A.4.3. Convolution Using Discrete Fourier Transform
In this section, we will study the relation between convolution and
circular convolution and consider how to carry out convolution using
the discrete Fourier transform.
Let x1(n) and x2(n) be two finite-length sequences over 0nN11
and 0nN21, respectively. If f(n) and g(n) are the convolution and
the N-point circular convolution of x1(n) and x2(n), respectively, then
we have
That is, g(n) equals f(n) extended with period N and limited to period
0nN1. Since f(n) is a finite-length sequence over 0nN1+N22,
we can draw the following conclusions. If N N1+N21, g(n) equals
f(n). Otherwise, aliasing occurs. The relation between f(n) and g(n) is
illustrated in figure A.9.
1.Nn0 ,)iNn(f)n(g
i
(A.36)
0
N1+N22
m
N
…
…
0
N1+N22
m
0
N1+N22
m
Figure A.9. Relation between Convolution and Circular Convolution.
NN1+N21
0
N1+N22
m
N
… …
0
N1+N22
m
N
本文档为【A. Basics of Discrete Fourier Transform】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。