Рекуррентный метод построения алгоритмов линейной свертки различной длины с помощью гиперкомплексных числовых систем

Abstract

Рассмотрен синтез последовательного ряда алгоритмов линейной свертки массивов, длина которых не равна 2ⁿ, для чего используются методы гиперкомплексных числовых систем. Синтез последовательного ряда алгоритмов линейной свертки основан на рекуррентном окаймлении сумм парных произведений отсчетов свертки с последующим применением изоморфных гиперкомплексных числовых систем. Полученные алгоритмы по числу умножений близки к алгоритмам Винограда.

Розглянуто члени послідовностей, що згортаються, вимірності N = 2ⁿ як компоненти гіперкомплексних чисел деякої ГЧС Г₁ вимірності dimГ₁ = 2ⁿ. Добуток цих гіперкомплексних чисел буде містити парні добутки, які входять до складу числових послідовностей, що будуть згортатися. Однак вони будуть об'єднуватись у суми не в тому порядку, як це потрібно для організації індексів. Показано можливість створення алгоритмів з урахуванням лінійної згортки числових послідовностей. довжини яких відрізняються від цілих ступенів двійки. Алгоритми представляють собою рекурентне «облямування» компонент згортки попередньої довжини послідовності, що згортається. За початок рекурсії приймається згортка, побудована на основі алгоритму декомпозиції з використанням ГЧС для довжини, що дорівнює найближчій ступені двійки по відношенню до заданої довжини. Алгоритми подібного типу найбільш ефективні для довгих послідовностей, близьких до 2ⁿ зверху (кількість множень зменшується на ^30 %).

The terms of convolutional numerical sequences are considered as components of hypercomplex numbers belonging to some FPS dimension. The product of these hypercomplex numbers will contain paired products of components of convolutional numerical sequences. However, they will be combined in amounts not in the same composition as necessary to organize the convolution components. The possibility of constructing algorithms for calculating the linear convolution of numerical sequences whose lengths differ from integral powers of two is shown. Algorithms are a recurrent «fringing» of convolution components of the previous length of a convolution sequence. The beginning of the recursion is a convolution constructed on the basis of the decomposition algorithm with the use of the FPS for the sequence length equal to the nearest lower degree of the deuce relative to the given length. Algorithms of this type are most effective for lengths of sequences being close to from upward (the number of multiplications is reduced by ≈ 30 %).