1. CSN
  2. Всі випуски
  3. Номер 857, 2016
  4. Огляд алгоритмів ефективного обчислення дпф на основі циклічних згорток

Огляд алгоритмів ефективного обчислення дпф на основі циклічних згорток

CSN.
2016;
, Номер 857
: с. 82 - 87
https://doi.org/10.23939/csn2016.857.082
Автори:
  1. Ігор Процько
1
Львівський державний університет безпеки життєдіяльності, кафедра управління інформаційною безпекою

Розглянуто підходи ефективного обчислення дискретних перетворень класу Фур’є на основі циклічних згорток. Описано сутність переформулювання базисних матриць перетворення ДПФ на блочно-циклічні структури для кожного підходу. Аналізуються переваги і недоліки алгоритмів для кожного підходу.

швидке перетворення класу Фур’є (ШПФ)
циклічна згортка
твірний масив
  1. R. E. Blahut, Fast Algorithms for Signal Processing, Cambridge University Press, 2010.
  2. Гольденберг Л. М., Матюшкин Б. Д., Поляк М. Н., Цифровая обработка сигналов: Справочник. – М.: Радио и связь, 1985. – 312 с.
  3. Rader C. M., Discrete Fourier transform when the number of data samples is prime. Proc.IEEE 56, 1968, p. 1107–1108.
  4. R. Tolimiery, M. An, C. Lu, Algorithms for Discrete Fourier Transform and Convolution, New York, Springer –Verlag, 1997 (s.ed.).
  5. McClellan J. H., Rader С. М., Number Theory in Digital Signal Processing, Prentice Hall, Englewood Cliffs, NJ, 1979.
  6. Goertzel G. – An algorithm for the evaluation of finite trigonometric series. – Amer. Math. Mon., 1968, v.65, p. 34–35.
  7. Bluestein L. I. Linear filtering approach to the computation of discrete Fourier transforms. –IEEE Trans. Audio Electroacoust., 1970, v.AU-18, p. 451–455.
  8. Good I. J., “The interaction algorithm and practical Fourier analysis”, J. Roy. Stat. Soc. B-20, pp. 361–372, 1958; vol. 22, pp. 372–375, 1960.
  9. Thomas L. H., “Using of computer to solve problems in physics”. -In Applications of digital computers, Boston: Ginn and Co., 1963.
  10. Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов. – М.: Мир, 1978. – 848 с.
  11. Winograd S., “On computing the discrete Fourier transforms”, Proc. Nat. Acad. Sci. USA, vol. 73, pp. 1005–1006, 1976.
  12. Zohar S., “Faster Fourier Transformation: The Algorithm of S. Winograd”, Jet Propulsion Laboratory JPL Publication 78-104, under NASA Contract No. NAS7-100, pp. 1–93, February 15, 1979.
  13. Winograd S., “On computing the discrete Fourier transforms”, Mathematics of Computation, vol. 32, pp. 175–199, 1978.
  14. Нуссбаумер Г. Дж. Быстрое преобразование Фурье и алгоритмы вычисления сверток. –М.: Радио и связь, 1985. – 248 c.
  15. Kolba D. P., Parks T. W., “A Prime Factor FFT Algorithm Using High Speed Convolution”, IEEE Trans, on Acoustics, Speech, and Signal Processing ASSP-25, pp. 281–294, 1977.
  16. Гагарин Ю. И., Рекурсивное преобразование Фурье через свертки. Проблемы передачи информации. – 1989. – Т. XXV, Вып. 4, C. 93–95.
  17. Muddhasani D. P. V., Wagh M. D., “Bilinear algorithms for discrete cosine transforms of prime lengths”, Signal Processing, vol. 86, no. 9, pp. 2393–2406, 2006.
  18. Meher P. K., “Systolic designs for DCT using a low complexity concurrent convolutional formulation”, IEEE Trans. Circuits & Systems for Video Technology, vol. 16, no. 10, pp.1041–1050, 2006.
  19. Chan Y. H., Siu W. C., “Generalized approach for the realization of discrete cosine transform using cyclic convolutions”, in: Intl. Conf. on Acoustics, Speech and Signal Processing ICASSP’93, vol. 3, pp. 277–280, 1993.
  20. Wagh M. D., Ganesh H., “A new algorithm for the discrete cosine transform of arbitrary number of points”, IEEE Trans. on Computers, C-29 (4), pp. 269–277, 1980.
  21. I. Prots’ko, “Algorithm of Efficient Computation of DCT I-IV Using Cyclic Convolutions”, International Journal of Circuits, Systems and Signal Processing, vol. 7, is. 1, pp. 1–9, 2013.
  22. I. Prots’ko, “Algorithm of efficient computation of generalized discrete Hartley transform based on cyclic convolutions”, IET Signal Processing, vol.4, is. 4, pp. 301–308, 2014.
  23. I. Prots’ko, R. Rikmas, V. Teslyuk, The program implementation of the synthesis the efficient algorithms for computation of DCT-II via cyclic convolutions. Proceeding of the IXth International Scientific and Technical Conference (CSIT’2014), Lviv, 18-22 November 2014. – P. 116–118.