Процессор быстрого преобразования фурье

(51) НИЕ ИЗОБРЕТЕНИЯ ория ии сигна СССР1980,ОБРАЗОВАГОСУДАРСТ 8 ЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ТОРСНОМУ СВИДЕТЕЛЬСТ(21) 413043924-24 (22) 30.06,86 (46) 15,04,88, Бюл. Мф 14 (72) Г.В.Зайцев и Н,Е.Нагулин (53) 681,32 (088,8) (56) Рабинер Л., Гоулд Б, Те применение цифровой обработк лов. И,: Мир, 1978,Авторское свидетельство У 788114, кл.С 06 Г 15/332, (54) ПРОЦЕССОР БЫСТРОГО ПРЕ НИЯ ФУРЬЕ (57) Изобретение относится к области вычислительной техники, в частности к устройствам для спектральноЯаР го анализа сигналов, представленныхв цифровой форме. Цель изобретения -повышение быстродействия, Поставленная цель достигается за счет того,что в состав процессора входит блоксинхронизации 1, счетчик итераций 2,счетчик отсчетов 3, счетчик адресовформирователь сигналов приращений 5, формирователи адреса 6мультиплексоры 8,9, регистры адреса10,11, блок постоянной памяти 12,дешифратор 13, блок памяти 14, коммутаторы 15,16, арифметический блок17, элемент НЕ 18, коммутатор 19.3 з.п. ф-лы, 4 ил,1388892 Изобретение относится к вычислительной технике, в частности к уст" ройствам для спектрального анализа сигналов представленных в цифровой Форме.Цель изобретения " повышение быстродействия устройства.На фиг.1 приведена Функциональная схема процессора быстрого преоб разования Фурье (БПФ); на Фиг,2 - Функциональная схема Формирователя сигналов приращений; на фиг.З - Функциональная схема формирователя адреса (оперативной памяти); на фиг.4 - Функциональная схема формирователя адреса постоянной памяти.Процессор (фиг.1) содержит блок 1 синхронизации , счетчик 2 итера" ции, счетчик 3 отсчетов, счетчик 4 адресов весовых коэффициентов, формирователь 5 сигналон приращений, Формирователь 6 адреса оперативной памяти, формирователь 7 адреса постоянной памяти, мультиплексор 8 ад-. 25 реса оперативной памяти, мультиплексор 9 адреса постоянной памяти, регистр 10 адреса оперативной памяти, регистр 11 адреса постоянной памяти, блок 12 постоянной памяти, дешифратор 13, блок 14 оперативной памяти, коммутаторы 15 и 16, арифметический блок 17, элемент НЕ 18 и коммутатор 19. Особенностью базовой операции алгоритма БПФ действительной последовательности по сравнению с базовой операцией стандартного алгоритма БПФ являются перестановка мнимой части первого оперенда и действительной части второго оперенда при показателе весового множителя, равном нулю, и комплексное сопряжение числа на выходе вычитателя арифметического блока 17.В режиме обработки действительного сигнала, который задается внешним управляющим сигналом типа обрабатываемой последовательности (комплексной или действительной), поступающим через блок 1 синхронизации (фиг,1) на вход дешифратора 13 и на управляющие входы коммутатора 19, мультиплекФормирователь сигналов приращений 35 (Фиг,2) образуют элементы НЕ 20 - 1- 20-К+1, дешифратор 21, коммутаторы 22-1-22-К, элементы Ы 23 -1 - 23 - Кр элементы И 24-1 - 24-К и элемент ИЛИ 25.40Формирователь адреса оперативной памяти включает элементы ИЛИ 26-1 26-К-З, сумматоры 27- 1 - 27-Кпо модулю 2 и коммутаторы 28-1 - 28-К.45Формирователь адреса постоянной памяти (Фиг,4) содержит элементы ИЛИ 29-1 - 29-К, сумматоры по модулю 30-1 - ЗО-Ки коммутаторы 31-1 31-К-З.Устройство работает следующим образом.На вход блока 1 синхронизации по." ступает внешний управляющий сигнал запуска.Запись последовательности отсчетов 55 входного сигнала в блок 14 оперативной памяти осуществляется в нормальном порядке.При обработке комплексной последовательности в блоке 14 операК тинной памяти записывается М=2 где К - целое, комплексных отсчетов сигнала, В режиме обработки действительного сигнала в блок 14 оперативной памяти вводится 2 М действительных отсчетов сигнала, причем вторая половина последовательности записывается в ячейки памяти, отведенные для мнимой части М-точечной входной последовательности, далее производятся операции над образованной таким способом М"точечной комплексной последовательностью.Вычисление спектра действительнойпоследовательности выполняется поспециальному алгоритму БПФ,В соответствии с графом алгоритмаБПФ действительной последовательности с замещением для записи промежуточных результатов вычислений требуется М ячеек памяти комплексных чисел, Такой объем памяти требуется ив режиме обработки устройством М"точечной последовательности по стандартному алгоритму БПФ с замещением,После записи всей входной информации начинается процесс ее обработки, При вычислении спектра действительной последовательности на любойитерации из блока 14 оперативной памяти считываются два оперенда, представляющие собой комплексные числа,которые поступают в арифметическийблок 1, реализующее вычисление базовой операции специального алгоритма БПФ действительной последовательности,сора 8 анр.са опс ративной памяти имультиплексора 9 адреса постояннойпамяти, для реализации базовой операции алгоритма БПФ действительной последовательности дешифратор 3 форми 5рует управлябщий сигнал, по которомуна выходы коммутаторов 15 и 16 пропускаются сигналы соответственно свторого и третьего выхода блока 14оперативной памяти, а на выход коммутатора 19 пропускается сигнал непосредственно с выхода мнимой частивторого результата арифметическогоблока 7 15Новые значения операндов с выходов арифметического блока 17 и коммутатора 19 поступают на входы блока14 операвтивной памяти,Порядок выборки входных операндовв арифметический блок 7 и записирезультатов вычислений в блок 14оперативной памяти на любой итерацииформируется с помощью счетчика 3 отсчетов и Формирователя 5 сигналов 25приращений, На произвольной 1-йитерации (1-,К) базовые операции1-1можно разбить на 2 групп так,что в каждой из групп базовые операции имеют одно и то же значение весового множителя, причем в пределаходной группы для каждой базовой операции двоичный код адреса второгооперанда получается из двоичного кодаадреса первого оперенда путем инверсии его (К 1.1-1)-го разряда, Это35свойство использовано в формирователе 5 сигналов приращений, Для формирования адресов операндов используются 3,4 К+2-1 разряды счетчика 4 О3 отсчетов, Сигнал с каждого 1-горазряда счетчика 3 отсчетов (1=З,К+2)поступает через элемент НЕ 20-1-1на один вход и непосредственно надругой вход коммутатора 22-1-245(фиг.2), Управление коммутатором221-2 осуществляется сигналом с выхода элемента И 23-1-2, на входыкоторого поступают с (К+3-1)-говыхода дешифратора 21 и сигнал первого разряда счетчика 3 отсчетов,в зависимости от состояния которогона (К+3-1)-й итерации на выход коммутатора 22-1-2 пропускается прямоеили инверсное значение 1-го разрядасчетчика 3 отсчетов. На 1-й итерации,(1-1,К) по управляющему сигналу с(К+1-1)-го элемента И 23-К+1- 1, навход которого подается сигнал 1-го разряда дешифратара 21, находящийсяна 1-и итерации в единичном состоянии, на выход (К+1-)-го коммутатора22-К+1-1 пропускается инверсное значение (К+3-1)-го разряда счетчикаотсчетов с выхода (К+1-)-гоэлемента НЕ 20-К+1-1 в тот момент,когда сигнал первого разряда счетчика 3 отсчетов 3 находится в единичном состоянии, На выходах коммутаторов 22-1 (1=Г,К) последовательно формируются адрес первого операнда принулевом состоянии сигнала 1-го разряда счетчика отсчетов и адрес второго оперенда при единичном состояниисигнала 1"го разряда счетчика отсчетов. Сигналы с выходов коммутаторов22-1 (1=1,К) переписываются в блокоперативной памяти с тактом следования операндов,Поскольку для образования адресаоперанда используются 3 (К+2)-1 разряды счетчика 3 отсчетов, а на управляющие входы коммутаторов 22-1(1=1,К) подается 1-й разряд счетчикаотсчетов, то каждая пара адресов операндов Формируется дважды: для считывания исходных операндов из блока14 оперативной памяти, а затем длязаписи результатов вычислений в блокоперативной памяти по тем жеадресам. Переход к Формированию адресов следующей группы базовых операций осуществляется путем параллельной перезаписи содержимого регистра 10 адреса оперативной памяти в счетчик 3 отсчетов па выходному сигналу количества групп базовых операций формирователя 5 сигналов приращений, С приходом после перезаписи счетного импульса счетчик 3 отсчетов начинает вырабатывать сигналы для формирования адресов операндов новой группы. Число перезаписей в счетчик 3 отсчетов определяется количеством групп базовых операций на текущей итерации, Для формирования сигнала количества групп базовых операций в формирователе 5 сигналов приращений используются элемент ИЛИ и элементы И 2 б1=1,К), на входы которых подаются сигналы от дешифратора 21, 3;(К+1)- разряды счетчика 3 отсчетов и гребенка импульсов от блока 1 синхронизации с периодом, в 2 раза большим периода следования операндов.При выполнении базовой операции алгоритма БПФ в арифметической блок 17 по соответствуюшему входу подается значение весового коэффициента из5 блока 12 постоянной памяти. В блоке 12 постоянной памяти значения весовой экспоненцальной функции записаны в нормальном порядке, Для считывания весовых коэффициентов в соответствии 10 с алгоритмом БПФ действительной последовательности используется формирователь 7 адреса постоянной памяти, являющийся комбинационной схемой и преобразующий двоичный код 155 к-з5 поступающий от счетчика 4 адресов весовых коэффициентов по Формуле 5 к 1 К-рс-1, 5 (той 2),К" р,1:о 20 30 Як- Як-з"до двоичный код нана выходе формирователя адре 25са постоянной памяти;р - номер самого старшего из ненулевых разрядов двоичногокода 5 к-г 5 к-з5 опри 5, =0 (1 щ 0,3-2) Р=О.Результирующий адрес весового коэффициента 9д д через мультиплексор 9 адреса постоянной памяти поступает на регистр 11 адреса постоянной памяти.Организация считывания по алго "ритму БНФ на 1-й итерации 2 значений весовых коэффициентов каждое из которых повторяется й/2 раз, осуществляется на основе счетчика 4 адресов весовых коэффициентов, на счетный вход которого подается сигнал перезаписи счетчика 3 отсчетов. Перед началом каждой итерации по сигналу от блока 1 синхронизации счетчик 4 адресов весовых коэффициентов обну ляется. Число состояний счетчика адреса на каждой итерации определяется числом перезаписей счетчика 3 отсчетов, что эквивалентно количеству групп базовых операций, 50Для считывания результатов вычислений из блока 14 оперативной памяти в нормальном порядке используется формирователь 6 адреса оперативной памяти, реализующий преобразование 55д кода Я , Я к9 о ступающего от формирователя 5 сигналов приращений по формуле,+ 9,+ (пюд 2), рс 1 К,1=К Кф 5,;= Режим обработки устройством комплексной входной последовательности во многом аналогичен режиму обработки действительной последовательности, поскольку реализуемые специальный алгоритм БПФ действительной последовательности и стандартный алгоритм комплексной последовательности имеют одинаковую структуру. Отличие заключается в следующем, В случае обработки комплексной последовательности при нулевом значении показателя весового коэффициента по управляющему сигналу от дешифратора 13 осуществляется коммутация второго и третьего выходов блока 14 оперативной памяти так, что на выход коммутатора 15 пропускается сигнал с третьего выхода, на выход коммутатора 16 - с второго выхода блока оперативной памяти 14, а на выход коммутатора 19 пропускается сигнал после элемента НЕ 18. За счет этих коммутаций реализуется выполнение базовой операции стандартного алгоритма БПФ комплексной последовательности. Кроме того, на вход регистра 11 адреса постоянной памят через мультиплексор 9 адреса постоянной памяти записываются состояния где р - номер самого младшего из ненулевых разрядов числа 9, фпри 90 считается р=К;5 к к-5- двоичный код навыходе формирователя адресаоперативной памяти,На этапе считывания результатов вычисления спектра сигнала на выход мультиплексора 8 адреса оперативной памяти пропускаются двоичные коды адресов спектральных отсчетов 5 к, 55, от формирователя 6 адреса оперативной памяти, которые записываются в регистр 1 О адреса оперативной памяти.При вычислении спектра 2 М-точечной действительной последовательности по специальному алгоритму БПФ устройствойвыполняет Ч, = ", 1 од Н базовых операций, а общее количество базовых операций, выполняемое известным устройстввом, составляет Ч =(1 од 8+3)-12йо1368892 счетчика 4 адресов весовых коэффициентов. При этом для организации считывания весовых коэффициентов в двоично-инверсном порядке в старшие разряды регистра 11 адреса постоян 5 ной памяти записываются значения младших разрядов счетчика 4 адресов весовых коэффициентов, Для считывания результатов вычислений спектра сигнала из блока 14 оперативной памяти используются разряды счетчика отсчетов, значения которых поступают через мультиплексор 8 адреса оперативной памяти на вход регистра 10 адреса15 оперативной памяти. Для формирования двоично-инверсного порядка следо. вания адресов также используется перестановка разрядов счетчика 3 отсчетов, 20 Формула изобретения 1,Процессор быстрого преобразования Фурье, содержащий блок памяти, блок постоянной памяти, арифметический блок, блок синхронизации, первый и второй регистры адреса, формирователь сигналов приращений, счетчик итераций и счетчик отсчетов, информационные выходы счетчика итераций и счетчика отсчетов подключены соответственно к первому и второму входам формирователя сигналов приращений, выходы первого и втоРого регистров адреса подключены к адресным входам соответственно блока памяти и блока постоянной памяти, о т л ич а ю щ и й с я тем, что, с целью повышения быстродействия, в него введены три коммутатора, элемент НЕ, дешифратор, первый и второй мультиплексоры, первый и второй формирова тели адреса и счетчик адреса, инфор,мационный выход которого подключен45 к первому информационному входу первого мультиплексора и входу первого формирователя адреса, выход которого подключен к второму информационному входу первого мультиплексора, выход которого подключен к информационному входу второго регистра адреса, тактовый вход которого подключен к первому выходу блока синхронизации, второй третий, четвертый, пятый и шестой выходы которого подключены соответственно к тактовому входу первого регистра адреса, счетному входу счетчика итерации,счетному входу счетчика отсчетов,третьему входу формирователя сигналов приращений и счетному входу счетчика адреса, вход обнуления которогосоединен с входом обнуления счетчика отсчетов и подключен к первомувыходу блока приращений, второй выход которого подключен к первомуинформационному входу второго мультиплексора, второй информационныйвход которого соединен с входомвторого формирователя адреса и подключен к информационному выходу счетчика отсчетов, установочный входкоторого подключен к выходу первогорегистра адреса, информационныйвход которого подключен к выходу второго мультиплексора, третий информационный вход которогоподключен к выходу второго формирователя адреса, седьмой выходблока синхронизации подключен кпервому управляющему входу второго мультиплексора, первому входудешифратора и управляющему входу первого коммутатора, первый информационный вход которого подключен к выходуэлемента НЕ, вход которого соединенс вторым информационным входом второго коммутатора и подключен к выходумнимой части второго операнда арифметического блока, выходы реальнойи мнимой частей первого операнда ивыход реальной части второго операнда которого подключены соответственно к входам реальной и мнимой частейпервого операнда и реальной частивторого операнда блока памяти, выходыреальной части первого операнда и мнимой части второго операнда которогоподключены к входам соответственнореальной части первого операнда имнимой части второго операнда арифметического блока, входы мнимой частипервого операнда и реальной частивторого операнда которого подключенык выходам соответственно второго итретьего коммутаторов, первые информационные входы которых подключенык выходу мнимой части первого операнда блока памяти, выход реальнойчасти второго операнда которого подключен к вторым информационным входамвторого и третьего коммутаторов,управляющие входы которых подключенык выходу дешифратора, второй вход которого соединен с входом заданиякоэффициентов арифметического блока30 и подключен к выходу блока ттостояшпэйпамяти, выходпервого коммутатораподключен к входу мпцмс й части вто- .рого операнда блока памяти вход уп 5равления записью-считгнванием которогоподключен к восьмому выходу блокасинхронизации, девятый выход которого подключен к второму управляющемувходу второго мультиплексора, а информационными гходами группы процессора являются входы реальных и мнимыхчастей первого и второго операндовблока памяти,2. Процессор по п.1, о т л и -ч а ю щ и й с я тем, что формирователь сигналов приращений содержитК+1 (К=1 од й, й - размер преобразователя) элементов НЕ, дешифратор,К коммутаторов, элемент ИЛИ, первую 20и вторую группы из К элементов И,выход 1-го (1=2, К + 1) элемента НЕподключен к первому информационномувходу (1-1) -го коммутатора, второйинформационный вход которого соединен с входом 1-го эл.емента НЕ, пер- .вым входом 1-го элемента И первойгруппы и является входом 1-го разряда второго входа Формирователя сигналов приращений, первым входомкоторого является вход дешифратора,1-й (1 = 1,К) выход которого подключен к первому входу (К+1)-го элемента И второй группы, 1-й (1=1,К) выход дешифратора подключен квторому входу (К+1)-го элемента И35первой группы, третий вход которогосоединен с (К)-м входом элементаИЛИ и годключен к выходу (К)-гоэлемента И первой группы К-й выходдешифратора подключен к первому входу первого элемента И первой группы,второй вход которого являетсятретьим входом формирователя сигналов приращений, первым выходом которого является выход элемента ИЛИ,выход первого элемента НЕ подключенк вторым входам элементов И второйгруппы, управляющий вход 1-го коммутатора подключен к выходу 1-го элемента И второй группы, а выходы коммутаторов объединены и являются вторым выходом Формирователя сигналовприращений, входом первого разрядавторого входа которого является вход55первого элемента НЕ,3. Процессор по и,1, о т л и -ч а ю щ и й с я тем, что первый формип в:гнель адреса содержит Кэлементов ИЛИ, Ксумматоров по модулю два, Ккоммутаторов, выход 1-го(1=1, К) элемента И 11 И подключен куправляюнему входу 1-го коммутатора,первый информационньн вход которогосоединен с первым входом (1+1)-госумматора по модулю два и подключенк выходу 1-го сумматора по модулюдва, первый вход 1-го (3=,К) элемента ИЛИ подключен к выходу (1+1)-гоэлемента ИЛИ, а первый вход (К)-гоэлемента ИЛИ соединен с управляющимвходом (К)-го коммутатора и является входом (К)-го разряда первого Формирователя адреса, выход(К) -го сумматора по модулю дваподключен к первому информационномувходу (К)-го коммутатора, второйвход 1-го элемента ИЛИ соединен свторым входом (1+1)-го сумматора помодулю два, вторым информационнымвходом (1+1)-го коммутатора,и является входом (1+2)-го разряда первогоформирователя адреса, входом второгоразряда которого являются соединенные между собой второй информационный вход первого коммутатора и первый вход первого сумматора по модулюдва, первьп вход которого являетсявходом первого разряда первого Формирователя адреса, выходы коммутаторов объединены с входами первого иК-го разрядов первого Формирователяадреса и являются выходом первогоФормирователя адреса,4, Процессор по п.1, о т л и -ч а ю щ и й с я тем, что,второйФормирователь адреса содержит К элементов ИЛИ, Ксумматоров по модулю два, Ккоммутаторов, причемвнход 3-га (= Г, к-Э лементаИЛИ подключен к управляющему входу (1+1)-го коммутатора, выход э-го (1=1, К) элемента ИЛИподключен к первому входу (3+1)-гоэлемента ИЛИ, а первый вход первогоэлемента ИЛИ соединен с управляющимвходом первого коммутатора и является входом К-го разряда второго формирователя адреса, входом 1-го (1=3,К) разряда которого являются соединенные между собой второй вход(К-1) -го сумматора по модулю два,второй вход (К)-го сумматора помодулю два и первый информационныйвход (К)-го коммутатора, второйинформационный вход которого подклю1388892 11чен к выходу (К)-го сумматора по модулю два, второй вход первого элемента ИЛИ соединен с вторым входом первого сумматора по модулю два, первым информационным входом первого коммутатора и является входом(К)"го разряда второго формирователя адреса, входом второго разряда которого являются соединенные между собой первый вход (К)-го сумматора по модулю два, первый вход (К)-го сумматора по модулю два и первый информационный вход (К)-го коммутатора, второй информационный вход которого подключен к выходу (К)-госумматора по модулю два, второй входкоторого являетея входом первого разряда второго формирователя адреса,а выход первого сумматора по модулюдва подключен к второму",информационному входу первого коммутатора, 10 выходы коммутаторов, входы первогои К-го разрядов второго формирователя адреса объединены и образуют выход второго формирователя адреса.1388892 Составитель Л.Барановедактор А,Огар Техред И.Ходанич Коррек тяга Заказ 158 Производственно оектна рафическое предприяти Ужг 51 Тираж 704 ВНИИПИ Государственног по делам изобретений 13035, Иосква, Ж РаушПодлиснокомитета, СССРи открытийская наб д. 4/5