Розвиток алгоритму Вінограда перетворення Фур’є на базі твірного масиву
Date
2017-03-28
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Видавництво Львівської політехніки
Abstract
Розглянуто загальну методику ефективного обчислення ДПФ за допомогою
циклічних згорток для обсягів, що дорівнюють цілому степеню два. Проаналізовано
подальший розвиток алгоритму Вінограда перетворення Фур’є (WFTA). Застосовано
твірний масив для стислого опису блочно-циклічної структури базисної матриці ДПФ.
Визначено загальну блочно-циклічну структуру дискретної базисної матриці та
обчислювальні затрати для ДПФ обсягів N = 2n.
The general technique of efficient computation DFT using of cyclic convolutions for sizes of integer power of two is considered. Further development of Winograd Fourier transform algorithm (WFTA) is analyzed. The hashing array for the compacting definition of the blockcyclic structure the basis matrix of DFT is proposed. The general block-cyclic structure of discrete basis matrix for the computation of DFT of sizes N=2n is determined.
The general technique of efficient computation DFT using of cyclic convolutions for sizes of integer power of two is considered. Further development of Winograd Fourier transform algorithm (WFTA) is analyzed. The hashing array for the compacting definition of the blockcyclic structure the basis matrix of DFT is proposed. The general block-cyclic structure of discrete basis matrix for the computation of DFT of sizes N=2n is determined.
Description
Keywords
швидке перетворення Фур’є (ШПФ), циклічна згортка, твірний масив, fast Fourier transform, cyclic convolution, hashing array
Citation
Процько І. Розвиток алгоритму Вінограда перетворення Фур’є на базі твірного масиву / І. Процько, Р. Рикмас // Вісник Національного університету «Львівська політехніка». Серія: Комп’ютерні науки та інформаційні технології. — Львів : Видавництво Львівської політехніки, 2017. — № 864. — С. 291–299.