数字信号处理

任意长度信号的快速变换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