Automatic generation of the efficient algorithms of DCT-II based on cyclic convolutions.

: pp. 120 - 124
Lviv Polytechnic National University, Lviv, Ukraine
Lviv Polytechnic National University Department of Informational Systems and Technology

Program of efficient implementation the discrete cosine transform of type-II using cyclic convolutions have been considered. The stages of automatic code generation the algorithms for the computation of DCT-II an arbitrary size N have been determined. The algorithm of DCT-II presents a better program performance for short sizes of transform, than known FFTW library.

  1. Prots'ko I., Rykmas R. Becoming of Discrete Harmonic Transform Using Cyclic Convolutions, American Journal of Circuits, Systems and Signal Processing. vol. 1, no. 3, pp. 114–119, 2015.
  2. Winograd S. On computing the discrete Fourier transform, in Proc. Nat. Acad. Sci. USA, vol. 73, no. 4, pp. 1005–1006, April 1976, Mathematics.
  3. Blahut R. E. Fast algorithms for signal processing. Cambridge University Press, 2010. – 469 p.
  4. Nussbaumer Henri J. Fast Fourier Transform and Convolution Algorithms, by Springer-Verlag, Berlin, Heidelberg, 1982.
  5. FFTW Homepage. URL:
  6. Spiral Homepage. URL:
  7. Nukada A., Nukada FFT library. Web site. 2011. URL: ̃nukada/nufft/
  8. NVIDIA. CUFFT libray. Fetched March 23, 2012. 2701 San Tomas Expressway, Santa Clara, CA 95050, 2012.
  9. Math Kernel Library. Accessed May 14, 2012. URL:
  10. Gacic A., Voronenko Y., Chen K., Johnson R. W., Rizzolo N. SPIRAL: Code generation for DSP transforms // Proceedings of the IEEE, – 2005. – Vol. 93. – No. 2. – P. 232–275, special issue on "Program Generation, Optimization".
  11. Prots'ko I. The generalized technique of computation the discrete harmonic transforms. Proceedings of the IVth International Conference (MEMSTECH'2008). – Polyana, 21–24 may, 2008. – P. 101–102.
  12. Prots'ko I. Ukraine Patent 96540, G06F 17/16 (2006.01), H03M 7/30 (2006.01).
  13. Prots'ko I. Algorithm of Efficient Computation of DCT I-IV Using Cyclic Convolutions, International Journal of Circuits, Systems and Signal Processing,vol. 7, issue 1, pp. 1–9, 2013.
  14. Prots'ko I., Rykmas R., Teslyuk V. The program implementation of the synthesis the efficient algorithms for computation of DCT-II via cyclic convolutions. Proceedings of the IXth International Scientific and Technical Conference (CSIT'2014). – Lviv, 18–22 november, 2014. – P. 116–118.
  15. Frigo M., Johnson S. G. The design and implementation of FFTW3 Proc. IEEE, vol. 93, no. 2, pp. 216–231, Feb. 2005. Lviv Polytechnic National University Institutional Repository
Protsko I. Automatic generation of the efficient algorithms of DCT-II based on cyclic convolutions / I. Protsko, R. Rykmas // Visnyk Natsionalnoho universytetu "Lvivska politekhnika". Serie: Kompiuterni systemy ta merezhi. — Lviv : Vydavnytstvo Lvivskoi politekhniky, 2017. — No 881. — P. 120–124.