离散傅里叶变换

篇一：离散傅里叶变换性质证明

1. ax[n]?by[n]?aX(ej?)?bX(ej?) Proof:

?

?(ax[n]?by[n])e

??

??j?n?

?j?n?a?x[n]e

???b?y[n]e??

j??j?n ?aX(ej?)?bX(e)

2. (1)x[n?nd]?X(e

Proof:

?j?)e?j?nd

?

n???x[n?nd]e

??j?n

??

n???x[n?nd]e

j??j?(n?nd).e?j?n ?X(e)e?j?nd

(2) e

Proof:

?j?0nx[n]?X(ej(???0)) ?

?

n???ej?0nx[n]e?j?n??n???x[n]e?j(???0)n?X(ej(???0))

3. x[?n]?X(e?j?)

Proof:

??

?

n???x[?n]e?j?n??n???x[?n]ej?(?n)?X(e?j?) if x[n] is real X(e?j?)=X(e*j?) 4. nx[n]?j

Proof:

?dX(ed?j?) X(e

?j?)?j??n???x[n]e??j?ndX(e

d?)

j??)?n????(?jn)x[n]e

nx[n]e?j?n ?jdX(e

d???

n????j?n

?

5. (1)?

n???|x[n]|?212???

??|X(ej?)|d? 2

Proof:

1

2?

???|X??(ej?)|d?21

2?

1

2?

1

2?

?????X(e?j?)Xe(?j?d)???? ???n??????x[ne]?j?n?n???xn[e]d?*j?n? ??n???

2??|x[n]|d?1

2??2??

n???

?|x[n]|

2???d???

n???

?|x[n]|?

(2) ?

n???x[n]y[n]?*12??

??X(ej?)Y(e*j?)d? Proof:

1

2?

?????X(e?j?)Y(e*j?)d?1

2?

1

2?

????X(e?j?)Y(e?j?)d????1??n????

*??x[n]e?j?n?n???y[n]e*j?nd?

2?

???n????

*??x[n]y[n]d?1

2????

n???

?x[n]y[n]

*??n?????d???

n???x[n]y[n]

6. x[n]*y[n]?X(e

Proof: j?)Y(ej?)

?

?

n???{x[n]*y[n]}e

?j?n

?

??n????{x[i]y[n?i]}e??j?n

y[n?i]e?j?(n?i)?

n???x[i]e

j??j?i?n?i????X(e)Y(ej?)

7. x[n]y[n]?

Proof: 1

2?

??12?????X(ej?)Y(e（j???）)d? ???[?12?????X(ej?)Y(e1

2?（j???）)d?]d?12?

1

2?

1

2?????X(ej?)ej?n???Y(e（j???）)d?d?? ????X(ej?)ej?ny[n]d? ???

??X(ej?)ej?nd?.y[n]

?x[n].y[n]

篇二：离散傅里叶变换性质

数 字 信 号 处 理

实验名称：实验日期：姓 名：学 号：实验报告

离散傅里叶变换的性质 2011年11月16日 许鹏 090240229

哈尔滨工业大学（威海）

一、实验目的

验证离散傅里叶变换的性质，包括线性特性、时移特性、频移特性、对称性和循环卷积等性质

二、实验原理

1. 线性特性

DFT[ax1(n)?bx2(n)]?aX1(k)?bX2(k)

2. 时移特性

DFT[x(n?m)]?W?kmX(k)DFT[x(n?m)]?WX(k)

3. 频移特性

km

nl

IDFT??X?k?l????IDFT??X?k???WN

4. 对称性

设由x(n)开拓成的周期序列为 则xp

xp?n?

?n??xpe?n??xpo?n?

1*

??xn?x??pp?N?n?? ?21*

?xn?x奇序列xpo?n?????pp?N?n??

2?

偶序列xpe?n??将xpe

?n? 和xpo?n? 截取主周期，分别得

xpet?n??xpe?n?RN?n? xpot?n??xp?on?R?N?n则x

?n??xp?n?RN?n??xpet?n??xpot?n?

x(n)序列的实部和虚部的离散立叶变换

DFTRe??x?n????Xpet?k? DFTjIm??x?n????Xpot?k?

??

??

X?(k)?X(?k)?X(N?k)XR(k)?XR(?k)?XR(N?k)XI(k)??XI(?k)??XI(N?k) X(k)?X(N?k)arg?X(k)???arg?X(?k)?

5. 循环卷积

x3(n)?x1(n)x2(n)?X3(k)?

1

X1(k)?X2?k? N

有限长序列线性卷积与循环卷积的关系 X1(n)和x2(n)的线性卷积：

x3(n)?

m???

?x(m)x(n?m)??x(m)x(n?m)

1

2

1

2

m?0N?1

?N1?1

??x1(m)x2(n?m)

m?0

将X1(n)和x2(n)开拓成以N为周期的周期序列

xp1(n)?

r???

?x(n?rN) x

1

?

p2

(n)?

q???

?x(n?qN)

2

?

则它们的周期卷积为

xp4(n)??xp1(m)xp2(n?m)

m?0

N?1

??x1(m)xp2(n?m)

m?0

N?1

??x1(m)?x2(n?m?qN)

m?0

q???

N?1?

?N?1?????x1(m)x2(n?qN?m)? q????m?0??

?

q???

?x(n?qN)

3

?

X1(n)和x2(n)周期开拓后的周期卷积等于他们的线性卷积的的周期开拓。

三、实验内容和步骤

任取长度为N=8的随机实序列x1[n]，x2[n]，例如x1[n]=[1 3 5 3 6 8 3 9]，x2[n]=[2 4 3 6 7 9 0 2 ]，和长度为N=8的随机复序列x3[n]，x4[n]，例如x3[n]=[1+2j 3+4j 5+3j 3+4j 6+j 8+2j 3+3j 9+2j]，x4[n]=[4+1j 6+4j 4+3j 3+4j 7+j 8+3j 3+4j 1+2j]，采用MATLAB编程验证傅里叶变换的如下性质。 1. 线性特性

a. 给出序列 x1[n]的傅里叶变换X1[k]，并画出其幅度谱和相位谱 b. 给出序列 x2[n]的傅里叶变换X2[k] ，并画出其幅度谱和相位谱

c. 给出序列 Z=2*X1[k]+6*x2[k],并与序列2*x1[n]+6*x2[n]的傅里叶变换比较， 用matlab编程画出的图形如下图所示：

x1 fft X1[k]幅频特性

x1 fft X1[k]相频特性

x2 fft X2[k]的幅频特性

x2 fft X2[k]相频特性

02468Z=2*X1[k]+6*X2[k]的幅频特性

02468Z=2*X1[k]+6*X2[k]的相频特性

02468z=2*x1[n]+6*x2[n] fft的幅频特性

02468z=2*x1[n]+6*x2[n] fft的相频特性

由图可以发现，Z=2*X1[k]+6*x2[k]与序列z=2*x1[n]+6*x2[n]的傅里叶变换相同。验证了线性特性

DFT[ax1(n)?bx2(n)]?aX1(k)?bX2(k)。

2. 时移特性

给出序列x1[n]右移3 位后的傅里叶变换的幅度谱和相位谱，并和原始序列的幅度谱 和相位谱相比较

Matlab编程画出图形如下：

x1的傅里叶变换X[k]的幅频特性

x1的傅里叶变换X[k]的相频特性

02468

02468

移位序列xc的傅里叶变换的幅频特性0

2

4

6

8

移位序列xc的傅里叶变换的相频特性0

2

4

6

8

Wn3k*X[k]幅频特性

Wn3k*X[k]相频特性

2468

02468

由图看出，移位序列xc的傅里叶变换的幅度谱相位谱与原序列傅里叶变换的幅度谱相位谱并不相同，而是与原序列傅里叶变换乘以Wn3k后的结果相同。由此可以验证时移性质

DFT[x(n?m)]?W?kmX(k)DFT[x(n?m)]?WX(k)

3. 频移特性

km

。

设DFT[x(n)]=X (k)，比较 x(n) *exp( j * 2pi/N *l *n)的DFT与X (k)的不同. a. l= +2 b. l=‐3

篇三：第5快速离散傅里叶变换

第5章 快速傅里叶变换(FFT)

快速傅里叶变换（FFT）是根据计算量的最小化原理来设计和实施离散傅里叶变换(DFT)计算的方法。1965年，库利（T.W.Cooley）和图基（J.W.tukey）发表了著名的《计算机计算傅里叶级数的一种算法》论文。从此掀起了快速傅里叶变换计算方法研究的热潮。各种快速、高效的离散傅里叶变换计算方法伴随着DSP技术的发展不断出现，并促进了DSP技术的发展。快速傅里叶变换（FFT）的出现，实现了快速、高效的信号分析和信号处理，为离散傅里叶变换(DFT)的广泛应用奠定了基础。

本章主要讲述快速傅里叶变换的原理和典型应用。按照快速傅里叶变换方法的引入、时域抽取基2FFT算法、频域抽取基2FFT算法、高效率计算FFT的方法的探讨、离散傅里叶反变换的FFT算法、线性调频Z变换算法、典型FFT算法的MATLAB实现的顺序进行讲述。

本章是数字信号处理的重点内容之一，其中的时域抽取基2 FFT算法和典型FFT算法的MATLAB实现是实现离散傅里叶变换(DFT)走向实用化的关键性技术。

5.1 快速傅里叶变换方法的引入

5.1.1离散傅里叶变换(DFT)的计算

按照公式4.3.1，设x(n)是一个长度为M的有限长序列， 则定义x(n)的N点离散傅里叶变换为

N?1n?0kN

X(k)?DFT[x(n)]??x(n)WN 0?k?N?1

kn

02k(N?1)k

?x(0)WN?x(1)W?x(2)WN??x(N?1)WN (5.1.1)

按照公式5.1.1进行计算称为DFT的直接计算方法。为了统计不同DFT计算的工作量，

我们把2个复数的加法运算和乘法运算各称为1次复数运算；对于2个复数的1次复数的加法运算和乘法运算的计算工作量视为相等。因为专用的DSP处理器进行复数加法和乘法运算的速度和效率基本相同。 直接计算的工作量：

对于一个固定的k值：复数乘法N次；复数加法N-1次；小计2N-1次复数运算。

对于N个k值：复数乘法N次；复数加法N(N?1)次；共计N(2N?1)次复数运算。

2

可以看出，当N?10的时候，2N?1?2N，N点的DFT计算的工作量是2N。一8

般情况下，N?10000，DFT计算的工作量最少是2?10次复数运算。短时间内完成计算

2

N

任务是困难的。因为，N点的DFT计算的工作量是2NN点的DFT计算的工作量是，

22

减少DFT计算的点数N可以减少DFT的计算量。减少运算量是提高运算速度的好方法。 5.1.2减少DFT计算量的方法

2

2

k

减少DFT的计算量的主要途径是利用WN的性质和计算表达式的组合使用，其本质是

减少DFT计算的点数N以便减少DFT的计算量。

k

的性质： WN

k?mNk（1）全周期对称性：WN（m是整数） (5.1.2) ?WN

（2）半周期反对称性：WN证明： W

k?mN

N

k?

N2

k

(5.1.3) ??WN?j2?kN

?e

?e

?j

2?

(k?mN)N

?ee

?j

2?mNN

（m是整数）

?j

2?kN

e?j2?m

?e

k ?WN

?j

2?kN

2?kN

2?N2N

WN

k?

N2

?e

?j

2?N(k?)N22?

kN

?e

?j

e

?j

?e

?j

e?j?

??ek ??WN

证毕。

k

利用WN的性质把DFT的表达式进行化简是减少计算量工作的第一步，DFT的表达式

?j

2?

kN

中的同类项合并是减少计算量工作的关键性一步。因为同类项的计算只需要进行一次，而其它的同类项就不需要重复计算了。这样就能有效地减少运算量。

如何减少运算量，提高运算速度？我们通过一个例题进行说明。 例题5.1.1 计算N?4，DFT[x(n)]。 解：X(k)?

?x(n)WN

n?0

N?1

kn

0k2k3k

?x(0)WN?x(1)WN?x(2)WN?x(3)WN 0?k?3

X(0)?x(0)W40?x(1)W40?x(2)W40?x(3)W40

X(1)?x(0)W40?x(1)W41?x(2)W42?x(3)W43 (5.1.4) X(2)?x(0)W40?x(1)W42?x(2)W44?x(3)W46 X(3)?x(0)W40?x(1)W43?x(2)W46?x(3)W49

利用W

k?mNN

?W（m是整数）和WN

kN

k?

N2

k

的规律，对公式(5.1.4)进行优化，得??WN

到公式(5.1.5)。

X(0)?x(0)W40?x(1)W40?x(2)W40?x(3)W40

X(1)?x(0)W40?x(1)W41?x(2)W40?x(3)W41 (5.1.5) X(2)?x(0)W40?x(1)W40?x(2)W40?x(3)W40 X(3)?x(0)W40?x(1)W41?x(2)W40?x(3)W41

我们对公式(5.1.5)进行组合，得到公式(5.1.6)

X(0)?[x(0)?x(2)]W40?[x(1)?x(3)]W40 （a）

X(1)?[x(0)?x(2)]W40x(1)?x(3)]41 (b ) (5.1.6) X(2)?[x(0)?x(2)]W40?[x(1)?x(3)]W40 (c ) X(3)?[x(0)?x(2)]W441 (d )

我们对公式(5.1.6)进行分析，（a）式和(c ) 式的对应部分可以只计算一次；同理，（b）式和(d )式的对应部分可以只计算一次。计算量：复数加法8次，复数乘法4次，共计复数运算12次。

如果我们对公式(5.1.4)直接进行计算，计算量：复数加法12次，复数乘法16次，共计复数运算28次。

k

通过上述例题，我们发现，利用WN的性质和计算表达式的组合使用，可以大幅度减少

运算量，提高计算速度。其本质是减少DFT计算的点数N，以便减少DFT的计算量。例如公式(5.1.6)中的（a）式和(c ) 式的对应部分，相同的表达式只需要计算一次。公式(5.1.6) （a）式（b）式中的x(0)?x(2)和x(0)?x(2)就是计算x(0)和x(2)的2点的DFT；x(1)?x(3)和x(1)?x(3)就是计算x(1)和x(3)的2点的DFT；公式(5.1.4) （a）式（c）式中的

[x(0)?x(2)]W40?[x(1)?x(3)]W40和[x(0)?x(2)]W40?[x(1)?x(3)]W40就是计算[x(0)?x(2)]W40和[x(1)?x(3)]W40的2点的DFT。在这里，我们对公式5.1.6的解释是从对x(n)的抽取、推导到X(k)的顺序进行的，其算法表现称为时域抽取基2FFT算法。计算

表达式的组合使用看起来复杂，但是有规律可循。

请注意：公式(5.1.6)中的计算顺序方法不是唯一的，这样就产生了不同的FFT计算方法。最基本的FFT计算方法是时域抽取基2FFT算法、频域抽取基2FFT算法。其它的FFT计算方法都可以从时域抽取基2FFT算法变化得到，以便满足不同的工作需求。对此，我们分别进行讲述。

5.2 时域抽取基2 FFT算法

N点DFT的计算量和N成正比，减少参与DFT的点数N，就减少了DFT的计算量。N?2的计算是最简化的DFT计算。把N点DFT的计算转化成若干2点的DFT的计算，2点的DFT的输入是在时域n上抽取的，我们称之为时域抽取基2 FFT算法。

2

5.2.1时域抽取基2 FFT算法原理

M

设x(n)，0?n?N?1，N?2，M是正整数，取DFT[x(n)]。

X(k)?DFT[x(n)]??x(n)WN 0?k?N?1

kn

n?0

N?1

?

n取偶数N?12

?x(n)W

kn

N

?

n取奇数N?12n?0

?x(n)W

kn

N

??x(2n)WN

2kn

??x(2n)WN??x1(n)WN

n?0N?12

n?0N?12

??x(2n?1)WN

N?12

k(2n?1)

2kn

?WNk?x(2n?1)WN?WNk?x2(n)WN

n?0N?12

2kn

2kn

n?0N?12

2kn

??x1(n)WN

n?0

2

n?0N?12

kn

k?WN?x2(n)WN (5.2.1)

kn

n?0

2

令：

X1(k)??x1(n)WN 是长度为

kn

n?0

2

N

?12

N

的DFT (5.2.2) 2

N

的DFT (5.2.3) 2

N

的DFT。 2

X2(k)??x2(n)WN 是长度为

kn

n?0

2

N2

N?12

k

X(k)?X1(k)?WNX2(k) 0?k?N?1 (5.2.4)

考虑到WN

k?

k

，X1(k)和X2(k)是长度为??WN

k?NNN

X(k?)?X1(k?)?WN2X2(k?)

222

k

?X1(k)?WNX2(k) (5.2.5)

N

我们把公式(5.2.4)和公式(5.2.5)重写如下：

k

X(k)?X1(k)?WNX2(k) 0?k?

N

?1 (5.2.6) 2

NN

X(k?)?X1(k)?WNkX2(k) 0?k??1 (5.2.7)

22

这样，经过一次分解，X(k)、X(k?

NN

)、X1(k)、X2(k)都变成长度为的DFT。22

k

X1(k)、WNX2(k)的计算结果可以同时为公式(5.2.6)和公式(5.2.7)共用，节省了计算工作

量。

计算工作量的估算：直接计算共计2N次复数运算；经过一次分解，DFT的计算量

2

2?2(

N2

)次，复数加法N次，共计N(N?1)?N2次复数运算。节省一半计算量。 2

为了用图形表示DFT运算，我们定义2点DFT运算图，也称为蝶形图。

A A+BC A

X(k) X1(k)

k WN

A-BC

C B

X2(k)

5.2.1 蝶形图 5.2.2 2点DFT运算蝶形图

5.2.3 经过一次分解8点DFT运算图

与第一次分解相同，将x1(n)按奇偶分解成两个N/4长的子序列x11(n)和x12(n)，即

X1(k)??x1(n)WN 0?k?

kn

n?0

2

N?12

N?1 2

?

n取偶数

?

x1(n)WN

2

kn

?

n取奇数

?

x1(n)WN

2

kn

??x1(2n)WN

n?0

2

N?14

2kn

??x1(2n?1)WN

n?0

2

N?14

N?14

k(2n?1)

??x1(2n)WN

n?0

2

N?14

2kn

k?WN?x1(2n?1)WN

2n?0

2

2kn

??x11(n)WN

n?0

2

N?14

2kn

k?WN?x12(n)WN

2n?0

N?14kN12n?02kn

N?14

2kn

2

??x11(n)WN

n?0

4N?14n?0

N?14

kn

?W

?x(n)WN (5.2.8)

kn4

令：

X11(k)??x11(n)WN

4

是长度为

N

的DFT (5.2.9) 4

N

的DFT (5.2.10) 4

N

?1 (5.2.11) 2

X12(k)??x12(n)WN 是长度为

kn

n?0

4

N?14

k

X1(k)?X11(k)?WNX12(k) 0?k?

2

k根据WN的性质和长度为

N

的DFTX11(k)、X12(k)的周期性， 4

Nk

X1(k)?X11(k)?WNX12(k) 0?k??1 (5.2.12)

42

X1(k?

NNk

)?X11(k)?WNX12(k) 0?k??1 (5.2.13)

442

N

?1 (5.2.14) 4

同理得到：

k

X2(k)?X21(k)?WNX22(k) 0?k?

2

X2(k?

NNk

)?X21(k)?WNX22(k) 0?k??1 (5.2.15)

442

NN

点的DFT分解成2个点的DFT，如图5.2.424

这样，经过第二次分解，我们把1个所示。同理，2个

NN

点的DFT比1个点的DFT运算量减少一半。我们继续按照上述思42

路进行分解，一直分解到只有2点输入的DFT，如图5.2.5所示，完成了时域抽取基2FFT

的计算。

图5.2.4 经过二次分解8点DFT运算图

篇四：离散傅里叶变换

第3章 离散傅里叶变换

在第二章讨论了利用序列的傅里叶变换和z变换来表示序列和线性时不变系统的

?

?

?n

方法，公式分别为：X(z)?

?x(n)z

n???

和X(e

jw

)?

?x(n)e

n???

?jwn

。对于有限长序列，

也可以用序列的傅里叶变换和z变换来分析和表示，但还有一种方法更能反映序列的有限长这个特点，即离散傅叶里变换。这就是我们这一章要讨论的问题。离散傅里叶变换除了作为有限长序列的一种傅里叶表示法在理论上相当重要之外，而且由于存在着计算离散傅里叶变换的有效快速算法，因而离散傅里叶变换在各种数字信号处理的算法中起着核心的作用。这一章讨论的问题有：

1、 傅里叶变换的几种可能形式：至今学过很多种傅里叶变换形式，到底之间有什么

不 同，需要分析一下；

2、 周期序列的离散傅里叶级数(DFS)：通常的周期信号都可以表示成傅里叶级数，然

后根据傅里叶级数可以得到傅里叶变换；也就是说傅里叶级数与傅里叶变换之间有一定的关系；

3、 有限长序列的离散傅里叶变换(DFT)：这是我们的重点，我们会对其性质等作分析

讨论； 4、 DFT的应用：学习了这种傅里叶变换，怎么用？计划作一个实验。

3.1 傅里叶变换的几种形式

傅里叶变换就是建立以时间为自变量的"信号"与以频率为自变量的"频率函数"之间的某种变换关系。都是指在分析如何综合一个信号时，各种不同频率的信号在合成信号时所占的比重。

如连续时间周期信号f(t)?f(t?mT)，可以用指数形式的傅里叶级数来表示，可以分解成不同次谐波的叠加，每个谐波都有一个幅值，表示该谐波分量所占的比重。

T

?

傅里叶表示形式为：f(t)?

?F

n???

n

e

jn?t

?Fn?

1T

2

?

?

f(t)e

?jn?t

dt（Fn离散、衰减、

T2

非周期）。例如周期性矩形脉冲，其频谱为Fn?形。

?sin(n??/T)

T

n??/T

,n?0,?1,?。画出图

对于非周期信号，如门函数，存在这样的关系式：f(t)?

12?

?

?

jwt

?F(jw)e

??

dw?F(jw)?

?

??

f(t)e

?jwt

dt，时域非周期连续，频率连续非

周期。画出图形。

?

例如序列的傅里叶变换，变换关系为：X(e

?

jw

)?

?x(n)e

n???

?jwn

，

x(n)?

12?

?

??

X(e

jw

)e

jwn

dw，时域为非周期离散序列，频域为周期为2π的连续周期

函数。

以上三种傅里叶变换都是符合傅里叶变换所谓的是建立以时间为自变量的"信号"与以频率为自变量的"频率函数"之间的某种变换关系。不同形式是因为时间域的变量和频域的变量是连续的还是离散而出现的。这三种傅里叶变换因为总有一个域里是连续函数，而不适合利用计算机来计算。那么如果时间域里是离散的，而频域也是离散的，就会适合在计算机上应用了，那么傅里叶变换会是什么形式？见书上90页图形，可见时域和频域都对应为序列的形式。

3.2 周期序列的离散傅里叶级数（DFS）

回顾一下，对于周期信号，通常都可以用傅里叶级数来描述，如连续时间周期信

?

号f(t)?f(t?mT)，用指数形式的傅里叶级数来表示为f(t)?

?F

n???

n

e

jn?t

，可以看

成信号被分解成不同次谐波的叠加，每个谐波都有一个幅值，表示该谐波分量所占的比重。其中e

j?t

为基波，基频为Ω=2π/T（T为周期）。设~x(n)是周期为N的一个周期序

列，即~x(n)=~x(n?rN)，r为?a href="http://www.zw2.cn/zhuanti/guanyuwozuowen/" target="_blank" class="keylink">我庹弥甘问降母道镆都妒硎居Ω梦?/p>

~x(n)=

?

?

k???

~

Xke

jkw0n

，其中ω0=2π/N是基频，基频序列为e

jw0n

。下面来分析一下第

（K+rN）次谐波e表达式中，得到e

j(k?rN)w0n

和第（k）次谐波e

jkw0n

jkw0n

之间的关系。因为ω0=2π/N，代入

j(k?rN)w0n

=e，r为任意整数。这说明第（K+rN）次谐波能够被第

（k）次谐波代表，也就是说，在所有的谐波成分中，只有N个是独立的，用N个谐波

1

就可完全的表示出~x(n)。K的取值从0到N-1。这样~x(n)=

N

N?1

?

k?0

~Xke

jkw0n

，

1N

是为

了计算的方便而加入的。

~

下面来看看Xk如何根据~x(n)来求解。先来证明复指数的正交性：

N?1

?e

n?0

j(

2?N

)(k?r)n

?1,k?r?mN,m为整数

??，注意该表达式是对n求和，而0,其它?

表达式的结果取决于（k-r）的值。

1

在~x(n)=

N

N?1

N?1

?

k?0

~Xke

jkw0n

两边都乘以e?j(2?/N)rn，并且从n=0到n=N-1求和，得

到

?

n?0

?j(2?/N)rn~x(n)e?

N?1

?

n?0

1N

N?1

?X

k?0N?1

~

ek

j(2?/N)(k?r)n

交换求和顺序，再根据前面证明

的正交性结论可以得出：

?

n?0

~?j(2?/N)rn~x(n)e?X(r)，换一个变量，有

?j~~X(k)=?x(n)e

n?0

N?1

2?N

kn

，从X(k)的表达式可以看出X(k)也是周期为N的周期序列，

~~

即X(k)=X(k?N)。

1~x(n)=N

N?1

N?1

~~

?

k

?0

~Xke

jkw0?j~

x(n)eX(k)=?~

n?0

2?N

在上面的傅里叶级数对中，n和k的范围是从-∞到∞。

?j(2?/N)

为了表示的方便，引入变量WN?e，N表示周期。重新写上面的级数对。

讨论如下内容：

?j(2?/N)Nk21）WN?e，以N为周期。WN?1，WN?WN/2；

2）求和只对序列的一个周期的值进行，但求出的X(k)或~x(n)却是无限长的； 3）由~x(n)以N为周期推导出X(k)以N为周期；

4）对于周期序列~x(n)=~x(n?rN)，因为z变换不收敛，所以不能用z变换，但若取~则z变换是收敛的。X(z)?x(n)的一个周期，

~

X(z)?X(k)，而X(e

jw

~

~

x(n)z?~

n???

?

?n

，当取z?ej(2?/N)k时，

~

)=X(k)，这

)?X(z)|z?ejw，当w?(2?/N)k时，X(e

jw

相当于在ω=0到ω=2π的范围内，以2π/N的频率间隔在N个等间隔的频率上对傅里叶变换进行采样。

5）引入主值序列的概念，即序列在0~N-1区间的序列称为主值序列。 举例：

例1 求~x(n)的DFS系数。设~x(n)为周期冲激串~x(n)=

?

??(n?rN)，对于0≤n≤

r???

N?1

~~~N-1，x(n)=?(n)，可以求出X(k)=??(n)WNkn=1，即对于所有的k值，X(k)均相

n?0

同

~x(n)=

。

?

~x(n)

1N

表

N?1

示

1N

N?1

成级数形式为

??(n?rN)=

r???

?W

k?0

?knN

?

?

k?0

e

j(2?/N)kn

?1,n?rN=?。 ?0,其它

例2 设~x(n)的周期为N=10，在主值区间内，0≤n≤4时，~x(n)=1，在5≤n≤9时，

~x(n)~

X(k)=

4

=0。

4

kn10

画出

~x(n)

的图

~

形，则

?W

n?0

?

?

n?0

e

?j(2?/10)kn

=e

?j(4?k/10)

sin(?k/2)sin(?k/10)

，画出X(k)的幅值图。

~~~~~~~

X(0)=5，X(±1)=3.23，X(±2)=0，X(±3)=1.24，X(±4)=0，X(±5)=1，X(±

6)=0，X(±7)=1.24，X(±8)=0，X(±9)=3.23，这是一个周期内的值。设n取5~14，

~~~

即不是取主值周期，随便取一个周期，计算傅里叶级数X2(k)，得到的结果和在主值周期中的结果X(k)一样。下面计算有限长序列x(n)=?

?j5w?jw

~

~

?1,0?n?4?0,5?n?9

的傅里叶变换。

?4

?jwn

X(e

jw

)?

?x(n)e

n???

=?e

n?0

?jwn

=

1?e

1?e

=

e

?j(5/2)w?j(1/2)w

sin(5w/2)sin(w/2)

e

，如果将ω=2πk/10代入上式，则结果和X(k)一样。X(e

~

jw

)的

幅度一个周期图如下所示：

~

可以看出X(k)相当于在ω=0到ω=2π的范围内，以2π/10的频率间隔在10个等间隔的频率上对傅里叶变换进行采样。

例3 例题中得到这样一个结论，对于以N为周期的周期序列~任取一个周期求得x(n)，的傅里叶系数X2(k)与~（n=0~N-1）中求得的傅里叶系数X1(k)相同。x(n)在主值区间

?j~~现在已知~x(n)的周期为N，X1(k)=?x(n)e

n?0N?1

2?Nkn

~~

~

，X2(k)=

~

m2

?

n?m1

~x(n)e

?j

2?N

kn

，

m1=rN+n1，m2=rN+n1+N-1，0≤n1≤N-1，证明X1(k)=X2(k)。 证明：

~

X2(k)=

rN?n1?N?1

~

?

n?rN?n1

~x(n)

e

?j

2?N

kn

（令n-m=rN或m=n-rN）

篇五：离散傅里叶变换和快速傅里叶变换

实验报告

课程名称： 信号分析与处理 指导老师： 成绩：__________________

实验名称：离散傅里叶变换和快速傅里叶变换 实验类型： 基础实验 同组学生姓名：

第二次实验 离散傅里叶变换和快速傅里叶变换

一、实验目的

1.1掌握离散傅里叶变换（DFT）的原理和实现；

1.2掌握快速傅里叶变换（FFT）的原理和实现，掌握用FFT对连续信号和离散信号进行谱分析的方法。 1.3 会用Matlab软件进行以上练习。

二、实验原理

2.1关于DFT的相关知识

序列x(n)的离散事件傅里叶变换（DTFT）表示为

X(e)?

j?

n???

?x(n)e

?

?j?n

，

如果x(n)为因果有限长序列，n=0,1,...,N-1，则x(n)的DTFT表示为

j?

X(e)??x(n)e?j?n，

n?0

N?1

x(n)的离散傅里叶变换（DFT）表达式为

X(k)??x(n)e

n?0

N?1

?j

2?nkN

(k?0,1,...,N?1)，

序列的N点DFT是序列DTFT在频率区间[0,2π]上的N点灯间隔采样，采样间隔为2π/N。通过DFT，可以完成由一组有限个信号采样值x(n)直接计算得到一组有限个频谱采样值X(k)。X(k)的幅度谱为

X(k)?

2XR(k)?XI2(k)，其中下标R和I分别表示取实部、虚部的运算。X(k)的相位谱为

?(k)?XI(k)

。

XR(k)

2?

离散傅里叶反变换（IDFT）定义为

jnk1N?1

x(n)??X(k)eN

Nn?0

(n?0,1,...,N?1)。

2.2关于FFT的相关知识

快速傅里叶变换（FFT）是DFT的快速算法，并不是一个新的映射。FFT利用了e

?j2?nN

函数的周期性

和对称性以及一些特殊值来减少DFT的运算量，可使DFT

(来自:WWw.SmhaiDa.com 海达范文网:离散傅里叶变换)

的运算量下降几个数量级，从而使数字信号处

理的速度大大提高。

若信号是连续信号，用FFT进行谱分析时，首先必须对信号进行采样，使之变成离散信号，然后就可以用FFT来对连续信号进行谱分析。为了满足采样定理，一般在采样之前要设置一个抗混叠低通滤波器，且抗混叠滤波器的截止频率不得高于与采样频率的一半。

比较DFT和IDFT的定义，两者的区别仅在于指数因子的指数部分的符号差异和幅度尺度变换，因此可用FFT算法来计算IDFT。

三、实验内容与相关分析（共6道）

说明：为了便于老师查看，现将各题的内容写在这里——

题目按照3.1、3.2、...、3.6排列。每道题包含如下内容：题干、解答（思路、M文件源代码、命令窗口中的运行及其结果）、分析。其中“命令窗口中的运行及其结果”按照小题顺序排列，各小题包含命令与结果（图形或者序列）。

Ω

3.1 求有限长离散时间信号x(n)的离散时间傅里叶变换（DTFT）X(ej)并绘图。 ．．（1）已知x(n)??

?1?2?n?2n

；（2）已知x(n)?2

?0其他

0?n?10。

【解答】

思路：这是DTFT的变换，按照定义编写DTFT的M文件即可。考虑到自变量Ω是连续的，为了方便计算机计算，计算时只取三个周期[-2π,4π]中均匀的1000个点用于绘图。

理论计算的各序列DTFT表达式，请见本题的分析。 M文件源代码（我的Matlab源文件不支持中文注释，抱歉）： function DTFT(n1,n2,x)

%This is a DTFT function for my experiment of Signal Processing & Analysis. w=0:2*pi/1000:2*pi;%Define the bracket of omega for plotting. X=zeros(size(w));%Define the initial values of X. for i=n1:n2

X=X+x(i-n1+1)*exp((-1)*j*w*i);%It is the definition of DTFT. end

Amp=abs(X);%Acquire the amplification.

Phs=angle(X);%Acquire the phase angle (radian). subplot(1,2,1);

plot(w,Amp,'r'); xlabel('\Omega');ylabel('Amplification');hold on; %Plot amplification on the left. subplot(1,2,2);

plot(w,Phs,'b');xlabel('\Omega');ylabel('Phase Angle (radian)');hold off; %Plot phase angle on the right. end

命令窗口中的运行及其结果（理论计算的各序列DTFT表达式，请见本题的分析）： 第（1）小题

>> n=(-2:2); >> x=1.^n;

>> DTFT(-2,2,x);

Phase Angle (radian)

Amplificatio

n

??

第（2）小题

>> n=(0:10); >> x=2.^n;

>> DTFT(0,10,x);

图3.1.1在[-2π,4π]范围内3个周期的幅度谱和相位谱（弧度制）

432

Phase Angle (radian)

10-1-2-3-4

Amplificatio

n

??

图3.1.2在[-2π,4π]范围内3个周期的幅度谱和相位谱（弧度制）

【分析】

对于第（1）小题，由于序列x(n)只在有限区间（-2，-1，-，1，2）上为1，所以是离散非周期的信号。它的幅度频谱相应地应该是周期连续信号。事实上，我们可计算出它的表达式：

X(?)?

n???

?x(n)e?j?n?

??

n??2

?e?j?n

2

?e?5j?e2j?1?e?5j?

??X(?)?，可见幅度频谱拥有主极大?j??j?

1?e?e

??

和次极大，两个主极大间有|5-1|=4个极小，即有3个次级大。而对于它的相位频谱，则是周期性地在-π、0、π之间震荡。

对于第（2）小题，由于是离散非周期的信号。它的幅度频谱相应地应该是周期连续信号。而它的表达式：X(?)?

n???

?x(n)e

??

?j?n

??2e

n?0

10

?

?j?n

?

1?211e?11j?211??X(?)?，因此主极大之间只有?j??j?

1?2e?2e

|0-1|=1个极小，不存在次级大。而对于它的相位频谱，则是在一个长为2π的周期内有|11-1|=10次振荡。

而由DTFT的定义可知，频谱都是以2π为周期向两边无限延伸的。由于DTFT是连续谱，对于计算机处理来说特别困难，因此我们才需要离散信号的频谱也离散，由此构造出DFT（以及为加速计算DFT的FFT）。

3.2已知有限长序列x(n试分别采用DFT和FFT求其离散傅里叶变换X(k)的幅度、相位图。 【解答】

思路：按照定义编写M文件即可。 M文件源代码： i) DFT函数：

function DFT(N,x)

%This is a DFT function for my experiment of Signal Processing & Analysis. k=(0:N-1);%Define variable k for DFT.

X=zeros(size(k));%Define the initial valves of X. for i=0:N-1

X=X+x(i+1)*exp((-1)*j*2*k*pi/N*i);%It is the definition of DFT. end

Amp=abs(X);%Acquire the amplification.

Phs=angle(X);%Acquire the phase angle (radian). subplot(1,2,1);

stem(k,Amp,'.',’MarkerSize’,18); xlabel('k');ylabel('Amplification');hold on; %Plot amplification on the left. subplot(1,2,2);

stem(k,Phs,'*');xlabel('k');ylabel('Phase Angle (radian)');hold off; %Plot phase angle on the right. end

ii) 基2-FFT函数

function myFFT(N,x)

%This is a base-2 FFT function. lov=(0:N-1); j1=0;

for i=1:N %indexed addressing if i

temp=x(j1+1); x(j1+1)=x(i); x(i)=temp; end

k=N/2;

while k<=j1 j1=j1-k; k=k/2; end

j1=j1+k; end

digit=0; k=N;

while k>1

digit=digit+1; k=k/2; end

n=N/2;% Now we start the "butterfly-shaped" process. for mu=1:digit

dif=2^(mu-1);%Differnce between the indexes of the target variables. idx=1; for i=1:n idx1=idx; idx2=1;

for j1=1:N/(2*n)

r=(idx2-1)*2^(digit-mu);

wn=exp(j*(-2)*pi*r/N);%It is the "circulating coefficients". temp=x(idx);

x(idx)=temp+x(idx+dif)*wn;

x(idx+dif)=temp-x(idx+dif)*wn; idx=idx+1; idx2=idx2+1; end

idx=idx1+2*dif; end n=n/2; end

Amp=abs(x);%Acquire the amplification.

Phs=angle(x);%Acquire the phase angle (radian). subplot(1,2,1);

stem(lov,Amp,'.',’MarkerSize’,18);

xlabel('FFT k');ylabel('FFT Amplification');hold on; %Plot the amplification. subplot(1,2,2);

stem(lov,Phs,'*');xlabel('FFT k');ylabel('FFT Phase Angle (radian)');hold off; end

命令窗口中的运行及其结果：

字数作文