有限长度离散子波变换的快速算法

本文提出了一种有限长度离散子波变换的结构化算法，分析和综合滤波矩阵Ｈ、Ｇ可以分解成循环矩阵和下三角矩阵的Ｋｒｏｎｅｃｋｅｒ积．循环矩阵用ＦＦＴ实现，而下三角矩阵直接实现。算法的计算复杂性优于全ＦＦＴ实现。由于二维离散子波变换的滤波矩阵可以分解成一维离散子波变换矩阵的Ｋｒｏｌｌｅｃｋｅｒ积，所以，本算法可以方便地推广到二维离散子波变换。

THE FAST ALGORITHM FOR THE FINITE LENGTH DISCRETE WAVELET TRANSFORM

This paper presents a structured algorithm for the finite length discrete wavelet transform. The analysis and synthesis filter matrices H, G can be decomposed in kronecker product form with cyclic block matrix and lower-triangle block matrix. The cyclic matrix can be implemented using FFT and the lower-triangle matrix is implemented sthaightforward. The atithmetic complexity of the algorithm is prior to the full-FFT implementation. Since the filter matrix of two-dimensional discrete wavelet transform can be separated into the kronecker product of the filter matrices of one-dimensional discrete Wavelet transform, the algorithm can also be extended to the two-dimensional discrete Wavelet transform conveniently.