Структура гиперкомплексного метода быстрого вычисления линейной свертки дискретных сигналов
Исследован метод быстрого вычисления линейной свертки числовых массивов длиной 2ⁿ с помощью представления их в специальных, гиперкомплексных числовых системах, имеющих изоморфные им системы, выполнение гиперкомплексных операций в которых требует меньшего количества вещественных операций....
Gespeichert in:
| Datum: | 2013 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут проблем реєстрації інформації НАН України
2013
|
| Schriftenreihe: | Реєстрація, зберігання і обробка даних |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/87053 |
| 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: | Структура гиперкомплексного метода быстрого вычисления линейной свертки дискретных сигналов / Я.А. Калиновский // Реєстрація, зберігання і обробка даних. — 2013. — Т. 15, № 1. — С. 31-44. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-87053 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-870532015-10-11T03:02:32Z Структура гиперкомплексного метода быстрого вычисления линейной свертки дискретных сигналов Калиновский, Я.А. Математичні методи обробки даних Исследован метод быстрого вычисления линейной свертки числовых массивов длиной 2ⁿ с помощью представления их в специальных, гиперкомплексных числовых системах, имеющих изоморфные им системы, выполнение гиперкомплексных операций в которых требует меньшего количества вещественных операций. The method for fast evaluation of linear convolution of long arrays of numbers 2n by representing them in special hypercomplex number systems and having isomorphic to these systems, the implementation of hypercomplex operations that require less real operations, has been investigated. 2013 Article Структура гиперкомплексного метода быстрого вычисления линейной свертки дискретных сигналов / Я.А. Калиновский // Реєстрація, зберігання і обробка даних. — 2013. — Т. 15, № 1. — С. 31-44. — Бібліогр.: 10 назв. — рос. 1560-9189 http://dspace.nbuv.gov.ua/handle/123456789/87053 004.942 ru Реєстрація, зберігання і обробка даних Інститут проблем реєстрації інформації НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Математичні методи обробки даних Математичні методи обробки даних |
| spellingShingle |
Математичні методи обробки даних Математичні методи обробки даних Калиновский, Я.А. Структура гиперкомплексного метода быстрого вычисления линейной свертки дискретных сигналов Реєстрація, зберігання і обробка даних |
| description |
Исследован метод быстрого вычисления линейной свертки числовых массивов длиной 2ⁿ с помощью представления их в специальных, гиперкомплексных числовых системах, имеющих изоморфные им системы, выполнение гиперкомплексных операций в которых требует меньшего количества вещественных операций. |
| format |
Article |
| author |
Калиновский, Я.А. |
| author_facet |
Калиновский, Я.А. |
| author_sort |
Калиновский, Я.А. |
| title |
Структура гиперкомплексного метода быстрого вычисления линейной свертки дискретных сигналов |
| title_short |
Структура гиперкомплексного метода быстрого вычисления линейной свертки дискретных сигналов |
| title_full |
Структура гиперкомплексного метода быстрого вычисления линейной свертки дискретных сигналов |
| title_fullStr |
Структура гиперкомплексного метода быстрого вычисления линейной свертки дискретных сигналов |
| title_full_unstemmed |
Структура гиперкомплексного метода быстрого вычисления линейной свертки дискретных сигналов |
| title_sort |
структура гиперкомплексного метода быстрого вычисления линейной свертки дискретных сигналов |
| publisher |
Інститут проблем реєстрації інформації НАН України |
| publishDate |
2013 |
| topic_facet |
Математичні методи обробки даних |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/87053 |
| citation_txt |
Структура гиперкомплексного метода быстрого вычисления линейной свертки дискретных сигналов / Я.А. Калиновский // Реєстрація, зберігання і обробка даних. — 2013. — Т. 15, № 1. — С. 31-44. — Бібліогр.: 10 назв. — рос. |
| series |
Реєстрація, зберігання і обробка даних |
| work_keys_str_mv |
AT kalinovskijâa strukturagiperkompleksnogometodabystrogovyčisleniâlinejnojsvertkidiskretnyhsignalov |
| first_indexed |
2025-07-06T14:37:14Z |
| last_indexed |
2025-07-06T14:37:14Z |
| _version_ |
1836908685117358080 |
| fulltext |
ISSN 1560-9189 , , 2013, . 15, 1 31
004.942
. .
. . , 2, 03113 ,
n2 -
, ,
.
: , ,
, , .
-
.
, , , -
, —
.
n
)( 2nO , n , « »
.
( )
)log( nnO . -
-
.
, , , -
.
[1] -
12n , -
. , [2]: «
-
© . .
. .
32
. -
, -
. -
,
, , -
, , -
, . -
, ,
, ,
, « » , -
».
n2 . -
, -
( ) 1
n2dim 1 . -
. -
,
. ,
n22 , . .
, , .
, : — -
; -
— .
,
.
,
, . -
[4, 5].
.
.
,
[3, 4]
- , -
W 1W ( [4]),
:
ISSN 1560-9189 , , 2013, . 15, 1 33
011
100
10
:
eee
eee
eeW
W
11
00
101
1
0
0:
ff
ff
ffW
W . (1)
1
~ WW :
0 0 1
1 0 1
,
,
e f f
e f f
0 0 1
1 0 1
( ) / 2,
( ) / 2.
f e e
f e e
(2)
[5] – [6] -
- ,
. ,
-
.
)4,,(~)4,,( 11
2
1
)2( WWWWWW .
: )2(W — .
— , .
— :
01234
10322
23011
32100
3210
)2(
)2( :)4,,(
eeeee
eeeee
eeeee
eeeee
eeeeW
WWW
33
22
11
00
3210
)2(
1
11
)2(
1
000
000
000
000
:)4,,(
ff
ff
ff
ff
ffffW
WWW .(3)
)2(
1
)2( ~ WW :
0 0 1 2 3
1 0 1 2 3
2 0 1 2 3
3 0 1 2 3
,
,
,
,
e f f f f
e f f f f
e f f f f
e f f f f
0 0 1 2 3
1 0 1 2 3
2 0 1 2 3
3 0 1 2 3
( ) / 4,
( ) / 4,
( ) / 4,
( ) / 4.
f e e e e
f e e e e
f e e e e
f e e e e
(4)
)8,),4,,((~)8,),4,,(( 111
)2(
1
)3(
1
)2()3( WWWWWWWWWW .
)3(W ( )3(
1W ) )2(W (
)2(
1W ) W 1W
. .
34
)8,,,()3( WWWW :
012345677
103254766
230167455
321076544
456701233
547610322
674523011
765432100
76543210
)3(
eeeeeeeee
eeeeeeeee
eeeeeeeee
eeeeeeeee
eeeeeeeee
eeeeeeeee
eeeeeeeee
eeeeeeeee
eeeeeeeeW
. (5)
)3(
1W - .
, )4,,( 11
)2(
1 WWW (3), -
88 .
)3(
1
)3( ~ WW :
0 0 1 2 3 4 5 6 7
1 0 1 2 3 4 5 6 7
2 0 1 2 3 4 5 6 7
3 0 1 2 3 4 5 6 7
4 0 1 2 3 4 5 6 7
5 0 1 2 3 4 5 6 7
6 0 1 2 3 4 5 6 7
7 0 1 2
,
,
,
,
,
,
,
e f f f f f f f f
e f f f f f f f f
e f f f f f f f f
e f f f f f f f f
e f f f f f f f f
e f f f f f f f f
e f f f f f f f f
e f f f 3 4 5 6 7 ,f f f f f
0 0 1 2 3 4 5 6 7
1 0 1 2 3 4 5 6 7
2 0 1 2 3 4 5 6 7
3 0 1 2 3 4 5 6 7
4 0 1 2 3 4 5 6 7
5 0 1 2 3 4 5 6 7
6 0 1 2
( ) / 8,
( ) / 8,
( ) / 8,
( ) / 8,
( ) / 8,
( ) / 8,
(
f e e e e e e e e
f e e e e e e e e
f e e e e e e e e
f e e e e e e e e
f e e e e e e e e
f e e e e e e e e
f e e e e3 4 5 6 7
7 0 1 2 3 4 5 6 7
) / 8,
( ) / 8.
e e e e
f e e e e e e e e
(6)
, n2
n .
. , ,
.
[1, 2, 7]:
)()()( mkymxkz
k
m
. (7)
n2 -
, 12 1n n22
. -
.
ISSN 1560-9189 , , 2013, . 15, 1 35
. 1n , . .
— 10 , xx 10 , yy . (7)
:
0 0
0 1 1 0
1 1
( 1) ,
(0) ,
(1) .
z x y
z x y x y
z x y
(8)
(8), 4
.
10 , xx 10 , yy
W (1):
1100 exexX , (9)
1001 eyeyY . (10)
.
W
1110000110 )()( eyxyxeyxyxXY . (11)
(11) , -
(8). , 0e
)1(z , 1e .
4, (8). -
, : - ,
(11), , - — )0(z )2(z .
W 1W . 111, WYX (9)
(10) (2). :
1100101 )()( fxxfxxX , (12)
1010011 )()( fyyfyyY . (13)
4 . , ,
,
1W , , W
1W 2 .
(12) (13) 1W
1011000110110011 ))(())(( fyyxxfyyxxffYX (14)
. .
36
2 .
1W W -
(2) :
1
10
0
10
22
eeXY , (15)
2 . 2 — ,
. .
(11) (15), :
2
10
0110 yxyx , (16)
2
10
1100 yxyx . (17)
(17), ,
00 yx , (8) :
0 0
0 1
0 1
0 0
( 1) ,
(0) ,
2
(1) ,
2
z x y
z
z x y
(18)
3 5 . (8) -
4 1 . -
. , , -
. , ,
.
yx0 ( . 1). -
, -
, — .
,
.
0 1
0 y
1
. 1. = 1
ISSN 1560-9189 , , 2013, . 15, 1 37
2n , . . —
3210 ,,, xxxx 3210 ,,, yyyy . (7) 7 :
0 0
0 1 1 0
0 2 1 1 2 0
0 3 1 2 2 1 3 0
1 3 2 2 3 1
2 3 3 2
3 3
( 3) ,
( 2) = ,
( 1) = ,
(0) ,
(1) ,
(2) ,
(3) .
z x y
z x y x y
z x y x y x y
z x y x y x y x y
z x y x y x y
z x y x y
z x y
(19)
16 -
9 .
3210 ,,, xxxx 3210 ,,, yyyy
)2(W (3):
33221100 exexexexX . (20)
30211203 eyeyeyeyY . (21)
)2(W (20) (21)
:
3
0i
iieXY , (22)
i :
0 0 3 1 2 2 1 3 0
1 0 2 1 3 2 0 3 1
2 0 1 1 0 2 3 3 2
3 0 0 1 1 2 2 3 3
,
,
,
.
x y x y x y x y
x y x y x y x y
x y x y x y x y
x y x y x y x y
(23)
)2(W (2)
1W . )2(W (2)
1W
(20) (21) (3), :
3
1 0 1 2 3 0 0 1 2 3 1
0
0 1 2 3 2 0 1 2 3 3
= ( ) ( )
( ) ( ) .
i i
i
X f x x x x f x x x x f
x x x x f x x x x f
(24)
. .
38
1Y :
i
i
i fY
3
0
1 . (25)
16 . , ,
,
1W , , (2)W
(2)
1W 8 .
(24) (25) (2)
1W
i
i
ii fYX
3
0
11 (26)
4 .
(3)
:
3
0 0 1 1 2 2 3 3 0 0 0 1 1 2 2 3 3 1
0
0 0 1 1 2 2 3 3 2 0 0 1 1 2 2 3 3 3
1 1( ) ( )
4 4
1 1 ( ) ( ) ,
4 4
i i
i
XY e e e
e e
(27)
8 . 4 — , -
. .
( M )
( A ) :
0 0
0 1 1 0
0 2 1 1 2 0
0
( 3) = 1 ,
( 2) = 2 1 ,
( 1) = 3 2 ,
(0) =
z x y M
z x y x y M A
z x y x y x y M A
z
1 0 2 2 0 2 2
2 0 1 1 0
3 0 0 1 1 2 2
4 ,
(1) = ( ) 1M 2 ,
(2) = ( ) 1 ,
(3) = ( ) 3 .
M
z x y x y x y A
z x y x y A
z x y x y x y A
(28)
11 25 ( 16 , -
(2)W (2)
1W ).
-
( . 2).
ISSN 1560-9189 , , 2013, . 15, 1 39
0 1 2 3
0 y
1
2
3
. 2. 2n
3n , -
– 70 ,..., xx 80 ,..., yy . (7) 15
, . 3.
. 3. 32
64
49 .
( 2,1n ),
8- )3(
1
)3( ~ WW , (6).
:
)7(z 00 yx
)6(z 10 yx 01yx
)5(z 20 yx 11yx 02 yx
)4(z 30 yx 21yx 12 yx 03 yx
)3(z 40 yx 31yx 22 yx 13 yx 04 yx
)2(z 50 yx 41yx 32 yx 23 yx 14 yx 05 yx
)1(z 60 yx 51yx 42 yx 33 yx 24 yx 15 yx 06 yx
(0)z 0 7x y 1 6x y 2 5x y 3 4x y 4 3x y 5 2x y 6 1x y 7 0x y
)1(z 71yx 62 yx 53 yx 44 yx 35 yx 26 yx 17 yx
)2(z 72 yx 63 yx 54 yx 45 yx 36 yx 27 yx
)3(z 73 yx 64 yx 55 yx 46 yx 37 yx
)4(z 74 yx 65 yx 6 5x y 7 4x y
(5)z 5 7x y 66 yx 7 5x y
)6(z 76 yx 67 yx
)7(z 77 yx
. .
40
i
i
iexX
7
0
, (30)
.
7
0
7
i
iieyY (31)
)3(W (30) (31)
:
7
0i
iieXY ,
i :
0 0 7 1 6 2 5 3 4 4 3 5 2 6 1 7 0
1 0 6 1 7 2 4 3 5 4 2 5 3 6 0 7 1
2 0 5 1 4 2 7 3 6 4 1 5 0 6 3 7 2
3 0 4 1 5 2 6 3 7 4 0 5 1 6 2 7 3
4 0 3 1 2 2 1 3 0 4 7
,
,
,
,
x y x y x y x y x y x y x y x y
x y x y x y x y x y x y x y x y
x y x y x y x y x y x y x y x y
x y x y x y x y x y x y x y x y
x y x y x y x y x y 5 6 6 5 7 4
5 0 2 1 3 2 0 3 1 4 6 5 7 6 4 7 5
6 0 1 1 0 2 3 3 2 4 5 5 4 6 7 7 6
7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7
,
,
,
.
x y x y x y
x y x y x y x y x y x y x y x y
x y x y x y x y x y x y x y x y
x y x y x y x y x y x y x y x y
(32)
)3(W )3(
1W (30) (31) -
(6). :
7
1 0 1 2 3 4 5 6 7 0
0
0 1 2 3 4 5 6 7 1
0 1 2 3 4 5 6 7 2
0 1 2 3 4 5 6 7 3
= ( )
( )
( )
( )
i i
i
X f x x x x x x x x f
x x x x x x x x f
x x x x x x x x f
x x x x x x x x f
0 1 2 3 4 5 6 7 4
0 1 2 3 4 5 6 7 5
0 1 2 3 4 5 6 7 6
0 1 2 3 4 5 6 7 7
( )
( )
( )
( ) .
x x x x x x x x f
x x x x x x x x f
x x x x x x x x f
x x x x x x x x f
(33)
1Y :
i
i
i fY
7
0
1 . (34)
ISSN 1560-9189 , , 2013, . 15, 1 41
32 .
(33) (34) )3(
1W
i
i
ii fYX
7
0
11 (35)
8 .
)3(
1W )3(W
(6). 32 . 8 — -
, . -
.
, 45 118 -
( 64 , )2(W )2(
1W
).
-
( . 4).
0 1 2 3 4 5 6 7
0 y
1
2
3
4
5
6
7
. 4. = 3
( 3n ), -
[9].
, )()(
1
ii WW
i2 . , -
, Y
i2 ( [1, 2] « »).
,
,
.
. .
42
%
1 2 4 1 25
2 4 16 5 31,3
3 8 64 19 30
,
.
2 2 ( 1n )
, [1, 2].
, , .
— nn 22 m2
mnmn 22 . , , 3210 ,,, xxxx
3210 ,,, yyyy 4- 10 , xx 10 , yy , 10 , xx
32 , yy , 32 , xx 10 , yy , 32 , xx 32 , yy , -
( . 5):
. 5.
1243 ,
44 . , 5
.
— . -
44 . -
10 , xx 10 , yy . 3 , 11yx
0110 yxyx . 10 xx
, . -
20 , xx 20 , yy . 2 -
)3(z 00 yx
)2(z 10 yx 10 yx
)1(z 20 yx 11yx 02 yx
)0(z 30 yx 21yx 12 yx 03 yx
)1(z 31yx 22 yx 13 yx
)2(z 32 yx 23 yx
)3(z 33 yx
ISSN 1560-9189 , , 2013, . 15, 1 43
22 yx 0220 yxyx ,
. , ,
5 . ,
.
, 9 30 -
( 5 10 22 ,
14 , )2(W )2(
1W ).
88 .
00 yx ,
10 , xx 10 , yy , 20 , xx 20 , yy ,…, 60 , xx 60 , yy ,
13 24 .
X )3(W )3(
1W , 30 .
)3(
1W 8 . )3(
1W
)3(W 32 . ,
, :
44 127 . , -
44
( AM 309 ), , 88
4 44 . 13
88 -
36 140 .
)7(z 00 yx –
)6(z 10 yx 01yx –
)5(z 20 yx 11yx 02 yx A1
)4(z 30 yx 21yx 12 yx 03 yx AM 22
)3(z 40 yx 31yx 22 yx 13 yx 04 yx AM 32
)2(z 50 yx 41yx 32 yx 23 yx 14 yx 05 yx AM 44
)1(z 60 yx 51yx 42 yx 33 yx 24 yx 15 yx 06 yx AM 54
)0(z 0 –
)1(z 264462062442601 )( yxyxyxyxyxyxyx AM 32
)2(z 4554051441502 )( yxyxyxyxyxyx AM 22
)3(z )( 2615046251403 yxyxyxyxyxyx + 64 yx 55 yx 46 yx AM 64
)4(z 4 ( 03122130 yxyxyxyx ) A2
)5(z 5 ( 466413023120 yxyxyxyxyxyx )+ 66 yx AM 41
)6(z 6 ( 455423320110 yxyxyxyxyxyx ) A2
)7(z 7 ( 00 yx 11yx 22 yx 33 yx 44 yx 55 yx 66 yx ) A7
. .
44
, -
.
, -
-
.
1. . / . . .: ,
1989. 449 .
2. . /
. . — .: , 1985. — 248 .
3. . . / . . , . . . — .: ,
1973. — 144 .
4. . . . .
/ . . , . . , . . . — .: , 2010. — 388 .
5. . .
/ . . , . . -
. — .: , 2012. — 183 .
6. Chaitin-Chatelin F. Computation with Hypercomplex Numbers [ ] /
Chaitin-Chatelin F., Meskauskas T., Zaoui A. // GERFACS Technical Report TR/PA/00/69. —
: http://www.gerfacs.fr (2000)
7. . . / . . . — .: , 2003. —
604 .
8. . .
/ . . // , .
. — 2011. — . 13, 3. — . 30–39.
9. . / . , . // . -
. — 2012. — . 55, 10. — . 44–54.
10. . . , , /
. . . — .: , 2008. — 316 .
13.02.2013
http://www.gerfacs.fr
|