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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК06 Г 15/ЗЗ ЕТЕНИ Е П":ЛЬСТВ АВТОРСНО колаевсГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ПИСАНИЕ ИЗ(71) Научно-исследовательский институт прикладных физических проблем им. акад. А.Н. Сенченко(56) 1. Авторское свидетельство СССР 9 809198, кл. С 06 Р 15/332, 1979.2, Авторское свидетельство СССР В 814122, кл, С 06 Р 15/332, 1979 (прототип).(54)(57) УСТРОЙСТВО УПРАВЛЕНИЯ ДЛЯ ПРОЦЕССОРА БЫСТРОГО ПРЕОБРАЗОВАНИЯФУРЬЕ, содержащее генератор тактовыхимпульсов, выход которого являетсявыходом синхронизации устройства иподключен к тактовому входу счетчика, выход-го (ъ = 1,м 1 Ф 2,3) разряда которого соединен с первым входом -го (Я = 1 рт) элемента Игруппы, выход которого соединен с-ым входом первого коммутатора кода,выход которого является первым адресным выходом устройства, выходя-го разряда счетчика соединен с последовательным входом первого сдвиговогорегистра, выход-го разряда которого подключен к второму входу-го элемента И группы, выход. первого разряда счетчика соединен с управляющимвходом первого коммутатора кода, а выход второго коммутатора кода яв. ляется вторым адресным выходом устройства, о т л и ч а-ю щ е е с я тем, что, сцелью повышения быстродействия,в него введены второй сдвиговый ре.ЯО 1 И 1173 гистр, два элемента ИСКЛЮЧАЮЩЕЕ ИЛИ,два элемента И и триггер режима, выход которого соединен с первым входомпервого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ,второй вход которого объединен с управляющим входом второго сдвиговогорегистра и подключен к выходу второгоэлемента ИСКЛЮЧАЮЩЕЕ,ИЛИ, первый входкоторого соединен с выходом второгоразряда счетчика, выход третьего разряда которого является выходом управления записью-считыванием устройстваи подключен к второму входу второгоэлемента ИСКЛЮЧАЮЩЕЕ ИЛИ, вход триггера режима соединен с выходомут)-горазряда счетчика выход ъ-го (ъ = аЭе- 1,1 р ъФ 2,3) разряда которого подключая к входу ) -го С 1,о) разряда Явторого сдвигового регистра, выходз-го разряда которого соединен с 1, -м Ъ,входом второго коммутатора кода, управляющий вход которого подключен квыходу первого элемента И, первый)вход которого соединен с выходомвторого элемента И, второй вход -которого подключен к последовательномувыходу первого сдвигового регистра,второй вход первого элемента И объединен с тактовым входом счетчика,выход второго разряда которого является выходом режима работы устройства, последовательный выход второгосдвигового регистра подключен. к последовательному входу второго сдвиговогорегистра, выход первого элементаИСКЛ 10 ЧАЮЩЕЕ ИЛИ является третьим ад- .ресным выходом устройства, а первыйвход второго элемента И является входом задания режима устройства.ным выходом устройства, выход Р-горазряда счетчика соединен с последовательным входом первого сдвиговогорегистра, выход -го разряда которого подключен к второму входу 1 -гоэлемента И группы, выход первогоразряда счетчика соединен с управляющим входом первого коммутатора кода,а выход второго коммутатора кода является вторым адресным выходом устройства, введены второй сдвиговый регистр, два элемента ИСКЛЮЧАЮЩЕЕ ИЛИ,два элемента И и триггер режима, вы"ход которого соединен с первым входом первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ,второй вход которого объединен с управляющим входом второго сдвиговогорегистра и подключен к выходу второгоэлемента ИСКЛЮЧАЮЩЕЕ ИЛИ, первый входкоторого соединен с выходом второгоразряда счетчика, выход третьегоразряда которого является выходомуправления записью-считыванием устройства и подключен к второму входувторого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ,вход триггера режима соединен с выходом я -гс разряда счетчика, выход-го (= 1,ю,ьФ 2,3) разряда которого подключен к входу-го ( =1,в)разряда второго сдвигового регистра,выход-го разряда которого соединен с ) -м входом второго коммутаторакода, управляющий вход которого подключен к выходу первого элемента И,первый вход которого соединен с выходом второго элемента И, второйвход которого подключен к последова-,тельному выходу первого сдвиговогорегистра, второй вход первого элемента И объединен с тактовым входомсчетчика, выход второго разряда которого является выходом режима работыустройства, последовательный выходвторого сдвигового регистра подключен к последовательному входу. второгосдвигового регистра, выход первогоэлемента ИСКЛЮЧАЮЩЕЕ ИЛИ являетсятретьим адресным выходом устройства,а первый вход второго элемента И является входом задания режима устройства. Сущностью изобретения является изменение устройства управления процессором БПФ, что позволяет реализовать более эффективный алгоритм вычиелений, Применение известного устройства позволяет реализовать безызбыточный алгоритм БПФ с прореживанием 1 1111173 1Устройство относится к вычислительной технике, в частности к устройствам, реализующим алгоритмы быстрого преобразования фурье (БПФ), иможет быть использовано в многоканаль ных системах спектрально-корреляционной обработки сигналов.Известно устройство для реализации БПФ, содержащее постоянную и оперативную память, арифметический блок 10и блок управления 11 .Недостатком этого устройства является низкое быстродействие, обусловленное несовершенным блоком управления, не позволяющим эффективноиспользовать арифметический блок.Наиболее близким по техническойсущности к изобретению является устроиство управления для процессораБПФ, содержащее счетчик, первую ивторую схемы инверсии кода, второйрегистр сдвига, блок элементов И,генератор тактовых импульсов, приэтом второй выход генератора тактовыхимпульсов является вторым выходом 25блока управления, первый выход гене-ратора тактовых импульсов подключенк входу счетчика, выход последнегоразряда которого соединен с входомвторого регистра сдвига, выход блокаэлементов И подключен к первому входувторой схемы инверсии кода, выходкоторой является вторым выходом блока управления, а выход первой схемыинверсии кода его первым выходом 23.35Это устройство позволяет реализовать безызбыточный алгоритм с прореживанием по времени и с замещением.Однако оно сложно по конструкции ине позволяет повысить быстродействиепроцессора БПФ из-эа неэффективногоиспользования арифметического блока,так как не может обрабатывать одновременно несколько массивов данных.Целью изобретения является повышение быстродействия.Поставленная цель достигаетсятем, что в устройство, управлениядля процессора быстрого преобразования Фурье, содержащее генератор тактовых импульсов, выход которого:является выходом синхронизации устройства и подключен к тактовому входусчетчика, выход а -го ( ъ = 1,ю,3,12,3)разряда которого соединен с первымвходом 1 -го (=1,е) элемента Игруппы, выход которого соединен с) -ым входом первого коммутатора кода,выход которого является первым адрес11111 В оперативную память 1, которая разбита на две половины, записываются исходные данные таким образом, что в первую половину памяти 1 данные заносятся в двоично-инверсном поряд ке, а во вторую половину " в прямом порядке. В постоянной памяти 3 записаны значения векторов поворота,3по времени, т.е. дает возможностьпроводить обработку одновременноДвух действительных массивов данных.Однако существует ряд задач, в частности задачи обнаружения и слеженияза целями в гидроакустике, когда возникает необходимость в одновременнойобработке трех и более действительных массивов данных. Известные уст, ройства не могут решить эти задачи, 1 Ов то время как предлагаемое устрой-.ство позволяет проводить одновременную обработку двух комплексных иличетырех действительных массивов данных. 15На. фиг.1 приведен граф реализованного алгоритма для 16-точечной последовательности данных (движение пографу слева направо соответствуетвыполнению алгоритма с прореживанием. 20по частоте, а движение справа налево -алгоритма с прорекиванием по времени,для первого случая номера векторовповорота указаны без скобок),нафиг.2 - блок-схема устройства управления процессора БПФ; на фиг.З -функциональная схема устройства управления.Устройство содержит оперативнуюпамять 1, арифметический блок 2, по- З 0стоянную память 3, устройство управления 4 (фиг,2), счетчик 5, сдвиговый регистр 6, группу элементов И 7,сдвиговый регистр 8, коммутатор кода9, элементы ИСКЛЮЧАЮЩЕЕ ИЛИ 10 и 11,35триггер режима 12, генератор такто -вых импулЬсов 13, коммутатор кода14, элементы И 15 и 16 (фиг.3).Процессор БПФ работает в двух режимах: обработка двух комплексныхпоследовательностей данных; обработка четырех действительных последовательностей данных.Режим работы процессора задаетсяпотенциалом на входе устройства Х 1. 45Потенциал "О" соответствует обработке двух, а потенциал "1" - четырехмассивов данных,Режим 1 - обработка двух комплексных последовательностей данных.1 50 73 4которые выбираются из памяти по кодам адресЬв, формируемых устройством управления 4, и заносятся в арифметический блок на обработку. Работу устройства поясняет граф, приведенный на фиг. 1, Над первой частью памяти 1 выполняется алгоритм БПФ с прореживанием по времени, над второй - с прореживанием по частоте.Процессор работает следующим образом.По кодам адресов, вырабатываемых устройством управления 4, из первой части памяти 1 выбираются операнды и заносятся на обработку в арифметический блок 2. Начинается обработка двух операндов. За это время устройство управления 4 формирует еще дваадреса для выбора двух операндов из второй части памяти 1, которые записываются во входные регистры арифметического блока 2. После обработки первой пары операндов устройство уп-равления 4 формирует коды адресов, по которым информация записывается во вторую часть памяти 1, а другая пара после обработки - на место выбранной информации из первой половины памяти. Затем снова формируются адреса для выбора информации из памяти 1. Так работает устройство на одной итерации БПФ. Как видно из графа, приведенного на фиг. 1, порядок выбора операндов на каждой итерации остается неизменным. Кроме того, номера векторов поворота для каждой итерации остаются одинаковыми для алгоритмов БПФ с прореживанием по времени и частоте. Объем обрабатываемых массивов определяет количество итераций, необходимых для вычисления БПФ.Режим 11 - обработка четырех действительных массивов данных.В этом случае в процессоре БПФ реализуются безызбыточные алгоритмы вычисления БПФ, когда два действительных массива данных х 0 с) и у 0 с) представляются в виде одного комплексного массива. Е 0 с):1Е 0 с) = х 0 с) + ду(3 с)(1)Затем производится преобразованиеФурье комплексных массивов данных,как было рассмотрено ранее. Отличиеработы устройства в режимах 1 и 2заключается в том, что при работе врежиме 2 для восстановления спектровисходных сигналов х(п) и у(п) наположительных частотах требуетсядополнительная итерация. Спектрывосстанавливаются согласно соотношениям:- Ке 2(п)+2(И-пЯ121 ш 2(п)-2(И-п)Д12- 1 ш 2 (и) +2 (и-п)12- Ке 2(п) -2(Ж-п)3,12 Кех(п)1 = 1 шх(п)1 = Ке У(п)Д " 1 ш У(п) =(2)0 Работу устройства 4 управления (фиг.З) поясняет таблица, на которой показано формирование команд устройством 4 управления на последней итерации восьмиточечного БПФ. Устройствс Основным устройством процессора 1БПФ, в котором закодирован алгоритм 15 вычислений, является устройство управ,ления 4.На первом выходе У 1 устройства 4 управления формируются адреса операндов, выбираемых из памяти 1. На 20 втором выходе У 2 - импульсы синхронизации арифметического блока 2. На третьем выходе УЗ - адреса операндов, выбираемых иэ постоянной памяти 3. На выходе У 4 формируются команды для режима работы арифметического блока 2, т.е. выполняется алгоритм БПФ с прореживанием по времени или частоте. Импульсы на выходе У 5,пятом выходе устройства 4 управления, определяют30 часть памяти 1, откуда выбирается информация, а на шестом выходе Уб формируются импульсы, которые разрешают запись или считывание информации из оперативной памяти 1. Коммутаторы кода 9 и 14 представляют собой набор элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, первые входы каждого элемента являются входом коммутаторов кода, а вторые входы каждого элемента объединены и 40 являются вторым входом коммутаторов . кода 14 и 9. При подаче на второй вход потенциала "0" информация проходит через коммутатор без изменения, а при потенциале 1 инвертируется. 4 В первый выход счетчика 5 объединяются выходы всех его разрядов, исключая второй и третий разряды. Выходы счетчика 5 и регистра 8 подключаются к группе элементов И 7, таким образом, что входы одного элемента И соединены с выходами равнозначных разрядовсчетчика 5 и регистра 8. 4 управления работает в двух режимах: обработка двух комплексных последовательностей данных; обработка четырех действительных последовательностей данных.При обработке двух комплексных последовательностей на вход устройства Х 1 (первый вход второго элемента И 16) подается потенциал "0". В исходном состоянии счетчик 5, регистры 6 и 8 обнулены,триггер режима 12 установлен в нулевое состояние, На всех выходах устройства 4 управления Потенциалы соответствуют уровню "0". Элемент И 16 блокируетпрохождение информации на второй вход коммутатора 14, на нем устанавливается потенциал "0", и через коммутатор 14 информация проходит без изменения. Запускается генератор 13, и начинается работа устройства 4 управления и процессора в целом.Тактовые импульсы поступают на вход счетчика 5, начинается формирование команд для выполнения реализуемого алгоритма БПФ, Информация о состоянии разрядов счетчика 5 переписывается по входу в регистр 6. Выходы второго и третьего разрядов счетчика 5 анализируются с помощью элемента 10 ИСКЛЮЧАЮЩЕЕ ИЛИ. Если состояние разрядов различное (см.таблицу), формируется импульс сдвига информации на один разряд в сторону младших разрядов. Если состояние разрядов одинаковое, то импульс сдвига не форми-. руется. Второй выход сдвигового регистра б (выход со стороны младших разрядов). соединен с входом, и при поступлении импульса сдвига с выхода элемента 10 из кода адреса 001 на выходе сдвигового регистра 6 получается код 100, который через коммутатор кода 14 поступает на выход У 1 устройства 4 управления. Одновременно на выходе УЗ формируются коды адресов информации, выбираемой из постоянной памяти 3. Группа элементов И 7 в зависимости от выполняемой итерации БПФ, определяемой состоянием разрядов сдвигового регистра 8, преобразует- информацию с первого выхода счетчика 5 в коды адресов для выбора информации из памяти 3 (см, таблицу). Выборкой информации из памяти 3 управляет младший разряд счетчика 5, подключенный к входу коммутатора 9, 11 И0 в младшем разряде счетчика соот(3) 45 7ветствует выборке значения косинуса, 1 И1 - синуса, путем инверсии кода адресов косинуса.Признак части памяти 1 для выбора и записи информации формируется с 5 помощью элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 10 и 11. "О," на выходе У 5 соответствует обращению к первой половине памяти 1, а 1" - к второй половине (см.таблицу). Третий разряд счетчика 10 5 определяет режим записи или считывания информации из оперативной памяти 1 - выход У 6 (см.таблицу, "0" соответствует считыванию информации "1" - записи). После заполнения счет чика 5 (выполнена итерация БПФ) "1" с последнего разряда счетчика 5 заносится со стороны старших разрядов в сдвиговый регистр 8, и начинается следующая итерация вычислений. Одно временно с занесением в регистр 8 "единицы" триггер 12 режима меняет свое состояние. На каждой нечетной итерации информация проходит на выход У 5 через элемент 11 без измене ний, а на четных итерациях (на выходе триггера 12 - "1") инвертируется, Необходимость менять адресацию в зависимости от итерации вычислений обусловливается алгоритмом вычисле ний (см. фиг.1). Информация на выходе У 4 соответствует различным режимам работы арифметического блока 2/Арифметический блок 2 работает в35 двух режимах. При потерциале, соответствующем уровню "О", на выходе У 4 устройства 4 управления арифметический блок реализует алгоритм с прореживанием по времени и выполняет 40 операции в соответствии с выражением а при потенциале "1" на выходе У 4реализуется алгоритм с прореживанием .по частоте и выполняются операцииХ+- Х+ 7;(4) 50 Ъ= (Х - ,)фгде Х,У - операнды на -ой итерации; Н - комплексный вектор поворота.Как видно из приведенного на фиг. 1 реализованного алгоритма, на каждой итерации вычислений порядок выбора операндов из оперативной памяти 1 остается постоянным. Постоянным остается и порядок записи информаЦии в память 1 после обработки в арифметическом блоке 2. Следует отметить, что порядок выбора информации из памяти 3 при реализации алгоритмов с прореживанием по частоте и по време-. ни совпадает.При обработке четырех действительных массивов данных на вход Х 1 подается потенциал, соответствующий уровню "1", Входные последователь-, ности данных представляются в виде (1), и начинается обработка информации по безызбыточиому алгоритму. Работа устройства 4 управления при реализации безызбыточного алгоритма отличается тем, что после завершения вычислений требуется дополнительная итерация для .восстановления спект. ров сигналов в соответствии с выражениями (2). Из приведенных соотношений видно, что для получения кода адреса операнда Х(й.-ч) необходимо проинвертировать код адреса операнда Х(о). Для этого служит коммутатор кода 14, который включается в работу лишь на дополнительной итерации. Единичный потенциал на входе Х 1 разбло- кирует второй элемент И 16 После завершения последней итерации вычислений "1" записывается в сдвиговый регистр 8, и он полностью заполняется "единицами". На выходе элемента И 16 устанавливается потенциал "1" и разрешается прохождение информации на второй вход коммутатора кода 14. При подаче на другой вход коммутатора 14 потенциала "О" на выходе У 1 формируется код адреса Х(е), а при подаче потенциала "1" - код адреса ХХ(Й-и) .Предлагаемое устройство просто по своей конструкции. Область его применения расширяется эа счет возможности одновременной обработки четырех массивов действительных данных.О 1111173 оперативнпамяти постоянной памяти 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 О 0 1 О 1 О 0 0 1 0 1 0 0 0 1 О 0 0 1 0 0 0 0 1 ф 0 0 0 1 0 О 0 1 0 Состряние раэ- Коды адреса рядов счетчика О 0 0 0 0 0 0 0 О 0 0 0 1 0.0 1 0 0 0 1 0 0 0 00 0 0 1 1 1 0 0 0 0 1 0 О. 0 0 0 О 0,1 О. 1 1 0 0 0 О 1 1 0 0 0 0 0 0 1 1 1, 0 00 1 0 0 0 0 1 0 0 1 0 1 О 0 0 1 0 1 0 1 1 1 0 1 О 1 1 О 0 0 01 0 1 1 0 1 1 0 1 0 1 1 1 0 00 0 1 1 1 1 0 1 1 1 0 0 0 00 0 1 0 0 0 10 1 1 0 0 1 0 0 1 0 1 0 0 1 11 0 Режимработыарифметическогоблока Частьоперативной памяти Режим ОП запись-считывание12 1111173 Продолжение таблицы Коды адреса оперативнойпамяти постоянной памя ти 1 О О О 1 1 О О О 1 О О О О ОО О О О О О О О О О О О О О О О У 1 УЗ У 4 У 5 Уб Состояние разрядов счетчика 1 О 1 О О О 1 О 1 О 1 О 1 1 1 О 1 О 1 1 О О 1 О 1 О 1 11 1 О 1 1 1 О О О 1 1 ОЖ1 1 О О 1 1 1 11 1 О 1 О О 1 11 1 О 1 1 1 1 1 1 1 1 О О О 1 1 1 1 1 О 1 1 1 1 1 1 1 1 О 1 1 О 1 1 1 1 1 1 1 1 Выкод блокауправления Режимработыарифметическогоблока Частьоперативной памяти Режим ОП запись-считывание1111173 г Составитель А. БаранТехред Т.Дубинчак Корректор И. И 1 ароши Редакто на Тираж 698 П ВНИИПИ Государственного комитета СС по делам изобретений и открытий 113035, Иосква, Ж, Раушская наб,М