离散W变换-Ⅱ的一种快速递归算法

A Fast Recursive Algorithm for the Discrete W Transform- Ⅱ

离散W变换(DWT)是一种新型的实正交变换。具有一定对称特性与反对称特性的离散W变换有四种类型,即DWT-j,j=Ⅰ,Ⅱ,Ⅲ,Ⅳ,它们均可用于数字信号处理。本文首先导出了DWT-Ⅱ的递归特性,由此提出了计算长度-2~m离散W变换-Ⅱ(DWT-Ⅱ)的一种新算法——快速递归算法。该算法由两个同阶的低阶DWT-Ⅱ直接形成较高阶的DWT-Ⅱ。文中给出了长度为2~1,2~2,2~2,2~4的DWT-Ⅱ快速递归算法的信号流图,列出了DWT-Ⅱ的直接算法与快速递归算法所需的实乘次数、实加次数以及实乘和实加总次数。本文提出的算法不仅大大减少了计算DWT-Ⅱ的运算量,而且具有数值稳定、结构简单规则、易于硬件或软件实现等优点。本文对促进DWT的实际应用也有重要价值。

Discrete W transform (DWT) is a new type of real orthogonal transform. It has four different versions .which have the properties of symmetry and antisymmetry, namely, DWT- j, j= Ⅰ, Ⅱ , Ⅲ . Ⅳ . All of them find applications in digital signal processing. In this paper the recursive property is first derived and then a new fast recursive algorithm for computing the length- 2m DWT- Ⅱ is suggested. This algorithm allows us to generate the next high-order DWT- Ⅱ from two identical lower-order DWT- Ⅱ 's. Given in this paper are the signal flow graphs of the length - 21, 22,23, 24 DWT- I fast recursive algorithm,and the number of arithmetic operations required by the direct algorithm and the fast recursive algorithm. The suggested algorithm requires much fewer arithmetic operations and is numerically stable. Besides,the very simple and regular struture of the algorithm suggested makes it easy to be implemented either by hardware or by software. This paper is also valuable in stimulating the practical applications of DWT.