tceic.com
学霸学习网 这下你爽了
相关文章
当前位置:首页 >> 信息与通信 >>

一种基于离散傅里叶变换的小波变换的快速算法


第3卷 第1期 2005 年 3 月

南京工 程学院 学报( 自然科 学版 )
Jo urnal o f Nanjing Institut e of T echnolo gy ( Nat ural Science Edition)

V o l. 3, N o . 1 M ar . , 2005

文章编号 : 1672- 2558( 2005) 01- 0011- 07

一种基于离散傅里叶变换的 小波变换的快速算法
徐伟业 宋宇飞 宗 慧
南京, 210013) ( 南京工程学院通信工程系 , 江苏


要 : 小波理论中的多分辨率 分析和 M allat 算法近年来已在数字信 号处理中 得到了广泛 的应用 . 但如果 直接按

照上述算法计算信号的小波分解和重构 , 其计算量将是很大的 . 通过对离散傅里叶变换及 M allat 算法 原理的分析 , 针对离散小波变换算法结构特征 , 对其结构进行了重组 , 在此基础上利用快速傅 里叶变换 , 提出了 一种快速 离散小 波变换算法 , 并从理论上进行了 分析和论证 ; 与直接算法相比 , 可有效降低运算量 . 关键词 : 小波分析 ; 离散傅里叶变换 ; M allat 算法 ; 快速 离散小波变换 中图分类号 : T N911. 7: O 242 文献标识码 : A

A Fast Wavelet Transform Algorithm Based on Discrete Fourier Transform
XU Weiye SONG Yufei ZONG H ui
( Dept . of Comm unicat io ns Engineering, Nanjing Inst it ut e o f T echnolog y, Nanjing 210013, China)
Abstract: T he M ulti resolution analysis and M allat algo rithm of wav elet theory hav e been widely used in digital sig nal pr ocessing recent ly . H ow ever, if the sig nal deco mpo sitio n and r eco nstr uction are calculated in terms of t he a bov e mentioned alg o rithm, the com putatio nal complex ity w ill be v ery hug e. Based on t he analysis of the Discrete Four ier T ransfo rm and M allat alg or ithm pr inciple, a fast alg or ithm fo r Discrete Wav elet T ransfor m is pro posed, and has been pr oven valid in theor y. Co mpar ed w ith the direct method, it can reduce the computational co mplexity effectively . Key words: w avelet ana lysis; discr ete Four ier T ransf orm; M allat algo rithm; fast discrete w avelet transfor m

1 引言
小波分析近年来在数学界和信号处理领域中日益受到重视, 它继承和发展了窗口傅里叶变换的局部 化思想, 而且克服了窗口大小不随频率变化而改变, 缺乏离散正交基的缺点, 具有良好的时频局部化性 能, 是进行信号处理和分析的有效工具 . 1987 年 M allat 将计算机视觉领域内的多分辨率思想引入到小波 分析中, 提出了多分辨分析理论 , 并给出了完美的数学描述和一种子带滤波器机构的离散小波变换与 重构算法 Mallat 算法. 其本质是不需要知道尺度函数和小波函数的具体结构 , 由系数就可以实现信
[ 1]

收稿日期 : 2004- 10- 25 基金项目 : 南京工程学院科研基金项目 ( 科 04- 83) . 作者简介 : 徐伟业 ( 1977- ) , 女 , 研究生 , 助教 , 研究方向为数字通信 , 信号处理及数字电路分析 . E mail: xu w ei ye 2002@ 163. com

12

南京 工程学院学报 ( 自然科学版 )
[ 2]

2005 年 3 月

号的分解和重建 , 而且运用该算法可使信号每次分解时的长度减半 , 因而它是一种快速算法

. 但是如果

直接用该算法来计算信号的小波分解和重构 , 在信号长度较大的情况下 , 其运算量将会变得非常大, 从而 影响信号的实时处理 . 所以有必要对小波变换的快速算法作进一步研究. 本文在分析 M allat 算法结构特 点的基础上, 对其结构进行重组, 并结合离散傅里叶变换 ( DFT ) 相关知识, 提出了一种基于 DFT 的快速 离散小波变换算法, 该算法特别对长度较大的滤波器和信号非常有效. 与直接计算方法相比, 它可使运算 量大为下降, 这从相应的理论分析中得到了很好的证实 .

2 离散傅里叶变换及快速算法
离散傅立叶变换从理论上解决了傅立叶变换应用于实际的可能性, 是数字信号处理中一种非常有效 的变换方法, 它可通过相应的快速算法 , 即快速傅里叶变换 ( FF T ) 来实现 . 对于 M 长的有限长序列 x ( m) , 其 DF T 为
M- 1

X ( k) =
m= 0

x ( m) W M , k = 0 , 1, . . . , M - 1.

mk

( 1)

反变换( IDF T ) 为 x ( m) = 1 M
M- 1 M- 1

X ( k) W M
k= 0

- mk

=

[ 1 X * ( k) ] W mk M k= 0 M

*

, m = 0, 1, . . . , M - 1.

( 2)

从( 1 ) 式可看出: 计算每一个 X ( k) 有 M 次复乘, M - 1 次复加, 故完成整个运算总共需要 M 2 次复乘及 M( M - 1) 次复加. 由于( 2) 式与 ( 1) 式的差别只在于 W M 的指数符号不同, 以及差一个常数乘因子 , 故两 者的计算量相同 . FF T 算法的基本原理就是把一个 M 长 DF T 分解成两个 M / 2 长 DF T , 再把 M/ 2 长 DF T 分解成 M / 4 长 DF T , 再分解成 M / 8 长 DF T , 一直分解到长度为 2 的 DF T 为止 . 这种 M 为 2 的整数幂的 F FT 也称基 2 FF T , 它可使原有 DFT 的计算量大为减少 , 通过实际的理论推导[ 3] , 采用 F FT 计算 M 长 DFT , 计算量为 ( M/ 2 ) log 2 M 次复乘, M log 2 M 次复加. 鉴于一次复乘需要四次实乘和两次实加, 所以 F FT 相应的计算量 为 2M log 2 M 次实乘和 2 M log 2 M 次实加 . M 长 IDFT 也可由 IF FT 来完成 , 其计算量与 M 点 DF T 相同. 在 M 越大的情况下 , FF T 算法较之直接的 DF T 计算的优越性就越明显 [ 3] . 在实际信号处理中, 输入的数据 x ( m) 一般都是实序列 , 如果不采取特殊措施, 往往把 x ( m) 视为一个 虚部为 0 的复序列, 这就增加了运算的时间. 为此 , 文献 [ 4] 采用了分裂基( split - radix) FF T 算法来有效 降低相应的运算量 . 通过计算 , 对长度为 M = 2 m 的实数据信号 , 采用分裂基 F FT 后的计算量为 : 2m- 1 ( m 3) + 2 次实乘以及 2m- 1 ( 3m - 5) + 4 次实加 .

3

基于塔式分解的 M allat 算法
Mallat 于 1987 年把多分辨率思想引入到小波分析中, 提出了多分辨分析理论, 并给出了完美的数学

描述和一种子带滤波器机构的离散小波变换与重构算法 时的长度减半, 使得在实际应用中减少了小波变换的复杂度 示为

M allat 算法 , 运用该算法可使信号每次分解
[ 1]

, 因而它是一种快速算法. 其分解式子可表

第 3 卷第 1 期

徐伟业等 : 一种基于离散傅里 叶变换的小波变换的快速算法

13

c j+ 1 ( n) =
i z

c j ( i ) h( i - 2n) c j ( i ) g( i - 2n)
i z

( 3) ( 4)

d j+ 1 ( n) = 重构式子可表示为 cj ( n) =
i z

c j + 1 ( i) h( n- 2i ) + d j + 1 ( i) g( n - 2 i)

( 5)

在利用 M all at 快速算法进行信号分析时 , 常采用信号 f ( t) 的采样序列 f ( n t) ( 对时间归一化后表示 为 f ( n) ) 来近似为 c0 ( n) , 即 c0 ( n) = f ( n) . 由上述算法公式可知, 信号的小波分解和重建可通过子带滤 波的形式来实现. M allat 算法的塔式分解与重构如图 1 所示, 图中 , G, H 分别为分解滤波器组的高、 低通滤 波器 ; G 、 H 为重构滤波器组的高、 低通滤波器.

图1

基于 M allat 算法的小波分解与重构示意图

4

离散小波变换的快速算法
4. 1 离散小波变换算法结构及其重组

基于上面的分析 , 离散小波变换( DWT ) 及反变换可以用图 2、 图 3 的结构示意图来表示, 通过重复这 个结构可实现不同单元的分解和重构. 图 2 是小波变换的每个单元分解示意图 ( 为了便于分析, 这里用对 应的 z 变换来表达图 1 的变换关系 ) , H ( z ) 是低通滤波器, 它的输出经下采样被送入下一个单元进行进一 步处理. G( z ) 是高通滤波器 , 它的输出经下采样就是小波系数 . 图 3 是小波变换的重构示意图 , 前一个单 元的输出经上采样送入 H ( z ) ; 其结果与输出的结果相加, 以此进行该单元的信号重建, 重建后再进入下 一单元, 进行下一步处理 . 考虑到实际问题的需要 , 下面的分析将局限于实数据信号的 DWT 和等长度实 系数 F IR 滤波器 . 即 : f ( n) 为实信号序列; H , G 为等长度 ( 长度设定为 N ) 实系数滤波器 , 至于非等长情 况, 可通过补零方法来实现. 对于离散小波反变换 ( IDWT ) , 其对应于重构图, 如果是规范正交的情况, 可以对 DWT 流图作厄尔 密特 ( H ermit e) 转置得到; 如果不是 , 则 需要对 DWT 流图作 H ermit e 转置 , 同 时把滤波器系数 h( n) , g( n) , 用 h( n) , g( n) 来代替. 由此可见, IDWT 和 DWT 具有相同的运算复杂度. 在每个分解单元 , 信号经滤波器 G 的输出为小波变换后的细节信号 , 而滤波器 H 的输出作为小波变

14

南京 工程学院学报 ( 自然科学版 )

2005 年 3 月

图2

离散小波变换的分解示意图

图3

离散小波变换的重建示意图

换后的概貌信号被输入到下一个单元 [ 2] . 对每一输入, 实现滤波器 h( n) , g( n) 的滤波需要 2N 乘法和 2( N - 1) 次加法; 即每输入一点计算量为 2N 次实乘法 / 点 / 单元; 2( N - 1) 次实加法 / 点 / 单元 ; 由于下采 样因子的作用 , 第 j 个单元的输入减采样了倍, 总的运算量为( 1+ 2- 1 + 2- 2 + !+ 1/ 2 j- 1 = 2 ( 1- 2- j ) ) 次 , 即: 4 N ( 1 - 2- j ) 次乘法 / 点 ; 4 ( N - 1) ( 1 - 2- j ) 次加法 / 点 . 由此可见, 当 j 和 N 增加时, 特别是 N 比较 大时 , 这个计算量将明显增加 . 考虑到图 2 中两个 FI R 滤波器不是单独出现的 , 而是紧接着下抽样因子 , 所以有必要对图 2 进行结构 重组, 以此减少每个单元的运算 , 从而减小总的运算量 . 具体步骤如下 : 即先把输入序列 f ( n) 分为奇次和 偶次序列 , 然后使用 z 变换对其进行分解, 从而有以下表达式 F( z ) =
n

f ( n) z

- n

=
n

f ( 2 n) z

- 2n

+
n

f ( 2n + 1 ) z

- 2n- 1

= F0 ( z 2 ) + z- 1 F1 ( z 2 ) 其中 , F 0 ( z ) =
n

( 6) f ( 2n + 1) z
n - n

f ( 2n) z

-n

, F1 ( z ) =

然后再把滤波器 H , G 也同样地分成奇偶序列, 这样就可以得到本尺度单元的输出 R ( z ) , 即图 1 中的 c1 ( z ) , 具体表示为 F ( z ) H ( z ) = ( F0 ( z ) + z
2 - 1

F1 ( z ) ) ( H 0 ( z ) + z

2

2

-1

H 1 (z )) ( 7)

2

= F 0 ( z 2 ) H 0 ( z 2 ) + z - 2 F 1 ( z 2 ) H 1 ( z 2 ) + 奇次项 选出偶次项即为 R( z ) , 即:

第 3 卷第 1 期

徐伟业等 : 一种基于离散傅里 叶变换的小波变换的快速算法

15

R ( z ) = F0 ( z ) H 0 ( z ) + z 同样可求得小波系数 ( 即图 1 中的 d 1 ( z ) )

-1

F1 ( z ) H 1 ( z )

( 8)

d 1 ( z ) = F 0 ( z ) G 0 ( z ) + z - 1 F 1 ( z ) G1 ( z )

( 9)

通过重新组织后 , 偶次项 F 0 ( z ) 和奇次项 z - 1 F 1 ( z ) 作位输入 , 分别作用于H 0 ( z ) , H 1 ( z ) , 滤波后将各 自输出的两项相加就可得到 R( z ) ( 也即下一个尺度单元的输入 ) . 具体的流程图如图 4 所示, 与图 1 相比 , 这里使用了四个的滤波器 , 它们的滤波器系数由 H ( z ) 、 G( z ) 下抽样( 隔二取一 ) 而得.

图4

离散小波变换的结构重组

4. 2

离散小波变换的快速算法 从上一小节的分析来看, 直接计算图 4 中的滤波器作用过程 , 其计算量还是比较大, 特别是滤波器长

度比较大时将表现得更为明显 . 为此, 本文提出一种利用离散傅里叶变换的快速方法来计算小波分解与 重构的快速算法 , 该算法的原理如图 5 所示.

图5

基于 FF T 的快速小波变换算法原理图

考虑到两个序列信号的卷积可通过在频域的傅氏变换值相乘 , 然后再进行相应的傅氏反变换来实 现, 由此可降低运算量. 在此, 我们先把输入的数据 F( z ) 分成两个等长的下采样的输入块 , 计算各个输入 块的 FFT , 再和滤波器的 F FT 作乘积, 然后对乘积结果相加并作傅氏反变换 ( IFF T ) ; 为了避免截尾效应 , 如果滤波器的长度为 N/ 2, 输入块为 L / 2( L 为输入信号的长度 ) , 则卷积后的长度必须满足 M > L / 2 +

16

南京 工程学院学报 ( 自然科学版 )

2005 年 3 月

N / 2 - 2 , 可以取 L = 2M - ( N - 2) . 具体做法是首先把输入分成奇次项和偶次项, 对每个输入项, 使用 M 长度的 FF T , 然后分别同四个滤波器的傅氏变换值相乘, 再分别对应相加 , 最后再进行相应的 IFF T , 得到 所期望的小波变换输出 . 这需要 4M 次复乘和 2M 次复加 ; 以及两次 FF T 和两次 IF F T , 故有以下的计算量 2* M 长 F FT + 4M 复乘 + 2M 复加 + 2* M 长 IF FT ( 10)

这里 , 没有考虑到四个滤波器的傅氏变换 , 是因为这四个值在每次小波变换时是不变的 , 所以 , 可以 预先已求出, 以后不再计算它们的值, 从而也不再计入总的计算量. 考虑到一次复乘需要四次实乘和两次实加, 一次复加需要两次实加[ 3] , 以及第 2 节给出的实信号进行 FF T 的运算量 , 我们可求出上述计算量对应的实乘次数和实加次数. 即: [ ( m + 5) 2 m+ 1 + 8] / [ 2M - ( N 2) ] 实乘 / 点 / 单元 ; 以及 [ ( 3 m + 1) 2 m+ 1 + 16] / [ 2M - ( N - 2) ] 实加 / 点 / 单元. 在给定 N 时 , 可有最优 值 L = 2 M - ( N - 2) , 使得 M = 2 时, 上述计算量为最小 . 由此 , 可得基于 F FT 的快速算法的计算量与 直接计算时的计算量的比较, 如表 1 所示 . 从表中可看出所提快速算法的计算量要小于应用直接法时的计 算量 , 特别是滤波器长度较大时, 其效果越明显, 相对于直接法的运算效率也越高.
m

表1
滤 波器长度 / N 8 16 32 64 128 256 512 !

直接方法与快速算法的计算量比较 ( 次数 / 点 / 单元 )
直接计算方法 ( 实加和实 乘) 14+ 16 30+ 32 62+ 64 126+ 128 254+ 256 510+ 512 1022+ 1024 ! 快速 DWT 算法 ( 实加和实乘 ) 16. 62+ 11. 38 ( M = 16) 20. 80+ 12. 96 ( M = 32) 24. 98+ 14. 45 ( M = 64) 28. 48+ 14. 81 ( M = 256) 31. 95+ 15. 97 ( M = 512) 35. 40+ 17. 13 ( M = 1024) 38. 84+ 18. 28 ( M = 2048) !

5 结束语
综上所述, 在进行多分辩率分析时 , 应尽量在信号的小波变换近似过程中, 减少低通和高通滤波器长 度的差别 , 这样就可以有效地使用前面介绍的快速小波算法. 从文章的算法分析和推导过程可看出, 信号 的分解算法和重建算法的计算量主要取决于快速傅立叶变换以及逐点乘积, 而且它们有着很高的并行 度, 非常适应计算机及信息处理系统的并行体系, 从而可使计算量大大减少, 提高运行速度 . 而且对于一 般长度的 DF T , 当长度 L 含有较大素因子 , 可运用算术傅里叶变换 ( AF T ) 方法, 其运行速度比 FF T 快, 适 合 VL SI 设计 , 并在图像处理领域得到了广泛应用[ 5] . 但是, 我们也看到本文提出的快速算法有着一定的 局限性, 对长度较小的滤波器其效果不明显, 这主要是受限于 FF T , 它对长度较小的信号的运算效率不明

第 3 卷第 1 期

徐伟业等 : 一种基于离散傅里 叶变换的小波变换的快速算法

17

显. 另外没有考虑到有限长信号的边界问题, 当考虑到边界问题时, 算法效率将可能有所下降 .

参考文献 :
[ 1] S. M all at . A t heory f or mult iresolut ion signal decom posit ion: t he w avelet repres ent ati on. IEEE Transact ion on Pat t ern A nalys is and M achin e Int ell igence [ J] , 1989, 11( 4) : 674- 693. [ 2] [ 3] [ 4] 彭玉华 . 小波变换与工程应用 [ M ] . 北京 : 科学出版社 , 1999. 程佩青 . 数字信号处理教程 [ M ] . 北京 : 清华大学出版社 , 1998. P. D uhamel. Impl ement of split - radix FFT algorit hms f or compl ex, real, and real - symmet ric dat a. IEEE T ransact ion on A coust . , Speech , Si gnal Processing [ J] . 1986, 34 ( 4) : 285- 295. [ 5] H . par k and V . K . Prasanna. M odular V LSI archit ect ures f or com put ing t he arit hmetic f ourier t ran sform . IEEE Transact ion on Signal Processing [ J] . 1993, 41( 6) : 2236- 2246.

[ 责任编校: 胡可乐 ]


推荐相关:

一种基于离散傅里叶变换的小波变换的快速算法_图文.pdf

一种基于离散傅里叶变换的小波变换的快速算法 - 第 卷 第期年月 ( ) 南京工

一种基于离散傅里叶变换的小波变换的快速算法.pdf

小波分析的理解 13页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 一种基于离散傅里叶变换的小波变换的快速算法 ...

一种快速离散小波变换算法及其在语音信号中的应用_徐伟业.pdf

通过对 实序列的快速傅里叶变换 (FFT) 算法的推导及 Mallat 算法原理的分析, 根据离散小波变换算法结构特征, 提出了一种基于 FFT 的 快速离散小波变换算法, 并...

一种基于离散傅里叶变换的小波变换的快速算法_图文.pdf

一种基于离散傅里叶变换的小波变换的快速算法_信息与通信_工程科技_专业资料。一种

一种离散小波变换的快速分解和重构算法_虞湘宾.pdf

32 No. 4 July 2002 一种离散小波变换的快速分解和重构算法虞湘宾 董 涛 ( 东南大学无线电工程系 , 南京 210096) 摘要 : 通过对实序列的快速傅里叶变换算法...

小波变换快速算法及应用小结.doc

的快速算法 Mallat 算法[经典算法] 在小波理论中,多分辨率分析是一个重要的组成...基于 FFT 的小波变换快速算法是通过离散傅里叶变换建立起 FFT 和 mallat 算法...

一种基于离散傅里叶变换的频率测量算法.pdf

一种基于离散傅里叶变换的频率测量算法 - 对一种基于离散傅里叶变换(DFT)的频率测量算法进行了分析,该算法认为信号的频率偏移量在邻近的2个周期保持不变,因此在...

一种快速离散小波变换算法及其在语音信号中的应用.pdf

一种快速离散小波变换算法及其在语音信号中的应用_电子/电路_工程科技_专业资料...信号的小波分解和重构,其计算量将是很大的.通过对实序列的快速傅里叶变换(FFT...

一种快速离散小波变换算法及其在语音信号中的应用_免费....pdf

通过对 实序列的快速傅里叶变换 (FFT) 算法的推导及 Mallat 算法原理的分析, 根据离散小波变换算法结构特征, 提出了一种基于 FFT 的 快速离散小波变换算法, 并...

一种快速离散小波变换算法及其在语音信号中的应用_论文.pdf

通过对实序列的快速傅里叶变换(FFT)算法的推导)及Mallat算法原理的分析,根据离散小波变换算法结构特征,提出了一种基于FFT的快速离散小波变换算法,并 ...

基于递推离散傅里叶变换和同步采样的谐波电流实时检测....pdf

周期延时、计 算量大等不足,文章提出了一种基于离散傅里叶变换的快速 谐波...基于小波变换与人工神经网络的各种智能算法 也开始应用于谐波电流检测, 这些算法...

FFT与DWT(快速傅里叶变换和离散小波变换).doc

FFT与DWT(快速傅里叶变换离散小波变换)_信息与通信_工程科技_专业资料。一篇...而其意义远远超过了算法研究的范围, 进而为诸多科技领域的研究打开了一个崭新的...

傅里叶变换、离散余弦变换与小波变换.doc

傅里叶变换离散余弦变换与小波变换_计算机软件及应用...DFT 是一种基本和重要的正交变换。为了提高计算效率...二维离散小波变换逼近,并采用 Mallat 二维快速算法求...

小波变换与傅里叶变换的对比、异同.doc

经过 3 步,我们最终地得到了一个二进离散化稳定 的小波变换,这正是我们要的结果。 三、快速算法。 如果说现代数字信号处理革命算法,甚至是很多快速算法的老...

一种基于改进傅里叶变换的回弹补偿算法研究_图文.pdf

4改进的傅里叶算法为了实现频域模具修正算法,本文采用了小波变换将时域 下模具型面和冲压件型面形状数据变换为频域的参数表示形 式。由于计算机本质上只能处理离散...

快速傅里叶和小波变换.ppt

专题讲座小波变换 79页 免费 一种基于FFT计算离散小波变... 4页 8财富值...DFT的快速算法-快速傅里叶变换(FFT);同时简要介绍了FFT算法的发展历程;此外还要...

基于SRFFT算法的快速小波变换谐波检测法_论文.pdf

基于SRFFT算法的快速小波变换谐波检测法 - 为快速准确的提取谐波分量及克服传统的FFT方法无时域局部性的缺点,提出一种基于复序列加窗插值分裂基快速傅里叶变换算法(...

数字图像处理 第三章 图像变换.ppt

基于特征向量的变换: ? 从哈尔变换、短时傅里叶变换到小波变换。 ? 各种变换的定义和有关快速算法及实现方法。 ? Slide 3 3.1 ? 二维离散傅里叶变换(DFT) ...

快速傅里叶变换(FFT)与小波变换技术_图文.pdf

一种离散傅里 叶变换 的快 速算法 ,H 即(atorrrnPrtn,FsFui asti )才使得 D T的计 eToaoF 算工作量大为减少 . 为了表达傅里叶变换 的快速 算法 ,...

小波变换原理与基本案例分析_图文.pdf

利用加窗 Fourier(小波变换)分析几种典型的合成信号 4.观察分析窗函数,窗长...正变换数学描述 有限长序列通过离散傅里叶变换,并通过快速傅里叶变换算法 FFT ...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com