Recursive method for constructing linear convolution algorithms of various lengths using hypercomplex number systems.
Linear convolution of discrete signals with a certain core is the most common and important computational task in the field of digital signal processing. Since this operation, as a rule, is performed many times, the problem of synthesizing fast algorithms for performing linear convolution is very ac...
Saved in:
| Date: | 2019 |
|---|---|
| Main Authors: | , , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем реєстрації інформації НАН України
2019
|
| Subjects: | |
| Online Access: | http://drsp.ipri.kiev.ua/article/view/178872 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Data Recording, Storage & Processing |
Institution
Data Recording, Storage & Processing| id |
drspiprikievua-article-178872 |
|---|---|
| record_format |
ojs |
| institution |
Data Recording, Storage & Processing |
| baseUrl_str |
|
| datestamp_date |
2019-12-10T11:54:19Z |
| collection |
OJS |
| language |
Russian |
| topic |
hypercomplex number system linear convolution isomorphism multiplication bicomplex numbers quadriclex numbers |
| spellingShingle |
hypercomplex number system linear convolution isomorphism multiplication bicomplex numbers quadriclex numbers Kalinovsky, Ya. A. Boyarinova, Yu. E. Sukalo, A. S. Khitsko, Ya. V. Recursive method for constructing linear convolution algorithms of various lengths using hypercomplex number systems. |
| topic_facet |
гіперкомплексна числова система лінійна згортка ізоморфізм множення бікомплексні числа квадріплексні числа hypercomplex number system linear convolution isomorphism multiplication bicomplex numbers quadriclex numbers |
| format |
Article |
| author |
Kalinovsky, Ya. A. Boyarinova, Yu. E. Sukalo, A. S. Khitsko, Ya. V. |
| author_facet |
Kalinovsky, Ya. A. Boyarinova, Yu. E. Sukalo, A. S. Khitsko, Ya. V. |
| author_sort |
Kalinovsky, Ya. A. |
| title |
Recursive method for constructing linear convolution algorithms of various lengths using hypercomplex number systems. |
| title_short |
Recursive method for constructing linear convolution algorithms of various lengths using hypercomplex number systems. |
| title_full |
Recursive method for constructing linear convolution algorithms of various lengths using hypercomplex number systems. |
| title_fullStr |
Recursive method for constructing linear convolution algorithms of various lengths using hypercomplex number systems. |
| title_full_unstemmed |
Recursive method for constructing linear convolution algorithms of various lengths using hypercomplex number systems. |
| title_sort |
recursive method for constructing linear convolution algorithms of various lengths using hypercomplex number systems. |
| title_alt |
Рекурентний метод побудови алгоритмів лінійної згортки різної довжини за допомогою гіперкомплексних числових систем |
| description |
Linear convolution of discrete signals with a certain core is the most common and important computational task in the field of digital signal processing. Since this operation, as a rule, is performed many times, the problem of synthesizing fast algorithms for performing linear convolution is very actual, which is the main subject of this work. Since the complexity of calculating the linear convolution of sequences having length N is , and rapidly increases with growth N, then the methods of «fast» computations are used. One of the most common methods is convolution using Fast Fourier Transform (FFT) with complexity of . At the heart of numerous FFT algorithms is the decomposition of the original large-dimensional problem into a large number of low-dimensional problems. Therefore, it is very important to develop such methods for solving problems of small dimension.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 %). |
| publisher |
Інститут проблем реєстрації інформації НАН України |
| publishDate |
2019 |
| url |
http://drsp.ipri.kiev.ua/article/view/178872 |
| work_keys_str_mv |
AT kalinovskyyaa recursivemethodforconstructinglinearconvolutionalgorithmsofvariouslengthsusinghypercomplexnumbersystems AT boyarinovayue recursivemethodforconstructinglinearconvolutionalgorithmsofvariouslengthsusinghypercomplexnumbersystems AT sukaloas recursivemethodforconstructinglinearconvolutionalgorithmsofvariouslengthsusinghypercomplexnumbersystems AT khitskoyav recursivemethodforconstructinglinearconvolutionalgorithmsofvariouslengthsusinghypercomplexnumbersystems AT kalinovskyyaa rekurentnijmetodpobudovialgoritmívlíníjnoízgortkiríznoídovžinizadopomogoûgíperkompleksnihčislovihsistem AT boyarinovayue rekurentnijmetodpobudovialgoritmívlíníjnoízgortkiríznoídovžinizadopomogoûgíperkompleksnihčislovihsistem AT sukaloas rekurentnijmetodpobudovialgoritmívlíníjnoízgortkiríznoídovžinizadopomogoûgíperkompleksnihčislovihsistem AT khitskoyav rekurentnijmetodpobudovialgoritmívlíníjnoízgortkiríznoídovžinizadopomogoûgíperkompleksnihčislovihsistem |
| first_indexed |
2025-07-17T10:57:26Z |
| last_indexed |
2025-07-17T10:57:26Z |
| _version_ |
1850411325632544768 |
| spelling |
drspiprikievua-article-1788722019-12-10T11:54:19Z Recursive method for constructing linear convolution algorithms of various lengths using hypercomplex number systems. Рекурентний метод побудови алгоритмів лінійної згортки різної довжини за допомогою гіперкомплексних числових систем Kalinovsky, Ya. A. Boyarinova, Yu. E. Sukalo, A. S. Khitsko, Ya. V. гіперкомплексна числова система лінійна згортка ізоморфізм множення бікомплексні числа квадріплексні числа hypercomplex number system linear convolution isomorphism multiplication bicomplex numbers quadriclex numbers Linear convolution of discrete signals with a certain core is the most common and important computational task in the field of digital signal processing. Since this operation, as a rule, is performed many times, the problem of synthesizing fast algorithms for performing linear convolution is very actual, which is the main subject of this work. Since the complexity of calculating the linear convolution of sequences having length N is , and rapidly increases with growth N, then the methods of «fast» computations are used. One of the most common methods is convolution using Fast Fourier Transform (FFT) with complexity of . At the heart of numerous FFT algorithms is the decomposition of the original large-dimensional problem into a large number of low-dimensional problems. Therefore, it is very important to develop such methods for solving problems of small dimension.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 %). Лінійна згортка дискретних сигналів з деяким ядром є найбільш важливою задачею в області цифрової обробки сигналів. Так як ця операція, як правило, виконується багато разів, це дуже актуальна задача синтезу швидких алгоритмів виконання лінійної згортки. Так як складність обчис-лення лінійної згортки послідовності п є і швидко збільшується з ростом п, то використовуються методи «швидких» обчислень. Одним із найбільш поширених методів є методи із застосуванням швидкого перетворення Фур’є (ШПФ) зі складністю . В основі багаточисельних алгоритмів ШПФ лежить декомпозиція вихідної задачі великого розміру в багато задач маленької розмірності. Тому важливим є розробка таких методів для вирішення задач малого розміру.Розглянуто члени послідовностей, що згортаються, вимірності як компоненти гіперкомплексних чисел деякої ГЧС Г1 вимірності . Добуток цих гіперкомплексних чисел буде містити парні добутки, які входять до складу числових послідовностей, що будуть згортатися. Однак вони будуть об’єднуватись у суми не в тому порядку, як це потрібно для організації індексів.Показано можливість створення алгоритмів з урахуванням лінійної згортки числових послідовностей, довжини яких відрізняються від цілих ступенів двійки. Алгоритми представляють собою рекурентне «облямування» компонент згортки попередньої довжини послідовності, що згортається. За початок рекурсії приймається згортка, побудована на основі алгоритму декомпозиції з використанням ГЧС для довжини, що дорівнює найближчій ступені двійки по відношенню до заданої довжини. Алгоритми подібного типу найбільш ефективні для довгих послідовностей, близьких до 2 зверху (кількість множень зменшується на »30 %). Табл.: 1. Іл.: 5. Бібліогр.: 13 найм. Інститут проблем реєстрації інформації НАН України 2019-11-04 Article Article application/pdf http://drsp.ipri.kiev.ua/article/view/178872 10.35681/1560-9189.2018.20.4.178872 Data Recording, Storage & Processing; Vol. 20 No. 4 (2018); 40-52 Регистрация, хранение и обработка данных; Том 20 № 4 (2018); 40-52 Реєстрація, зберігання і обробка даних; Том 20 № 4 (2018); 40-52 1560-9189 ru http://drsp.ipri.kiev.ua/article/view/178872/182515 Авторське право (c) 2021 Реєстрація, зберігання і обробка даних |