Устройство управления для процессора быстрого преобразования Фурье Советский патент 1984 года по МПК G06F9/00 G06F17/14 

Устройство относится к вычислительной технике, в частности к устройствам, реализующим алгоритмы быс рого преобразования Фурье (БПФ), и может быть использовано в многокана ных системах спектрально-корреляцио ной обработки сигналов. Известно устройство для реализации БПФ, содержащее постоянную и оп ративную память, арифметический бло и блок управления С1 .. Недостатком этого устройства является низкое быстродействие, обусловленное несовершенным блоком управления, не позволяющим эффективно использовать арифметический блок. Наиболее близким по технической сзпцности к изобретению является устройство управления для процессора БПФ, содержащее счетчик, первую и вторую схемы инверсии кода, второй регистр сдвига, блок элементов И, генератор тактовых импульсов, при этом второй выход генератора тактовы импульсов является вторым выходом блока управления, первый выход генератора тактовых импульсов подключен к входу счетчика, выход последнего разряда которого соединен с входом второго регистра сдвига, выход блока элементов И подключен к первому вход второй схемы инверсии кода, выход которой является вторым выходом блока управления, а выход первой схемы инверсии кода его первым выходом C2J Это устройство позволяет реализовать безызбыточный алгоритм с прореживанием по времени и с замещением Однако оно сложно по конструкции и не позволяет повысить быстродействие процессора БПФ из-за неэффективного использования арифметического блока, так как не может обрабатывать одновременно несколько массивов данных. Целью изобретения является повышение быстродействия. Поставленная цель достигается тем, что в устройство, управления для процессора быстрого преобразования Фурье, содержащее генератор тактовых импульсов, вькод которого является выходом синхронизации устро ства и подключен к тактовому входу счетчика, выход i-го (- 1,т,,3 разряда которого соединен с первым входом -го (,П1-2) элемента И группы, выход которого соединен с -ым входом первого коммутатора кода выход которого является первым адрес 32 ным выходом устройства, выход гп-го разряда счетчика соединен с последовательным входом первого сдвигового регистра, выход-j-го разряда которого подключен к второму входу j-го элемента И группы, выход первого разряда счетчика соединен с управляющим входом первого коммутатора кода, а выход второго коммутатора кода является вторым адресным выходом устройства, введены второй сдвиговый регистр, два элемента ИСКЛЮЧАЮЩЕЕ ИЖ, два элемента И и триггер режима, выход которого соединен с первым входом первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, второй вход которого объединен с управляющим входом второго сдвигового регистра и подключен к выходу второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, первый вход которого соединен с выходом второго разряда счетчика, выход третьего разряда которого является выходом управления записью-считыванием устройства и подключен к второму входу второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, вход триггера режима соединен с выходом m -го разряда счетчика, выход 1.-ГО (г 1,vn,г 2,3) разряда которого подключен к входу -го Q 1 ,-2) разряда второго сдвигового регистра, выход -го разряда которого соединен с j-м входом второго коммутатора кода, управляющий вход которого подключен к вькоду первого элемента И, первый вход которого соединен с выходом второго элемента И, второй вход которого подключен к последова- . тельному выходу первого сдвигового регистра, второй вход первого элемента И объединен с тактовым входом счетчика, выход второго разряда кото рого является выходом режима работы устройства, последовательньй выход второго сдвигового регистра,подключен к последовательному входу второго сдвигового регистра, выход первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ является третьим адресным выходом устройства, а первый вход второго элемента И является входом задания режима устройства. Сущностью изобретения является изменение устройства управления процессором БПФ, что позволяет реализовать более эффективный алгоритм вычислений. Применение известного устройства позволяет реализовать безызбыточный алгоритм БПФ с прореживанием 31 по времени, т.е. дает возможность проводить обработку одновременно Двух действительных массивов данных. Однако существует ряд задач, в частности задачи обнаружения и слежения за целями в гидроакустике, когда воз никает необходимость в одновременной обработке трех и более действительных массивов данных. Известные устройства не могут решить эти задачи, в то время как предлагаемое устроит ство позволяет проводить одновременную обработку двух комплексных или четырех действительных массивов даиных. На фиг.1 приведен граф реализован ного алгоритма для 16-точечной после довательности данных (движение по графу слева направо соответствует вьшолнению алгоритма с прореживанием по частоте, а движение справа налево алгоритма с прор сиванием по времена для перво1 о случая номера векторов поворота указаны без скобок)-на фиг.2 - блок-схема устройства управления процессора БПФ; на фиг.З функциональная схема устройства управления. . Устройство содержит оперативную память 1, арифметический блок 2, постоянную память 3, устройство управления 4 (фиг.2), счетчик.5, сдвиговый регистр 6, группу элементов И 7 сдвиговый регистр 8, коммутатор кода 9, элементы ИСКЛЮЧАЩЕЕ ИЛИ 10 и 11, триггер режима 12, генератор такто- вых импулЬсов 13, коммутатор кода 14, элементы И 15 и 16 (фиг.З). Процессор БПФ работает в двух режимах: обработка двух комплексных последовательностей данных; обработка четьфех действительных последовательностей данных. Режим работы процессора задается потенциалом на входе устройства XI. О соответствует обработПотенциал1 - четьфех ке двух, а потенциал массивов данных. Реашм 1 - обработка двух комплекс ных последовательностей данных. В оперативную память 1, которая разбита на две половины, записываютс исходные данные таким образом, что в первую половину памяти 1 данные заносятся в двоично-инверсном порядке, а во вторую половину - в прямом порядке. В постоянной памяти 3 записаны значения векторов поворота, 34 которые выбираются из памяти по кодам адресЬв, формируемых устройством управления 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 и 2 заключается в том, что при работе в режиме 2 для восстановления спектров исходных сигналов х(п) и у(п) на положительных частотах требуется дополнительная итерация. Спектры восстанавливаются соглаьно соотношениям:(n) I ReCz(n).+Z(N-n) (n)J I (n)-Z(N-n) (n) 5 (n)+Z(N-n) (n) (n)-Z(N-n). Основньм устройством процессора БПФ, в котором закодирован алгоритм вычислений, является устройство упра .ления 4. На первом выходе У1 устройства 4 управления формируются адреса операндов, выбираемых из памяти 1. На втором выходе У2 - импульсы синхронизации арифметического блока 2. На третьем выходе УЗ - адреса операндов выбираемых из постоянной памяти 3. На выходе У4 формируются команды для режима работы арифметического блока 2, т.е. вьтолняется алгоритм БПФ с прореживанием по времени или частоте Импульсы на выходе У5,пятом выходе устройства 4 управления, определяют часть памяти 1, откуда выбирается информация, а на шестом вькоде У6 формируются импульсы, которые разрешают запись или считывание информации из оперативной памяти 1. КоммуТа торы кода 9 и 14 представляют собой набор элементов ИСКЛЮЧАНЩЕЕ ИЛИ, пер вые входы каждого элемента являются входом коммутаторов кода, а вторые входы каждого элемента объединены и являются вторым входом коммутаторов кода 14 и 9. При подаче на второй вход потенциала О информация прохо дит через коммутатор без изменения, а при потенциале 1 инвертируется. В первый выход счетчика 5 объединяют ся выходы всех его разрядов, исключа второй и третий разряды. Выходы счет чика 5 и регистра 8 подключаются к группе элементов И 7, таким образом, что входы одного элемента И соединены с выходами равнозначньгх разрядов счетчика 5 и регистра 8. Работу устройства 4 управления () поясняет таблица, на которой показано формирование команд устройством 4 управления на последней итерации восьмиточечного БПФ. Устройств 4управления работает в двух режимах: обработка двух комплексных последовательностей данных; обработка четырех действительных последовательностей данных. При обработке двух комплексных последовательностей на вход устройства XI (первьш вход второго элемента И 16) подается потенциал О. В исходном состоянии счетчик 5, регистры 6 и В обнулены,триггер режима 12 установлен в нулевое состояние. На всех выходах устройства 4 управления йотенциалы соответствуют уровню О. Элемент И 16 блокирует прохождение информации на второй вход коммутатора 14, на нем устанавливается потенциал О, и через коммутатор 14 информация проходит без изменения. Запускается генератор 13, и начинается работа устройства 4 управления и процессора в целом. I . Тактовые импульсы поступают на вход счетчика 5, начинается формирование команд для выполнения реализуемого алгоритма БПФ. Информация о состоянии разрядов счетчика 5 переписывается по входу в регистр 6. Выходы второго и третьего разрядов счетчика 5анализируются с помощью элемента 10 ИСКЛЮЧАЩЕЕ ИЛИ. Если состояние разрядов различное (см.таблицу), формируется импульс сдвига информации на один разряд в сторону младших разрядов. Если состояние разрядов одинаковое, то импульс сдвига не формит руется. Второй выход сдвигового регистра 6 (выход со стороны младших разрядов) соединен с входом, и при поступлении импульса сдвига с выхода элемента 10 из кода адреса 001 на выходе сдвигового регистра 6 получается код 100, который через коммутатор кода 14 поступает на выход У1 устройства 4 управления. Одновременно на выходе УЗ формируются коды адресов информации, выбираемой из постоянной памяти 3. Группа элементов И 7 в зависимости от выполняемой итерации БПФ, определяемой состоянием разрядов сдвигового регистра 8, преобразуетинформацию с первого выхода счетчика 5 в коды адресов для выбора информации из памяти 3 (см. таблицу). Выборкой информации из памяти 3 управляет младший разряд счетчика 5, подключенный к входу коммутатора 9. О в младшем разряде счетчика с.оот7ве -ствует выборке значения косинуса 1 синуса, путем инверсии кода адресов косинуса. Признак части памяти 1 для выбор и записи информации формируется с помощью элементов ИСКЛЮЧАЩЕЕ ИЛИ 10 и 11. О на выходе У5 соответст вует обращению к первой половине па мяти 1, а 1 - к второй половине (см.таблицу). Третий разряд счетчик 5 определяет режим записи или считы вания информации из оперативной памяти 1 - выход У6 (см.таблицу, О соответствует считыванию информации 1 - записи). После заполнения сче чика 5 (вьтолнена итерация БПФ) 1 последнего разряда счетчика 5 заносится со стороны старших разрядов в сдвиговый регистр 8, и начинается следующая итерация вычислений. Одно временно с занесением в регистр 8 единицЬ триггер 12 режима меняет свое состояние. На каждой нечетной итерации информация проходит на выход У5 через элемент 11 без изменекий, а на четных итерациях (на выхо триггера 12 - 1) инвертируется. Необходимость менять адресацию- в за висимости от итерации вычислений обусловливается алгоритмом вычислеНИИ (см. фиг.1), Информация на выходе У4 соответствует различным режимам работы ари(| 1етического блок /2. . : I . Арифметический блок 2 работает двух режимах. При потерциале, соответствующем уровню О, на выходе У4 устройства 4 управления арифметический блок реализует алгоритм с прореживанием по времени и выполняе операции в соответствии с выражением , Х|, + Yi , а при потенциале 1 на выходе У4 реализуется алгоритм с прореживанием по частоте и выполняются операции хг- XI-H Yi , (4) (Xt - Yi)-W p где X-t,Y - операнды на i-ой итерац W - комплексный вектор noiBo- рота. Как видно из приведенного на фиг.1 реализованного алгоритма, на каждой итерации вычислений порядок выбора операндов из оперативной памяти 1 остается.постоянным. Постоянным остается и порядок записи информагщи в память 1 после обработки в арифметическом блоке 2. Следует отметить, , что порядок выбора информации из памяти 3 при реализации алгоритмов с прореживанием по частоте и по времени совпадает. При обработке четырех действительных массивов данных на вход XI подается потенциал, соответствующий уровню 1. Входные последователь-, ности данных представляются в виде (1), и начинается обработка информации по безызбыточиому алгоритму. Работа устройства 4 управления при реализации безызбыточного алгоритма отличается уем, что посЛе завершения вычислений Требуется дополнительная итерация для восстановления спектров сигналов в соответствии с выражениями (2). Из приведенных соотношений видно, что для получения кода адреса операнда X() необходимо проинвертировать код адреса операнда Х(о) Для этого служит коммутатор кода 14, который включается в работу лишь на дополнительной итерации. Единичный потенциал на входе XI разблокирует второй элемент И 16. После завершения последней итерации вычислений 1 записывается в сдвиговый регистр 3, и он полностью заполняется единицами. На выходе элемента И 16 устанавливается потенциал 1 и разрешается прох(хкдение информации на второй вход коммутатора кода 14. При подаче на другой вход коммутатора 14 потенциала О на выходе У1 форми руется код адреса ХМ а гфи подаче потенциала 1 - код адреса ) X(H-V4). Предлагаемое устройство просто по своей конструкции. Область его применения расширяется за счет возможности одновременной обработки четырех массивов действительных данных.

. Продолжение таблицы

О 8 и 12 2 10 6 Iff I 9 5 13 3 11 7 1

О 1 2 3 5 6 7 В 9 10

ff 12 /J 1f 1

фие1

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

Фиг.5