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

.ЯО 1277 А б Г 15/33 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ ИСАНИЕ ИЗОБРЕТЕНИЯ А ВТОРСКОМУ СВИДЕТЕЛЬСТВ 3903425/24-2429,05.851512,86. Бюл. В 46В.П.Карасев и В.А.Шаньги681,32(088,8)Патент США У 3680105,06 Р 15/332, 1974.торское свидетельство СС9027, кл. С 06 Р 15/332,(21) (22) (46) (72) (53) (56) кл, САв 9 11 Р БЫСТРОГО ПРЕОБРАЗОВА ЬР(54) ПРОЦЕ НИЯ ФУРЬЕ (57) Изобртельной тевычисленияобратногоразличных сивов, в тИзобретенидля постро тение относится к вычисли нике и предназначено для коэ 3 ициентов прямого и реобразований Фурье при линах обрабатываемых масм числе вычисления сверто может быть использовано ния цифровых систем обработки в различных областях техники,Цель изобретения - расширение Функциональных возможностей устройства засчет вычисления прямого и обратногопреобразований Фурье при различныхдлинах обрабатываемых массивов. Поставленная цель достигается за счеттого, что процессор имеет в своем составе арифметический блок, три блокапамяти, блок постоянной памяти, пятьмультиплексоров, три регистра адреса,блок Формирования команд, сдвиговыйрегистр, блок Ьормирования адресов,счетчик отсчетов, блок синхронизации.сдвигатель, счетчик и реверсивныйсчетчик, Причем блок Аормирования команд содержит узел постоянной памяти,счетчик, мультиплексор, пять элементов Й и три элемента ИЛИ. 1 з.п. ф-лы,5 ил.Изобретение относится к вычислительной технике, предназначено длявычисления коэффициентов прямого иобратного, преобразований Фурье, в томчисле вычисления сверток, и может 5быть использовано для построения цифровых систем обработки в различныхобластях техники.Цель изобретения - расширение функциональных возможностей устройства 10за счет выполнения, помимо прямого,и обратного преобразований Фурье приразличных длинах обрабатыгаемых массивов,На фиг.1 представлена функциональная схема процессора; на фиг.2 - функциональная схема блока формированиякаманд; на фиг,З - схема блока формирования адресов, на фиг.4 - схема блока синхронизации; на фиг,5 - диаграмма преобразования адресов.Процессор быстрого преобразованияФурье (БПФ) содержит мультиплексор 1,блоки 2 и 3 (оперативной) памяти,мультиплексор 4, арифметический блок255, регистры 6 и 7 адреса, блок 8 постоянной памяти, мультиплексоры 9 и10, регистр 11 адреса (постоянной памяти), блок 12 формирования команд,(фиг,2) вырабатывает необходимые управляюшие сигналы для блоков процессора, обеспечивая выполнения заданной программы работы. Формирователькоманд содержит узел 22 постояннойпамяти, счетчик 23 мультиплексор 24,элементы И 25-29, элементы ИПИ 30-31,Блок 14 формирования адресов(фиг.З) служит для выработки адресовоперандов и весовых коэффициентов,необходимых для выполнения алгоритмаБПФ, Структурная схема блока определяется основанием алгоритма БПФ,уровнем совмещения операций в процессоре, На фиг,З приведена схема блокадля алгоритмов БПФ с основанием 2 сзамещением. Формирователь адресов содержит мультиплексор 32, поразрядныедвухоходовые элементы ИЛИ 33, счетчики адресов операндов 34 и адресов ко"эффициентов 35,Блок 16 синхронизации (фиг.4) содержит генератор 36 тактовых импульсов, распределитель 37 импульсов,элемент ИЛИ 38, элемент И 39 и ждущиймультивибратор 40,Рассмотрим работу процессора напримере обработки массива И = 8 привычислении свертки, Как известно, длявычисления свертки необходимо выполнить следующие операции: вычислениеспектра входной реализации, перемножение спектров входного и эталонногосигналов, обратное преобразованиеФурье от результат йеремножения.В исходном состоянии иа второйвход процессора поступает код, соответствующий длине массива И = 8, натретий вход - код, соответствующийначальному адресу программы работыпроцессора (в данном случае вычислению программы свертки), н блоке 17памяти хранятся спектры эталонныхсигналов. По команде "Пуск", поступающей на вход процессора, блок синхронизации вырабатывает сигнал "Уст, 0",который поступает на все блоки процессора и блокирует выработку синхросигналов распредепителя 37 на время,определяемое длитепьностью импульсаждущего мультивибратора 40. По заднему фронту этого сигнала в счетчик 23заносится начальный адрес провраммыработы процессора, а в младший разрядитерационного сдвигового регистра за-.носится 1На выходе ПЗУ формируются сигналы,обеспечивающие выполнение операций иввода массива отсчетов. При этом через мультиплексор 1 первый вход процессора подключается к входу блока 2памяти, Выход счетчика 20 через первый.вход мультиплексора 19 подключается на вход сцвигателя 18, причем1все разряды.двоичноинвертированы. Науправляющий вход сдигателя 18 с выхода формирователя команд поступает код,обеспечивающий сдвиг кода адреса вмладшие разряды, при этом в старших.разрядах - нули, /иэграмма, поясняющая эти операции,.приведена на фиг.5,Из диаграммы видно, что при И = 8 навыходе сдвигателя остаются толькотри разряда счетчика, при И = 16 - четыре разряда и т.д при этом они двоичноинвертированы В общем случаесдвигатель должен обеспечивать сдвигкода на число разрядов М 1 о 8 И, гдеИ - количество разрядов счетчика ад 12773реса, Код с выхода сдвигателя 18 через открытый вход мультиплексора 9поступает на адресный регистр 6 и далее - на блок 2 памяти, Мультиплексор24 контролирует старшие разряды счет 5чика 15, при этом при И = 8 на выходмультиплексора выводится 4-й разряд(при И = 16 - пятый и т.д,),После окончания импульса "Уст. Ораспределитель импульсов 37 начинает 10вырабатывать синхросигналы.За время выполнения базовой операции вырабатывается 22 синхросигнала,При операции ввода массива за времявыполнения базовой операции обеспечивается запись одного отсчета, иввод всего массива завершается за двеитерации. Подсчет числа базовых операций осуществляется счетчиком 15.На выходе блока 16 формируется сумма 20двух синхросигналов СИ 11 и СИ 21,которая поступает на счетный входсчетчика 15. Первый разряд четвертоговыхода при операции ввода находитсяв состоянии "1" и разрешает прохождение синхросигналов через элемент И 27на счетный вход счетчика 20 адресовввода. После ввода четырех отсчетов(И/2) четвертый разряд счетчика 15устанавливается в состояние "1". Через мультиплексор 24 и элемент И 25(на второй вхоц элемента И 25 поступает высокий уровень с восьмого выхода ПЗУ) на счетный вход счетчика 23поступает сигнал "+1". Состояниесчетчика увеличивается на единицу.Кроме того, сигнал с выхода мультиплексора 24 через элемент ИЛИ 30 поступает на вход установки в нульсчетчика 15. Начинает выполняться 10вторая итерация операции ввода. Состояние выходов ПЗУ сохраняется. Послеввода остальных четырех отсчетов всчетчик 23 добавляется единица, Навыходах ПЗУ формируются сигналы, обе спечивающие выполнение операции прямого преобразования Фурье. При этомна первом выходе блока 12 формирования команд устанавливается сигнал"0", и выход блока 5 через второйвход мультиплексора 1 подключаетсяна вход блока 2 памяти, На четвертомвыходе блока формирования команд устанавливается код 001, при котороммультиплексор 9 подключает на входрегистра 6 адреса выход формирователя14 адресов. На девятом выходе ПЗУ устанавливается код 01, настраивающийблок на выполнение операции БПФ. В процессоре реализован алгоритм БПФ с основанием 2 с двоичной инверсией отсчетов на входе с замещением, На одиннадцатом выходе ПЗУ устанавлива-, ется уровень "1", при этом выход мультиплексора 24 через элемент И 26 подключается к тактовому входу регистра 13 сдвига.Формирователь адресов работает следующим образом (фиг.3). На второй вход блока поступает код с итерационного регистра 13 сдвига, На первый вход поступает младший разряд счетчика 15 отсчетов, который управляет переключением мультиплексора 32. При нулевом значении разряда на выход блока пропускается код счетчика 34, на котором формируются первые адреса базовой операции. При единичном значении разряда на выход пропускается выход схем ИЛИ 33, на которых образуются вторые адреса операндов базовой операции, На входы счетчиков .34 и 35 поступает синхроимпульс, который через схемы входной логики изменяет состояние разрядов счетчиковУправление порядком счета осуществляется сдвиговым регистром 13 и состоит в том, что выход разряда итерационного регистра, который находится в состоянии "1", блокирует соответствующий разряд счетчика, запрещая прохождение единиц переноса в этот разряд с предыдущего и разрешая прохождение этих единиц переноса непосредственно в следующий за блокируемым разряд, Адрес второго операнда пары формируется на выходах поразрядньгх элементов ИЛИ 33, на одни входы которых поступает код счетчика 34, а на другие входы - код с итерационного сдвигового регистра 13 с "1" в соответствующем разряде. Код адреса весового коэффициента формируется на счетчике 35, причем за счет входной логики счетные импульсы поступают на тот разряд счетчика, на который приходит "1" со сдвигового регистра 13. При появлении "1" в четвертом разряде счетчика 15 добавляется "1" в счетчик 23 и проходит сигнал регистра 13 сдвига, Начинается выпол-нение второй итерации. После выполнения третьей итерации на выходах ПЗУ устанавливаются коды, при которых выполняется операция перемножения комплексных массивов. При выполнении этой операции спектр сигнала находит- 1277135ся в блоке 2 памяти, эталонные спектры - в блоке 17 памяти и поступают ка второй и первый входы арифметического блока 5 соответственно, Результаты перемножения записываются в блок 3 памяти. Адреса считывания спектра сигнала образуются на счетчике 20 и через второй вход мультиплексора 9 (определяется кодом на четвертом выходе блока 12 Формирования команд) и регистр б поступают на адресный вход блока 2 памяти. Адреса считывания эталонного сигнала формируются на счетчике 20.Адреса записи результатов для блока 3 памяти образуются следующим образом, Известно, что для выполнения операции обратного преобразования Фурье достаточно перед ее выполнением кроизвестипереупаковку массива следующим образом: Исходный массив: 0,1,2,3 М,ИПереупаковочныймассив:О, И, И, 3, 2, 1 Кроме того, учитывая, что в процессоре используется граф с двоичной инверсией отсчетов на входе, необходимо произвести двоичную инверсию отсчетов.С целью экономии времени такая переадресация массива производится при выполнении операции перемножения комплексных массивов при Формировании, адресов записи в блок 3 памяти. При выполнении этой операции сигнал с выхода счетчика 2 1 через открытый второй вход мультиплексора 19 проходит через сдвигатель и далее через первый вход ьтльтиплексора 10 и регистр 7 поступает на адресный вход блока 3 памяти. Счетчик 21 работает при этом на вычитание. На вычитающий вход счетччка 21 поступает сикхросигналы с выхода элемента И 28, ка первый вход которого поступает разрешающий сигнал с третьего выхода ПЗУ, При передаче кода счетчика на сдвигатель выполняется двоичная инверсия разрядов, так же, как и при выполнении операции ввода, осуществляется сдвиг кода на соответствующее количество разрядов. За время базовой операции выполняется перемножение одной пары отсчетов, и вся операция длится две итерации. После выполнения операции перемножения комплексных мсассивов на счетчике 23 устанавливается код по которому иэ ПЗУ считываются коды команды, обеспечивающие выполнение операции обратного преобразования Фурье.При этом выход блока 12 Формирования ,адресов через вход мультиплексора 10 5 и регистр 7 подключается к адресномувходу блока 3 памяти, Выход последнего через вход мультиплексора подключается к второму вхсду арифметического блока 5. В остальном операция выполняется аналогично операции прямого преобразовакия Фурьс. Результаты вычислений находятся в блоке 3 памяти.После выполнения операции обратного преобразования Фурье на выходе ПЗУ формируются коды команд, обеспечивающие выполнение операций вывода.При этой операции адреса считывания для блока 3 памяти Формируются на счетчике 21, который в этом случае работает на сложение, Адреса поступают на вход блока 3 памяти через вход мультиплексора 10 и регистр 7, Операция вывода длится две итерации, Далее по программе выполняется операция перемножения комплексных массивов, причем на седьмом выходе блока 12 формирования адресов появляется код 001, и при выполнении операции перемножения из блока 17 памяти считывается второй эталонный спектр, Операции обратного преобразования Фурье и вывода выполняются так же, как и в первом цикле. При соответствующем увеличении объема блока 17 35 памяти и удлинении программы можнопроизводить обработку с различным числом копий. Ввод эталонных сигналов в блок 17 памяти при необходимости можно выполнять одновременно с обработкой сигнала, например с выполнением операций вычисления преобразования Фурье. При появлении на счетчике 23 кода 0011 на выходе формирователя ко-. манд устанавливается сигнал "0", который поступает на входы элементов И 39, ИЛИ 38 и блокирует работу распределителя 37 импульсов, Процессор пе реходит в режим ожидания до появления следующего запускающего импульса 50"Пуск". Работа процессора при этом повторяется аналогично описанной выше. Формула из обретения 1, Процессор быстрого преобразования Фурье, содержащий арифметический блок, первый и второй блоки памяти, адресные входь 1 которых подключены к7 1277 выходам соответственно первого и второго регистров адреса, вход задания коэАфициентов арифметического блока подключен к информационному выходу блока постоянной памяти, адресный вход которого подключен к выходу третьего регистра адреса, инАормациончый вход которого подключен к первому,выходу блока Формирования адресов, первый вход которого подключен к выходу 1 О первого разряда счетчика отсчетов, счетный вход которого подключен к первому выходу блока синхронизации, вход запуска которого является выходом запуска процессора, информационный выход ариАметического блока соединен с инйормационным входом второго блока памяти и первым инАормационным входом первого мультиплексора, выход которого подключен к.инАормационному входу первого блока памяти, информа- ционный выход которого подключен к первому инАормационному входу второго мультиплексора, выход которого подключен к информационному входу ариА метического блока, информационный выход второго блока памяти подключен к второму информационному входу второго мультиплексора и является информационным выходом процессора, инАормаци- уо онным входом которого является второй инАормационный вход первого мультиплексора, второй выход Формирования адресов подключен к первым информационным входам третьего и четвертого мультиплексоров, выходы которых подключены к инАормационным входам соответственно первого и второго регистров адреса, информационный выход сдвигового регистра подключен к второму входу блока Формирования адресов, о т л и т а ю щ и й с я тем, что, с целью расширения функциональных возможностей за счет выполнения, помимо прямого, и обратного преобра. - 45 зования фурье при различных длинах обрабатываемых массивов., в .него введены сдвигатель, счетчик, реверсивный счетчик, пятый мультиплексор, третий блок памяти и блок Аормирования команд, первый, второй, третий, четвертый и пятый выходы блока Формирования "команд подключены к управляющим входам соответственно первого, второго, четвертого, третьего и пятого мульти плексоров, шестой выход блока формирования команд подключен к управляющему входу сдвигателя, а седьмой, восьмой и девятый выходы блока форми 135 Ярования команд подключены к счетномувходу счетчика, суммирующему и вычнтающему входам реверсивного счетчика,информационный выход счетчика отсчетов подключен к первому входу блокаформирования команд, десятый выходкоторого подключен к входу остановаблока синхронизации, одиннадцатый идвенадцатый выходы блока формированиякоманд подключены к установочным входам счетчика отсчетов и сдвиговогорегистра, инАормационный выход реверсивного счетчика подключен к вторыминформационным входам четвертого ипятого мультиплексоров, выходы разрядов пятого мультиплексора подключены к входам соответствующих разрядов сдвигателя, инАормационный выходкоторого подключен к третьим инАормационным входам третьего и четвертого мультиплексоров, инАормационныйвыход счетчика подключен к первомуинформационному входу пятого мультиплексора, к второму инАормационномувходу третьего мультиплексора и первому адресному входу третьего блокапамяти, второй адресный вход которого подключен к тринадцатому выходублока Формирования команд, четыр адцатый выходкоторого подключен квходу синхронизации арифметическогоблока и управляющим входам блокапостоянной памяти и третьего блокапамяти, инАормационный вход которогоявляется входом задания параметров процессора, управляющие входы первого и второго блоков памяти подключены к пятнадцатому выходу блока Аормирования команд, шестнадцатый выход которого подключен к тактовому входу сдвигового регистра, второй и третий входы блока Аормирования команд являются соответственно входом задания размера преобразования и входом задания режима работы процессора.2, Процессор по п.1, о т л и ч аю щ и й с я тем, что блок Формирования команд содержит узел постоянной памяти, счетчик, мультиплексор, пять элементов И, причем первым входом блока является инАормационный вход счетчика, установочный вход которого объединен с первыми входами первого и второго элементов ИЛИ и является установочным входом блока, счетный вход счетчика объединен с вторым входом второго элемента ИЛИ и первым входом второго элемента И и подключен к выходу первого элемента1 7713И, первый и второй информационные входы мультиплексора являются соответственно вторым и третьим входами блока, выход мультиплексора подключен к первому входу первого элемента И, вто - 5 рой вход которого подключен к выходу восьмого разряда узла постоянной памяти, информационный выход счетчика подключен к адресному входу узла постоянной памяти, выходы разрядов с 1 О первого по десятый которого являются соответственно первым, вторым, третьим, четвертым, шестым, пятым, тринадцатым, десятым, четырнадцатым и пятнадцатым выходами блока, выход 15 второго элемента ИЛИ является один" надцатым выходом блока, выход одиннадцатого разряда узла постоянной памяти подключен к первому входу второго элемента И, выход которого являет ся шестнадцатым выходом блока, выход двенадцатого разряда узла постояннон памяти подключен к второму входу первого элемента ИЛИ, вихол которого является двенадцатым выходом блока, выход четвертого разряда узла постоянной памяти подключен к первому входу третьего элемента И, выход которого является седьмым выходом блока, выход третьего разряда узла постоянной памяти подключен к первому входу четвертого элемента И, выход которого является девятым выходом блока, выход седьмого разряда узла постоянной памяти подключен к первому выходу пятого элемента И, выход которого является восьмым выходом блока, вторые входы третьего, четвертого и пятого элементов И и третий вход первого элемента И объединены и являются тактовым входом блока..у о/7 д оставитель А.Барановехред М.Ходанич 1(орректор А Обру Редакто бченко Подписное Заказ 6669 тная,город, ул. роизводственно-полиграфическое предприятие ТГосударствен делам изобрет Москва; И,ВНИИПИ11303июлуасиРь а юИСИ 11 СФРГ Уела 0 й 7 Д сг о(з Ко . Ы аж 671го комитета ССий и открытийаушская наб.,