任意長度信號的快速變換Ref: Cooley

J

W

and

Tukey

J

W, gorithm

for

the

machine

calculation

ofcomplex

Fourier

series,

Mathematics

of

Computation,

1965,19(90):

297-301.數字信號處理第七章（4）2020/11/121快速算法思路數值。的一個N

2M例如，N

30

，可以在序列x(n)中補進x(31)

x兩個零值點，使N

32。如果計算FFT的目的是為了了解整個頻譜，而不是特定頻率點，則算法可行。因為有限長序列補零以后并不影響其頻譜X

(eiw

)，只是頻譜的采樣點變化了。如果要求特定頻率點的頻譜，則信號長度N

不能改變，此時補零算法不可行。如果N

為合數，則可以用以任意數為基數的FFT算法來計算。如果N

為質數，目前還很難找到有效的快速算法。當信號

x(n)

的長度N

不是2的整數次冪時，

可以采用補零的方法延長將信號延長，使N

增長到最鄰近數字信號處理第七章（4）2020/11/1222020/11/12數字信號處理第七章（4）3長度為合數的信號的離散變換信號x(n)

的離散 變換為現在考慮當信號長度N

為合數，即N

變換的快速算法。令時，離散則N

1n0X

(m)

x(n)W

nm

,0

m

N

1.1m

m1r1

m0

,n

n1r2

n0

,m1

0,1,n1

0,1,m0

0,1,

r1

1,n0

0,1,

r2

1,r2

1,r1

1.01

2

1

0x(n

,

n

)WX

(m1,

m0

)

n1

n0mnmnrW

.數字信號處理第七章（4）2020/11/124由于則內層求和僅依賴于m0

和n0

，定義一個新的序列有序列

x1

有

N

個元素，計算每個元素需要

r1

個乘法運算，因此計算序列

x1

共需要

Nr1

個乘法運算。同理，通過

x1

計算

X

需要Nr2

個乘法運算。于是，通過此2-step算法共需要個乘法運算。Wmn1

2r

Wm0n1r2

,0

1

2x1

(m0

,

n0

)

m

n

rn1x(n1,

n0

)W

.1

1

0

0n0X

(m1,

m0

)

x1

(m0

,

n0

)W(m

r

m

)k.N(r12如果

N

r1

r2

rm

，按照如上的思想和方法， 容易給出一個m-step算法，并易得其共需要的乘法運算量為當

N

2M

時，有T

2N

log

N

。2T

N(r1

r2

rm

).r如果所有ri

都相等，則有

m

lo

，總的乘法運算量為T

(r)

rN

logr

N.，有如果N

rmsnt

p.T

m·r

n·

s

p·

t

,Nlog2

N

m

log2

r

n

log2

s

p

log2

t

,T

m·r

n·

s

p·

t

,N

log2

N m

log2

r

n

log2

s

p

log2

t

數字信號處理第七章（4）2020/11/125數字信號處理7.有限離散傅氏變換(Ⅳ)7.5有限離散哈特利變換、余弦變換和廣義中值函數cos

1

(ei

ei

), sin

i

(ei2

2

ei

)A.

有限離散哈特利變換一、函數cas設

為實數，令cas

cos其中cas為“cos

and

sin”三個字的縮寫。由于則2數字信號處理第七章（4）2020/11/1272cas

e7.5有限離散哈特利變換、余弦變換和廣義中值函數同樣，由2cos

1

cas

cas(

),2sin

1

cas

cas(

)casei

12

2有二、有限離散哈特利變換（FDHT）kN

k

2

,n離散信號

x

,

n

0,1, ,

N

1

，令則xn

的離散哈特利變換定義為N

1HXm

xncasmn

,n0顯然周期為

N

。m

0,1,,

N

1.數字信號處理第七章（4）2020/11/1287.5有限離散哈特利變換、余弦變換和廣義中值函數下面求哈特利逆變換N

1

N

1

N

1

HXmcasmn

xkcasmk

casmnm0

m0

k

0N

1

N

1

xk

casmk

casmnk

0

m0

iei

(mk

mn

)

iei

(mk

mn

)數字信號處理第七章（4）2020/11/1291mn

mkmk由cas定義知casmn

casei

(

)

1

ei

(

)mk

mn

22由第七章第一節所證明的等式NN

1i(nl

)m

2em0k為整數

N,

n

l

kN,0,

n

l

kN,7.5有限離散哈特利變換、余弦變換和廣義中值函數有m00,mnN

1

cas

N,

k

n

lN,k

n

lN

,casmk則有1n

0,1, ,

N

1nm

mnHX

cas

,x

NN

1m0該式稱為有限離散逆哈特利變換從而有下面有限離散哈特利和逆哈特利變換公式nx

casHX1N2

mn,Ncas

2

mn

1NN

1n0N

1HX

xn

H

(HXm

)Nm

mm0其中，m,n

0,1,,

N1數字信號處理第七章（4）2020/11/12107.5有限離散哈特利變換、余弦變換和廣義中值函數B.

有限離散余弦變換一、有限離散 型余弦變換離散信號：xn

,

n

0,1, ,

N.其有限離散 型余弦變換和有限離散 型逆余弦變換為2xn

, (0

m

N

) (5

1)NXm

m

nk

k

cosmnNn0Nmn

1

,i

0,

N1

i

N

12ik

1,2數字信號處理第七章（4）2020/11/1211Xm

, (0

n

N

)(5

2)Nxn

m

nk

k

cosNm0N其中7.5有限離散哈特利變換、余弦變換和廣義中值函數二、有限離散Ⅱ型余弦變換離散信號xn

,n

0,1,,

N

1則其有限離散Ⅱ型余弦變換和有限離散Ⅱ型逆余弦變換為其中N

1n021

m2mNXm

N, 0

m

N

1x

cos

n

n

,0

n

N

1xn

N2

N2

N

1m01

m

X

cos

n

m

m

2數字信號處理第七章（4）2020/11/1212

1

,m

m

0,1, 1

m

N

1.7.5有限離散哈特利變換、余弦變換和廣義中值函數三、有限離散逆 型余弦變換公式的證明問題：已知（5-1）式，證明（5-2）式。首先給出幾個初等公式2

222

2

2NNini

sin

i

(

N

1)

i

1

e

e

e1

ee

1

eii

i

e

2

e

e

2

sin

N

1

e

2(

2k

)n0數字信號處理第七章（4）2020/11/12137.5有限離散哈特利變換、余弦變換和廣義中值函數取上式的實部和虛部，得2

2;sinN2sin

N

1

cos

N

cos

n

n02

2.sinN2sin

N

sin

N

1

sin

n

n0將（5-1）式代入（5-2）式右邊，得N數字信號處理第七章（4）2020/11/12142kkmkl

cosNNml

NN

m0l0l0xl

nkl

xl

A(l,n) (5

3)N2

mn

2

Nkmkn

cos

N

7.5有限離散哈特利變換、余弦變換和廣義中值函數其中

2數字信號處理第七章（4）2020/11/1215cos11

12

2sin1

12

2sinNmk

cosN

Nm

n

N

N2N

2

N

2

N

2Nmn

mlnlm0A(l,

n)

m

n

l

l

cos

cos

(1)2

sin

N

1

n

l

cos

N

n

l

1

2

N

2

N

2

n

l

sin

N

1

n

l

cos

N

n

l

(1)n

l

m0N

(5-4)nl7.5有限離散哈特利變換、余弦變換和廣義中值函數由上式知2m2m

0

NN

1k

k

2

k

2

NA(0,

0)

A(N

,

N

)

(5-5)Nm0km1當l

n,0

n

N 時，

N

1

1

N

1

1

1

N2

2

2數字信號處理第七章（4）2020/11/1216A(n,

n)

222nsin

n

n

cos

n1212

1sin(5

6)N1

1

cosNm2n

1

12

(1)

N

Nm0n7.5有限離散哈特利變換、余弦變換和廣義中值函數當l

n

時，由n

l

(n

l)

2l

，故n

l

與n

l同偶或同奇當l

n

，n

為奇數時，n

也為奇數，因此2

N

2

Ncos

N

n

c由（知A(l,n)

0,

l

n,n

l當l

n

，n

為偶數時，n

l

2

，這時有

n

l

2cos

N

n

l

cos

k

(1)k2

N2

Nsin

N

1

n

sin

N

數字信號處理第七章（4）2020/11/12177.5有限離散哈特利變換、余弦變換和廣義中值函數sin

n

l

sin

k2N N因此2

N

2

Nsin

N

1

n

l

cos

N

n

l

sin

n

l

1(5

8)2N同樣有2數字信號處理第七章（4）2020/11/1218sin

N

(1)k

l

sinNN7.5有限離散哈特利變換、余弦變換和廣義中值函數n

l

2Nk

l

N2

Nsin

sincos

N

n

co因此2

N

2

N數字信號處理第七章（4）2020/11/1219sin

N

1

n

l

cosN

n

l

1(5

9)sin

n

l

2N由（5-8）、（5-9）和（5-4）知A(l,n)

0,

l

n,n l由（5-5）、（5-6）、（5-7）、（5-10）和（5-4）知有限離散逆Ⅰ型變換公式成立。C.廣義中值函數7.5有限離散哈特利變換、余弦變換和廣義中值函數一、廣義中值函數若對函數g

，存在函數

(

)，使(

)且它們的

(

)還是相同的，即(

)

2

cos

。數字信號處理第七章（4）2020/11/1220g

(2k

1)

或者g

(2k

1)

(

)

g

(2k

2)

g

2k

則稱g

為廣義中值函數，其中

k

為整數，

為實數。容易驗證，cos

，sin

，cas

和

ei

都是廣義中值函數，而

xN

1

，上兩式中要求(

/2)

0。其中x1數字信號處理第七章（4）2020/11/12217.5有限離散哈特利變換、余弦變換和廣義中值函數為一組離散數據，則n性質1

g

為廣義中值函數，N

為正整數，x

(0

n

N

1)1N

11

(

/

2)其中x

0

；或者nn1N

1g(N

)x

x

g(n

)

xx

gN

1n0

1

n

2

n

n0N

1n0N

11

(

/

2)n0nn1N

1x

x

g(n

)

xg(N

)

g(0)x

g

1

n

2

n

7.5有限離散哈特利變換、余弦變換和廣義中值函數證明：由中值函數的定義知1

1

g

n

(

/

2)

g

n

1

g(n

)2

因此由上式可知性質1兩式成立。數字信號處理第七章（4）2020/11/1222

k

12

1

(/

2)1

n

1

g(n

)

(/

2)N

11

x

g(n

)

x

g(k

)Nk

1x

gN

1n0

nn

x

gN

1n0

n

n0

n7.5有限離散哈特利變換、余弦變換和廣義中值函數性質2

g

為廣義中值函數，N

為正偶數，xn

,(0

n

N

1)為一組離散數據，則；或者其中x1

其中x1

0，上兩式中要求。

(

)

0N

N

/

21x2n1

x2n11

(

)

g(2n

)

xN

1g(N

)

n0N

1

N

/

21

xn

g(n

)

x2n

g(2n

)n0

n0

數字信號處理第七章（4）2020/11/1223

N

/

21x2n1

x2n11

(

)

g(2n

)

xN

1

g(N

)

g(0)

n0N

1

N

/

21

xn

g(n

)

x2n

g(2n

)n0

n0

7.5有限離散哈特利變換、余弦變換和廣義中值函數證明：根據自然分解式：N

1

N

/

21

N

/

21

xn

g(n

)

x2n

g(2n

)

x2n1g

2n

1

n0

n0

n0對上式的第二項，利用性質1（用2

代替性質1中的）就得到性質2中的兩式。性質2中的兩式把長度為N

的變換轉化為兩個長度為N

/2的同一變換，體現了快速二分法的思想。二、一種余弦變換的快速算法設

N

1為

N

個實數，當

快速算法時，取

N

2k，k

為正整數。數字信號處理第七章（4）2020/11/12247.5有限離散哈特利變換、余弦變換和廣義中值函數考慮一種余弦變換CN

：m

0,1,2mn

/

N

,N

1X

1

x

cos

n m

n0令

g()

，(

)

2

cos

，

(m

1,

N

1，由于cos

是廣義中值函數，由性質2中第二式可得1

0。其中x

cos

n

m

1

/

N

/

2數字信號處理第七章（4）2020/11/1225N

/

21n0n01

N

/

2122n

/

N

/

2

2

mX

1

x

cos

n m

1

2

cos

m

2

/

N

x2n1

x2n1

7.5有限離散哈特利變換、余弦變換和廣義中值函數由上式可得其中

22N2

/

N

/

2

,

/

N

/

2

,N/

21N/

211

A

x

cos

n m

0

m

11

B

x

xcos

n m

m

2nn0m

2n1