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

Авторы патента:

G06F9 - Устройства для программного управления, например блоки управления (программное управление для периферийных устройств G06F 13/10)

G06F17/14 - преобразования Фурье, Уолша или аналогичные преобразования

УСТРОЙСТВО УПРАВЛЕНИЯ ДЛЯ ПРОЦЕССОРА БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее генератор тактовых импульсов, выход которого является выходом синхронизации устройства и подключен к тактовому входу счетчика , вькод i -го (т- Г,,. 2,3) разряда которого соединен с первым входом g-ro ( 1 ,п-2) элемента И группы, выход которого соединен с j-ым входом первого коммутатора кода, выход которого является первым адресным выходом устройства, выходтп-го разряда счетчика соединен с последовательным входом первого сдвигового регистра, выход -го разряда которого подключен к второму вхоДу j-го элемента И группы, выход первого разряда счетчика соединен с управляющим входом первого коммутатора кода, а выход второго коммутатора кода является вторым адресным выходом устройства , о т л и ч аю щ е е с я тем, что, сцелью повышения быстродействия., в него введены второй сдвиговый регистр , два элемента ИСКЛЮЧАЩЕЕ ИЛИ, два элемента И и триггер режима, выход которого соединен с первым входом первого элемента ИСКЛЮЧАЭДЕЕ ИЛИ, второй вход которого объединен с управляющим входом второго сдвигового регистра и подключен к йыходу второго элемента ИСКЛЮЧАЮЩЕЕ ,ШШ, первый вход которого соединен с выходом второго разряда счетчика, выход третьего разряда которого является выходом управления записью-считыванием устройства и подключен к второму входу второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, вход триггера режима соединен с выходомm-го разряда счетчика, выход v-го ( г. 1,V), i 2,3) разряди которого под (Л ключен к входу 3-го (,m-2) разряда второго сдвигового регистра, выход -го разряда которого соединен с V.-M входом второго коммутатора кода, управляющий вход которого подключен к выходу первого элемента И, первый 1 вход которого соединен с выходом второго элемента И, второй вход -которого подключен к-последовательному ; выходу первого сдвигового регистра, второй вход первого элемента И объе | со динен с тактовым входом счетчика, выход второго разряда которого является выходом режима работы устройства , последовательный выход второго сдвигового регистра подключен к последовательному входу второго сдвигового регистра, выход первого элемента ИСКГИОЧАЩЕЕ ШШ является третьим адресным выходом устройства, а первый вход второго элемента И является входом задания режима устройства.

СОЮЗ СОВЕТСНИХ

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

РЕСПУБЛИК

„„SU„„1 И 1173 у G 06 F 15/332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3541033/18-24. (22) 20.01.83 (46) 30.08.84. Бюл, У 32 (72) А.Н. Карташевич, В.В. Николаевский,и А.И. Ходосевич (71) Научно-исследовательский институт прикладных физических проблем им. акад. А.Н. Сенченко (53) 681.32(088.8) (56) 1. Авторское свидетельство СССР

Р 809198, кл. G 06 F 15/332, 1979.

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

Ф 814122, кл. G 06 Р 15/332, 1979 (прототип). (54)(57) УСТРОЙСТВО УПРАВЛЕНИЯ ДЛЯ

ПРОЦЕССОРА БЫСТРОГО ПРЕОБРАЗОВАНИЯ

ФУРЬЕ, содержащее генератор тактовых импульсов, выход которого является выходом синхронизации устройства и подключен к тактовому входу счетчика, выход i -го (ъ = 1 р, K Ф 2;3) разряда которого соединен с первым входом g- p (g = 1,m-2) элемента И группы, выход которого соединен с 1 р -ым входом первого коммутатора кода, выход которого является первым адресным выходом устройства, выход т-го разряда счетчика соединен с последовательным входом первого сдвигового регистра, выход j --го разряда которого подключен к второму вхоДу ) --го элемента И группы, выход. первого разряда счетчика соединен с управляющим входом первого коммутатора кода, а выход второго коммутатора кода яв. ляется вторым адресным выходом устройства, о т л и ч а-ю щ е е с я тем, что, с целью повышения быстродействия, в него введены второй сдвиговый регистр, два элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, два элемента И и триггер режима, выход которого соединен с первым входом первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, второй вход которого объединен с управляющим входом второго сдвигового регистра и подключен к выходу второго элемента ИСКЛЮЧАЮЩЕЕ,ИЛИ, первый вход которого соединен с выходом второго разряда счетчика, выход третьего разряда которого является выходом управления записью-считыванием устройства и подключен к второму входу второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, вход триггера режима соединен с выходом1п-го разряда счетчика, выход i-o (ъ = вЂ” 1,111, ъj 2,3) разряда которого подключен к входу j --го (=1 рт-2) разряда второго сдвигового регистра, выход

j-ro разряда которого соединен с -м входом второго коммутатора кода, управляющий вход которого подключен к выходу первого элемента И, первый вход которого соединен с выходом второго элемента И, второй вход -которого подключен к.последовательному выходу первого сдвигового регистра, второй вход первого элемента И объединен с тактовым входом счетчика, выход второго разряда которого является выходом режима работы устройства, последовательный выход второго сдвигового регистра подключен. к последовательному входу второго сдвигового регистра, выход первого элемента

ИСКЛ10ЧАЮЩЕЕ ИЛИ является третьим ад- . ресным выходом устройства, а первый вход второго элемента И является входом задания режима устройства. ным выходом устройства, выход о-го разряда счетчика соединен с последовательным входом первого сдвигового регистра, выход -II-ro разряда которого подключен к второму входу j -ro элемента И группы, выход первого разряда счетчика соединен с управляющим входом первого коммутатора кода, а выход второго коммутатора кода является вторым адресным выходом устройства, введены второй сдвиговый регистр, два элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, два элемента И и триггер режима, выход которого соединен с первым входом первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, второй вход которого объединен с управляющим входом второго сдвигового регистра и подключен к выходу второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, первый вход которого соединен с выходом второго разряда счетчика, выход третьего разряда которого является выходом управления записью-считыванием устройства и подключен к второму входу второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, вход триггера режима соединен с выходом w -го разряда счетчика, выход

i-ro (i = 1,п, ь 2, 3) разряда которого подключен к входу j-го (g =1+-2) разряда второго сдвигового регистра, выход j --ro разряда которого соединен с -м входом второго коммутатора кода, управляющий вход которого подключен к выходу первого элемента И, первый вход которого соединен с выходом второго элемента И, второй вход которого подключен к последова-, тельному выходу первого сдвигового регистра, второй вход первого элемента И объединен с тактовым входом счетчика, выход второго разряда которого является выходом режима работы устройства, последовательный выход второго сдвигового регистра подключен к последовательному входу. второго сдвигового регистра, выход первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ является третьим адресным выходом устройства, а первый вход второго элемента И является входом задания режима устройства.

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

4 1111173 2

Устройство относится к вычислительной технике, в частности к устройствам, реализующим алгоритмы быстрого преобразования Фурье (БПФ), и может быть использовано в многоканаль-5 ных системах спектрально-корреляционной обработки сигналов.

Известно устройство для реализации БПФ, содержащее постоянную и оперативную память, арифметический блок и блок управления i1) .

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

Наиболее близким по технической сущности к изобретению является устроиство управления для процессора

БПФ, содержащее счетчик, первую и вторую схемы инверсии кода, второй регистр сдвига, блок элементов И, генератор тактовых импульсов, при этом второй выход генератора тактовых импульсов является вторым выходом 25 блока управления, первый выход гене- ратора тактовых импульсов подключен к входу счетчика, выход последнего разряда которого соединен с входом второго регистра сдвига, выход блока элементов И подключен к первому входу второй схемы инверсии кода, выход которой является вторым выходом блока управления, а выход первой схемы инверсии кода его первым выходом С23.

Это устройство позволяет реализовать безызбыточный алгоритм с прореживанием по времени и с замещением.

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

Целью изобретения является повы- 45 шение быстродействия.

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

:является выходом синхронизации устройства и подключен к тактовому входу счетчика, выход а -ro (< = 1,ю,i>2,3) разряда которого соединен с первым входом 1 --ro (=1,vn-2) элемента И группы, выход которого соединен с

) -ым входом первого коммутатора кода, выход которого является первым адрес11111

В оперативную память 1, которая разбита на две половины, записываются исходные данные таким образом, что

s первую половину памяти 1 данные заносятся в двоично-инверсном поряд- 55 ке, а во вторую половину - в прямом порядке. В постоянной памяти 3 записаны значения векторов поворота, 3 по времени, т.е. дает возможность проводить обработку одновременно

Двух действительных массивов данных.

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

На. фиг.1 приведен граф реализованного алгоритма для 16-точечной последовательности данных (движение по графу слева направо соответствует выполнению алгоритма с прореживанием. 20 по частоте, а движение справа налевовЂ” алгоритма с прорекиванием по времени, для первого случая номера векторов поворота указаны без скобок),на фиг.2 вЂ” блок-схема устройства управ- р5 ления процессора БПФ; на фиг.ЗвЂ” функциональная схема устройства управления.

Устройство содержит оперативную память 1, арифметический блок 2, по- 30 стоянную память 3, устройство управления 4 (фиг.2), счетчик 5, сдвиговый регистр 6, группу элементов И 7, сдвиговый регистр 8, коммутатор кода

9, элементы ИСКЛКИАЮЩЕЕ ИЛИ 10 и 11, 35 триггер режима 12, генератор тактовЂ” вых импулЬсов 13, коммутатор кода

14, элементы И 15 и 16 (фиг.З).

Процессор БПФ работает в двух режимах: обработка двух комплексных последовательностей данных; обработка четырех действительных последовательностей данных.

Режим работы процессора задается потенциалом на входе устройства Х1. 45

Потенциал "0" соответствует обработке двух, а потенциал "1" вЂ” четырех массивов данных.

Режим 1 - обработка двух комплексных последовательностей данных.

1 50

73 4 которые выбираются из памяти по кодам адресЬв, формируемых устройством управления 4, и заносятся в арифметический блок на обработку. Работу устройства поясняет граф, приведенный на фиг. 1. Над первой частью памяти 1 выполняется алгоритм БПФ с прореживанием по времени, над второй вЂ” с прореживанием по частоте.

Процессор работает следующим образом.

По кодам адресов, вырабатываемых устройством управления 4, из первой части памяти 1 выбираются операнды и заносятся на обработку в арифметический блок 2. Начинается обработка двух операндов. За это время устройство управления 4 формирует еще два адреса для выбора двух операндов из второй части памяти 1, которые записываются во входные регистры арифметического блока 2. После обработки первой пары операндов устройство уп- равления 4 формирует коды адресов, по которым информация записывается во вторую часть памяти 1, а другая пара после обработки вЂ” на.место выбранной информации из первой половины памяти. Затем снова формируются адреса для выбора информации из памяти

1. Так работает устройство на одной итерации БПФ. Как видно из графа, приведенного на фиг. 1, порядок выбора операндов на каждой итерации остается неизменным. Кроме того, номера векторов поворота для каждой итерации остаются одинаковыми для алгоритмов БПФ с прореживанием по времени и частоте. Объем обрабатываемых массивов определяет количество итераций, необходимых для вычисления БПФ.

Режим 11 вЂ” обработка четырех действительных массивов данных.

В этом случае в процессоре БПФ реализуются безызбыточные алгоритмы вычисления БПФ, когда два действительных массива данных x(k) и y(k) представляются в виде одного комплексного массива. Z(k):

Z(k) = x(k) + jy(k) (1)

Затем производится преобразование

Фурье комплексных массивов данных, как было рассмотрено ранее. Отличие работы устройства в режимах 1 и 2 заключается в том, что при работе в режиме 2 для восстановления спектров исходных сигналов х(п) и y(n) на

1111173 положительных частотах требуется дополнительная итерация. Спектры восстанавливаются согласно соотношеiниям: вЂ” Re fZ(n)+Z(N-n)J

Im (Z(n)-Z(N-n)g

Im jZ (n) +Z (N-n))

2 вЂ” Re fZ(n)- Z(N-n)) .

Re fx(n)j =

Im(x(n)g =

Re (Y(n))

Im fY(n)J = (2)

Работу устройства 4 управления (фиг.3) поясняет таблица, на которой показано формирование команд устройством 4 управления на последней итерации восьмиточечного БПФ. Устройствс

Основным устройством процессора

БПФ, в котором закодирован алгоритм 15 вычислений, является устройство управ.ления 4.

На первом выходе У1 устройства 4 управления формируются адреса операндов, выбираемых из памяти 1. На 20 втором выходе У2 вЂ” импульсы синхронизации арифметического блока 2. На третьем выходе УЗ вЂ” адреса операндов, выбираемых иэ постоянной памяти 3.

На выходе У4 формируются команды для режима работы арифметического блока

2, т.е. выполняется алгоритм БПФ с прореживанием по времени или частоте.

Импульсы на выходе У5,пятом выходе устройства 4 управления, определяют 30 часть памяти 1, откуда выбирается информация, а на шестом выходе У6 формируются импульсы, которые разрешают запись или считывание информации из оперативной памяти 1. Коммута-35 торы кода 9 и 14 представляют собой набор элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, первые входы каждого элемента являются входом коммутаторов кода, а вторые входы каждого элемента объединены и 40 являются вторым входом коммутаторов . кода 14 и 9. При подаче на второй вход потенциала "0" информация проходит через коммутатор без изменения, а при потенциале 1 инвертируется. 45

В первый выход счетчика 5 объединяются выходы всех его разрядов, исключая второй и третий разряды. Выходы счетчика 5 и регистра 8 подключаются к группе элементов И 7, таким образом, что входы одного элемента И соединены с выходами равнозначных разрядов счетчика 5 и регистра 8.

4 управления работает в двух режимах: обработка двух комплексных последовательностей данных; обработка четырех действительных последовательностей данных.

При обработке двух комплексных последовательностей на вход устройства Х1 (первый вход второго элемента И 16) подается потенциал "О".

В исходном состоянии счетчик 5, регистры 6 и 8 обнулены,триггер режима 12 установлен в нулевое состояние. На всех выходах устройства 4 управления Потенциалы соответствуют уровню "0". Элемент И 16 блокирует прохождение информации на второй вход коммутатора 14, на нем устанавливается потенциал "0", и через коммутатор 14 информация проходит без изменения. Запускается генератор 13, и начинается работа устройства 4 управления и процессора в целом. !

Тактовые импульсы поступают на вход счетчика 5, начинается формирование команд для выполнения реализуемого алгоритма БПФ. Информация о состоянии разрядов счетчика 5 переписывается по входу в регистр 6. Выходы второго и третьего разрядов счетчика

5 анализируются с помощью элемента

10 ИСКЛЮЧАЮЩЕЕ ИЛИ. Если состояние разрядов различное (см.таблицу), формируется импульс сдвига информации на один разряд в сторону младших разрядов. Если состояние разрядов одинаковое, то импульс сдвига не форми-. руется. Второй выход сдвигового регистра 6 (выход со стороны младших разрядов). соединен с входом, и при поступлении импульса сдвига с выхода элемента 10 из кода адреса 001 на выходе сдвигового регистра 6 получается код 100, который через коммутатор кода 14 поступает на выход У1 устройства 4 управления. Одновременно на выходе УЗ формируются коды адресов информации, выбираемой из постоянной памяти 3. Группа элементов И 7 в зависимости от выполняемой итерации

БПФ, определяемой состоянием разрядов сдвигового регистра 8, преобразуетинформацию с первого выхода счетчика 5 в коды адресов для выбора информации из памяти 3 (см. таблицу).

Выборкой информации из памяти 3 управляет младший разряд счетчика 5, подключенный к входу коммутатора 9.

It u

0 в младшем разряде счетчика соот1111173

+ (3) Yit- =- X1, - Y W, 45

7 ветствует выборке значения косинуса, ! I !!

1 вЂ” синуса, путем инверсии кода адресов косинуса.

Признак части памяти 1 для выбора и записи информации формируется с помощью элементов ИСКЛЮЧАЮЩЕЕ ИЛИ

10 и 11. "О," на выходе У5 соответствует обращению к первой половине памяти 1, а 1" вЂ” к второй половине (см.таблицу). Третий разряд счетчика 10

5 определяет режим записи или считывания информации из оперативной памяти 1 вЂ” выход У6 (см.таблицу, "О" соответствует считыванию информации

"1" вЂ” записи). После- заполнения счет- 15 чика 5 (выполнена итерация БПФ) "1" с последнего разряда счетчика 5 заносится со стороны старших разрядов в сдвиговый регистр 8, и начинается следующая итерация вычислений. Одно- 2О временно с занесением в регистр 8

"единицы" триггер 12 режима меняет свое состояние. На каждой нечетной итерации информация проходит на выход У5 через элемент 11 без измене- 25 ний, а на четных итерациях (на выходе триггера 12 вЂ” "1") инвертируется.

Необходимость менять адресацию. в зависимости от итерации вычислений обусловливается алгоритмом вычислений (см. фиг.1). Информация на выходе У4 соответствует различным режимам работы арифметического блока

2..

Арифметический блок 2 работает в

35 двух режимах. При потерциале, соответствующем уровню "0", на выходе

У4 устройства 4 управления арифметический блок реализует алгоритм с прореживанием по времени и выполняет 4> операции в соответствии с выражением а при потенциале ".1" на выходе У4 реализуется алгоритм с прореживанием . по частоте и выполняются операции

Х„- <- Х + Y (4) 50

Y1+< = (Х где X>,Y - вЂ” операнды на -ой итерации;

W вЂ” комплексный вектор поворота.

Как видно из приведенного на фиг. 1 реализованного алгоритма, на каждой итерации вычислений порядок выбора операндов из оперативной памяти 1 остается постоянным. Постоянным остается и порядок записи информаЦии в память 1 после обработки в арифметическом блоке 2. Следует отметить, что порядок выбора информации из памяти 3 при реализации алгоритмов с прореживанием по частоте и по времени совпадает.

При обработке четырех действительных массивов данных на вход Х1 подается потенциал, соответствующий уровню "1". Входные последователь-. ности данных представляются в виде (1), и начинается обработка информации по безызбыточному алгоритму.

Работа устройства 4 управления при реализации безызбыточного алгоритма отличается тем, что после завершения вычислений требуется дополнительная итерация для .восстановления спектров сигналов в соответствии с выражениями (2). Из приведенных соотношений видно, что для получения кода адреса операнда Х(й-w) необходимо проинвертировать код адреса операнда

X(n). Для этого служит коммутатор кода 14, который включается в работу лишь на дополнительной итерации. Единичный потенциал на входе Х1 разбло- кирует второй элемент И 16.- После завершения последней итерации вычислений "1" записывается в сдвиговый регистр 8, и он полностью заполняется

"единицами". На выходе элемента И 16 устанавливается потенциал "1" и разрешается прохождение информации на второй вход коммутатора кода 14.

При подаче на другой вход коммутатора

14 потенциала "0" на выходе У1 формируется код адреса X(n) а при подаче потенциала "1" вЂ” код адреса Х()

X(8-и)

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

I0 11!1173 оперативн памяти постоян ной памяти

О О

О 1

1 О

О 1

1 0

О 1

1 О

О 1

1 О

О 1

° 0