Аналіз похибки обчислення швидких перетворень класу Фур'є на підставі циклічних згорток

Simple item page
dc.citation.epage56
dc.citation.issue1
dc.citation.journalTitleУкраїнський журнал інформаційних технологій
dc.citation.spage52
dc.citation.volume2
dc.contributor.affiliationНаціональний університет “Львівська політехніка”
dc.contributor.affiliationLviv Polytechnic National University
dc.contributor.authorПроцько, І. О.
dc.contributor.authorОстровка, Д. В.
dc.contributor.authorProtsko, I. O.
dc.contributor.authorOstrovka, D. V.
dc.coverage.placenameЛьвів
dc.coverage.placenameLviv
dc.date.accessioned2022-05-24T11:10:11Z
dc.date.available2022-05-24T11:10:11Z
dc.date.created2020-09-23
dc.date.issued2020-09-23
dc.description.abstractПроаналізовано особливості обчислювальної моделі дискретних перетворень класу Фур'є на підставі циклічних згорток для визначення алгоритмічної похибки розрахунку. На підставі підходу ефективного обчислення дискретного перетворення класу Фур'є довільного обсягу N, що ґрунтується на використанні твірного масиву для переформування дискретної базисної матриці перетворення у набір блочно-циклічних під матриць, розглянуто складові обчислювальних затрат. Ці складові обчислювальних затрат залежать від виду перетворення, обсягу та від блочно-циклічної структури ядра перетворення. Подано приклади обчислювальної моделі та блочно-циклічної структури матриць спрощених аргументів базисів для взаємозворотних дискретних косинусних перетворень типів ІІ, ІІІ. Обчислювальна модель характеризує накопичення похибок округлення на етапах додавання вхідних даних, обчислення циклічних згорток, об'єднання результатів згорток. Дискретні циклічні згортки можуть бути реалізовані за допомогою швидких алгоритмів або виді систем, що відповідають цифровим фільтрам зі скінченними імпульсними характеристиками. Можливість паралельного обчислення зменшеної кількості циклічних згорток робить аналіз похибок нечутливим до переупорядкування їх обчислень. Операції множення, що здійснюється при обчисленні циклічної згортки, використовують меншу кількість коефіцієнтів базису перетворення, що дорівнює N/4 або N/2 залежно від обсягу перетворення. Розглянуто формати представлення дійсних чисел в обчислювальній систем, що також визначають величину похибки обчислення перетворень. Подано результати виконання прямого та швидкого обчислення дискретного косинусного перетворення типу ІІ на підставі циклічних згорток обсягом N=58 у форматі з рухомою крапкою подвійної точності та похибки обчислення між ними. Апріорний процес дослідження похибок перетворення відповідного виду та обсягу методом математичного моделювання та обчислювального експерименту носить наближений характер, який дає змогу передбачити статистичні середні значення точності обчислення дискретного перетворення класу Фур'є довільного обсягу на підставі циклічних згорток.
dc.description.abstractThe 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.
dc.format.extent52-56
dc.format.pages5
dc.identifier.citationПроцько І. О. Аналіз похибки обчислення швидких перетворень класу Фур'є на підставі циклічних згорток / І. О. Процько, Д. В. Островка // Український журнал інформаційних технологій. — Львів : Видавництво Львівської політехніки, 2020. — Том 2. — № 1. — С. 52–56.
dc.identifier.citationenProtsko I. O. Analysis of the error of computation fast transforms of Fourier class based on cyclic convolutions / I. O. Protsko, D. V. Ostrovka // Ukrainian Journal of Information Technology. — Lviv : Vydavnytstvo Lvivskoi politekhniky, 2020. — Vol 2. — No 1. — P. 52–56.
dc.identifier.urihttps://ena.lpnu.ua/handle/ntb/56902
dc.language.isouk
dc.publisherВидавництво Львівської політехніки
dc.relation.ispartofУкраїнський журнал інформаційних технологій, 1 (2), 2020
dc.relation.ispartofUkrainian Journal of Information Technology, 1 (2), 2020
dc.relation.references[1] Blahut, R. E. (2010). Fast algorithms for signal processing. Cambridge: University Press.
dc.relation.references[2] Cooley, J. W., & Tukey, J. W. (1965). An Algorithm for the Machine Computation of Complex Fourier Series. Math. Comput., 19, 297–301.
dc.relation.references[3] FFTW. (2020). Homepage. Retrieved from: http://fftw.org
dc.relation.references[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.
dc.relation.references[5] Kaneko, T., & Liu, B. (1970). Accumulation of roundoff error in Fast Fourier Transform. Journal Assoc. Comput. Machine, 17, 637–654.
dc.relation.references[6] McClellan, J. H. Rader, C. M. (1979). Number Theory in Digital Signal Processing. Inc. Englewood Cliffs, New Jersey: Brentice-Hall.
dc.relation.references[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.
dc.relation.references[8] Muddhasani, D. P. V., & Waghm, M. D. (2006). Bilinear algorithms for discrete cosine transforms of prime lengths. Signal Processing, 86(9), 2393–2406.
dc.relation.references[9] Oppenheim, A. V. Schafer, R. W. (1999). Digital Signal Processing. Inc. Englewood Cliffs, New Jersey: Brentice-Hall.
dc.relation.references[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
dc.relation.references[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.
dc.relation.references[12] Rader, C. M. (1968). Discrete Fourier transform when the number of data samples is prime. Proc. IEEE, 56, 1107–1108.
dc.relation.references[13] Tolimiery, R., An, M. Lu, C. (1997). Algorithms for Discrete Fourier Transform and Convolution. Edition second (2nd). New York: Springer.
dc.relation.references[14] Weinstein, C. J. (1969). Roundoff noise in floating point Fast Fourier transform computation, IEEE Trans. Audio Electroacoustics, AU-17, 209–215.
dc.relation.references[15] Winograd, S. (1976). On computing the discrete Fourier transforms. Proc. National Academy of Sciences USA, 73(4), 1005–1006.
dc.relation.referencesen[1] Blahut, R. E. (2010). Fast algorithms for signal processing. Cambridge: University Press.
dc.relation.referencesen[2] Cooley, J. W., & Tukey, J. W. (1965). An Algorithm for the Machine Computation of Complex Fourier Series. Math. Comput., 19, 297–301.
dc.relation.referencesen[3] FFTW. (2020). Homepage. Retrieved from: http://fftw.org
dc.relation.referencesen[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.
dc.relation.referencesen[5] Kaneko, T., & Liu, B. (1970). Accumulation of roundoff error in Fast Fourier Transform. Journal Assoc. Comput. Machine, 17, 637–654.
dc.relation.referencesen[6] McClellan, J. H. Rader, C. M. (1979). Number Theory in Digital Signal Processing. Inc. Englewood Cliffs, New Jersey: Brentice-Hall.
dc.relation.referencesen[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.
dc.relation.referencesen[8] Muddhasani, D. P. V., & Waghm, M. D. (2006). Bilinear algorithms for discrete cosine transforms of prime lengths. Signal Processing, 86(9), 2393–2406.
dc.relation.referencesen[9] Oppenheim, A. V. Schafer, R. W. (1999). Digital Signal Processing. Inc. Englewood Cliffs, New Jersey: Brentice-Hall.
dc.relation.referencesen[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
dc.relation.referencesen[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.
dc.relation.referencesen[12] Rader, C. M. (1968). Discrete Fourier transform when the number of data samples is prime. Proc. IEEE, 56, 1107–1108.
dc.relation.referencesen[13] Tolimiery, R., An, M. Lu, C. (1997). Algorithms for Discrete Fourier Transform and Convolution. Edition second (2nd). New York: Springer.
dc.relation.referencesen[14] Weinstein, C. J. (1969). Roundoff noise in floating point Fast Fourier transform computation, IEEE Trans. Audio Electroacoustics, AU-17, 209–215.
dc.relation.referencesen[15] Winograd, S. (1976). On computing the discrete Fourier transforms. Proc. National Academy of Sciences USA, 73(4), 1005–1006.
dc.relation.urihttp://fftw.org
dc.relation.urihttps://doi.org/10.1109/MEMSTECH.2008.4558753
dc.rights.holder© Національний університет “Львівська політехніка”, 2020
dc.subjectдискретні косинусні перетворення
dc.subjectпохибка алгоритму
dc.subjectблочно-циклічна структура
dc.subjectциклічна згортка
dc.subjectобчислювальна модель
dc.subjectdiscrete cosine transform
dc.subjectalgorithm error
dc.subjectblock-cyclic structure
dc.subjectcyclic convolution
dc.subjectcomputational model
dc.titleАналіз похибки обчислення швидких перетворень класу Фур'є на підставі циклічних згорток
dc.title.alternativeAnalysis of the error of computation fast transforms of Fourier class based on cyclic convolutions
dc.typeArticle

Files

Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
2020v2n1_Protsko_I_O-Analysis_of_the_error_of_52-56.pdf
Size:
1.32 MB
Format:
Adobe Portable Document Format
Download
No Thumbnail Available
Name:
2020v2n1_Protsko_I_O-Analysis_of_the_error_of_52-56__COVER.png
Size:
1.85 MB
Format:
Portable Network Graphics
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.83 KB
Format:
Plain Text
Description:
Download

Collections

Ukrainian Journal of Information Technology. – 2020. – Vol. 2, No. 1