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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИ ЧЕСНИХРЕСПУБЛИК 4 С 06 Р 15/3 И ской кибернетики ыхов,и Н,Н88.8) А, Золотои,Легонин ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИ ПИСАНИЕ ИЗОБРЕА ВТОРСКОМУ СВИДЕТЕЛЬСТВ 21) 421421 7/24-2422) 25,03,8746) 23.09.88, Бюл71) Институт технН БССР72) Р.Х. Сад) Изобретение относится к с ализированным устройствам цифровойобработки сигналов, использующихалгоритм быстрого преобразованияФурье, и может быть применено в различных областях техники, использующих спектральный и корреляционныйанализ. Цель изобретения. - повьппениебыстродействия. Поставленная цельдостигается за счет того, что в состав устройства входят блок 1 вычисления коэфФициентов фурье, блокперестановки 2, блок памяти 3, блокадресации 4, 6 ил.Изобретение относится к специализированным вычислительным устройствам цифровой обработки сигналов, использующих алгоритм быстрого пр .образо 5 вания Фурье (БПФ), и может быть использовано в различных областях техники, использующих спектральный и корреляционный анализЦель изобретения - повышение бы стродействия процессора за счет сокращения числа операций на перестановку выходного массива, при сокра щении объема рабочей памяти в двараза, 15На фиг. 1 представлена функцио нальная схема устройства," на фиг.2 - функциональная схема блока перестановки; на фиг. 3 - временные диаграммы функционирования узла управ ления и формирования сигнала Я/ВЭ; на фиг. 4 - функциональная схема узла управления на фиг. 5 - функциональная схема коммутатора; на фиг, 6 функциональная схема блока адресации. 25Процессор (фиг,1) содержит блок , 1 вычисления коэффициентов Фурье,блок 2 перестановки, блок 3 памяти,блок 4 адресации.Блок 2 перестановки (фиг.2) со ,держит регистры 5 и 6, мультиплек- сор 7.Узел управления (фиг,4) содержит одновибратор 8, триггеры 9-12, элемент ИЛИ 13 и одновибратор 14Блок 4 адресации (фиг.5) содержит35узел 15 управления, мультиплексор 16, счетчик 17, мультиплексор 18, регистр 19, коммутатор 20, компаратор 21,. элементы ИЛИ 22 и 23, элементы И 24 и 25, сдвигатель 26, одновибратор 27, мультиплексор 28, элемент И 29, одновибратор 30, элемент ИЛИ 31, триггер 32, реверсивный счетчик 33, элемент И 34, элемент НЕ 35.45Блок 4 адресации работает следующим образом.По включению питания все регистры и счетчики устанавливаются в "0", Триггер 9 узла 15 устанавливается в "1", которая блокирует триггеры 10- 12 и устанавливает их в "0", "0" на выходе узла 15 обеспечивает подключение выходов триггера 32 и счетчика 17 через мультиплексор 28 к адресно 55 иой шине блока 4 адресации. 1 на выходе узла 15 обеспечивает прохождение тактовых импульсов через элементы И 24 и 25, что обусловливает изменение адреса, (формируемого триггером 32 и счетчиком 17) по каждому такту и генерирование сигналов записи в блок 3 памяти (на выходе узла и входе блока 4 адресации присутствуют "1"). "1" на управляющем входе мультиплексора 7 блока 2 перестановки обеспечивает соединение выхода про-. цессора быстрого преобразования фурье с информационным входом блока 3 памяти. Тем самым обеспечен режим последовательной записи в блок 3 памяти коэффициентов Фурье.При передаче последнего коэффици-. ента в блок 3 памяти блок 1 формирует сигнал конца преобразования, который поступает на вход блок 4 адресации и запускает одновибратор 14, устанавливающий триггер 9 в "0". Одиночный импульс с выхода одновибратора 14 поступает также на К-входы триггера 32 и счетчиков 17 и 33 и устанавливает их в "0", "0" на входах элементов ИЛИ, 22 и 23 разрешает управление прохождением тактовых импульсов через элементы И 24 и 25 от компаратора, а также управление муль" типлексором 16 и триггером 32 от мультиплексора 18. Кроме того, по импульсу с выхода одновибратора 14 в регистр 19 записывается код, управляющий размерностью преобразования. Максимальная размерность определяется разрядностью счетчика 17 плюс единица (поскольку триггер 32 формирует младший разряд адресного кода).,При этом для размерности И=2 (и)-й разряд счетчика 17 подключается через элемент И 34 и к Б-входу триггера 32 и управляющему входу мультиплексора 16, а сдвигатель 26 обеспечивает сдвиг исходного кода Х на 1 разрядов в сторону младших раз. рядов. Пусть И=2 (=10), Рассмотрим процедуру перестановки двух операнцов, которая выполняется за четыре такта, По импульсу с выхода элемента ИЛИ 13 счетчики 17 и 33 и триггер 32 устанавливаются в "0". На выходе ЫХ компаратора устанавливается "1", а на выходе ы с Х компаратора "0", тем самым следующий тактовый импульс поступает на тактовый вход триггера 1 узла 15, При этом управляющие сигналы для блока 3 не сформированы, а содержимое счетчика (триггер 32 - счетчик 17) увеличивается на единицу. При этом на выходах компаратора 21состояние изменяется на противоположное, т.е, разрешается прохождение последующих тактовых импульсовна тактовый вход узла 15, на выходах которого формируются сигналы согласно временной диаграмме (фиг,3),Высоким уровнем сигнала на выходеузла к адресному входу блока 3 подключается модифицированный код м.0001 и иэ ячейки памяти с этимадресом считывается первый операнди записывается в регистр 5 блока 2перестановки,Далее по второму такту низкимуровнем сигнала на вькоде узла иадресному входу через мультиплексор28 подключается исходный код Х=100и в регистр 5 записывается второйоперанд, при этом первый операнд переписывается в регистр 6 блока 2 перестановки и поступает на информационный вход блока 3 памяти, По следующему такту формируется сигналИВ./В 2 записи и первый операнд записывается по адресу исходного кодаХ. Далее высоким уровнем на выходеузла 15 по второму адресу записывается второй операнд,Затем перепадом из "0" в "1" навыходе узла 15 содержимое счетчика(триггер 32 - счетчик 17) увеличивается на единицу и процедура перестановки следующей пары операндов повторяется аналогично. При блокировкеузла 15 (содержимое счетчика триггер32 - счетчик 17 увеличивается на единицу) перестановка не осуществляется.Указанная процедура формирования адресов перестановки осуществляетсявплоть до адреса Б/2-1, Далее приадресе, равном М/2, "1" старшего разряда модифицированного кода поступает через мультиплексор 18 на управляющий вход мультиплексора 16 и Б-входтриггера 32, При этом на выходе триггера 32 устанавливается "1", а тактовые импульсы через мультиплексор16 поступают на тактовый вход счетчика 17, Далее модифицированный кодформируется с шагом два, т,е. в диапазоне адресов от Н/2 до Ианализируется только И/4 нечетных адресов.Реверсивный счетчик 33 включенпараллельно счетчику 17, на управляющий вход счетчика 33 поступаетсигнал с вькода мультиплексора 18,При "0" счетчик 33 работает в режиме суммирования, а при адресе М/2 ивыше в режиме вычитания, Таким образом, при Формировании счетчиком 17 (И)-го адреса счетчик 33 обнуляется и на его выходе переноса формируется сигнал окончания процедуры перестановок, который поступает на вход узла синхронизации и запускает одно- вибратор 8, который устанавливает триггер 9 в "1", а счетчики 17 и 33 и триггер 32 обнуляется. Тем самым блок 4 адресации вновь готов к работе. При подаче на вход блока 4 адресации низкого потенциала запрещено формирование сигнала записи и реализуется режим считывания иэ блока 3.Процессор быстрого преобразования Фурье работает следующим образом.Исследуемый. процесс поступает на вход блока 1 вычисления коэффициентов фурье, на выходе которого формируются спектральные коэффициенты в обратном двоичном порядке, поступающие последовательно через мультиплексор 7 блока 2 перестановки в блок 3. При этом блок 4 адресации формирует по тактам последовательные адреса и управляющие сигналы для бло-. ка 3. После формирования последнего коэффициента Ср из блока 1 в блок 4 адресации поступает сигнал конца преобразования и блок 4 адресации переводится в режим переупорядочения, при этом выход регистра 6 подключен через мультиплексор 7 к входу блока 3. В результате описанных процедур перестановки через 3/4 И циклов в блоке 3 содержатся данные, упорядоченные в естественном порядке. 1 О 15 20 25 30 35 Формула изобретения 40.тем, что, с целью повышения быстродействия, информационный выход и выход окончания вычислений блока выПроцессор быстрого преобразования1Фурье, содержащий блок вычислениякоэффициентов Фурье, блок перестановки, блок памяти и блок адресации, 45тактовый выход которого подключен квходу управления перестановкой блока перестановки, выход которого подключен к информационному входу блокапамяти, вькод которого является выходом процессора, информационнымвходом которого является информацион 1ный вход блока вычисления коэффициентов Фурье, тактовый вход которого является первым тактовым входомпроцессора, о т л и ч а ю щ и й с ячисления коэффициентов Фурье подключены соответственно к первому информационному входу блока перестановки и входу условий блока адреса 5 ции, адресный выход, выход управления записью-считыванием и выход выборки которого подключены соответственно к адресному входу, входу управления записью-считыванием и вхо ду выборки блока памяти, вьмод которого подключен к второму информационному входу блока перестановки, тактовый вход которого является вто-рым тактовым входом процессора, тре тьим и четвертым тактовыми входами которого являются соответственнопервый и второй тактовые входы блока , адресации, вход задания размера пре-образования которого является вхо Одом задания размера преобразования процессора, причем блок перестановкисодержит первый и второй регистр и ,мультиплексор, первый информационный , вход которого подключен к выходу 2 б ,первого регистра, информационный вход которого подключен к выходу второго ,регистра, вход записи которого соединен с входом записи первого регистра ,и является тактовым входом блока перестановки, первым и вторым информа" ,ционными входами и входом управления перестановкой которого являются соответственно второй информационный вход мультиплексора, информационный вход второго регистра и управляющий ;вход мультиплексора, выход которого является выходом блока перестановки, при этом блок адресации содержит узел управления, коммутатор, сдвигатель, компаратор, три мультиплексора, два одновибратора, счетчик, реверсивный счетчик, триггер, регистр, три элемента ИЛИ, четыре элемента И и элемент НЕ, выход которого подключен к первому входу первого элемента И, выход которого подключен к управляющим входам реверсивного счетчика и первого мультиплексора и Б-входу триггера, выход которого подключен к первому информационному входу первого мультиплексора, выход которого подключен к счетным входам счетчика и реверсивного счетчика, установочные входы которых соединены с входом записи регистра, К-входом триггера и подключены к первому выходу узла управления, второй выход которого подключен к первому входу первого элемента ИЛИ, выход которого подключенк второму информационному входу первого мультиплексора и тактовому входу триггера, выход переноса реверсивного счетчика подключен к входу останова узла управления, третий выходкоторого подключен к управляющемувходу второго мультиплексора, первыйинформационный вход которого соединен с первым входом компаратора иподключен к вьмоду сдвигателя, информационный вход которого подключен квыходу коммутатора, информационныйвыход счетчика и выход триггера через шину данных подключены к второмуинформационному входувторого мультиплексора,информационному входукоммутатора, второму входукомпаратора иинформационному входутретьего мультиплексора, выход которого подключен к второму входу нНеравноп первого элемента И, вьмоды "Равно" компаратора подключены к первым входам соответственно второго и третьего элементов ИЛИ,выходы которых подключены к первымвходам соответственно второго и третьего элементов И, выходы второгоэлемента И подключены к второму входу первого элемента ИЛИ, .выход третьего элементаИ подключен к первому входу четвертого элемента И и тактовому вхо"ду узла управления, четвертый выход кото-рого подключен к второмувходу четвертого элемента И, выход которого подключенк входу первого одновибратора, вьмодрегистра подключен к упраыяющим входам третьего мультиплексора и сдвигателя, а пятый выход узла управленияподключен к входу элемента НЕ, вторым входам второго и третьего элементов ИЛИ и является тактовым выходомблока адресации, выходом выбора которого является выход второго одновибратора, вход которого соединен с вторым входом второго и третьего элементов И и является первым тактовым входом блока адресации, выходом управления записью-считыванием и адреснымвыходом которого являются соответственно выходы первого одновибратораи второго мультиплексора, а входомзадания размера преобразования, вторым тактовым входом и входом запускабпока адресации являются соответственно информационный вход регистра,третий вход четвертого элемента Ии вход запуска узла управления, приэтом узел управления содержит четыре14257 триггера, два одновибратора и элемент ИЛИ, причем прямой выход первого триггера подключен к тактовому входу второго триггера, инверсный5 выход которого подключен к П-входу первого триггера, инверсный выход первого триггера подключен к Э-входу первого триггера и тактовому входу третьего триггера, инверсный. выход которого подключен к Э-входу третьего триггера, К-вход которого соединен с К-входом первого триггера и подключен к выходу четвертого триггера, Я-вход которого соединен с пер вым входом элемента ИЛИ и подключен к выходу первого одновибратора, а вы 098ход второго одновибратора подключен к К-входу четвертого триггера и второму входу элемента ИЛИ, выход которого является первым выходом узла управления, вторым, третьим, четвертым и пятым выходами которого являются соответственно прямой выход второго триггера, инверсный выход третьего триггера, инверсный выход второго триггера и выход четвертого триггера, входом останова, тактовым входом и входом запуска узла управления являются соответственно вход первого одновибратора, тактовый вход первого триггера и вход второго одновибратора.1425709 0425 ЧХб 7 Составитель А. Техред М,Дидык ов Редактор М. Бланар тор М, Васильев о каз 4773/4 н ИИПИ 4/5 3035 венно-полиграфическое предприятие, г. Ужгород, ул. Проектная,Прои Тираж 704 Государственног елам изобретений сква, Ж, Рауш