The Wavelet-Based DFT: A New Interpretation, Extensions and Applications

Authors: Abdulnasir Hossen, Ulrich Heute

Abstract:

In 1990 [1] the subband-DFT (SB-DFT) technique was proposed. This technique used the Hadamard filters in the decomposition step to split the input sequence into low- and highpass sequences. In the next step, either two DFTs are needed on both bands to compute the full-band DFT or one DFT on one of the two bands to compute an approximate DFT. A combination network with correction factors was to be applied after the DFTs. Another approach was proposed in 1997 [2] for using a special discrete wavelet transform (DWT) to compute the discrete Fourier transform (DFT). In the first step of the algorithm, the input sequence is decomposed in a similar manner to the SB-DFT into two sequences using wavelet decomposition with Haar filters. The second step is to perform DFTs on both bands to obtain the full-band DFT or to obtain a fast approximate DFT by implementing pruning at both input and output sides. In this paper, the wavelet-based DFT (W-DFT) with Haar filters is interpreted as SB-DFT with Hadamard filters. The only difference is in a constant factor in the combination network. This result is very important to complete the analysis of the W-DFT, since all the results concerning the accuracy and approximation errors in the SB-DFT are applicable. An application example in spectral analysis is given for both SB-DFT and W-DFT (with different filters). The adaptive capability of the SB-DFT is included in the W-DFT algorithm to select the band of most energy as the band to be computed. Finally, the W-DFT is extended to the two-dimensional case. An application in image transformation is given using two different types of wavelet filters.

Keywords: Image Transform, Spectral Analysis, Sub-Band DFT, Wavelet DFT.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1332744

References:

[1] Mitra, S.; Petraglia, M.; and Shentov, O.: ''DFT Calculation via Subband Decomposition'', Proc. of Eusipco 1990, pp. 501-504, 1990.
[2] Guo, H.; Burrus, C. S.: ''Wavelet Transform Based Fast Approximate Fourier Transform'', Proc. of ICAASP-1997, Munich, Germany.
[3] Oppenheim, A. V.; Schafer, R. W.: ''Discrete-Time Signal Processing'', Prentice-Hall, 1989.
[4] Shentov, O.; Mitra, S.; Heute, U.; Hossen, A.: ''Sub-band DFT-Part I: Definition, Interpretation and Ex-tensions'', Signal Processing, Vol.41, no.3, Feb. 1995, pp.261-277.
[5] Hossen, A.; Heute, U.; Shentov, O.; and Mitra, S.: ''Subband DFT-Part II: Accuracy, Complexity, and Applications'', Signal Processing, Vol. 41, no.3, Feb. 1995, pp.279-294.
[6] Hossen, A.; Heute, U.: ''Fully Adaptive Evaluation of SB-DFT'', Proc. of IEEE Int. Symp. on Circuits and Systems (ISCAS), Chicago, Illinois, pp.655-658, 1993.