版本3-dft离散变换

第一部分信号处理与分析第五章（续）离散

变换主要内容：对于有限长的离散时间序列，可以得到离散变换(DFT)；所谓离散 变换（DFT），实质上是对于离散时间 变换进行频域采样所得到的频域采样点；（连续时间 变换(CTFT)）（离散时间 变换(DTFT)）离散

变换的优点，不仅在于它是离散化形式，更由于它有快速算法(FFT)，因此在实现各种数字信号处理算法中起着 作用。第五章（续）离散变换2020/11/172第五章（续）离散变换5.1离散在离散变换变换中，有下列结论：周期），则 级数系数。已知非周期信号x[n]以及它的周期延拓~x[n]

（以N

为~x[n]的变换

X

(e

j

)

之间满足关系：ka

与x[n]的kNa

1

X

(e

jk0

)N0其中

2问题：已知序列

x[n]

，可以得到

；反过来，如果ak

已知ak

，是否可以恢复序列x[n]？2020/11/173第五章（续）离散变换假设序列

x[n]有限长，则可以得到它的

变换N2X

(e

j

)

x[n]e

jnn对于

X

(e

j

)

以频率

0

进行采样，记为~jk0X

[k]

X

(e

)因为X

(e

j

)以2

为周期，所以以N

为周期。~X

[k]0jX

(e

)~X

[k]x[n]M2020/11/174第五章（续）

离散

变换X

[k

]N级数系数，即1

~

~则

可以看作某个以

N

周期的序列x[n]

的X

(e

j

)~X

[k]k

N

X

[k

]e

~~x[n]

1Njk0n~x[n]

0N2020/11/175第五章（续）离散变换又因为：所以有前面已经证明：n00

)

x[n]eX

[k]

X

(e~

jk

njkN

m

kN

xmeeN

kN

mN

kN

xem

0

[]1

[]

1Xk[]e

~

1~xn[]jk

nm

)(

jk0m

jk0njk0n2020/11/1760101

n

m

rN，r

Z其它eN

k

N

jk

(nm)第五章（续）离散变换所以有则

为周期的周期延拓，它在每个周期内

N

m

k

N

1~x[n]

x[m]

e

jk0(nm)

x[n

rN]r

对于有限长的x[n]，如果其有x[n]M限长度满足

M

N

，~x[n]就是以N~x[n]MN的值就是

x[n]

；反之，不成立。~x[n]MN2020/11/1772020/11/178第五章（续）离散变换期的延拓x[n]MM0N

M

2也就是说，对于X

(e

j

)的采样频率足够高，满足0X

(e

j

)~X

[k]~则利用频域采样点的值X

[k]，可以构造原来信号的以N

为周~x[n]，从而恢复x[n]~x[n]MN第五章（续）离散变换，可以定义其在一个周期的序列x[n]因此，对于有限长度为N离散 变换：r

N记为

~x[n]

x[((n))

]1）构造x[n]的周期延拓，有~x[n]

x[n

rN

]~2）计算x[n]的~级数系数X

[k]；~NX[k]3）

x[n]的离散 变换

X

[k

]

就是~内的值，即NX

[k]

X

[((k))N

]2020/11/179第五章（续）

离散

变换离散时间级数：离散时间

变换：x[n]的离散变换X

[k

]及其反变换满足：1N

1jk

nNN

1n0N

X

[k]eN

k

0x[n]

X

[k]

x[n]e2

jk

2

nNN

nN

ak

2

jk

2

njk

nx[n]

ake

Nk

N

x[n]e122x[n]

1

X

(e

j

)e

jndnX

(e

j

)

x[n]e

jn2020/11/1710第五章（续）

离散

变换8.2

离散 变换的快速算法（FFT）1

X

[k]ex[n]

X

[k]

x[n]eN

1N

k

0jk

nNN

1n0N,

n

0,1,,

N

1,

k

0,1,,

N

12

jk

2

n算法复杂性：对于有限长度为

N

的序列

x[n]

，计算其全部的叶变换需要

N

2

次乘法和

N

(N

1)

次加法。问题：如何降低算法复杂性？2020/11/1711第五章（续）

离散

变换2）周期性所有快速算法都基于这两条性质。x[n]W

,X

[k]

N

1n0knNk

0,1,,

N

1令WN

j

2N

，则变换公式可以写成：

e容易证明，WN

满足下列性质：1）复共轭对称性*knNNNW

W

Wknk

(

N

n)knN N

WWN

W(

N

k

)nk

(

N

n)NW

0NW

1NW

2NW

0NW

nN2020/11/1712W

N

n第五章（续）

离散

变换变计算过程用下面方式说明：x[n]W

,X

[k]

N

1n0knNk

0,1,,

N

11.按时间抽取的FFT算法假设N为2的整数次幂，即N

2v

。则其离散换为N点DFTx[n]2020/11/1713n0,,N

1X

[k]k

0,,N

1第五章（续）

离散

变换将 变换的计算公式按照时间的奇偶性分成两部分所以有2020/11/1714N

1/22

krNN

1/22

krN

N

r

0r

0k r

1()2NN

/

21

N

1/2r

0N

1](W

)x[2rx[2r](W

)

W

kx[2r

1]WX

[k]

x[2r]W

2krr

0因为

WN

满足W

2

WN N

/

2x[2r]Wx[2rNkrN

/

2NkrN

/

2

G[k

]

W

k

H[k

]1]W

W

kX

[k

]

N

/

21r

0N

/

21r

02020/11/1715第五章（续）离散变换其中N

/

21r

0krN

/

2x[2r]WG[k]

N

/

21krN

/

2x[2r

1]WH[k]

k

0,1,,

N

1r

0虽然

k

可以取

N

种不同的值，但是由于WN

/

2

的周期性，G[k]和

H

[k

]

都是以

(N

/

2)

为周期的；也就是说，]H[2G[

N

k

]

G[k

]2

k

0,1,,

N

/

2

12020/11/1716第五章（续）离散变换的奇数点的x[n]

的偶数点所构而H[k]k

0,,N

/21即则是

x[n](N

点/2D)FT。因此，G[k]k

0,,N

/21

可以看成是成信号的(N

/2)点DFT；N/2点DFTx[2r]r

0,,N

/

21G[k]k

0,,N

/

21N/2点DFTx[2r

1]r

0,,N

/

21H[k]k

0,,N

/

212020/11/1717第五章（续）

离散

变换的计算可以通此时的计算复杂性为乘法次数：事实上，x[n]

的

N

点DFT

X

[k]k

0,,N

1过先计算两个

(N

/

2)

点DFT，然后通过它们之间的线性组合来计算，即N/2点DFTx[2r]r

0,,N

/

21G[k]k

0,,N

/

21N/2点DFTx[2r

1]r

0,,N

/

21H[k]k

0,,N

/

21X[k]k

0,,N

1

N

N

2

2

22

2

加法次数：2

N

(N

1)

N第五章（续）离散变换下面给出

N

等于8时的情形：N/2点DFTN/2点DFTx[0]x[2]x[4]x[6]x[1]x[3]x[5]x[7]G[0]G[1]G[2]G[3]H

[0]H[1]H

[2]H

[3]X

[0]X

[7]NX

[1]W

0NX

[2]W

1N

X

[3]W

2NW

3NX

[5]X

[4]W

4N

X

[6]W

5NW

6NW

72020/11/1718第五章（续）

离散

变换N/4点DFTx[0]x[4]x[2]x[6]G[0]G[3]N

/

2W

0N

/

2G[2]W

1

G[1]N

/

2W

23N

/

2WN/4点DFT只要N

为偶数，这种将多个点的DFT转变为两个更少点

DFT的过程就可以继续下去，直到分解不能进行为止。继续给出N

为8继续分解的情形：x[0]x[4]N

/

4W

0N

/

4W

12020/11/1719第五章（续）

离散

变换为8时，整个分解过程为（蝶形图）Nx[0]x[4]x[2]x[6]x[1]x[5]x[3]x[7]X

[0]X

[1]X

[2]X

[3]X

[4]X

[5]X

[6]X

[7]WNNW

12WN3WNNW

4NW

5NW

6NW

7N

/

4W

0N

/

4W

10

0WN

/

2N

/

2W

1N

/

2W

2N

/

2W

3N

/

2W

0N

/

2W

1N

/

2W

23WN

/

2N

/

4W

0N

/

4W

00N

/

4W

1N

/

4W

1WN

/

4N

/

4W

12020/11/1720第五章（续）离散变换此时算法的复杂性为：分层数log

2

N2020/11/1721每层内需要加法

N

次，

乘法

N

次。

总的加法

N

log

2

N

次，乘法

N

log

2

N

次。NN

2N

log

2

N644096384128655362048512262144460810241048576102402048419430422528第五章（续）

离散

变换则前面的递推公式可以写成N

N]X

[2N

G[k

]

W

k

H[k

]NX

[k]

G[k]

W

k

H[k]k

0,1,,

N

/

2

1事实上，利用WN的性质，前面的过程可以进一步简化。因为 满足WNW

(

N

/

2k

)

W

k2020/11/17222020/11/1723第五章（续）离散变换此时的乘法次数减少为原来的一半：N

为8时，整个分解过程改进为:x[0]x[2]x[4]x[6]x[1]x[3]x[5]x[7]X

[0]X

[1]X

[2]X

[3]X

[4]X

[5]X

[6]X

[7]NW

0NW

1NW

23WN0WN

/

4N

/

2W

0WN

/

21111N

/

4W

0N

/

4W

0N

/

4W

0N

/

2W

01WN

/

21111

11111N2log

N2第五章（续）

离散

变换比较信号x[n]的排列顺序以及X

[k

]的排列顺序，有下列规律：x[0]

x[000]

X

[000]

X

[0]x[4]

x[100]

X

[001]

X

[1]x[2]

x[010]

X

[010]

X

[2]2020/11/1724x

[x61[]10

X

[]011

X

[3]x

x[10[0]

1

X

[1]00

X

[]4xx[3]x[7]

x

X

X

[5]x[011]

X

[110]

X

[6]x[111]

X

[111]

X

[7]第五章（续）

离散

变换输入P

{P0

,P1,,PN

1}，输出为F

{F0

,F1,,FN

1}其中N

2K2020/11/1725第五章（续）

离散

变换变分别计算其奇数变换和偶数 变换。x[n]W

,X

[k]

N

1n0knNk

0,1,,

N

12.按频率抽取的FFT算法假设N为2的整数次幂，即N

2v

。则其离散换为2020/11/1726第五章（续）离散变换有因为所以2020/11/1727n0rnNNn0NN

1nN

/2N

/212rnNN

/21n0N

/21NN

12rnN

n/]W[22(/2)

x

N

x[]n

W

2rnx[]nW

x[]n

W

2rnX

r

[2x[]n]

Wn0NN

/2

WWrnW

2

( /

2nN)

r

2rnNN

/

21n0N

/

2X

[2r]

(x[n]

x[N

/

2

n])W

rn第五章（续）离散变换N

1/22020/11/1728N N

/2x[N

/

2

n])W

nW

rn(x[n]类似地，有X

[2r

1]N

/

2

n01n0rnN

/

2(x[n]

x[N

/

2

n])WX

[2r]

r

0,1,,

N

/

2

1同样，将一个

N

点DFT的计算转变成两个(N

/

2)点DFT的计算，继续分解直到不能分解为止。第五章（续）离散变换下面给出

N

等于8时的情形：N/2点DFTN/2点DFTx[0]x[1]x[2]x[3]x[4]x[5]x[6]x[7]X

[1]X

[3]X

[5]X

[7]X

[0]X

[2]X

[4]X

[6]NW

01NWNW

2NW

311112020/11/1729第五章（续）

离散

变换N为8时，整个分解过程为（蝶形图）x[0]x[1]x[2]x[3]x[4]x[5]x[6]x[7]X

[0]X

[4]X

[2]X

[6]X

[1]X

[5]X

[3]X

[7]0N

/

4W0N

/

2W1N

/

2W0WN

/

2WN

/

2N

/

4W0N

/

4WWN

/

4WW0N1N2NW3NW1111111111

011

1

02020/11/1730第五章（续）

离散

变换N为8时，整个分解过程为（蝶形图）x[0]x[1]x[2]x[3]x[4]x[5]x[6]x[7]X

[0]X

[4]X

[2]X

[6]X

[1]X

[5]X

[3]X

[7]0N

/

4W0N

/

2W1N

/

2W0WN

/

2WN

/

2N

/

4W0N

/

4WWN

/

4WW0N1N2NW3NW1111111111

011

1

02020/11/1731第五章（续）离散变换5.3离散余弦变换1

X

[k]ex[n]

X

[k]

x[n]eN

1N

k

0jk

nNN

1n0N,

n

0,1,,

N

1,

k

0,1,,

N

12

jk

2

n即使x[n]为实值信号，X

[k

]为复数。在数据压缩中经常使用的是离散余弦变换(DCT)。在早期版本的图像压缩标准JPEG

（

JointPhotographicsExperts

Group）中使用。2020/11/1732第五章（续）离散变换DCT与IDCT变换公式：一维情形：其中2N

Nn01

Nk012N1(k)2nn0

[[]]kcX[oxsk]nk

0

N

1

xkn[[kcX][o]s] 1(k)2nN

11k

0

Nk

0N2[k

]

2020/11/1733第五章（续）离散变换二维情形：其中类似地，DFT也有快速算法。