Development of WFTA based on the hashing array

Abstract

EN: method of efficient computation of DFT using cyclic convolutions for sizes of integer power of two has been considered. The further development of Winograd Fourier transform algorithm based on a hashing array has been proposed. The research object is the process of the reformulation the basis matrix of DFT into the block-cyclic structures. The research subject lays in the technique of the reformulation the basis matrix of DFT for sizes of integer power of two into the block-cyclic structures. Objective. The purpose of the work is the analysis of the structure specifics the left-circulant submatrices of the basis square matrix WN for sizes of transform N = 2i using the hashing arrays. Method. The article considers a technique for the efficient computation of DFT using cyclic convolutions for sizes of integer power of two, which is based on the cyclic decomposition of substitution. A hashing array has been proposed for the compressed description of the block-cyclic structure of discrete basis matrix and for the efficient computation of DFT for sizes of integer power of two. Results. A generalized block-cyclic structure of discrete basis matrix for the efficient computation of DF using cyclic convolutions for sizes of an integer power of two based on the hashing arrays has been determined. The proposed technique is relevant for concurrent programming of DFT and for its implementation in parallel systems. Conclusions. A general block-cyclic structure of basis matrix of DFT is regularly formed with an increase in the value of the exponent of two and is recommended for use in practice when developing the efficient means of DFT. The prospects for further research will include the formation of block-cyclic structure of basis matrix of DFT for arbitrary sizes. UK: Актуальність. Розглянуто метод ефективного обчислення ДПФ з використанням циклічних згорток для обсягів цілої степені два. Проаналізовано подальший розвиток Алгоритму Вінограда перетворення Фур’є на основі твірного масиву. Об’єктом дослідження є процес реформулювання базисної матриці ДПФ в блочно-циклічні структури. Предмет дослідження полягає в методі реформулювання базисної матриці ДПФ обсягів цілої степені два в блочно-циклічні структури. Мета роботи полягає в проведенні аналізу особливостей розміщення ліво-циркулянтних підматриць в структурі базисної квадратної матриці WN для обсягів перетворення N = 2i на основі використання твірних масивів. Метод. У статті розглядається методика ефективного обчислення ДПФ з використанням циклічних згорток для обсягів рівних цілій степені два, що базується на циклічному розкладі підстановки. Запропоновано застосування твірного масиву для стислого опису і обчислення блочно-циклічної структури дискретної базисної матриці ДПФ обсягів цілої степені два. Результати. Визначено загальну блочно-циклічну структуру дискретної базисної матриці для ефективного обчислення ДПФ з використанням циклічних згорток для обсягів цілої степені два на основі твірних масивів. Запропонована методика актуальна для паралельного програмування ДПФ та реалізації в паралельних обчислювальних системах. Висновки. Загальна блочно-циклічна структура базисної матриці ДПФ регулярно нарощується зі збільшенням значення показника цілої степені два і рекомендується для використання на практиці при розробці ефективних засобів ДПФ. Перспективи подальших досліджень включатимуть формування блочно-циклічних структур базисної матриці ДПФ для довільних розмірів.