Структура гиперкомплексного метода быстрого вычисления линейной свертки дискретных сигналов
Исследован метод быстрого вычисления линейной свертки числовых массивов длиной 2ⁿ с помощью представления их в специальных, гиперкомплексных числовых системах, имеющих изоморфные им системы, выполнение гиперкомплексных операций в которых требует меньшего количества вещественных операций. The method...
Збережено в:
| Опубліковано в: : | Реєстрація, зберігання і обробка даних |
|---|---|
| Дата: | 2013 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем реєстрації інформації НАН України
2013
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/87053 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Структура гиперкомплексного метода быстрого вычисления линейной свертки дискретных сигналов / Я.А. Калиновский // Реєстрація, зберігання і обробка даних. — 2013. — Т. 15, № 1. — С. 31-44. — Бібліогр.: 10 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-87053 |
|---|---|
| record_format |
dspace |
| spelling |
Калиновский, Я.А. 2015-10-10T12:37:16Z 2015-10-10T12:37:16Z 2013 Структура гиперкомплексного метода быстрого вычисления линейной свертки дискретных сигналов / Я.А. Калиновский // Реєстрація, зберігання і обробка даних. — 2013. — Т. 15, № 1. — С. 31-44. — Бібліогр.: 10 назв. — рос. 1560-9189 https://nasplib.isofts.kiev.ua/handle/123456789/87053 004.942 Исследован метод быстрого вычисления линейной свертки числовых массивов длиной 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. ru Інститут проблем реєстрації інформації НАН України Реєстрація, зберігання і обробка даних Математичні методи обробки даних Структура гиперкомплексного метода быстрого вычисления линейной свертки дискретных сигналов The Structure of a Hyper Fast Calculation Method Linear Convolution of Discrete Signals Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Структура гиперкомплексного метода быстрого вычисления линейной свертки дискретных сигналов |
| spellingShingle |
Структура гиперкомплексного метода быстрого вычисления линейной свертки дискретных сигналов Калиновский, Я.А. Математичні методи обробки даних |
| title_short |
Структура гиперкомплексного метода быстрого вычисления линейной свертки дискретных сигналов |
| title_full |
Структура гиперкомплексного метода быстрого вычисления линейной свертки дискретных сигналов |
| title_fullStr |
Структура гиперкомплексного метода быстрого вычисления линейной свертки дискретных сигналов |
| title_full_unstemmed |
Структура гиперкомплексного метода быстрого вычисления линейной свертки дискретных сигналов |
| title_sort |
структура гиперкомплексного метода быстрого вычисления линейной свертки дискретных сигналов |
| author |
Калиновский, Я.А. |
| author_facet |
Калиновский, Я.А. |
| topic |
Математичні методи обробки даних |
| topic_facet |
Математичні методи обробки даних |
| publishDate |
2013 |
| language |
Russian |
| container_title |
Реєстрація, зберігання і обробка даних |
| publisher |
Інститут проблем реєстрації інформації НАН України |
| format |
Article |
| title_alt |
The Structure of a Hyper Fast Calculation Method Linear Convolution of Discrete Signals |
| description |
Исследован метод быстрого вычисления линейной свертки числовых массивов длиной 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.
|
| issn |
1560-9189 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/87053 |
| citation_txt |
Структура гиперкомплексного метода быстрого вычисления линейной свертки дискретных сигналов / Я.А. Калиновский // Реєстрація, зберігання і обробка даних. — 2013. — Т. 15, № 1. — С. 31-44. — Бібліогр.: 10 назв. — рос. |
| work_keys_str_mv |
AT kalinovskiiâa strukturagiperkompleksnogometodabystrogovyčisleniâlineinoisvertkidiskretnyhsignalov AT kalinovskiiâa thestructureofahyperfastcalculationmethodlinearconvolutionofdiscretesignals |
| first_indexed |
2025-11-27T00:27:59Z |
| last_indexed |
2025-11-27T00:27:59Z |
| _version_ |
1850788570444333056 |
| 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
|