Самарский государственный аэрокосмический университет им. С.П. Королева,
Институт систем обработки изображений РАН

Аннотация:
В работе исследуются операция приведения и операция построения приведенного компетентного алгоритма над множеством известных алгоритмов постоянной сложности. В качестве известных алгоритмов опорного множества используются алгоритм прямого вычисления свертки и наиболее известные алгоритмы на основе быстрых дискретных ортогональных преобразований (с декомпозицией Кули-Тьюки и Гуда-Томаса, алгоритм Рейдера для коротких длин). Показано, что совместное их использование, которое дает приведенный компетентный алгоритм, позволяет снизить вычислительную сложность формируемого алгоритма вычисления свертки даже по отношению к наилучшим алгоритмам опорного множества.

Литература:

1. Мясников В.В. О синтезе эффективного алгоритма над множеством алгоритмов вычисления свертки // Компьютерная оптика, 2006. В. 29. С. 78-117.
2. L.R. Rabiner, B. Gold Theory and applications of digital signal processing // New Jersey: Prentice-Hall, Inc. Englewood Cliffs, 1975.
3. H.J. Nussbaumer Fast Fourier Transform and Convolution Algorithms // Heidelberg, Germany: Springer, 1990. P. 276.
4. R.E. Blahut Fast Algorithms for Digital Signal Processing // Reading, MA: Addison-Wesley Inc., 1984.

---

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