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

Ё

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

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

Цель изобретения - сокращение аппаратных затрат.

На фиг. 1 представлена функциональная схема устройства; на фиг. 2 - функциональная схема блока микропрограммного управления; на фиг. 3 - схема алгоритма блока микропрограммного управления.

Устройство для формирования адресов БПФ (фиг. 1) содержит блок 1 микропрограммного управления, реверсивный счетчик 2, первый счетчик 3, второй счетчик 4, блок 5 постоянной памяти, блок 6 модификации

адреса, регистр 7, блок 8 сравнения, (программируемый) коммутатор 9 и с первого по четвертый мультиплексоры 10-13.

Блок 1 микропрограммного управления (фиг. 2) образуют счетчик 14 адреса, узел 15 памяти микропрограмм, регистр 16 микрокоманды, мультиплексор 17 условий и элементы И 18 и 19.

Устройство работает следующим образом.

Длина выборки задается извне на входах устройства Длина выборки в двоичном коде. На входе признака расположения данных в выборке Расположение данных задается признак прямой (Р 1) или двоично-инверсной (Р 0) адресации. Например, обрабатывается выборка данных длиной 1024 отсчета. При этом двоичный код 1010 (целое двоичное М-разрядное число, равное 1о§2 1024/М loga 10 4/Мвдво- ичном коде) поступает на адресные входы

О Ч)

со

ел со

мультиплексора 10. При этом на выходе последнего формируется информация {0 или 1), соответствующая информации на прямом выходе того разряда реверсивного счетчика 2, номер которого равен коду дли- иы последовательности Для рассматриваемого случая номер выхода - десять (одиннадцатый выход счетчика 2 - нумерация идет от нуля).1 Появление единицы на выходе мультиплексора 10 сигнализирует об окончании вычислений го слою алгоритма БПФ. Данный сигнал анализируется блоком 1 микропрограммного управление, и по его появлению (сигнал логической единицы на выходе мультиплексора 10) блок 1 микрс- программного управпения сигнзпом . третьего вьиода сбрасывает реверсивный счетчик 2, а в первый счет чикЗ, определяющий номер слоя, сигналом с пятого выхода блока 1 микропрограммного управления дс- бавляется единица. При этом осуществляется переход к вычислениям по очередному слою.

Перед выполнением каждого слоя алгоритма БПФ необходимо произвести комму- тацио 1-го разряда адреса D 1| на входе коммутатора 9 с j-м разрядом адреса D Oi на выходе коммутатора 9. Для программировс - ния связей по всем N разрядам (N - «ислз разрядов а адресе, N log2 Ц, где L - длина выборки) требуется N тактов, в течение которых на девятом выходе блока 1 микропрограммною управления поддерживается сигнал низкого урошя. Перебор N адресов для программирования связей осуществля- ется с помбщью счетчика 4, который пеоед началом программирования связей потенциальным сигналом с шестого выхода блока 1 микропро раммного управления устанавливается в нулевое состояние. Выходы счет- чика 4 адресуют младшие N разрядов адресных входов блока 5 постоянной памяти, старшие N разрядов адресных входов кот рого адресуются счетчиком 2, определяющим программирование связей в зави- симости от номера слоя

Порядок коммутации адресных разрядов основывается на той особенности алгоритма БПФ, что адреса пары операндов отличаются информацией в одном разряде, номер которого соответствует номеру слоя алгоритма(эта особенность использована и в известном устройстве для адресации ряда мультиплексоров), следовательно, в каждом слое адреса отличаются от кодов счетчика только порядком следования разрядов. Для нулевого слоя разряды адреса коммутируются в естественном порядке (D 1 0 с D 00 D 1. с D Oi и т.д.), для первого слоя разряд D1 0 коммутируется с D Oi, a D

(см. табл. 1). Прошивка блока 9 постоянной памяти для выборки длиной 8 приведена в габл. 2.

По окончании вычислений по основному алгоритму (для выборки 1024-десять слоев: 0. 1, 29) устройство переходит на адресацию в специальный слой (для рассматриваемого примера слой 10), Наличие перехода в специальный слой сигнализиру- отся блоком 8 сравнения, на вторую группу входов которого подается через мультиплексор 13 (на адресный вход которого поступает сигнал низкого уровня с одиннадцатого выхода блока 1 микропрограммного управления) код номера текущего слоя со счетчика 3, а на первую - код Длина выборки. Специальный слой требуется для использования алгоритмов БПФ обработки действительных последовательностей, что позволяет устранить-выполнение избыточных вычислений. В специальном слое формируются адреса операндов I и L-I, где 1 1, 2,. ., L/2-1.L длина выборки. Формирование таких адресов в предлагаемом устройстве происходит следующим образом. Счетчик 2 обнуляется и происходит про- | рзммирование связей в коммутаторе 9 аналогично нулевому слою алюритма БПФ. Адрес первого операнда (адрес L-I) записывается в выходной регистр 7 с инверсных выходов счетчика 2 через мультиплексор 12. Адрес второго операнда (адрес I) формируется путем прибавления 1 к содержимому счетчика и поступает в регистр 7 через коммутатор 9 и мультиплексор 12 Окончание вычислений по специальному слою ал- горитмаБПФопределяется

мультиплексором 11. Для мультиплексора 11 информация на входах смещена на один разряд по отношению к мультиплексору 10 (фиг. 1), что соответствует характеру вычислений в специальном слое.

При наличии сигнала высокого уровня на адресном входе мультиплексора 13 на вторую группу входов блока 8 сравнения поступает код номера коммутируемого разряда с выхода счетчика 4. В этом случае сигнал высокого уровня на выходе блока 8 сравнения сигнализирует об окончании программирования связей в коммутаторе 9. Управление работой устройства осуществляется блоком 1 микропрограммного управления (фиг. 2), Счетчик 14 с возможностью параллельного занесения информации выполняет функцию регистра адреса микрокоманды. Его выходы подключены к входам узла 15 постоянной памяти, в котором записана микропрограмма работы всего устройства. Считанная из узла 15 постоянной памяти микрокоманда запоминается в ре чстре 16 микрокоманды. Выбор адреса следующей микрокоманды осуществляется автоинкрементным способом (путем добавления единицы к содержимому счетчика 14) либр путем условного или безусловного перехода к требуемому адресу (занесение в счетчик 14 параллельного кода адреса перехода). Адрес перехода определяют разряды микрокоманды Q 0 Q 5 после адресов перехода. Переход инициируется сигналом (логической единицы), возникающим на выходе мультиплексора 17. Сигнал на выходе мультиплексора 17 появляется в том случае, если в поле признаков перехода Q 6, Q 7 сформирован код, отличный от 11, а на адресных входах мультиплексора 17 - код условия перехода (X 0 - ХЗ, табл. 3).

Разряды Q 8 и Q 9 регистра 16 строби- руются с помощью элементов И 18 и 19 и являются соответственно первым и вторым выходами блока 1 микропрограммного управления. Выходы разрядов Q 10 - Q 18 регистра 16 являются соответственно треть- им-одиннадцатым выходами блока 1 микропрограммного управления.

Работа устройства для формирования адресов иллюстрируется схемой алгоритма (фиг. 3), кодировка макрокоманд которого представлена в табл. 4.

На фиг. 3 введены следующие обозначения:

+1СТ1 (1 в столбце Q8 табл. 4) соответствует формированию импульса на первом выходе блока 1 микропрограммного управления, подключенном к суммирующему входу реверсивного счетчика 2;

-1СТ1 (Г в столбце Q9 табл. 4) соответствует формированию импульса на втором выходе блока 1 микропрограммного управления, подключенном к вычитающему входу реверсивного счетчика 3;

Сброс СТГ (1 в столбце Q10 табл. 4) соответствует формированию потенциального сигнала на третьем выходе блока 1 микропрограммного управления, подключенном к выходу сброса реверсивного счетчика 2;

3nRG ( 1) в столбце Q11 табл. 4) соответствует формированию потенциального сигнала на четвертом выходе блока 1 микропрограммного управления, подключенном к синхровходу регистра 7;

-+1СТ2 (0й в столбце 012табл. 4)соответствует формированию потенциального сигнала на пятом выходе блока 1 микропрограммного управления, подключенном к счетному входу счетчика 3;

Сбр.СТ2 (1 в столбце Q13 табл. 4) соответствует формированию потенциального сигнала на шестом выходе блока 1 микропрограммного управления, подключенном к входу сброса счетчика 3;

+1СТЗ (О в столбце Q14 табл. 4) со- ответствует формированию потенциального сигнала на седьмом выходе блока 1 микропрограммного управления, подключенном к счетному входу счетчика 4;

Сброс СТЗ (Г в столбце Q15 табл. 4) соответствует формированию потенциального сигнала на восьмом выходе блока 1 микропрограммного управления, подключенном к входу сброса счетчика 4;

Z (столбец Q16 табл. 4) - вход разре- шения программирования связей в коммутаторе 9 (активный уровень - низкий);

АГ (столбец Q17 табл. 4) - адресный вход мультиплексора 12 (А1 0, к входам регистра 7 подключены инверсные выходы счетчика 2, А1 1 - выходы коммутатора 9); А2 (столбец Q18 табл. 4) - адресный вход мультиплексора 12 (А2 0, к второй группе входов блока 8 сравнения подключены выходы счетчика 3, А2 1 - выходы счет- чика4);

Р - пустая микрокоманда. Алгоритм формирования адресов следующий:

+1СТ1, а затем и 3nRG, чем осуществляется запись в регистр 7 адреса второго операнда нулевой пары операндов (адрес 000...01). Далее эти операнды могут обрабатываться арифметическим устройством, причем операнды нулевой пары требуют тривиального умножения на единицу, поэтому для своей обработки требуют меньшего времени, чем операнды остальных

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

В результате их выполнения в регистр 7 заносится адрес первого операнда первой пары операндов (000...010).

Микрокоманды с адресами 14-16 три раза выполняют микрооперацию -1СТ1 и формируют микрооперацию 3nRG в микрокоманде с адресом 15, чем осущест вляет- ся формирование адреса первого операнда (п-1)-й пары (на момент входа в циклический участок адрес 000.. 00).

Микрокоманды с адресами 17-19 аналогичны микрокомандам с адресами 5-7 и осуществляют формирование адреса второго операнда (п-1)-й пары (на момент входа в циклический участок адрес 00...001).

Микрокоманды с адресами 20-22 ри раза выполняют микрооперацию +1СТ1 и формируют микрооперацию 3nRG в микрокоманде 22. Этим осуществляется формирование адреса первого операнда (п+1}й пары (на момент входа в циклический уча сток адрес 000...0100).

Микрокоманды с адресами 23-25 аналогичны микрокомандам с адресами 5-7 и осуществляют формирование адреса второго операнда (п-Н)-й пары (на момент входа в циклический участок адрес 000...0101).

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

В микрокоманде с адресом 16 анализируется условие ХО. При попытке сформировать адрес для записи в память первого операнда (п-1)-й пары, не принадлежащего пространству адресов слоя алгоритма БПФ для данной выборки, условие ХО становится

равным единице. При этом происходит условный переход к выполнению микрокоманды с адресом 26. Если первый операнд (пара операндов) принадлежит пространству, то

перехода не происходит и циклический участок повторяется снова.

0 и +1СТ2, Добавление единицы в счетчик 3 означает формирование следующего слоя алгоритма БПФ. В микрокоманде Канализируется условие Х1, которое сигнализирует о переходе в специальный слой алгоритма

5 БПФ.

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

0 наличии перехода в специальный слой осуществляется переход к выполнению микрокоманды с здресом 28, т.е. вход в участок алгоритма, осуществляющий формирование адресов операндов специального слоя.

5 9. Выполняется циклический участок микрокоманд с адресами 29 и 30, чем осуществляется программирование связей коммутатора 9.

5 11. Выполняются микрокоманды с адресами 32-34 Данные микрокоманды аналогичны микрокомандам с адресами 5-7. В регистр 7 записывается адрес с прямых выходов счетчика 2 через коммутатор 9 В ре0 зультате выполнения этих микрокрманд осуществляется формирование адреса второго операнда первой пары специального слоя (адрес 0000,..001). Первая пара поступает далее в арифметическое устройство

5 для обработки.

0 13. Выполняются микрокоманды с адресами 37-39. Данные микрокоманды аналогичны микрокомандам с адресами 5-7. В результате выполнения этих микрокоманд осуществляется формирование адреса вто5 рого операнда второй пары специального слоя (000...010).

момент входа в циклический участок - вторая пара операндов), адресованная микрокомандами с адресами 34-39. За время обработки n-й пары операндов в арифметическом устройстве необходимо адресовать (гИ)-ю пару операндов, обработанную в арифметическом устройстве в предыдущем цикле (в момент входа в циклический участок первая пара), и (п+1)-ю пару, которая будет обрабатываться в следующем такте.

Микрокоманды с адресами 40-42 два раза выполняют микрооперацию -1СТГ и формируют микрооперацию 3nRG в микрокоманде с адресом 42. В этих микрокомандах осуществляется формирование адреса первого операнда (п-1)-й пары (на момент входа в циклический участок адрес 111 ...111). Микрокоманды с адресами 43-45 аналогичны микрокомандам с адресами 5-7 и осуществляют формирование адреса вто- рого операнда (п-1)-й пары (на момент входа в циклический участок адрес 00...001).

Микрокоманды с адресами 46-48 аналогичны микрокомандам с адресами 5-7 при наличии сигнала А1 1. Эти микроко- манды позволяют адресовать первый операнд (п+1)-й пары операндов (на момент входа в циклический участок алгоритма адрес 111...101).

Микрокоманды с адресами 49-51 ана- логичны микрокомандам с адресами 5- 7.Этим осуществляется формирование адреса второго операнда (п+1)-й пары (на момент входа в циклический участок адрес 00...011).

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

В микрокоманде с адресом 42 анализируется условие Х2. Если условие Х2 равно единице, то это означает, что все пары специального слоя обработаны и окончены все вычисления по специальному слою. Проис- ходит переход к выполнению микрокоманды с адресом 52, т.е. Конец. В противном случае циклический участок выполняется снова.

Данные, адресуемые устройством, мо- гут быть представлены как в прямом, так и двоично-инверсном коде. Двоично-инверсный код предполагает перекоммутацию разрядов адреса в обратном порядке. Младший становится старшим и т.д. Пред- ставление данных в прямом или двоично- инверсном порядке осуществляется блоком б модификации адреса. Суммирование с кодом Смещение, задаваемым извне, позволяет размещать произвольные выборки в памяти с любого адреса.

Формула изобретения Устройство для формирования адресов процессора быстрого преобразования Фурье, содержащее блок микропрограммного управления, реверсивный счетчик, первый счетчик, блок постоянной памяти, блок модификации адреса, блок сравнения, первый и второй мультиплексоры, регистр, выходы которого являются информационными выходами устройства, входы регистра соединены с выходами блока модификации адреса, входы суммирования, вычитания и сброса реверсивного счетчика - соответственно с первым, вторым и третьим выходами блока микропрограммного управления четвертый выход которого соединен с тактовым входом регистра, пятый и шестой выходы блока микропрограммного управления - соответственно со счетным входом и входом сброса первого счетчика, выходы первого и второго мультиплексоров и выход блока сравнения подключены соответственно к первому, второму и третьему входам блока микропрограммного управления, тактовый вход которого является тактовым входом устройства, адресные входы первого и второго мультиплексоров соединены с входами первой группы блока сравнения, управляющими входами первой группы блока модификации адреса и являются группой входов задание длины выборки устройства, вторая группа управляющих входов блока модификации адреса является группой входов кода смещения адреса устройства, а управляющий вход блока модификации адреса является входом задания признака расположения данных устройства, информационные входы первого и второго мультиплексоров подключены к прямым выходам соответствующих разрядов реверсивного счетчика.отл и ч ающеесятем.что.сцелью сокращения аппаратных затрат, оно содержит коммутатор NxN (N - разрядность адреса), второй счетчик, третий и четвертый мультиплексоры, причем j-й (j 1. N), информационный вход коммутатора подключен к прямому выходу j-ro разряда реверсивного счетчика, j-й выход коммутатора подключен к J-му информационному входу первой группы третьего мультиплексора, j-й информационный вход второй группы которого подключен к инверсному выходу j-ro разряда реверсивного счетчика, а выходы третьего мультиплексора подключены к соответствующим информационным входам блока модификации адреса, седьмой и восьмой выходы блока микропрограммного управления соединены соответственно со

четным входом и входом сброса второго Счетчика, выходы которого подключены к информационным входам первой группы четвертого мультиплексора и адресным входам первой группы блока постоянной памя- fn, адресные входы второй группы которого подключены к информационным выходам первого счетчика, j-й (J 1, М, М log2N) двухразрядный выход блока постоянной памяти соединен поразрядно с J-ми адресными входами соответственно первой и второй

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 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

Q6

Q7

Условие

0ХО Анализируется выход мультиплексора 10

1Х1 Анализируется выход блока 8

Oi Х2 Анализируется выход мультиплексора 11 1 ХЗ Передается константа для организации безусловного перехода

Продопжение табл.2

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

о

о

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 о о п I 1

о 1 1

о о о I 1 1

Г)

1 о о о 1 1 1 1 о

Таблица 3

Комментарий

Таблица

n

ю cc

О

to

тн

+ 1

2°

Щ

2

От От От

ДёЗЖ яоз.8

msJl

fcH

КО M

xz Ж.

АО

AL

С

SF r-:Hf№t

(BiaxotZ)

Фиг. 2

Г/Г-i -ЛГУ/

,,

C «J /ЈVtJ 1

/( ()

ff/.Jflfff

rj--i

C3

CS

«

,.

№ QCCTJ,fCTZ

. -

LZm

fjfe/vl

..l

C /C24 H

гдг-j-|