Оптимизация метода Питасси вычисления свертки
Vernadsky National Library of Ukraine
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Оптимизация метода Питасси вычисления свертки
|
|
| Creator |
Терещенко, А.Н.
|
|
| Subject |
Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем
|
|
| Description |
Предложенный метод расширяет диапазон используемых разрядностей циклической свертки за счет применения эффективного метода вычисления циклической свертки разрядностью 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. |
|
| Date |
2010-04-19T11:43:33Z
2010-04-19T11:43:33Z 2009 |
|
| Type |
Article
|
|
| Identifier |
Оптимизация метода Питасси вычисления свертки / А.Н. Терещенко // Штучний інтелект. — 2009. — № 1. — С. 204-212. — Бібліогр.: 6 назв. — рос.
1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/7827 681.3:519 |
|
| Language |
ru
|
|
| Publisher |
Інститут проблем штучного інтелекту МОН України та НАН України
|
|