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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХ СПУБЛИ 6 Р 15 33 Б 13ЗОБРЕТЕН ЕЛЬСТВ УС вычисли-. ти ко анализа ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ(56) Клан и др. Специализированный процессор для быстрого решения зада гармонического анализа. - Электроника, 1968, т.41, Р 13, с. 3-9.Авторское свидетельство СССР Р 788114, кл. С 06 Р 15/332, 1980. (54) ПРОЦЕССОР БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ(57) Изобретение относится к тельной технике и, в частнос устройствам для спектральног .сигналов, представленных в цифровой форме. Цель изобретения. - повышение быстродействия. Поставленная цельдостигается тем, что в состав устройства входит синхронизатор, два счетчика отсчетов, счетчик итераций, формирователь сигналов приращений, блокформирования дополнительного кода,три мультиплексора, регистр адресапостоянной памяти, блок постояннойпамяти,два регистра адреса,два блокапамяти, арифметический блок. Кроме этого, формирователь сигналов приращенийсодержит К+1 элементов НЕ (К=1 оц Я,И - размер преобразования), дешифратор, 2 Ккоммутаторов, 2 К элементов И, элемент КПИ и ККЯ-триггеров, а блок формирования дополнительного кода содержит Кэлементов И,К элементов НЕ, К коммутаторов,К одноразрядных сумматоров. 3 ил.124Изобретение относится к вычислительной технике, в частности к устройствам для спектрального анализа сигналов, представленных в цифровой форме.Цель изобретения - повышение быстродействия процессора быстрого преобразования Фурье.На фиг. 1 приведена функциональная схема процессора быстрого преобразования Фурье (БПФ); на фиг. 2 функциональная схема формирователя сигналов приращений; на фиг. 3 функциональная схема блока формирования дополнительнЬго кода.Устройство содержит синхронизатор 1, счетчик 2 отсчетов, счетчик 3 итераций, счетчик 4 отсчетов, формирователь 5 сигналов приращений, блок 6 формирования дополнительного кода, мультиплексоры 7 и 8, регистр 9 адреса постоянной памяти, блок 10 постоянной памяти, регистры 11 и 12 адреса (оперативной памяти), блоки 13 и 14 (оперативной) памяти, мультиплексор 15, арифметический блок 16. Формирователь 5 сигналов приращений (фиг. 2) содержит элементы НЕ (17-1) - (17-К+1), дешифратор 18, коммутаторы (19-1)-(19-К), элементы И (20-1)-(20 - К), элементы И (2 1-1)- (21-К), элемент ИЛИ 22, КБ-триггеры (23-1)-(23-К), коммутаторы (24-1) -(24-К).Блок 6 формирования дополнительного кода (фиг. 3) содержит Кэлементов И (25-1)-(25-К), К элементов НЕ (26-1)-(26-К), К коммутаторов (27-1)-(27-К), Кодноразрядных сумматоров (28-1)-(28-К) .Устройство работает следующим образом.На вход синхронизатора 1 поступает внешний сигнал запуска. Запись последовательности отсчетов входного сигнала производится в один из блоков оперативной памяти, например в блок 14. В И/2 ячеек памяти комплексных чисел блока 14 оперативной памяти зак+писывается 2 И=2 отсчетов действительного сигнала так, что первая половина входной последовательности записывается в ячейки памяти действительной части, а вторая половина - в ячейки памяти мнимой части комплексных чисел. После записи входной информации начинается процесс ее обработки. При891 2вычислении на первой итерации алгоритма БПФ из блока 14 оперативнойпамяти считываются два операнда,представляющие собой комплексные числа, и записываются в арифметическийблок 16 через мультиплексор 15, пропускающий на первой итерации сигналыот блока 14 оперативной памяти. Арифметический блок 16 реализует вычисле О ние базовой операции алгоритма БПФдействительной последовательности,особенностью которой по сравнению сбазовой операцией стандартного алгоритма БПФ является перестановка мни ной части первого операнда и действительной части второго операнда припоказателе весового множителя, равном нулю, и комплексное сопряжениечисла на выходе вычитателя арифметищ ческого блока 16.После выполнения базовой операциирезультирующие значения операндов свыходов арифметического блока 16 поступают на входы приема информации д блока 13 оперативной памяти.На второй итерации считываниеоперандов производится из блока 13оперативной памяти, а запись результатов вычислений арифметического блоо ка 16 - в блок 14 оперативной памяти.Чередование режимов записи-считывания блоков 13 и 14 оперативной памяти выполняется и на последующихитерациях. При этом коммутация адресов операндов для записи или считывания блоков 13 и 14 оперативной памятивыполняется мультиплексорами 7 и 8,Порядок выборки входных операндовна арифметический блок 16 и записирезультатов вычислений в блоки 13 и14 оперативной памяти на любой итерации формируется с помощью счетчиков2 и 4 отсчетов, счетчика 3 итераций,формирователя 5 сигналов приращенийи блока 6 формирования дополнительного кода, управление которыми производится по сигналам от синхронизатора 1.Формирование адресов для считывания операндов в арифметический блок16 осуществляется следующим образом,Из алгоритма БПФ действительнойпоследовательности следует, что напроизвольной -й итерации (х = 1,2,К) базовые операции можно раз 55 бить на группы так, что в каждой изгрупп базовые операции имеют одно и,то же значение весового множителя.Причем для каждой базовой операции в3 12 ч 7 пределах одной группы при считывании операндов в арифметический блок 16 двоичный код адреса второго операнда получается из двоичного кода адреса первого операнда путем инверсии (К+1-)-го разряда двоичного кода адреса первого операнда. Это свойство использовано в формирователе 5 сигналов приращений. Для формирования адресов операндов используются 2, 1 О 3(К+1) разряды счетчика 2 отсчетов. Сигнал с каждого -го разряда счетчика 2 отсчетов (1=2,3К+1) поступает непосредственно на первый вход и через элемент НЕ 17-з-на вто рой вход коммутатора 191. Управ,ление коммутатором 19-1-1 осуществляется сигналом с выхода элемента И 20-1-1, на входы которого поступают сигналы с (К+2-х) - 20го выхода дешифратора 18 и с первого разряда счетчика 2 отсчетов, в зависимости от состояния которого на (К+2-а)-й итерации на выход коммутатора 19-1-1 пропускается прямое или 25 инверсное значение сигнала -го разряда счетчика 2 отсчетов. Таким образом, на произвольной 3-Й итерации (3 = 1, 2К) по управляющему сигналу с (К+1-1)-го элемента И30 20-К+1-1, на вход которого подается сигнал 3-го разряда дешифратора 18, находящийся в единичном состоянии, на выход (К+1-3)-го коммутатора (19-К+1-1) сначала пропускается сиг 35 нал (К+2-3)-го разряда счетчика 2 отсчетов, когда сигнал первого разряда счетчика 2 отсчетов находится в нулевом состоянии, а затем - инверсное. значение (К+2-1)-го разряда40 счетчика отсчетов с выхода (К+1-3)- го элемента НЕ 17-К+1-3 в тот мо-. мент, когда сигнал первого разряда счетчика 2 отсчетов находится в еди- ниЧИОМ состоянии При этОм последО 45 вательно формируются адреса и .Оного и второго операндов на выходах коммутаторов 19-х (д = 1, 2 К) .Сигналы с выходов коммутаторов19-1 (1 = 1, 2,, К) пропуска-.ются в зависимости от режимовработы блоков 13 и 14 оперативной памяти на выход одного из мультиплексоров 7 и 8 и записываются в соответствующий регистр адреса опера тивной памяти с тактом следованияоперандов.Переход к формированию адресов следующей группы базовых операций. 891 4осуществляется путем параллельной перезаписи сигналов на выходах коммутаторов 19- (=1,2К) в соответствующие разряды счетчика 2 отсчетов по выходному сигналу перезаписи формирователя сигналов приращений.С приходом после перезаписи счетного импульса счетчик 2 отсчетов начинает вырабатывать сигналы для формирования адресов операндов новой группы. Число перезаписей в счетчик 2 отсчетов определяется количеством групп базовых операций на текущей итерации. Для формирования сигнала перезаписи в формирователе 5 сигналов приращений используется элемент ИЛИ 22 и элементы И 21-1. (д=1,2, ,К), на входы которых подаются сигналы от дешифратора 18, (2-К)-е разряды счетчика отсчетов 2 и гребенка импульсов от синхронизатора 1. Формирование адресов для записи результатов вычисления арифметического блока 16 в один из блоков опера" тинной памяти выполняется на основе преобразования счетчика 4 отсчетов. В соответствии с графом алгоритма БПФ в качестве адреса первого результата можно использовать непосредственно сигналы разрядов счетчика отсчетов. Адрес второго результата на первых двух итерациях получается пу" тем инверсии старшего разряда двоичного кода первого операнда. На х-Й итерации (1=3,4К), адрес второго результата формируется из адреса первого результата следующим образом.В двоичном коде первого результата БББ где Б, = О или 1 (1,2К), инвертируется старший разряд Би выполняется вычислениедополнительного кода В 8 к-а 8 к-+ разрядов Б ,Б .,Б;,1 . Получаемый после преобразования двоичный код Б8, я. Б; Б, где Б - инверсное значение старшего разряда Б , и является адресом второго результата. Формирование адресов записи результатов арифметического блока выполняется в блоке 6 формиро-вания дополнительного кода. Последовательность формирования адресов управляется сигналом первого разряда счетчика 4 отсчетов, от селектированного соответствующим сигналом номера итерации с выхода дешифратора На произвольной итерации при нулевом состоянии сигнала 1-го разряда счет 1247891чика отсчета на выход блока 6 формирования дополнительного кода пропуска. ются сигналы 2, 3(К+ 1)-го разрядов счетчика 4 отсчетов без изменений и используются в качестве адреса.пер. вого результата. Когда сигнал 1-го разряда счетчика 4 отсчетов принимает единичное состояние, выполняется преобразование сигналов 2, 3 О (К+1)-го разрядов счетчика 4 отсчетов описанным выше способом. При этом на выход К-го коммутатора 27-К пропускается инверсное значение сигнала К-го разряда счетчика 4 отсчетов, а на первые входы одноразрядных сумматоров 28-К, 28-К28-К-х+1 пропуска-; ются инверсные значения КдК-+ +1)-го разрядов счетчика 4 отсчетов для вычисления дополнительного кода. 20 В соответствии с операцией дополнительного кода на второй вход сумматора 28-К-+1 в этот момент подается "1", для формирования которой используется сигнал с 1-го разряда счетчика 25 отсчетов, отселектированный сигналом номера итерации с выхода дешифратора 18. Полученный после преобразования двоичный код на выходе блока 6 формирования дополнительного кода Зп представляет собой адрес записи второго результата арифметического блока16 в один из блоков оперативной памяти.Для выполнения базовой операцииалгоритма БПФ в арифметический блок 16 по соответствующему входу подается значение весового коэффициента из блока 10 постоянной памяти, в котором запИсаны значения комплексной экспоненты в порядке возрастания показателя степени. Дпя организации считывания в соответствии с графом алгоритма БПФ на произвольной -й итерации 2 значений весовых коэффициен.-1 45тов каждое из.которых повторяется О/2 раз, используются ЙЯ-триггеры 23-1 Д 1=1,2К) и коммутаторы 24- (1=1,2К) формирователя 8 сигналов приращений. По началу первой итерации от управляющего сигнала с 1-го выхода дешифратора 18 все ЙЗ-триггеры устанавливаются в единичное состояние. При этом все коммутаторы 24- (=1,2,К), на управляющие входы которых подаются сиг палы с выходов соответствующих ВЯ- триггеров 23- (х=1,2К), про. пускают на выход "О" и из блока 10 постоянной памяти считывается для выполнения базовых операций только одно значение весового множителя с. нулевым показателем степени. На вто рой итерации переводится в нулевое состояние КБ-триггер 23-1 по сигналу второй итерации с 2-го выхода дешифратора 18 и на выход коммутатора 24-Кпропускается сигнал К-го разряда счетчика 4 отсчетов, который используется в качестве старшего разряда кода адреса весового коэффициента.При этом из блока постоянной памяти считываются два значения весового коэффициента с показателями степени 0 и И/2. На третьей итерации по сигналу с 3-го .выхода, дешифратора в нулевое состояние переводится КЯ- триггер 23-2 и считываются значения весового коэффициента с показателями степени О, Н/4, И/2, ЗИ/4 и т.д, На К-й итерации все КБ-триггеры 23-д Д.=1,2К) находятся в нулевом состоянии, и при выполнении базовых операций используются соответственно все М/2 значений весового коэффициента в порядке возрастания показателя степени.Результаты вычислений спектравходного сигнала формируются на К-йитерации на выходе арифметическогоблока.Формула изобретенияПроцессор быстрого преобразования Фурье, содержащий синхронизатор, первый счетчик отсчетов, счетчик итераций, формирователь сигналов приращений, первый регистр адреса, регистр адреса постоянной памяти, блок постоянной памяти, первый блок памяти, арифметический блок, блок формирования дополнительного кода, причем вход задания коэффициента арифметического блока подключен к выходу блока постоянной памяти, вход которого подключен к выходу регистра адреса постоянной памяти, информационные входы первой и второй групп формирователя сигналов приращений подключены к выходам разрядов группы соответственно первого счетчика отсчетов и счетчика итераций, адресный вход первого блока памяти подключен к выходупервого регистра адреса, о т л ич а ю щ и й с я тем, что, с целью повышения быстродействия, в него вве дены второй счетчик отсчетов, три мультиплексора, второй блок памяти и .второй регистр адреса, причем выход результата арифметического блока подключен к информационным входам первого и второго блоков памяти, входы чтения записи которых подключены к О первому выходу синхронизатора, выходь первого и второго блоков памяти подключены соответственно к первому и второму информационным входам первого мультиплексора, выход 15 которого подключен к информационному входу арифметического блока, управля,ющие входы первого, второго и третьего мультиплексоров подключены к второму. выходу синхронизатора, входы разрядов группы регистра адреса постоянной памяти соединены с выходами первой группы формирователя сигналов приращений, выходы второй группы которого подключены к информационным 25 входам первого счетчика отсчетов, к информационным входам первых групп второго и третьего мультиплексоров, выход третьего мультиплексора подключен к информационному входу второго регистра адреса, выход которого подключен к адресному входу второго блока памяти, выходы третьей группы формирователя сигналов приращений подключены к входам первой группы блока формирования дополнительного кода, выходы группы которого подключены к информационным входам вторых групп третьего и второго мультиплексоров, выход второго мультиплексора подключен к информационному входу первого40 регистра адреса, выход сигнала перезаписи формирователя сигналов приращений подключен к входу разрешения записи первого счетчика отсчетов, входы обнуления и счетные входы пер 45 вого и второго счетчиков отсчетов и счетчика итераций подключены соответственно к первому и второму выходам синхронизатора, выходы разрядов группы счетчика итераций подключенык входам второй группы блока формирования дополнительного кода и к информационным входам третьей группы формирователя сигналов приращений, управляющий вход которого подключен к тре тьему выходу синхронизатора, причем формирователь сигналовприращений содержит К+1 элементов НЕ (К=1 ояМ,И - размер преобразования), 2 К элементов И, 2 Ккоммутаторов, К КБ-триггеров, дешифратор и элементИЛИ, причем входы элементов НЕ группы являются информационными входамипервой группы формирователя сигналовприращений, информационными входамивторой группы которого являются вхо"ды группы дешифратора, первые инфоомационные входы(К+)-х (д=1, К) коммутаторов являются информационнымивходами третьей группы формирователя сигналов приращений, выход 1-гоЦ=2, К+1) элемента НЕ подключен кпервому информационному входу (1-1)го коммутатора, второй информационный вход которого объединен с входом1-го элемента НЕ, выходы ш-х (ш=,К)коммутаторов являются выходами второйгруппы формирователя сигналов приращений, управляющий вход ш-го коммутатора подключен к выходу ш-го элемен"та И, первые входы элементов И объединены и подключены к выходу первогоэлемента НЕ, а второй вход ш-го элемента И подключен к (К+д-ш)-му выходу дешифратора первый вход (К+1)-гоэлемента И является управляющимвходом формирователя сигналов прира"щений, а второй вход подключен к К-мувыходу дешифратора, второй вход (К++Б)-го элемента И (Б=2, К)подключенк (К+1-Б)-му выходу дешифратора, третий вход подключен к выходу Б-гоэлемента НЕ, выход (К+)-го элементаИ подключен к -му входу элемента ИЛИи первому входу (К1)-го элементаИ, выход 2 К-го элемента И подключенк К-му входу элемента ИЛИ, выход которого является выходом сигнала перезаписи формирователя сигналов приращений, К-входы КБ-триггеров объединены и подключены к первому выходудешифратора, Б-вход -го КБ-триггера подключен к (+1)-му выходу дешифратора, а выход - к управляющимвходам (2 К-)-го коммутатора, инфор;мационные входы первой группы (К+)-хкоммутаторов объединены и являются.входом задания логического "О" процессора, выходы (К+)-х коммутаторовявляются выходами первой группы формирователей сигналов приращений, авыходы КБ-триггеров являются выходамитретьей группы формирователя сигналовприращений, причем блок формированиядополнительного кода содержит К элементов И, К элементов НЕ, К ком9 12 мутаторов и Кодноразрядных сумматоров, при этом первые входы -х (=1 К) элементов И являются входами первЬй группы блока формирования дополнительного кода, входы 1-х (1=1, К) элементов НЕ и управляющий вход К-го коммутатора являются выходами второй группы блока формирования дополнительного кода, вторые входы элементов И и управляющий вход К"го коммутатора объединены, выход -го элемента НЕ подключен к первому информационному входу 1-го коммутатора, второй информационный вход ко) 47891 1 Оторого объединен с входом 1-го элемента НЕ, выход -го элемента И подключен к управляющему входу (К-д)-го коммутатора и первому входу (К-д)-го 5 одноразрядного сумматора, второй входкоторого подключен к выходу (К-)-го коммутатора выход переноса а-го (щ = 1, К) одноразрядного сумматора подключен к входу переноса (в+1)- го одноразрядного сумматора, выход К-го коммутатора и выходы одноразрядных сумматоров являются выходами группы блока формирования долв тельного кода.1247891 Ото От Составитель А. Барано Техред М.Ходанич амборская Коррект едактор И. Рыбченко Подписное Заказ 4128 5 венно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 о Тираж 671 ВНИИПИ Государственного ко по делам изобретений и 113035, Москва, Ж, Рауш