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

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

Цель изобретения - расширение области применения устройства путем обеспечения возможности адресации действительной последовательности отсчетов длиной 2 (j 1, 2, .„., N).

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

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

Блок 9 модификации адреса (фиг.2) содержит коммутатор 12, состоящий

со х

СлЭ

со

из групп элементов И 13 и элементов ИЛИ 14, сумматор 15 н декщфра- тор 1бо

Блок 1 (фиго 3) содержит счетчик 17 адреса, блок 18 памяти мшфопро- грамм, регистр 19 микрокоманд, мультиплексор 20 признаков, первьш элемент И 21, второй элемент И 22 и элемент И-НЕ 23.

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

Длина выборки в двоичном коде за дается на входе устройства Длина выборки о На входе признака расположения данньтх в выборке Расположение данных задается признак прямой (М 1) или двоично-инверсной (М 0) адресации. Например, обрабатывается выборка данных длиной 1024 отсчета. При этом двоичный код 0.... 01010, целое двоичное N-разрядное число,равное log 2 1024, прступает на адресные вход мультиплексора 10. На выходе последнего формируется признак (О или 1), если код числа на реверсивном счетчике 2 совпадает с кодом длины последовательности. Для рассматр1шаемого случая (N 1024) номер выхода - десять (одиннад1;а1Ъ1й выход счетчика 2 - нумерация идет от нуля. Появление единицы на выходе мультиплексора 10 сигнализирует об окончании вычислений по слою алгоритма БПФ. По данному сигналу в блоке 1 на его третьем выходе вырабатывается сигнал сброса реверсивного счетчика 2, а в счетчик 3, определяющий номер слоя, сигналом с шестого выхода блока 1 добавляется единица. При этом осу- ществляется переход к вьгаислениям по очередному слою.

Для каждого слоя алгоритма БПФ каналы мультиплексоров 5 коммутиру- ются, как приведено в табЛо 1.

Каждый мультиплексор 5 имеет два адресных входа А1 и АО. Если сформирован код А1 О и АО О, то на вы- ход коммутируется канал ХО, если А1 0, а АО 1, на выход коммутируется канал XI, если А1 1, а АО О, на выход коммутируется канал X2s, если на А1 « 1 иАО - 1, на выход коммутируется канал ХЗ (фиг. 1).

Для этого прошивка блока 7 памяти 11ЫГЛЯДИТ согласно табл 2.

По окончании вычислений по основ ному алгоритму (для выборки 1024 - десять слоев: О, 1, 2, ..., 9) устройство переходит на адресацию в специальный слой (для рассматриваемого примера слой 10) Наличие перехода в специальный слой сигнализи руется блоком 8 сравнения, на вторую группу входов которого подается код номера текущего слоя со счетчика 3, а на первую - код Длина выборки. Окончание вычислений по специальному слою алгоритма БПФ определяется

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

в специальном слое алгоритма БПФ. При наличии сигнала логической еди ницы на пятом выходе блока 1 блок 7 постоянной памяти отключается и на его выходах появляются уровни логической единицыс На адресных входах АО, А1 всех мультиплексоров 5 появ ляются уровни логической единицы. Этим достигается коммутация на выкод информации с информационных входов ХЗ, подключенных к инверсным входам реверсивного счетчика 2. При наличии уровня логического нуля на пятом выходе блока 1 происходит формирование адресов аналогично нулевому слою алгоритма БПФ, так как блок 7 постоянной памяти вклюхген и на его адресные входы поступает код 00... 0.

Управление работой устройства осуществляется блоком 1. Счетчшс 17 адреса с возможностью параллельного занесения информации работает как регистр адреса микрокоманды. Выходы его подключены к входам блока 18 по стоянной памяти, в котором записана микропрограмма работы всего устрой- ствао Считанная из блока 18 постоян ной памяти микрокоманда запоминается в регистре 19 микрокоманд. Выбор адреса след тощей микрокоманды осуществляется путем добавления единицы к содержимому счетчика 17 адреса, либо путем условного или безусловного перехода к требуемому адресу занесения в счетчик адреса 17 парал лельного кода адреса переходзо Адрес перехода определяют разряды мшфо- команды QO-Q5 в поле адресов перехода Переход инициируется сигналом

возникающим на выходе мультиплексора 20 признаков.

Сигнал на выходе мультиплексора 20 признаков появляется в том случае, если в поле признаков перехода Q6, Q7 сформирован код, отличньй от 11, а на адресных входах мультиплексора 20 признаков - код условия перехода ХО-ХЗ (табл. 3).

Разрйды Q8 и Q9 регистра 19 микрокоманд стробируются с помощью элементов 21 и 22 и являются соответственно первым и вторым выходами блока 1 , Выходы разрядов Q10, ..., Q14 регистра 19 микрокоманд являются соответственно пятым, четвертым, третьим, шестым и седьмым выходами 6jioKa 1 о Выход элемента И-НЕ 23 яв™ ляется восьмым выходом блока 1.

Алгоритм работы устройства для формирования адресов представлен на граф-схеме алгоритма (фиг, 4), кодировка микрокоманд которого представлена в табЛо 4, На фиг, 4 введены следующие обозначения;

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

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

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

Зп, RG ( в столбце Q11 табЛо 4) соответствует формированию потенциального сигнала на четвертом выходе блока 1, подключенном к синхровходу регистра 6; inv (О в столбце Q10 табл, 4) , вырабатьгоаемьй только в специальном слое алгоритма БПФ, соответствует формированию потенциального сигнала на пятом выходе блока 1 1 , подключенном к вторым входам ряда 4 элементов И|

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

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

Алгоритм формирования адресов следующий„

, I, Выполняются микрокоманды с ад- ресамиОи1 (десятичный эквивалент двоичного адреса), Б этих микрокомандах осуществляется сброс счетчиков 2 и 3 (сигналы Сброс СТ1 и Сброс СТ2), чем устройство подго- тавливается к работе,

II,Выполняется микрокоманда с адресов 2 о Формируется сигнал ЗпоКС, чем осуществляется запись в регистр 6 адреса первого операнда

нулевой пары операндов (адрес 000,,, 00) о

III,Вьшолняется микрокоманда с адресами 3-5 о В которых формируются сигналы +1 СТ1, а затем и Зп RG,

чем осуществляется запись в регистр 6 адреса второго операнда нулевой пары операндов (адрес 000 ,„, 01), Далее эти операнды могут обрабатываться арнфметическш-j устройством,

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

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

IV,Выполняются микрокоманды с адресами 6-8, Они аналогичны микрокомандам 3-5, В результате их выполнения в регистр 6 заносится адрес первого операнда первой пары операндов (000 ,,, 010),

V Выполняются микрокоманды с адресами 9-11, Они также аналогичны микрокомандам с адресами 3-5, В результате их выполнения в регистр 6 заносится адрес второго операнда

(000 ,,0 011)„

VI, Выполняется циклический участок микропрограммы, содержащий микрокоманды с адресами 12-23, В данном участке.обрабатывается в арифметическом устройстве п-я пара операндов (в момент входа 1-я пара, адресованная микрокомандами с адресами 6-11), За время обработки п-й пары в арифметическом устройстве необходимо

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

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

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

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

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

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

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

VII„ Выполняются микрокоманды с адресами 24 и 23, В них осуществляется формирование операций Сброс СТ1 и +1 СТ2. Добавление единицы в счетчик 3 означает формирование

0

5

0

5

0

5

0

5

0

5

следующего слоя алгоритма БПФ, В микрокоманде 25 анализируется условие XI, которое сигнализирует о переходе в специальный слой алгоритма БПФ.

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

VIII,Выполняется микрокоманда с адресом 26, в которой формируются микрооперации inv и Зп RG, чем осуществляется формирование адреса первого операнда первой пары алгоритма операндов специального слоя (адрес 11- ,,. 11).

IX.Выполняются микрокоманды с адресами 27-29. Данные микрокоманды аналогичны микрокомандам с адресами 3- 5о Сигнал inv не вырабатывается, В результате выполнения этих микрокоманд осуществляется форм1-фование адреса второго операнда первой пары специального слоя (адрес 0000 .,. 001), Первая пара поступает далее

в арифметическое устройство дпя обработки.

Хо Выполняются микрокоманды с адресом 30-32,, Вырабатывается микрооперация inv и Зп RG в микрокоманде 32„ Данные микрокоманда формируют адрес первого операнда второй пары специального слоя (адрес 111,.. 110),

XIо Вьтолняются микрокоманды с адресами 33-35. Данные микрокоманды аналоги шы микрокомандам с адресами, 3-5. В результате выполнения этих микрокоманд осуществляется формирова- адреса второго операнда второй пары специального слоя (000..„010),

XII, Выполняется циклический участок микропрограммы с адресами 36-47. В данном участке обрабатьша- ется в арифметическом устройстве п-я пара операндов (в момент входа в циклический участок вторая пара операндов), адресованная микрокомандами с адресами 30-35, За время обработ ки п-й пары операндов в арифметическом устройстве необходимо адресовать (п-1)-ю пару операндов, обработанную в арифметическом устройстве в преды914

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

Микрокоманды с адресами 36-38 два раза выполняют микрооперацию -1 СТ1 и формируют микрооперацию Зп RG в микрокоманде с адресом 38. Во всех трех микрокомандах сигналом inv осуществляется формирование адреса первого операнда (п-1)-и, пары (на момент входа в циклический участок адрес 1 1 1 ... 1 1 1 ) о

1 О

в устройстве использован блок 9 модификации адреса (фиг. 2). При формировании адресов в двоично-инверсном порядке дешифратор 16 включен (на управляющем входе уровень логического нуля). Дешифратор 16 дешифрует код Длина выборки и выбира- ei в каждой группе только один двух- входовый элемент И из группы элементов И 13„

При формировании адресов в прямом порядке на управляющий вход дешифратора--, 16 поступает уровень логической

Изобретение относится к вычислительной технике и может быть использовано при построении специализированных процессоров БПФ и других ортогональных преобразований. Цель изобретения - расширение области применения устройства за счет обеспечения возможности адресации действительной последовательности отсчетов длиной 2^J. С этой целью в устройство для формирования адресов процессора БПФ, содержащее блок управления, реверсивный счетчик, счетчик, регистр, N мультиплексоров данных, группу элементов И, узел постоянной памяти, введены блок модификации адреса, блок сравнения, первый и второй мультиплексоры. Введение новых блоков и связей позволило выполнять адресацию для вычисления БПФ выборки данных произвольной длины, кратной двум. 1 з.п.ф-лы, 4 ил., 4 табл.

Микрокоманды с адресами 39-41 акало- единицы и выходы его устанавливаются

20

25

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

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

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

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

Б микрокоманде с адресом 38 анализируется условие Х2, Если условие Х2

35

40

в состояние ноля. При этом включаются элементы И, которые обеспечивают формирование канала с прямым следованием разрядов адреса. С выходов группы элементов ИЛИ 14 код адреса поступает на сумматор 15, где суммируется с информацией на выходе устройства Смещение, и поступает на информационные входы регистров для записи ,его туда на время обращения к запоминающему устройству. Суммирование с кодом Смещение, задаваемым извне, позволяет размещать выборки в памяти с

произвольные любого адреса.

Формула изобретения

1 о Устройство для формирования адресов процессора быстрого преобразования Фурье, содержащее блок микропрограммного управления, реверсивный счетчик, счетчик, группу элементов И, труппу из N (где N - разрядность адреса) мультиплексоров, регистр, блок лостоянной памяти, каждый разряд входа адреса которого соединен с выходом соответствующего элемента И группы, j-й двухразрядньй выход (J 1,N) блока постоянной памяти подключен к адресным входам j-ro мультиплексора группы, j-й инверсный выход реверсивного счетчика соединен с первым информационным входом J-го мультиплексора группы, первьй прямой выход реверсивного счетчика соединен с вторыми информационными входами N мультиплексоров группы и третьим информационным входом первого мультиплексора группы, К-й прямой выход (к 2, N-1) реверсивного счетчика соединен с четвертым информационным входом (К-1)-го и третьим входом К-го мультиплексоров группы, N-й прямой выход реверсивного счетравно единице, то это означает, что все пары специального слоя обработаны и окончены все вычисления по специальному слою. Происходит переход к выполнению микрокоманды с адресом 48, т.ео Конец. В противном случае циклический участок выполняется снова Таким образом, на выходах группы мультиплексоров 5 формируются адреса для выполнения алгоритма БПФ и специального слоя алгоритма БПФ дпя произвольной выборки.

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

в состояние ноля. При этом включаются элементы И, которые обеспечивают формирование канала с прямым следованием разрядов адреса. С выходов группы элементов ИЛИ 14 код адреса поступает на сумматор 15, где суммируется с информацией на выходе устройства Смещение, и поступает на информационные входы регистров для записи ,его туда на время обращения к запоминающему устройству. Суммирование с кодом Смещение, задаваемым извне, позволяет размещать выборки в памяти с

произвольные любого адреса.

Формула изобретения

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

чика соединен с третьим информационным входом N-ro мультиплексора груп- itti, входы с /ммирования, вычитания и сброса реверсивного счетчика соединены соответственно с первым, вторым и третьим входами блока микропрограммного управления, четвертый выход которого соединен с тактовым входом

регистра, а пятый - с первыми входами элементов И группы, вторые входы которой соединены с соотззетствзтощими выходами счетчика, шестой выход блока микропрограммного управления под- ктаочен. к входу чтения блока постоянной памяти, отличающееся темэ что, с целью расширения области применения устройства путем обеспечения возможности адресации действительной последовательности отсчетов длиной 2 в него дополнительно введены блок сравнения, блок модифшса- ции адреса, первый и второй мультиплексоры,, j-e информационные входы которьпс соединены с соответствующим прямым выходом реверсивного счет , выходы первого, второго мультиплексоров и блока сравнения подключены соответственно к первому, второму и третьему входам логических условий блока микропрограммного управления, тактовый вход которого является тактовым входом устройства, и шестой выходы блока микро- nporpaf-iMHoro управления соединены соответственно со счетным входом и входом сброса счетчика, выходы которого подключены к первой группе входов блока сравнения, адресные входы первого и второго мультиплексоров

1 2

0

5

0

5

0

5

0

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

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

Таблица 1

Таблица 2

Таблица 4

Продолжение табл,4