New algorithms for the radix-3 fast W transform(-Ⅱ,Ⅲ)

The discrete W transform (DWT)is a new type of real orthogonal transform.The commonly used DWT has four different versions, namely DWT-j,j=Ⅰ,Ⅱ, Ⅲ, Ⅳ. Inthis paper new radix-3 fast algorithms are proposed for the length-3^m DWT(-Ⅱ,Ⅲ). First,The radix-3 fast algorithms of the DWT-Ⅱ and DWT-Ⅲ are derived respectively and theircomputational complexity is analyzed. Then,a comparison is made with the direct algorithmand radix-2 fast algorithm. Finally,the signal flowgraphs for the radix-3 fast W transform(-Ⅱ, Ⅲ)for the length N=3² are given. Compared with direct algorithms, the radix-3 fastalgorithms greatly reduce the arithmetic operations and can be comparable to the radix-2 fastalgorithm. The can allow in-place computation and are numerically stable. The simple andregular structure makes it easy to be implemented. The proposed algorithms extend theapplicability of the fast W transform algorithm.