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

 

Изобретение относится к вычислительной технике и может быть использовано при вычислении спектра сигналов и их фильтрации в частотной области. Цель изобретения - повышение быстродействия устройства. Последнее содержит шесть регистров, четыре умножителя, два сумматора, два вычитателя, два сумматора-вычитателя два коммутатора, два дешифратора . 1 ил. Ivd 4 tC се 00 Од

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

ВО (л

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

Н A ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ВМИ МО й., ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3814 112/24-24 (22) !9.11.84 (46) 07.07.86. Бюл. )! 25 (72) А.А.Мельник, Е.Я.Ваврук, Ю.)!.Захарко и И.Г.Цмоць (53) 681.32(088.8) (56) Рабинер Л., Гоулд Б: Теория и применение цифровой обработки сигналов. — М.: Мир. 1)78.

Авторское свидетельство СССР

9 421994, кл. С 06 F 15/332, 1971. г

„„SU„, )) 242986 А 1 (51)4 G 06 Р 15/332 (54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИ4

БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к вычислительной технике и может быть использовано при вычислении спектра сигналов и их фильтрации в частотной области. Цель изобретения — повышение быстродействия устройства.

Последнее содержит шесть регистров, четыре умножителя, два сумматора, два вычитателя, два сумматора-вычитателя два коммутатора, два дешифратора. 1 ил. 1242986 где A

В (l

1,1 Р

Т, = i=„,„„+ 2со + ted@ где Цмн tcM

I еЛ; < = ReA„+ ReВ„, (2) ImA, = ImA „+ ТшВ;;

ReB„ = ReA „— ReB>, Выражения в устройстве

ReA

ImA < qt = I mA „ - Re B <, ReBct1 ReAI, — ImB (3) ImB„t< = ХтА; + КеВ .

Изобретение относится к автомати" ке и вычислительной технике и может быть использовано при вычислении спектра сигналов и их фильтрации в частотной области в системах связи, навигации, сейсморазвелки н других областях техники.

Цель изобретения — повышение быстродействия устройства.

На чертеже представлена функциональная схема устройства для выполнения быстрого преобразования Фурье (ВПФ) ..

Устройство содержит регистры 1 — 6 (операндов и весового коэффициента), умножители 7-10, сумматоры 11 и 12, вы гитатели 13 и 14, дешифраторы 15 и 16, коммутаторы 17 и 18) сумиаторывычитатели 19 и 20.

Ллгоритм работы устройства описы. вается следующим образом:

RcA„,t =ReA„+(КеВ„- ReWÄ +ImBÄ ImW;)>

Р,Р, Iiv>kÄ« =ImA„+ (ImB„° Ке11 -Йе13 ХвЛ )

P Р

Ке13;, =ReA„— (ReB„ КеЫ„+ХшВ ImW„))

:1mB,. =ТпЛ„- (Im13„- ReW. -PeB. ° ImWÄ ), р первый комплексный операнд, второй комплексный операнд; комплексный весовой коэф- фициент; показатель степени.

Вь!ражение (1) представляет собой базовую операцию алгоритма БПФ при

Р=-0 и Р Ф

Ж

При Р = О выражение принимает вид

ImI3 t» = ImA — ImB а при Р = gt./2 имеет вид

В устройстве реализуются выражеHIifl (1 ) (3) В зависимости от зна чения P .

Устройство работает следующим ооразом.

На i-й итерации алгоритма БПФ в регистры 1-6 пос.тупают соответственP

5 Н0 значения ReA1 КеВ-„, йпВ„", КеИ„, Р

ImW, ImA „. Если показатель P весового коэффициента И- равен нулю, то

ReW = 1, ImW„ == О и в регистр 4 дейP Р ствительной части весового коэффициента запишутся все единицы.. При этом на выходе дешифратора 15 сфор-.. мируется логическая единица. Если

Т р P

Р = — — то ReW = 0 ImW. = 1 и в

2 4, регистр 5 мнимой части весового коэффициента .запишутся все единицы, при этс м на выходе дешифратора 16 сформируется логическая единица. Значения пз дешнфраторов 15 и lб поступают

20 на управляющие входы коммутаторов 17 и 18 и в зависимости от управляющего входа на >зыход коммутаторов проходят значения ОО-(Re13„ ; КеИ + ImB„ ImW )

P Р

Ь и (ТтВ„Ке — КеВ ImW„); 01

25 КеБ„ и Im13„ 10 — ReI3„" и ImB„.. При коде О на управляющем входе сумматоров >зычитателей выполняется операция сложения, при коде 1 — вычитания.

Таким образом, при коде 00 на выходе

1О дешифрато ров в устройстве Db>IIQJ(IIH ется выражение (1), при коде 01 — выражение (2), при коде 10 — выражение(3). На выход устройства из сумматора 12, вычитателя 14 и сумматороввычитателей 19 и 20 поступают соответственно значения КеЛ„-+4, КеВ -t4

ImI3;,, ImA «, Выражение (1 ) выполняется в устройстве за время — вреия выполнения операций умножения и сложения; — задержка информации в коммутаторе. .С» и (3) выполняются за время

+ ко+ " м где Е !>. — время срабатывания дешифратора.

При выполнении алгоритма БПФ число операций вида (.2) равно N-l, где

- 5 N — число отсчетов, число операций вида (3) равно И/2-1, число операций вида (1) равно N/2-1ogqN — 3/2 N+?.

Тогда время выполнения N-точечного!

242986

ЕПФ с испольэованием предлагаемого устройства равно

Т = (-N-2) Т + (-1ogP- — N+2)T

3, N 3

2 2 „2 2 "5

Время выполнения N-точечного БПФ с использованием иэвестного устройства равно

N N, !О т = - logqN(tire„+2tr ) — log NT, 1 2

Формула иэ обретения

Устройство для выполнения быстро-, го преобразования Фурье, содержащее первый регистр, выход которого подключен к первым входам первого сумматора и первого вычитателя, выходы ко- 2п торых являются выходами реальных частей соответственно первого и второго операндов устройства, второй регистр, выход которого подключен к первым входам первого и второго умножителей,25 выходы которых подключены к первым входам соответственно первого сумматора и первого вычитателя, вторые входы которых подключены к выходам соответственно третьего и четвертого умножителей, первые входы которых подключены к выходу третьего регистра, информационный вход которого является входом мнимой части второго операнда устройства, входами реальных

35 частей первого и второго операндов которого являются информационные входы соответственно первого и второго регистров, вторые входы первого и четвертого умножителей подключены к входу четвертого регистра, информационный вход которого является входом реальной части коэффициента устройства, входом мнимой части коэффиl циепта которого является информационФ ный вход пятого регистра, выход которого подключен к вторым входам второго и третьего умножителей, информационный вход шестого регистра является входом мнимой части первого операнда устройства, о т л и ч а ющ е е с я тем, что, с целью повышения быстродействия1 в него введены первый и второй дешифраторы, первый и второй коммутаторы, первый и второй сумматоры-вычитатели, выходы которых являются выходами мнимых частей соответственно первого и второго операндов устройства, выход второго регистра подключен .к первым информационным входам первого и второго коммутаторов, вторые информационные входы которых подключены к выходу третьего регистра, выход второго сумматора подключен к третьему информационному входу первого коммутатора, выход которого подключен к вторым входам первого сумматора и первого вычнтателя, выход второго выгитателя подключен к третьему информационно ry входу второго коммутатора, выход которого подключен к первым входам первого и второго сумматоров-вычитателей, вторые входы которых подключены к выходам шестого регистра, выход четвертого регистра подключен к входу первого дешпфратора, выход которого подключен к первым управляющим входам первого и второго коммутаторов, вторые управляющие вхо- ды которых объединены с управляющим входом первого сумматора-вычитателя и подключены к прямому выходу второго дешифратора, вход которого подключен к выходу пятого регистра, а инверсный выход второго дешифратора подключен к управляющему входу второго сум матора-вычитателя.

1242986 Составитель А..Баранов

Техред И.Гайдош Корректор О.Луговая

Редактор Н.Гунько

Заказ 3708/50 Тираж б71 Подписное

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

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

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