Алгоритм обчислення одновимірної згортки з використанням гіперкомплексних чисел
Представлено алгоритм обчислення одновимірної дійсної згортки з переходом до двовимірного перетворення Фур’є і використанням гіперкомплексних чисел. Проведено аналіз обчислювальної складності розробленого алгоритму при використанні різних гіперкомплексних числових систем. Представлен алгоритм вычисл...
Saved in:
| Published in: | Реєстрація, зберігання і обробка даних |
|---|---|
| Date: | 2009 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут проблем реєстрації інформації НАН України
2009
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/50367 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Алгоритм обчислення одновимірної згортки з використанням гіперкомплексних чисел / М.В. Синьков, А.І. Закидальський, Є.О. Цибульська // Реєстрація, зберігання і оброб. даних. — 2009. — Т. 11, № 1. — С. 20-26. — Бібліогр.: 5 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859693658551353344 |
|---|---|
| author | Синьков, М.В. Закидальський, А.І. Цибульська, Є.О. |
| author_facet | Синьков, М.В. Закидальський, А.І. Цибульська, Є.О. |
| citation_txt | Алгоритм обчислення одновимірної згортки з використанням гіперкомплексних чисел / М.В. Синьков, А.І. Закидальський, Є.О. Цибульська // Реєстрація, зберігання і оброб. даних. — 2009. — Т. 11, № 1. — С. 20-26. — Бібліогр.: 5 назв. — укр. |
| collection | DSpace DC |
| container_title | Реєстрація, зберігання і обробка даних |
| description | Представлено алгоритм обчислення одновимірної дійсної згортки з переходом до двовимірного перетворення Фур’є і використанням гіперкомплексних чисел. Проведено аналіз обчислювальної складності розробленого алгоритму при використанні різних гіперкомплексних числових систем.
Представлен алгоритм вычисления одномерной действительной свертки с переходом к двумерному преобразованию Фурье и использованием гиперкомплексных чисел. Проведен анализ вычислительной сложности разработанного алгоритма при использовании различных гиперкомплексных числовых систем.
The algorithm for computing 1D real convolution with conversion to 2D Fourier transform and using hypercomplex numbers is presented. The computing complexity of developed algorithm by using various hypercomplex numerical systems is analyzed.
|
| first_indexed | 2025-12-01T00:09:02Z |
| format | Article |
| fulltext |
20
УДК 620.179.15:004.421.2
М. В. Синьков, А. І. Закидальський, Є. О. Цибульська
Інститут проблем реєстрації інформації НАН України
вул. М. Шпака, 2, 03113 Київ, Україна
Алгоритм обчислення одновимірної згортки
з використанням гіперкомплексних чисел
Представлено алгоритм обчислення одновимірної дійсної згортки з
переходом до двовимірного перетворення Фур’є і використанням гі-
перкомплексних чисел. Проведено аналіз обчислювальної складності
розробленого алгоритму при використанні різних гіперкомплексних чи-
слових систем.
Ключові слова: згортка, дискретне перетворення Фур’є, швидке пе-
ретворення Фур’є, гіперкомплексні числові системи.
Вступ
Останнім часом усе більш поширеним стає представлення інформації з вико-
ристанням гіперкомплексних числових систем (ГЧС), зокрема, в теорії цифрової
обробки сигналів. У роботах [1–3] представлені алгоритми обчислення двовимір-
ного дискретного перетворення Фур’є (ДПФ) і двовимірної згортки за допомогою
гіперкомплексних числових систем кватерніонів (H) і квадриплексних чисел (K).
Основна ідея цих алгоритмів полягає в наступному. У випадку одновимірної згор-
тки дійсність вхідної послідовності )(nx дозволяє переходити при перетворенні
Фур’є до допоміжної
2
N
-періодичної комплексної послідовності )2()(1 kxnx
)12( kix ,
2
,...,0
n
k , що вдвічі скорочує кількість операцій при обчисленні
ДПФ. При згортці двовимірних послідовностей аналогічна ідея реалізується за
допомогою використання чотиривимірних гіперкомплексних числових систем. У
цьому випадку множення на повертаючі коефіцієнти при перетворенні Фур’є ви-
конується тільки для чверті відліків послідовностей, що вдвічі скорочує кількість
операцій порівняно з комплексним ДПФ.
Метою роботи було створити алгоритми, які дозволяють використовувати гі-
перкомплексні числа для обчислення одновимірної згортки, а також розглянути
можливість використання інших гіперкомплексних числових систем.
© М. В. Синьков, А. І. Закидальський, Є. О. Цибульська
Алгоритм обчислення одновимірної згортки з використанням гіперкомплексних чисел
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2009, Т. 11, № 1 21
Застосування алгоритмів двовимірного дискретного перетворення
Фур’є до одновимірних числових послідовностей
Гіперкомплексне перетворення Фур’є двовимірної послідовності ),( mnx роз-
мірності MN при використанні комутативних систем квадриплексних і біком-
плексних чисел задається формулою:
1
0
1
0
22
),(),(
N
n
M
m
j
M
vm
i
N
un
eemnyvuY
. (1)
Розглянемо одновимірну послідовність довжини MNT . Її можна пере-
творити на двовимірний масив з N стовпчиків і M рядків [5]. Візьмемо деякий
відлік ),( mnx . Якщо у вхідної одномірної послідовності він мав номер l , то
nNml .
Знайдемо ДПФ отриманого двовимірного масиву. Нехай n і m — змінні по-
чаткового сигналу, r і s — змінні двовимірного ДПФ по стовпчикам і рядкам, які
перетворюються в одну змінну sMrk . Тоді коефіцієнти одновимірного ДПФ
),()( rsXkX pp можна визначити через перетворення масиву ),()( nmxlx , ви-
користовуючи формули перерахунку індексів:
1
0
1
0
))((),(),()(
N
n
M
m
sMrmNl
ppp WnmxrsXkX . (2)
Розкладемо ))(( sMrmNlW на множники з урахуванням того, що
1 TlrNMlr WW . Тоді (2) можна записати як
1
0
),(
1
0
),(),(
N
n
snq
N
n
NsmnsMnr
p WmnxWWrsX
. (3)
Внутрішня сума — це ДПФ п-го стовпчика з ядром перетворення NW , зовні-
шня сума — ДПФ т-го рядка з ядром перетворення MW .
У результаті перетворення номери рядків і стовпчиків міняються місцями. Це
відбувається тому, що при збільшенні n на 1 номер відліку вхідного масиву
nNm також збільшується на 1, а при збільшенні на 1 номеру стовпчика пере-
твореного масиву r аргумент ),( rsX зростає на M .
Таким чином, для обчислення швидкого перетворення Фур’є (ШПФ) з пере-
ходом до двовимірних масивів потрібно виконати такі дії:
1) перетворити одновимірну послідовність у двовимірний масив;
2) виконати ДПФ стовпчиків масиву;
3) помножити всі елементи на додатковий повертаючий коефіцієнт;
4) виконати ДПФ рядків масиву;
5) виконати перестановку «рядокстовпчик».
Різницею між (1) і (3) є множення на додатковий повертаючий коефіцієнт при
М. В. Синьков, А. І. Закидальський, Є. О. Цибульська
22
виконанні двовимірного перетворення Фур’є.
Алгоритм обчислення одновимірної згортки
У даній статті представлено розроблені алгоритми обчислення одновимірної
дійсної згортки за допомогою ДПФ із використанням гіперкомплексних числових
систем квадриплексних чисел (К) і бікомплексних чисел (СС) [4]. У цих алгори-
тмах факт необхідності розбиття на 4 частини аналогічний тому, що зроблено в
інших алгоритмах, представлених у роботах [1–3], але при цьому в процесі роз-
биття запропоновано одночасно виконувати лінійне перетворення відліків послі-
довностей, що в подальшому приводить до зменшення сумарного обсягу обчис-
лень.
Крім того, при переході від одновимірного до двовимірного перетворення
Фур’є і подальших обчислень запропоновано використовувати бікомплексну ГЧС.
Це дозволило скоротити кількість операцій за рахунок більш економічної таблиці
множення бікомплексних чисел, яка містить значну кількість нулів.
Враховуючи сказане вище, алгоритм обчислення одновимірної згортки за до-
помогою двовимірних гіперкомплексних спектрів буде складатися з таких дій:
1) перетворити одновимірні послідовності довжини MNT у двовимірні
масиви розмірності MN ;
2) для переходу від дійсної числової системи до гіперкомплексної виконати
поділ масиву ядра на 4 масиви за правилами:
для квадриплексних чисел — ijji
x
x
x
x
y
y
y
y
1
1111
1111
1111
1111
3
2
1
0
3
2
1
0
,
для бікомплексних чисел — ji
xx
xx
xx
xx
y
y
y
y
11
1010
0101
1010
0101
32
32
10
10
3
2
1
0
,
де ]2,2[0 jixx ; ]12,2[1 jixx ; ]2,12[2 jixx ; ]12,12[3 jixx ;
2
0
N
i ;
2
0
M
j ;
3) аналогічно виконати поділ масиву даних;
4) обчислити ДПФ стовпчиків масивів із урахуванням чотиримірності відлі-
ків;
5) помножити всі елементи на додатковий повертаючий коефіцієнт;
6) обчислити ДПФ рядків масивів з урахуванням чотиривимірності відліків;
7) виконати перетворення «рядокстовпчик»;
Алгоритм обчислення одновимірної згортки з використанням гіперкомплексних чисел
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2009, Т. 11, № 1 23
8) перемножити поелементно масиви даних із масивами ядра за правилами
множення гіперкомплексних чисел;
9) обчислити обернене дискретне перетворення Фур’є (ОДПФ) стовпчиків
масивів із урахуванням чотиривимірності відліків;
10) помножити всі елементи на повертаючий коефіцієнт, спряжений додатко-
вому;
11) обчислити ОДПФ рядків масивів із урахуванням чотиривимірності відлі-
ків;
12) виконати перетворення «рядокстовпчик» масиву результату;
13) перетворити гіперкомплексний результат у дійсний за правилами:
для квадриплексних чисел — ijji
y
y
y
y
x
x
x
x
1
1111
1111
1111
1111
4
1
3
2
1
0
3
2
1
0
,
для бікомплексних чисел — ji
yy
yy
yy
yy
x
x
x
x
11
1010
0101
1010
0101
4
1
32
32
10
10
3
2
1
0
;
14) перетворити двовимірний масив результату в одновимірну послідовність.
Оцінка обсягу обчислень згортки за допомогою двовимірного
гіперкомплексного швидкого перетворення Фур’є
Для оцінки обчислювальної складності підрахуємо кількість дійсних операцій
множення і додавання, необхідних для обчислення згортки одновимірних послі-
довностей довжини MNT .
У загальну кількість операцій увійдуть:
1) перетворення одновимірної дійсної послідовності в гіперкомплексну: T3
— для квадриплексної ГЧС і T2 — для бікомплексної ГЧС;
2) базова операція «метелик» алгоритму Кулі–Тьюки — T
T
2log
44
9
операцій
для квадриплексної ГЧС і T
T
2log
44
7
операцій для бікомплексної ГЧС;
3) множення на додатковий повертаючий коефіцієнт —
4
12
T
операцій;
4) добуток двох гіперкомплексних послідовностей — T
T
7
4
28 операцій для
квадриплексної ГЧС і T
T
3
4
12 операцій для бікомплексної ГЧС.
М. В. Синьков, А. І. Закидальський, Є. О. Цибульська
24
Тоді двовимірне гіперкомплексне перетворення Фур’є одновимірної послі-
довності довжини MNT потребує дійсних операцій:
з квадриплексними числами —
4
123log
44
9
2
T
TT
T
;
з бікомплексними числами —
4
122log
44
7
2
T
TT
T
.
Згортка одновимірних послідовностей потребує дійсних операцій:
з квадриплексними числами — TT
T
19log
42
9
2 ;
з бікомплексними числами — TT
T
13log
42
7
2 .
Порівняння обчислювальної складності алгоритмів згортки
Була розглянута обчислювальна складність алгоритмів згортки одновимірних
послідовностей за допомогою ШПФ з основою 2, ШПФ зі змішаною основою,
двовимірного ШПФ із ГЧС К, двовимірного ШПФ із ГЧС СС. Для прикладу
розглядалися довжини послідовностей, що дорівнюють деякій степені 2.
Для сигналів різної довжини в табл. 1 наведена кількість дійсних операцій
обчислення перетворення Фур’є — загальна та на 1 елемент.
Таблиця 1. Кількість операцій алгоритмів обчислення ШПФ
ШПФ із
основою 2
ШПФ зі
змішаною основою
2D ШПФ із
ГЧС К
2D ШПФ із
ГЧС CCNM
усього на 1 ел. усього на 1 ел. усього на 1 ел. усього на 1 ел.
88 768 12 388 6,06 600 9,37 552 8,63
816 1792 14 1028 8,03 1272 9,49 1160 9,06
1616 4096 16 2564 10,01 2688 10,5 2432 9,5
1632 9216 18 6148 12 5664 11,06 5088 9,94
На рис. 1 зображені графіки, що характеризують кількість дійсних операцій
на один відлік для різних алгоритмів обчислення ШПФ.
У табл. 2 наведена кількість дійсних операцій обчислення згортки — загальна
та на 1 елемент.
Таблиця 2. Кількість операцій алгоритмів обчислення згортки
Згортка з ШПФ
з основою 2
Згортка з ШПФ зі
змішаною основою
Згортка з 2D
ШПФ із ГЧС К
Згортка з 2D
ШПФ із ГЧС
CC
NM
усього на 1 ел. усього на 1 ел. усього на 1 ел. усього на 1 ел.
88 1920 30 1160 18,12 1648 25,75 1216 19
816 4352 34 2824 22,06 3440 26,85 2448 19,68
1616 9728 38 6664 26,03 7168 28 5120 22
1632 21504 42 15368 30,01 14912 28,12 10688 24,87
Алгоритм обчислення одновимірної згортки з використанням гіперкомплексних чисел
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2009, Т. 11, № 1 25
На рис. 2 зображено графіки, що характеризують кількість дійсних операцій
на один відлік для різних алгоритмів обчислення згортки.
Висновки
Як видно з таблиць і графіків, найкращі показники за кількістю операцій має
алгоритм обчислення згортки з двовимірним швидким перетворенням Фур’є з ви-
Рис. 1. Кількість операцій на один відлік різних алгоритмів обчислення ШПФ
Порівняння кількості операцій для обчислення ШПФ
0
5
10
15
20
64 128 256 512
Кількість відліків
К
іл
ьк
іс
ть
о
п
ер
ац
ій
н
а
в
ід
л
ік
ШПФ з основою 2 ШПФ зі змішаною основою
2D ШПФ з ГЧС К 2D ШПФ з ГЧС C+C
Рис. 2. Кількість операцій на один відлік різних алгоритмів обчислення згортки
Порівняння кількості операцій для обчислення згортки за
допомогою ШПФ
0
5
10
15
20
25
30
35
40
45
64 128 256 512
К ількість відл ік ів
К
іл
ь
к
іс
ть
о
п
ер
ац
ій
н
а
в
ід
л
ік
ШПФ з основою 2 ШПФ зі зміш аною основою
2D ШПФ з ГЧС К 2D ШПФ з ГЧС С+С
М. В. Синьков, А. І. Закидальський, Є. О. Цибульська
26
користанням бікомплексної ГЧС. При довжині послідовностей, більшій ніж 128
відліків, він має меншу обчислювальну складність, ніж алгоритм обчислення зго-
ртки із ШПФ зі змішаною основою, який є одним з найпродуктивніших. Також
представляється, що для обчислення згорток великої довжини доцільно буде роз-
глянути використання ГЧС більш високих порядків, що буде зроблено в подаль-
ших роботах.
1. Chicheva M.A. On Various Schemes of 2D-DFT Decomposition with Data Representation in the
Quaternion Algebra / M.A.Chicheva, M.V.Pershina // Image Processing & Communications. — 2004. —
Vol. 2, N.1. — Р. 13–20. — Published by the Institute of Telecommunications Bydgoszcz, Poland.
2. Алиев М.В. Алгоритмы двумерного ДПФ с представлением данных в алгебре гиперкомпле-
ксных чисел / М.В. Алиев, М.А. Чичева // кн. Алгебра и линейная оптимизация: Труды междуна-
родного семинара, посвященного 90-летию со дня рождения С.Н. Черникова.— Екатеринбург:
УрО РАН, 2002. — С. 18–26.
3. Felsberg M. Fast Algorithms of Hypercomplex Fourier Transform / M. Felsberg, T. Bulov, G.
Sommer, V.M. Chernov // The Art of Scientific Computing. — 2006. — Р. 232–254.
4. Каліновський Я.О. Методи комп’ютерного моделювання та обчислень з використанням гі-
перкомплексних числових систем: дис. ... доктора техн. наук: 01.05.02 / Я.О.Каліновський; НТУУ
«КПІ» — К., 2007. — 417 с.
5. Рабинер Л. Теория и применение цифровой обработки сигналов / Л. Рабинер, Б. Гоулд. —
М.: Мир, 1978. — 848 с.
Надійшла до редакції 04.03.2009
|
| id | nasplib_isofts_kiev_ua-123456789-50367 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1560-9189 |
| language | Ukrainian |
| last_indexed | 2025-12-01T00:09:02Z |
| publishDate | 2009 |
| publisher | Інститут проблем реєстрації інформації НАН України |
| record_format | dspace |
| spelling | Синьков, М.В. Закидальський, А.І. Цибульська, Є.О. 2013-10-12T10:05:32Z 2013-10-12T10:05:32Z 2009 Алгоритм обчислення одновимірної згортки з використанням гіперкомплексних чисел / М.В. Синьков, А.І. Закидальський, Є.О. Цибульська // Реєстрація, зберігання і оброб. даних. — 2009. — Т. 11, № 1. — С. 20-26. — Бібліогр.: 5 назв. — укр. 1560-9189 https://nasplib.isofts.kiev.ua/handle/123456789/50367 620.179.15:004.421.2 Представлено алгоритм обчислення одновимірної дійсної згортки з переходом до двовимірного перетворення Фур’є і використанням гіперкомплексних чисел. Проведено аналіз обчислювальної складності розробленого алгоритму при використанні різних гіперкомплексних числових систем. Представлен алгоритм вычисления одномерной действительной свертки с переходом к двумерному преобразованию Фурье и использованием гиперкомплексных чисел. Проведен анализ вычислительной сложности разработанного алгоритма при использовании различных гиперкомплексных числовых систем. The algorithm for computing 1D real convolution with conversion to 2D Fourier transform and using hypercomplex numbers is presented. The computing complexity of developed algorithm by using various hypercomplex numerical systems is analyzed. uk Інститут проблем реєстрації інформації НАН України Реєстрація, зберігання і обробка даних Математичні методи обробки даних Алгоритм обчислення одновимірної згортки з використанням гіперкомплексних чисел Алгоритм вычисления одномерной свертки с использованием гиперкомплексных чисел Algorithm for Computing 1D-Convolution by Using Hypercomplex Numbers Article published earlier |
| spellingShingle | Алгоритм обчислення одновимірної згортки з використанням гіперкомплексних чисел Синьков, М.В. Закидальський, А.І. Цибульська, Є.О. Математичні методи обробки даних |
| title | Алгоритм обчислення одновимірної згортки з використанням гіперкомплексних чисел |
| title_alt | Алгоритм вычисления одномерной свертки с использованием гиперкомплексных чисел Algorithm for Computing 1D-Convolution by Using Hypercomplex Numbers |
| title_full | Алгоритм обчислення одновимірної згортки з використанням гіперкомплексних чисел |
| title_fullStr | Алгоритм обчислення одновимірної згортки з використанням гіперкомплексних чисел |
| title_full_unstemmed | Алгоритм обчислення одновимірної згортки з використанням гіперкомплексних чисел |
| title_short | Алгоритм обчислення одновимірної згортки з використанням гіперкомплексних чисел |
| title_sort | алгоритм обчислення одновимірної згортки з використанням гіперкомплексних чисел |
| topic | Математичні методи обробки даних |
| topic_facet | Математичні методи обробки даних |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/50367 |
| work_keys_str_mv | AT sinʹkovmv algoritmobčislennâodnovimírnoízgortkizvikoristannâmgíperkompleksnihčisel AT zakidalʹsʹkiiaí algoritmobčislennâodnovimírnoízgortkizvikoristannâmgíperkompleksnihčisel AT cibulʹsʹkaêo algoritmobčislennâodnovimírnoízgortkizvikoristannâmgíperkompleksnihčisel AT sinʹkovmv algoritmvyčisleniâodnomernoisvertkisispolʹzovaniemgiperkompleksnyhčisel AT zakidalʹsʹkiiaí algoritmvyčisleniâodnomernoisvertkisispolʹzovaniemgiperkompleksnyhčisel AT cibulʹsʹkaêo algoritmvyčisleniâodnomernoisvertkisispolʹzovaniemgiperkompleksnyhčisel AT sinʹkovmv algorithmforcomputing1dconvolutionbyusinghypercomplexnumbers AT zakidalʹsʹkiiaí algorithmforcomputing1dconvolutionbyusinghypercomplexnumbers AT cibulʹsʹkaêo algorithmforcomputing1dconvolutionbyusinghypercomplexnumbers |