Structure of an algoritsm for quick two-dimensional convolution by means of isomorphing hypercomplex numerical systems

• Дата: 2018
• Автори: Kalinovsky, Ya. A., Boyarinova, Yu. E., Khitsko, Ya. V., Sukalo, A. S.
• Формат: Стаття
• Мова: Russian
• Опубліковано: Інститут проблем реєстрації інформації НАН України 2018
• Теми: hypercomplex number system; two-dimensional convolution; isomorphism of hypercomplex number systems; double numbers; orthogonal double numbers; isomorphism operator; Maple
• Онлайн доступ: http://drsp.ipri.kiev.ua/article/view/142899
• Назва журналу: Data Recording, Storage & Processing

In the mathematical modeling of linear systems, it is necessary to repeatedly perform a linear convolution of discrete signals. The complexity of calculating the linear convolution rapidly increases with the length of the convoluted arrays and their dimension, thus the methods of «fast» convolution calculations are used. One of the most common methods is convolution using Fast Fourier Transform (FFT) algorithms, which are based on decomposition of the original large-dimensional problem into a large number of low-dimensional problems. Thus, it is very important to develop such methods for solving problems for small dimension, which use, possibly, a smaller number of real operations. There are a number of methods for the rapid calculation of linear convolution: the methods of Cook-Toom, Vine, Fast Fourier Transform (FFT), Cooley-Tuke, Good-Thomas, and others. The algorithms for performing convolution based on the transition to hypercomplex spaces are considered. The basis of this approach has been developed by the authors. Convoluted numerical sequences are considered as components of hypercomplex numbers belonging to some HNS. The product of these numbers will contain paired products of components of convolutional numerical sequences. Nevertheless, they will be combined in amounts not in the same composition as necessary for organizing convolution components. In addition, the number of real multiplications with multiplication of hypercomplex numbers in the general case is the same as in the direct calculation of convolution, that’s why there is no profit. In this way there are two problems: the first one is a reduction in the number of real operations when multiplying hypercomplex numbers; the second one is the organization of the choice of paired products of convolution components. The solution of these two problems allows synthesize such convolution algorithms, which by the number of operations are more efficient than direct calculation algorithms for convolution.