1. CSN
  2. All Volumes and Issues
  3. Number 857, 2016
  4. Review the algorithms of the efficient computation of dft based on cyclic convolutions

Review the algorithms of the efficient computation of dft based on cyclic convolutions

CSN.
2016;
, Number 857
: pp. 82 - 87
https://doi.org/10.23939/csn2016.857.082
Authors:
  1. Ihor Protsko
1
Lviv State University of Life Safety Department of Information Security Management

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.

fast discrete transform of Fourier class
cyclic convolution
hashing array
  1. R. E. Blahut, Fast Algorithms for Signal Processing, Cambridge University Press, 2010.
  2. Goldberg LM, Matyushkin BD, Polyak M.N., Digital Signal Processing: A Handbook. -M .: Radio and communication, 1985. -312 p.
  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 SM, Number Theory in Digital Signal Processing, Prentice Hall, Englewood Cliffs, NJ, 1979.
  6. Goertzel G. -An algorithm for the evaluation of a 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. - EIEE Trans. Audio Electroacoustic., 1970, v.AU-18, pp. 451-545.
  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 a computer to solve problems in physics." In Applications of Digital Computers, Boston: Ginn and Co., 1963.
  10. Rabiner L., Gould B. Theory and the application of digital signal processing. - M .: Mir, 1978. -848s.
  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. Nussbaumer G. J. Fast Fourier Transform and Convertor Calculating Algorithms. -M .: Radio and Communications, 1985. - 248 p.
  15. Float D.P., Park 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. Gagarin Yu. I., Recursive Fourier Transform Through Convolution. Problems of information transfer. Volume XXV, Ex. 4, 1989, p.93-95.
  17. Muddhasani DP, Wagh MD, "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. 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. Protsko, "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, p. 4, pp. 301-308, 2014.
  23. I. Protsko, R. Rikma, V. Teslyuk, The program for the synthesis of the efficient algorithms for the computation of DCT-II through cyclic convolutions. Proceeding of the IXth International Scientific and Technical Conference (CSIT'2014), Lviv, 18-22 November, 2014. - P.116-118.