第一部分信號處理與分析第五章（續(xù)）離散

變換主要內(nèi)容：對于有限長的離散時間序列，可以得到離散變換(DFT)；所謂離散 變換（DFT），實質(zhì)上是對于離散時間 變換進行頻域采樣所得到的頻域采樣點；（連續(xù)時間 變換(CTFT)）（離散時間 變換(DTFT)）離散

變換的優(yōu)點，不僅在于它是離散化形式，更由于它有快速算法(FFT)，因此在實現(xiàn)各種數(shù)字信號處理算法中起著 作用。第五章（續(xù)）離散變換2020/11/172第五章（續(xù)）離散變換5.1離散在離散變換變換中，有下列結(jié)論：周期），則 級數(shù)系數(shù)。已知非周期信號x[n]以及它的周期延拓~x[n]

（以N

為~x[n]的變換

X

(e

j

)

之間滿足關(guān)系：ka

與x[n]的kNa

1

X

(e

jk0

)N0其中

2問題：已知序列

x[n]

，可以得到

；反過來，如果ak

已知ak

，是否可以恢復(fù)序列x[n]？2020/11/173第五章（續(xù)）離散變換假設(shè)序列

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ù)）

離散

變換X

[k

]N級數(shù)系數(shù)，即1

~

~則

可以看作某個以

N

周期的序列x[n]

的X

(e

j

)~X

[k]k

N

X

[k

]e

~~x[n]

1Njk0n~x[n]

0N2020/11/175第五章（續(xù)）離散變換又因為：所以有前面已經(jīng)證明：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)第五章（續(xù)）離散變換所以有則

為周期的周期延拓，它在每個周期內(nèi)

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ù)）離散變換期的延拓x[n]MM0N

M

2也就是說，對于X

(e

j

)的采樣頻率足夠高，滿足0X

(e

j

)~X

[k]~則利用頻域采樣點的值X

[k]，可以構(gòu)造原來信號的以N

為周~x[n]，從而恢復(fù)x[n]~x[n]MN第五章（續(xù)）離散變換，可以定義其在一個周期的序列x[n]因此，對于有限長度為N離散 變換：r

N記為

~x[n]

x[((n))

]1）構(gòu)造x[n]的周期延拓，有~x[n]

x[n

rN

]~2）計算x[n]的~級數(shù)系數(shù)X

[k]；~NX[k]3）

x[n]的離散 變換

X

[k

]

就是~內(nèi)的值，即NX

[k]

X

[((k))N

]2020/11/179第五章（續(xù)）

離散

變換離散時間級數(shù)：離散時間

變換：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第五章（續(xù)）

離散

變換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算法復(fù)雜性：對于有限長度為

N

的序列

x[n]

，計算其全部的葉變換需要

N

2

次乘法和

N

(N

1)

次加法。問題：如何降低算法復(fù)雜性？2020/11/1711第五章（續(xù)）

離散

變換2）周期性所有快速算法都基于這兩條性質(zhì)。x[n]W

,X

[k]

N

1n0knNk

0,1,,

N

1令WN

j

2N

，則變換公式可以寫成：

e容易證明，WN

滿足下列性質(zhì)：1）復(fù)共軛對稱性*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ù)）

離散

變換變計算過程用下面方式說明：x[n]W

,X

[k]

N

1n0knNk

0,1,,

N

11.按時間抽取的FFT算法假設(shè)N為2的整數(shù)次冪，即N

2v

。則其離散換為N點DFTx[n]2020/11/1713n0,,N

1X

[k]k

0,,N

1第五章（續(xù)）

離散

變換將 變換的計算公式按照時間的奇偶性分成兩部分所以有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第五章（續(xù)）離散變換其中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ù)）離散變換的奇數(shù)點的x[n]

的偶數(shù)點所構(gòu)而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ù)）

離散

變換的計算可以通此時的計算復(fù)雜性為乘法次數(shù)：事實上，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

加法次數(shù)：2

N

(N

1)

N第五章（續(xù)）離散變換下面給出

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第五章（續(xù)）

離散

變換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

為偶數(shù)，這種將多個點的DFT轉(zhuǎn)變?yōu)閮蓚€更少點

DFT的過程就可以繼續(xù)下去，直到分解不能進行為止。繼續(xù)給出N

為8繼續(xù)分解的情形：x[0]x[4]N

/

4W

0N

/

4W

12020/11/1719第五章（續(xù)）

離散

變換為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第五章（續(xù)）離散變換此時算法的復(fù)雜性為：分層數(shù)log

2

N2020/11/1721每層內(nèi)需要加法

N

次，

乘法

N

次。

總的加法

N

log

2

N

次，乘法

N

log

2

N

次。NN

2N

log

2

N644096384128655362048512262144460810241048576102402048419430422528第五章（續(xù)）

離散

變換則前面的遞推公式可以寫成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的性質(zhì)，前面的過程可以進一步簡化。因為 滿足WNW

(

N

/

2k

)

W

k2020/11/17222020/11/1723第五章（續(xù)）離散變換此時的乘法次數(shù)減少為原來的一半：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ù)）

離散

變換比較信號x[n]的排列順序以及X

[k

]的排列順序，有下列規(guī)律：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]第五章（續(xù)）

離散

變換輸入P

{P0

,P1,,PN

1}，輸出為F

{F0

,F1,,FN

1}其中N

2K2020/11/1725第五章（續(xù)）

離散

變換變分別計算其奇數(shù)變換和偶數(shù) 變換。x[n]W

,X

[k]

N

1n0knNk

0,1,,

N

12.按頻率抽取的FFT算法假設(shè)N為2的整數(shù)次冪，即N

2v

。則其離散換為2020/11/1726第五章（續(xù)）離散變換有因為所以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第五章（續(xù)）離散變換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的計算轉(zhuǎn)變成兩個(N

/

2)點DFT的計算，繼續(xù)分解直到不能分解為止。第五章（續(xù)）離散變換下面給出

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第五章（續(xù)）

離散

變換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第五章（續(xù)）

離散

變換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第五章（續(xù)）離散變換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

]為復(fù)數(shù)。在數(shù)據(jù)壓縮中經(jīng)常使用的是離散余弦變換(DCT)。在早期版本的圖像壓縮標(biāo)準(zhǔn)JPEG

（

JointPhotographicsExperts

Group）中使用。2020/11/1732第五章（續(xù)）離散變換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第五章（續(xù)）離散變換二維情形：其中類似地，DFT也有快速算法。