Устройство для дискретного преобразования фурье
Изобретение относится к автоматике и вычислительной технике, в частности к устройствам дискретного преобразования Фурье, и может найти применение для построения параллельных спектральных анализаторов. Цель изобретения - упрощение устройства. Поставленная цель достигается за счет того, что устройство для дискретного преобразования Фурье содержит группы косинусных и синусныхблоков понижения порядка первого и второго типов 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 пы выходов узла умножения на коэффициент являются соответственно первой, второй и третьей группами выходов блока понижения порядка, причем косинусный и синусный блоки понижения порядка второго типа содержат узел суммирования-вычитания, входы и выХОДЫ КОТОРОГО ЯВЛЯЮТСЯ СООТветс твенно входами и выходами блока.
