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

 

Союз Советских

Социалистических

Республик

К АВТОИ:КОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. саид-ву— (22)Заявлено 02.09.80 (2l} 2979525/18-24 с присоединением заявки М (23) Приоритет

Опубликовано 23.04.82. Бюллетень И15

Дата опубликования описания 23.04.82 ьцм. кл.

G 06 F 15/332

Коеудеретеениьй камнтет

СССР по делам изобретений н.еткритнй (т8) УЙК 681. .32

{088.8) (72) Авторы изобретения

А.И.Шемаров и А.И.Никонов (71) Заявитель

Иинский радиотехнический институт (54)УСТРОЙСТВО ДЛЯ ФОРИИРОВАНИЯ АДРЕСОВ

ПРОЦЕССОРА БЫСТРОГО ПРЕОБРАЗОВАНИЯ

ФУРЬЕ

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

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

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

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

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

sxop, группы элемейтов ИЛИ соединены

922

763

4S

50 соответственно с пятым, шестым, седьмым и первым входами устройства.

На второй, третий, четвертый, пятый, шестой, седьмой входы устройства

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

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

Цель изобретения — упрощение и повышение быстродействия устройства.

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

-второй и третий, выходы которого соединены соответственно со входом суммирования, входом вычитания и тактовым входом первого реверсивного счетчика, выход переноса и выход заема которого соединены соответственно с cóìèèðóþùèì и вычитающим входами второго реверсивного счетчика, выходы которого соединены со входами дешифратора, выход старшего разряда которого подключен к первому входу блока управления, второй вход которого является тактовым входом устройства, а четвертый выход блока управления соединен с тактовым входом регистра, выходы которого являются выходами устройства, содержит Х узлов блокировки, каждый иэ которых содержит элемент, ИЛИ-НЕ, элемент И-НЕ и два сумматора по модулю два, причем выход элемента ИЛИНЕ подключен к первому входу первого сумматора по модулю два, выход которого соединен с первым входом второго сумматора по модулю два, второй вход первого сумматора помодулю два соединен с выходом элемента И-НЕ, первый вход которого объединен с первым входом элемента ИЛИ-НЕ, при этом второй вход элемента ИЛИ-НЕ

i-го (1=1, Й) узла блокировки соединен с 1-ым информационным выходом первого реверсивного счетчика, второй вход элемента И-HE 1-го узла блокировки (1-1, Й) соединен с пятым выходом блока управления, второй вход второго сумматора по модулю два 1-го (i=1, Й) узла блокировки соединен с шестым выходом блока управления, а выход второго сумматора по модулю два i-ro (i=1, Й) узла блокировки соединен с 1-ым (i

=1, Й) информационным входом регистра и л-ым (i=l, Й) информационным входом первого реверсивного .счетчика, причем 1-ый выход (i O, Й-Т) дешифратора подключен к первому входу элемента ИЛИ-НЕ i+ I-ro (i =l, М) узла блокировки.

Кроме того, блок управления содержит сдвиговый регистр, пять элементов ИЛИ и девять элементов И, причем первые входы первого, второго, третьего, четвертого, пятого, шестого и седьмого элементов И объединены

„Й являются первым входом блоке управления, выход седьмого элемента И является первым выходом блока управления, выход первого элемента ИЛИ подключен ко вторым входам пятого и шестого элементов И, выходы восьмого и девятого элементов И являются соответственно вторым и третьим выходамн блока управления, выход второго элемента ИЛИ является четвертым выходом блока управления, а выходы пятого и шестого элементов И являются соответственно пятым и шестым выходами блока управления, первый выход сдвигового регистра соединен с первым входом четвертого элемента

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

Устройство для формирования адресов алгоритма быстрого преобразования Фурье содержит блок 1 управления, первый реверсивный счетчик 2, второй реверсивный счетчик 3, дешифратор 4, 5 9 первому входу третьего элемента K5f второму входу второго элемента И и первому входу пятого элемента ИЛИ, четвертый выход сдвигового регистра соединен со вторым входом третьего элемента ИЛИ, пятый выход сдвигово" го регистра соединен со вторым вхо" с дом первого элемента HJIH; третьим

iBxo+oM второго элемента ИЛИ, третьим входом третьего элемента ИЛИ и вторым входом четвертого элемента И, шестой выход сдвнгового регистра

)соединен с информационным входом, сдвигового регистра, четвертым входом второго элемента ИЛИ и вторым входом третьего элемента И, выход третьего элемента ИЛИ соединен со вторым входом седьмого элемента И, выход первого элемента И соединен со вторым входом четвертого элемента ИЛИ, выход которого подключен к первому входу восьмого элемента

И, выходы второго, третьего и четвертого элементов И соединены соот" ветственно со вторым, третьим и четвертым входами пятого элемента

ИЛИ, выход которого подключен к первому входу девятого элемента И, второй вход которого объединен со вто- рым входом восьмого элемента И, третьим входом седьмого элемента И, тактовым входом сдвигового регистра н является вторым входом блока управления.

Принцип работы устройства заключается в следующем.

Адреса пары операндов алгоритма быстрого преобразования Фурье отлиэ чаются информацией в одном разряде, номер которого соответствует номеру слоя алгоритма быстрого преобразования Фурье, причем адрес первого операнда содержит логический ноль в данном разряде, а адрес второго операнда - логическую единицу. Если заблокировать данный разряд, т.е. не пропускать информацию данного разряда на выходе- устройства, а вместо информации заблокированного разря да подавать на соответствующий вы- " ход устройства уровень логического нуля или единицы, то можно адресовать пару операндов (первый и второй операнды соответственно). Каждое состояние счетчика адресует пару опе рандов, поэтому счетчик обладает избыточностью.

ДХ я устранения избыточности вводится операция восстановления перво5

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

\ счет применения параллельного счетчика, который не мог применяться совместно с блокЬм реконфигурации

1 счетчика.

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

Адресуется пара операндов и, 2 -и, и где n=1,2 "-11 и — количество раз-. рядов первого счетчика.

Формирование адресов осуществляется следующим образом.

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

Фурье.

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

763 8 нуля, а на выходе 1 — уровень логической единицы. Данные уровни поступают на вторые входы узлов 5, при этом информация с разрядных выходов е а 2-20 2 21-", 2 " 2Мчерез два инвертара и повторитель (элементы ИЛИ-НЕ, первый и второй

М2) поступают íà вхопы регистра

6 D, 0 ... D " 0 D" D 1+ на вход 0 регистра 6 поступает информация с четвертого выхода блока

1 управления через инвертор и два повторителя (элементы И-НЕ, первый и второй M2) i ãî узла 5. В счетчике

2 хранится информапия, адресующая и-ую пару операндов, В первом такте на втором выходе блока l управления вырабатывается сигнал, по которому производится вычитание единицы из счетчика 2, чем адресуется и-1-ая пара операндов.

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

2 на первом выходе блока 1 управления при сигнале на четвертом выходе блока 1 управления равному логическому нулю. в результате чего s l - ом разряде счетчика 2 восстанавливается значение логической единицы, а по заднему фронту сигнала на шестом выходе блока 1 управления в регистр 6 заносится адрес второго операнда и-1-ой пары, В первой половине пятого такта вырабатывается сигнал на третьем выходе блока 1 управления, по которому в счетчик 2 добавляется.единица и тем самым адресуется

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

2 добавляется единица и тем самым

7 922

2 2 узлов блокировки разряда 5 и ре-., гистр 6.

Каждый узел блокировки 5 содержит элемент 2 И-НЕ, элемент 2 ИЛИ-НЕ и два сумматора по модулю два М2 (не

/указаны).

Блок управления содержит сдвиговый регистр 7, элемент ИЛИ 8, элемент

ИЛИ 9, элемент ИЛИ 10, элемент И )1, элемент И 12, элемент И 13, элемент 10

И 14, элемент И 15, элемент И 16,. элемент И 27, элемент ИЛИ 18, элемент

ИЛИ 19, элемент И 20, элемент И 21.

Устройство для формирования адресов алгоритма быстрого преобразова- 15 ния Фурье функционирует следующим образом.

В первоначальном состоянии все счетчики обнулены, а регистр 7 блоКа l управления установлен в состоя- щ ние "10000000". На управляющий вход регистра 7 поступают тактовые импульсы и логическая единица продвига ется по регистру 7, который функцио- . нирует как кольцевой регистр. Уп- 25 равляющие сигналы вырабатываются комбинационной схемой, состоящей из элементов 8-21 {фиг. 2)- Согласно приведенной вре .енной диаграмме фиг. 3, где ТИ - тактовые импульсы, 50

А2-АЯ - разрядные выходы регистра 7, 22 — сигнал на первом входе блока 1, 23 - сигнал на третьем выходе блока

1, 24 - сигнал на втором выходе блока

25 — сигнал на .первом выходе бло35 ка 1, 26 - сигнал на шестом выходе блока 1, 27 — сигнал на четвертом выходе блока 1, 28 — сигнал на пятом выходе блока 1.

Рассмотрим функционирование устройства при обработке и-ой пары i-го слоя алгоритма быстрого преобразования Фурье.

Пусть в данном цикле (8 тактов} обрабатывается и-ая пара I-го слоя

45 алгоритма быстрого преобразования

Фурье. Во время обработки и-ой пары операндов должна быть адресована и-1-ая пара операндов для записи их в запоминающее устройство(эта. пара обработана в предыдущем цикле), 50 и a+I-ая пара операндов дпя считывания их из запоминающего устройства (эта пара будет обработана в следующем цикле). Номеру слоя соответствует состояние счетчика 3. В соот55 ветствии с этим состоянием иа выхо,дах дешифратора 4 — О, 1, 2

1+1 появляется уровень логического

9 922763

10 адресуется и+1-ая пара операндов, а во второй половине вырабатывается сигнал на первом выходе блока 1 управления, при сигнале на четвертом выходе блока 1 управления равном ло- 5 гической единице, тем самым в ) -ом разряде счетчика 1 восстанавливается значение логического нуля. Кроме того, в шестом такте вырабатываешься сигнал на шестом выходе блока 1 управле- 16 ния, по заднему фронту которого в регистр 6 заносится адрес первого операнда и +1-ой пары. В седьмом такте управляющие сигналы не вырабатываются. В восьмом такте вырабатывается 15 сигнал на шестом выходе блока l управления, при сигнале на четвертом выходе блока 1 управления, равном логическому нулю, по заднему фронту которого в регистр 6 заносится адрес 20 второго операнда n +I-ой пары.

Цикл повторяется до .тех пор, пока не будут обработаны все пары опЕрандов по всем слоям, после чего устройство начинает вырабатывать адреса 25 пар операндов специального слоя безизбыточного алгоритма быстрого преобразования Фурье. При этом на выходах дешифратора 4 — О, l, 2, ° ° .й"! устанавливается уровень логического ну- Зб ля, а на выходе !ч уровень логической единицы. Пи один из разрядов счетчика 2 не блокируется. Информация с разрядных выходов счетчика 2 через два инвертора и повторитель (сигнал на пятом выходе блока 1 управления равный логическому нулю) — элементы

ИЛИ-НЕ, первый и второй М2 или же через три инвертора (сигнал на пятом выходе блока 1 управления) элементы

ИЛИ-НЕ, первый и второй М2, поступает на.информационные входы регистра. 6, Пусть в данном цикле необходимо обработать и-ую пару операндов спе- .циального слоя (адреса и и 2 -n).

М

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

n+1-ая пара операндов (адреса n+1 и

N $0

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

В первом такте блоком l управлеSS ния вырабатывается сигнал на втором выходе, по которому из счетчика 2 вычитается единица, чем адресуется первый операнд и-1 пары. Во втором такте на втором выходе блока управления вырабатывается сигнал, по которому из счетчика 2 вычитается единица, кроме того, на шестом выходе бло" ка 1 управления вырабатывается сигнал занесения в регистр 6 при сигнале на пятом выходе блока управления 1, равном логической единице, по заднему фронту которого в регистр 6 заносится адрес второго операнда и-i-ой пары (2 -и+1) . В третьем такте управляющие сигналы не вырабатываются. В четвертом такте вырабатывается сигнал на третьем выходе блока

1 управления, по которому в счетчик

2 добавляется единица, кроме того, на шестом выходе блока 1 управления вырабатывается сигнал, при сигнале на пятом выходе блока 1 управления, равном логическому нулю, по заднему фронту которого в регистр 6 заносится адрес первого операнда и-)-ой пары (n-13 . В пятом такте вырабатывается сигнал íà третьем выходе блока 1 управления, по которому в счет" чик 2 добавляется единица. В шестом такте вырабатывается сигнал на шестом выходе блока 1 управления, при сигнале нз пятоМ выходе блока управления, равном логической единице, по заднему фронту которого в регистр

6 заносится адрес второго операнда

n+1-ой пары (2"-и- Q . В седьмом такте управляющие сигналы не вырабатываются. В восьмом такте вырабатывается сигнал на третьем выходе блока управления, по которому в счетчик

2 добавляется единица, кроме того вырабатывается сигнал на шестом выходе блока управления при сигнале на пятом выходе блока 1 управления, при сигнале иа пятом выходе блока 1 управления, равному логическому нулю, по заднему фронту которого в ре" гистр 6 заносится адрес первого one" ранда п+1-ой пары операндов )n+l) . !

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

После обнулЕния счетчиков 2 и 3 устройство снова готово. к работе.

Таким образом, изобретение позволяет упростить конструкцию блока и повысить быстродействие.

922763

1J

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

Устройство для формирования адресов процессора быстрого преобразования Фурье, содержащее первый и второй счетчики, дешифратор, регистр и блок управления, первый, второй и третий выходы которого соединены соответственно с входом суммирования, входом вычитания и тактовым входом to первого реверсивного счетчика, выход переноса и выход заема которого соединены соответственно с суммирующим и вычитающим входами второго реверсивного счетчика, выходы которого 1ф соединены с входами дешифратора, выход старшего разряда которого подключен к первому входу блока управления, второй вход которого является тактовым входом устройства, а четвер- щ тый выход блока управления соединен с тактовым входом регистра, выходы которого являются выходами устройства, отличающееся тем, что, с целью упрощения устройства и повышения быстродействия, оно содерб . жит N узлов блокировки, каждый из которых содержит элемент ИЛИ-НЕ, элемент 1

° И-НЕ и два сумматора по модулю два, причем выход элемента ИЛИ-НЕ подключен к первому входу первого сумматора по модулю два, выход которого соединен с первым входом второго сумматора по модулю два, второй вход первого сумматора по модулю два соединен с выходом элемента И-НБ, первый вход

33 которого объединен с первым входом элемента ИЛИ-НЕ, при этом второй вхбд элемента ИЛИ-НЕ i-го (i=i, К) узла

° блокировки соединен с 1-ьщ информаци40 онным выходом первого реверсивного счетчика, второй вход элемента И -НЕ

i "ãî узла блокировки (i =Г, Й) соединен с йятым выходом блока управления, второй вход второго сумматора по модулю. два -ro (i=i, М) узла

45 блокировки соединен с шестым выходом блока управления, а выход второго сум матора по модулю два i-ro (i=1, Й) узла блокировки соединен с i-ым (i=

=1, Й) информационным входом регистра и i-ым (11, Й) инФормационным входом первого реверсивного счетчика, причем i-ый выход (1=0, Й"1) дешифратора подключен к первому входу элемента ИЛИ-НЕ i+i-ro (i=i, М) узла блокировки.

2. Устройство по п. 1, о т л и " ч а ю щ е е с я тем, что блок управления содержит сдвиговый регистр, пять элементов ИЛИ и девять элементо

И, причем первые входы первого, второго, третьего, четвертого, пятого, шестого и седьмого элементов И объединены и являются первым входом блока управления, выход седьмого элемента И является первым выходом блока управления, выход первого элемента HJJH подключен к вторым входам пятого и шестого элементов И, выходы восьмого и девятого элементов И являются соответственно вторым и третьим выходами блока управления, выход второго элемента HJJH является четвертым выходом блока управления, а выходы пятого и шестого элементов

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

ИЛИ, выход которого подключен к первому входу девятого элемента И, второй вход которого объединен с вторым входом восьмого элемента И, третьим входом седьмого, элемента И, тактовым входом сдвигового регистра и.являет13 ся вторым входом блока управления °

Источники информации, принятые во внимание при экспертизе

922763 14

I. Авторское свидетельство СССР

У 430381, кл. 6 06 F 9/00,. 1975.

2. Авторское свидетельство СССР

9548863,кл. G 06 F 15/332,1976(прототип), 5

922763 """ 1 g 3 Ф Х Ф 7 8 I g У Ф Ф У Т У

h$

Л7

Фраз

Составитель А.Баранов

Техред И. Гайду Корректор Н.Макаренко

Редактор Н.Пушненкова

Филиал 11ПП 11атент, r .. Ужгород, ул. Проектная, 4

Заказ 2583/65 Тираж 732 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5