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

 

Изобретение относится к обл-асти автоматики и вычислительной техники, в частности к устройствам дискретного преобразования Фурье сигналов, и может найти применение при построении параллельных спектральных анализаторов . Цель изобретения - упрощение устройства. Поставленная цель достигается за счет того, что устройство содержит группу из п блоков суммирования второго рода, косинусный и синусньй каналы, каждый из которых состоит КЗ блока суммирования первого рода, блока суммирования второго рода , группы блоков умножения первого рода, группы блоков умножения второго рода и группы блоков суммирования второго рода. 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