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

ме ФОРМИРОВАНИЯЫСТРОГО ПРЕОБк вычислиь испольы изиро налфу ГОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМПРИ Гкнт СССР ОПИСАНИЕ СКОМУ СВИДЕТЕЛЬСТВ(54) УСТРОЙСТВО ДЛЯАДРЕСОВ ПРОЦЕССОРА БРАЗОВАНИЯ ФУРЬЕ(57) Изобретение относитсятельной технике и может б тзовано при построении специ Изобретение относится к вычислительной технике и может быть использовано в составе процессора быстрого преобразования Фурье (БПФ) или быстрого преобразования в базисах ортогональных функций, используемых в. спектроанализаторах, генераторах широкополосного случайного процесса, синтезаторах речевых сигналов и т,д.Бель изобретения - расширение области применения устройства путем обеспечения возможности адресации действительной последовательности отсчетов длиной 2 (З = 1, 2, , М).На фиг, 1 представлена функциоьная схема устройства; на фиг.2 нкциональная схема блока модификаванных процессоров БПФ и других ортогональных преобразований. Цель изобретения - расширение области применения устройства за счет обеспечения возможности адресации действительной последовательности отсчетов длиной 21, С этой целью в устройство для формирования адресов процессора БПФ, содержащее блок управления, реверсивный счетчик, счетчик, регистр, И мультиплексоров данных, группу элентов И, узел постоянной памяти, введены блок модификации адреса, блок сравнения, первый и второй мультиплексоры, Введение новых блоков и связей позволило выполнять адресац для вычисления БПФ выборки данных произвольной длины, кратной двум.1 з.п.ф-лы, 4 ил 4 табл. ции адреса; на фиг, 3 - функциональная схема блока микропрограммного управления; на фиг, 4 - блок-схема алгоритма работы блока микропрограммного управления.Устройство для формирования адресов процессора БПФ (фиг. 1) содержит блок, 1 микропрограммного управления, реверсивный счетчик 2, счетчик 3, группу элементов И 4, группу1499373 Составитель Е, Румянцеактор Б. Петраш Техред Л.Сердюкова,Шекм орре аказ 469649 Тираж 668 писно оизводственно-издательский комбинат "Патент", г. Ужгород, ул. Гагари ВНИИПИ Государственного комитета113035, Москва, Ж 4 Ьг Ф изобретениям и открытиям при ГКНТ СССР Раушская наб., д. 4/53 149937 из групп элементов И 13 и элементов ИЛИ 14, сумматор 15 и дешифра-тор 1 б.Блок 1 (фиг, 3) содержит счетчик 17 адреса, блок 18 памяти микропрограмм, регистр 19 микрокоманд, мультиплексор 20 признаков, первый элемент И 21, второй элемент И 22 и элемент И-НЕ 23, 1 ОУстройство работает следующим образом.Длина выборки в двоичном коде за" дается на входе устройства "Длина выборки. На входе признака распо ложения данных в выборке "Расположе" ние данных" задается признак прямой (М 1) или двоично-инверсной (М = О) адресации. Например, обрабатывается выборка данных длиной 1024 отсчета. 20При этом двоичный код 001010,целое двоичное И-разрядное число, равное 1 оя 1024, поступает на адресные входы мультиплексора 10, На выходе последнего формируется признак (О или 1), если код числа на реверсивном счетчике 2 совпадает с кодом длины последовательности. Для рассматриваемого случая (И = 1024) номер выхода - десять (одиннадцатый выход счетчи ка 2 - нумерация идет от нуля. Появление единицы на выходе мультиплексора 10 сигнализирует об окончании вычислений по слою алгоритма БПФ. По данному сигналу в блоке 1 на его 35 третьем выходе вырабатывается сигнал сброса реверсивного счетчика 2, а в счетчик 3, определяющий номер слоя, сигналом с шестого выхода блока 1 добавляется единица. При этом осу- . 40 ществляется переход к вычислениям по очередному слою.Для каждого слоя алгоритма БПФ каналы мультиплексоров 5 коммутиру ются, как причедено в табл. 1.Каждьй мультиплексор 5 имеет дваадресных входа А 1 и АО. Если сформирован код А 1 = 0 и АОО, то на выход коммутируется канал ХО, еслиА 1 О, а АО = 1, на выход коьщутируется канал Х 1, если А 1 = 1, а АО =,О, на выход коммутируется каналХ 2, если на А 1 1,и АО щ 1, на выход 55коммутируется канал ХЗ (фиг. 1),Для этого прошивка блока 7 памятивыглядит согласно табл. 2. 3 4По окончании вычислений по основ ному алгоритму (для выборки 1024 - десять слоев: О, 1, 2, , 9) устройство переходит на адресацию в специальный слои (для рассматриваемого примера слой 10). Наличие перехода в специальный слой сигнализируется блоком 8 сравнения, на вторую группу входов которого подается код номера текущего слоя со счетчика 3, а на первую - код "Длина выборки". Окончание вычислений по специальному слою алгоритма БПФ определяется мультиплексором 11. Для данного муль" типлексора 11 информация на выходе смещена на один разряд.(фиг. 1) по отношению к мультиплексору 10, что соответствует характеру вычислений в специальном слое алгоритма БПФ, При наличии сигнала логической еди ницы на пятом выходе блока 1 блок 7 постоянной памяти отключается и на его выходах появляются уровни логической единицы, На адресных входгх АО, А 1 всех мультиплексоров 5 появляются уровни логической единицы. Этим достигается коммутация на выход информации с информационных входов ХЗ, подключенных к инверсным входам реверсивного счетчика 2. При наличии уровня логического нуля на пятом выходе блока 1 происходит формирование адресов аналогично нулевому слою алгоритма БПФ, так как блок 7 постоянной памяти включен и на его адресные входы поступает код 00 О. Управление работой устройства осуществляется блоком 1. Счетчик 17 адреса с возможностью параллельного занесения информации работает как регистр адреса микрокоманды. Выходы его подключены к входам блока 18 постоянной памяти, в котором записана микропрограмма работы всего устройства, Считанная из блока 18 постоянной памяти микрокоманда запоминается в регистре 19 микрокоманд, Выбор адреса следующей микрокоманды осуществляется путем добавления единицы к содержимому счетчика 17 адреса, либо путем условного или безусловного перехода к требуемому адресу занесения в счетчик адреса 17 парал лельного кода адреса перехода. Адрес перехода определяют разряды микро- команды 0-Я 5 в поле адресов перехода. Переход инициируется сигналом, 5 1499373возникающим на выходе мультиплексора 20 признаков.Сигнал на выходе мультиплексора 20 признаков появляется в том случае, если в поле признаков перехода Я 6, Я 7 сформирован код, отличный от "11", а на адресных входах муль= типлексора 20 признаков - код условия перехода ХО-ХЗ (табл. 3).Разряды 18 и Я 9 регистра 19 микрокоманд стробируются с помощью элементов 21 и 22 и являются соответственно первым и вторым выходами блока 1. Выходы разрядов 010, , Я 14 регистра 19 микрокоманд являются соответственно пятым, четвертым, третьим, шестым и седьмым выходами блока 1, Выход элемента И-НЕ 23 является восьмым выходом блока 1. Алгоритм работыустройства для формирования адресов представлен на граф-схеме алгоритма (фиг. 4), кодировка микрокоманд которого представлена в табл. 4. Ка фиг. 4 введены следующие обозначения:"+ 1 СТ 1" ("1" в столбце 08 табл. 4) соответствует формированию импульса на первом выходе блока 1, подключенном к суммирующему входу реверсивного счетчика 2;"-1 СТ 1" ("1" в столбце 19 табл.4) соответствует Формированию импульса на втором выходе блока 1, подключенном к входу вычитания реверсивного счетчика.2;"Сброс СТ 1" ("1" в столбце (12 табл. 4) соответствует формированию потенциального сигнала на третьем выходе блока 1, подключенному к выходу сброса реверсивного счетчика 2;"Зп. КС" ("0" "1" в столбце Я 11 табл. 4) соответствует Формированию потенциального сигнала на четвертом выходе блока 1, подключенном к синхровходу регистра 6;"дпч" ("0" в столбце 010 табл. 4) сиГнал, вырабатываемый только в специальном слое алгоритма БПФ, соответствует формированию потенциального сигнала на пятом выходе блока 11, подключенном к вторым входам ряда 4 элементов И;"+1 СТ 2" ("0" в столбце (13 табл. 4) соответствует Формированию потенциального сигнала на шестом выходе блока 1, подключенном к суммирующему входу счетчика 3;"Сброс СТ 2" ("1" в столбце (14табл. 4) соответствует формированиюпотенциального сигнала на седьмомвыходе блока 1, подключенном к вход,сброса счетчика 3.Алгоритм формирования адресовследующий.1. Выполняются микрокоманды с адресами Ои 1 (десятичный эквивалентдвоичного адреса). В этих микрокомандах осуществляется сброс счетчиков 2 и 3 (сигналы "Сброс СТ 1" и"Сброс СТ 2"), чем устройство подготавливается к работе.11. Выполняется микрокомандас адресов 2. формируется сигнал"Зп.КС", чем осуществляется записьв регистр 6 адреса первого операнданулевой пары операндов (адрес 00000),111. Выполняется микрокоманда садресами 3-5. В которых формируютсясигналы "+1 СТ 1", а затем и "Зп Ы",чем осуществляется запись в регистр6 адреса второго операнда нулевойпары операндов (адрес 00001).Далее эти операнды могут обрабатываться арифметическим устройством,причем операнды нулевой пары требуют тривиального умножения на единицу, поэтому для своей обработки требуют меньшего времени, чем операндыостальных пар. Это используетсяпри входе в циклический участок алгоритма, когда время на обработку нулевой пары уменьшено до трех тактов.1 Ч. Выполняются микрокоманды с адресами 6-8Они аналогичны микро- командам 3-5. В результате их выполнения в регистр 6 заносится адрес первого операнда первой пары операндов (000010)Ч, Выполняются микрокоманды с адресами 9-11. Они также аналогичны микрокомандам с адресами 3-5. В результате их выполнения в регистр 6 заносится адрес второго операнда (000011). Ч 1. Выполняется циклический участок микропрограммы, содержащий микрокоманды с адресами 12-23. В данном участке. обрабатывается в арифметическом устройстве и-я пара операндов (в момент входа 1-я пара, адресованная микрокомандами с адресами 6-11), За время обработки п-й пары в арифметическом устройстве необходимо40 адресовать (и)-ю пару, обработанную в арифметическом устройстве впредыдущем цикле (в момент входа вциклический участок 0-я пара) и95(и+1)-ю пару, которая будет обрабатываться в следующем цикле,Микрокоманды с адресами 12-14три раза выполняют микрооперацию"Зи КС" в микрокоманде с адресом 14,чем осуществляется формирование адреса первого операйда (и)-й пары(на момент входа в циклический участок адреса 00000).15Микрокоманды с адресами 15-17 аналогичны микрокомандам с адресами3-5 и осуществляют формирование адреса второго операнда (и)-й пары(на момент входа в циклический участок адрес 00001).Микрокоманды с адресами 18-20три раза выполняют микрооперацию"Зи КС" в микрокоманде 20. Этщ осу 25ществляется формирование адреса первого операнда (и+1)-й пары (на момент входа в циклический участок адрес 0000100),Микрокоманды с адресами 21-23аналогичны микрокомандам с адресами3-5 и осуществляют формирование адреса второго операнда (и+1)-й пары(на момент входа в циклический участок адрес 0000101).Таким образом, при выполнении циклического участка происходит адресация (и)-й пары для записи в память, (и+1)-й пары для считыванияиэ памяти и обработки в следующемцикле.В микрокоманде с адресом 14 анализируется условие ХО, При попытке сформировать адрес для записи в памятьпервого операнда (и)-й пары, не принадлежащего п ространству адресов слояалгоритма БПФ для данной выборки, условие ХО становится равным единице;При этом происходит условный переходк выполнению микрокоманды с адресом24, Ясли первый операнд (пара операндов) принадлежит пространству, топерехода не происходит и циклическийучасток повторяется снова.711. Выполняются микрокоманды садресами 24 и 25. В них осуществляется формирование операций "СбросСТ 1" и "+1 СТ 2", Добавление единицыв счетчик 3 означает формирование следующего слоя алгоритма БПФ. В микрокоманде 25 анализируется условиеХ 1, которое сигнализирует о переходе в специальный слой алгоритма БПФ.Если нет перехода в специальныйслой алгоритма БПФ, то устройствоначинает обрабатывать следующий слойпутем выполнения микрокоманды с адресом 2, При наличии перехода вспециальный слой осуществляется переход к выполнению микрокоманды садресом 26, т.е, вход в участок алгоритма, осуществляющий формированиеадресов операндов специального слоя.Ч 111. Выполняется микрокомандас адресом 26, в которой формируютсямикроопераЦии "батю" и "Зи КС", чемосуществляется формирование адресапервого операнда первой пары алгоритма операндов специального слоя(адрес 111),1 Х. Выполняются микрокоманды садресами 27-29. Данные микрокомандыаналогичны микрокомандам с адресами3- 5. Сигнал "ич" не вырабатывается.В результате выполнения этих микрокоманд осуществляется формированиеадреса второго операнда первой парыспециального слоя (адрес 0000001), Первая пара поступает далеев арифметическое устройство для обработки.Х, Выполняются микрокоманды с адресом 30-32, Вырабатывается микрооперация "бич" и "Зп КС" в микрокоманде 32, Данные микрокоманды формируют адрес первого операнда второйпары специального слоя (адрес 111110) .Х 1. Выполняются микрокоманды садресами 33-35, Данные микрокомандыаналогичны микрокомандам с адресами3-5. В результате выполнения этихмикрокоманд осуществляется формирова"иие адреса второго операнда второйпары специального слоя (000010),Х 11, Выполняется циклическийучасток микропрограммы с адресами36-47, В данном участке обрабатывается в арифметическом устройстве и-япара операндов (в момент входа в циклический участок вторая пара операндов), адресованная микрокомандамис адресами 30-35. За время обработки п-й пары операндов в арифметическом устройстве необходимо адресовать(и)-ю пару операндов, обработаннуюв арифметическом устройстве в преды 1499373 1020 дущем цикле (в момент входа в циклический участок 1-я пара) и (и+1)-юпару, которая будет обрабатыватьсяв следующем такте.Микрокоманды с адресами 36-38 два5раза выполняют микрооперацию "-1 СТ 1"и формируют микрооперацию "Зп КС"в микрокоманде с адресом 38. Во всехтрех микрокомандах сигналом "хпч"осуществляется формирование адресапервого операнда (и)-й пары (на момент входа в циклический участок адрес 111111).Микрокоманды с адресами 39-41 аналогичны микрокомандам с адресами 3-5 иосуществляют формирование адреса второго операнда (и)-й пары (на момент входа в циклический участокадрес 00001)Микрокоманды с адресами 42-44аналогичны микрокомандам с адресами3-5 при наличии сигнала "1 пч" Этимикрокоманды позволяют адресоватьпервый операнд (и+1)-й нары операндов (на момент входа в циклическийучасток алгоритма адрес 111101).Иикрокоманды с адресами 45-47 аналогичны микрокомандам с адресами3-5. Этим осуществляется формирование 30адреса второго операнда (и+1)-й пары(на момент входа в циклический участок адрес 00011),Таким образом, при выполнении циклического участка происходит адресация (и)-й пары для записи в память35(и+1)-й пары считывания из памятии обработки в следующем цикле.В микрокоманде с адресом 38 анализируется условие Х 2, Всли условие Х 2равно единице, то это означает, чтовсе пары специального слоя обработаны и окончены все вычисления по специальному слою. Происходит переходк выполнению микрокоманды с адресом 4548, т.е. "Конец", В противном случаециклический участок выполняется снова. Таким образом, на выхсдах группымультиплексоров 5 формируются адресадля выполнения алгоритма БПФ и специального слоя алгоритма БПФ для50произвольной выборки,Данные, адресуемые устройством,могут быть представлены как в прямом,так и в двоично-инверсном коде, Двоично-инверсный код предполагает перекоммутацию разрядов адреса в обратном порядке. Младший сТановитсястаршим и т.д,В устрой"тве использован блок 9 модификации адреса (фиг. 2). При формировании адресов в двоично-инверсном порядке дешифратор 16 включен (на управляющем входе уровень логического нуля). Дешифратор 16 дешифрует код "Длина выборки" и выбирает в каждой группе только один двухвходовый элемент И из группы элементов И 13.При формировании адресов в прямом порядке на управляющий вход дешифратора-,16 поступает уровень логической единицы и выходы его устанавливаются в состояние ноля, При этом включаются элементы И, которые обеспечивают формирование канала с прямым следованием разрядов адреса. С выходов груп; пы элементов ИЛИ 14 код адреса поступает на сумматор 15, где суммируется с информацией на выходе устройства "Смещение", и поступает на информационные входы регистров для записи его туда на время обращения к запоминающему устройству. Суммирование с кодом "Смещение", задаваемым извне, позволяет размещать произвольные выборки в памяти с любого адреса.Формула изобретения1. Устройство для формирования адресов процессора быстрого преобразования Фурье, содержащее блок микропрограммного управления, реверсивный счетчик, счетчик, группу элементов И, группу из М (где М - разрядность адреса) мультиплексоров, регистр, блок.,постоянной памяти, каждый разряд входа адреса которого соединен с выходом соответствующего элемента И группы, 3-й двухразрядный выход Ц = 1,М) блока постоянной памяти подключен к адресным входам 1-го мультиплексора группы, 1-й инверсный выход реверсивного счетчика соединен с первым информационным входом З-го мультиплексора группы, первый прямой выход реверсивного счетчика соединен с вторыми информационными входами М мультиплексоров группы и третьим информационным входом первого мультиплексора группы, К-й прямой выход (К = 2, М) реверсивного счетчика соединен с четвертым инфор" мационным входом (К)-го и третьим входом К-го мультиплексоров группы, М-й прямой выход реверсивного счет12 1499373 51015 Таблица 1 ещее щт вюи51 ЕЕ В ЕЕЕ Л1:3 Слой ХО ХО ХО ХО ХО ХО ХО ХО ХО О 1 2 ХО ХО Х 1 ХО Х 1 Х 2 Х 1 Х 2 Х 2 ФЭХОХОХОХОХ 1Х 2еХ 1 Х 2 Х 2 Х 2 Х 2 Х 2 Х 2 Х 2 Х 2 Х 2 Х 2 Х 2ФХ 1 ееХ 2 аВ4 Х 2 Х 2 Х 2 Х 2 чика соединен с третьим информационным входом И-го мультиплексора группы, входы суммирования, вычитанияи сброса реверсивного счетчика соединены соответственно с первым, вторыми третьим входами блока микропрограммного управления, четвертый выходкоторого соединен с тактовым входомрегистра, а пятый - с первыми входами элементов И группы, вторые входыкоторой соединены с соответствующимивыходами счетчика, шестой выход блока микропрограммного управления подключен.к входу чтения блока постоянной памяти, отличающее с ятем, что, с целью расширения областиприменения устройства путем обеспечения возможности адресации действительной последовательности отсчетовдлиной 2, в него дополнительно введены блок сравнения, блок модификации адреса, первый и второй мультиплексоры, -е информационные входыкоторых соединены с соответствующимЗ-и прямым выходом реверсивного счет"чика, выходы первого, второго мультиплексоров и блока сравнения подключены соответственно к первому,второму и третьему входам логическихусловий блока микропрограммного управления, тактовый вход которогоявляется тактовым входом устройства,пятый и шестой выходы блока микропрограммного управления соединенысоответственно со счетным входом ивходом сброса счетчика, выходы которого подключены к первой группе входов блока сравнения, адресные входыпервого и второго мультиплексоров соединены с второй группой входов блока сравнения, первой группой управляющих входов блока модификации адреса и являются группой входов задания длины выборки устройства, вторая группа управляющих входов блока модификации адреса является группой входов кода смещения адреса устройства, а управляющий вход соединен с входом задания признака расположения данных устройства, выходы мультиплексоров группы подключены к группе информационных входов блока модификации адреса, выходы которого соединены с информационными входами регистра, выходы которого являются информационными выходами устроиства. 2 О 25 30 35 40 2. Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок модификации адреса содержит коммутатор, сумматор и дешифратор, информационные входы которого являются второй группой управляющих входов блока, уп" равляющий вход которого является стробирующим входом дешифратора и соединен с первым управляющим входом коммутатора, информационные входы которого являются группой информационных входов блока, группа выходов коммутатора подключена к второй группе входов сумматора, первой группой входов которого является первая группа управляющих входов блока, выходы которых являются выходами сумматора, выходы дешифратора соединены с остальными управляющими входами коммутато- рае4 1499373 Таблица 2еКод А 1 АО мультиплексора 5 из ряда Слой 2г-г ,гЯ 1 00 00 00 000000 01 10 10 0000 0000 0100 0 1 2 00 01 10000001000110а011010:101010Ф101010 10 10 10 3 3 ИТаблица 3 07 Условие 0 ХО 1 Х 1 О Х 2 1 Х 3 Комментарий Ф Я 6 Анализируется выход мультиплексора 10Анализируется выход блока 8Анализируется выход мультиплексора 1Передается константа для организации безусловного перехода Таблица 4 Данные0 01 02 03 04 05 06 07 08 09 ОО 011 012 013 014 Адрес А 5 А 4 АЗ А 2 А 1 АО 0 0 0 0 9 0 10 1. 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 0 0 0 0 0 0 0 0 0 0 0 0 0 О 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 О 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 О 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 О 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 О 10 0 1 1 1 1 О 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1г 1 1 1 1 1 1 1 1 1 1 1 1 1 1 г 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1г1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 0 1 1 0 0 0 111111 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.1 11111 1 1,1 1 1 1 о 1о о г 0 0 0 0 1 0 1 1 11 1 1 1 1 1 1 1 О 1 0 0 0 1 0 0 00 0 О 1 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 1 1 00 1 0 О 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 10 0 1 0 О 0 1 0 О 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 00 11 0 0 1 1 0 1 1 0 1 0 0 1 1 0 1 1 0 1 0 О 1 1 0 1 1 0 г 0 0 1 1 0 1 1 0 1 0 0 1 1 01 0 1 0 0 1 1 0 1 1 0 1 О 0 1 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 0 0 0 1 0 1 1 1 Ь 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1, 0 1 0 1 0 1 00 0 1 0 1 0 1 0