Устройство для реализации быстрого преобразования Фурье Советский патент 1986 года по МПК G06F17/14 

1

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

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

На фиг. 1.изображена структурная схема предлагаемого устройства; на фиг. 2 - функциональная схема блока управления; на фиг. 3 - граф.

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

Арифметический блок 4 предназначен для вьтолнения операций вида (,,)W и содержит четыре сумматора, четьфе умножителя, два инвертора четьгре входных регистра хранения мнимых и действительных частей первого и второго операндов, регистр синуса и регистр косинуса для занесения значения экспоненциального множителя,, причем выходы хранения реальных частей первого и второго операндов подключены к первым входам первого и второго сумматоров, выход регистра хранения мнимой части первого операнда - к второму информационному входу второго сумматора, выход регистра хранения мнимой части второго операнда - к второму информационному входу первого сумматора, управляющий вход первого сумматора соединен с входом первого инвертора и является первым управляющим входом арифметического блока 4, выход первого инвертора подключен к управляющему входу второго сумматора, выход первого сумматора - к первым информационным входам первого и второго умножителей выходы которых подключены к входам третьего сумматора, выход второго сумматора подключен к первым входам третьего и четвертого умножителей, выходы которых подключены ко входам четвертого сумматора, выход регистра кранелтя ctiHyca подключен к вторым

1662

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

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

Блок управления (фиг. 2) содержит h-разрядньй коммутатор 10 (,N, где N- общее число операндов, записанных в блоке 1 оперативной памяти,

0 (- 1)-разрядный регистр It сдвига, (и-1)-разрядный регистр 12 хранения, (h-|)-разрядный сумматор 13, узел элементов И 14, управляемый регистр 13 сдвига, .h-разрядный второй 16 и (h+1)-разрядный первый 17 счетчики, (-1)-разрядный коммутатор 18, элемент И 19, триггер 20, (ь-2)-разрядный коммутатсф 21 (fv, ) ,, (-разрядный (итерационный) счетчик 225 выходы у2 - у5 блока управления, вход х2 блока управления.

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

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

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

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

5

0

3

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

Вычесление итерации БПФ в устройстве заключается в последовательном вьтолнении в арифметическом блоке 4 двух элементарных операций вида ()w и (,,)w2 , где х и х - соответственно первый и второй операнды, извлекаемые из блока 1 оперативной памяти, представляемые как значения их действительных и мни мых частей, W, и iv)j - соответственно первый и второй экспоненциальные множители, извлекаемые из блока 2 памяти коэффициентов. В последнем экспоненциальные множители записаны как значения синуса и значения косинуса показателя экспоненциального множителя.

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

Режим Полное комплексное умножение вьшолняется при наличии на выходе элемента ИЛИ 6 уровня логической 1. В этом случае по высоком;, уровню потенциала с пятого выхода блока 3 управления на выходе элемента И 7 сформирован сигнал, который переводит триггер в единичное состояние. Низким потенциалом с инверсного выхода триггера 8 первый элемент И 5 закрывает поступление тактовых импульсов на вход блока 3 управления. Сигнал с пря мого выхода триггера 8 переводит в режим счета счетчик 9. Высокий уровень на выходе элемента ИЛИ 6 разрешает всем множителям арифметического блока 4 произвести операцию сум- мы и разности реальных и мнимых частей операндов, извлеченных ранее из блока 1 оператирной памяти, ( +1 X.) и ( X ) на значение сиbrs 7W 1 Р 7

нуса и косинуса, также извлеченных ранее из блока 2 памяти коэффициентов .занесенных в регистры хранения арифметического 6.1К1КЯ 4 и представляющих

ЬЬ4

сс1бой первый экспоненцпальнып множитель. Полученные произведения Rp( -jx,,) ,- показатель первого экспоненциального множителя), Лх,- х) S,H%, (l,(x,-,iX,,) ::v,.4, и I к( X ) Cos ч-, поступают на входы третьего и четвертого сумматоров, на выходах которых форм груются соответственно действительная и мнимая части операнда R е ( х,, )Cos4, + Rf,(x.,-jx,j)S,b ч, и i( pCocAf, - - 1,(х,-,)Х) Sir Ч , и заносятся в блок оперативной памяти на место извлеченного ранее первого операнда.

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

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

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

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

а на выходе

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

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

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

Тактовые импульсы с выхода первого элемента И 5 поступают на такто- вьш вход счетчика 17, итерационный счетчик 22 формирует на выходе код, управляющий работой селектора блока 15 управляемого сдвига. По сигналу пере хода из низкого логического уровня в высокий с выхода коммутатора 21 формируется код адресов экспонени аль ных множителей с показателями, отличными от нуля, Б этом случае триггер 20 с помощью элемента И 19 формирует одиночный импульс длительностью, равной длительности импульсов на выходе первого разряда счет- чика 17,

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

Такой же импульс, но противоположной полярности с инверсного выхода элемента И 19 поступает на вход узла элементов И 14 и блокирует прохождение на вход сумм:;тора 13 с выхода

0

0

5

0

5

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

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

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

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

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

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

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

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

ронства, блок управления и блок постоянной памяти, информационный выход которого подключен к входу коэффициентов арифметического блока, отличающееся тем, что, с целью повь шения быстродействия, jB него введены первый и второй элементы И, триггер, счетчик и элемент ИЛИ, выход которого подключен к первому входу первого элемента И, выход которого подключен к первому установочному входу триггера, прямой выход которого подключен к входу обнуления счетчика, вькод переполнения которого подключен к второму установочному входу триггера, инверсный выход которого подключен к первому входу второго элемента И, второй вход которого соединен со счетным входом счетчика и является тактовым входом устройства, причем блок управления содержит регистр, сумматор, узел элементов И, первый, второй и третий коммутаторы, управляемый регистр сдвига, элемент И, первый, второй и третий счетчики, триггер, регистр сдвига, выход третьего коммутатора подключен к информационному входу триггера, входу обнуления регистра и первому входу элемента И, прямой выход которого подключен к управляющему входу первого коммутатора и тактовому входу первого счетчика, информационньш выход которого подключен к информационному входу управляемого регистра сдвига и первому инфор- мационному входу первого коммутатора выход которого подключен к первому входу сумматора, выход которого подключен к информационному входу регистра, информационный выход которого подключен к второму входу первого- коммутатора, выход .(+ 1)го разряда второго счетчика подключен к тактово

j fg 0 5 Q

668

му входу регистра сдвига, входу обнуления первого счетчика и счетному в ходу третьего счетчика, информационньш выход которого подключен к управляющему входу третьего коммутатора и управляющему входу управляемого регистра сдвига, информационньш выход которого подключен к первому входу узла элементов И, выход которого подключен к второму входу сумматора, инверсный выход элемента И подключен к второму входу узла элементов И, выход i-го (, h + 1; i ) разряда второро счетчика подключен к t-му разряду первого информационного входа второго коммутатора, второй информационньш вход которого подключен к информационному выходу регистра сдвига, выход J -го , h-1) разря- - да второго счетчика подключен кj -му разряду информационного входа третьего коммутатора, информационные входы регистра и второго коммутатора блока управления подключены к адресным входам соответственно блока постоянной памяти и блока памяти, вход управления записью-считыванием которого соединен с вторым входом первого элемента И и подключен к выходу второго разряда второго счетчика блока управления, выход первого разряда которого подключен к входу синхронизации арифметического блока, выход к-(к 1 ,1-1) разряда регистра блока управления подключен к к-му входу элемента ИЛИ, выход которого объединен с выходом h-го разряда регист- ра блока управления и подключен к установочному входу арифметического блока, а выход второго элемента И подключен к счетному входу второго счетчика, входу синхронизации сумматора и входу синхронизации триггера блока управления.

Vc

г -с.; 5 Составитель А.Баранов Редактор А.Саенко Техред О.Сопко Корректор С.Черни

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

ВШдаГМ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

;5

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