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

тв 32 ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ПИСАНИЕ ИЗ(54) (57) УСТРО)1 СтвО ДЛЯ ФОР 11 ИРОВАНИЯ АДРЕСОВ ОПЕРАНДОВ ПРОЦЕССОРА БИСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее, регистр итерации, выходы разрядов которого соединены с входами разрядов счетчика и соответственно с первьп)е входами элементов ИЛИ группы, выходы разрядов счетчика соединены соответственно с вторыми входами элементов ИЛИ, первым инФормационным входом коммутатора адреса и соответственно с входамн разрядов первого регистра, выход которого соединен с вторым инФормационным входом коммутатора адреса, третий информационный вход которого подключен к выходам элементов 1 СП 1 группы, а выход коммутатора адреса является выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены второй регистр, мультиплексор, два триггера, шесть элементов И, дна элемента ИЛИ и два элемента НЕ, причем выход старшего разряда регистра итераций подключен к перному входу первого элемента И и входу первого элемента НЕ,выход которого подключен к первомувходу второго. элемента И, ныход которого соединен с первым входом третьего элемента И, выход которого под.ключен к первому входу первого элемента ИЛИ, второй вход которого подключен к выходу четвертого элементаИ, первый вход которого объединен спервым входом пятого элемента И ивходом первого разряда адреса коммутатора адреса, ныход второго элемента НГ соединен с вторыми входамитретьего, четвертого и пятого элементов И и первым входом шестого элемента И, выход которого соединен спервым входом второго элемента ИЛИ,второй вход которого подключен к выходу пятого элемента И, выход первого триггера подключен ко вторым входам первого и второго элементов И итактовому входу второго триггера,выход которого соединен с вторымвходом шестого элемента И и управляющими входаьи счетчика первого ивторого регистров, выходы элементовИЛИ соединены с инФормационными входами мультиплексора и соответственно с входами разрядов второго регистра, выходи разрядов которого сое"динены с четвертым информационнымвходом коммутатора адреса, входы второго и третьего разрядов адреса которого соединены с выходами соответственно второго и первого элементовИЛИ выход первого элемента И подключен к управляющему входу коммутатора адреса, третий вход четвертого элемента И, третий вход пятого1056207 элемента И и управляющий вход муль"типлексора образуют вход заданияобъема преобразования устройства,третьи входы третьего и шестого элементов И объединены и вместе с входом второго элемента НЕ и первым вхоИзобретение относится к вычислительной технике, а конкретно к устройствам для выполнения быстрого преобразования Фурье (БПФ), которые могут использоваться для построения циФровых анализаторов спектра, применяемых визмерительной техчике, радиолокации, технике связи и др.Извесно индексное устройство процессора БПФ дпя адресации операндов 10 и тригонометрических коэМициентов, содержащее два двоичных счетчггка, итеративный сдвиговый регистр и ло - гическое устройство управления приращением счетчиков 1, 15Однако это устройство не способно выполнять безызбыточные алгоритмы БПФ, кроме того, в нем применяется лишь частичное совмещение операций обращения к оперативкой памяти и 20 арифметических операций, что снижа" ет быстродействие процессора БПФ,Известгго также индексное устройство процессора БПФ, содержащее два25 двоичных счетчика с входной логикой, итерационный сдвиговый регистр, два логический блока и форгирователь номера модуля, предназначенный для одновременной адресации двух операн - дов 2 .30Однако это устройство не позволяет достичь высокого быстродейст-, вия из-за последовательного выполненения арифметических операций и операций обращения к памяти. 3,.Известен также блок формирования адресов для устройства, реализующего быстрое преобразование Фурье, содержащий счетчик, узел реконфигурации счетчика, управляемый признака ми итерации, .регистр задержки адреса, подключенный к выходу счетчика, группу элементов И.И, соединенную с выходами счетчика и признаками итедом пятого элемента И образуют вход задания режима устройства, тактовый вход первого триггера является тактовым входом устройства,а инФормационный выход мультиплексора соединен с управляющим входом регистра итераций,рации, регистр задержКи адреса,подключенный к выходу счетчика, группуэлементов ИЛИ, соединенную с выходами счетчика и признаками итерации,выход группы элементов ИЛИ соединенс одним из входов блока выдачиггнормации, другие входы которогосоединены с выходом счетчика и с выходом регистра Устройство позволяет реализовать безызбыточный алгоритм БПФ .3.Однако известное устройство непозволяет достичь максимально возможного быстродействия, так как операции обращения к памяти и выполнение арифметических операций разделены во времени.Цепью изобретения является повышение быстродействия,Поставленная цель достигается тем, что в устройство для формирования адресов операндов процессора быстро" го преобразования Фурье, содержащее регистр итерации, выходы разрядов которого соединены с входами разрядов счетчика и соответственно с,первыми входами элементов ИЛИ группы, выходы разрядов счетчика соединены соответственно с вторыми входами элемента ИЛИ, первым информационным входом коммутатора адреса и соответственно с входами разрядов первого регистра, выход которого соединен с вторым информационным входог г ког гмутатора адреса, третий .информационный вход - которого подключен к выходам элементов ИЛИ группы, а выход коммутатора адреса является выходом устройства, в него введены второй регистр, мультиплексор, два триггера,шесть элементов И, два элемента ИЛИ и два элемента НГ, причем выход старше. - го разряда регистра итераций подклю"Э1056 чеи к первому входу первого элемента И и входу первого элемента НЕ, выход которого подключен к первому входу второго элемента И, выход которо.го соединен с первым входом третьего элемента И, выход которого подключен к первому входу первого элементаИЛИ, второй вход которого подключен к выходу четвертого элемента И, первый вход которого объединен 1 О с первым входом пятого элемента И и входом первого разряда адреса коммутатора адреса, выход второго,элемен" та НЕ соединен с вторыми входами третьего, четвертого и пятого эле ментов И и первым входом шестого элемента И, выход которого соединен с первым входом второго элемента 11 Л 11, второй вход которого подключен к выходу пятого элемента И, выход первого 20 триггера подключен к вторым входам первого и второго элементов И и тактовому входу второго триггера, выход которого соединен с вторым входом шестого элемента И и управляющими г 5 входами начетчика, первого и второго регистров, выхсды.элементов ИЛИ соединень с информационными входами мультиплексора и соответственно с входами разрядов второго регистра, выходы разрядов которого соединены с четвертым информационным входом коммутатора адреса, входы второго и третьего разрядов адерса которого соединены с выходами соотнетствен35 но, второго и первого элементов ИЛИ, выход первого элемента И подключен к управляющему входу коммутатора адреса, третий вход четвертого элемента И, третий вход пятого элемен 40 та И и управляющий вход мультиплексора образуют вход задания объема преобразования устройства, третьи входы третьего и шестого элементов И объединены и вместе с входом второго элемента НЕ и первым входом пя 45 того элемента И образуют вход задания режима устройства, тактовый вход первого триггера является тактовым входом устройства, а информационный выход мультиплексора соединен с управляющим входом регистра итераций,На Лиг,изображена блок-схема устройства для Аормирования адресов; на Лиг, 2 - временные диаграммы ра боты устройства; на Аиг 3 - подробная функциональная схема узла управления .выдачей адресов. 207 4 Устройство для Аормирования адре"сон операндов процессора БПФ состо-ит из двоичного счетчика 1 с входной логикой 2, группы элементов ИЛИ3, регистра 4 итераций, первого регистра (задержки адреса) 5, коммутатора 6 адресов, второго регистра(узла выбора размера) 8, узла управления ныдачей адресов 9 входазадания размера преобразования 1 О,тактового входа 11, входа заданиярежима 12, индюрмационного выхода 13устройства.Узел управления выдачей адресов(Лиг, 3) состоит из двухкаскадногоделителя частоты синхроимпульсов натриггерах 14 и 5, первый нз которых 14 соединен с входной шиной синхроимпульсов первого элемента И 16,второго элемента И 17 (выход старшего разряда 18 регистра 4 итераций),первый элемент НЕ 19, третьего элемента И 20, четвертого элемента И 21входа БИФ 12- 1 входа задания режима12, второго элемента НЕ 22, входа"Считывание" 12-2 входа задания режима 12, пятого, элемента И 23, шестогоэлемента И 24, тактового выхода 25,входа "Запись" 12-3, входа заданиярежима 12, выхода старшего разряда26 выходного кода, первого элементаИЛИ 27, выход второго разряда 28 выходного кода, второго элемента ИЛИ29, ныход младшего разряда 30 выходного кода управляющего выхода 31.Устройство работает следующим образом,Предварительно по входу 1 О устанавливается размер преобразования, например 1024, 512 или 256 точек. Затем ло входу 12 устанавливается режим работы блока адресации путем подачи единичного потенциала на однуиз линий 12-1-2-3. При влкючении режима БПФ подан потенциал на линию2-1, При этом входные синхроимпульсы поступают на входную шину 11 узлауправления выдачей адресов 9, пройдя через делитель на триггерах 14 и 15 с частотой в 4 раза меньшей входной. Синхроимпульсы ( фиг.2 а, б, фиг.3) поступают на входную логику 2 счетчика 1,который изменяет свое состояние с каждым входным синхроимпульсом, причемодин из разрядов счетчика 1 блокируется с помощью входной логики, управляемой регистром 4, который произ 1056207водит сдвиг "1" с окончанием каж" дой итерации. На первой итерации блокируется старший разряд счетчика 1, на второй - предпоследний разряд и т.д, Блокируемый разряд счет чика остается в нулевом состоянии, а выход.предыдущего разряда подается мимо блокируемого в последующие каскады. Параллельный код с выхода счетчика 1 поступает на группу элементов ИЛИ 3, один из входов которых соединен с одним из разрядов счетчика 1, а другой вход с соответствующим разрядом регистра 4. На выходе каждого элемента ИЛИ получается логическая сумма одноименных разрядов счетчика 1 и регистра 4. В результа-, те этого коды на выходах счетчика 1 и группы элементов ИЛИ 3 отличаются на единицу в разряде, определяе мом номером текущей итерации и об" разуют адреса пар операндов согласно алгоритму БПФ. Для задержки адресов операндов на один такт используются регистры задержки 5 и 7, подключенные к выходу группы элементов ИЛИ 3 и счетчика 1, Задержка адресов используется для совмещения операций обращения к оперативному запоминающему устройству (ОЗУ) и ЗО ариАметических операций, что иллюстрируется на дыг. 2, В начале каждого цикла, в течение которого выполняется одна .базовая операция алгоритма БПФ, производится считывание первого и второго операнда по адресам А и А Это производится при наличии "0" на выходах триггеров 14 и 15 делителя и при "0" на входе 18 элементов НЕ 19, "1" на линии БПФ 12-1, при этом на линиях 26, 28 и 30 выходного кода узла управления выдачей адресов присутствует код 000, так как элемент И 21 закрыт нулевым потенциалом с выхода триггера 15, а 45 элемент. И 24 - нулевым потенциалом линии "Запись" 12-3. При этом к выходу 13 устройствакоммутатором 6 подключается выход двоичного счетчика 1, т.е. адрес первого операнда,50 С поступлением первого синхроимпульса на вход 11 первый триггер 14 делителя устанавливается в "1", а второй - 15 остаетсяв "0", что приводит к появлению на выходе узла управления выдачей адресов кода 001, при этом к выходу 13 устройства подключается адрес второго операнда, образованный на выходе группы элементов ИЛИ 3. ОЗУ при этом находится в режиме "Считывание" и выдает операндыпо адресам А 1, и А на вход ариАметического устройства процессора БПФ,и пока происходит выполнение арифметических операций блок адресациивыбирает адреса А;. и А1, по которым производится запись результатов арифметических операций с операндами, выбранными из ОЗУ в предыдущем цикле, Адреса А 1и А;хранятся в регистрах 5 и 7 и подключаются к выходу коммутатора 6 при подаче на вход 11 второго и третьегосиихроимпульсов, выходной код блока9 имеет при этом вид 010 и 011 соответственно, С приходом четвертогосинхроимпульса на выходе 25 появляется выходной синхроимпульс, переводящий счетчик 1 в новое состояние, а триггеры 14 и 15 устанавливаются в нулевое состояние. При этомк выходу 13 подключен выход счетчика 1, с приходом пятого синхроимпуль"са на вход 1 на выход 13 подключается выход группы элементов ИЛИ 3и т.д, Кроме этого, каждый четвертыйвходной синхроимпульс вызывает переписывание содержимого счетчика 1 игруппы элементов ИЛИ 3 в регистры 7и 5 соответственно, т,е, при этом задерживаются адреса операндов предыдущего цикла, В начале следующегоцикла производится считывание из ОЗУоперандов А +и А, , к этому моменту заканчиваются ариАметические операции и подключение к выходу 13 адресов А и Ащ, хранимых в регистрах5 и 7 позволяет произвести результат вычислений над операндами по вд"ресам их первоначального хранения.Такая последовательность выполнения"базовых операций сохраняется до концатекущей итерации, определяемой выбранным размером преобразования с по"мощью мультиплексора 8, на инЫрмационные входы которого поданы старшие разряды с выхода группы элементов ИЛИ 3, В зависимости от кода размера, подаваемого на другой входблока Я, признаком сдвига регистра8, т,е, моментом окончания итерациислужит появление "1" на одном изстарших разрядов группы элементовИЛИ 3, С началом следующей итерациипорядок проведения адресации операнфдов происходит аналогично описанному, только изменяются значения адресов, так как происходит сдвиг "1"в регистре 4 и соответствующее перемещение "0" в блокируемом разрядесчетчика 1. После выполнения всехобычных итераций согласно безыэбыточному алгоритму ВПФ образуется дополнительная итерация, в которой адреса пар операндов должны быть симметричны относительно М/2, где 1 - число точек преобразования. Известно,что симметричные адреса образуют дополнением одного адреса до И и дляих получения достаточно образоватьдополнительный код к известномуадресу. С этой целью в устройстве выходстаршего разряда регистра 4, принимавоФй значение,"1" во время действия дополнительной итерации, подключен к одному из входов узла управления выдачей адресов, а именно квходу 18 элемента И 17 и элемента 11 Е9, при этом выходом элемента НЕ 19запирается элемент И 16, запрещаю-щий прохождение на выходную шину кода блока 9 выхода первого триггера14, однако "1" на выходе этого триггера проходит открытый элемент17и потенциал на управляющей линии 31вызывает появление дополнительногокода на выходе 13 от кода, поданного на вход. Последовательность кодовна выходной шине блока 9 будет следующей за цикл: 000, 000, 010, 010,а вид выходной информации на выходе13 таким;состояние счетчика 1; дополнительный код счетчика 1; состояниерегистра задержки 7; дополнительный,код регистра 7,Таким образом, в первой половинецикла производится считывание операн Одов с адресами А и А , а во второй половине цикла запись результатов арифметических операций над аналогичными операндами из предыдущегоцикла.45В течение цикла проводится чередование адресов считывания одних операндов .с адресами записи операндовиз предЫдущего цикла, что позволяетпроводить арифметические действиянад операндами одновременно с обращением к ОЗУ,Перевод блока адресации в режимзаписи входных счетчиков производится подачей единичного потенциалана линию "Запись" 12-3 входа задания 55режима 12, что приводит к появлению"1" на выходе старшего разряда 26выходного кода узла управления вьщачей адресов 9. В зависимости от кода размера на входах 10-1 и 10-2 выходы 28 и 30 принимают состояния "О"или 1 , а выходной кол, узла 9 принимает следующие состояния , 100 1 0 1 1 1 0 и 1 1, Так как входные отсчеты при записи должны поступать в двоично-ин версном порядке , к индюрмационному входу коммутатора 6 адре со в, выходы счетчика 1 подключены в двоично-ин вер сном порядке , т . е . к входу мп адще го разряда коммутатора 6 под" ключен старший разряд счетчика 1 , к входу второго разряда - предпоследний разряд счетчика и т . д . К другому информационному входу коммутатора 6 подключены выходы счетчика 1 в двоично-инвер сном порядке , но сдвинутые на 1 разряд влево , т , е . вход младше го разряда коммутатора 6 соединен с предпоследним старшим разрядом счетчика 1 , а вход предпоследнего старше го раэ ряда коммутатора 6 соединен с младшим разрядом счетчика 1К информационным входам коммутатора 6 также подсоединены в двоично-инвер сном порядке сдвинутые на 2 и на 3 разряда выходы счетчика 1, Этим дости гается уменьшение размера прео бр азо вания при переходе от пятого до восьмого значения выходного управляюще го кода узла 9 .Каждый четвертый иэ синхроимпульсов на входе 1 вызывает увеличение на содержимого счетчика 1, при этом элементы И 20 и 21 узла управления выдачей адресов 9 закрыты нулевым потенциалом с линии БПФ 12-1 и выходной код узла 9 на линиях 26, 28 и 30 определяется .только кодом размера, подаваемым в порядке предварительной установки. Режим "Запись" заканчивается в момент переполнения счетчика 1 и устройство переходит в режим ожидания.В режиме "Считывание" на вход 12-2 подается единичный потенциал, который после инвертирования элементом ПЕ 22 запирает элементы И 20, 21, 23, 24 и выходной код узла 9 в режиме "Считы" ванне" постоянно составляет 000, т.е. к выходу 13 устройства постоянно подключен счетчик 1, который увеличивает свое содержимое с каждым синх- роимпульсом, поступающим на его вход, при этом на выходе 13 устройства образуется последовательность возрастающих от 0 до Мадресов, что со 105620 100 ответствует выбранному алгоритму БПФс двоично-инверсным порядком данныхна входе и прямым - на выходе, Регистр 4 итераций в режиме "Запись"и "Считывание" не изменяет своегосостояния, поэтому входная логика 2не производит блокировку разрядовсчетчика 1, сохраняя естественныйпорядок его счета,Таким образом, данное устройство для Аормирования операндов процессора БПФ способно производить адресацию записи входных выборок в ОЗУ,адресацию считывания коэААициентовфурье иэ ОЗУ, а также адресацию операндов в процессе вычисления козААициентов Фурье. В последнем режиме данное устройство позволяет вычислять безызбыточные алгоритмы БПФ ипроизводить вычисления с высокойскоростью, так как выбор операндовиз ОЗУ или запись в ОЗУ производится одновременно с выполнением арифметических операций с другими первидамиеБаренко Составител Техред Л,Пи топ А, Галанд Заказ 9308/43ВНЕ и отк ытии наб. д. 4 п 1130"Патент", г. Ужгород, ул. Проектная, 4 лиал П Тираж 706 Государственного елам изобретений Москва )КР овКорректор А,ЗимокосовПодписноеа СССР