离散傅里叶变换计算方法(DFT、FFT,HDT)

福利叶变换

第三章 DFT——离散付氏变换 DFS 和 DFT 的导出 DFS 和 DFT 的性质 Z 变换与 DFS 的关系 FFT IDFT 频谱分析

福利叶变换

3.1 问题的提出：连续信号的傅里叶变换 连续信号 xa(t),其傅里叶变换为：X a ( )

xa ( t )e j t dt

1 x a (t ) 2

X a ( )e j t d

xa(t) 为时域连续信号 Xa(Ω) 为频域连续信号

北京邮电大学信息与通信工程学院

福利叶变换

3.1 问题的提出：离散信号的变换 离散信号在两种变换域中的表示方法(1)离散时间傅里叶变换 DTFT -- 提供了绝对可加的离散时间序列 在频域(ω)中的表示方法。

X (e jw )

(2)Z 变换 -- 提供任意序列的 z 域表示。

n

x( n)e jnw

X (z)

n

x ( n) z n

这两种变换有两个共同特征：(1)变换适合于无限长序列 (2)它们是连续变量 ω 或 z 的函数北京邮电大学信息与通信工程学院3

福利叶变换

3.1 问题的提出：可计算性 问题：X(z),X(ejw) 都是连续的，利用计算机处理有困难，例如使用 Matlab,因此 提出了在频域内取样，使频谱离散化的问题； 必须截断序列，得到有限个点的序列。

目标：我们需要得到一个可进行数值计算的变换 方法：(1)DTFT - 频域中原始信号频谱的周期拓展 (2)对 DTFT 在频域中采样 -- DFS (3)将 DFS 推广到有限持续时间序列 DFT (DFT 避免了前面提到的那两个问题，并且它是计算机可实现 的变换方式。)

DFT 已成为 DSP 算法中的核心变换，原因：(1)有限长序列傅里叶变换的重要方法 (2)有快速算法

北京邮电大学信息与通信工程学院

福利叶变换

3.1 问题的提出：傅里叶变换的四种形式 (1)时间函数

频率函数

非周期连续时间—傅里叶变换(FT)-连续频率 周期连续时间—傅里叶级数(FS)-离散频率 非周期离散时间—离散时间傅里叶变换(DTFT)-连续频率 周期离散时间—离散傅里叶级数(DFS)-离散频率

时域连续函数造成频域是非周期的谱 时域的非周期造成频域是连续的谱

北京邮电大学信息与通信工程学院

福利叶变换

3.1 问题的提出：傅里叶变换的四种形式 (2)1. 连续信号(非周期)的付氏变换x(t ) X ( )

t

x(t ) X ( ),1 x(t ) 2

t X ( ) x(t )e j t dt

X ( )e d

j t

时域连续函数造成频域是非周期的谱 时域的非周期造成频域是连续的谱北京邮电大学信息与通信工程学院6

福利叶变换

3.1 问题的提出：傅里叶变换的四种形式 (3)2. 周期连续时间信号：傅里叶级数 FS~ (t ) x X (n 0 )

t T

时域周期 频域离散

0

2 T

x(t)

~

n -

X(

n 0 )e jn 0t

时域连续函数造成频域是非周期的谱。 频域的离散对应时域是周期函数。北京邮电大学信息与通信工程学院7

1 X ( n 0 ) T

T 2

T 2

( t )e jn 0t dt x

福利叶变换

3.1 问题的提出：傅里叶变换的四种形式 (4)3. 非周期离散信号：离散时间傅里叶变换 DTFTx(nT )

X (e j T )

T

时域离散 频域周期

2 T

T x(nT ) 2 X (e j T )

T T

X (e j T )e jn T d

取样定理

n

x(nT )e jn T

1 X ( 0 ) T n

时域的离散化造成频域的周期延拓 时域的非周期对应于频域的连续北京邮电大学信息与通信工程学院8

福利叶变换

3.1 问题的提出：傅里叶变换的四种形式 (5)4. 周期离散时间信号：离散傅里叶级数 DFS x( nT1 )n 周期

T N T=NT1 T1k

T X (k 0 )

T1

取样间隔

2 T1 0 2 T

2 2 0 T NT12 N 0T1

时域周期、离散 频域周期、离散

1 ( n) x N

X ( k )ek 0

N 1

j

2 nk N

X (k )

x ( n )en 0

N 1

j

2 nk N

一个域的离散造成另一个域的周期延拓 离散傅里叶级数的时域和频域都是离散的和周期的北京邮电大学信息与通信工程学院9

福利叶变换

3.1 问题的提出：傅里叶变换的四种形式 (6) 四种傅里叶变换形式的归纳总结：形式 傅里叶 变换 FT 傅里叶 级数 FS 时间函数 连续 非周期 连续 周期(T0) 频率函数 非周期 连续 非周期 离散(Ω0=2π/T0) 周期(Ωs=2π/T) 连续 周期(Ωs=2π/T) 离散(Ω0=2π/T0)

结论：① 时域中函数取样(离散) (映射) 频域中函数周期重复； ② 频域中函数取样 (映射) 时 域中函数周期重复； ③ 取样间隔 (映射) 周期(2π/间隔)

离散时间 离散(T) 傅里叶变 非周期 换DTFT 离散傅里 离散(T) 叶级数 周期(T0) DFS

s 1 离散时间函数的取样间隔：T1,取样频率：f s 2 T 1

离散频率函数的取样间隔：F0,时间周期：T 1 2 0北京邮电大学信息与通信工程学院

F0

0

福利叶变换

3.1 问题的提出：傅里叶变换的四种形式 (7)xa(t) (a) FTt

Xa(Ω)

0

Tm~(t ) x

-Ωm

Ωm Xa(kΩ1) 1

(c) FSt

-T1

0x(n) = xa(nT)

Tm T11/T

-Ωm~ X ( )

Ω1 Ωm

(b) DTFTn

0

T

Tm

-Ωs

-Ωm1/T

Ωm

Ωs

~(n) ~(nT ) x x(d) DFSn

~ ~ X (k ) X (k 1 )k

-N

0

N

-N

0

N

时域中函数的取样和频域中函数的取样

福利叶变换

3.2 DFS 及其性质 由以上讨论可以清楚地看到，时域取样将引起频

域的周期延拓，频域取样也将引起时域的周期延 拓。 因此可以设想，如果同时对频域和时域取样，其

结果是时域和频域的波形都变成离散、周期性的 波形，从而我们可以利用付氏级

数这一工具，得 到它们之间的离散付氏级数 DFS 关系。

北京邮电大学信息与通信工程学院

福利叶变换

DFS 定义：预备知识 基本关系式 若 r,m 都是整数,则:

ek 0

N 1

j

2 k (r m ) N

N 0

r m r m

证明: 对于r=m:不论 k 取何值，显然等式成立。对于r≠m:N 1 k 0 2 k (r m ) N

e

j

1 WN 1 e j 2 ( r m ) WN k ( r m ) 0 2 ( r m ) j (r m ) 1 WN k 0 1 e NN 1 (r m ) Nkm N

Wk 0

N 1

- kr N

W

N 0

r m r m

其中: W e j N N

2

北京邮电大学信息与通信工程学院

福利叶变换

DFS 定义：正变换 为了推导 x( nT1 ) X ( k 0 ) 的关系，作下列变量代换： 时域： nT 1DFS

n

频域： k 0

k

?~ X (k)

则得：~(n) x

DFSn

01

N