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

вым входом k-ro элемента ИЛИ группы, второй вход которого подключен к выходу второго элемента И k-ой пары группы, а выход k-ro элемента ИЛИ группы является управляющим выходом k-разрядного счетчика, вторые входы элементов И группы являются информационными входами k-разрядного счетчика, причем второй вход первого, элемента И во всех парах группы является инверсным входом k-разрядного счетчика, а первые входы элементов И первой пары группы соединены с управляющим входом k-разрядного счетчика.

4. Устройство по п. 1, отличающееся тем, что блок формирования адреса содержит группу элементов И и группу элементов ИЛИ, состоящих из k элементов каждая, выходы каждого элемента И группы соединены с первыми входами соответствующих элементов ИЛИ группы, выходы которых являются выходами блока формирования адреса, вторые вхбды элементов ИЛИ группы являются первой группой входов блока формирования адреса, первые входы элементов И группы образуют вторую группу входов блока формирования адреса, а вторые входы элементов И группы соединены с управляющим входом блока формирования адреса.

1. УСТРОЙСТВО ДЛЯ АДРЕСАЦИИ ПРОЦЕССОРА БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее (m+k)-разрядный; регистр адреса, выходы которого являются выxoдa и устройства, блок формирования адреса, первая группа входов которого соединена с информа ционными выходами k-разрядного счет чика,. а вторая группа входов блока формирования адреса подключена к выходу k-разрядного регистра сдвига, выходы которого соединены с информационными входами к-разрядного счетчика, управляющий вход регистра ад- реса, первый управляющий вход регист--ра сдвига и управляющий вход блока формирования адреса соединены соот- ветственно с первым, вторым и третьим выходами блока синхронизации, отличающееся тем,-что, с целью расширения его функциональных возможностей за счет обработки п мерных процессов и упрощения схемы, в него введен т-разрядный счетчик, вход которого соединен с третьим выходом блока синхронизации, а информационные выходы т-разрядного . счетчика соединены с первой группой входов регистра адреса, вторая группа входов которого подключена к выходгш блока формирования -адреса, выход т-го разряда соединен с управляххцим входом k-разрядного счетчика управляющий выход которого подключен к управляющему входу k-pa8« рядного регистра сдвига, а выход ;k-ro разряда регистра сдвига соединен с входом блока синхронизации. 2.Устройство по п. 1, о т л ичающееся тем, что блок синхронизации содержит первый и второй триггеры, генератор одиночного импульса, элемент И, элемент задержки, генератор тактовых импульсов, выход которого соединен с первымвходом элемента И, выход которого соединен с первым входом элемента И, выход которого подключен к входу элемента задержки и является первым выходом блока синхронизации, вход установки в нуль первого триггера и вход установки в единицу второго триггера соединены с выходом генератора СО .одиночного импульса, выход которого является вторым выходом блока синхронизации, выход элемента задержки соединен со счетным входом первого триггера, выход которого является третьим выходом блока синхронизации, вход установки в нуль второго триггера подключен к входу блока синхронизации, а выход второго триггера соединен с вторым входом элемента И. 3.Устройство по п. 1, о т л ичающееся тем, что k-разряд4;:аь ный счётчик содержит k пар элеменсо тов И, k элементов ИЛИ и k триггеров, выход первого элемента И группы в i-ой паре

Изобретение относится к специали зированным средствам вычислительной техники и может быть применено в системах цифровой обработки сигналов , в информационно-измерительных системах, в устройствах формирования и анализа случайных процессов. Известно устройство адресации процессора быстрого преобразования Фурье, содержащее блок реконфигураНИИ счетчика, выход которого соединен с управляющим входом счетчи.ка, б,лок выдачи адресов, первый информационный вход которого соединен с выходом счетчика, а выход - с выходом устройства .в целом, причем вход блока реконфигурации счетчика, первый и второй, счетные входы счёт чика и первый управляющий вход блок выдачи- адресов соединены соответственно с перВЕлм, вторым, третьим и четвертым входами блока, выход счет чика соединен с информационным входом регистра и первым входом группы элементов ИЛИ, выход регистра и выход группы элементов ИЛИ соединены соответственно с вторым и третьим информационными входами блока выдач сшресов, второй и третий управляющие входы которого, управляющий вход регистра и второй вход группы схем ИЛИ соединены срответственно с пятым, шестым, седьмым и первым входс1ми блока Cl. Недостатком данного устройства является сложность построения и невозможность использования в процессоре с параллельной обработкой л мерных векторных процессов. Наиболее близким по технической сущности к предлагаемому является устройство ёшресации процессора быстрого преобразования Фурье, содержащее блок выдачи адреса, вход которого соединен с выходом сумматора и через блок выдачи информации с выходом счетчика, представляющего собой двоичный счетчик с логической схемой, позволяющей делить его на две части, причем вхрд сумматора соединен с.выходом блока ввода информации в сумматор, выход блока разделения счетчика соединен с управляющими входами счетчика и блока ввода информации в сумматор, информационнввй вход которого соединен с выходом счетчика и выходом блока выдачи информации. Синхронизацию работы всего устройства осуществляет блок управляющих импульсов и потенциалов 2. Недостаток известного устройствасложность построения: наличие сумматора и двоичного счетчика со специальной логической схемой, позволяющей делить его на две части, а также невозможность адресации операндов при обработке п -мерных векторных процессов, кроме того, сложность переналадки устройства для реализации другой разновидности алгоритма быстрого преобразования Фурье, например, прореживания по времени с инверсным или прямым упорядочением выходных данных, т.е. малая степень унификации устройства. Таким образом, основными недостатками известных устройств адресации процессора быстрого преобразования Фурье являются малые функциональные возможности невозможно использовать устройство в процессоре обраб тки п. -мерных векторных :процессов), сложность структурной реализации; малая степень унификации.

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

Поставленная цель достигается тем, что в устройство для адресации процессора быстрого преобразования Фурбе, содержащее (m+k)-разрядный регистр адреса,, выходы которого являются выходами устройства, блок формирования адреса, первая группа входов которого соединена с информационными выходами k-разрядного. счетчика, а вторая группа входов блока формирования .адресу подключена к выходу k-разрядного регистра .сдвига, выходы которого соединены с йнформационныко входами k-разрядного счетчика, управляющий вход регистра, первый управляющий вход регистра сдвига и управляющий входо блока формирования адреса соединены соответственно с первым, вторым и третьим выходами блока синхронизации, введен т-разрядиый счетчик, вход которого соединен с третьим выходом блока синхронизации, а информационные выходы т-разрядного счетчика соединены с первой группой входов регистра адреса, вторая группа входов которого подключена к выходгш блока формирования гщреса дыходт-го разряда соединен с управляющим входом k-разрядного счетчика, управляющий выход которого подключен к второму управляющему в ходу k-разрядного регистра сдвига, а выход k-ro разряда регистра СДБЙга соединен с входом блока синхро- низации.

Причем блок синхронизации содержит первый и вторсЛ триггеры, генератор одиночного импульса, элемент И, элемент задержки, генератор та ктовых импульсов, выход которого соединен с первым входом элемента И, выход которого подключен к входу элемента задержки и является. перВЕЛМ выходом блока синхронизации, вход установки в нуль первого триггера и вход установки в единицу второго триггера соединены с выходом.генератора одиночного импульса, выхо|1. которого является вторым выходом ., блока синхронизации, вшод эллмента эгшержки соединен со счетным входом первого триггера, выход которого Является третьим выходом блока синхронизации, вход установки в нуль второго триггера подключен к. входу ёлока синхронизации, а выход второгй триггера соединен с вторым вводом элемента И. f

При этсм k-разрядный счетчик содержит k пар элементов И, k элементов ИЛИ н k триггер ов, выход первог элемента И группы в 1-й паре 1 « « 2, k) соединен с первьм входом

(i-l)-ro элемента ИЛИ группы, второй вход которого соединен с выходом второго элемента И в (1-13-ой паре группы, а выход (i-l)-ro элемента Т ИЛИ соединен со счетным входом i-го триггера группы, выход (i -1)-го триггера группы соединен с первыми входами элементов И в i-ft паре группы, выход первого элемента И в первой паре группы соединен- со

0 счетным входом первого триггера, а выход k-ro триггера группы соединен с первым входом k-ro элемента ИЛИ группы, второй вход которого подключен к выходу второго элемента И

5 k-ой пары группы, а выход k-ro элемента ИЛИ группы является управляющим выходом k-разрядного счетчика, вторые входы элементов И группы являются информационными входами kразрядного счетчика, причем второй

0 вход первого элемента И во всех парах группы является инверсным входом k-разрядного счетчика, а.первые входы элементов И первой пары группы соединены с управляющим входом k-раз5рядного счетчика, причем блок формирования адреса содержит группу элементов И и группу элементов ИЛИ, состоящих из k элементов каждая, йыходы каждого элемента И группы со0единены с первыми входами соответствующих элементов ИЛИ группы, выходы которых являются выходс1ми блока формирования адреса, вторые входы элементов ИЛИ группы являются первой

5 группой входов блока формирования адреса, первые входы элементов И группы образуют вторую группу входов блока формирования адреса, а вторые входы элементов И группы со

0 единены с управляющим входом блока формирования адреса.

На фиг. 1 показана структурная схема устройства для адресации про цессора быстрого преобразования Фурье; на фиг. 2 - структурная схе5ма блока синхронизации; на фиг. 3 времен1ше диаграммы, поясняющие принцип работы блока синхронизации, на фиг. 4 ю функциональная схема k-разрядного первого счетчика; на

0 фиг. 5 - функциональная схема блока формирования адреса.

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

Блок 5 синхронизации предназначен

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

5 нератор 7 тактовых импульсов, элемент И 8, элемент Sf задержки, первый триггер 10, второй триггер-41, генератор 12 одиночного импульса. К-разрядный первый счетчик 3 с упраЪляемЯмй цепями переноса предназначен для подготовки базы сщреса. Его разрядность определяется следующим образом: k log2N, . где N-2 - количество элементов в компоненте Х входного вектора , .... хД п - мерность векторного про -цесса; Т - знак транспортирования вектора, матрицы. К-разрядный первый счетчик 3 со держит (фиг. 4) группу элементов И 13 из k пар элементов И, группу элементов ИЛИ 14 из k элементов ИЛ и группу триггеров 15 из k триггер Второй т-разрядный счетчик 6 не обходим для формирования базы адре са при обработке п-мерных векторны процессов, разрядность m которого определяется согласно выражению m EntdogAn) +1. Второй m-разрядный счетчик б представляет собой двоичный суммирующи счетчик с коэффициентом пересчета, равным мерности п обрабатываемого векторного процесса. Блок формирования адреса 2 назначен для формирования адресов элементов обрабатываемого массива в соответствующих, базовых операция алгоритма быстрого преобразования Фурье с учетом полученных баз в k-разрядном первом счетчике 3 и в регистре 4 сдвига. Блок 2 формирования адреса (фиг. 5) содержит гру пу элементов И 16 и группу элементов ИЛИ 17, состоящих из k элементов .-. Регистр адреса 1 предназначен для фиксирования адреса элементов обрабатываемого векторного процес са в соответствукядих базовых опера циях алгоритма быстрого преобразов ния Фурье, Он представляет собой (in+k)-разрядный регистр хранения информации, k-разрядный регистр 4 сдвига служит для управления цепями переноса k-разрядного первого счетчика 3. Он представляет собой k-разрядный регистр сдвига на один разряд, в котором также имеются цепи занесения определенного кода в разряды. Устройство адресации процессора быстрого преобразования Фурье рабо тает следующим образом. По сигналу с выхода 2 блока синхронизации в регистр 4 сдвига заносится код 100... 0. Данная единица по сигналу с управляющего выхода К-разрядного первого счетчика 3 сдвигается вправо (в сторону младших разрядов) на один разряд после выполнения каждой итерации в алгоритме быстрого преобразования Фурье. Следовательно, на одном из выходов k-разрядного регистра 4 сдвига будет потенциал единицы, что будет разрешать перенос из (1-1)-го разряда в (1+1)-ый и запрещать перенос в t-ый разряд k-разрядного первого счетчика 3, т.е. единица на 1-ом выходе k-paзpяднor;o регистра 4 сдвига поступает на 1-ую пару элементов И группы 13 k-разрядного первого счетчика 3 и запрещает прохождение единицы переноса с (J-l)-ro разряда через (1-1)-ый элемент ИЛИ группы 14 в 1-ый разряд данного счетчика, с другой стороны потенциал единицы на 1-ом выходе К-разрядного регистра 4 сдвига разрешает прохождение данной единицы переноса через 1-ый элемент ИЛИ группы 14 в (+1)-ый разряд fc-разрядного первого счетчика 3. -Следует .отметить, что -ай разряд данного счетчика будет в нуле и в течение выполнения 1-ой итерации не изменится его состояние. Здесь номер 1-го разряда соответствует fk - (-1) номеру итерации в алгоритме быстрого преобразования Фурье. Данный код в регистре 4 сдвига на k - (-1)-ой итер&ции выполнения алгоритма быстрого преобразования Фурье участвует в формировании адресов операндов базовых операций, вычисляемых на этой итерации,:соответствующих компонент векторного процесса. Согласно алгоритму быстрого преобразования Фурье на каждой итерации происходит обработка базовых операций всех компонент вектора x(Xv , т.е. устройство адресации процессора быстрого преобразования Фурье должно определя:ть адреса операндов базовых операций компоненты ), i i, Н вектора Х, затем Xjd), ... X (1). Для этого блок. 5 синхронизации выдает все последовательности сигналов ТИ1 и ТИЗ (фиг. 2 и 3) на первом и третьем выходах соответственно. Сигналы ТИЗ образуются путем деления в два раза частоты задержанных сигналов ТИ1. Это осуществляется с помоцыб элемента 9 задержки и второго триггера 11 Время i и частота cifTHaлов ТИ1 определяется, исходя из

лительности вычисления базовой опеации операционным автоматом процес сора быстрого преобразования Фурье.. Согласно алгоритму БПФ на каждой итерации первыми определяются адреса операндов базовой операции компоненты Xj вектора X , затем компбненты. Xj, ..,, Хр. Поэтому по первому сигналу последовательности ТИ1 с перво-го выхода блока 5 синхронизации содержимое т-разрядного счетчика 6 записывается в первые m старших разрядов регистра 1 адреса, а содержимое k-разрядного счетчика 3 через группу элементов ИЛИ 17 блока 2 формирования адреса передается в последующие k разрядов (m+k)-разрядного регистра адреса. При этом определяется адрес первого элемента Х компоненты Х вектора X в базовой операции. Затем формируется первый сигнал последовательности ТИЗ с третьего выхода блока 5 синхронизации на управляющий вход блока 2 формирования адреса и разрешает передачу чег рез группу элементов И 16 и группу элементов ИЛИ 17 на k младших информационных входа регистра 1 адреса содержимое k-раз.рядного счетчика 3 и регист1 а 4 сдвига. Далее согласно алгоритм5( работы блока 5 синхронизации (фиг.I 3). поступает второй сигнал последовательности ТИ1 с первого выхода блока 5 синхронизации на уп1)авдяквдий вход регистра 1 адреса, г по которому, содержимое т-разрядного счетчика б, k-разрядного счетчика 3 и регистра 4 сдвига записывается . В (m+k)-разрядный регистр адреса. При этом, как отмечалось выше, в J-ый разряд регистра 1 адреса на , Qk - (1-1)-ой итерации запишетсяединица,, так KJK в этом разряде k-разряднЬго счетчика 3 на дайной итерации всегда ноль. Полученный адрес в регистре 1 адреса определяёт второй элемент Х,(2 компоненты . Х вектора Х в базов эй операции. По заднему фронту данного сигна-5 ла йоследовательности ТИЗ в т-разрядный счетчик добавится единица.

Далее по следующей паре сигнгшрв последовательности ТИ1 сигналу по- V следовательности ТИЗ аналогично описанному выше формируются адреса элементов компоненты К.2 зектора Х. Снова к содержимому т-разряя- него счетчика 6 прибавляется едини- . ца по заднему фронту сигнала последовательности ТИЗ. Затем аналогично определяются адреса элементов Xj2 компоненты X, вектора базовой операции и т.д. И, наконец, фбрмируются адреса элементов X, иХо2

базовой

компоненты X.. вектора

операции. По заднему фронту сигнала последовательности ТИЗ с третьего выхода блока 5 синхронизации к содержимому т-разрядного счетчика 6 добавляется единица, счетчик переполняется, так как в нем было код

11 4. 1

при п log22 и по сигналу

п -

0

переполнения т-разрядного счетчика .происходит добавление единицы к содержимому k-разрядного счетчика, .(алее процесс продолжается аналогич но описанному выше и определяются

5 адреса элементов компонент Х,,, Х,, ..., Хр вектора X следующих бабочек на fk - ( Е-1)-ой-итерации.

Сигнал переполнения k-разрядного счетчика 3 означает окончание данной итерации. Он поступает на управляющий вход регистра 4 и сдвигает хранящуюся в нем единицу на один разряд вправо (в сторону младших разрядов). Далее начинается форми5рование адресов на следующей .ции(k-l) аналогично описанному выше. После .формирования адресов последней k-ой итерации по сигналу переполнения с управляющего выхода

0 k-разрядного счетчика 3 производится сдвиг содержимого, регистра 4, по сигналу с которого выдвигаемая за пределы регистра единица поступает на вход блока 5 синхронизации и.устанавливает в ноль первый триггер 11,

5 что обеспечит нулевой потенциал на входе элемента И 8, а это запретит формирование последовательностей сигналов ТИ1 и ТИЗ. На этом кончается один цикл работы устройства гшре0сации процессора быстрого преобразования Фурье, и устройство готово к работе с новыми исходными данными, с новым вектором xJ.

5

i

Таким образом, используя данный подход для реализации устройства адресации Процессора быстрого преобразования Фурье, оказывается возможным проводить обработку п-мерных

0 векторных процессов, что особенно важно при построении цифровых систем управления пространственно-многомерными случайными вибрациями, при этом возможно построение матрич5ных процессоров обработки п-мерных векторных процессов.

Креме того, устройство отличает простота технической реализации (от-. сутствие сумматора, счетчика со спе0циальной разделительной схемой).

f/fo/teq/

r fffMff /

;ж/7л/у:/ йг//

Iptff.f

f-/fajfleu jvfff /fff em fysari ififf/уегг / /м сч / / -yfe t/vcAfi/f /Ю f f//fi/ y ff yfM-evwfff /fr /wj/ffjt eff (Уел7« улу ff

0if.4

ff /TO/fff

6/jr.

ff/7 /rffA-ff f

f/fff f

Фуг.