任意長(zhǎng)度信號(hào)的快速變換Ref: Cooley

J

W

and

Tukey

J

W, gorithm

for

the

machine

calculation

ofcomplex

Fourier

series,

Mathematics

of

Computation,

1965,19(90):

297-301.數(shù)字信號(hào)處理第七章（4）2020/11/121快速算法思路數(shù)值。的一個(gè)N

2M例如，N

30

，可以在序列x(n)中補(bǔ)進(jìn)x(31)

x兩個(gè)零值點(diǎn)，使N

32。如果計(jì)算FFT的目的是為了了解整個(gè)頻譜，而不是特定頻率點(diǎn)，則算法可行。因?yàn)橛邢揲L(zhǎng)序列補(bǔ)零以后并不影響其頻譜X

(eiw

)，只是頻譜的采樣點(diǎn)變化了。如果要求特定頻率點(diǎn)的頻譜，則信號(hào)長(zhǎng)度N

不能改變，此時(shí)補(bǔ)零算法不可行。如果N

為合數(shù)，則可以用以任意數(shù)為基數(shù)的FFT算法來(lái)計(jì)算。如果N

為質(zhì)數(shù)，目前還很難找到有效的快速算法。當(dāng)信號(hào)

x(n)

的長(zhǎng)度N

不是2的整數(shù)次冪時(shí)，

可以采用補(bǔ)零的方法延長(zhǎng)將信號(hào)延長(zhǎng)，使N

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

的離散 變換為現(xiàn)在考慮當(dāng)信號(hào)長(zhǎng)度N

為合數(shù)，即N

變換的快速算法。令時(shí)，離散則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

.數(shù)字信號(hào)處理第七章（4）2020/11/124由于則內(nèi)層求和僅依賴于m0

和n0

，定義一個(gè)新的序列有序列

x1

有

N

個(gè)元素，計(jì)算每個(gè)元素需要

r1

個(gè)乘法運(yùn)算，因此計(jì)算序列

x1

共需要

Nr1

個(gè)乘法運(yùn)算。同理，通過(guò)

x1

計(jì)算

X

需要Nr2

個(gè)乘法運(yùn)算。于是，通過(guò)此2-step算法共需要個(gè)乘法運(yùn)算。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

，按照如上的思想和方法， 容易給出一個(gè)m-step算法，并易得其共需要的乘法運(yùn)算量為當(dāng)

N

2M

時(shí)，有T

2N

log

N

。2T

N(r1

r2

rm

).r如果所有ri

都相等，則有

m

lo

，總的乘法運(yùn)算量為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

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

1

(ei

ei

), sin

i

(ei2

2

ei

)A.

有限離散哈特利變換一、函數(shù)cas設(shè)

為實(shí)數(shù)，令cas

cos其中cas為“cos

and

sin”三個(gè)字的縮寫。由于則2數(shù)字信號(hào)處理第七章（4）2020/11/1272cas

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

1

cas

cas(

),2sin

1

cas

cas(

)casei

12

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

k

2

,n離散信號(hào)

x

,

n

0,1, ,

N

1

，令則xn

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

1HXm

xncasmn

,n0顯然周期為

N

。m

0,1,,

N

1.數(shù)字信號(hào)處理第七章（4）2020/11/1287.5有限離散哈特利變換、余弦變換和廣義中值函數(shù)下面求哈特利逆變換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

)數(shù)字信號(hào)處理第七章（4）2020/11/1291mn

mkmk由cas定義知casmn

casei

(

)

1

ei

(

)mk

mn

22由第七章第一節(jié)所證明的等式NN

1i(nl

)m

2em0k為整數(shù)

N,

n

l

kN,0,

n

l

kN,7.5有限離散哈特利變換、余弦變換和廣義中值函數(shù)有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數(shù)字信號(hào)處理第七章（4）2020/11/12107.5有限離散哈特利變換、余弦變換和廣義中值函數(shù)B.

有限離散余弦變換一、有限離散 型余弦變換離散信號(hào)：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數(shù)字信號(hào)處理第七章（4）2020/11/1211Xm

, (0

n

N

)(5

2)Nxn

m

nk

k

cosNm0N其中7.5有限離散哈特利變換、余弦變換和廣義中值函數(shù)二、有限離散Ⅱ型余弦變換離散信號(hào)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數(shù)字信號(hào)處理第七章（4）2020/11/1212

1

,m

m

0,1, 1

m

N

1.7.5有限離散哈特利變換、余弦變換和廣義中值函數(shù)三、有限離散逆 型余弦變換公式的證明問題：已知（5-1）式，證明（5-2）式。首先給出幾個(gè)初等公式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數(shù)字信號(hào)處理第七章（4）2020/11/12137.5有限離散哈特利變換、余弦變換和廣義中值函數(shù)取上式的實(shí)部和虛部，得2

2;sinN2sin

N

1

cos

N

cos

n

n02

2.sinN2sin

N

sin

N

1

sin

n

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

cosNNml

NN

m0l0l0xl

nkl

xl

A(l,n) (5

3)N2

mn

2

Nkmkn

cos

N

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

2數(shù)字信號(hào)處理第七章（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有限離散哈特利變換、余弦變換和廣義中值函數(shù)由上式知2m2m

0

NN

1k

k

2

k

2

NA(0,

0)

A(N

,

N

)

(5-5)Nm0km1當(dāng)l

n,0

n

N 時(shí)，

N

1

1

N

1

1

1

N2

2

2數(shù)字信號(hào)處理第七章（4）2020/11/1216A(n,

n)

222nsin

n

n

cos

n1212

1sin(5

6)N1

1

cosNm2n

1

12

(1)

N

Nm0n7.5有限離散哈特利變換、余弦變換和廣義中值函數(shù)當(dāng)l

n

時(shí)，由n

l

(n

l)

2l

，故n

l

與n

l同偶或同奇當(dāng)l

n

，n

為奇數(shù)時(shí)，n

也為奇數(shù)，因此2

N

2

Ncos

N

n

c由（知A(l,n)

0,

l

n,n

l當(dāng)l

n

，n

為偶數(shù)時(shí)，n

l

2

，這時(shí)有

n

l

2cos

N

n

l

cos

k

(1)k2

N2

Nsin

N

1

n

sin

N

數(shù)字信號(hào)處理第七章（4）2020/11/12177.5有限離散哈特利變換、余弦變換和廣義中值函數(shù)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數(shù)字信號(hào)處理第七章（4）2020/11/1218sin

N

(1)k

l

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

l

2Nk

l

N2

Nsin

sincos

N

n

co因此2

N

2

N數(shù)字信號(hào)處理第七章（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.廣義中值函數(shù)7.5有限離散哈特利變換、余弦變換和廣義中值函數(shù)一、廣義中值函數(shù)若對(duì)函數(shù)g

，存在函數(shù)

(

)，使(

)且它們的

(

)還是相同的，即(

)

2

cos

。數(shù)字信號(hào)處理第七章（4）2020/11/1220g

(2k

1)

或者g

(2k

1)

(

)

g

(2k

2)

g

2k

則稱g

為廣義中值函數(shù)，其中

k

為整數(shù)，

為實(shí)數(shù)。容易驗(yàn)證，cos

，sin

，cas

和

ei

都是廣義中值函數(shù)，而

xN

1

，上兩式中要求(

/2)

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

g

為廣義中值函數(shù)，N

為正整數(shù)，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有限離散哈特利變換、余弦變換和廣義中值函數(shù)證明：由中值函數(shù)的定義知1

1

g

n

(

/

2)

g

n

1

g(n

)2

因此由上式可知性質(zhì)1兩式成立。數(shù)字信號(hào)處理第七章（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有限離散哈特利變換、余弦變換和廣義中值函數(shù)性質(zhì)2

g

為廣義中值函數(shù)，N

為正偶數(shù)，xn

,(0

n

N

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

其中x1

0，上兩式中要求。

(

)

0N

N

/

21x2n1

x2n11

(

)

g(2n

)

xN

1g(N

)

n0N

1

N

/

21

xn

g(n

)

x2n

g(2n

)n0

n0

數(shù)字信號(hào)處理第七章（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有限離散哈特利變換、余弦變換和廣義中值函數(shù)證明：根據(jù)自然分解式：N

1

N

/

21

N

/

21

xn

g(n

)

x2n

g(2n

)

x2n1g

2n

1

n0

n0

n0對(duì)上式的第二項(xiàng)，利用性質(zhì)1（用2

代替性質(zhì)1中的）就得到性質(zhì)2中的兩式。性質(zhì)2中的兩式把長(zhǎng)度為N

的變換轉(zhuǎn)化為兩個(gè)長(zhǎng)度為N

/2的同一變換，體現(xiàn)了快速二分法的思想。二、一種余弦變換的快速算法設(shè)

N

1為

N

個(gè)實(shí)數(shù)，當(dāng)

快速算法時(shí)，取

N

2k，k

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

：m

0,1,2mn

/

N

,N

1X

1

x

cos

n m

n0令

g()

，(

)

2

cos

，

(m

1,

N

1，由于cos

是廣義中值函數(shù)，由性質(zhì)2中第二式可得1

0。其中x

cos

n

m

1

/

N

/

2數(shù)字信號(hào)處理第七章（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有限離散哈特利變換、余弦變換和廣義中值函數(shù)由上式可得其中

22N2

/

N

/

2

,

/

N

/

2

,N/

21N/

211

A

x

cos

n m

0

m

11

B

x

xcos

n m

m

2nn0m

2n1