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

 

ПРОЦЕССОР БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащий арифметический блок, первый и второй блоки памяти, адресные входы которых подключены к информационным выходам соответственно первого и второго регистров адреса, вход задания коэффициентов арифметического блока подключен к информационному выходу блока постоянной памяти, адресный вход которого подключен к информационному выходу третьего регистра адреса, информационный вход которого подключен к первому выходу формирователя сигналов приращения, первый вход которого подключен к информационному выходу счетчика отсчетов, выход переноса которого подключен к тактовому входу сдвигового регистра, выходы разрядов первой группы кЬторого подключены поразрядно к второму входу формирователя сигналов приращений, тактовый вход которого подключен к первому выходу блока синхронизации, второй, третий и четвертый выходы которого подключены соответственно к счетному входу счетчика отсчетов, тактовому входу арифметического блока и управляющим входам первого и второго блоков памяти, выход переноса сдвигового регистра подключен к входу останова блока синхронизации, вход запуска которого является входом запуска процессора, отличающийся тем, что, с целью повышения быстродействия,, в него введены первый, второй, третий и четвертый мультиплексоры, первый и второй элементы ИЛИ, информационный выход арифметическох о блока подключен к информационному входу второго блока памяти и первому информационному входу первого мультиплексора, информационный выход которого подключен к ин§ формационному входу первого блока памяти, информационный выход которого (Л подключен к первому информационному входу второго мультиплексора, инфорс: мационный выход которого подключен к информационному входу арифметического 5 блока, информационный выход второго 1 блока памяти подключен к второму информационному входу второго мультиплексора и является информационным выходом процессора, информационным входом которого является второй инСО О формационный вход первого мультиплексора , второй вьпсод формирователя .сигьэ налов приращений подключен к первым ч1 информационным входам третьего и четвертого мультиплексоров, информационные входы которых подключены к информационным входам соответственно первого и второго регистров адреса, вЬпсоды разрядов второй группы сдвигового регистра подключены к соответствующим входам первого элемента ИЛИ, выход которого подключен к управляющим входам первого, второго и третьего мультиплексоров и является выходом

СОЮЗ COBETCHHX

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (11) 7 А

З(51) G 06 F 15/332

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО. ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3623602/18-24 (22) 12.04.83 (46) 15.10.84. Бюл. № 38 (72) В.П. Карасев, П.П. Перьков и В.А. Шаньгин (53) 681.32(088.8) (56) 1. Авторское свидетельство СССР № 590750, кл. G 06 F 15/332, 1978.

2. Авторское свидетельство СССР

¹ 788114, кл. G 06 F 15/32, 1980 (прототип). (54) (57) ПРОЦЕССОР БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащий арифметический блок, первый и второй блоки. памяти, адресные входы которых подключены к информационным выходам соответственно первого и второго регистров адреса, вход задания коэффициентов арифметического блока подключен к информационному выходу блока постоянной памяти, адресный вход которого подключен к информационному выходу третьего регистра адреса, информационный вход которого подключен к первому выходу формирователя сигналов приращения, первый вход которого подключен к информационному выходу счетчика отсчетов, выход переноса которого подключен к тактовому входу сдвигового регистра, выходы разрядов первой группы которого подключены поразрядно к второму входу формирователя сигналов приращений, тактовый вход которого подключен к первому выходу блока синхронизации, второй, третий и четвертый выходы которого подключены соответственно к счетному входу счетчика отсчетов, тактовому входу арифметического блока и управляющим входам первого и второго блоков памяти, выход переноса сдвигового регистра подключен к входу останова блока синхронизации, вход запуска которого является входом запуска процессора, о т л и ч а юшийся тем, что, с целью повышения быстродействияу в него введены первый, второй, третий и четвертый мультиплексоры, первый и второй элементы ИЛИ, информационный выход арифметического блока подключен к информационному входу второго блока памяти и первому информационному входу первого мультиплексора, информационный выход которого подключен к информационному входу первого блока щ памяти, информационный выход которого ,подключен к первому информационному входу второго мультиплексоРа, иаформационный выход которого подключен к информационному входу арифметического Я блока, информационный выход второго блока памяти подключен к второму информационному входу второго мультиплексора и является информационным выходом процессора, информационным входом которого является второй информационный вход первого мультиплексора, второй выход формирователя .сигналов приращений подключен к первым информационным входам третьего и четвертого мультиплексоров, информационные входы которых подключены к информационным входам соответственно первого и второго регистров адреса, выходы разрядов второй группы сдвиго-. вого регистра подключены к соответствующим входам первого элемента ИЛИ, выход которого подключен к управляющим входам первого, второго и третьего мультиплексоров и является выходом

111 разрешения ввода процессора, выходы разрядов третьей группы сдвигового регистра подключены к соответствующим входам второго элемента ИЛИ, выход которого подключен к управляющему входу четвертого мультиплексора и

9027 является выходом разрешения вывода процессора, первым и вторым входами задания адреса которого являются вторые информационные входы соответственно третьего и четвертого мультиплексоров.

Изобретение относится к .вычислительной технике и может быть исполь зовано при решении задач гармонического анализа, где необходимо производить обработку сигнала в реальном 5 масштабе времени.

Известно устройство, содержащее блок оперативной памяти, арифметический блок, блок хранения весовых коэффициентов, счетчик адресов.операндов, счетчик номера аберации, дешифратор номера. итерации, формирователь адреса весовых коэффициентов.

Перед началом вычисления спектра в блок оперативной памяти производится 15 ввод массива чисел, над которым произ водятся вычисления спектра. Вычисле ния производятся постоянно, причем операнды попарно выбираются из блока оперативной памяти и после преобра- 20 зования (вычисления) записываются в память по тем же адресам.

После завершения вычислений, ре" зультаты должны быть выведены иэ блока оперативной памяти 1 ). 25

Недостатком данного устройства является низкая эффективность использования оборудования, так как во время выполнения. операций ввода-вывода большая часть оборудования 30 устройства простаивает.

Наиболее близким к предлагаемому является процессор быстрого преобразования Фурье, состоящий из арифметического устройства, входы которого подключены к входам оперативного запо» минающего устройства (ОЗУ), постоянного запоминающего устройства (ПЗУ), выход которого подключен к входу арифметического устройства, регистра 40 адреса ОЗУ, регистра адреса ПЗУ, .формирователя сигналов приращений регистров, счетчика отсчетов, счетчика итераций, устройства управления, узла формирования дополнительного 45

2 кода, блока сравнения и дополнительного регистра адреса f2 3.

Недостатком известного устройства является то, что во время ввода исходного массива в процессор и вывода .результатов вычислений большая часть оборудования процессора простаивает.

Кроме того, при использовании такого процессора в системе обработки информации в реальном масштабе времени действительное. время обработки информации складывается из времени обработки плюс время на операции вводавывода, что приводит к уменьшению производительности процессора.

Цель изобретения — повышение быстродействия процессора.

Поставленная цель достигается тем, что процессор быстрого преобразования Фурье, содержащий арифметический блок, первый и второй блоки памяти, адресные входы которого подключены к информационным выходам соответственно первого и второго регистров адреса, вход задания коэффициентов арифметического блока подключен к информационному выходу блока постоянной памяти, адресный вход которого подключен к информационному выходу третьего регистра адреса, информационный вход которого подключен к первому выходу формирователя сигналов приращений, первый вход которого

-подключен к информационному выходу счетчика отсчетов, выход переноса которого подключен к тактовому входу сдвигового регистра, выходы разрядов первой группы которого подключены поразрядно к второму входу формирователя"сигналов приращений, тактовый вход которого подключен к первому выходу блока синхронизации, второй, третий и четвертый выходы которого подключены соответственно к счетному входу счетчика отсчетов, тактовому

1119027 входу арифметического блока и управляющим входом первого и второго блоков памяти, выход переноса сдвигового регистра подключен к входу останова блока синхронизации, вход запуска которого является входом запуска процессора, введены первый, второй, третий и четвертый мультиплексоры, первый и второй элементы ИЛИ, информационный выход арифметического блока 10 подключен к информационному входу второго блока памяти и первому информационному входу первого мультиплексора, информационный выход которого подключен к и н4ормационному! входу пер- f 5 вого блока памяти, информационный выход которого подключен к первому информационному входу второго мультиплексора, информационный выход которого подключен к информационному входу арифметического блока, информационный выход второго блока памяти подключен к второму информационному входу второго мультиплексора и является информационным выходом процессора, информационным входом которого является второй информационный вход первого мультиплексора, второй выход формирователя сигналов приращений подключен к первым информационным . входам третьего и четвертого мультиплексоров, информационные входы которых подключены к информационным входам соответственно первого и второго регистров сброса, выходы разрядов второй группы сдвигового регистра подключены к соответствующим входам первого элемента ИЛИ, выход которого подключен к управляющим входам первого, второго и третьего мультиплексоров и является выходом разрешения ввода процессора, выходы разрядов третьей группы сдвигового регистра подключены к соответствующим выходам второго элемента ИЛИ, выход которого подключен к управляющему входу четвертого мультиплексора и является выходом разрешения вывода процессора, первым и вторым входами задания адреса которого являются вторые информационные входы соответственно третьего и четвертого мультиплексоров °

На фиг.1 представлена функциональная схема предлагаемого процессора (пример конкретной реализации); на фиг.2 — временная диаграмма работы процессора; на фиг.3 — блок-схема формирователя сигналов приращений; на фиг.4 — то же, блока синхронизации.

Процессор БПФ (фиг. 1) содержит мультиплексор 1, блоки 2 и 3 (оперативной) памяти, мультиплексор 4, арифметический блок 5, регистры 6, 7 адреса и блок 8 постоянной памяти, мультиплексоры 9 и 10, регистр 11 адреса (постоянной памяти), элементы

ИЛИ 12 и 13. Формирователь 14 сигналов приращений (регистров), (итерационный) сдвиговый регистр 15, счетчик 16 отсчетов и блок 17 синхронизации.

Формирователь 14 сигналов приращений регистров (фиг.3) служит для выработки адресов операадов и весовых

1 коэффициентов необходимых для выполнения алгоритма БПФ. Структурная схема блока определяется основанием алгоритма БПФ, уровнем совмещения микроопераций в процессоре. На фиг.3 приведена схема блока для алгоритма БПФ с основанием 2 и последовательной работой арифметического блока и блока памяти.

Формирователь сигналов приращений регистров содержит мультиплексор 18, группу элементов ИЛИ 19, счетчик 20 адресов (операндов с входной логикой) счетчик 2 l адресов (ПЗУ) с входной логикой) 21.

Схема блока 17 синхронизации приведена на фиг.4. Он содержит генератор 22 тактовых импульсов, распределитель 23 импульсов, элемент И 24, два элемента ИЛИ 25 и 26 и ждущий мультивибратор 27.

Рассмотрим работу процессора на примере обработки массива длиной

И256 отсчетов. Для конкретности примем, что операция ввода исходного массива выполняется за две иберации алгоритма БПФ, т. е. на входы элемента ИЛИ 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 процессора через мультиплекt0 сор 10 соединен с входом регистра адреса 7.

С приходом тактового импульса через блок 17 поступают сигналы, включающие счетчик 16 и регистр 15.

В зависимости от кодов на выходах этих блоков формирователь 14 подает сигналы на регистр 6 адреса через мультиплексор 9 и регистр 11, которые формируют адреса обращений к блоку 2 и блоку 8 согласно графу

БПФ.

На.втором выходе процессора устанавливается уровень "1", что является сигналом для внешнего устройства

25 на разрешение вывода информации из блока через выход 1, при этом на вход 2 внешнее устройство должно подавать адреса считывания.

Таким образом, в процессоре вы- 30 полняются две операции: операция, БПФ и операция "Вывод".

Так продолжаются пять итераций.

В шестой итерации устанавливается

"1" в шестом разряде регистра 15.

На выходе элемента 13 Ш1И устанавливается сигнал "О" (фиг.2). На выходе 2 процессора устанавливается сигнал "0", запрещающий выполнение операции "Вывод". Мультиплексор 10

40 подключает к регистру 7 выход 2 формирователя 14. На этой итерации выполняется только операция БПФ, причем адреса для считывания поступают от формирователя 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 установлены в ноль сигналом У >

i"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 его формируется сигнал Y "0", который поступает на вход элемента 2$, а также к другим устройствам процес11 11 сора. По окончании сигнала Y 0 запускается распределитель импульсов 23. Распределитель импульсов

Ъырабатывает 22 синхроимпульса, смещенных во времени. Эти синхроимпульсы поступают к устройствам процессора, обеспечивая согласованный. режим работы.

На выходе 1 формируется сумма двух синхроимпульсов С„ 11 и C 21; которая поступает на счетный вход счетчика 16 отсчетов. После выполнения последней итерации БПФ на выходе

2 итерационного регистра 15 устанавливается уровень "1". Этот сигнал поступает на вход элемента ИЛИ 25 и блокирует работу распределителя.

Таким образом, предлагаемое устройство позволяет полностью совместить во времени выполнение операций

"ввод-вывода" с операцией БПФ и тем самым повысить производительность процессора. В данном процессоре можно перераспределять время между операциями "Ввода" и "Вывод", что позволяет организовать сопряжение процессора с различными устройствами без применения буферной памяти.

1119027 о аащин1 ЯЗФ fb ? 8t г 3 0 5 6 У 8 1

Операция Ви)1ед(-g) ,8bФОФ

gblX 1

Иеера ия

„ХПУ

Желания

„Ипд

Вых0д . ,иле" ц ию() равд(() 8$ul(g +ã)

ХЛ7(см

®РФ(i: y) 1119027

Синиросигноаы

ВЫ# 7

Cvf т.0

Aff 4М

Pui. Ф

Закаэ 7455/37 Тираж 698. Подписное

ВНИИПИ Государственного комитета СССР по делам иэобретений и открытий

1 13035, Иосква, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4

Составитель А. Баранов

Редактор Н. Воловик Техред Л.Коцюбняк Корректор О, Луговая