1. UJIT
  2. All Volumes and Issues
  3. Volume 2 · Number 1
  4. ANALYSIS OF THE ERROR OF COMPUTATION FAST TRANSFORMS OF FOURIER CLASS BASED ON CYCLIC CONVOLUTIONS

ANALYSIS OF THE ERROR OF COMPUTATION FAST TRANSFORMS OF FOURIER CLASS BASED ON CYCLIC CONVOLUTIONS

UJIT.
2020;
Volume 2, Number 1
: 52-56
https://doi.org/10.23939/ujit2020.02.052
Received: September 03, 2020
Accepted: October 25, 2020

Цитування за ДСТУ: Процько І. О., Островка Д. В. Аналіз похибки обчислення швидких перетворень класу Фур'є на підставі циклічних згорток. Український журнал інформаційних технологій. 2020, т. 2, № 1. С. 52–56.

Citation APA: Protsko, I. O., & Ostrovka, D. V. (2020). Analysis of the error of computation fast transforms of Fourier class based on cyclic convolutions. Ukrainian Journal of Information Technology, 2(1), 52–56. https://doi.org/10.23939/ujit2020.02.052

Authors:
  1. I. O. Protsko
  2. D. V. Ostrovka
1
Lviv Polytechnic National University, Lviv, Ukraine
2
Lviv Polytechnic National University, Lviv, Ukraine

The features of the computational model of discrete transforms of Fourier class based on cyclic convolutions to determine the algorithmic calculation error are analyzed. Based on the approach of efficient computation of discrete transforms of Fourier class of arbitrary size N, using of a hashing array to transform a discrete basis matrix into a set of block-cyclic submatrices, the components of computational costs are considered. These components of computational costs depend on the type of transform, the size and the block-cycle structure of the transformation core. Examples of computational model and block-cyclic structure of matrices of simplified arguments of basis functions for mutually inverse discrete cosine transforms of types II, III are given. The computational model characterizes the accumulation of rounding errors at the stages of adding input data, computing cyclic convolutions, combining the results of convolutions. Discrete cyclic convolutions can be implemented using fast algorithms or a type of system that corresponds to digital filters with finite pulse characteristics. The possibility of parallel computation of the reduced number of cyclic convolutions makes the analysis of errors insensitive to rearrangement of their computations. The multiplication operations performed when computing the cyclic convolution uses a smaller number of basis coefficients equal to N/4 or N/2 depending on the size of transform. The formats of representation of real numbers in computer systems are considered, which also determine the magnitude of the computational error of transforms. The results of direct and fast computation of discrete cosine transform of type II based on cyclic convolutions with size N=58 in the format wit floating point of double precision and computation error between them are presented. The apriori process of studying the transform errors of the corresponding type and size by the method of mathematical modeling and computational experiment is approximate, which allows to predict the statistical averages of the accuracy of computing the discrete Fourier transform of arbitrary size based on cyclic convolutions.

discrete cosine transform
algorithm error
block-cyclic structure
cyclic convolution
Computational model
  1. Blahut, R. E. (2010). Fast algorithms for signal processing. Cambridge: University Press.
  2. Cooley, J. W., & Tukey, J. W. (1965). An Algorithm for the Machine Computation of Complex Fourier Series. Math. Comput., 19, 297–301.
  3. FFTW. (2020). Homepage. Retrieved from: http://fftw.org
  4. Frigo, M. (1999). A Fast Fourier Transform Compiler. Proceedings of the 1999 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), Atlanta, Georgia, 169–180.
  5. Kaneko, T., & Liu, B. (1970). Accumulation of roundoff error in Fast Fourier Transform. Journal Assoc. Comput. Machine, 17, 637–654.
  6. McClellan, J. H. Rader, C. M. (1979). Number Theory in Digital Signal Processing. Inc. Englewood Cliffs, New Jersey: Brentice-Hall.
  7. Meher, P. K. (2006). Systolic designs for DCT using a low complexity concurrent convolutional formulation. IEEE Trans. Circuits & Systems for Video Technology, 16(10), 1041–1050.
  8. Muddhasani, D. P. V., & Waghm, M. D. (2006). Bilinear algorithms for discrete cosine transforms of prime lengths. Signal Processing, 86(9), 2393–2406.
  9. Oppenheim, A. V. Schafer, R. W. (1999). Digital Signal Processing. Inc. Englewood Cliffs, New Jersey: Brentice-Hall.
  10. Prots'ko, I. (2008). The generalized technique of computation the discrete harmonic transforms. Proceedings of the IVth International Conference of Young Scientists (MEMSTECH'2008). Poljana, 101–102. https://doi.org/10.1109/MEMSTECH.2008.4558753
  11. 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.
  12. Rader, C. M. (1968). Discrete Fourier transform when the number of data samples is prime. Proc. IEEE, 56, 1107–1108.
  13. Tolimiery, R., An, M. Lu, C. (1997). Algorithms for Discrete Fourier Transform and Convolution. Edition second (2nd). New York: Springer.
  14. Weinstein, C. J. (1969). Roundoff noise in floating point Fast Fourier transform computation, IEEE Trans. Audio Electroacoustics, AU-17, 209–215.
  15. Winograd, S. (1976). On computing the discrete Fourier transforms. Proc. National Academy of Sciences USA, 73(4), 1005–1006.