Aleksandr Cariow; Galina Cariowa

Algorithmic Tricks for Reducing the Complexity of FDWT/IDWT Basic Operations Implementation

Full Text (PDF, 620KB), PP.1-9

Views: 0 Downloads: 0

Author(s)

Aleksandr Cariow ^1,* Galina Cariowa ¹

1. Faculty of Computer Science and Information Technology, West Pomeranian University of Technology, Szczecin, Poland

* Corresponding author.

DOI: https://doi.org/10.5815/ijigsp.2014.10.01

Received: 30 May 2014 / Revised: 10 Jul. 2014 / Accepted: 13 Aug. 2014 / Published: 8 Sep. 2014

Index Terms

Discrete wavelet transform, fast algorithms, matrix notation

Abstract

In this paper two different approaches to the rationalization of FDWT and IDWT basic operations execution with the reduced number of multiplications are considered. With regard to the well-known approaches, the direct implementation of the above operations requires 2L multiplications for the execution of FDWT and IDWT basic operation plus 2(L-1) additions for FDWT basic operation and L additions for IDWT basic operation. At the same time, the first approach allows the design of the computation procedures, which take only 1,5L multiplications plus 3,5L+1 additions for FDWT basic operation and L+1 multiplications plus 3,5L additions for IDWT basic operation. The other approach allows the design of such computation procedures, which require 1,5L multiplications, plus 2L-1 addition for FDWT basic operation and L+1 addition for IDWT basic operation.

Cite This Paper

Aleksandr Cariow, Galina Cariowa,"Algorithmic Tricks for Reducing the Complexity of FDWT/IDWT Basic Operations Implementation", IJIGSP, vol.6, no.10, pp.1-9, 2014. DOI: 10.5815/ijigsp.2014.10.01

Reference

[1]Mallat S. G., A theory for multiresolution signal decomposition: The wavelet representation, IEEE Trans. Patt. Anal. Mach. Intell., vol. 11, pp. 674-693, July 1989.

[2]Daubechies I., Ten lectures on Wavelets, SIAM, Philadelphia, PA, 1992.

[3]Chui C. K., Montefusco L., Puccio L. Wavelets: Theory, Algorithms and Applications, Academic Press, New York, 1994.

[4]Vetterli M., Kovačević J. Wavelets and Subband Coding, Prentice Hall PTR, Englewood Cliffs, 1995.

[5]Stollnitz E. J., DeRose A. D., Salesin D. H. Wavelets for Computer Graphics, Morgan Kaufmann, 1996.

[6]Burrus C. S., Gopinath R. A. Intoduction to Wavelets and Wawelets Transforms: A Primer, Prentice Hall, New Jersey, 1998.

[7]Goswami J. C., Chan A. K. Fundamentals of Wavelet: Theory, Algorithms and Applications. Wiley-Interscience, New York, 1999.

[8]Debnath L. Wavelet Transforms and Their Applications, Birkhauser, 2001.

[9]Frazier M. W., An Introduction to Wavelets through Linear Algebra, Springer-Verlag, New York, 2001.

[10]Cohen A. Numerical Analysis of Wavelet Methods. Studies in Mathematics and Its Applications, Elsevier Science B.V. Printed in the Netherlands, 2003.

[11]Weeks M., Bayoumi M. Discrete Wavelet Transforms: Architectures, Design and Performance Issues, Journal of VLSI Signal Processing, 2003, no. 35, pp. 155-178.

[12]Ţariov A., Ţariova G, Majorkowska-Mech D. Algorithms for multilevel decomposition and reconstruction of Digital signals, Commission of Informatics, Polish Academia of Science (Gdansk branch) Press, 2012. (in Polish).

[13]Ţariov A. Algorithmic aspects of computing rationalization in digital signal processing”. West Pomeranian University of Technology Press, (2011), 232 p. (in Polish).

[14]Winograd S. A new algorithm for inner product. IEEE Trans. Computers, vol. C-17, pp. 693-694, 1968.

[15]Regalia Ph. A. and Mitra S. K. Kronecker Products, Unitary Matrices and Signal Processing Applications, SIAM Review, vol. 31, no. 4, pp. 586-613, 1989.

International Journal of Image, Graphics and Signal Processing (IJIGSP)