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

 

Изобретение относится к области вычислительной техники. Цель изобретения - повышение быстродействия. Достигается цель за счет введения в известное устройство первого и второго элемента И, триггера, счетчика и элемента ИЛИ. Это позволяет сократить в работе устройства число операций умножения и уменьпмть время умножения на тривиальный множитель. Изобретение может быть использовано при спектрально-корреляционном анализе широкополосных сигналов. 3 ил. с & СО ОЭ О5 сг

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

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

РЕСПУБЛИК

„„SU 1233166

А1 (g)) 4 G 06 F 15/332

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

К А BTOPCH05hV СВИДЕТЕЛЬСТВУ (21) 3685 144/24-24 (22) 04.01.84 (46) 23.05.86. Бюл. ¹ 19 (71) Специальное конструкторско-технологическое бюро с опытным производством при Белорусском государственном университете им. В.И.Ленина (72) А.Н.Карташевич и М.С.Курлянд (53) 681.82(088.8) (56) Авторское свидетельство СССР № 809198, кл. С 06 F 15/332, 1979.

Авторское свидетельство СССР № 814122, кл. G 06 F 15/332, 1979.

Авторское свидетельство СССР № 1119025, кл . С 06 F 15/332, 10.06.83. (54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к области вычислительной техники. Цель изобретения — повышение быстродействия.

Достигается цель за счет введения в известное устройство первого и второго элемента И, триггера, счетчика и элемента ИЛИ. Это позволяет сократить в работе устройства число операций умножения и уменьшить время умножения на тривиальный множитель. Изобретение может быть использовано при спектрально-корреляционном анализе широкополосных сигналов. 3 ил.

12331

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

Цель изобретения — повышение быстродействия за счет сокращения числа операций умножения и уменьшения времени умножения на тривиальный множитель.

На фиг. 1.изображена структурная 10 схема предлагаемого устройства; ка фиг. 2 — функциональная схема блока управления; на фиг. 3 — граф, Устройство (фиг. 1) содержит блок 1 (оперативной) памяти, блок 2 15 постоянной памяти (коэффициентов), блок 3 управления, арифметический блок 4, элемент И 5, элемент ИЛИ 6, элемент И 7, триггер 8, счетчик 9, тактовый вход х1 устройства, информа- 26 ционный выход у1 устройства. Разрядность счетчика 9 на один разряд больme разрядности операндов, записанных в блохе 1 оперативной памяти.

Арифметический блок 4 предназна- 25 чен для выполнения операций вида (x, +„х )W и содержит четыре сумматора, четыре умножителя, два инвертора, четыре входных регистра хранения мни1 мых и действительных частей первого ЗО и второго операндов, регистр синуса и регистр косинуса для занесения значения экспоненциального множителя„ причем выходы хранения реальных частей первого и второго операндов подключены к первым входам первого и второго сумматоров, выход регистра хранения мнимой части первого операнда — к второму информационному входу второго сумматора, выход регистра хранения мнимой части второго операнда — к второму информационному входу первого сумматора., управляющий вход первого сумматора соединен с входом первого инвертора и является первым управляющим входом арифметического блока 4, выход первого инвертора подключен к управляющему входу второго сумматора, выход первого сумматора — к первым информационным 50 входам первого и второго умножителей, вь,ходы которых подключены к входам третьего сумматора, выход второго сумматора подключен к первым входам третьего и четвертого умножителей, выходы которых подключены ко входам четвертого сумматора„ выход регистра хранения синуса подключен к вторым

66 2 информационным входам перв го и трет F, его умножителей, выход регистра хранения косинуса подключен к вторым информационным входам второго и четвертого умножителей, первые управляющие входы умножителей соединены и являются третьим управляющим входом арифметического блока 4, вторые управляющие входы второго и четвертого умножителей соединены с входом второго инвертора и являются вторым управляющим входом арифметического блока 4, выход второго инвертора подключен к вторым входам первого и второго умножителей.

При коце 00 на установочном входе умножителя операция умножения не выполняется, а на выход умножителя передается информация с первого информационного входа умножителя. При коде 01 на установочном входе умножителя операция умножения также не выполняется, а на выходе умножителя устанавливается уровень логического "0""

Блок управления (фиг. 2) содержит -разрядный коммутатор 10 (h= Fog,N, где N — общее число операндов, записанных в блоке 1 оперативной памяти, (h =1)-разрядный регистр 11 сдвига, ,h-i) ðàçðÿäHûé регистр 12 хранения, (ь -1) -разрядный сумматор 13, узел элементов И 14, управляемый регистр 15 сдвига,.h -разрядный второй 16 и (h +1) †разрядн первый 17 счетчики, (ь -1)-разрядный коммутатор 18, элемент И 19, триггер 20, (- -2)-разрядный коммутатор 21 (=,,ь ), -разрядный (итерационный) счетчик 22, выходы у2 — y5 блока управления, вход х2 блока управления.

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

Исхоцная И -точечная последовательность занесена в блок 1 оперативной памяти.

В исходном состоянии триггер 8, счетчик 9,"счетчики 16 и 17, итерационный счетчик 22, регистр 12 хранения и триггер ?О обнулены.

Во все разряды регистра 11 сдвига занесена .логическая "1". По входу х1 устройства на первый вход первого элемента И 5 поступают тактовые импульсы и, поскольку на втором входе первого элемента И 5 установлен уровень ло1 ическои 1 идут на вход блока 3 управления, на первом выходе

1233 ) 6! которого формируются адреса оиераи— дов, необходимых для вычисле пия БПФ, на втором и третьем выходах — адреса экспоненциальных множителей. По низкому потенциалу на пятом выходе блока 3 управления осуществляется считывание операндов из блока 1 оперативной памяти, по высокому потенциалу — запись новых операндов в блок 1 оперативной памяти на место ранее из- 10 влеченных операндов.

Вычесление итерации БПФ в устройстве заключается в последовательном выполнении в арифметическом блоке 4 двух элементарных операций вида f5 (х-jx )!,,! и (х, +J х )!.1,, гдe х, и х — соответственно первый и вто2 рой операнды, извлекаемые из блока 1 оперативной памяти, представляемые как значения их действительных и мни- щ мых частей, I4„ и !.!, — соответственно, первый и второй экспоненциальные множители, извлекаемые из блока 2 памяти коэффициентов. В последнем экспоненциальные множители записаны как значения синуса и значения косинуса показателя экспоненциального множителя.

При выполнении итерации БПФ предлагаемое устройство работает в одном З0 из режимов: "Полное комплексное умножение, "Умножение на тривиальный множитель

Режим Полное комплексное умножение выполняется при наличии на выхо-35 де элемента ИЛИ 6 уровня логической

"1". В этом случае по высокому уровню потенциала с пятого выхода блока 3 управления на выходе элемента И 7 сформирован сигнал, который переводит 40 триггер в единичное состояние. Низким потенциалом с инверсного выхода триггера 8 первый элемент И 5 закрывает поступление тактовых импульсов на вход блока 3 управления. Сигнал с пря45 мого выхода триггера 8 переводит .I в режим счета счетчик 9. Высокий уровень на выходе элемента ИЛИ 6 разрешает всем множителям арифметического блока 4 проиэвести операцию сум — 50 мы и разности реальных и мнимых частей операндов, извлеченных ранее из блока 1 оперативной памяти, (Р, х +

+! х ) и (! х — Р х ) на значение си2 1 нуса и косинуса, также извлеченных 55 ранее из блока 2 памяти коэффициентов,,занесенных в регистры хранения арифметического блока 4 и представляющих сс бой первый экспоненциалт ный множиTE-.-ль. !!олученные произведения h„(х — гх ) Co 4 (где 4, — †показате первого экспоненциального множителя),, (х, — х„) S» ч„((,,(х —,, х„) =. е и х х ) c» " поступают на входы третьего и четвертого сумматоров, на выходах которых формируютс я соответственно действительная и мнимая части операнда к е (х - х„)сз ", +

+Rp(x х )ь Х и 1 (х,lx )!а — 1 (х, —,i х,) S и заносятся в блок 1 оперативной памяти на место извлеченного ранее первого операнда.

По окончании вычисления нового первого операнда высоким потенциалом с выхода старшего разряда счетчика 9 (разрядность счетчика 9 на один разряд больше разрядности операндов, записанных в блоке 1 оперативной памяти, поступающим на вход сброса триггера 8, последний переводится в нулевое состояние. В результате счетчик 9 обнуляется, а элемент И 5 пропускает на вход блока 3 управления следующий тактовый импульс. Блок 3 управления формирует адрес второго экспоненциального множителя, высоким потенциалом с четвертого выхода блока 3 управления первый сумматор переводится в релжм вычитания, а второй сумматор арифметического блока 4 — в режим сложения, и при высоком выходном уровне ня выходе элемента ИЛИ 6 указанным способом вычисляется новый второй операнд (х, - х )!.! и заносится в блок 1 оперативной памяти на место извлеченного второго операнда.

При низком логическом уровне на выходе элемента ИЛИ 6, т.е. при коде адреса экспоненциального множителя, содержащем либо только нули (показатель экспоненциального множителя равен нулю), либо нули и логическую единицу в старшем разряде (показатель экспоненциального множителя равен я /2) устройство переходит к режиму Умножение на тривиальный множитель

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

При нулевом показателе экспоненциального множителя синус показателя равен нулю, а косинус показателя единице. Поэтому на выходе умножите1233166 лей, осуществляющих умножение на синус показателя экспоненциального множителя, устанавливается сразу потенциал логического "0, а на выходе

5 умножителей, осуществляющих умножение на косинус — потенциал логической "1".

При равенстве Р/2 показателя экспоненциального множителя синус показателя равен единице, а косинус нулю. Соответственно на выходы умножителей, осуществляющих умножение на синус показателя экспоненциального множителя, проходит информация с первых входов умножителей, а на выходе умножителей, осуществляющих операцию умножения на косинус показателя — логической "0 .

Реализация алгоритма ЬПФ с уменьшенным числом операций умножителя обеспечивается прежде всего блоком управления (фиг. 2) в соответствии с графом (фиг. 3), где кружок обозначает процедуру формирования новых двух операндов, а цифры под точками, 25 обозначающими операнды, записываемые и считываемые из блока 1 оперативной памяти, — показатели экспоненциальных множителей, использованных при вычислении данного операнда. ЗО

Тактовые импульсы с:выхода первого элемента И 5 поступают на тактовый вход счетчика 17, итерационный счетчик 22 формирует на выходе код, управляющий работой селектора бло35 ка 1S управляемого сдвига. По сигналу перехода из низкого логического уровня в высокий с выхода коммутатора 21 формируется код адресов экспоненциальных множителей с показателями, отличными от нуля. В этом случае триггер 20 с помощью элемента И 19 фор— мирует одиночный импульс длительностью, равной длительности импульсов на выходе первого разряда счетчика 17. .Я

Этот импульс поступает на тактовый вход счетчика 16 и на управляющий вход блока 18 коммутатора, пропуская на его выход в двоично-инверсном порядке с выхода счетчика 16 код, который поступает на вход сумматора 13 и является кодом адреса первого экспо-! ненциального множителя.

Такой же импульс, но противоположной полярности с инверсного выхода элемента И 19 поступает на вход узла элементов И 14 и блокирует прохождение на вход сумм-тора 13 с выхода управляемого регистра 15 сдвиг» кода, представляющего собой второе слагаемое, необходимое для вычисления кодов адресов остальных экспоненциальных множителей.

По окончании импульса на выходе элемента И 19 к входу сумматора 13 .коммутатор 18 подключает группу выходов регистра 12 хранения, а к входу сумматоров 13 узел элементов И 14 пропускает код с выхода управляемого регистра 15 сдвига.

По тактовым импульсам, поступаюцнм на вход синхронизации, сумматор 13 производит операцию суммирования уже занесенной в регистр 12 хране.ния информации с информацией, поступающей на первый вход сумматора с выхода узла элементов И 14.

По сигналу перехода из высокого логического уровня в низкий с выхода селектора 21 регистр 12 хранения обнуляется, и на выходах регистра формируются коды адресов экспоненциальных множителей, содержащие лишь одни нули (т.е. показатель экспоненциального множителя равен нулю).

Одновременно с формированием адре— сов экспоненциальных множителей„ записанных в блоке 2 памяти коэффициентов, на выходе коммутатора 10 из ко— дов на группы вьглодов счетчика 17 с помощью регистра 11 сдвига формируются адреса операндов, извлекаемых и"- блока 1 оперативного памяти.

По окончании вычисления очередной итерации счетчик 16 обнуляется сигналом перехода из состояния логичес— кой "1" в "0" с выхода старшего разряда счетчика 17, в регистре 11 сдвига происходит сдвиг информации в сторону младших разрядов с занесением логического н0 . в старший разряд, на выходе итерационного счетчика 22 формирует1=я новый управляющий код, и устройство начинает вычисление новой итерации ..

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

Устройство для реализации быстрого преобразования Фурье, содержащее блок памяти, информационный выход которого поцключен к входу операндов арифметического блока, информационный выход которого подключен к информационному входу блока памяти и является информационным выходом уст7 1233 ройства, блок управления и блок постоянной памяти, информационный выход которого подключен к входу коэффициентов арифметического блока, о т л ичающееся тем,что;с целью повьппения быстродействия,,в него введены первый и второй элементы И, триггер, счетчик и элемент ИЛИ, выход которого подключен к первому входу первого элемента И, вьгход кото-1ð рого подключен к первому установочно— му входу триггера, прямой выход которого подключен к входу обнуления счетчика, выход переполнения которо— го подключен к второму установочному входу триггера, инверсный выход которого подключен к первому входу второго элемента И, второй вход которого соединен со счетным входом счетчика и является тактовым входом устройства, причем блок управления содержит регистр, сумматор, узел элементов И, первый, второй и третий коммутаторы, управляемый регистр сдвига, элемент И, первый, второй д и третий счетчики, триггер, регистр сдвига, выход третьего коммутатора подключен к информационному входу триггера, входу обнуления регистра и первому входу элемента И, прямой выход которого подключен к управляющему входу первого коммутатора и тактовому входу первого счетчика, информационный выход которого подключен к информационному входу управляемого регистра сдвига и первому инфор5 мационному входу первого коммутатора, выход которого подключен к первому входу сумматора, выход которого подключен к информационному входу pel0 гистра, информационный выход которого подключен к второму входу первого коммутатора, выход (ь+1) -го разряда второго счетчика подключен к тактово166 8 му входу регистра сдвига, входу обнуления первого счетчика и счетному входу третьего счетчика, информационньп» выход которого подключен к управляющему входу третьего коммутатора и управляющему входу управляемого регистра сдвига, информационньп» выход которого подключен к первому входу узла элементов И, выход которого подключен к второму входу сумматора, инверснъ»й выход элемента И подключен к второму входу узла элементов И, выход i --го (» =1, л +1; » 2) разряда второго счетчика подключен к 1 — му разряду первого информационного входа второго коммутатора, второй информационный вход которого подключен к информационному выходу регистра сдвига, выход s -ro (» =2, л — 1) разряда второго счетчика подключен к » -му разряду информационного входа третьего коммутатора, информационные входы регистра и второго коммутатора блока управления подключены к адресным входам соответственно блока постоянной памяти и блока памяти, вход управления записью-считыванием которого соединен с вторым входом первого элемента И и подключен к выходу второго разряда второго счетчика блока управления, выход первого разряда которого подключен к входу синхронизации арифметического блока, выход к- (к =1,n-1) разряда регистра блока управления подключен к к -му входу элемента ИЛИ, выход которого объединен с выходом и --го разряда регистl ра блока управления и подключен к установочному входу арифметического блока, а выход второго элемента И подключен к счетному входу второго счетчика, входу синхронизации сумматора и входу синхронизации триггера блока управления.

I I 1 ( л ve

Ус

2

ФМО. д

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

Редактор А.Саенко Техред О .Сопко Корректор С.Черни

Заказ 2772/51 Тираж 671 Подписное

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

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

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