Рекурентний метод побудови алгоритмів лінійної згортки різної довжини за допомогою гіперкомплексних числових систем
DOI:
https://doi.org/10.35681/1560-9189.2018.20.4.178872Ключові слова:
гіперкомплексна числова система, лінійна згортка, ізоморфізм, множення, бікомплексні числа, квадріплексні числаАнотація
Лінійна згортка дискретних сигналів з деяким ядром є найбільш важливою задачею в області цифрової обробки сигналів. Так як ця операція, як правило, виконується багато разів, це дуже актуальна задача синтезу швидких алгоритмів виконання лінійної згортки. Так як складність обчис-лення лінійної згортки послідовності п є і швидко збільшується з ростом п, то використовуються методи «швидких» обчислень. Одним із найбільш поширених методів є методи із застосуванням швидкого перетворення Фур’є (ШПФ) зі складністю . В основі багаточисельних алгоритмів ШПФ лежить декомпозиція вихідної задачі великого розміру в багато задач маленької розмірності. Тому важливим є розробка таких методів для вирішення задач малого розміру.
Розглянуто члени послідовностей, що згортаються, вимірності як компоненти гіперкомплексних чисел деякої ГЧС Г1 вимірності . Добуток цих гіперкомплексних чисел буде містити парні добутки, які входять до складу числових послідовностей, що будуть згортатися. Однак вони будуть об’єднуватись у суми не в тому порядку, як це потрібно для організації індексів.
Показано можливість створення алгоритмів з урахуванням лінійної згортки числових послідовностей, довжини яких відрізняються від цілих ступенів двійки. Алгоритми представляють собою рекурентне «облямування» компонент згортки попередньої довжини послідовності, що згортається. За початок рекурсії приймається згортка, побудована на основі алгоритму декомпозиції з використанням ГЧС для довжини, що дорівнює найближчій ступені двійки по відношенню до заданої довжини. Алгоритми подібного типу найбільш ефективні для довгих послідовностей, близьких до 2 зверху (кількість множень зменшується на »30 %). Табл.: 1. Іл.: 5. Бібліогр.: 13 найм.Посилання
Blejhut R. Bystrye algoritmy cifrovoj obrabotki signalov. Moskva: Mir, 1989. 449 s.
Nussbaumer G. Bystroe preobrazovanie Fur'e i algoritmy vychislenija svertok Moskva: Radio i svjaz', 1985. 248 s.
Sergienko A.B. Cifrovaja obrabotka signalov. Sankt-Peterburg: Piter, 2003. 604 s.
Kalinovskij Ja.A. Struktura giperkompleksnogo metoda bystrogo vychislenija linejnoj svertki diskretnyh signalov. Reyestratsiya, zberihannya i obrob. danykh. 2013. T. 15. No. 1. S. 31–44.
Sin'kov M.V., Bojarinova Ju.E., Kalinovskij Ja.A. Konechnomernye giperkompleksnye chislovye sistemy. Osnovy teorii. Primenenija. Kiev: Infodruk, 2010. 388 s.
Kalinovskij Ja.A., Bojarinova Ju.E. Vysokorazmernye izomorfnye giperkompleksnye chislovye sistemy i ih ispol'zovanie dlja povyshenija jeffektivnosti vychislenij. Kiev: Infod-ruk, 2012. 183 s.
Kalinovskij Ja.A., Landje D.V., Bojarinova Ju.E., Hicko Ja.V. Giperkompleksnye chislovye sistemy i bystrye algoritmy cifrovoj obrabotki informacii. Kiev: IPRI NANU, 2014. 130 s.
Kalinovs'kyy Ya.O. Rozvytok metodiv teoriyi hiperkompleksnykh chyslovykh system dlya matematychnoho modelyuvannya i komp"yuternykh obchyslen': dys. dokt. tekhn. nauk: 01.05.02. Kyyiv, 2007. 308 s.
Kalinovskij Ja.A., Sin'kova T.V. Algoritmy bystrogo vychislenija ciklicheskoj svertki c predstavleniem diskretnyh signalov giperkompleksnymi chislami. Reyestratsiya, zberihannya i obrob. danykh. 2014. T. 16. No. 1. S. 9–18.
Kalinovskij Ja.A. Issledovanie simmetrij operatora izomorfizma giperkompleksnyh chislovyh sistem i ih ispol'zovanie dlja sinteza algoritmov bystrogo vychislenija ciklicheskoj svertki. Reyestratsiya, zberihannya i obrob. danykh. 2014. T. 16. No. 2. S. 42–51.
Кalinovskij Ja.A., Bojarinova Ju.E., Sin'kova T.V., Cukalo A.S. Postroenie vysokoraz-mernyh izomorfnyh giperkompleksnyh chislovyh sistem dlja povyshenija jeffektivnosti vychis-litel'nyh processov. Jelektronnoe modelirovanie. 2016. T. 38. No. 6. S. 67–84.
Kalinovsky Y.A., Boyarinova Y.E., Sukalo A.S., Khitsko Y.V. The basic principles and the structure and algorithmically software of computing by hypercomplex number. arXiv preprint arXiv:1708.04021, 2017.
Kalinovskij Ja.A., Bojarinova Ju.E., Hicko Ja.V., Sukalo A.S. Programmnyj kompleks dlja giperkompleksnyh vychislenij. Jelektronnoe modelirovanie. 2017. T. 39. No. 5. S. 81–96.
