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

 

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

223247 3

1

f I

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

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

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

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

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

Узел 3 управления сдвигом (фиг.4) содержит элемент 17 задержки, элемент И-НЕ 18, элемент 2И-ИЛИ 19, триггер 20, вход 21 импульсов занесения, вход 22 импульсов сдвига,, вход 23 управляющего сигнала, вход

24 потенциала комплексного преобразования Фурье, выход 25 строба регистра адреса, выход 26 управления регистром адреса.

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

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

Для объяснения принципа работы устройства введем дополнительные величины: дА .» величина приращения адремакс са, при максимальном количестве элементов, используемых при быстром преобразовании Фурье;

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

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

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

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

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

2И-ИЛИ 34. На другие входы элемента 2И-ИЛИ 34 с выхода регистра 30 поступают соответственно потенциал вида алгоритма, который обуславливает двоично-инверсное преобразование адресов исходной последовательности MIeMpHTos> а также потенциал чтения, благодаря которому двоично-инверсное преобразование происходит при считывании элементов из рабочей памяти. В свою очередь, триггер 32 по Я вЂ” входу устанавливается выходным сигналом элемента И 27, с помощью которого выделяется первый иэ синхроимпульсов, поступающих на вход 35 счетчика 31 этапов. С этой целью на один из входов элемента И 27 заводится вы1223247

11макс A макс

25

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

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

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

ll, Теи: самым выполняется двоичноинверсное преобразование адресов последовательности исходных элементов для быстрого преобразования

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

Во 2-м режиме сигнал на вход узла

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

Фурье в реальную. память.

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

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

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

При этом в целях экономии объема рабочей памяти целесообразно младшие биты начального значения адреса заносить в те разряды регистра 5 сдвига, которые не используются при наращивании адреса с помощью приращения А. Если величина А равна 2;

4; 8; 16 и т.д., то соответственно

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

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

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

1223247

45

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

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

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

8 арифметического блока l. Регистр

5 сдвига работает в режимах записи и сдвига вправо.

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

3 с выхода распределителя 2. Этот импульс попадает на вход элемента

2И-ИЛИ 19, на другой вход которого у заведен единичный выход триггера 20.

Таким образом, синхроимпульсы с входа 21 в режиме записи оказываются на выходе 25 узла 3 и, попадая на

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

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

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

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

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

На этом режим записи заканчивается.

В режиме сдвигов вправо на вход

S2 — регистра 5 сдвига поступает нулевой потенциал, который устанавливается на выходе 26 по окончании импульса на входе 21. При этом элемент

2И-ИЛИ 19 пропускает импульс с входа

22 на выход 25 благодаря потенциалу логической единицы, приходящему на вход элемента 2И-ИЛИ 19 с инверсного выхода триггера 20.

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

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

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

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

1223247

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

Блок адресации для процессора быстрого преобразования Фурье, содержащий сумматор, выход которого подключен к информационному входу регистра, выход которого подключен к информационному входу регистра адреса, выход которого является пер- !О вым адресным выходом блока и подключен к первому входу сумматора, второй вход которого является входом задания приращения адреса блока, а тактовые входы регистра и регистра 15 адреса подключены соответственно к первому и второму выходам распределителя импульсов, вход которого является тактовым входом блока, о тл и ч а ю шийся тем, что, с 20 целью повышения быстродействия, в него введены узел мультиплексоров, узел управления сдвигом, узел управления и регистр сдвига, информационный выход которого объединен с информационным выходом регистра адреса, а выходы разрядов регистра адреса подключены к соответствующим информационным входам узла мультиплексоров, выход которого яв- 30 ляется вторым адресным выходом блока, выход регистра подключен к информационному входу регистра сдвига, первый управляющий вход узла мультиплексоров подключен к третьему входу распределителя импульсов, тактовый вход блока соединен с вторым управляющим входом узла мультиплексоров, при этом узел управления сдвигом содержит элемент 2И- 40

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

И, RS-триггер, элемент 2И-ИЛИ, регистр начальных условий, выходы первого и второго, третьего и четвертого разрядов которого подключены соответственно к первому, второму, третьему и четвертому входам элемента 2И-ИПИ, пятый и шестой входы которого подключены к выходам соответственно первого элемента И и триггера, R- вход и S — вход которого подключены к выходам соответственно второго и третьего элементов И, информационный выход счетчика подключен к входу нуль-органа, инверсный выход которого подключен к первому входу второго элемента И, прямой выход нуль-органа подключен к первым входам первого и третьего элементов И, установочному входу счетчика, второй вход распределителя импульсов подключен к третьему входу элемента 2И-ИЛИ и входу синхронизации триггера узла управления сдвигом, выход элемента 2И-KIH которого подключен к тактовому входу регистра сдвига, вход управления сдвигом которого подключен к прямому входу триггера узла управления сдвигом, первый и второй входы И-НЕ которого объединены соответственно с третьим и четвертым управляющими входами узла мультиплексоров и подключены соответственно к выходу элемента 2И-ИЛИ и выходу пятого разряда регистра начальных условий узла управления, второй вход первого элемента И которого подключен к четвертому выходу распределителя импульсов, пятый выход которого подключен к входу синхронизации счетчика и вторым входам второго и третьего элементов И узла управления, информационный вход счетчика которого является входом задания числа этапов блока, а третий выход распределителя импульсов подключен к входам элемента задержки и четвертому входу элемента 2И вЂ” ИЛИ узла управления сдвигом.

) 223247

1223247

Фиг.г

1223247! 223247

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

Редактор В. Петраш ТехредЛ.Олейник КорректорИ. Демчик

Заказ 1715/52 Тираж 671 Подписное

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

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

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