Устройство для дискретного преобразования фурье

Устройство для дискретного преобразования фурье

Иллюстрации

Показать все

Реферат

 

Изобретение относится к автоматике и вычислительной технике, в частности к устройствам дискретного преобразования Фурье, и может найти применение для построения параллельных спектральных анализаторов. Цель изобретения - упрощение устройства. Поставленная цель достигается за счет того, что устройство для дискретного преобразования Фурье содержит группы косинусных и синусныхблоков понижения порядка первого и второго типов 73 1 so 7 72 7 зз с 1с 2 -1с 2 и 1 2 и 2 и группы 3 блоков су {мирования-вычитания с соответствующими связями между блоками устрой- S ства. 3 ил. (Л ГС 00 Ч 4ib

союз советсних социАлистичесних

РЕСПУБЛИН . (я) 4 G 06 F 15/332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ е:

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР пО делАм изОБРетений и ОтнРытий (21) 3836668/24-24 (22) 07.01.85 (46) 30.01.87. Бюл. В 4 (71) Куйбышевский институт инженеров железнодорожного транспорта (72) Ю.И.Шафоростов, В.И.Шафоростов и С.П.Орлов (53) 681.32(088.8) (56) Авторское свидетельство СССР

Ф 1084807, кл. G 06 F 15/332, 1984.

Капорин И.Е. Новый алгоритм быстрого преобразования Фурье./

/Вычислительная математика и математическая физика, т. 20, 1980, Ф 4, M. Наука,. с. 1024-1058. (54) УСТРОЙСТВО ДЛЯ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

„„80„„12871?4 А 1 (57) Изобретение относится к автоматике и вычислительной технике, в частности к устройствам дискретного преобразования Фурье, и может найти применение для построения параллельных спектральных анализаторов. Цель изобретения — упрощение устройства. По" ставленная цель достигается за счет того, что устройство для дискретного преобразования Фурье содержит группы косинусных и синусных блоков понижения порядка первого и второго типов

1 =2 1с=2 и 1 2з 1 =2 . 2 =22 2

h — г

=2 и 2 =2 -2 =2 и группы 3 блоков

3 суммирования-вычитания с соответствующими связями между блоками устрой- Ж ства. 3 ил.

12871

Изобретение относится к автоматике и вычислительной технике, в частности к устройствам дискретного преобразования Фурье сигналов (формирования сигналов) и может найти широкое 5 применение для построения параллельных спектральных анализаторов, Цель изобретения — упрощение устройства.

На фиг. 1 изображена блок-схема устройства; на фиг. 2 — блок-схема косинусного (синусного) блока повышения порядка первого типа; на фиг. 3— блок-схема косинусного (синусного) блока понижения порядка второго типа.

Устройство содержит группы косинусных и синусных блоков понижения

Р порядка первого типа 1 -2 -1 -2

Р с и 1 -2 -1 -2 группы косинусных блоS

У ков понижения порядка второго типа

2 -22 -2 -2 и 2 -22 -2 -2 и группы 3

Р P с с S S блоков суммирования-вычитания.

Косинусный (синусный) блок понижения порядка первого типа (фиг. 2) содержит узел суммирования вычитания, состоящий из сумматоров 4 — 6 и узла 7 умножения на коэффициент. Косинусный (синусный) блок понижения порядка второго типа (фиг. 3) содержит узел 8 суммирования-вычитания.

Работа устройства основывается на следующем алгоритме.

Выражение а (2 (2k+1)) для дискретного .синус- преобразования Фурье

2 сигналов обладает следующим свой- 35 с Гвом.

Я -1 а (2 (21<+1))= A (1 k ()"

e=0

I it(2k+1)

< я п (1) 40

"С- где J =О, i n; k=0,1,2,; ..; (=0,1,2,...;

А (1PkP() =x(1); 1=0, 1,... «2 -1; 45

А (О,k,ф) =А, (2,k,() sinlI (2k+

„,") (24- g-1

А (1,k, () =А,1„(1,k, @+Ay, (2

-1,k, )+2A„,. х(2" + 5t(2k+1) 50

+I,k ф)соя- — — —; (2) э э

2-S-1

1=0,1,...,2 -1 °

Соотношение (1) легко доказывается индукцией по Р при любых значениях

k u . 55

Любое целое действительное число из множества, ограниченного интерваи лом (-2, 2" ), может быть получено иэ выражения

Нулевой цикл, Сигналы Р

Ф; >, э ь ..., У с учетом (5) можно предстат вить в виде

0+ (+О}

Ф

OcI o

Ч> =ф2 (2k+! ), Ф вЂ” знак и+в или 1-11.

Любое целое действительное число иэ множества, ограниченного интерваЬ rý лом (-2, 2 ), может быть представлено в виде алгебраической суммы возрастающих с гепеней двойки.

Следовательно, при определенных значениях k и может иметь место равенство

Ф2 (2k+1 ) о2 ф 2 Р 2 ...Ф; 2 ф;,2ф;2 ..., (3) где О - с (tt c r... p A z... а и.

Для выражения (1), характеризующего дискретное преобразование Фурье от действительной последовательности сигналов х(1) (1=0,1,. .,2 -1), при любом k и справедливы равенства а (2 (2k+1) ) =а (-2 (2k+1) ); а (2 (2k+1) ) =-а (-2 (2k+1) ) . (4)

Определяют способ формирования дискретного преобразования Фурье сигналов х(1). На основании (3) вводят последовательность сигналбв аргументов Р „=.ОФ,2; О с ап;

= Р, у 2; рог(п;

gj. а z

p V i

o< < -P z с (-2,2 ) ..

c(5I Ф

Сигналы (функции) а (Р „ ), с учетом указанных свойств и заготовок, использующихся при формировании данных сигналов (функций) от сигналов (аргументов) р с меньшими значениями своих индексов, могут быть сформированы циклически.

1287174 . а (0)=2 А, ();

2 -1 c(S) а (V )=,) A

0 ЕаО

5 с(5) ф; c< 9) а (М,) )=2 А (о) о а, =О

s, o) Ф, 1((; — О) (I)Ä,Ä) ее -1 хам) (v, -o) ое-1

9 (7) †...-А (Х Р -О)(о) о где и =и. о (6) t0 Используя указанные свойства и (2), с(5) (6), закон формирования сигналов а (), игналов А не зависят

o(î) мента. Исходя из это- начиная с аргумента М -, можно предod ать ставить в виде

-4 с(5) 9 2 с(5) gà со5 111(М ) 0) ,"" (ч ) = А (ХЧ -О)

О,с/. =- 1) od (5<г ) 0 0 о

5 -ъ)а а

<,) Ф„ а<5) ф Соз У)< (« -О) а (V. )= А (Х,V "— О)

dP 9 (Sir ) (аО а и 2 с(б) g) с(9) 4 соs I (а(ф ) (g)

a (< „) = рА) (,V, -0,.„) (

<<). Ф

))z о(Разности (Р 1-0),.... с учетом (Я следующим образом:

c(.P

-о)=(-О)+((е"-o)-(-о))=(е -0)+(v - е ) °

Ф ф ф ) .). И, ф о,(о(Е oc(oo((Р ж

-0) =(V о-0)+ (Lp -(Р а) . (9) где )) =О, 1,...

Представляют (Р 1 (%van „

)) Z

Первый цикл. На ря во внимания (9) е мирования сигналов

40 c(s) ф„с(5) а (Ч "),...,а ставить в виде первом цикле, бе(11), закон форс(5) Ч, а { Р ), Оа< (>z ) можно предгде k, =0,1,...; 1,=0,1 ° ° °; (,=д.;

2" е)

c(S)

e =()

",1

)= А„„ (аО

2 -1

)= А с(5) (<(>Фа

od с(5) Ф„ а ((<" c(5) Ф„. а (Р " о а

5<5) . IT(2 (- Е ) — A (1) sin- — — — — — -э

<+) Со)1

2 ее -1

9(5) . I112 (PaZ - +od )

4, ф, ()), (I) sin — — — — — — — —, (12) (о)1

<,-1

<1 1 Фа

I)<2 (" - о ) (I) cos

- )о 4 1 1 < а

1112 (

Ф1 — 1

2 где n =n — ))

1 о o а (2k +1) ) соз — — — ——

I>t (2k +1) о — 5

c(S) c(e)

А (Х) =A„(I, 6,2 о (2k +1)) sin — — — - — -

I "ПФ (2k, +1) c,-,-1 (13) с<5)

Сигналы А ) формируются по формулам(2) . пРи =no 4 (о А, О+ (y > +O);

1(З (-)9

„df -0+(y,@+О)

Кроме того, учитывая (2) для можно записать

c(5) C (5) @а ()о (I,Î) =A()о(I,Ч -О) =

=А (Х Ч1 -О)(о)О dP

А(о)о () т.е. значения с от второго аргу го, можно запис

Кроме того, выбирают такое ), c(5) чтобы сигналы А при возрастании о второго аргумента не меняли своего значения, т.е. чтобы бьши справедливы равенства с(8) ())

=...=А, (I,V„ -О)=... =

=А„ (Zop)ооз (2„, +1)),(10) 30

2)) (при gt =0,1, ° ° ° о

Используя (2) с учетом (6), получают, что ). должно удовлетворять условию о<). р

5 1287174 6 (о 1

Используя указанные свойства и (2) та )" ь, могут быть записаны следуюдля сигналов (12), начиная с аргумен- щие формулы: ,-)), )/ у gj

c(5) Р)„2 -(с(ь) -))о Ф« Ф, IJ(2 ((« - ) а (У )=;Г (А (Х 2 (() - Р ))cos--- — - — -2-1 - g

1/. р, 1 с()г о,/. и 1

LcO 2 (- . 41 ф.. I((2 (-ч ) .-A (f. 2 (г "- р ))sin — — — — — -). ф; ф с(5! (!); у — (с) ))о Ф! ф Х)(2 (Р,) 2 — Vo ") (ñ ) = 5 (А (I 2 (1 (о î))cos е. 2))) 2 ))1 )/2 оД, n,— < ()

5(5) - "о @1 Ф Х1(2 ((,/2 - («о ) (I 2 ((р "-Ч) о))sin — -- — — - - — —; (14)

Ос)

1 2

-( где "1=0, 1,...;

С (С) -) р ф« ф с(51 -, (//) ф c(c) ч ),..., y - 1=(р .) (/) ()), ((), Ф; ф, / aag )/Z о( ()1 -(« ),... через разность (V <- М, )

0d ц))), о Кроме того выберем такое )) (16)

1. Э с учетом (5) следующим образом: чтобы сигналы А и A„- при возс(с) 5(Я (t „ - „")=(V 1- )+((V ;)-, растании второго аргумента не меняли

25 своего значения, т.е. чтобы были (v — v ) =(т — )+(т - v ); справедливы равенства: д. )) /),/, c/.P о<у. /". )" с/. P ог а (Y )=Е. А (I); (=() (" () -)) )

///. 2 "г-«c(c) ХЪ2 а (5) ((() =, ) (A (Х) сов (о)2 "г. г

Х>2 (),2 - „ ), (19)

Ог — 1

2 тде п =и -v

1 1

c(c.) c(c) « 2 )(41(2k +1)

А (1) =А (I, )/ 2 (2k +1) ) cos — — — -) —— (0)2 )) У 1 n„- ф

Itl Ф (2k+1)

xs in — - / — - — —;

2 1

-1 -1

А(„) (1) =A ) (I, (Р,? (2k .+1) ) cos

5(5) 5(о) ф Л Ф1(21с, +1)

ХМ1(2k +1) (20)

2" 4 с (с) S(S) сигналы А,/, А,/ формируются

I по формулам (4), (2) при n n, ф = ч«1

kk,; ))=)/,, Hтд °

i-ый цикл. Ha i-ом цикле для сигнаФ; (- )

5(S) — А (I) sin x (о) 2 (-,, А (Х,(?)12 " (2k, +1)х 1 с(с) ,+, A g (I, Ф,, 2 1 (2kÄ +1) ) x

I с (5) лов à"" (Y>< ), a ((t< )..., учитывая предыдущие выводы, можно запи-! / сать следующий закон формирования:

А„(1,2 (-т@ ))=...=А„(Х,2 („"-М ))=...=А (Х,Ф„2 " (2k„+1));

A " (Х 2 (((«г/ о)) A (I 2 (((/,/ 1! а) =А (Х ф2 (2k «-1) (17)

1 )/Е Оа

1 где k 0,1,...; g =0,1,...; (,= ç-)),; Оа )/, < r-,. (18) .,«-p-«, „ „ Второй цикл. На втором цикле для с =/)) 2 при/ =0,1,... с(5)

Используя (2) с учетом (15), полу* 35 данных сигналов а ((«" ) (1 ° ° ° 1 чают что )), должно удовлетворять а („),..., беря во внимание (16)— условию (18), закон формирования имеет вид:.1287,! 74

Г() ! сО (О)!

t=o

)!

s(s) 262 (+ А sin (I);

-()о ),+ - )- ) 11

) 1Я 2 ())у»((р))) (I)cos (+ ...1,, ) („Ф,, 3,.)

Ч вЂ” р,) (21) !

1; -!

2 с(с) 5(6)

Сигналы А, А формируются по

))j-! формуле (2), при n=n,. ф =

Значения (., = )).-()), +)), +...+ )). )

z-))-! и 1с . =) 2 при 3 =0,1..., определяются íà (i-1)-ом цикле, исходя

)).-У) -I c(c) (,) !.)) !c +)).

cos

n --) п 2 (ч )) (23) х(р — Pep ) з п

) z

У из выводов по всем предыдущим циклам, аналогично 1 и 2 циклам.

Используя указанные свойства и учитывая все предыдущие выводы для формируемых сигналов, начиная с аргумента можно записать. где ", =0,1,... с(с)

Оп)

5(s) (о)!

8о+ ))! (I,2 (Î+ . ° + 1-! ) (I,2

4. Ф . c(c) (V -v ))=А . <(Х):

Р !) <о)! ф, ()) s(s) (V„, -,„,) ))=A„„(l). (24) (16) и кроме того, выбирается такое

I чтобы сигналы А „" и А )

1 !

Далее, если есть аргументы, больФ! -45 шие, чем Y (например, учитывая (2), )z

Ф, имеем: Y ь =Ч,) ф. 2, где zchcn ux разности с )(! „ выражаются через разФ;, ность () - ()),„ ") аналогично (9), при возростании второго аргумента не меняли своего значения, т.е. чтобы выполнились равенства:

)=...=А (I,Ф, 2 (2k,.+1)); !

)=...=A„ " (I,фг (2k,.+1), (о + (I,2

-(!),+)) )-... +)), ) (1,2 (Ч,) — )() !) ) о(с)

А )). (25) $И)! где k;=О, ф; -z-(),+ при М =0,1,... Используя (2), с учетом (24) получают:

1,...;, =0,1,. ° .;

),+...+ )1, ); 1с; =М 2 -, где n, =n,. формируются на (i-1)-ом цикле, исходя

Значения и =и. 1 и ). опреде fO из выводов по всем предьдущим циклам, I аналогично 1 и 2 циклам. о

c(c) с(c) . РБф (2k +1) ()=А„(I,()f 2 (2k. +1))соз — „- — - - — (+ з; — (о) о ф; 1 7 Ф. (2k „+1) () д, )", ф. 2 -! (2k +1) ) sin- — с — - — -

i-! !

1-1 tl1-!

У

2 -FA =А (У Р- 2" (2k +1) (cos Ж -..)(2 +1)

l-! )11 — ф -1 )1-1 (I,А,2 (2k +1))s @ (— ) (22)

\ 1 ф)-!

12871

74 где n- =n — g.;

3+(1 (+2 (2k;+1))cos — — — ->.— — — А (1 д

c () () ф, - f fcp (2 ) .1 ) s(s) х2 (21(+1) ) я @ (2(.1+1)

).-1.-() -(i с

5(5) (О) I t!

SCs) ()- ° Ф, 2 " (21(, +1))соя-- — "« +1)

2 (-)

f х (Х, Ф г"" (2k. +1) s in ) 4(2k +1)

n, -,- -1 ° (28) А ) формируются

sC5)! при n=-n.; ф =ф;

c(c)

Сигналы А ) ! по формулам (2)

k=k,; y= .. изобретения

Формула

О < Л. с h-()),+))Ä+...+ ));, ), (26) т.е. )) должно лежать в пределах ! от нуля до значения (i+1)-го показателя степени двойки без, суммы всех предыдущих (i+1) ûé цикл. На (i+1) îì цикле с(Ь)(((! для данных сигналов а ()!, ), принимая во внимание сказанное, по- 1< лучают закон формирования сигналов:

Устройство для дискретного преобразования Фурье, содержащее первую группу из двух блоков суммированиявычитания, о т л и ч а ю щ е е с я 35 тем, что, с целью упрощения устройства, оно содержит и групп косинусныз и синусных блоков понижения порядка первого типа (n=-1о! И, N— размер преобразования по (2 †(-1) ) 10 (р=1,n) блоков в р-й группе, п групп косинусных и синусных блоков понижеР пия порядка второго типа по (2 +2»

«(-1) блоков в р-й группе и (и 1) групп блоков суммирования-вычитания по ((2 -(-1)"7з " блоков в каждой группе, причем первая группа выхода р-го косинусного блока понижения по- . рядка первого типа р-й группы подключена к группе входов (р+1)-ro ко- 50 синусного блока понижения порядка второго типа (р+1)-1 группы, вторая и третья группы выходов р-го косинусного блока понижения порядка первого типа р-й группы подключена к груп" 55 пам входов соответственно (р+1 )-го синусного блока понижения порядка второго типа и (p+1)-го косинусного

I0

2"(-! (!! )=Е р>„,(!) .(2!) (,:î и далее следующие значения сигнас(5) лов а от следующих аргументов с использованием сигналов А (() я(я) (0) (+ аналогично (12), (19), (21) 1, 2.

i-го циклов, блока понижения порядка первого типа (р+1)-й группы, причем первая, вторая и третья группы выходов синусного блока понижения порядка первого типа р.-й группы подключены к группам входов соответственно (р+1)-го синусного блока понижения порядка второго типа, (р+1)-го косинусного блока понижения порядка второго типа и (р+1)-ro синусного блока понижения .порядка первого типа (р+1)-й группы, группы выходов i-х (i-=1,р) косинусного и синусного блоков понижения порядка второго типа р-й группы подключены к группам входов соответственно i-х косинусного и синусного блоков понижения порядка первого типа (р+1)-й группы, группы выходов

i õ косинусного и синусного блоков понижения порядка первого типа р-й группы подключены к группам входов соответственно первого и второго блоков суммирования-вычитания р-й групЬ)ы, группы ))ыходов суммы и разности первого блока сложения-вычитания подключены к группе входов соответствен- . но первых косинусного и синусного блоков понижения порядка второго типа (р+1)-Й группы, группы выходов суммы и разности второго блока суммирования-вычитания р-й группы подключены к группам входов соответственно вторых косинусного и синусного блоСоставитель А.H.Áàðàíoâ

Редактор С.Лисина Техред А.Кравчук

Корректор М. Пожо

Заказ 7719/53 Тираж 694

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Подписное

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

ll 1287 ков понижения порядка второго типа (р+1)-й группы, причем косинусный и синусный блоки понижения порядка первого типа содержат узел суммированиявычитания и узел умножения на .коэф5 фициент, вход которого подключен к выходу узла суммирования-вычитания, группа входов которого является группой входов блоков понижения порядка, а первая, вторая и третья груп- fp

174 12 пы выходов узла умножения на коэффициент являются соответственно первой, второй и третьей группами выходов блока понижения порядка, причем косинусный и синусный блоки понижения порядка второго типа содержат узел суммирования-вычитания, входы и выХОДЫ КОТОРОГО ЯВЛЯЮТСЯ СООТветс твенно входами и выходами блока.