Structure of an algoritsm for quick two-dimensional convolution by means of isomorphing hypercomplex numerical systems
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...
Збережено в:
| Дата: | 2018 |
|---|---|
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | rus |
| Опубліковано: |
Інститут проблем реєстрації інформації НАН України
2018
|
| Теми: | |
| Онлайн доступ: | http://drsp.ipri.kiev.ua/article/view/142899 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Data Recording, Storage & Processing |
Репозитарії
Data Recording, Storage & Processing| id |
drspiprikievua-article-142899 |
|---|---|
| record_format |
ojs |
| institution |
Data Recording, Storage & Processing |
| collection |
OJS |
| language |
rus |
| topic |
hypercomplex number system two-dimensional convolution isomorphism of hypercomplex number systems double numbers orthogonal double numbers isomorphism operator Maple гиперкомплексная числовая система двухмерная свертка изоморфизм гиперкомплексных числовых систем двойные числа ортогональные двойные числа оператор изоморфизма Maple гіперкомплексна числова система двомірна згортка ізоморфізм гіперкомп-лексних числових систем подвійні числа ортогональні подвійні числа оператор ізоморфізму Maple |
| spellingShingle |
hypercomplex number system two-dimensional convolution isomorphism of hypercomplex number systems double numbers orthogonal double numbers isomorphism operator Maple гиперкомплексная числовая система двухмерная свертка изоморфизм гиперкомплексных числовых систем двойные числа ортогональные двойные числа оператор изоморфизма Maple гіперкомплексна числова система двомірна згортка ізоморфізм гіперкомп-лексних числових систем подвійні числа ортогональні подвійні числа оператор ізоморфізму Maple Kalinovsky, Ya. A. Boyarinova, Yu. E. Khitsko, Ya. V. Sukalo, A. S. Structure of an algoritsm for quick two-dimensional convolution by means of isomorphing hypercomplex numerical systems |
| topic_facet |
hypercomplex number system two-dimensional convolution isomorphism of hypercomplex number systems double numbers orthogonal double numbers isomorphism operator Maple гиперкомплексная числовая система двухмерная свертка изоморфизм гиперкомплексных числовых систем двойные числа ортогональные двойные числа оператор изоморфизма Maple гіперкомплексна числова система двомірна згортка ізоморфізм гіперкомп-лексних числових систем подвійні числа ортогональні подвійні числа оператор ізоморфізму Maple |
| format |
Article |
| author |
Kalinovsky, Ya. A. Boyarinova, Yu. E. Khitsko, Ya. V. Sukalo, A. S. |
| author_facet |
Kalinovsky, Ya. A. Boyarinova, Yu. E. Khitsko, Ya. V. Sukalo, A. S. |
| author_sort |
Kalinovsky, Ya. A. |
| title |
Structure of an algoritsm for quick two-dimensional convolution by means of isomorphing hypercomplex numerical systems |
| title_short |
Structure of an algoritsm for quick two-dimensional convolution by means of isomorphing hypercomplex numerical systems |
| title_full |
Structure of an algoritsm for quick two-dimensional convolution by means of isomorphing hypercomplex numerical systems |
| title_fullStr |
Structure of an algoritsm for quick two-dimensional convolution by means of isomorphing hypercomplex numerical systems |
| title_full_unstemmed |
Structure of an algoritsm for quick two-dimensional convolution by means of isomorphing hypercomplex numerical systems |
| title_sort |
structure of an algoritsm for quick two-dimensional convolution by means of isomorphing hypercomplex numerical systems |
| title_alt |
Структура алгоритма быстрой двухмерной свертки с помощью изоморфных гиперкомплексных числовых систем Структура алгоритму швидкої двомірної згортки за допомогою ізоморфних гіперкомплексних числових систем |
| description |
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. |
| publisher |
Інститут проблем реєстрації інформації НАН України |
| publishDate |
2018 |
| url |
http://drsp.ipri.kiev.ua/article/view/142899 |
| work_keys_str_mv |
AT kalinovskyyaa structureofanalgoritsmforquicktwodimensionalconvolutionbymeansofisomorphinghypercomplexnumericalsystems AT boyarinovayue structureofanalgoritsmforquicktwodimensionalconvolutionbymeansofisomorphinghypercomplexnumericalsystems AT khitskoyav structureofanalgoritsmforquicktwodimensionalconvolutionbymeansofisomorphinghypercomplexnumericalsystems AT sukaloas structureofanalgoritsmforquicktwodimensionalconvolutionbymeansofisomorphinghypercomplexnumericalsystems AT kalinovskyyaa strukturaalgoritmabystrojdvuhmernojsvertkispomoŝʹûizomorfnyhgiperkompleksnyhčislovyhsistem AT boyarinovayue strukturaalgoritmabystrojdvuhmernojsvertkispomoŝʹûizomorfnyhgiperkompleksnyhčislovyhsistem AT khitskoyav strukturaalgoritmabystrojdvuhmernojsvertkispomoŝʹûizomorfnyhgiperkompleksnyhčislovyhsistem AT sukaloas strukturaalgoritmabystrojdvuhmernojsvertkispomoŝʹûizomorfnyhgiperkompleksnyhčislovyhsistem AT kalinovskyyaa strukturaalgoritmušvidkoídvomírnoízgortkizadopomogoûízomorfnihgíperkompleksnihčislovihsistem AT boyarinovayue strukturaalgoritmušvidkoídvomírnoízgortkizadopomogoûízomorfnihgíperkompleksnihčislovihsistem AT khitskoyav strukturaalgoritmušvidkoídvomírnoízgortkizadopomogoûízomorfnihgíperkompleksnihčislovihsistem AT sukaloas strukturaalgoritmušvidkoídvomírnoízgortkizadopomogoûízomorfnihgíperkompleksnihčislovihsistem |
| first_indexed |
2024-04-21T19:33:50Z |
| last_indexed |
2024-04-21T19:33:50Z |
| _version_ |
1796974083529768960 |
| spelling |
drspiprikievua-article-1428992019-12-27T07:58:00Z Structure of an algoritsm for quick two-dimensional convolution by means of isomorphing hypercomplex numerical systems Структура алгоритма быстрой двухмерной свертки с помощью изоморфных гиперкомплексных числовых систем Структура алгоритму швидкої двомірної згортки за допомогою ізоморфних гіперкомплексних числових систем Kalinovsky, Ya. A. Boyarinova, Yu. E. Khitsko, Ya. V. Sukalo, A. S. hypercomplex number system two-dimensional convolution isomorphism of hypercomplex number systems double numbers orthogonal double numbers isomorphism operator Maple гиперкомплексная числовая система двухмерная свертка изоморфизм гиперкомплексных числовых систем двойные числа ортогональные двойные числа оператор изоморфизма Maple гіперкомплексна числова система двомірна згортка ізоморфізм гіперкомп-лексних числових систем подвійні числа ортогональні подвійні числа оператор ізоморфізму Maple 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. Рассмотрены вопросы построения алгоритмов быстрой двухмерной свертки массивов различной размерности. Алгоритмы строятся на основе представления массивов данных в изоморфных гиперкомплексных числовых системах, полученных умножением размерности систем двойных чисел и ортогональных двойных чисел, что дает возможность простого по структуре перехода от одной системы к другой. Это приводит к уменьшению количества операций, необходимых для выполнения двухмерных линейных сверток массивов различной величины. Изучен эффект уменьшения количества операций. Исследования выполнены с помощью системы аналитических вычислений Maple. Розглянуто питання побудови алгоритмів швидкої двомірної згортки масивів різної розмірності. Алгоритми будуються на основі подання масивів даних в ізоморфних гіперкомплексних числових системах, отриманих множенням розмірності систем подвійних чисел і ортогональних подвійних чисел, що дає можливість простого за структурою переходу від однієї системи до іншої. Це призводить до зменшення кількості операцій, що необхідні для виконання двомірних лінійних згорток масивів різної величини. Вивчено ефект зменшення кількості операцій. Дослідження виконано за допомогою системи аналітичних обчислень Maple. Інститут проблем реєстрації інформації НАН України 2018-04-03 Article Article application/pdf http://drsp.ipri.kiev.ua/article/view/142899 10.35681/1560-9189.2018.20.1.142899 Data Recording, Storage & Processing; Vol. 20 No. 1 (2018); 17–29 Регистрация, хранение и обработка данных; Том 20 № 1 (2018); 17–29 Реєстрація, зберігання і обробка даних; Том 20 № 1 (2018); 17–29 1560-9189 rus http://drsp.ipri.kiev.ua/article/view/142899/140348 Авторське право (c) 2021 Реєстрація, зберігання і обробка даних |