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

(56) 1. Авторское свидетельство СССРР 590750, кл. С 06 Г 15/332, 1978.2. Авторское свидетельство СССРР 788114, кл. С 06 Г 15/32, 1980(прототип),(54)(57) ПРОЦЕССОР БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащий арифметический блок, первый и второй блоки.памяти, адресные входы которых подключены к информационным выходамсоответственно первого и второго регистров адреса, вход задания коэффициентов арифметического блока подключен к информационному выходу блокапостоянной памяти, адресный вход которого подключен к информационномувыходу третьего регистра адреса, информационный вход которого подключенк первому выходу формирователя сигналов приращения,первый вход которого подключен к информационному выходу счетчика отсчетов, выход переноса которого подключен к тактовомувходу сдвигового регистра, выходыразрядов первой группы которого подключены поразрядно к второму входуформирователя сигналов приращений,тактовый вход которого подключен кпервому выходу блока синхронизации,второй, третий и четвертый выходыкоторого подключены соответственнок счетному входу счетчика отсчетов,тактовому входу арифметического блока и управляющим входам первого и второго блоков памяти, выход переноса сдвигового регистра подключен к входу останова блока синхронизации, вход запуска которого является входом запуска процессора, о т л и ч а ющ и й с я тем, что, с целью повышения быстродействия, в него введены первый, второй, третий и четвертый мультиплексоры, первый и второй элементы ИЛИ, информационный выход арифметического блока подключен к информационному входу второго блока памяти и первому информационному входу первого мультиплексора, информационный выход которого подключен к информационному входу первого блока памяти, информационный выход которого ,подключен к первому информационному входу второго мультиплексора, информационный выход которого подключен к информационному входу арифметического блока, информационный выход второго блока памяти подключен к второму инФормационному входу второго мультиплексора и является информационным выходом процессора, информационным входом которого является второй информационный вход первого мультиплексора, второй выход формирователя .сигналов приращений подключен к первым информационным входам третьего и чет вертого мультиплексоров, информационные входы которых подключены к информационным входам соответственно пер" вого и второго регистров адреса, выходы разрядов второй группы сдвигового регистра подключены к соответствующим входам первого элемента ИЛИ, выход которого подключен к управляющим входам первого, второго и третьего мультиплексоров и является выходом111разрешения ввода процессора, выходыразрядов третьей группы сдвиговогорегистра подключены к соответствующимвходам второго элемента ИЛИ, выходкоторого подключен к управляющемувходу четвертого мультиплексора и 9027является выходом разрешения вывода процессора, первым и вторым входами задания адреса которого являются вторые информационные входы соответственно третьего и четвертого мультиплексоров.Изобретение относится к .вычислительной технике и может быть исполь- зовано при решении задач гармонического анализа, где необходимо производить обработку сигнала в реальном 5масштабе времени.Известно устройство, содержащееблок оперативной памяти, арифметический блок, блок хранения весовыхкоэффициентов, счетчик адресов.операндов, счетчик номера аберации, дешифратор номера. итерации, формирователь адреса весовых коэффициентов.Перед началом вычисления спектра вблок оперативной памяти производится 35ввод массива чисел, над которым производятся вычисления спектра. Вычисле ния производятся постоянно, причемоперанды попарно выбираются из блокаоперативной памяти и после преобра- Юзования (вычисления) записываютсяв память по тем же адресам.После завершения вычислений, ре"зультаты должны быть выведены иэблока оперативной памяти 1 ). 25Недостатком данного устройстваявляется низкая эффективность использования оборудования, так как вовремя выполнения. операций ввода-вывода большая часть оборудования 30устройства простаивает.Наиболее близким к предлагаемомуявляется процессор быстрого преобразования фурье, состоящий из арифметического устройства, входы которогоподключены к входам оперативного запо.минающего устройства (ОЗУ), постоянного запоминающего устройства (ПЗУ),выход которого подключен к входуарифметического устройства, регистра 4 Оадреса ОЗУ, регистра адреса ПЗУ,.формирователя сигналов приращенийрегистров, счетчика отсчетов, счетчика итераций, устройства управления,узла формирования дополнительного 45 3кода, блока сравнения и дополнительного регистра адреса Г 2 3.Недостатком известного устройства является то, что во время ввода исходного массива в процессор и вывода .результатов вычислений большая часть оборудования процессора простаивает. Кроме того, при использовании такого процессора в системе обработки информации в реальном масштабе времени действительное. время. обработки информациискладывается из времени обработки плюс время на операции ввода- вывода, что приводит к уменьшению производительности процессора.Цель изобретения - повышение быстродействия процессора,Поставленная цель достигается тем, что процессор быстрого преобразования Фурье, содержащий арифметический блок, первый и второй блоки памяти, адресные входы которого подключены к информационным выходам соответственно первого и второго регистров адреса, вход задания коэффициентов арифметического блока подключен к информационному выходу блока постоянной памяти, адресный вход которого подключен к информационному выходу третьего регистра адреса, информационный вход которого подключен к первому выходу формирователя сигналов приращений, первый вход которого .подключен к информационному выходу счетчика отсчетов, выход переноса которого подключен к тактовому входу сдвигового регистра, выходы разрядов первой группы которого подключены поразрядно к второму входу формирователя"сигналов приращений, тактовый вход которого подключен к первому выходу блока синхронизации, второй, третий и четвертый вьмоды которого подключены соответственно к счетному входу счетчика отсчетов, тактовомуНа фиг.1 представлена функциональная схема предлагаемого процессора (пример конкретной реализации); на фиг.2 - временная диаграмма работы процессора; на фиг.З - блок-схема формирователя сигналов приращений; 55 входу арифметического блока и управляющим входом первого и второго блоков памяти, выход переноса сдвигового регистра подключен к входу остановаблока синхронизации, вход запускакоторого является входом запуска процессора, введены первый, второй, третий и четвертый мультиплексоры, первый и второй элементы ИЛИ, информационный выход арифметического блока 1 Оподключен к информационному входувторого блока памяти и первому информационному входу первого мультиплексора, информационный выход которогоподключен к информационному входу пер вого блока памяти, информационный выход которого подключен к первомуинформационному входу второго мультиплексора, информационный выход которого подключен к информационному входу арифметического блока, информационный выход второго блока памяти подключен к второму информационному входу второго мультиплексора и является информационным выходом процес сора, информационным входом которого является второй информационный вход первого мультиплексора, второй выход формирователя сигналов приращений подключен к первым информационным , входам третьего и четвертого мультиплексоров, информационные входы которых подключены к информационным входам соответственно первого и второго регистров сброса, выходы разрядов второй группы сдвигового регистра под-ключены к соответствующим входам первого элемента ИЛИ, выход которого подключен к управляющим входам первого, второго и третьего мультиплексоров и является выходом разрешения ввода процессора, выходы разрядов третьей группы сдвигового регистра подключены к соответствующим выходам второго элемента ИЛИ, выход которого подключен к управляющему входу четвертого мультиплексора и является выходом разрешения вывода процессора, первым и вторым входами задания адреса которого являются вторые информационные входы соответственно третьего и четвертого мультиплексоровна фиг,4 - то же, блока синхрониза" ции.Процессор БПФ (фиг. 1) содержит мультиплексор 1, блоки 2 и 3 (оперативной) памяти, мультиплексор 4, арифметический блок 5, регистры 6, 7 адреса и блок 8 постоянной памяти, мультиплексоры 9 и 10, регистр 11 адреса (постоянной памяти), элементы ИЛИ 12 и 13. Формирователь 14 сигналов приращений (регистров), (итерационный) сдвиговый регистр 15, счетчик 16 отсчетов и блок 17 синхронизации.формирователь 14 сигналов приращений регистров (фиг.З) служит для выработки адресов операадов и весовых 1коэффициентов необходимых для выполнения алгоритма БПФ. Структурная схема блока определяется основанием алгоритма БПФ, уровнем совмещения микроопераций в процессоре. На фиг.З приведе.на схема блока для алгоритма БПФ соснованием 2 и последовательной работой арифметического блока и блокапамяти.Формирователь сигналов приращений регистров содержит мультиплексор 18, группу элементов ИЛИ 19, счетчик 20 адресов (операндов с входной логикой) счетчик 21 адресов (ПЗУ) с входной логикой) 21.Схема блока 17 синхронизации приведена на фиг.4. Он содержит генератор 22 тактовых импульсов, распределитель 23 импульсов, элемент И 24, два элемента ИЛИ 25 и 26 и ждущий мультивибратор 27.Рассмотрим работу процессора на примере обработки массива длиной Иотсчетов. Для конкретности примем, что операция ввода исходного массива выполняется за две иберации алгоритма БПФ, т.е, на входы элемента ИЛИ 12 заведены 7 и 8 разряды итерационного сдвигового регистра 15. На операцию вывода результатов вычисления отведены пять итераций алго ритма БПФ, т.е. на входы элемента ИЛИ 13 заведены выходы с первого по пятый разряды итерационного сдвигового регистра 15.В исходном состоянии счетчик 16 в состояние "0", в итерационном сдвиговом регистре в первый разряд записывается "1", в остальные - "0", а все регистры установлены в состояние "0". На выходе элемента1119027ИЛИ 12 устанавливается уровень "0", а на выходе элемента ИЛИ 13 уровень "1". При этом через мультиплексор к блоку 2 .подключен выход арифметического блока 5, а выход блока 2 5 подключен к входу арифметического .блока через мультиплексор 4. Выход 2 формирователя 14 через мультиплексор 9 соединен с входом, регистра 6. Вход 2 процессора через мультиплек 10 сор 10 соединен с входом регистра адреса 7.С приходом тактового импульса чврез блок 17 поступают сигналы, включающие счетчик 16 и регистр 15. В зависимости от кодов на выходах этих блоков формирователь 14 подает сигналы на регистр 6 адреса через мультиплексор 9 и регистр 11, которые формируют адреса обращений к ,блоку 2 и блоку 8 согласно графу БПФ.На втором выходе процессора устанавливается уровень "1", что является сигналом для внешнего устройства5 на разрешение вывода информации из блока через выход 1, при этом на вход 2 внешнее устройство должно подавать адреса считывания.Таким образом, в процессоре вы полняются две операции: операция . БПФ и операция "Вывод".Так продолжаются пять итераций. В шестой итерации устанавливается "1" в шестом разряде регистра 15. На выходе элемента 13 ИЛИ устанавливается сигнал "О" (фиг.2), На выходе 2 процессора устанавливается сигнал "0", запрещающий выполнение операции "Вывод . Мультиплексор 101 40 подключает к регистру 7 выход 2 фор" мирователя 14. На этой итерации выполняется только операция БПФ, причем адреса для считывания поступают от45 формирователя 14 через мультиплексор 9 на регистр 6 и далее на адресный вход блока 2. Адреса для записи поступают от формирователя 14 через мультиплексор 10, регистр 7 и далее на адресный вход блока 3. Таким обра 50 зом, на этой итерации информация считывается из блока 2 и после обработки записывается в блок 3. После перебора всех адресов по сигналу переполнения счетчика 16 происходит сдвиг единицы в итерационном сдвиговом регистре 15. Это соответствует началу выполнения седьмой итерации. На выходе элемента 12 устанавливается сигнал "1". По этому сигналу мультиплексор 1 подключает вход 1 процессора к информационному входу блока 2, мультиплексор 9 подключает вход 3 процессора к входу регистра 6 адреса и на выходе 3 процессора появляется сигнал разрешающий выполнение операции "Ввод". Мультиплексор 4 подключает к входу арифметического блока 5 выход блока 3.Таким образом, (фиг.2) в процессоре выполняются две операции: БПФ и "Ввод", это продолжается до тех пор пока не выполнится последняя, восьмая операция. В результате ее выполнения в блоке 3 находится результат вычислений, а в блоке 2 - новая информация, которую необходимо обработать.По окончании восьмой итерации сигнал с выхода 2 итерационного сдвигового регистра 15 поступает на вход 1 блока 17 синхронизации и цикл вычислений повторяется.Формирователь 14 работает следующим образом,В исходном состоянии счетчики 20 и 21 установлены в ноль сигналом Уст "0". На вход 2 поступает 8-ми разрядный код с итерационного сдвигового регистра 15 (1-й разряд - "1", остальные - "0"). На вход 1 поступает выход первого разряда счетчика 16 отсчетов, который управляет переключением мультиплексора 18. При нулевом значении разряда на выход 2 пропускается выход счетчика 20, на котором формируются первые адреса базовой операции. При единичном значении разряда на выходе 2 пропускается выход элемента 19, на котором образуются вторые адреса операндов базовой операции. Далее на входы счетчиков 20 и 21 поступает синхроимпульс, который через элементы входной логики изменяет состояние разрядов счетчиков.Управление порядком счета осуществляется итерационный сдвиговый регистр. Управление порядком счета состоит в том, что выход разряда итерационного регистра, который находится в состоянии "1", блокирует соответствующий разряд счетчика, запрещая прохождение единиц переноса в этот разряд с предыдущего и разрешая прохождение этих единиц переноса7 111902непосредственно. в следующий за блокируемым разрядом.Адрес второго операнда пары формируется на выходах элементов ИЛИ 19,на однивходы которых поступаеткод счетчика операндов 20, а на друние входы - код с итерационного сдвигового регистра 15 с "1" в соответствующем разряде.Код адреса весового коэффициентаформируется на счетчике адреса ПЗУ 21,причем за счет входной логики счетные импульсы поступают на тот разряд счетчика, на который приходит"1" с итерационного сдвигового регистра.Блок синхронизации работает встарт-стопном режиме,Предположим, что в данный моментпроцессор закончил вычисление и находится в состоянии ожидания. Навход блока синхронизации поступаетсигнал "1", вырабатываемый итерационным сдвиговим регистром при окончании вычислений. Этот сигнал поступает на вход элемента ИЛИ 25 и блокирует работу распределителя.С приходом на вход 2 запускающегоимпульса на выходе элемента И 24возникает сигнал, который запускает30ждущий мультивибратор 27. На выходе 7 8его формируется сигнал У "0", который поступает на вход элемента 25,а также к другим устройствам процес 11 1сора. По окончании сигнала У 0запускается распределитель импульсов 23. Распределитель импульсовЪырабатывает 22 синхроимпульса, смещенных во времени. Эти синхроимпульсы поступают к устройствам процессора,обеспечивая согласованный. режим работы,На выходе 1 формируется суммадвух синхроимпульсов С 11 и С 21;которая поступает на счетный входсчетчика 16 отсчетов. После выполнения последней итерации БПФ на выходе2 итерационного регистра 15 устанавливается уровень "1". Этот сигналпоступает на вход элемента ИЛИ 25 иблокирует работу распределителя.Таким образом, предлагаемое устройство позволяет полностью совместить во времени выполнение операций"ввод-вывода" с операцией БПФ и темсамым повысить производительностьпроцессора. В данном процессоре можно перераспределять время междуоперациями "Ввода" и "Вывод", чтопозволяет организовать сопряжениепроцессора с различными устройствамибез применения буферной памяти.1119027 Сцниросцгноаа Выхст,О Составитель А. БарановРедактор Н. Воловик Техред Л.Коцюбняк Луговая Коррект акаэ 7455/ ал ППП "Патент", г, Ужгород, ул, Проектна Тираж 698 НИИПИ Государств по делам иэобре 13035, Иосква, Ж Подписноенного комитета СССРений и открытий35, Раушская наб., д. 4/