Применение изоморфных гиперкомплексных числовых систем для синтеза быстрых алгоритмов линейной свертки
Рассмотрен метод повышения эффективности умножения гиперкомплексных чисел для построения быстрых алгоритмов линейной свертки. Он заключается в переходе к таким изоморфным гиперкомплексным числовым системам (ГЧС), где гиперкомплексное умножение требует меньшего числа вещественных умножений. Синтезиро...
Gespeichert in:
| Datum: | 2018 |
|---|---|
| Hauptverfasser: | , , , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут проблем реєстрації інформації НАН України
2018
|
| Schriftenreihe: | Реєстрація, зберігання і обробка даних |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/168764 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Применение изоморфных гиперкомплексных числовых систем для синтеза быстрых алгоритмов линейной свертки / Я.А. Калиновский,Ю.Е. Бояринова, А.С. Сукало, Я.В. Хицко // Реєстрація, зберігання і обробка даних. — 2018. — Т. 20, № 3. — С. 37–48. — Бібліогр.: 11 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-168764 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1687642020-05-08T22:07:18Z Применение изоморфных гиперкомплексных числовых систем для синтеза быстрых алгоритмов линейной свертки Калиновский, Я.А. Бояринова, Ю.Е. Сукало, А.С. Хицко, Я.В. Математичні методи обробки даних Рассмотрен метод повышения эффективности умножения гиперкомплексных чисел для построения быстрых алгоритмов линейной свертки. Он заключается в переходе к таким изоморфным гиперкомплексным числовым системам (ГЧС), где гиперкомплексное умножение требует меньшего числа вещественных умножений. Синтезированы такие пары изоморфных ГЧС, а также выражения операторов изоморфизма. Розглянуто метод підвищення ефективності множення гіперкомплексних чисел для побудови швидких алгоритмів лінійної згортки, який полягає в переході до таких ізоморфних гіпер-комплексних числових систем, де гіперкомплексне множення вимагає меншого числа дійсних множень. Синтезовано такі пари ізоморфних гіперкомплексних числових систем, а також вирази операторів ізоморфізму. The linear convolution of discrete signals is the most common computational task in the field of digital signal processing. The complexity of calculating the linear convolution of arrays n is long 0{n²} and rapidly increases when n grows, so the methods of «fast» calculations are used: a fast Fourier transform, a transition to a ring of polynomials. The method of increasing the efficiency of multiplying hypercomplex numbers to construct fast linear convolution algorithms is considered. 2018 Article Применение изоморфных гиперкомплексных числовых систем для синтеза быстрых алгоритмов линейной свертки / Я.А. Калиновский,Ю.Е. Бояринова, А.С. Сукало, Я.В. Хицко // Реєстрація, зберігання і обробка даних. — 2018. — Т. 20, № 3. — С. 37–48. — Бібліогр.: 11 назв. — рос. 1560-9189 DOI: https://doi.org/10.35681/1560-9189.2018.20.3.158516 http://dspace.nbuv.gov.ua/handle/123456789/168764 004.942 ru Реєстрація, зберігання і обробка даних Реєстрація, зберігання і обробка даних Інститут проблем реєстрації інформації НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Математичні методи обробки даних Математичні методи обробки даних |
| spellingShingle |
Математичні методи обробки даних Математичні методи обробки даних Калиновский, Я.А. Бояринова, Ю.Е. Сукало, А.С. Хицко, Я.В. Применение изоморфных гиперкомплексных числовых систем для синтеза быстрых алгоритмов линейной свертки Реєстрація, зберігання і обробка даних |
| description |
Рассмотрен метод повышения эффективности умножения гиперкомплексных чисел для построения быстрых алгоритмов линейной свертки. Он заключается в переходе к таким изоморфным гиперкомплексным числовым системам (ГЧС), где гиперкомплексное умножение требует меньшего числа вещественных умножений. Синтезированы такие пары изоморфных ГЧС, а также выражения операторов изоморфизма. |
| format |
Article |
| author |
Калиновский, Я.А. Бояринова, Ю.Е. Сукало, А.С. Хицко, Я.В. |
| author_facet |
Калиновский, Я.А. Бояринова, Ю.Е. Сукало, А.С. Хицко, Я.В. |
| author_sort |
Калиновский, Я.А. |
| title |
Применение изоморфных гиперкомплексных числовых систем для синтеза быстрых алгоритмов линейной свертки |
| title_short |
Применение изоморфных гиперкомплексных числовых систем для синтеза быстрых алгоритмов линейной свертки |
| title_full |
Применение изоморфных гиперкомплексных числовых систем для синтеза быстрых алгоритмов линейной свертки |
| title_fullStr |
Применение изоморфных гиперкомплексных числовых систем для синтеза быстрых алгоритмов линейной свертки |
| title_full_unstemmed |
Применение изоморфных гиперкомплексных числовых систем для синтеза быстрых алгоритмов линейной свертки |
| title_sort |
применение изоморфных гиперкомплексных числовых систем для синтеза быстрых алгоритмов линейной свертки |
| publisher |
Інститут проблем реєстрації інформації НАН України |
| publishDate |
2018 |
| topic_facet |
Математичні методи обробки даних |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/168764 |
| citation_txt |
Применение изоморфных гиперкомплексных числовых систем для синтеза быстрых алгоритмов линейной свертки / Я.А. Калиновский,Ю.Е. Бояринова, А.С. Сукало, Я.В. Хицко // Реєстрація, зберігання і обробка даних. — 2018. — Т. 20, № 3. — С. 37–48. — Бібліогр.: 11 назв. — рос. |
| series |
Реєстрація, зберігання і обробка даних |
| work_keys_str_mv |
AT kalinovskijâa primenenieizomorfnyhgiperkompleksnyhčislovyhsistemdlâsintezabystryhalgoritmovlinejnojsvertki AT boârinovaûe primenenieizomorfnyhgiperkompleksnyhčislovyhsistemdlâsintezabystryhalgoritmovlinejnojsvertki AT sukaloas primenenieizomorfnyhgiperkompleksnyhčislovyhsistemdlâsintezabystryhalgoritmovlinejnojsvertki AT hickoâv primenenieizomorfnyhgiperkompleksnyhčislovyhsistemdlâsintezabystryhalgoritmovlinejnojsvertki |
| first_indexed |
2025-07-15T03:31:57Z |
| last_indexed |
2025-07-15T03:31:57Z |
| _version_ |
1837682201779503104 |
| fulltext |
ISSN 1560-9189 , , 2018, . 20, 3 37
004.942
. . 1, . . 1,2,
. . 3, . . 2
1
. . , 2, 03113 ,
2 « . »
, 37, 03113 ,
3
. , 11, 33028 ,
-
.
( ),
. -
, .
: ,
, , , , .
-
. -
, , , -
, —
,
, .
n
)( 2nO n , « »
.
.
1. ( )
)log( nnO . [1, 2]
.
-
, , , .
© . . , . . , . . , . .
. . , . . , . . , . .
38
2. [1]. ,
, , ,
, .
.
[1] -
12n , -
. , [1]: «
.
,
.
, ,
, ,
, ,
, . -
, ,
, ,
, « » , -
».
-
( ) .
, , ,
( , — , -
— H ), , -
. -
[4, 5].
, , -
.
. -
. n ,
n - , :
1) 2 1n , -
n ;
2) n
, — 1 n .
, ,
N ,
,
3n N n ,
2n .
ISSN 1560-9189 , , 2018, . 20, 3 39
-
. -
[3], -
. , [4]
,
, - , -
— . .
1. ( ,2)W e 1( , 2)W f .
( ,2)W e , 1( , 2)W f
:
W 1e 2e
1e 1e 2e
2e 2e 1e
1W 1f 2f
1f 1f 0
2f 0 2f
(1)
, 2W e 4 -
2 , -
1 ,2R R W f — 2 .
, , 2W e
1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 2( )( ) ( ) ( )a e a e b e b e a b a b e a b a b e , (2)
1 ,2R R W f —
1 1 2 2 1 1 2 2 1 1 1 2 2 2( )( )c f c f d f d f c d f c d f . (3)
[4, 5]:
1 1
2 1 2
,
:
.
e f f
L
e f f (4)
, ,
(2). (2) , 2W e 1 ,2R R W f , -
(4). (3), ,
L
1 1 21
2 1 2
/ 2
:
/ 2
f e e
L
f e e
(5)
, 2W e .
(2). , (2) -
. . , . . , . . , . .
40
2 4. , (2)
2×2.
(4) (5) , « » , 2W e 1 ,2R R W f -
— 6 2 2. -
, ,
4. , 2 — ,
. , ,
. , -
2 4 , -
.
2. 33G 3R -
R .
.
(6)
33G 3×3,
9
— , -
3×3.
9 . - -
[3], 33G 3R ,
R , R , -
R .
33G 3R . [5] -
3 3 3 3 3
1 1 =1 =1 =1
, , , 1,...,3k r
ks ij ik js ks
k s k s r
i j k , (7)
r
ks — , ks —
33G 3R , 27
(7) , -
, . ,
33G 3R .
33G R . (7) 21 -
, :
33G 1e 2e 3e
1e 1e 2e 3e
2e 2e 3e 1e
3e 3e 1e 2e
3R 1f 2f 3f
1f 1f 0 0
2f 0 2f 0
3f 0 0 3f
R 1f 2f 3f
1f 1f 0 0
2f 0 2f 3f
3f 0 3f 2f
ISSN 1560-9189 , , 2018, . 20, 3 41
1 1 2 2 1 2 2 2 1 2 2
1 3 1 3= , = , = .
2 2 2 2
e f f e f f f e f f f (8)
3 3 0
2
, -
, 33G R . , -
, R 4 -
. , (8), 33G R -
4 ( , 2 — -
). -
33G R 8
, 1
.
-
T [4, 5], :
(9)
R .
(7) -
, :
1 1 2
2 3
3 1 2
,
: ,
.
e f f
L e f
e f f
1 1 3
1
2 1 3
3 2
( ) / 2,
: ( ) / 2,
.
f e e
L f e e
f e
(10)
(10), T R -
, -
2.
5 . 4, -
-
:
( )( ) = ( ( ) ( )) ( ( ) ( ))a bi c di a c d d a b i b c d d a b . (11)
, -
. -
, , 2n ,
. , [5], -
.
T 1e 2e 3e
1e 1e 2e 3e
2e 2e 3 1( ) / 2e e 2e
3e 3e 2e 1e
. . , . . , . . , . .
42
, .
(9). -
, . , - , -
, , - , [4],
(9) . (9) — 3n
2n , -
. n — . 4n -
Maple , 4n
. -
, [5, 6], .
-
[5]. , , -
, , -
, .
.
, -
- -
[5].
- ,
-
, , - 2.
, 2,
, -
,
. , , -
.
1( , )e n 2 ( , )f m : 1 2, , ,e n f m .
.
, -
. , -
, -
. , -
, .
, [5], :
1) -
;
2) -
;
3) -
, ,
ISSN 1560-9189 , , 2018, . 20, 3 43
,
.
-
, , -
, , , -
. -
,
.
,
, .
, 2W e 1 , 2W f
4.
. :
1 1 3, 2 , 2 , 2 , 2e W e W f f 2 1 4, 2 ,2 ,2 ,2g W g W h h .
1 , 2e 3 , 2f
(4) (5). 2 , 2g 4 , 2h -
:
1 1 2
2
2 1 2
:
g h h
L
g h h
, 1 1 21
2
2 1 2
/ 2,
:
/ 2.
h g g
L
h g g
(12)
1 2 ( 3
4 ):
5 1 2, 4 , 2 , , 2eg e g , 6 3 4, 4 , 2 , , 2fh f h .
5 6 4.
5 6 . :
=i j r s i r j s m ne g e g e e g g e g , i j r s i r j s m nf h f h f f h h f h , , , , 1,2i j r s .
2( 1)m n m ne g e , (13)
5 6
2W 1
(2)W ,
:
. . , . . , . . , . .
44
(14)
2W — , 2
1W — -
.
56L , -
eg fh ( ),
56 2L L L ,
:
1 1 1
56 65 2L L L L .
(12),
2W 2
1W , :
1 1 2 3 4
2 1 2 3 4
3 1 2 3 4
4 1 2 3 4
,
,
,
.
e f f f f
e f f f f
e f f f f
e f f f f
1 1 2 3 4
2 1 2 3 4
3 1 2 3 4
4 1 2 3 4
/ 4,
/ 4,
/ 4,
/ 4.
f e e e e
f e e e e
f e e e e
f e e e e
. (15)
(14)
2W 2
1W e f .
, 4 -
2
1W , (15)
2
1W , (14),
(15) 2
1W . , 16
12 4 24
, 4 .
[7–10] , -
2W 1e 2e 3e 4e
1e 1e 2e 3e 4e
2e 2e 1e 4e 3e
3e 3e 4e 1e 2e
4e 4e 3e 2e 1e
2
1W 1f 2f 3f 4f
1f 1f 0 0 0
2f 0 2f 0 0
3f 0 0 3f 0
4f 0 0 0 4f
ISSN 1560-9189 , , 2018, . 20, 3 45
. -
K . -
. K
CC , .
[4–6] .
(7).
(16)
-
(7). :
1 1 3
2 2 4
3 2 4
4 1 3
,
,
:
,
.
e f f
e f f
L
e f f
e f f
1 1 4
2 2 31
3 1 4
4 2 3
/ 2,
/ 2,
:
/ 2,
/ 2.
f e e
f e e
L
f e e
f e e
(17)
, K
16 12 , -
CC
(11) 6 , 18 4 -
2.
, 4 ,4K e C C f 1, 2 ,2W g W h
8- .
, 4K e , , 2W g :
( ,4), ,2 ,8K e W g KW eg ,
( ,4)C C f , 1( , 2)W h :
1, 4 , , 2 ,8C C f W h CCW fh .
, , -
KW CCW :
K 1e 2e 3e 4e
1e 1e 2e 3e 4e
2e 2e 1e 4e 3e
3e 3e 4e 1e 2e
4e 4e 3e 2e 1e
CC 1f 2f 3f 4f
1f 1f 2f 0 0
2f 2f 1f 0 0
3f 0 0 3f 4f
4f 0 0 4f 3f
. . , . . , . . , . .
46
KW 1e 2e 3e 4e 5e 6e 7e 8e
1e 1e 2e 3e 4e 5e 6e 7e 8e
2e 2e 1e 4e 3e 6e 5e 8e 7e
3e 3e 4e 1e 2e 7e 8e 5e 6e
4e 4e 3e 2e 1e 8e 7e 6e 5e
5e 5e 6e 7e 8e 1e 2e 3e 4e
6e 6e 5e 8e 7e 2e 1e 4e 3e
7e 7e 8e 5e 6e 3e 4e 1e 2e
8e 8e 7e 6e 5e 4e 3e 2e 1e
CCW 1f 2f 3f 4f 5f 6f 7f 8f
1f 1f 0 3f 0 0 0 0 0
2f 0 2f 0 4f 0 0 0 0
3f 3f 0 1f 0 0 0 0 0
4f 0 4f 0 2f 0 0 0 0
5f 0 0 0 0 5f 0 7f 0
6f 0 0 0 0 0 6f 0 8f
7f 0 0 0 0 7f 0 5f 0
8f 0 0 0 0 0 8f 0 6f
-
(7). :
1 1 2 5 6
2 1 2 5 6
3 3 4 7 8
4 3 4 7 8
5 3 4 7 8
6 3 4 7 8
7 1 2 5 6
8 1 2 5 6
,
,
,
,
:
,
,
,
.
e f f f f
e f f f f
e f f f f
e f f f f
L
e f f f f
e f f f f
e f f f f
e f f f f
1 1 2 7 8
2 1 2 7 8
3 3 4 5 6
4 3 4 5 61
5 1 2 7 8
6 1 2 7 8
7 3 4 5 6
8 3 4 5 6
/ 4,
/ 4,
/ 4,
/ 4,
:
/ 4,
/ 4,
/ 4,
/ 4.
f f f f f
f f f f f
f f f f f
f f f f f
L
f f f f f
f f f f f
f f f f f
f f f f f
,
KW 64 56 ,
CCW 16 , 72
8 4.
ISSN 1560-9189 , , 2018, . 20, 3 47
2n
,
, 2. -
, : T -
- R , W 1W
:
T R , 1W W .
:
,3 , ,2 ,6T e W g TW eg ,
1,3 , ,2 ,6R C f W h RCW fh ,
:
TW R W .
, , -
TW RCC :
-
(7). :
TW 1e 2e 3e 4e 5e 6e
1e 1e 2e 3e 4e 5e 6e
2e 2e 1e 4e 3e 6e 5e
3e 3e 4e 5 1( ) / 2e e 6 2( ) / 2e e 3e 4e
4e 4e 3e 6 2( ) / 2e e 5 1( ) / 2e e 4e 3e
5e 5e 6e 3e 4e 1e 2e
6e 6e 5e 4e 3e 2e 1e
RCC 1f 2f 3f 4f 5f 6f
1f 1f 0 0 0 0 0
2f 0 2f 0 0 0 0
3f 0 0 3f 0 5f 0
4f 0 0 0 4f 0 6f
5f 0 0 5f 0 3f 0
6f 0 0 0 6f 0 4f
. . , . . , . . , . .
48
1 1 2 3 4
2 1 2 3 4
3 5 6
4 5 6
5 1 2 3 4
6 1 2 3 4
,
,
( ) / 2,
:
( ) / 2,
,
.
e f f f f
e f f f f
e f f
L
e f f
e f f f f
e f f f f
1 1 2 3 4
2 1 2 3 4
3 1 2 3 41
4 1 2 3 4
5 3 4
6 3 4
( ) / 4,
( ) / 4,
( ) / 4,
:
( ) / 4,
( ) / 2,
( ) / 2.
f e e e e
f e e e e
f e e e e
L
f e e e e
f e e
f e e
, 6- TW
40 30 , -
CCW 10 , 42 -
10 4.
,
, , -
-
, , .
2n n , -
/ 2n . -
.
1. . . : , 1989. 449 .
2. . . :
, 1985. 248 .
3. . ., . . . : , 1980. 192 .
3. . ., . ., . .
. . . : , 2010. 388 .
4. . ., . .
. : -
, 2012. 183 .
5. . . -
. .
2017. . 39. 1. . 75–90.
6. Toyoshima H. Computationally Efficient Implementation of Hypercomplex Digital Filters.
Trans. Fundamentals. 2002. Aug. E85-A. 8. P. 1870–1876.
7. Schutte H.D. Digitalfilter zur Verarbeitung komplexer und hypercomplexer Signale. Disserta-
tion. Paderborn, 1991. 100 .
8. Schulz D., Seitz J., LustosadaCosta J.P. Widely Linear SIMO Filtering for Hypercomplex Num-
bers. IEEE Information Theory Workshop. 2011. P. 390–394.
9. . ., . ., . . -
. . 2015. . 37. 5. . 117–126.
10. . . -
’ : . … . . . , 2007. 308 .
11. . .
. , . . 2013. . 15. 1. . 31–44.
21.06.2018
|