[01] Ihor Prots’ko, Department of Civil Security, Lviv State University of Life Safety, Lviv, Ukraine. [02] Roman Rykmas, LtdC “Uniservice”, Lviv, Ukraine.

The enumeration approaches of efficient computation discrete transform of Fourier class using cyclic convolutions is considered. The formulation of the basis matrix of transforms into the block cyclic structures is described of each approach. The analysis of the advantages and imperfections of the algorithms are discussed.

Discrete Transform of Fourier Class, Cyclic Convolution, Efficient Algorithms

[01] C. Runge, “Uber die Zerlegung empirisch gegebener periodischer Funcktionen іn Sinnuswellen”, Z. Math. Physik, vol. 48, pp. 443-456, 1903. [02] G. C. Danielson, and C. Lanczos, “Some Improvements in Practical Fourier Analysis and Their Application to X-Ray Scattering from Liquids”, J. Franklin Institute, vol. 233, 1942. [03] J. W. Cooley, J. W. Tukey, “An Algorithm for the Machine Computation of Complex Fourier Series”, Math. Comp. 19, pp. 297-301, 1965. [04] I. J. Good, “The interaction algorithm and practical Fourier analysis”, J. Roy. Stat. Soc. B-20, pp. 361-372, 1958; vol. 22, pp. 372-375, 1960. [05] L. H. Thomas, “Using of computer to solve problems in physics”. -In Applications of digital computers, Boston: Ginn and Co., 1963. [06] R. Yavne, “An economical method for calculating the discrete Fourier transform”, AFIPS conference proceedings, vol.33, part 1 (Thompson book co., Washington, D.C.,) pp.115-125, 1968. [07] S. Winograd, “On computing the discrete Fourier transforms”, Mathematics of Computation, vol. 32, pp. 175-199, 1978. [08] O. K. Ersoy, Fourier - related transforms, fast algorithms and applications, Prentice Hall, Upper Saddle River, NJ, 1997. [09] G. Bongiovanni, P. Corsini, and G. Frosini, “One-dimensional and two-dimensional generalized discrete Fourier transforms”, IEEE Trans. Acoust., Speech, Signal Processing, Feb., vol. ASSP-24, pp. 97–99, 1976. [10] C. M. Rader, “Discrete Fourier transform when the number of data samples is prime”, Proc. IEEE 56, pp. 1107-1108, 1968. [11] R. Tolimiery, M. An, C. Lu, Algorithms for Discrete Fourier Transform and Convolution, New York, Springer –Verlag, 1997 (s.ed.). [12] G. Goertzel, “An algorithm for the evaluation of finite trigonometric series”, Amer. Math. Monthly, V.65, pp. 34-35, Jan. 1958. [13] L. I. Bluestein, “Linear filtering approach to the computation of discrete Fourier transforms”, IEEE Trans. Audio Electroacoust., v.AU-18, pp.451-455, 1970. [14] J. H. McClellan, С. М. Rader, Number Theory in Digital Signal Processing, Prentice Hall, Englewood Cliffs, NJ, 1979. [15] D. P. Kolba, T. W. Parks, “A Prime Factor FFT Algorithm Using High Speed Convolution”, IEEE Trans, on Acoustics, Speech, and Signal Processing ASSP-25, pp. 281-294, 1977. [16] J. S. Ward, Number theoretic techniques applied to algorithms and architectures for digital signal processing, Durham theses, Durham University (1983). [17] D. P. V. Muddhasani, M. D. Wagh, “Bilinear algorithms for discrete cosine transforms of prime lengths”, Signal Processing, vol. 86, no. 9, pp. 2393-2406, 2006. [18] P. K. Meher, “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] M. Püschel and J. M. F. Moura, “The Algebraic Approach to the Discrete Cosine and Sine Transforms and their Fast Algorithms”, SIAM Journal of Computing, vol. 32, no. 5, pp. 1280-1316, 2003. [20] Y. H. Chan, W. C. Siu, “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. [21] M. D. Wagh, H. Ganesh, “A new algorithm for the discrete cosine transform of arbitrary number of points”, IEEE Trans. on Computers, C-29 (4), pp. 269-277, 1980. [22] 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. [23] 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. [24] M. N. Murty “Realization of Prime-Length Discrete Sine Transform Using Cyclic Convolution”, International Journal of Engineering Science and Technology (IJEST), vol. 5, no.03, pp. 583-589, 2013. [25] 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. [26] R-X. Yin and W-C. Siu, “A new fast algorithm for computing prime-length DCT through cyclic convolutions”, Signal Processing, vol. 81, no. 5, pp. 895-906, May. 2001. [27] C. Cheng and K. K. Parthi, “A novel systolic array structure for DCT”, IEEE Trans. Circuits Syst.II, Exp. Briefs, vol.52, no.7, pp.366-369, Jul.2005. [28] D.-F. Chiper, M. N. S. Swamy, M. O. Ahmad, and T. Stouraitis, “Systolic algorithms and a memory-based design approach for a unified architecture for the computation of DCT/DST/IDCT/IDST,” IEEE Trans. Circuits Syst.I, Reg. Papers, vol.52, no.6, pp.1125-1137, Jun.2005. [29] P. K. Meher, J. C. Patra and M. N. S. Swamy, “High-throughput memory-based architecture for DHT using a new convolutional formulation,” IEEE Trans. Circuits Syst. II, vol. 54, no. 7, pp. 606-610, July 2007.