Study of the reduced competent algorithm compared to a set of convolution algorithms

A.Yu. Bavrina, V.V. Myasnikov

Image Processing Systems Institute оf the RAS

Full text of article: Russian language.

Abstract:

Reduction and build-up operations for the reduced competent algorithm compared to a set of existing sophisticated algorithms are investigated. As actual reference-set algorithms, we use a direct convolution algorithm and the best-known algorithms based on discrete fast orthogonal transformations (with Cooley-Tukey and Good-Thomas decomposition, Raider algorithm for high-frequency waves.) It is shown that their joint use provided by the reduced competent algorithm may lower computational complexity of the generated convolution algorithm with respect to reference-set algorithms.

Key words:

convolution, computational complexity, fast orthogonal transformations, reduced competent algorithm.

Citation:Bavrina AYu, Myasnikov VV. Study of the reduced competent algorithm compared to a set of convolution algorithms [In Russian]. Computer Optics 2008; 32(1): 64-67.

References:

- Myasnikov VV. On the synthesis of the efficient algorithm over the set of the convolution algorithms [In Russian]. Computer Optics 2006; 29: 78-117.
- Rabiner LRB. Gold Theory and applications of digital signal processing. New Jersey: Prentice-Hall, Inc. Englewood Cliffs 1975.
- Nussbaumer HJ. Fast Fourier Transform and Convolution Algorithms. Heidelberg, Germany: Springer 1990; 276 pp.
- Blahut RE. Fast Algorithms for Digital Signal Processing. Reading, MA: Addison-Wesley Inc. 1984.

© 2009, ИСОИ РАН

Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: ko@smr.ru ; тел: +7 (846) 332-56-22, факс: +7 (846 2) 332-56-20