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

(51)5 0 06 Р 15/332 Е ИЗОБРЕТЕНИ ПИ 0 0 00 (Я бд ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ВТОРСКОМУ СВИДЕТЕЛЬСТВ(71) Институт технической кибернетики АН БССР72) А.Н.Мороэевич, В,А.Федосенко, Б.Б.Трибуховский и А.Н,Дмитриев (53) 681.32(088.8)(56) Авторское свидетельство СССР ЬЬ 1174939, кл. 6 06 Р 15/332, 1984.Авторское свидетельство СССР Ф 1499373, кл. 6 06 Р 15/332, 15.06.87, (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ АДРЕСОВ ПРОЦЕССОРА БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ Изобретение относится к вычислительной технике и может быть использовано в составе процессоров быстрого преобразования Фурье (БПФ) или быстрого преобразования в базисах ортогональных функций, используемых в спектроанализаторах, генераторах широкополосного случайного процессора, синтезаторах речевых сигналов и т.д. Цель изобретения - сокращение аппаратных затрат.На фиг. 1 представлена функциональная схема устройства; на фиг, 2 - функциональная схема блока микропрограммного управления; на фиг. 3 - схема алгоритма блока микропрограммного управления.Устройство для формирования адресов БПФ (фиг. 1) содержит блок 1 микропрограммногоуправления, реверсивныйсчетчик 2, первый счетчик 3, второй счетчик 4, блок 5 постоянной памяти, блок 6 модификации(57) Изобретение относится к вычислительной технике и может быть использовано в составе процессоров быстрого преобразования Фурье или быстрого преобразования в базисах ортогональных функций, используемых в спектроаналиэаторах, генераторах широкополосного случайного процесса, синтезатора речевых сигналов и т,д. Цель изобретения - сокращение аппаратных затрат, Поставленная цель достигается эа счет того, что устройство содержит блок микропрограммного управления, реверсивный счетчик, первый и второй счетчики, блок по, стоянной памяти, блок модификации адреса, регистр, блок сравнения, программируемый коммутатор, мультиплексоры, 3 ил. адреса, регистр 7, блок 8 сравнения, (программируемый) коммутатор 9 и с первого по четвертый мультиплексоры 10-13,Блок 1 микропрограммйого управления (фиг. 2) образуют счетчик 14 адреса, узел 15 памяти микропрограмм, регистр 16 микро- команды, мультиплексор 17 условий и элементы И 18 и 19.Устройство работает следующим образом. Длина выборки задается извне на входахустройства "Длина выборки" в двоичном коде. На входе признака расположения данных в выборке "Расположение данных" задается признак прямой (Р = 1) или двоично-инверсной (Р = О) адресации. Например, обрабатывается выборка данных длиной 1024 отсчета. При этом двоичный код 1010 (целое двоичное М-разрядное число, равноеодг 1024/М = 1 о 92 10(=4/М вдвоичном коде) поступает на адресные входы1691853 актор А.Ога аказ 3929 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5 оизводственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина оставитель А.Баран ехред М,Моргентал гКорректор И Зрдиймультиплексора 10. При этом на выходе последнего формируется информация О или 1), соответствующая информации на прямом выходе того разряда реверсивного счетчика 2, номер каторога равен коду длины последовательности, Для рассматриваемого случая номер выхода - десять (одиннадцатый выход счетчика 2 - нумерация идет от нуля),Появление единицы на выходе мультиплексора 10 сигнализируег об окончании вычислений па слою алгоритма БПФ. Данный сигнал анализируется блоком 1 микропрограммного управления, и па его появлению (сигнал логической единицы на выходе мультиплексора 10) блок 1 микропрограммного управления сигналом;: третьего выхода сбрасывает реверсивный счетчик 2, а в первый счетчик 3, определяющий номер слоя, сигналом с пятого выхода блока 1 микропрограммного управления дсбавляется единица. При атом осуществляется переход к вычислениям по очередному слою.Перед выполнением каждого слоя алгсритма БПФ необходимо произвести коммутацию 1-го разряда адреса О 1 на входе коммутатора 9 с)-м разрядом адреса О О на выходе каммутатаоа 9, Для программирования связей па всем К разрядам (И - числа разрядов в адресе, й =)1 а 92 Ц, где- длина выборки) требуется й тактов, в течение которых на девятом выходе блока 1 микропраграммнага управления поддерживаетсясигнал низкого уровня. Перебор М адресов для программирования связей осуществляется с помощью счетчика 4, который перед началам прсграммирования связей потенциальным сигналам с шестого выхода блока 1 микропрограммного управления устанавливается в нулевое состояние, Выходы счет, чика 4 адресуют младшие Ы разрядов адресных входов блока 5 постоянной памя, ти, старшие М разрядов адресных входов кат:рого адресуются счетчиком 2, определяющим программирование связей в зависимости ат номера слоя,Порядок коммутации адресных разрядов основывается на тай особенности алгоритма БПФ, что адреса пары операндов отличаются информацией в одном разряде; номер которого соотвеп:твует номеру слоя алгоритма (эта особенность использована и в известном устройстве для адресации ряда мультиплексоров), следовательно, в каждом слое адреса отличаются ат кодов счетчика только порядком следования разрядов. Для нулевого слоя разряды адреса коммутируются в естественном порядке (О 1 8 с О Оф О 1; с О 01 и т,д,), для первого слоя разряд О 1 ф коммутируется с О О , а О 11 - с О Оф35 коммутатор 9 и мультиплексор 12, Окончание вычислений па специальному слою ал.- горитма БПФ определяется мультиплексором 11. Для мультиплексора 11 информация на входах смещена на одинразряд по отношению к мультиплексору 10 фиг. 1), что соответствует характеру вычислений в специальном слое.При наличии сигнала высокого уровняна адресном входе мультиплексора 13 навторую группу входов блока 8 сравнения поступает код номера коммутируемого разряда с выхода счетчика 4, В этом случае сигнал высокого уровня на выходе блока 8 сравнения сигнализирует об окончании50 программирования связей в коммутаторе 9,Управление работой устройства осуществляется блоком 1 микропрограммного управления (фиг. 2). Счетчик 14 с возможностью параллельного занесения информации выполняет функцию регистра адреса микрокоманды. Его выходы подключены к входам узла 15 постоянной памяти, в котором записана микропрограмма работы всего устройства, Считанная из узла 15 постоянной памяти микракоманда запоминается в рег ч 5 10 15 20 25 30 см; табл. 1). Прошивка блока 9 постоянной памяти для выборки длиной= 8 приведена в табл. 2.По окончании вычислений по основному алгоритму для выборки 1024-десять слоев: О, 1 2 9) устройство переходит на адресацию в специальный слой для рассматриваемого примера слой 10), Наличие перехода в специальный слой сигнализируется блоком 8 сравнения, на вторую группу входов которого подается через мультиплексор 13 (на адресный вход котороо поступает сигнал низкого уровня с одиннадцатого выхода блока 1 микропрограммного управления) код номера текущего слоя со счетчика 3, а на первую - кад "Длина вьбарки". Специальный слой требуется для использования алгоритмов БПФ обработки действительных последовательностей, что позволяет устранить выполнение избыточных вычислений. В специальном слое формируются аднреса операндов и 1:1, где = 1, 2, ,1/2-1 А. - . длина выборки, Формирование таких адресов в предлагаемом устройстве происходит следующим образом. Счетчик 2 обнуляется, и происходит про.раммирование связей в коммутаторе 9 аналогично нулевому слою алгоритма БПФ. Адрес первого операнда адрес 1:1) записывается в выходной регистр 7 с инверсных выходов счетчика 2 через мультиплексор 12. Адрес второго операнда адрес ) формируется путем прибавления "1" к содержимому счетчика 2 и поступает в региста 7 черезстре 16 микрокоманды, Выбор адреса следующей микрокоманды осуществляется автоинкрементным способом (путем добавления единицы к содержимому счетчика 14) либр путем условного или безусловного перехода к,требуемому адресу (занесение в счетчик 14 параллельного кода адреса перехода). Адрес перехода определяют разряды микрокоманды 0 О - 0 5 после адресов перехода. Переход инициируется сигналом (логической единицы), возникающим на выходе мультиплексора 17. Сигнал на выходе мультиплексора 17 появляется в том случае, если в поле признаков перехода 0 6, 0 7 сформирован код, отличный от "11", а на адресных входах мультиплексора.17. - код условия перехода (Х О - ХЗ, табл. 3).Разряды 0 8 и 0 9 регистра 16 стробируются с помощью элементов И 18 и 19 и являются соответственно первым и вторым выходами блока 1 микропрограммного управления. Выходы разрядов 0 10 - 0 18 регистра 16 являются соответственно третьим-одиннадцатым выходами блока 1 микропрограммного управления,Работа устройства для формирования адресов иллюстрируется схемой алгоритма (фиг. 3), кодировка макрокоманд которого представлена в табл. 4.На фиг. 3 введены следующие обозначения:"+1 СТ 1" ("1" в столбце 08 табл. 4) соответствует формированию импульса на первом выходе блока 1 микропрограммного управления, подключенном к суммирующему входу реверсивного счетчика 2;"-1 СТ 1" ("1" в столбце 09 табл. 4) соответствует формированию импульса на вто-. ром выходе блока 1 микропрограммного управления, подключенном к вычитающему входу реверсивного счетчика 3;"Сброс СТ 1" ("1" и столбце 010 табл. 4) соответствует формированию потенциального сигнала на.третьем выходе блока 1 микропрограммного управления, подключенном к выходу сброса реверсивного счетчика 2;"Зпйб" ("О"-е "1") в столбце 011 табл.4) соответствует. формированию потенциального сигнала на четвертом выходе блока 1 микропрограммного управления, подключенном к синхровходу регистра 7;"+1 СТ 2" ("О" в столбце 012 табл. 4) соответствует формированию потенциального сигнала на пятом выходе блока 1 микропрограммного управления, подключенном к счетному входу счетчика 3;"Сбр.СТ 2" ("1" в столбце 013 табл, 4) соответствует формированию потенциаль ного сигнала на шестом выходе блока 1 микропрограммного управления, подключенном к входу сброса счетчика 3;" -+1 СТЗ" ("О" в столбце 014 табл. 4) соответствует формированию потенциального сигнала на седьмом выходе блока 1 микропрограммного управления, подключенном к счетному входу счетчика 4;"Сброс СТЗ" ("1" в столбце 015 табл. 4) соответствует формированию потенциального сигнала нэ восьмом выходе блока 1 микропрограммного управления, подключенном к входу сброса счетчика 4;"Е" (столбец 016 табл. 4) - вход разрешенияпрограммирования связей в комму 51015 таторе 9 (активный уровень - низкий);"А 1" (столбец 017 табл. 4) - адресный вход мультиплексора 12 (А 1 =- О, к входам регистра 7 подключены инверсные выходы счетчика 2, А 1 = 1 - выходы коммутатора 9); 20(адрес 00000). 4. Выполняются микрокоманды с адре 45 сами 5 - 7, в которых формируются сигналы "+1 СТ 1", а затем и "Зпйб", чем осуществляется запись в регистр 7 адреса второго операнда нулевой пары операндов (адрес 00001). Далее эти операнды могут обрабатываться. арифметическим устройством, причем операнды нулевой пары требуют 50 тривиального умножения на единицу, поэтому для своей обработки требуют меньшего времени, чем операнды остальных пар. Это используется при входе в циклический участок алгоритма, когда время на обработку нулевой пары уменьшено до трех 55 тактов.,"А 2" (столбец 018 табл, 4) - адресныйвход мультиплексора 12 (А 2 = О, к второйгруппе входов блока 8 сравнения подключены выходы счетчика 3, А 2 = 1 - выходы счет 25 чика 4);Ф- пустая микрокоманда,Алгоритм формирования адресов следу ющий:1. Выполняются микрокомэнды с адреЗО сами О и 1 (десятичный эквивалент двоичного адреса), В этих микрокомандахосуществляется сброс счетчиков 2 - 4 (сигналы "Сброс СТ 1", "Сброс СТ 2", "Сброс СТЗ"),чем устройство подготавливается к работе,35 2, Выполняется циклический участокмикропрограммы с адресами 2, 3, чем осуществляется программирование связейкоммутатора 9.3. Выполняется микрокоманда с адре 40 сом 4, формируется сигнал "Зпйб", чем осуществляется запись в регистр 7 адресапервого операнда нулевой пары операндов5, Выполняются микрокоманды с адресами 8-10. Они аналогичны микрокомандам5-7 юВ результате их выполнения в регистр 7заносится адрес первого операнда первойпары операндов (000010).6, Выполняются микрокоманды с адресами 11-13. Они также аналогичны микрокомандам с адресами 5-7. В результате ихвыполнения в регистр 7 заносится адресвторого операнда (000.011),7. Выполняется циклический участокмикропрограммы, содержащий микрокомэнды с адресами 14-25, В данном участкеобрабатывается в арифметическом устройстае и-:я пара операндов в момент входапервая пара, адресованная микрокоманда ми с.адресами 6-11). Зэ время обработкии-й пары в арифметической устройстве не; .обходимо адресовать (и)-ю пару, обрабо танную в арифметическом устройстве впредыдущем цикле (в момент входа в цикли, ческий участок )О-я пара) и (и+1)-ю пару,которая будет обрабатываться в следующемцикле.Микрокоманды с адресами 14-16 трираза выполняют микрооперацию "-1 СТ 1" иформируют микрооперацию "Зпйб" в микрокоманде с адресом 16, чем осуществляется формирование адреса первого операнда. участок адрес 000., ОО).Микрокоманды с адресами 17-19 аналогичны.микрокомэндэм с адресами 5-7 иосуществляют формирование адреса второго операнда (и)-й пар,ы (на момент входа вциклическйй участок адрес 00001).Микрокоманды с адресами 20-22 рираза выполняют микрооперацию "+1 СТ 1" иформируют микрооперацию "Зпйб" в микрокоманде 23. Этим осуществляется формирование адреса первого операнда (и+1)-йпары (на момент входа в циклический участок адрес 0000100).Микрокоманды с адресами 23-25 аналогичны микрокомандам с,адресами 5-7 иосуществляют формирование адреса второго операнда (и+1)-й пары (на момент входа вциклический участок адрес 0000101),Таким образом, при выполнении циклического участка происходит адресация (п).й пары для записи в память, (и+1)-й пары длясчитывания из памяти и обработки в следующем цикле..В микрокоманде с адресом 16 анализируется условие ХО. При попытке сформировать. адрес для записи в память первогооперанда (и)-й пары, не принадлежащегопространству адресов слоя алгоритма. БПФдля данной выборки, условие ХО стайовится20 ЗО равным единице. При этом происходит условный переход к выполнению микрокоманды с адресом 26. Если первый операнд(пара операндов) принадлежит пространству, то перехода не происходит и циклический участок повторяется снова.8. Выполняются микрокоманды с адресами 26 и 27. В них осуществляется формирование операций "Сброс СТ 1", Сброс СТЗ" и "+1 СТ 2", Добавление единицы в счетчик 3 означает формирование следующего слоя алгоритма БПФ. В микрокоманде 27 анализируется условие Х 1, которое сигнализирует о переходе в специальный слой алгоритма БПФ.Если нет перехода в специальный слой алгоритма БПФ, то устройство начинает обрабатывать следующий слой путем выполнения микрокоманды с адресом 2. Приналичии перехода в специальный слой.осуществляется переход к выполнению микро- команды с адресом 28, т.е. вход в участок алгоритма, осуществляющий формирование адресов операндов специального слоя.9. Выполняется циклический участокмикрокомэнд с адресами 29 и ЗО, чем осуществляется программирование связей коммутатора 9, 10. Выполняется микрокоманда с адресом 31, в которой адрес с инверсных выходов счетчика 2 зэписываетая в регистр 7, чем осуществляется формирование адреса первого операнда первой пары операндов специального слоя (адрес 1111).11. Выполняются микрокоманды с адресами 32 - 34. Данные микрокомэнды аналогичны микрокомандам с адресами 5 - 7, В регистр 7 записывается адрес с прямых выходов счетчика 2 через коммутатор 9, В ре 40 зультате выполнения этих микрокомандосуществляется формирование адреса второго операнда первой пары специального слоя (адрес 0000001). Первая пара поступает далее в арифметическое устройство 45 для обработки,12. Выполняются микрокоманды с адресом 34-36, Данные микрокоманды формируют адрес первого операнда второй пары специального слоя (адрес 111110).5013. Выполняются микрокоманды с адресами 37-39. Данные микрокоманды аналогичны микрокомандам с адресами 5-7. В результате выполнения этих микрокоманд .осуществляется формирование адреса вто 55 рого операнда второй пары специальногослоя (000010).14. Выполняется циклический участокмикропрограммы с адресами 40-51, В данном участке обрабатывается в арифметическом устройстве п-я пара операндов (вмомент входа в циклический участок - вторая пара операндов), адресованная микро- командами с адресами 34-39. За время обработки и-й пары операндов в арифметическом устройстве необходимо адресовать (и)-ю пару операндов, обработанную в арифметическом устройстве в предыдущем цикле (в момент входа в циклический участок первая пара), и (и+1)-ю пару, которая будет обрабатываться в следующем такте.Микрокоманды с адресами 40-42 два раза. выполняют микрооперацию "-1 СТ 1" и формируют микрооперацию "ЗпВО" в микрокоманде с адресом 42. В этих микроко 10 мандах осуществляется. формирование адреса первого операнда (и)-й пары (на момент входа в циклический участок адрес 111111). Микрокоманды с адресами 43 - 45 аналогичны микрокомандам с адресами 5-1 20 и осуществляют формирование адреса второго операнда (и)-й пары (на момент входа в циклический участок адрес 00001).Микрокоманды с адресами 46-48 аналогичны микрокомандам с адресами 5 - 7 при наличии сигнала "А 1 =. 1". Эти микрокоманды позволяют адресовать первый операнд (и+1)-й пары операндов (на момент входа в циклический участок алгоритма адрес 111101). Микрокоманды с адресами 49-.51 аналогичны микрокомандам с адресами 5 - 7.Этим осуществляется формирование адреса второго операнда (п+1)-й пары (на момент входа в циклический участок адрес 30 00011).Таким образом, при выполнении циклического участка происходит адресация (и)- й пары для записи в память, (и+1)-й пары для считывания из памяти и обработки в следующем цикле единице, то это означает, что все пары специального слоя обработаны и окончены все вычисления по специальному слою. Происходит переход к выполнению микрокоманды с адресом 52, т.е, "Конец". В противном случае циклический участок выполняется снова. Данные, адресуемые устройством, мо гут быть представлены как в прямом, так и двоично-инверсном коде. Двоично-инверсный код предполагает перекоммутацию разрядов адреса в обратном порядке. Младший становится старшим и т.д. Представление данных в прямом или двоичноинверсном порядке осуществляется блоком 6 модификации адреса, Суммирование с кодом "Смещение", задаваемым извне, позво 55 В микрокоманде с адресом 42 анализируется условие Х 2. Если условие Х 2 равно. ляет размещать произвольные выборки в памяти с любого адреса.Формула изобретения Устройство для формирования адресов процессора быстрого преобразования Фурье, содержащее блок микропрограммного управления, реверсивный счетчик, первый счетчик, блок постоянной памяти, блок модификации адреса, блок сравнения, первый и второй мультиплексоры, регистр, выходы которого являются информационными выходами устройства, входы регистра соединены с выходами блока модификации адреса, входы суммирования, вычитания и сброса реверсивного счетчика - соответственно с первым, вторым и третьим выходами блока микропрограммного управления четвертый выход которого соединен с тактовым входом регистра, пятый и шестой выходы блока микропрограммного управления - соответственно со счетным входом и входом сброса первого счетчика, выходы первого и второго мультиплексоров и выход блока сравнения подключены соответственно к первому, второму и третьему входам блока микропрограммного управления, тактовый вход которого является тактовым входом устройства, адресные входы первого и второго мультиплексоров соединены с входами первой группы блока сравнения, управляю-щими входами первой группы блока модификации адреса и являются группой входов задания длины выборки устройства, вторая группа управляющих входов блока модификации адреса является группой входов кода смещения адреса устройства, а управляющий вход блока модификации адоеса является входом задания признака расположения данных устройства, информэционные входы первого и второго мульти-, .плексоров подключены к прямым выходам соответствующих разрядов реверсивного счетчика, о т л и ч а ющ е е с я тем, что, с целью сокращения аппаратных затрат, оно содержит коммутатор Мхй (И - разрядность адреса), второй счетчик, третий и четвертый мультиплексоры, причем)-й= 1, й), информационный вход коммутатора подключен к прямому выходу )-го разряда реверсивного счетчика, )-й выход коммутатора подключен к)-му информационному входу первой группы третьего мультиплексора, )-й информационный вход второй группы которого подключен к инверсному выходу)-го разряда реверсивного счетчика, а выходы третьего мультиплексора подключены к соответствующим информационным входам блока модификации адреса, седьмой и восьмой выходы блока микропрограммного управления соединены соответственно со12 1691853 групп коммутатора, вход разрешения записи которого соединен с девятым выходом блока микропрограммного управления, десятый и одиннадцатый выходы которого соединены 5 с адресными входами соответственно третьего и четвертого мультиплексоров, информационные входы второй группы четвертого мультиплексора - с информационными выходами первого счетчика, а выходы четвертого 10 мультиплексора подключены к входам второй группы блока сравнения..(. а б л и ц а 1 Разряды адресного слоя на входе (,1) и выходе (О) коммутатора 1 +1 ) +1+1 ( +11(,четным входом и входом сброса второго (,четчика, выходы которого подключены к (нформационным входам первой группы Четвертого мультиплексора и адресным входам первой группы блока постоянной памяти, адресные входы второй группы которого (Г(одключены к информационным выходам )ервого счетчика, -й О =: 1, М, М = (о 92 Й) двухразрядный выход блока постоянной паяти соединен поразрядно с 1-ми адресныи входами соответственно первой и второй 0 О О С О О О 1 О О 1 О О 1 О О 1 О О 1 1 1 О О.1691853 Продолжение табл.2 Адресные входы ИЗУ Выходы АЗ А 2 А 1 Ооо ) )о А 5 А 4 О О 0 О 0 0 О О 0 0 О 1 1 0 1 1 0 1 1 (2 0 0 1 0 1 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 О, 0 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1 0 1 1 1 .1 11.11 1 1 1 1 1 1 1 1 О О 1 1 0 0 10 1 О 1 О 1 1 0 1 О 1 0 1 0 1 0 1 0 1 1 О 1 О 1 0 1 0 б л ица ХО Х 1 Х 2 ХЗ О О О 1 1 О 1 Анализируется выход мультиплексораАнализируется выход блока 8Анализируется выход мультиплексораПередается константа для организации безусловного перехода 10 11 О О 0 1 1 1 1 1 1 1 0 О 0 О 0 0 0 О 1 1 1 1 1 1 О О О О О О О О 1 1 1 1 1 1 1 1 О О 0 1 1 1 О 0 0 О 1 1 1 0 О 0 0 1 1 1 О О О 0 1 1 1 1 О О О О 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 О 1 0 0 0 1 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 1 1 0 01 0 ) 1 1 0 0 1 1 0 0 1 0 0 .1 0 0 1 1 0 0 1 1 0 0 1 1 О О 1 1 0 0 1 1 1 1 1 0 0 О 0 1 1 1 1 0 0 1 01 0 0 0 1 0 1О 0 О 11 0 1 0 0 О 1 1 1 О