Швидке обчислення циклічної згортки багаторозрядних чиселна основі ШПФ у послідовній моделі обчислень

• Published in: Компьютерная математика
• Date: 2016
• Main Authors: Терещенко, А.М., Задірака, В.К.
• Format: Article
• Language: Ukrainian
• Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2016
• Subjects: Оптимизация вычислений
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/168424
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Швидке обчислення циклічної згортки багаторозрядних чиселна основі ШПФ у послідовній моделі обчислень / А.М. Терещенко, В.К. Задірака // Компьютерная математика. — 2016. — № 2. — С. 110-119. — Бібліогр.: 5 назв. — укр.

Аналізується складність за кількістю однослівних операцій при реалізації операції циклічної згортки. Розглянуто методи обчислення циклічної згортки, коли кожна точка згортки є багаторозрядним числом. Запропоновано швидкий метод обчислення циклічної згортки такого виду на основі ШПФ невеликої довжини Анализируется сложность по числу однословных операций при реализации операции циклической свертки. Рассмотрены методы вычисления циклической свертки, когда каждая точка свертки является многоразрядным числом. Предложено быстрый метод вычисления циклических сверток такого вида на основе БПФ небольшой длины. A complexity of number of single precision operations is analyzed in multi-digit convolution computation. Calculation methods of cyclic convolution elements are considered when every element is a high precision value. An effective method based on FFT of small length for calculation of cyclic convolution of multi-digit values is proposed.