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

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

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

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

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

Арифметический блок (фиг. 3) содержит параллельный сумматор 12, буферный регистр 13, вход 14 текущего значения адреса, вход 15 строп ба буферного регистра, выход 16 ариметического узла.

Узел 3 управления сдвигом (фиг,4 содержит элемент 17 задержки, элемент И-НЕ 18, элемент 2И-Ш1И 19, триггер 20, вход 21 импульсов занесения, 22 импульсов сдвига, вход 23 управлянлцего сигнала, вход 24 потенциала комплексного преобразования Фурье, выход 25 строба регистра адреса, выход 26 управления регистром адреса.

Узел 6 управления (фиг. 5) содержит элементы И 27-29, регистр 30 начальных условий, счетчик 31 этапов :RS -тиггер 32 (начального этапа), нуль-орган 33 (счетчика этапов), элмент 2И-ИЛИ 34, вход 35 синхроимпульсов, информационные входы 36 счетчика (этапов), 37 потенци23247i

ала логической единицы, вход 38 инверсного выхода нуль-органа делителя частоты, выход 3 управляющего сигнала, выход 40 потенциала комплекс5 иого преобразования Фурье.

Для объяснения принципа работы устройства введем дополнительные величины:

величина приращения адре10 са, при максимальном количестве элементов, используемых при быстром преобразовании Фурье;

ЛА - величина приращения при немаксимальном количестве элементов,

15 используемых при быстром преобразова- НИИ Фурье;

макс максимальное количество элементов, используемых при быстром преобразовании Фурье.

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

При выполнении быстрого преобразования Фурье максимального количества элементов памяти, которое можно

25 адресовать с помощью младгаей группы разрядов регистра адресов в зависимости от используемого алгоритма БПВ целесообразно рассмотреть следу(нцие режимы: двоично-инверсное преобра30 зование адресов дпя исходной последовательности элементов дпя БПФ (режим 1 ; двоично-инверсное преобразование адресов результирующей пос- ледовательности элементов БПФ (ре35 жим 2).

В 1-м режиме сигнал на вход узла 7 мультиплексоров с выхода уэла 6 управления формируется с помощью триггера 32, с выхода которо40

го он поступает на вход элемента

2И-ИЛИ 34. На другие входы элемента 2И-ИЛИ 34 с выхода регистра 30 поступают соответственно потенциал вида алгоритма, который.обус- лавливает двоично-инверсное преобразование адресов исходной последовательности элементов, а также iпотенциал чтения, благодаря которому двоично-инверсное преобразование

происходит при считывании элементов из рабочей памяти. В свою очередь, триггер 32 по S - входу устанавливается выходным сигналом элемента И 27, с помощью которого вы- деляется первый из синхроимпульсов, поступающих на вход 35 счетчика 31 этапов. С этой целью на один из входов элемента И 27 заводится вы3

ход нуль-органа 33, а на -второй - последовательность синхроимпульсов.

На R - вход триггера 32 поступает второй и последующий из синхроим- . пульсов, которые вьщеляются с помощью элемента И 29. С этой целью на один вход элемента И 29 заводится инверсный выход нуль-органа 33, а на другой - также последовательность синхроимпульсов.

Таким образом, триггер 32 формирует управляющий сигнал длительно- - стью от переднего фронта первого синхроимпульса до переднего фронта второго синхроимпульса. Данный сигнал , модулированный потенциалом чтения, при наличии разрешающего потенциала вида алгоритма поступает на выход 39, с которого постзшает на вход узла мультиплексоров, обеспечивая перекрестную коммутацию выходов разрядов регистра сдвига с вторыми входами разрядов узла 7 мультиплексоров, сигналы которых в этом же режиме поступают на выход 11. Тем: самым выполняется двоично- инверсное преобразование адресов последовательности исходных элементов для быстрого преобразования Фурье на этапе их считывания из рабочей памяти.

Во 2-м режиме сигнал на вход узла 7 мультиплексоров, поступающий с- выхода элемента 2И-ИЛИ 34, формируется с помощью элемента И 28, на один вход которого поступает сигнал с нуль-органа 33, на второй - с входа 38 сигнал с выхода распределителя. Выход элемента И 28 подается на вход элемента 2И-ИЛИ 34, на друг- гие входы которого поступает с выхода регистра 30 потенциал вида алгоритма, который обуславливает двоично-инверсное преобразование адресов резултирующей последовательности элементов, а также потенциал записи, благодаря которому двоично-инверсное преобразование происходит при записи результатов быстрого преобразования Фурье в реальную, память.

Начальные значения последовательности адресов при двоично-инверсном преобразовании порядка следования максимальной последовательности элементов содержат равными нулю значения регистра 5 сдвига. При этом обеспечивается корректность двоично-инве232474

сного преобразования благодаря отсутствию искажающего влияния переносов при суммировании в регистре 5 сдвига постоянной (не нулевой) и перемен- 5 ной составляющих адресного кода. Для простоты будем полагать, что величина приращения адреса, поступающая на вход 8 арифметического блока, равна 1, т.е. дА 1, при выполнео НИИ быстрого преобразования Фурье максимального количества элементов.

Если количество элементов, используемых при быстром преобразовании Фурье, не является максимальным, то 15 необходимо варьировать величину приращения адреса согласно соотношению

Алакс

(1)

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

заносить в те разряды регистра 5 сдвига, которые не используются при

наращивании адреса с помощью приращения А. Если величина А равна 2; 4; 8; 16 и т.д., то соответственно 1; 2; 3; 4 и т.д. самых младших разрядов регистра 5 сдвига не используются при наращивании адреса.. Размещая в этих разрядах младшие биты начального значения адреса последовательности элементов, подвергающейся двоично-инверсному преобразованию, необходимо их разместить таким образом, чтобы самый младший бит начального значения адреса был размещен в самом старшем из неиспользованных разрядов регистра 5 сдвига,

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

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

группе регистра адреса 4, располагаясь в соответственном порядке: более младший (Зит занимает более правую позицию.

При двоично-инверсном преобразо- вании последовательности комплексных элементов возможны различные варианты взаимного размещения действительных и мнимых компонентов.

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

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

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

В режиме записи на вход S2 регистра 5 адвига подается с выхода узла 3 управления сдвигом уровень единицы. С этой целью на S - вход триггера 20 узла 3 входа 22 через элемент 17 задержки поступает последовательность синхроимпульсов с выхода распределителя 2. Благодаря наличию элемента 17 задержки обеспечивается установка триггера 20 в единичное состояние через интервал времени по окончании импульса на входе 22, Триггер 20 остается в единичном состоянии во время импульса, приходящего на вход 21 узла 3 с выхода распределителя 2, Этот импульс попадает на вход элемента 2И-ИЛИ 19, на другой вход которого заведен единичный выход триггера 20

Таким образом, синхроимпульсы с входа 21 в режиме записи оказываются на выходе 25 узла 3 и, попадая на С-вход регистра 5 сдвига, обеспечивают занесение в него модифицирован- ного значения адреса с выхода арифметического блока .1 .

Одновременно синхроимпульсы с входа 21 поступают на С-вход триггера . 20, на 1 -вход которого с выхода

элемента И-НЕ 18 заведен потенциал логического нуля. В результате триггер 20 по заднему фронту синхроимпульса с входа 21 переходит в нулевое состояние. На вход элемента И-НЕ

18 при этом поступают следующие сигналы. С входа 23 единичный потенциал с выхода узла 6 управления, который на выход поступает с регистра 30 и свидетельствует о попарном размещеНИИ действительных и мнимых компонентов комплексных элементов. С входа 24 поступает единичный потенциал с выхода узла 6, который задает режим двоично-инверсного преобразования.

На этом режим записи заканчивается. В режиме сдвигов вправо на вход S2 - регистра 5 сдвига поступает нулевой потенциал, который устанавливается на выходе 26 по окончании импульса на входе 21. При этом элемент 2И-Ш1И 19 пропускает импульс с входа 22 на выход 23 благодаря потенциалу логической единицы, приходящему на вход элемента 2И-Ш1И 19 с инверсного

выхода триггера 20.

Поступая на С - вход регистра 5 сдвига импульс с выхода 25 выэьшает сдвиг вправо информации, которая была занесена в регистр по предыдущему импульсу.

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

действительных компонентов. С этой целью частота следования синхроимпульсов на входе 9 уменьшается вдвое по сравнению с предыдущими режимами. Синхроимпульсы задержанной последрвательности с выхода делителя частоты делят увеличенный период следования синхроимпульсов на входе 9 пополам по своему заднему фронту.

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

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

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

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

элементов И, установочному входу

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

выход элемента 2И-ИПИ которого подключен к тактовому входу регистра сдвига, вход управления сдвигом которого подключен к прямому входу триггера узла управления сдвигом,

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

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

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

ЩШ

11 If II l I

i

4mi4444+

in

III11 III itfttt-tl-iH

l || Hi i OO fi I

П I г n .I

I UHJU

tHf

um

шъ

lUUUUlJLJlJUlJLJLIL

nJUUUULJULJUlJlJL

4mi4444+

III11 III itfttt-tl-iH

Hi i fi I

I

tHf

m

um

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

8 o

/-/

14 o-

1

г

3

ч

5

6

7

8

т

f6 -o

fpu,Z-3

«с «м

СМ

м см

45 СМ

«$

I

«мсм

Составитель A. Баранов Редактор В. Петраш Техред Л. Олейник Корректор, М.

Заказ 1715/52 Тираж 671 Подписное ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская иаб., д. 4/5

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

fPuB.J