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

 

УСТРОЙСТВО ДЛЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее первый и второй регистры, информационные входы которых являются соответственно входами реальной и мнимой частей первого операнда устройства, первый и второй сумматоры-вычитатели, выходы которых являются выходами соответственно реальной и мнимой частей первого и второго операндов устройства , управляющие входы первого и второго регистров, первого и второго сумматоров-вычитателей соединены и являются тактовым входом устройства , входом запуска которого являются установочные входы первого и второго регистров, отличающееся тем, что, с целью упрощения устройства, оно содержит третий и четвертый регистры, первый и второй сумматоры, первый и второй коммутаторы, дешифратор знаков, четыре блока умножения и регистр знака, выходы первого и второго разрядов которого подключены к управляющим входам соответственно первого и второго коммутаторов, выходы которых подключены к первым входам соответственно первого и второго сумматоров-вычитателей , вторые входы которых подключены к выходам соответственно первого и второго сумматоров, информационные входы первого и второго коммутаторов подключены к информационным выходам соответственно первого и второго регистров, информационные входы третьего, и четвертого регистров являются соответственно входами реальной и мнимой частей коэффициентов устройства, знаковым входом которого является инфармационный вход регистра знака, (+2)-й (, 4) выход которого подключен к -i-My входу дешифратора знака, причем каждый блок умножения содержит сумматор , коммутатор, регистр и элемент И, выход которого подключен к первому входу сумматора, выход переноса которого подключен к первому информационному входу коммутатора, второй информационньй вход которого подключен к выходу старшего разряда регистра , выход младших разрядов которого подключен к второму входу сумматора, выход суммы которого подключен к информационному входу регистра, выходы коммутаторов первого и вторрго блоков умножения .подключены соответственно к первому и второму входам первого сумматора, а выходы коммутаторов третьего и четвертого блоков умножения - соответственно к первому и второму входам второго сумма,тора, i-й

(19) (! 2) СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК

Ш)4 С 06 F 15/332

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

Н ABTOPCHOMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТ8ЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3500711/24-24 (22) 15. 10. 82 (46) 30.07.85. Бюл. 0- 28 (72) В.А.Телековец и О.Н.Суменкова (71) Таганрогский радиотехнический институт им. В.Д.Калмыкова (53) 681.32(088.8) (56) Авторское свидетельство СССР

N - 598085, кл. G 06 F 15/332, 1.978.

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

Ф 7504949 кл. G 06 F 15/332, 1980. (54)(57) УСТРОЙСТВО ДЛЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее первый и второй регистры, информационные входы которьи являются соответственно входами реальной и мнимой частей первого операнда устройства, первый и второй сумматоры-вычитатели, выходы которых являются выходами соответственно реальной и мнимой частей первого и второго операндов устройства, управляющие входы первого и второго регистров, первого и второго сумматоров-вычитателей соединены и являются тактовым входом устройства, входом запуска которого являются установочные входы первого и второго регистров, о т л и ч а ю— щ е е с я тем, что, с целью упрощения устройства, оно содержит третий и четвертый регистры, первый и второй сумматоры, первый и второй коммутаторы, дешифратор знаков, четыре блока умножения и регистр знака, выходы первого и второго разрядов которого подключены к управляющим входам соответственно первого и второго коммутаторов, выходы которых подключены к первым входам соответственно первого и второго сумматоров-вычитателей, вторые входы: которых подключены к выходам соответственно первого и второго сумматоров, информационные входы первого и второго коммутаторов подключены к информационным выходам соответственно первого и второго регистров, информационные входы третьего,и четвертого регистров являются соответственно входами реальной и мнимой частей коэффициентов устройства, знаковым входом которого является информационный вход регистра знака, (1+2)-й (1=1, 4) выход которого подключен к

1-му входу дешифратора знака, причем каждый блок умножения содержит сумматор, коммутатор, регистр и элемент И, выход которого подключен к первому входу сумматора, выход переноса которого подключен к первому информационному входу коммутатора, второй информационный вход которого подключен к выходу старшего разряда регистра, выход младших разрядов которого. подключен к второму входу сумматора, вьиод суммы которого подключен к информационному входу регистра, выходы коммутаторов первого и второго блоков умножения .подключены соответственно к первому и второму входам первого сумматора, а выходы коммутаторов третьего и четвертого блоков умножения — соответственно к первому и второму входам второго сумматора, j-g (=1, 4) выход дешифратора знака подключен к. управляющему входу коммутатора i -го блока умножения, управляющий вход регистра которого соединен с входами синхронизации первого и второго сумматоров и явля11704б2 ется тактовым входом устройства, а первые входы элементов И второго и установочный вход регистра i --ro третьего блоков умножения, вторые блока умножения соединен с установоч- входы элементов И первого и третьего ными входами третьего и четвертого блоков умножения подключены к инрегистров и с входом запуска устрой- формационному выходу третьего рества, первые входы элементов И перво- . гистра, а информационный выход

ro и четвертого блоков умножения четвертого регистра подключен соединены и являются входом реальной к вторым входам элементов И части второго аргумента устройства, второго и четвертого блоков умвходом мнимой части которого являются ножения.

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

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

На чертеже изображена блок-схема устройства, Устройство содержит входы 1 и 2 реальной и мнимой частей первого операнда А, регистры 3 и 4, входы 5

Э и Ь реальной и мнимой частей коэффициента С,, регистры 7 и 8, группу знаковых входов 9 устройства, регистр 10 знака, коммутаторы 1 1 и 12, дешифратор 13 знаков, коммутатор 14, блоки 15-18 умножения, входы 19 реальной части второго операнда устройства В элемент И 20 вход 21 мниФ У

20 мой части второго операнда устройства, сумматор 22, регистр 23, сумматор 24, сумматор-вычитатель 25, выходы 2б и 27 реальных частей соответственно первого А;„ и второго В „ операндов, сумматор 28, сумматор-вычитатель 29, выходы 30 и 31 мнимых частей соответственно первого А;, и второго В;„ операндов устройства, входы 32 запуска устройства, тактовый

30 вход 33 устройства.

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

А =А +В С н

В А -В С;.

1Ф! I 1

Произведение операнда В„ на весовой коэффициент С„ вычисляется по алгоритму Ке(В;С; ) ReB; ReC; +ImB„. ImCq 1 (1)

Im(B„ C))=ИВ;КеС;-ReB; ImC, (2) «

В начале каждого цикла работы на первый управляющий вход 32 устройства подается импульс запуска, а на группу входов 9 устройства подаются значения знаков реальной и мнимых частей операндов и коэффициента, которые заносятся в регистр 10 знака импульсов запуска. Одновременно на входы 5 и 6 устройства подаются значения и разрядов реальной и мнимой частей коэффициента, которые заносятся в л-разрядные регистры 7 и 8.

Импульс запуска устанавливают также в нулевое состояние регистры 3 и 4 и регистры 23 блоков умножения.

Начиная с первого такта работы, на входы 1 и 2 устройства подаются значения вещественной и мнимой частей первого операнда А„ последовательно разряд за разрядом, начиная от старmего разряда, которые поступают в регистры 3 и 4. Одновременно на входы

19 и 21 устройства подаются значения реальной и мнимой частей второго аргумента В1 также последовательным кодом, старшими разрядами вперед, которые поступают на первые входы элементов И 20 и блоков 15-18 умножения. На второй управляющий вход 33 устройства поступают тактовые импульсы которые подаются на .управляющие входы регистров 3 и 4, регистров 23 блоков умножения, сумматоров 24 и 28 и сумматоров-вычитателей 25 и 29.

Работу блоков 15-18 умножения рассматривают на примере работы блока 15 умножения, так как все блоки умножения работают аналогично.

В каждом j --м такте работы (1 =

1,2,...) на первые входы элемента

1170

И 20 блока 15 умножения поступает значение j -го разряда реальной час1 ти второго операнда ReB, а на вторые входы элемента И 20 подаются значения и разрядов реальной части коэффициента ReC с выходов регистра 7.

При этом на первый элемент И подается значение первого (младшего) разряда реальной части коэффициента

ReC ., на второй элемент И подается 10

1 значение второго разряда реальной части коэффициента КеС1 и т.д. На и-й элемент И подается значение старшего и --го разряда реальной части коэффициента КеС;. На выходах эле- 15 и ментов И 20 в каждом 1 -м такте работы будет получено и -разрядное произведение ReB, ReC;, которое подается на первые входы и разрядов сумматора 22. Полученное в 1 -м так- 20 те работы произведение значения ) -го разряда реальной части второго операнда и реальной части коэффициента суииируется со значением (п-1) младших разрядов суммы произведений, 25 полученной в () — 1)-м такте работы устройства, которое подается с выходов (и-1) младших разрядов регистра 23 на вторые входы разрядов сумматоров 22 со второго по и -й (т.е. 30 со сдвигом иа один разряд в сторону старших разрядов). Значение старшего (о+1)-ro разряда результата сложения с выхода переноса сумматора 22 подается на первый вход коммутатора

14, а значения остальных и разрядов полученного результата с выходов сумматора 22 записываются в регистр

23. На второй информационный вход коммутатора 14 с выхода старшего раз- 0

40 ряда регистра 23 в каждом 1 -м такте работы подается значение и -го разряда результата сложения, полученного s(j-1)-м такте работы. На управляющий вход комиутатора 14 с первого 4 выходадешифратора 13 знака поступает значение знака произведения 1(п(КеВ; > ,>ReC< ) .;Если знак равен нулю, т.е. произведение положительно, то выходной коииутатор 14 передает информацию со своих входов на первую группу положительных входов последовательного сумматора 24, работающего в избыточной системе счисления. Если знак произведения равен единице, 462 4 т.е. произведение отрицательно, то выходной коммутатор 14 передает информацию со своих входов на первую группу отрицательных входов сумматора

24. На вторые группы положительных и отрицательных входов сумматора 24 поступают значения произведений модулей мнимых частей второго операнда коэффициента с выходов коммутатора

14 второго блока 16 умножения. Таким образом, на выходе сумматора 24 получаем значения реальной части произведения второго операнда В; на коэффициент Cj согласно выражению (1).

Аналогично на выходе сумматора 28 получаем значения мнимой части произведения второго операнда В на коэф( фициент С„ ° ЗнаЧения реальной части произведения В С„ с выхода суиматора

24 подаются на вторую группу входов сумматора-вычитателя 25 в избыточном коде, старшими разрядаии вперед. На первую группу входов сумматора-вычитателя 25 с выхода регистра 3 через коммутатор 11 подается задержанное значение реальной части первого операнда ReA . Коммутатор 11 управляется значением знака операнда ReA;, которое подается на управляющий вход коммутатора 11 с первого выхода регистра 10 знака, со второго выхода которого управляющий сигнал, соответствующий знаку операнда ImA подается на управляющий вход коммутатора 12. В зависимости от значения знаков КеА; и ImA; коммутаторы 11 и 12 подают значения операндов ReA; и ImA; на положительные или отрицательные входы сумматоров-вычитателей 25 и 29, которые работают в избыточной системе.

Сумматор-вычитатель 25 подает на выходы 26 и 27 устройства значения реальных частей вычисленных аргументов А + и В; „ в соответстйии с алгоритмом

ReA;,„=ReA; +Re(B, ° С„), ReB„, КеА1 -Re(B„° ) .

Сумматор-вычитатель 29 подает на выходы 30 и 31 устройства значения мнимых частей вычисленных операндов

А;,„и В„+, в соответствии с алгоритмом

ImA1í тщА4+ Im(B4 Cl) 1170462

_#_

27

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

Техред A.Âàáèíåö Корректор В.ГиРнЯк

Редактор Е.Копча

Заказ 4705/46 Тираж 710 Подписное

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

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

Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4