Оптимизация метода Питасси вычисления свертки

• Date: 2009
• Main Author: Терещенко, А.Н.
• Format: Article
• Language: Russian
• Published: Інститут проблем штучного інтелекту МОН України та НАН України 2009
• Subjects: Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/7827
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Оптимизация метода Питасси вычисления свертки / А.Н. Терещенко // Штучний інтелект. — 2009. — № 1. — С. 204-212. — Бібліогр.: 6 назв. — рос.

Предложенный метод расширяет диапазон используемых разрядностей циклической свертки за счет применения эффективного метода вычисления циклической свертки разрядностью 2К, где К – нечетное. Показано, что для вычисления свертки такой разрядности достаточно вычислить только две свертки половиной (от начальной) разрядности, при большем количестве пред- и поствычислений в виде циклических сдвигов по сравнению с методом Питасси. Представлены в общем виде формулы вычисления циклической свертки. Приведена реализация операции многоразрядного умножения на основе циклической свертки. В виде таблицы приведены оценки сложности вычисления свертки большой разрядности вида N=K*2^n , n>1 для K=3,5,7,9. Запропонований метод розширює діапазон використовуваних розрядностей циклічної згортки за рахунок застосування ефективного методу обчислення циклічної згортки розрядністю 2К, де К – непарне. Показано, що для обчислення згортки такої розрядності достатньо обчислити тільки дві згортки половинної (від начальної) розрядності, при більшій кількості перед- та постобчислень у вигляді циклічних зсувів. Представлені в загальному вигляді формули обчислення циклічної згортки. Наведена реалізації операції багаторозрядного множення на основі циклічної згортки. У вигляді таблиці наведені оцінки складності обчислення циклічної згортки великої розрядності виду N=K*2^n , n>1 для K=3,5,7,9. The suggested method extends the range of used measurements of cyclic convolutions with using of effective calculation method of cyclic convolutions with measurement 2K then K is odd. It is shown for convolution calculation with that measurement it is enough to calculate only 2 convolutions half-measurement with more number of pre- and post-calculations like cyclic shifts. It is given in general the calculation formulas of cyclic convolution. It is given the building of multi-digit multiplication with using cyclic convolution. The complexities of cyclic convolution calculation with measurement N=K*2^n , n>1 for K=3,5,7,9 are given in table.