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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК 9) (11) 6 151) 4 С Об Р 15/33 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ ТВУ СВИДЕТ АВТОРСНО(71) Специальное конструкторсконологическое бюро с опытным проством при Белорусском государстном университете им. В.И.Ленина(56) Авторское свидетельство СС(54) УСТРОЙСТВО ДЛЯ РЕАЛРОГО ПРЕОБРАЗОВАНИЯ фУР-тех звод тения - повьппецие быст Достигается цель за сч введени ен троиство первого и втов известно счетчик а И, триггеИЛИ. Это поз е устройств я и уменьши виальный мн нд еме ляет сокрачисло операвремя умно- житель. Изобзовано при м анализе 3 ил. и злетить ента рабо ноженСР 79 ини 79 е может быть испо ально-корреляцион полосных сигналов рете спек акиро ОПИСАНИЕ ИЗОБРЕТЕНИ112331Изобретение относится к вычисливтельной технике и может быть использовано при спектрально-корреляционном анализе широкополосных сигналов.Цель изобретения - повышение быстродействия за счет сокращения числа операций умножения и уменьшения времени умножения на тривиальный мно 66 2ицформациоццым входам перв го ц трет ьв его умножителей, выход регистра хранения косинуса подключен к вторым информационным входам второго и четвертого умножителей, первые управляющие входы умножителей соединены и являются третьим управляющим входом арифметического блока 4, вторые управляющие входы второго и четвертого умножителей соединены с входом второго ицвертора и являются вторым управляющим входом арифметического блока 4, выход второго инвертора подключен к вторым входам первого и второго умножителей.При коце ОО на установочном входе умцожителя операция умножения не выполняется, а ца выход умножителя передается информация с первого информационного входа умножителя . При коде 01 на установочном входе умножителя операция умножения также не выполняется, а на выходе умножителя устанавливается уровень логического "0Блок управления (фиг, 2) содержит ь-разрядный коммутатор 10 (ь= Ро,Н, где Н - общее число операндов, записанных в блоке 1 оперативной памяти, (ь =1)-разрядный регистр 11 сдвига, ;ь)-разрядный регистр 12 хранения, (ь) -разрядный сумматор 13, узел элементов И 14, управляемый регистр 15 сдвига,-разрядный второй 16 и Ь +1) -разрядный первый 17 счетчики, (ь -1)-разрядный коммутатор 18, элемент И 19, триггер 20, 1 ь -2)-разрядный коммутатор 21 (ъ: с.ь ),-разрядный (итерационный) счетчик 22, выходы у 2 - у 5 блока управления, вход х 2 блока управления,Устройство работает следующим образом.Исхоццая И -точечная последовательность занесена в блок 1 оперативной памяти,В исходном состоянии триггер 8,счетчик 9,дсчетчики 16 и 17, итерационный счетчик 22, регистр 12 хранения и триггер 20 обнулены.Во все разряды регистра 11 сдвига занесена .логическая "1", По входу х 1 устройства на первый вход первого элемента И 5 поступают тактовые импульсы и, поскольку ца втором входе первого элемента И 5 установлен уров вь лоическои 1 идут на вход блока 3 управления, ца первом выходекоторого формируются адреса оиераи - дон, необходимых для вьчисле ния БПФ, на втором и третьем выходах - адреса экспоненциальных множителей, По низкому потенциалу на пятом выходе блока 3 управления осуществляется считывание операндов из блока 1 оперативной памяти, по высокому потенциалу - запись новых операндов в блок 1 оперативной памяти на место ранее из влеченных операндов.Вычесление итерации БПФ в устройстве заключается в последовательном выполнении в арифметическом блоке 4 двух элементарных операций вида 15 (х-.х )А и (х, +, х )1.1 где хи х - соответственно первый и второй операнды, извлекаемые из блока 1 оперативной памяти, представляемые как значения их действительных и мни- щ мых частей, -1 и , - соответственно, первый и второй экспоненциальные множители, извлекаемые из блока 2 памяти коэффициентов. В последнем экспоненциальные множители записаны д как значения синуса и значения косинуса показателя экспоненциального множителя.При выполнении итерации БПФ предлагаемое устройство работает в одном З 0 из режимов: "Полное комплексное умножение", "Умножение на тривиальный множитель Режим Полное комплексное умножение выполняется при наличии на выхо де элмента ИЛИ 6 уровня логической "1". В этом случае по высокому уровню потенциала с пятого выхода блока 3 управления на выходе элемента И 7 сформирован сигнал, который переводит 40 триггер в единичное состояние, Низким потенциалом с инверсного выхода триггера 8 первый элемент И 5 закрывает поступление тактовых импульсон на вход блока 3 управления. Сигнал с пря 45 мого выхода триггера 8 переводит ,в режим счета счетчик 9. Высокий уровень на выходе элемента ИЛИ 6 разрешает всем множителям арифметического блока 4 проиэвести операцию сум мы и разности реальных и мнимых частей операндов, извлеченных ранее из блока 1 оперативной памяти, (Р, х + + х ) и (1 х - Р х ) на значение сиь, 2 12нуса и косинуса, также извлеченных 55 ранее из блока 2 памяти коэффициентов, ,занесенных в регистры хранения арифметического блока 4 и представляющих собой первый экспоненцияльный м)ож - телль, Полученные произведения (х, -- .1 х ) "с м,(где о - показатрль пер - ного экспоненциального множителя), р(х х ) ьч ( (х, х )и 1, х. - , х ) со " поступают на входы третьего и четвертого сумматоров, на выходах которых формируются соответственно действительная и мнимая части операнда е(х -х)сз," + +Рр(х) х )ьп Ч, и 1 (х - , х )ГаэГ, - 1(х, - ,х,)Б и заносятся в блок 1 оперативной памяти на место извлеченного ранее первого операнда.По окончании вычисления нового первого операнда высоким потенциал с выхода старшего разряда счетчика 9 (разрядность счетчика 9 на один разряд больше разрядности операндов, записанных в блоке 1 оперативной памяти, поступающим на вход сброса триггера 8, последний переводится в нулевое состояние, В результате счетчик 9 обнуляется, а элемент И 5 пропускает на вход блока 3 управления следующий тактовый импульс. Блок 3 управления формирует адрес второго экспоненциального множителя, высоким потенциалом с четвертого выхода блока 3 управления первый сумматор переводится в рейдм вычитания, а второй сумматор арифметического блока 4 - в режим сложения, и при высоком выходном уровне ня выходе элемента ИЛИ 6 указанным способом вычисляется новый второй операнд (х, -х )1 и заносится в блок 1 оперативной памяти на место извлеченного второго операнда,При низком логическом уровне на выходе элемента ИЛИ 6, т.е. при коде адреса экспоненциального множителя, содержащем либо только нули (показатель экспоненциального множителя равен нулю), либо нули и логическую единицу в старцем разряде (показатель экспоненциального множителя равен г /2) устройство переходит к режиму Умножение на тривиальный множительВ этом случае тактовые импульсы поступают через элемент И 5 на вход блока 3 управления, поскольку нет необходимости в прерывании работы блока управления вследствие отсутствияопераций умножения,При нулевом показателе экспоненциального множителя синус показателя равен нулю, а косинус показателяединице, Поэтому на выходе умножите 12331 бблей, осуществляющих умножение на синус показателя экспоненциального множителя, устанавливается сразу потенциал логического 0, а на выходе5 умножителей, осуществляющих умножение на косинус - потенциал логической "1".При равенстве Р/2 показателя экспоненциального множителя синус показателя равен единице, а косинус нулю. Соответственно на выходы умножителей, осуществляющих умножение на синус показателя экспоненциального множителя, проходит информация с первых входов умножителей, а на выходе умножителей, осуществляющих операцию умножения на косинус показателя - логической 0.Реализация алгоритма ЬПФ с уменьшенным числом операций умножителя обеспечивается прежде всего блоком управления (фиг. 2) в соответствии с графом (фиг. 3), где кружок обозначает процедуру Формирования новых двух операндов, а цифры под точками, 25 обозначающими операнды, записываемые и считываемые из блока 1 оперативной памяти, - показатели экспоненциальных множителей, использованных при вычислении данного операнда, ЗОТактовые импульсы с:выхода первого элемента И 5 поступают на тактовый вход счетчика 17, итерационный счетчик 22 формирует на выходе код, управляющий работой селектора бло 35 ка 15 управляемого сдвига, По сигналу перехода из низкого логического уровня в высокий с выхода коммутатора 21 формируется код адресов экспоненциальных множителей с показателями, отличными от нуля. В этом случае триггер 20 с помощью элемента И 19 Формирует одиночный импульс длительностью, равной длительности импульсов на выходе первого разряда счетчика 17.ЯЭтот импульс поступает на тактовый вход счетчика 1 б и на управляющий вход блока 18 коммутатора, пропуская на его выход в двоично-инверсном порядке с выхода счетчика 1 б код, который поступает на вход сумматора 13 и является кодом адреса первого экспоненциального множителя.Такой же импульс, но противоположной полярности с инверсного выхода элемента И 19 поступает на вход узла элементов И 14 и блокирует прохождение на вход сумм-тора 13 с выхода управляемого регистра 15 сдвиг кода,представляющего собой второе слагаемое, необходимое для вычисления кодовадресов остальных экспоненциальныхмножителей,11 о окончании импульса на выходеэлемента И 19 к входу сумматора 13.коммутатор 18 подключает группувыходов регистра 12 хранения, а к входу сумматоров 13 узел элементов И 14пропускает код с выхода управляемогорегистра 15 сдвига,По тактовым импульсам, поступающим на вход синхронизации, сумматор 13 производит операцию суммирования уже занесенной в регистр 12 хране.ния информации с информацией, поступающей на первый вход сумматорас выхода узла элементов И 14,По сигналу перехода из высокогологического уровня в низкий с выходаселектора 21 регистр 12 хранения обнуляется, и на выходах регистра формируются коды адресов экспоненциальных множителей, содержащие лишь однинули 1,т.е. показатель экспоненциального множителя равен нулю).Одновременно с формированием адресов экспоненциальных множителей записанных в блоке 2 памяти коэффициентов, на выходе коммутатора 10 из кодов на группы вьглодов счетчика 17с помощью регистра 11 сдвига формируются адреса операндов, извлекаемыхиз блока 1 оперативного памяти.По окончании вычисления очереднойитерации счетчик 16 обнуляется сигналом перехода из состояния логичес -кой "1" в "0" с выхода старшего разряда счетчика 17, в регистре 11 сдвига происходит сдвиг информации в сторону младших разрядов с занесениемлогического н 0 в старший разряд, навыходе итерационного счетчика 22формирует:я новый управляющий код, иустройство начинает вычисление новойитерацииФормула изобретенияУстройство для реализации быстрого преобразования Фурье, содержащее блок памяти, информационный выход которого поцключен к входу операндов арифметического блока, информационный выход которого подключен к информационному входу блока памяти и является информационным выходом уст 7 1233 ройства, блок управления и блок постоянной памяти, информационный выход которого подключен к входу коэффициентов арифметического блока, о т л ич а ю щ е е с я тем, что; с целью повьпцения быстродействияв него введены первый и второй элементы И, триггер, счетчик и элемент ИЛИ, выход которого подключен к первому входу первого элемента И, выход кото О рого подключен к первому установочно - му входу триггера, прямой выход которого подключен к входу обнуления счетчика, выход переполнения которо - го подключен к второму установочному входу триггера, инверсный выход которого подключен к первому входу второго элемента И, второй вход которого соединен со счетным входом счетчика и является тактовым входом устройства, причем блок управления содержит Регистр, сумматор, узел элементов И, первый, второй и третий коммутаторы, управляемый регистр сдвига, элемент И, первый, втоРой д и третий счетчики, триггер, регистр сдвига, выход третьего коммутатора подключен к информационному входу триггера, входу обнуления регистра и первому входу элемента И, прямой выход которого подключен к управляющему входу первого коммутатора и тактовому входу первого счетчика, информационный выход которого подключен к информационному входу управляемого регистра сдвига и первому инфор 5 мационному входу первого коммутатора, выход которого подключен к первому входу сумматора, выход которого подключен к информационному входу реЮ гистра, информационный выход которого подключен к второму входу первого коммутатора, выход (в+1) -го разряда второго счетчика подключен к тактово 166 8му входу регистра сдвига, входу обнуления первого счетчика и счетномувходу третьего счетчика, информационньп выход которого подключен к управляющему входу третьего коммутатора иуправляющему входу управляемого регистра сдвига, информационньп выходкоторого подключен к первому входуузла элементов И, выход которого подключен к второму входу сумматора,инверсный выход элемента И подключенк второму входу узла элементов И,выход-го ( =1, л +1;Ф 2) разрядавторого счетчика подключен к 1 - муразряду первого информационного входа второго коммутатора, второй информационный вход которого подключенк информационному выходу регистрасдвига, выход-го ( =2, л -1) разряда второго счетчика подключен к-муразряду информационного входа третьего коммутатора, информационные входырегистра и второго коммутатора блокауправления подключены к адреснымвходам соответственно блока постоянной памяти и блока памяти, вход управления записью-считыванием которогосоединен с вторым входом первогоэлемента И и подключен к выходу второго разряда второго счетчика блокауправления, выход первого разрядакоторого подключен к входу синхронизации арифметического блока, выходк. й(к =1,-1) разряда регистра блокауправления подключен к к -му входуэлемента ИЛИ, выход которого объединен с выходом и -го разряда регистра блока управления и подключенк установочному входу арифметическогоблока, а выход второго элемента Иподключен к счетному входу второгосчетчика, входу синхронизации сумматора и входу синхронизации триггера блока управления,1 1.Саенко Техред 0 .Сопко К ректор С.Черн акт каз 2772/51 В 1 ПИГИ Госу по делам 113035, Москваираж 671арственного комиизобретений и отЖ, Раушская Подписита СССР ытииб., д. 4/5 жгород, ул.Проектна оизводственно-полигра ическое предприятие