Швидке перетворення Фур’є (ШПФ), з часів появи алгоритму Кулі– Тюкі, займає важливу нішу у величезному інформаційно-технічному просторі сучасних імплементацій. Загалом оцінити важливість та вплив алгоритму Кулі – Тюкі на розвиток різних сфер науки – неймовірно складне завдання. В публікації розглянуто передумови та історичне становлення алгоритму Кулі – Тюкі як фундаментального алгоритму швидкого перетворення Фур’є. Розглянуто розвиток досліджень ШПФ у напрямі розроблення ефективних алгоритмів гармонічного аналізу, що привели до вагомих результатів, підтверджених численними публікаціями. Виділено основні напрями фор- малізації ШПФ та підкреслено багатоваріантність ефективних обчислень. Відзначено важливість взаємо- доповнювального впливу ШПФ на становлення високопродуктивних обчислювальних апаратних засобів. Адже саме розвиток нових методів та технічних можливостей для прискорення виконання ШПФ визначив архітектурні особливості сучасних мікропроцесорів як високоефективних засобів реалізації обчислень. Зазначено, що розвиток програмного забезпечення уможливив створення надійних і дуже швидких програмних систем для виконання перетворень класу Фур’є на різних комп’ютерних платформах та цифрових сигнальних процесорах. У публікації здійснено огляд розвитку ключових аспектів ШПФ у світовій практиці опрацювання сигналів та розроблення засобів ШПФ львівськими науково-дослідними установами за шістдесят років існування алгоритму Кулі – Тюкі. В ОКБ ЕІВТ ЛПІ, ще до появи швидкого алгоритму Кулі – Тюкі обчислення перетворення Фур’є, почали розробляти цифрові спектроаналізатори. Результатом розробок у 1983–1984 рр. став випуск серійних аналізаторів спектра (приблизно 200 зразків), параметри яких перевищували характеристики аналізаторів всесвітньо відомої фірми “Bruel&Kjaer” (Данія). Засоби ШПФ, розроблені у Львівському науково-дослідному радіотехнічному інституті, у Фізико-механічному інституті НАН України, дали змогу успішно використовувати їх для радіо- локаційних станцій, для наукових досліджень у космосі тощо.
Незважаючи на виконані аналізи значущості ШПФ, нові теоретичні результати все ще з’являються, завдяки прогресу в комп’ютерній сфері й апаратному забезпеченні постійно оновлюються основні завдання з використання ШПФ, а нові програми перетворень класу Фур’є розширюють сфери для прикладних досліджень.
[1] Cooley, J. W., & Tukey, J. W. (1965). An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation, 19(90), 297–301. https://doi.org/10.2307/ 2003354
[2] Cipra, B. A. (2000). The best of the 20th century: Editors name top 10 algorithms. SIAM news, 33(4), 1–2.
[3] Heideman, M. T., Johnson, D. H., & Burrus, C. S. (1985). Gauss and the history of the FFT. Archive for History of Exact Sciences, 34(3), 265–277. https://doi.org/10.1007/BF00348431
[4] Runge, C. (1903). On the decomposition of empirically given periodic functions into sine waves. Zeitschrift für Mathematik und Physik, 48, 443–456.
[5] Danielson, G. C., & Lanczos, C. (1942). Some improvements in practical Fourier analysis and their application to X-ray scattering from liquids. Journal of the Franklin Institute, 233(1), 45–52. https://doi.org/10.1016/S0016-0032(42)90767-1
[6] Good, I. J. (1960). The interaction algorithm and practical Fourier analysis: An addendum. Journal of the Royal Statistical Society: Series B (Methodological), 22(2), 372–375. https://doi.org/ 10.1111/j.2517-6161.1960.tb00384.x
[7] Thomas, L. H. (1963). Using of computer to solve problems in physics. In R. E. Rosser (Ed.), Applications of digital computers (pp. 67–83). Boston: Ginn and Co.
[8] Yates, F. (1937). The design and analysis of factorial experiments (Technical Communication No. 35). Harpenden, England: Imperial Bureau of Soil Science
[9] Butler, J. L., & Lowe, R. (1961). Beam forming matrix simplifies design of electronically scanned antennas. Electronic Design, 9(8), 170–173.
[10] Rabiner, L. R., & Gold, B. (1975). Theory and application of digital signal processing. Englewood Cliffs, NJ: Prentice-Hall.
[11] Oppenheim, A. V., & Schafer, R. W. (1975). Digital signal processing. Englewood Cliffs, NJ: Prentice-Hall.
[12] Yuan, W., Hao, P., & Xu, C. (2006). Matrix factorization for fast DCT algorithms. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (Vol. 3, pp. 948–951). IEEE. https://doi.org/10.1109/ ICASSP.2006.1660812
[13] Malvar, H. S. (1986). Fast computation of discrete cosine transform through fast Hartley transform. Electronics Letters, 22(7), 352–353. https://doi.org/10.1049/el:19860239
[14] Wang, Z.-D. (1982). A fast algorithm for the discrete sine transform implemented by the fast cosine transform. IEEE Transactions on Acoustics, Speech, and Signal Processing, 30(5), 814–815. https://doi.org/10.1109/TASSP.1982.1163963
[15] Vetterli, M., & Nussbaumer, H. J. (1984). Simple FFT and DCT algorithms with reduced number of operations. Signal Processing, 6(4), 267–278. https://doi.org/10.1016/0165- 1684(84)90059-8
[16] Lee, B. G. (1989). Input and output index mappings for a prime- factor decomposed computation of discrete cosine transform. IEEE Transactions on Acoustics, Speech, and Signal Processing, 37(2), 237–244.
[17] Pollard, J. M. (1971). The fast Fourier transform in a finite field. Mathematics of Computation, 25(114), 365–374. https://doi.org/ 10.1090/S0025-5718-1971-0301966-0
[18] Rader, C. M. (1968). Discrete Fourier transforms when the number of data samples is prime. Proceedings of the IEEE, 56(6), 1107–1108.
[19] Goertzel, G. (1958). An algorithm for the evaluation of finite trigonometric series. The American Mathematical Monthly, 65(1), 34–35.
[20] Nussbaumer, H. J. (1982). Fast Fourier transform and convolution algorithms (Vol. 2). Springer-Verlag. https://doi.org/10.1007/978-3-642-81897-4
[21] Rao, K. R., & Yip, P. (1990). Discrete cosine transform: Algorithms, advantages, applications (1st ed.). Academic Press.
[22] Duhamel, P. (1986). Implementation of split-radix FFT algorithms for complex, real, and real-symmetric data. IEEE Transactions on Acoustics, Speech, and Signal Processing, 34(2), 285–295. https://doi.org/10.1109/TASSP.1986.1164811
[23] Bracewell, R. N. (1983). The discrete Hartley transform. Journal of the Optical Society of America, 73(12), 1832–1835. https://doi.org/10.1364/JOSA.73.001832
[24] Nicholson, P. J. (1971). Algebraic theory of finite Fourier transforms. Journal of Computer and System Sciences, 5(5), 524–527.
[25] Martens, J.-B. (1984). Recursive cyclotomic factorization – a new algorithm for calculating the discrete Fourier transform. IEEE Transactions on Acoustics, Speech, and Signal Processing, 32, 750–762.
[26] Sorensen, H. V., Jones, D. L., Burrus, C. S., & Heideman, M. T. (1985). On computing the discrete Hartley transform. IEEE Transactions on Acoustics, Speech, and Signal Processing, 33(5), 1231–1238. https://doi.org/10.1109/TASSP. 1985.1164687
[27] Ahmed, N., Natarajan, T., & Rao, K. R. (1974). Discrete cosine transform. IEEE Transactions on Computers, 23(1), 90–93. https://doi.org/10.1109/T-C.1974.223784
[28] Jain, A. (1976). A Fast Karhunen-Loeve Transform for a Class of Random Processes. IEEE Transactions on Communications, 24(9), 1023–1029. https://doi.org/10.1109/TCOM.1976. 1093409
[29] Yavne, R. (1968). An economical method for calculating the discrete Fourier transform. Proceedings of the December 9–11, 1968, Fall Joint Computer Conference, Part I, 115–125. https://doi.org/10.1145/1476589.1476610
[30] Chan, S. C., & Ho, K. L. (1991). On indexing the prime-factor fast Fourier transform algorithm. IEEE Transactions on Circuits and Systems, 38(8), 951–953. https://doi.org/10.1109/31.85638 14 Ukrainian Journal of Information Technology, 2025, vol. 7, No. 1
[31] Bi, G., Zeng, Y., & Chen, Y. Q. (2001). Prime factor algorithm for multidimensional discrete cosine transform. IEEE Transactions on Signal Processing, 49(9), 2156–2161. https://doi.org/ 10.1109/78.942642
[32] Duhamel, P., & Hollmann, H. (1984). Split-radix FFT algorithm. Electronics Letters, 20(1), 14–16. https://doi.org/ 10.1049/ el:19840012
[33] Gilan, M. S., & Maham, B. (2024). Optimized power and speed of Split-Radix, Radix-4 and Radix-2 FFT structures. EURASIP Journal on Advances in Signal Processing, 2024(81). https://doi.org/10.1186/s13634-024-01178-4
[34] Blahut, R. E. (1985). Fast algorithms for digital signal processing. Reading, MA: Addison-Wesley.
[35] Winograd, S. (1976). On computing the discrete Fourier transforms. Proceedings of the National Academy of Sciences of the United States of America, 73(4), 1005–1006. https://doi.org/10.1073/pnas.73.4.1005
[36] McClellan, J. H., & Rader, C. M. (1979). Number theory in digital signal processing. Englewood Cliffs, NJ: Prentice Hall.
[37] Britanak, V., & Rao, K. R. (1999). The fast generalized discrete Fourier transforms: A unified approach to the discrete sinu- soidal transforms computation. Signal Processing, 79, 135–150.
[38] Hou, N. C., Chang, H. I., & Ersoy, O. K. (1992). Generalized discrete Hartley transform. IEEE Transactions on Signal Processing, 40(12), 2931–2940. https://doi.org/10.1109/78. 175737
[39] Britanak, V., Yip, P. C., & Rao, K. R. (2007). Discrete cosine and sine transforms: General properties, fast algorithms and integer approximations. Academic Press.
[40] Oppenheim, A. V., & Schafer, R. W. (1989). Discrete-time signal processing. Upper Saddle River, NJ: Prentice Hall.
[41] Gold, B., Lebow, I. L., McHugh, P. G., & Rader, C. M. (1971). The FDP, a fast programmable signal processor. IEEE Transactions on Computers, C-20(1), 33–38. https://doi.org/ 10.1109/T-C.1971.223078
[42] Rabiner, L. R., & Gold, B. (1975). Theory and application of digital signal processing. Prentice-Hall. [43] Sophie, G. R., & Chen, W. (1993). Fast Fourier transform on Motorola’s implementation on digital signal processors (Appli- cation Note No. 4). Motorola, Inc. https://www. bitsavers.org/ components/motorola/56000/ APPNOTES/ APR4.PDF
[44] Stallings, W. (2019). Computer organization and architecture: Designing for performance (11th ed.). Pearson Education.
[45] FFTW. (n.d.). FFTW: Fastest Fourier Transform in the West. Retrieved from http://www.fftw.org/
[46] Püschel, M., Singer, B., Xiong, J., Moura, J. M. F., Johnson, J., Padua, D., Veloso, M., Johnson, R. W. (2004). SPIRAL: A generator for platform-adapted libraries of signal processing algorithms. Journal of High Performance Computing and Applications, 18(1), 21–45. https://doi.org/10.1177/ 1094342004041291
[47] Du, P., Weber, R., Luszczek, P., Tomov, S., Peterson, G., & Dongarra, J. (2012). From CUDA to OpenCL: Towards a performance-portable solution for multi-platform GPU programming. Parallel Computing, 38(8), 391–407. https://doi.org/10.1016/ j.parco.2011.10.002
[48] Intel. (2017). Intel Math Kernel Library. Intel Press.
[49] Taylor, S. (2014). Intel integrated performance primitives: How to optimize software applications using Intel IPP. Intel Press.
[50] Nukada, A., & Matsuoka, S. (2010). Nukada FFT: An auto- tuning FFT library for CUDA GPUs. In Proceedings of the GPU Technology Conference, Research Summit Poster (San Jose, CA, USA).
[51] Frigo, M., & Johnson, S. G. (1997). The fastest Fourier transform in the West (Technical Report MIT-LCS-TR-728). Laboratory for Computer Science, MIT, Cambridge, MA.
[52] Burrus, C. S. (Ed.). (2008). Fast Fourier transforms. Rice University. [53]. Розенблат, М. Ш. (1977). Алгоритмічні та апаратні методи підвищення ефективності спектроаналізаторів, використо- вуючих швидке перетворення Фур’є [Algorithmic and hardware methods for improving the performance of spectrum analyzers using fast Fourier transform] (Автореферат дисертації на здобуття вченого ступеня кандидата технічних наук). Фізико-механічний інститут, Львів.
[54] Розенблат, М. Ш., & Швецкий, Б. Й. (1973). Об одном методе вычисления дискретного преобразования Фурье [A method for calculating the discrete Fourier transform]. Автометрия, 3, 23–32.
[55] Розенблат, М. Ш., & Швецкий, Б. Й. (1975). Об одном алгоритме быстрого преобразования Фурье [A fast Fourier transform algorithm]. Автоматика и телемеханика, 4, 138– 147.
[56] Yatsimirskij, M. N. (1992). Fast Hartley transform by Rader- Brenner method. Radiotekhnika, 1–2, 66–70.
[57] Yatsimirskij, M. N. (1993). Fast algorithms for the discrete cosine transformation. Computational Mathematics and Mathematical Physics, 33(2), 267–270.
[58] Погрібной, В. А. (1982). Дельта-модуляция в аппаратурном спектральном анализе [Delta modulation in hardware spectral analysis]. Радиотехника и электроника, 27(7), 1352–1361.
[59] Погрібной, В. А., & Яковлев, В. П. (1986). Реализация дискретного преобразования Фурье с дельта-модуляцией [Implementation of discrete Fourier transform with delta modulation]. Известия вузов СССР. Серия Радиоэлектро- ника, 29(5), 60–65.
[60] Погрібной, В. А. (1990). Дельта-модуляция в цифровой обработке сигналов [Delta modulation in digital signal processing]. Радио и связь.
[61] Ланцов, А. Л., & Дунець, Р. Б. (1985). Устройство микропрограмного управления [Device for microprogram control]. А. С. 1151961, Бюл. No 5, 1151961.
[62] Ланцов, А. Л. (1985). Устройство для вывода информации [Device for information output]. А. С. 1167614, Бюл. No 26, 1167614.
[63] Ланцов, А. Л. (1985). Устройство для связи в много- процессорной системе [Device for communication in a multiprocessor system]. А. С. 1180914, Бюл. No 30, 1180914.
[64] Prots’ko, I. (2013). Algorithm of efficient computation of DCT I-IV using cyclic convolutions. International Journal of Circuits, Systems and Signal Processing, 7(1), 1–9.
[65] Prots’ko, I. (2014). Algorithm of efficient computation of generalized discrete Hartley transform based on cyclic convolutions. IET Signal Processing, 4(4), 301–308. https://doi.org/10.1049/iet-spr.2013.0204
[66] Prots’ko, I., & Mishchuk, M. (2021). Block-cyclic structuring of the basis of Fourier transforms based on cyclic substitution. Cybernetics and Systems Analysis, 57(6), 1008–1016. https://doi.org/10.1007/s10559-021-00426-x
[67] Prots’ko, I., & Teslyuk, V. (2014). Algorithm of efficient computation DSTI-IV using cyclic convolutions. WSEAS Transactions on Signal Processing, 10, 278–288.
[68] Guo, J. I., Liu, C.-M., & Jen, C.-W. (2024). Unified array architecture for discrete cosine transform, sine transform and their inverses. Electronics Letters, 31(21), 1811–1812. https://doi.org/ 10.1049/el:19951254
[69] Xue, S., Qiu, W., Liu, F., & Jin, X. (2020). Faster image super- resolution by improved frequency-domain neural networks. Signal, Image and Video Processing, 14(2), 257–265. https://doi.org/10.1007/s11760-019-01548-8
[70]Zhang, H., & Ma, J. (2020). Hartley spectral pooling for deep learning. CSIAM Transactions on Applied Mathematics, 1(3), 518–529. https://doi.org/10.48550/ arXiv.1810.04028
[71] Lin, J., & Yao, Y. (2019). A fast algorithm for convolutional neural networks using tile-based fast Fourier transforms. Neural Processing Letters, 50, 1951–1967. https://doi.org/10.1007/ s11063-019-09981-z
[72] Zhang, J., Liao, Y., Zhu, X., Wang, H., & Ding, J. (2020). A deep learning approach in the discrete cosine transform domain to median filtering forensics. IEEE Signal Processing Letters, 27, 276–280. https://doi.org/10.1109/LSP.2020.2966888
[73] Bao, J., Zhang, J., Zhang, C., & Bao, L. (2025). DCTCNet: Sequency discrete cosine transform convolution network for visual recognition. Neural Networks, 185, 107143. https://doi.org/ 10.1016/j.neunet.2025.107143