Аналіз похибки обчислення швидких перетворень класу Фур'є на підставі циклічних згорток
Date
2020-09-23
Journal Title
Journal ISSN
Volume Title
Publisher
Видавництво Львівської політехніки
Abstract
Проаналізовано особливості обчислювальної моделі дискретних перетворень класу Фур'є на підставі циклічних
згорток для визначення алгоритмічної похибки розрахунку. На підставі підходу ефективного обчислення дискретного
перетворення класу Фур'є довільного обсягу N, що ґрунтується на використанні твірного масиву для переформування
дискретної базисної матриці перетворення у набір блочно-циклічних під матриць, розглянуто складові обчислювальних
затрат. Ці складові обчислювальних затрат залежать від виду перетворення, обсягу та від блочно-циклічної структури ядра
перетворення. Подано приклади обчислювальної моделі та блочно-циклічної структури матриць спрощених аргументів
базисів для взаємозворотних дискретних косинусних перетворень типів ІІ, ІІІ. Обчислювальна модель характеризує
накопичення похибок округлення на етапах додавання вхідних даних, обчислення циклічних згорток, об'єднання
результатів згорток. Дискретні циклічні згортки можуть бути реалізовані за допомогою швидких алгоритмів або виді систем, що
відповідають цифровим фільтрам зі скінченними імпульсними характеристиками. Можливість паралельного обчислення
зменшеної кількості циклічних згорток робить аналіз похибок нечутливим до переупорядкування їх обчислень. Операції
множення, що здійснюється при обчисленні циклічної згортки, використовують меншу кількість коефіцієнтів базису
перетворення, що дорівнює N/4 або N/2 залежно від обсягу перетворення. Розглянуто формати представлення дійсних
чисел в обчислювальній систем, що також визначають величину похибки обчислення перетворень. Подано результати
виконання прямого та швидкого обчислення дискретного косинусного перетворення типу ІІ на підставі циклічних згорток
обсягом N=58 у форматі з рухомою крапкою подвійної точності та похибки обчислення між ними. Апріорний процес
дослідження похибок перетворення відповідного виду та обсягу методом математичного моделювання та
обчислювального експерименту носить наближений характер, який дає змогу передбачити статистичні середні значення точності
обчислення дискретного перетворення класу Фур'є довільного обсягу на підставі циклічних згорток.
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.
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.
Description
Keywords
дискретні косинусні перетворення, похибка алгоритму, блочно-циклічна структура, циклічна згортка, обчислювальна модель, discrete cosine transform, algorithm error, block-cyclic structure, cyclic convolution, computational model
Citation
Процько І. О. Аналіз похибки обчислення швидких перетворень класу Фур'є на підставі циклічних згорток / І. О. Процько, Д. В. Островка // Український журнал інформаційних технологій. — Львів : Видавництво Львівської політехніки, 2020. — Том 2. — № 1. — С. 52–56.