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

 

О П И С А Н И Е 999062

ИЗОБРЕТЕНИЯ

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

Социаяиетиче сник

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (6) ) Дополнительное к авт. свид-ву

Ф (22) Заявлено 14. 09. 81 (2 t ) 3335706/18-.24 (51)M; Кл.

0 06 F 15/332 с присоединением заявки М

Гевумрвтваивй квинтет

СССР (23) Приоритет (53) УДК 68l.32 (088.8)

Опубликовано 23.02.83, Бюллетень йт 7 ав делам кмбретвккй и етквыткй

Дата опубликования описания 25.02.83 (72) Авторы изобретения

А.И. йемаров .и А.Е. Леусенко

,. Ъ ..! а л

Я Й ур

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

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

ФУРЬЕ то ва f >).

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

Фурье .(БПФ): спектроанализаторах, генераторах широкополосного случайного процесса, эхо- и гидролокаторах, синтезаторах речевых сигналов и т.д.

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

ИЛИ, выход регистра и группы элемен тов ИЛИ соединены соответственно с пятым, шестым, седьмым и первым входами устройства.

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

1О ления устройства. На первый вход устройства поступает информация о номере слоя алгоритма БПФ, в котором в . данный момент времени функционирует устройство.Для Формирования этой информации устройство должно содержать второй счетчик и дешифратор, причем выход второго счетчика соединен с входом.дешифратора, выход которого соединен с первым входом устройстНедостатками этого блока являются сложность его построения и невозможность реализации перекрытия цик3 9990 лов обращения к памяти и циклов выполнения операций алгоритма БПФ в арифметическом устройстве, которое предполагает в течение времени обработки текущей пары операндов t1, запись в память обработанноЖ пары операндов И- 1 и извлечение из памяти пары операндов И+1, которая будет обработана в следующем цикле.

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

Фурье, содержащее первый и второй счетчики, дешифратор, регистр и блок управления, первый, второй и третий выходы которого соединены соответственно с суммирующим, вычитающим и тактовым входами первого реверсивного счетчика, выход переноса и выход ао заема которого соединены соответственно с суммирующим и вычитающим входами второго реверсивного счетчика, выходы которого соединены с входами дешифратора, выход старшего раз25 ряда которого подключен к первому входу блока управления, второй вход которого является тактовым входом устройства, а четвертый выход блока управления соединен с тактовым входом регистра, выходы которого являют30 ся выходами .устройства, а также N узлов блокировки, каждый из которых содержит элемент ИЛИ-НЕ, элемент ИНЕ и два сумматора по модулю два, прйчем выход элемента ИЛИ-НЕ подклю- N чен . к первому входу:первого сумматора по модулю два, выход которого соединен с первым входом второго сумматора по модулю два, второй вход первого сумматора по модулю два сое- 46 динен с выходом элемента И-НЕ, первый вход которого объединен с первым ,входом элемента ИЛИ-НЕ, при этом второй вход элемента ИЛИ-НЕ 1.-го (i=i, N) узла блокировки соединен 4s с х-м (1.--1, N) информационным выходом первого реверсивного счетчика, второй вход элемента И-HE 1-ro (i=1, М) узла блокировки соединен с пятым выходом блока управления, se второй вход второго сумматора по модулю два 5.-ro (i=1,. N) узла блокировки соединен с шестым выходом блока управления, а выход второго сумматора по модулю два i-ro (i=1, Щ узла у блокировки соединен с 1-ым (i=1, N) информационным входом регистра и

1-м (i=1, N) информационным входом

62 4 первого реверсивного счетчика, причем 1-й выход (1.=0, Я-1) дешифратора подключен к первому входу элемента ИЛИ-НЕ i+1-го (i=0, N-1) узла блокировки f2).

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

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

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

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

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

j-го(=1, N-l) мультиплексора Х1 (i=0, j-1) соединены между собой и подключены к j-му (j=l, N- 1) разрядному выходу первого счетчика, информационный вход j-го (j=O, N-1) мультиплексора Х. {i=j) соединен с выхо I дом младшего разряда первого счетчика информационные входы,j-ro {j =Q, Й2) мультиплексора Х (i=j +; М-1) соединены между собой и с j+j -M (j=0, N-2) разрядным выходом первого счетчика, информационный вход j -ro (j =0, Й-1 ) мультипле ксора X- ° (i =N) соединен с инверсным разрядным выхосы, по отрицательному перепаду которых счетчик переключается в-новое состояние. Управляющие сигналы вырабатываются комбинационной схемой, состоящей из элементов 9-11, согласно временной диаграмме, представленной на фиг. 3, где, ТИ - тактовые импульсы; А1-А4 -. разрядные выходы

-1в счетчика 8; 12 — сигнал на втором входе блока 1 ; 13 — сиг" нал на первоч выходе блока 1 управления; 14 - сигнал на втором выходе блока 1 .управления; 15 - сигнал

М на третьем выходе блока l управлеИ ния; 16 - сигнал на четвертом выходе блока 1 управления.

Рассмотрим функционирование устройства при обработке и-й пары -ro о. слоя алгоритма БПФ. Пусть в данном цикле (12 тактов / будет обработайа

ll-я пара i""ão слоя алгоритма БПФ.

Во время обработки П-й пары операн" . дов должна быть адресована и-1-.я

25 пара операндов для записи в запоми. нающее устройство (эта пара была обработана в,предыдущем цикле) и и+1-я пара операндов для считывания их из запоминающего устройства (эта зв пара будет обработана в следующем цикле). Номеру слоя соответствует .= состояние второго счетчика 3. В со=. ответствии с этим состоянием (на третьем выходе блока 7 управления. присутствует уровень логической единицы) мультиплексоры 5 данных передают информацию с разрядных выходов первого счетчика 2 на свои выходы в следующем порядке; 1-й слой

21; 2 2 ...2" "; 2о 2 ° 2й

* и-1 ...2, т.е. в порядке, соответствующем адресам i-го слоя алгоритма

;БОФ. На выходе элемента И-НЕ 7 при™

,сутствует уровень логической едини" цы. Назначение элемент И-НЕ 7 - де45 шифрация сотояния второго счетчика соответствующего специаЛьному слою алгоритма БПФ. Хотя цикл работы устройства состоит из 12 тактов

1цикл работы известного устройства .

8 тактов), это не означает, что устройство теряет быстродействие, так как отсутствует микрооперация параллельного занесения информации в первый счетчик 2, а это дает возS 99906 дом j (j=d,×1:Ò) ое ного счетмиив, выход j-ro (j=, й-1) мультиплексора соединен с информационным входом

О . (J=O tl-1) регистра.

Блок управления содержит счетчик, элемент 4И-4И-3И/ИЛИ, элемент 4И4И/ИЛИ и элемент 2И-НЕ, причем первый вход блока соединен с тактовым входом счетчика, первым и вторым входами элемента 4И-4И/ИЛИ, первым, вторым и третьим входами, элемента .

4И-4И-3И/ИЛИ, второй вход блока соединен с четвертым входом элемента

4И-4И-3И/ИЛИ, третьим вМ фвм элемента. 4И-4И/ИЛИ и первом вхсщом элемента 2И-НЕ, вйход:элвМвита 4М-4И-3И/ИЛ является первым- выходом блока, выход элемента 4И-4И/ИЛИ является вторым . выходом блока, выход элемента 2И-НЕ является четвертым. выходом блока, первый выход счетчика соединен с пятым и шестым входами элемента 4И4И-3И/ИЛИ и четвертым входом элемента 4И-4И/ИЛИ, второй выход счетчика соединен с седьмым и девятым входами элемента 4И-4И-3И/ИЛИ, пятым и шес-. .тым входами элемента 4И-4И/ИЛИ и вторым входом элемента 2И-НЕ, третий

- выход счетчика соединен с десятым и одиннадцатым входами элемента 4И4И-3И/ИЛИ и с седьмым и восьмым входами элемента 4И-4И/ИЛИ, первый выход счетчика является третьим выходом блока.

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

Устройство для формирования адресов алгоритма быстрого преобразова .ния Фурье содержит блок 1 управле,ния, первый счетчик 2, представляющий собой .И-разрядный реверсивный счетчик,: второй счетчик 3, представляющий собой H-разрядный реверсивный счетчик (где H=int log log 2 ("+") ), rpynnny элементов И4, A мультиплексо ров И+1 канал в один канал 5, регистр 6 и И-входовой элемент И-НЕ 7.

Блок управления 1 содержит счетчик 8, элемент 4И-4И-3И/ИЛИ 9, элемент 4И 4И/ИЛИ 10, элемент 2И-НЕ 11.

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

2 . t счетчика 8 поступает тактовые импульможность подавать на суммирующий и вычитающий входы данного счетчика импульсы - более высокой частоты.

7, 9990

В первом, второй и третьем тактах на втором выходе блока 1 управления вырабатываются сигналы, по положи- . тельному перепаду которых из первого счетчика 2 производится вычитание трех единиц, чем адрцц=уется первый операнд n"1-:>A пары операндов, Кроме того, в третьем такте на третьем выходе блока управления вырабатывается сигнал, по отрицательному перепаду которого в регистр 6 заносится адрес первого операнда п-1+4 пары. В четвертом и пятом тактах управляющие сигналы не вырабатывают.ся ° В шестом такте на первом выходе 15 блока 1 управления вырабатывается сигнал, по. положительному перепаду которого в первый счетчик 2 добавля ется единица, чем производится адресация второго операнда п-1-й пары. 26

Кроме того, в шестом такте на тре тьем выходе блока управления вырабатывается сигнал, по отрицательному перепаду которого в регистр 6 зано- сится адрес второго операнда п-1-й 25 пары. В седьмом, восьмом и девятом тактах йа первом .выходе блока. 1 управления вырабатываются сигналы, по положительному перепаду которых в первый счетчик 2 добавляются три единицы, чем адресуется первый операнд n+1-й пары операндов, Кроме того, в девятом такте на третьем выходе блока 1 управления вырабатывается сигнал, по отрицательному neperi y которого в регистр 6 заносится . 35 адрес первого операнда и+1-й пары.

В десятом и одиннадцатом тактах управляющие сигналы не вырабатываются.

В двенадцатом такте на первом выхо46 де блока 1 управления вырабатывается сигнал, по положительному перепаду которого в первый счетчик 2 добавляется единица, чем адресуется второй операнд n+1-й пары. Кроме

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

6 заносится адрес второго операнда и+1-й пары.

Цикл повторяется снова и снова, пока не будут обработаны все пары операндов по всем слоям алгоритма

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

При этом второТ счетчик 3 устанавливается в,состояние Г " 3 .которое де62 8 шифрируется элементом И-НЕ 7, на выходе которого, соединенном с вторым входом блока 1 управления, появляется уровень логического нуля и этим разрешается появление уровня логического нуля на четвертом выходе блока 1 управления. С помощью мультиплексоров 5 на входах регистра 6 появляется информация с разрядных выходов первого счетчика 2 в следующем "порядке, Если на четвертом выходе блока

1 управления пристуствует уровень логической единицы та

2К 1

Если на четвертом выходе блока 1 управления присутствует уровень логического нуля, то .2о ° 21 ° 2 к 21 1 2 2 " й-1

Ф

/ т.е. прямой или инверсный код первого счетчика 2.

Пусть в данном цикле необходимо обработать и-ую пару операндов спе циального слоя Гадреса Pn)"и(2 -и)) .

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

В первом и втором тактах блоком

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

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

n"1-й пары. В четвертом, пятом и шестом тактах на четвертом выходе блока

1 управления появляется уровень логического нуля. Кроме того, в шестом такте вырабатывается сигнал на первом выходе блока 1 управления, по положительному перепаду которого в первый счетчик 2 добавляется единица, чем адресуется первый операнд и-1-й пары (n-1), также в шестом такте вырабатывается сигнал на третьем выходе блока 1 управления, по отрицательному перепаду которого в регистр 6 заносится адрес первого операнда п-1-й пары. В седьмом.9 99906 и восьмом тактах управляющие сигна- 1 лы не вырабатываг)тся. В девятом такте на первом выходе. блока 1 управления вырабатывается сигнал,. по положительному перепаду которого в пер- у вый счетчик 2 добавляется единица, чем адресуется второй операнд rl+1-й, пары (2 -г1;Ц. Кроме того, в девятом такте на третьем выходе блока l управления вырабатываетея сигнал, 1в .по отрицательному перепаду которого в регистр 6 заносится адрес второго операнда й+1-й пары. В десятом, одиннадцатом и двенадцатом тактах на четвертом выходе блока 1 управления И появляется уровень логического нуля.

Кроме того, в двенадцатом такте на первом выходе блока 1 управления вырабатывается сигнал, по положительному перепаду которого в первый счет- 2î чик 2 добавляется единица, чем адресуется первый операнд n+1-ой пары

122+1 ), такие в двенадцатом такте на третьем выходе блока 1 управления вырабатывается сигнал, по отрицатель 25 ному перепаду которого в регистр 6 заносится адрес первого операнда и+1-Й пары.

Цикл повторяется снова и снова, пока не будут обработаны все пары З00 операндов безызбыточного алгоритма

БПФ. После чего устройство заканчивает ра юту - ace адреса безызбыточного алгоритма БПФ реализованы.

После обнуления первого счетчика 2, второго счетчика 3 и счетчика 8 блока 1 управления устройство для формирования адресов процессора быстрого преобразования Фурье снова готово к работе. ,Таким образом, изобретение позволяет повысить быстродействие и упростить управление устройством.

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

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

10 управления соединен с тактовым входом регистра, выходы которого являются выходами устройства, о т л ич а ю щ е е с я тем,что, с целью повышения быстродействия, оно содержит )1 мультиплексоров, группу элементов И и элемент И-НЕ, причем выходы второго счетчика соединены с соответствующими входами элемента

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

j-го Д=1, N-1) мультиплексора Х„ (л.=О, j-l) соединены между собой и подключены к j-му Ц=1, К-1) разрядному выходу .первого счетчика инрормационныр вход j-го (j=0, N-l) мультиплексора = ) соединен с выходом младщего разряда первого счетчика информационные входы .1-го (=0, м"2) мультиплексора $ гьт+1, N-1) соединены между собой и с

j+1-м Ц=О, Н 2) )разрядным выходом первого счетчика информационный вход )-го (3=0, М-1) мультиплексора .

X „ (i=N) соединен с инверсным;раврлдным выходом 1 (j=0, N-1 первого счетчика, выход j -го < j=0 И-1) мультиплексора соединен с информационным входом D (1=0, V-1) регистра.

2 Устройство по и l о т л ич а ю щ е е с я тем, что блок управления содержит счетчик, элемент

4И-4И-3И/ИЛИ, элемент 4И-4И/ИЛИ. и элемент 2И-НЕ, причем первый вход блока соединен с тактовым входом счетчика, первым и BTopblM входами элемента 4И-4И/ИЛИ, первым, вторым и третьим входами элемента 4И-4И"

-3И/ИЛИ, второй вход блока соединен с четвертым входом элемента 4И-4И"

-.3И/ИЛИ, третьим входом элемента

4И-4И/ИЛИ и первым входом элемента

2И-НЕ, выход элемента 4И-4И-3И/ИЛИ является первым выходом блока, выход элемента 4И-4И/ИЛИ является вторым выходом блока, выход элемента .

2И-НЕ является четвертым выходом бло..

: ка, первый выход счетчика соединен с пятым и шестым входами элемента

99906 2, 12

4И-4И/ИЛИ, первый выход счетчика является третьим выходом блока.

11

4И-4И-3И/ИЛИ и четвертым входом элемента 4И-4И/ИЛИ, второй выход счетчика соединен с седьмым, восьмым и девятым входами элемента 4И-4И"3И/ИЛИ, пятым и шестым входами элемента 4И-4И/ИЛИ и вторым входом элемента 2И-НЕ, третий выход счетчика соединен с десятым и одиннадцатым входами элемента 4И-4И-3И/ИЛИ и с седьмым и восьмым входами элемента

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

1, Авторское свидетельство СССР 548863, кл. 806F 15/332, 1976.

2. Авторское свидетельство СССР по заявке И 2979625/24, кл. 6 OF t " 15/332, l981 прототий).

999062

Puz 8

Дурус 1 2 д У 5 b 7 LF Р 7011 1Г 1 g p y р у р 9 уды

1б

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

Редактор Л. Филиппова Техред И.Гергель Корректор M.làðîøè

Заказ 1158/73 Тираж 704 Подписное

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

11303 Москва Я-35 Раушская наб. д. 4/5

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