Устройство для дискретного преобразования фурье сигналов
Изобретение относится к обл-асти автоматики и вычислительной техники, в частности к устройствам дискретного преобразования Фурье сигналов, и может найти применение при построении параллельных спектральных анализаторов . Цель изобретения - упрощение устройства. Поставленная цель достигается за счет того, что устройство содержит группу из п блоков суммирования второго рода, косинусный и синусньй каналы, каждый из которых состоит КЗ блока суммирования первого рода, блока суммирования второго рода , группы блоков умножения первого рода, группы блоков умножения второго рода и группы блоков суммирования второго рода. 8 ил. (Л 1ЧЭ 00 00
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК 511 4 G 06 F 15/332
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К ASTOPCHOMY СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTKPblTI41 (21) 3951812/24-24 (22) 01.08.85 (46) 07.02.87. Бюл. У 5 (71) Куйбышевский политехнический институт им. В,В.Куйбышева (72) В.И.Шафоростов (53) 681.32 (088.8) (56) Авторское свидетельство СССР
N 1084707, кл. G 06 F 15/332, 1984.
Шафоростов Ю.И. Новая схема алгоритма быстрого преобразования
Фурье: В сб. Автоматизированные моделирующие системы в технологических задачах. Куйбьппев, 1984, с.5561. (54) УСТРОЙСТВО ДЛЯ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ СИГНАЛОВ
„,Я0„, 1288717 А1 (57) Изобретение относится к области автоматики и вычислительной техники, в частности к устройствам дискретного преобразования Фурье сигналов, и может найти применение при построении параллельных спектральных анализаторов. Цель изобретения — упрощение устройства. Поставленная цель достигается sa счет того, что устройство содержит группу из и блоков суммирования второго рода, косинусный и синусный каналы, каждый из которых состоит из блока суммирования первого рода, блока суммирования второго рода, группи блоков умножения первого рода, группы блоков умножения второго рода и группы блоков суммирования второго рода. 8 ил.
12887 (8) F (R) = F (2"-R)
F (R) =-Р (2 -R) .
S s (2) 35 (4) (13) Учитывая то, что
Используя равенства где а(о)=Х(о); а(2 ) =Х(2
a(i) =X(i)+X(2
h-Ь
1 <1<2 -1; 1 =0,1
h - -g, ° ..,2 (6) 55,...,n-l, k=0, 1 ь .. °, Изобретение относится к автоматике и вычислительной технике, в част- .ности к устройствам дискретного преобразования Фурье сигналов, и может найти применение при построении параллельных спектральных анализаторов.
Цель изобретения — упрощение устройства и увеличение быстродействия.
Определим некоторые свойства, ко- 10 торые нужны для дальнейших рассуждений.
Любое число из интервала (0,2") может быть получено иэ выражения
R = 2 (2k+1); (1) Для косинусного и синусного дискретных преобразований Фурье действительной последовательности 2" сигналов имеют место следующие соотношения:
При любых значениях k и можно записать равенство
cos3.(2 (2 -k-1)+1)7/2 =-cost(- (2k+ +1)/2 (3) Косинусное дискретное преобразование Фурье действительной последоh вательности 2 сигналов X(i) (i
= 0,1,...,2"-1) с учетом равенства (1) имеет вид
F (2 (21с+1) )
Х(г.) cos Й i(2k+1) 2 /2
П-1
1=0
cos(2 -i.) Й(21с+1) /2
= созе i (2k+1) /2 равенство (4) можно представить в виде .г
h-1
F (2 я (2k+1) 1= a(i) cos Л . (2k+ 5р
+1) 2 /2 (5) 17 2
Далее, используя равенства
cos (2 «+i) l . (2k+1) 2 /2
- -г и-ь (7)
=+(-1) sin > i(2k+1) 2 /2
" 4-1
П-1
cos (2 -i). н1 (2k+1) 2 /2
=соsЯ i (2k+1) 2 " /2 равенство.(5). можно записать в виде гь -ф -г
F (2 (2k+1))= Ь (i) (-1) sin T<.i
1 (2k+1)/2 (9)
h — g-г где Ь +1(i)=a (2 -i)-а (2 +i); (1< 1 < 2; Вг (10) а ь „() =а (г.)+а (2 д) ьь
06 i< 2 "-1; а „(2 ) =а (2 );, (11) а (i)=a(i) .
Синусное дискретное преобразование Фурье действительной последовательности 2 сигналов Х(х) (i = 0
h ь
1...,2 -1) с учетом равенства (1) имеет вид
F Г2 (2k+1))= (12)
= Е X(i) sin) -i(2k+1) 2 /2
Учитывая то, что
h h- (-1
s in (2 -i) Л (2k+1) /2
-я п2 i (2k+1) /2
1йожно записать в виде
F (2 (2к+1)1.= г" -1
П-1
a(i) sin i i(2k+1) ° 2 /2
j =1 где a(i) =X(i)-X(2 -i), л- -г
$ =O» ° ° ° ьп- l, k=0 ь 1 ь ° ° ° 2 (14) sin(2 -з.!2 (2k+1) 2 /2
П- -1
3ч — 1
sin 3 . i (2k+1) 2 /2
h- 3-1 . 1+1 h-1
sin(2 -i) Й (2k+1) 2 /2 +1 и-1 — ядпЙ i(2k+1). 2 /2 равенство (13) можно записать в виде " 6-г
F (2 (2k+1) ) =1 (15) — (i) я з и Я .i (2k+1) /2 4 (+l
3 1288717 где Ь „(i)=.à (i)+a (2 -i), с
1 с i c 2" -1, (16) f0 (18) =а (i)-а (2" Ф з) 1 < i c 2 1»
Рассматривают преобразование
st. 2 (2k+1) )
2П1
h,+
А(з.) sin Э х(21(+1)/2
i= » где и =n-ô-2.
Вводят соотношения А. (i,k) =A(i)
1
A4 (i,k) =A>„(i,k)+A< „(2 -i,k)+
+2 А4 (2 +i,k) cos 1 (2k+1) /2;. 20
Л,-Р
А4 (2 k)=A4, (2,,k)+
h,4 1
4++1
+2 А4, (2»k) созЪ (2k+1)/2
1 6 i» 2, 1<4 (n, (19)
11,- 25
С учетом равенства (3) можно записать А, (i, f-k-1) =A(i);
A4(i,2 -k-1)=A 4, (i,k)+ 30,-4» п,-4
+А4„(2. -i,k) 2 А4» (2 +
4+ 1
+i,k) cos 4i (2k+1)/2
Л1 -4 4- К+1 п,-4
А 4(2» 2 ) =А 4, (2 »к) — 35
11, -4+1 4+1
-2 А4.„(2,k) cos3 (2k+1) /2 (2p) Тогда равенство (18) можно записать в виде
11 4 40 2 з l2 /2k+1)j= А4(i,k) ° sinX i(2k+
+1) /2 (21) Соотношение (21) доказывается индукцией по 4 при использовании формулы синуса суммы двух аргументов..
При =п формула (21) принимает вид
s(2 (2k+1)7=A„(1,k) sinÚ (2k+
+1
+1) /2 (22) Преобразования (18), а следовательно, и (22) можно использовать для реализации равенств (9) и (15). Сле- 55 довательно, равенства (8)-(11) и (1 4)(22) являются теоретическими предпосылками для устройства, реализующего дискретное преобразование Фурье дейтвительной последовательности сигалов.
На фиг. 1 и 2 изображены структурные п-ярусные схемы косинусного и синусного каналов устройства для дис" кретного преобразования Фурье сигналов, на фиг. 3 и 4 — внутренние структуры блоков суммирования первого рода; на фиг. 5 и 6 — внутренние структуры блоков суммирования второго рода косинусного и синусного каналов устройства; на фиг. 7 и 8 — структуры блоков умножения первого и второго родов.
Рассмотрим схему устройства, реализующего дискретное преобразование
Фурье действительной последовательности 2 сигналов. и
Устройство имеет 2 " входов, на которые поступает действительная последовательность сигналов x(i) (i=0 1 ...,2 -1), и две группы по 2" выходов, на которых формируются сигналы, соответствующие косинусному и синусному дискретным преобразованиям Фурье..
Устройство (фиг. 1 и 2) содержит блок
1 суммирования второго рода, блок 2 умножения второго рода, блок 3 суммирования первого рода, блок 4 умножения первого рода.
Блок 3 д -2 суммирования первого рода косинусный (фиг. 3) и синусный (фиг. 4) состоит из (2"-1) (двухвходовых алгебраических) сумматоров 5 и сумматоров 6. Блок предназначен для формирования сигналов из входной последовательности 2 сигналов по формулам для блока косинусного канала
a(m)=х(m)+х(2"-m)
m=1 2,...,2 -i; а(о)=х(о); а(2" )=х(2" ); для блока синусного канала и-1
a (m) =x (m) -x (2" -m); m= 1» 2» ° ° » 2 1 э и определяет значение сигналов a(i) в формулах (8) и (14) °
Блок 1,-2 (фиг. 5) суммирования второго рода (косинусный) состоит из
1 двух групп по 2 " (двухвходовых алгебраических) сумматоров 7 и 8 ° Блок предназначен для формирования двух групп сигналов из входной последа>-Р+1 вательности 2 сигналов по формулам
Ь (m)=а (2 -m)-а (2 +m); а (m-1) =а (m-1) +a (2 -m+1) 5
a" .(2 )=а (2" ); ш=1,2,...,2
1288717 6
F (k) =(-1) А (1,k) sinЛ > (2k+1) /й" 4, А (ш,1с)=А (ш,k)+A (2 -ш,k)+
+2А (2 +ш,k). cos > (2k+1)/2
А (2,k) А (2,k)+
+2А (2,k) cos Р (2k+1) /2
А (ш,2 -k-1) А (m,k) + р+ P- - е
+А (2 +mók) -2A (2 +m k)ê. ксоз 2 (2k+1) /2
-2 А (2,k) cos3 (2k+1)/2 и определяет значение сигналов
A (i,k) и А „(д,2 ) в формулах (19) и (20) .
Блок 4 умножения первого рода (фиг. 8) состоит иэ умножителя 15 с весом (-1)" sin)((2k+1)/2" < для ,косинусного канала устройства и с весом з1пз (2k+1)/2 для синусного канала устройства, предназначен для формирования сигналов по формулам: для косинусного канала и .определяет значение сигналов Ъ +,(Ц и а „(i) в формулах (10) и (11). лок 1, — 2 (фиг. 6) суммироваP 5 ния второго рода (синусный) состоит из двух групп по (2" -1) (двухвходовых алгебраических) сумматоров 9 и 10. Блок предназначен для форми- 10 рования двух групп сигналов из входной .последовательности (2 " -1) сигналов по формулам
b (m) =а (ш)+а (2 -m);
ll5
b (2 ) а(2 ); а" (m)=a (m)-а (2 -m); ш=1,2,...,2 -1, и определяет значение сигналов b<„(i), 20 а, (з.) в формулах (16) и (17) .
Блок 2-2 умножения второго рода (фиг. 7) состоит из группы (2 -1) и двух групп по 2 (двухвходовых алгебраических) сумматоров 11-13 и группы 2 умножителей 14 с весом
2 cos И(2k+1)/2 . Блок 2-2 умножения второго рода предназначен для формирования двух групп сигналов из входной последовательности 30
2 " сигналов по формулам для синусного канала устройства
F (k)=A (1,k) sin l1 (2k+1)/2 и определяет значения сигналов
F L2 (k+1)) и F l2 (2k+1)) и, следовательно, s в формулах (9), (15) и (22 ) .
Иэ анализа схем (фиг. 1 и 2) видно, что число выходов устройства, а .5 следовательно, и сигналов F (R),F (R) определяется числом блоков 4 умножения первого. рода плюс три (нулевой, (2" )-й, (2 )-й сигналы, формируемые блоками 1 -2 суммирования
Р второго рода) и равно
n-x
-1) 2+3=2 +1;
-1) 2+1 =2 -1.
К =(2
R =(2
Остальные сигналы формируются беэ увеличения сложности схемы с учетом равенств (2).
Формула изобретения
Устройство для дискретного преобразования Фурье сигналов, содержащее группу иэ и блоков суммирования второго рода (n=log М, И вЂ” размер преобразования), вторая группа выходов р-ro (р=1,n) блока суммирования второго рода подключена соответственно к группе входов (р+1)-ro блока суммирования второго рода, а первый и второй выходы группы выходов и- го блока суммирования второго рода являются соответственно (2 )-м и нулевым инфопмационными выходами устройства, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, оно содержит косинусный и синусный каналы, каждый из которых содержит блок суммирования первого рода, блок суммирования второго рода, группу блоков умножения первого рода, группу блоков умножения второго рода и группу блоков суммирования второго рода, причем входы блока суммирования первого рода являются группой информационных входов устройства, а выходы блока суммирования первого рода подключены соответственно к входам блока суммирования второго рода, входы i-ro (i= .=З,n) блока умножения второго рода
128871 подключены к соответствующим выходам первой группы выходов (i-1)-ro блока суммирования второго рода, первая .и вторая группы выходов i-го блока умножения второго рода подключены к входам двух (i+1)-х блоков умножения второго рода, а выход и-го блока умножения второго рода подключен к входу блока умножения первого рода, выходы блоков умно- 10 жения первого рода являются. группой информационных выходов устройства, причем блок суммирования первого рода содержит (2 -1) сумматоров, первый и .второй входы и-го (и = 15
1,2" -1) сумматора являются соР1 ответственно ш-м и (2 -ш)-м входами блока суммирования первого рода, а, выход ш-ro сумматора является m-м выходом блока суммирования первого 20 рода, при этом j-й (j 2,n) блок суммирования второго рода косинусного канала содержит две группы сумматоров, первые входй m-x (ш=1,2"" ) сумматоров первой и второй групп, объединены и являются (2 -m)-м входом блока суммирования второго е рода, вторые входы сумматоров пер вой и второй групп объединены и являются (2" +m)-м входом блока суммирования второго рода,а выходы ш-х сумматоров первой и второй групп являются соответственно m-м выходом первой и (2 -m)-м выходом второй групп выходов блока суммирования второго рода, 35 причем j и блок суммирования второго рода синусного канала содержит две .группы сумматоров, первые входы k-х (k=
=1,2 " -1) сумматоров первой и вто40
7 8 рой групп объединены и являются k-м входом блока суммирования второго рода синусного канала, вторые входы
k-x сумматоров первой и второй групп объединены и являются (2 -К)-м входом блока суммирования второго рода синусного канала, а выходы k-x сумматоров первой и второй групп являются k-ми выходами соответственно первой и второй групп выходов блока суммирования второго рода синусного канала, при этом.i-й блок умнЬжения второго рода содержит три группы сумматоров и группу умножитепей первый и второй входы 1-го (1=1,2" -1) сумматора первой грудпы являются соответственно 1-м и (2" -1)-м входами блока умножения второго рода, вход в-ro (s= — 1,2" ) умножителя группы является (2" +s)-м входом блока умножения второго рода, выход s-го умножителя подключен к первым входам
s-х сумматоров второй и третьей групп вторые входы ш-х сумматоров второй
h $ и третьей групп являются (2 )-м входом блока умножения второго рада и подключены к выходу k-ro сумматора первой группы,1 а выходы ш-х (швв
=1,2" " ) сумматоров второй и третьей групп, являются m-ми выходами соответственно первой и второй групп выходов блока умножения второго рода, блок умножения первого рода косинусного канала выполнен в виде умножителя на (-1)" sintt(2k+1)/2 < (k=
=0,2 ), а блок умножения первого рода синусного канала выполнен в виде умножителя на sin Ó(2k+1) /2" .
1288717 я) я
uz(° °
2) 1288717 (-l g(g ) f(2"-+ ) ф"-Я) Х(0) 1 ы
Фиг.4
Фиг.f! 288717
1288717
1288717
4Ъ2 6
Составитель А.Баранов
Редактор Н.Бобкова Техред Л.Олейник Корректор Т.Колб
Заказ 7810/48 Тираж 673 Подписное
ВНИИПИ Государственного комитета СССР по делам изобретений и открытий
113035, Москва, Ж-35, Раушская наб., д. 4/5
Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4
