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

(71) Специальное констнологическое бюро с опством при Белорусскомном университете им. В(прототип). л укторско-техтным производ осударствен- И, Ленина тельство ССС/332, 1981.льство СССР /332, 1979 ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И О 1 НРЫТИЙ(54)(57) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИБЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ ПОСЛЕДОВАТЕЛЬНОСТИ С НУЛЕВЫМИ ЭЛЕМЕНТАМИ,содержащее блок оперативной памяти,арифметический блок, блок памятикоэффициентов, блок управления, причем вход операндов арифметическогоблока соединен с информационным выходом блока оперативной памяти, входкоэффициентов арифметического блокасоединен с информационным выходомблокапамяти коэффициентов, информационный выход арифметического блокаявляется информационным выходом устройства, о т л и ч а ю щ е е с ятем, что, с целью повышения быстродействия, в него введены счетчик занесения, триггер, первая и втораягруппы коммутаторов, причем информационный выход арифметического блокаподключен к первым информационнымвходам коммутаторов первой группы,вторые информационные входы которых.являются информационными входами устройства, управляющие входы коммута 801119025 торов первой и второй групп объединены и подключены к выходу триггера,параллельный выход счетчика занесенияподключен к первым информационнымвходам коммутаторов второй группы,первый установочный вход триггерасоединен с последовательным выходомсчетчика занесения, выходы коммутаторов первой группы подключены кинформационному входу блока оперативной памяти, адресный вход которогоподключен к выходам коммутатороввторой группы, причем блок управлениясодержит коммутатор, регистр сдвига,счетчик, первый и второй элементы И,элемент ИЛИ, сумматор, регистр хранения, причем вход сброса и тактовыйвход счетчика соединены соответственно с выходом триггера и тактовымвходом счетчика занесения, тактовыйвход которого является тактовым вхо"дом устройства, вход сброса счетчикасоединен с установочным входом регистра сдвига, выход первого разряда.счетчика подключен к тактовомувходу регистра сдвига, выходы разрядов, кроме второго разряда, счетчикаподключены к информационному входукоммутатора, управляющий вход которого соединен с выходами от первогодо (ь)"го разрядов регистра сдвига,выход второго разряда счетчика подключен к первому входу второго элемента И и тактовому входу регистрахранения, выходы разрядов, кромевторого разряда, счетчика соединенысоответственно со входами элементаИЛИ, выход которого подключен к первому входу первого элемента И, второвход которого соединен с инверснымвыходом (о+1)-го. разряда регистра11 ЬОЬ лительного блока. двоичного счетчика, выход второго элемента И соединен с входом второго 35разряда счетчика, выход первого эле,мента И соединен с входом регистрасдвига, первый выход регистра сдвига соединен с управляющим входом блока 40 коммутаторов, второй выход (инверс. сдвига, инверсный выход первого эле" мента И подключен ко второму входу второго элемента И, выход которогб подключен ко второму установочному входу, триггера, инверсные выходыот второго дб (в)-го разрядов. регистра сдвига подключены к первому входу сумматора, выход которого соединен с информационным входом регистра хранения, информационный выход кото 1Изобретение относится к вычислительной технике и может быть использовано в устройствах, .предназначенных для. оперативного спектральногои гармонического анализа.Известно устройство для реализации быстрого преобразования Фурье(БПФ) последовательности с нулевымиэлементами, содержащее входной блокпамяти, блок управления, распределительный блок, блок оперативной памяти, арифметический блок, блок па мяти коэффициентов, Входом устройстваслужит информационный вход входногоблока памяти, выход которого соединен с первым информационным входомблока оперативной памяти, выход которого подключен к первому информационному входу арифметического блока,второй вход которого соединен с выходом блока памяти коэффициентов,выход арифметического блока являетсявыходом устройства, выходы блока улравления соединены со входами синхронизации входного блока памяти, распределительного блока, блока оперативной памяти, арифметического блока, блока памяти коэффициентов 11.Во входной блок памяти записывается М ненулевых точек входной М -точечной последовательносТи, Распределительный блок переупорядочивает их и формирует новую й -точечную последовательность путем повторения ненулевых точек последовательности, Элементы полученной последовательности записываются в блок оперативной памяти и затем осуществляется БПФ. Вычисления начинаются с (и-ю+1) итерации, т.е. для выполнения М-точечного 10 15 20 25 30 рого подключен ко вторым информационным входам коммутаторов второй группы и соединен со вторым входом сумма"тора, выход н -го разряда регистрасдвига подключен к управляющему входу блока памяти коэффициентов, информационный выход коммутатора подключен к управляющим входам арифметического блока и блока оперативнойпамяти. 2БПФ необходимо ("в) итераций (щ =1 офМ, ь = 1 оы, где М - длительностьреализации; М - длительность, ненулевой части реализации).Не остатком данного устройства дявляются большие аппаратурно-временные затраты за счет введения входного блока оперативной памяти и распредеНаиболее близким к изобретению является устройство, содержащее блок оперативной памяти, блок памяти коэффициентов, арифметический блок, блок управления, причем первый, второй и третий выходы блока управления соединены соответственно с входами блока оперативной памяти, блока памяти коэффициентов и арифметического блока, первая и вторая группы входом, арифметического блокасоединены соответственно с группами выходов блока оперативной памяти и блока памяти коэффициентов, блок управления содержит двоичный сумматор, регистр сдвига, блок коммутаторов, сумматор, элементы И, регистр хранения, причем первый выход счетчика соединен с первым входом первого элемента И, второй вход которого соединен с вторым входом второго элемента И и яв.ляется первым входом блока управления, первый вход второго элемента Исоединен с выходом первого разряда11190зный) регистра сдвига соединен спервым входом сумматора, информационный вход блока коммутаторов соединенс вторым выходом счетчика, второйвход регистра хранения соединен стретьим выходом счетчика, выход сумматора соединен с первым входом ре- .гистра хранения, выход которого является первым выходом блока управления и соединен с вторым входом суммаОтора, первым входом блока управленияявляется вход двоичного счетчика,вторым выходом блока управления является выход блока коммутаторов 2 1,Однако в известном устройстве неиспользуются возможности для сокращения времени вычислений при преобразовании последовательностей, содержащихчасть нулевых элементов,Цель изобретения - повышениебыстродействия устройства за счетустранения избыточности при выполнении БПФ последовательности с нулевымиэлементами.Поставленная цель достигаетсятем, что в устройство, содержащееблок оперативной памяти, арифметический блок; блок памяти коэффициентов,блок управления, причем вход операндоварифметического блока соединен сЭО. информационным выходом блока опера.тивной памяти, вход коэффициентоварифметического блока соединен синформационным выходом блока памятикоэффициентов, информационный выходарифметического блока является информационным выходом устройства,введены счетчик занесения, триггер,первая и вторая группы коммутаторов,причем информационный выход арифметического блока подключен к первым40информационным входам коммутаторовпервой группы, вторые информационныевходы которых являются информационными входами устройства, управляющиевходы коммутаторов первой и второйгруппы объединены и подключены квыходу триггера, параллельный выходсчетчика занесения подключен к первыминформационным входам коммутатороввторой группы, первый установочный 5вход триггера соединен с последовательным выходом счетчика занесения,выходы коммутаторов первой группыподключены,к информационному входублока оперативной памяти, адресный 55вход которого подключен к выходамкоммутаторов второй группы, причемблок управления содержит коммутатор,ч 4 регистр сдвига, счетчик, первый ивторой элементы И, элемент ИЛИ, сумматор, регистр хранения, причемвход сброса и тактовый вход счетчикасоединены соответственно с выходом триггера и тактовым входом счетчиказанесения, тактовый вход которого является тактовым входом устройства, вход сброса счетчика соединен с установочным входом регистра сдвига, выход первого разряда счетчика подключен к тактовому входу регистра сдвига, выход разрядов, кроме второго разряда, счетчика подключены к инфор,мационному входу коммутатора, управляющий вход которого соединен с выходами от первого до и -1-го разрядоврегистра сдвига, выход второго разряда счетчика подключен к первому входу второго элемента И и тактовому входу регистра хранения, выходы разрядов,кроме второго разряда, счетчика соединены соответственно с входами элемента ИЛИ, выход которого подключенк первому входу первого элемента И,второй вход которого соединен с инверсным выходом в+1-го разряда регистра сдвига, инверсный выход первогоэлемента И подключен к второму входувторого элемента И, выход которогоподключен к второму установочному входу триггера, инверсные выходы отвторого до-1-го разрядов регистрасдвига подключены к первому входусумматора, выход которого соединенс информационным входом регистрахранения, информационный выход которого подключен к вторым информационным входам коммутаторов второй группыи соединен с вторым входом сумматора,выход о-го разряда регистра сдвигаподключен к управляющему входу блокапамяти коэффициентов, информационныйвыход коммутатора подключен к управляющим входам арифметического блокаи блока оперативной памяти.На Фиг.1 изображена структурнаясхема устройства; на Фиг,2 - Функцио,нальная схема блока управления; наФиг.З " граф процедуры шестнадцатиточечного БПФ с четырьмя ненулевымиточками, реализуемого данным устройствомУстройство для реализации БПФпоследовательности с нулевыми элементами (Фиг.1) содержит блок 1 оперативной памяти, арифметическийблок 2, блок 3 памяти коэффициентов,блок 4 управления,в -разрядный счет.025 . 6логическим потенциалам "ф и "0 ц,Выход первого разряда двоичного счетчика 1 1 подключен к первому информационному входу первого селектора и квторым информационным входам селекторов коммутатора 9, выход (+1)-горазряда, начиная с третьего разряда -к первому информационному входу 1-госелектора, выход (1+2)-го разряда -к третьему информационному входу-го селектора а выход третьегоразряда двоичного счетчика 11 подключен к третьему информационномувходу первого селектора.Выход второго разряда счетчика 11соединен с входом второго элементаИ 13, другой вход которого соединенс инверсным выходом первого элементаИ 12, Вход первого элемента И 12соединен с инверсным выходом (в+1)-горазряда регистра 1 О сдвига, а второго - с выходом элемента ИЛИ 14,ю-разрядный элемент ИЛИ 14 соединен с двоичным счетчиком 11 так,что в разрядов элемента ИЛИ соединенысоответственно с разрядами счетчика11 с первого до (п+1)-го, исключая,второй разряд.Выход о -го разряда регистра 10сдвига формирует сигнал обнулениятриггера 6, выход которого подключенк установочному входу регистра 10сдвига и к входу сброса двоичногосчетчика 11.Первый вход сумматора 15 соединенс инверсным четвертым выходом регист.- ра 10 сдвига так, что 1"й разрядсумматора подключается кинверсномувыходу (и-.+1) разряда (начиная совторого разряда) регистра сдвига.В данном устройстве реализованалгоритм БПФ с замещением и прореживанием по времени.Устройство работает следующим образом.В исходном состоянии щ-разрядныйсчетчик,5 занесения и триггер 6 обнулены. В группу коммутаторов 8 накоммутаторы с первого до (ь -т) поданы потенциалы "0". Выходы разрядовсчетчика 5 занесения подключены кпервым информационным входам коммутаторов 8 в двоично-инверсном порядкеследующим образом. Выход младшегоразряда счетчика 5 занесения соединенс входом старшего коммутатора группыкоммутаторов 8, выход старшего разряда счетчика 5 - с (ь -в+1) коммутатором группы коммутаторов 8,1119чик 5 занесения, триггер 6, группукоммутаторов (на два канала) 7,группу коммутаторов (на два канала)8, входы устройства Х 1, Х 2 и выходустройства Ч 1.5Параллельный выход в-разрядного(двоичного) счетчика 5 занесениясоединен с первыми информационнымивходами коммутаторов 8 таким образом,что 1-й разряд счетчика занесениясоединен с (ь+ 1) разрядом коммутаторов, вторые информационные входыкоммутаторов 8 соединены с четвертымвходом блока управления 4, Первыеинформационные входы коммутаторов 7являются информационным входом устройства Я 1, второй информационныйвход коммутаторов 7 соединен с выходом арифметического блока 2.Первая и вторая группы коммутаторовуправляются выходом триггера 6, пер-.вый установочный вход которого соединен с последовательным выходом счетчика 5 занесения, а второй установоч"ный вход - с третьим выходом блока4 управления.Арифметический блок 2 выполненаналогично прототипу и содержит сумматор и умножитель, выполняющийоперацию комплексного умножителя.Блок 4 управления (фиг.2) содержито-разрядный коммутатор 9, и -разрядныйрегистр 10 сдвига, (и+1)-разрядный(двоичный) счетчик 11, элементы И 12и 13, элемент ИЛИ 14, (п)-разрядный сумматор 15,-(д)-разрядныйрегистр 16 хранения, Входы блока Я 2и ХЗ управления, выходы блока 12, УЗ,У 4 и У 5.Первый выход в -разрядного регистра4010 сдвига представляет собой выходп-го разряда, второй выход - параллельный выход разрядов с первого до(о"1)-го, третий выход - инверсныйвыход (в+1)-го разряда, четвертый45выход регистра 10 сдвига - инверсныйпараллельный выход разрядов со второго до (п)-го.о -разрядный коммутатор 9 выполненна базе селекторов на три канала,каждый из которых имеет два управ 50ляющих входа, Первый управляющийвход 1-го селектора подключен к выходу (+1)-го разряда регистра 10 сдвига, второй управляющий вход - к выходу 1-горазряда, причем первыйуправляющий вход первого селектора ивторой управляющий вход и-го селектора подключены, соответственно, к11190На вход устройства У 1 через группу коммутаторов 7 поступает исходнаяпоследовательность и записывается вблок 1 оперативной памяти в двоичноинверсном порядке по адресам, которые формируются на выходе группыкоммутаторов 8 следующим образом.По входу устройства Х 2 на тактовый вход счетчика 5 занесения поступают тактовые импульсы, по которым О в-разрядный счетчик 5 занесения формирует напервом выходе последовательные коды, поступающие на первыеинформационные входы группы коммутаторов 8, на выходах которых формируются адреса занесения операндов.После занесения операндов сигналом перехода из "1" в "0" на выходестаршего разряда счетчика 5 занесения триггер 6 устанавливается в единичное состояние. Потенциал "1" с выхода триггера 6 переключает группыкоммутаторов У и 8 в режим выполненияБПФ. При этом к информационному входублока оперативной памяти 1 подключается выход ариФметического блока2, к адресному входу блока 1 оперативной памяти подключается четвертыйвыход блока 4 управления, формирующийадреса считывания и записи операндов блока 1 оперативной памяти, и в блок4 управления с выхода триггера 6 поступает сигнал разрешения выполнения итераций БПФ.Выполнение итерации БПФ заключа 35 ется в последовательном выполнении в арифметическом блоке 2 элементарных операций вида Я т ВФ, где Д и Ь - операнды, извлекаемые из блока 1 оперативной памяти; % в . экспоненциальный множитель, извлекаемый иэ блока 3 памяти коэффициентов.Процесс выполнения БПФ в предлагаемом устройстве для случая И = 16,М = 4 представлен графом БПФ на фиг 3 45 где Ео, Г,- элементы исходной последовательности; фо ф, ф спектральные коэффициенты; Ю ,% ,.о , Ф - экспоненциальные множители.Каждая элементарная операция БПФ выполняется за четыре такта. Считывание из блока 1 оперативной памяти первого операнда (в оперативную память исходная последовательность записывается в двоично-инверсном порядке, считывание из памяти производится в прямом порядке) и считывание экспоненциального множите 25 8 ля из блока 3 памяти коэффициентов и занесение их а арифметический блок 2,Выполнение операции умножения первого операнда на экспоненциальныь множитель и извлечение из блока 1 оперативной памяти второго операнда,Выполнение операции вычитания из второго операнда произведения первого операнда и экспоненциального множителя и занесение разности в блок 1 оперативной памяти на место извлеченного ранее первого операнда.Выполнение операции сложения второго операнда и произведения первого операнда и экспоненциального множителя и занесение суммы в блок 1 оператканой памяти на иестофиэвлеченного ранее второго операнда.В данном устройстве для выполнения БПФ последовательности с нулевыми элементами необходимо произвести (ь -ю) итераций. Выполнение БПФ начинается с (и-в+1) итерации, и в данном устройстве она является первой итерацией БПФ. При выполнении элементарных опера" ций первой итерации БПФ блокируется считывание из блока 1 оперативной памяти и занесение в арифметический блок 2 тех операндов, чьи адреса соответствуют нулевым точкам.Элементарная операция в этом случае выполняется с новым экспоненциальным множителем над операндами,уже занесенными в арифметическийблок 2. Блокировка считывания из блока 1 оперативной памяти и занесения в ариф метический блок 2 осуществляется вторым выходом У 4. блока управления(фиг.2).При появлении сигнала переходастаршего разряда счетчика 11 иэ "1" в "0" в регистре 10 сдвига происходит сдвиг и начинается выполнение следующей итерации БПФ.После выполнения (ь-ю) итераций БПФ блок управления 4 обнуляет триг" ,гер 6 и переводит устройство в исходное состояние,Адреса считывания и занесения операндов иэ блока 1 оперативной памяти формируются в блоке 4 управленияПри выполнении К -ой итерации блок 4 управления работает следующим образом.В исходном состоянии двоичный счетчик 11 обнулен, в регистре 10 сдвига во все разряды с первого до1119025 9К-го занесены "1", а в остальные от (К+1) до (и+1) - "0". Селекторы управляются таким образом, что при подаче на их управляющие входы двух сигналов "0" на выход передается ин формация .с первого информационного входа, при подаче сигналов "0" и " 1" на выход передается информация второго информационного зхода и при подаче на управляющие входы сигналов 1 б "1", информация передается с третьего информационного входа. На вход двоичного счетчика 11 подаются тактовые импульсы. Коммутатор 15 9, управляемый параллельным выходом регистра 10 сдвига, формирует из выходных сигналов счетчика адреса операндов, необходимых для выполнения элементарных операций БПФ. Одно п временно сумматор 15 и регистр 16 хранения формируют адреса экспоненциальных множителей, извлекаемых из блока 3 памяти коэффициентов.Управление занесением в арифме тический блок 2 и извлечение из блока 1 оперативной памяти организуется следующим образом. При появлении сигнала в (в+1) разряде регистра 10 сдвига и сигнала "0" в чей+1) разрядах двоичного счетчика 11 на инверсном выходе первого элемента И 12 появляется потенциал "1", который поступает на вход второго элемента И 13, на другой вход которого поступает сигнал с выхода второго разряда двоичного счетчика 11. Сигнал управления считыванием из блока 1 оперативной памяти и занесением в арифметический блок 2 формируется на выходе второго элемента И 13. Сигнал управления меняется на противоположный, как только появляется потенциал "1" на любом из входов элемента ИЛИ 14, либо появляется потенциал "О" на выходе (в+1)- го разряда регистра 1 О сдвига,Предлагаемое устройство позволяет повысить быстродействие за счет существенного сокращения числа итераций, необходимых для выполнения БПф последовательности, содержащей 1 нулевые элементы. По сравнению с поототипом время вычисления последовательности при М = 1024 и М 128 совращается на 30%.(;Р 4 Ь Ри иалУа аказ 7455737одписное Патент",ул. Проектнаа, 4