Оптимизация метода Питасси вычисления свертки - Терещенко, А.Н. (Інститут проблем штучного інтелекту МОН України та НАН України, 2009)
Предложенный метод расширяет диапазон используемых разрядностей циклической свертки за счет
применения эффективного метода вычисления циклической свертки разрядностью 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.