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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 09) Ш) 61)4 0 06 32 г.5 ОПИСАНИЕ ИЗОБРЕТЕНИЯ АВТОРСКОМУ СВИДЕТЕЛЬСТВУ щф" 4 гфй-жОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬПИЙ(56) Авторское свидетельство СССР У 1062714, кл. а 06 У 15/332, 1983Авторское свидетельство СССРУ 480079, кл. С 06 Р 15/332, 1975,(54)БЛОК АДРЕСАЦИИ ДЛЯ ПРОЦЕССОРАБЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ(57)Изобретение относится к вычис- .лительной технике и может быть использовано в процессорах быстрогопреобразования Фурье, решающих задачи спектрального анализа. Цельизобретения - повышение быстродействия. Устройство содержит арифметический блок, состоящий из сумматора и регистра, регистр адреса, распределитель импульсов, регистр сдвига, узел мультиплексоров, узелуправления сдвигом, включающий всебя триггер, элемент 2 И-ИЛИ, элемент задержки, элемент И-НЕ, узелуправления, который состоит из,счетчика, 3-х элеметов И, регистра,начальных адресов, элемента 2 И-ИЛИ,триггера и нуль-органа, 5 ил. Е223247 3 11Изобретение относится к вычислительной технике и может быть использовано для формирования последовательности адресов рабочей памятив ходе выполнения быстрого преобра зования Фурье (БПФ).Цель изобретения " повышение быстродействия за счет снижения затрат времени на двоично-инверсноепреобразование последовательностиадресов рперандов, обеспечения воз-.можности выполнения двоично-инверсного преобразования последовательности адресов как на завершающем,так и на начальных этапах выполнения БПФ.На фиг, 1 представлена схемаблока адресации для процессора быстрого преобразования Фурье; нафиг. 2 - временная диаграмма егоработы; на фиг. 3 - схема арифметического блока; на фиг. 4 - схема.узла управлейия сдвигов; на фиг. 5 схема узла управления.Блок адресации для процессорабыстрого преобразования Фурье содержит арифметический блок 1, распределитель импульсов 2, узел 3 управления сдвигом, регистр 4 адреса,регистр 5 сдвига, узел 6 управления,,первый и второй адресные выходы1 О и 11,Арифметический блок (фиг. Э) содержит параллельный сумматор 12,буферный регистр 13, вход 14 текущего значения адреса, вход 15 стро.ба буферного регистра, выход 16 арифметического узла.Узел 3 управления сдвигом (фиг.4)содержит элемент 17 задержки, элемент И-НЕ 18, элемент 2 И-ИПИ 19,триггер 20, вход 21 импульсов занесения, вход 22 импульсов сдвигавход 23 управляющего сигнала, вход24 потенциала комплексного преобразования Фурье, выход 25 строба регистра адреса, выход 26 управлениярегистром адреса. 50Узел 6 управления (фиг. 5) содержит элементы И 27-29, регистр 30 начальных условий, счетчик 31 этапов,,ВБ -тиггер 32 (начального этапа),нуль-орган 33 (счетчика этапов), элемент 2 И-ИПИ 34, вход 35 синхроимпульсов, информационные входы 36счетчика (этапов), вход 37 потенци 5 15 25 30 35 40 45 ала логической единицы, вход 38 инверсного выхода нуль-органа делителя частоты, выход 39 управляющего сигнала, выход 40 потенциала комплексного преобразования Фурье.Для объяснения принципа работы устройства введем дополнительные величины:ьА ." величина приращения адреюоксса, при максимальном количестве элементов, используемых при быстром преобразовании Фурье;ьА - величина приращения при немаксимальном количестве элементов, используемых при быстром преобразовании Фурье;Б , в .максимальное количество элементов, используемых при быстром преобразовании"Фурье.Устройство работает следующим образом.При выполнении быстрого преобразования Фурье максимального количества элементов памяти, которое можно адресовать с помощью младшей группы разрядов регистра адресов в зависимости от используемого алгоритма БПВ целесообразно рассмотреть следу 1 ощие режимы: двоично-инверсное преобразование адресов для исходной последовательности элементов для БПФ(режим 1 ; двоично-инверсное преобразование адресов результирующей последовательности элементов БПФ (ре" жим 2).В 1-м режиме сигнал на вход узла 7 мультиплексоров с выхода узла б управления формируется с помощью триггера 32, с выхода которо. го он поступает на вход элемента 2 И-ИЛИ 34. На другие входы элемента 2 И-ИЛИ 34 с выхода регистра 30 поступают соответственно потенциал вида алгоритма, который обуславливает двоично-инверсное преобразование адресов исходной последовательности элементов, а также потенциал чтения, благодаря которому двоично-инверсное преобразованиепроисходит при считывании элементов из рабочей памяти. В свою очередь, триггер 32 по Я - входу устанавливается выходным сигналом элемента И 27, с помощью которого выделяется первый иэ синхроимпульсов,поступающих на вход 35 счетчика 31этапов. С этой целью на один извходов элемента И 27 заводится вы5 1 О 15 20 ЗО Начальные значения последовательности адресов при двоично-инверсном преобразовании порядка следования максимальной последовательности эле ментов содержат равными нулю значения регистра 5 сдвига. При этом обеспечивается корректность двоично-инверход нуль-органа 33, а на второй -последовательность синхроимпульсов.На В - вход триггера 32 поступаетвторой и последующий из синхроим- .пульсов, которые выделяются с помощью элемента И 29. С этой цельюна один вход элемента И 29 заводится инверсный выход нуль-органа 33,а на другой - также последовательность синхроимпульсов.Таким образом, триггер 32 формирует управляющий сигнал длительно- .стью от переднего фронта первогосинхроимпульса до переднего фронтавторого синхроимпульса. Данный сигнал, модулированный потенциаломчтения, при наличии разрешающегопотенциала вида алгоритма поступаетна выход 39, с которого поступаетна вход узла мультиплексоров, обеспечивая перекрестную коммутацию выходов разрядов регистра сдвига свторыми входами разрядов узла 7мультиплексоров, сигналы которых 25в этом же режиме поступают на выход11. Теи: самым выполняется двоичноинверсное преобразование адресовпоследовательности исходных элементов для быстрого преобразованияФурье на этапе их считывания израбочей памяти.Во 2-м режиме сигнал на вход узла7 мультиплексоров, поступающий свыхода элемента 2 И-ИЛИ 34 формиру 1 35ется с помощью элемента И 28, наодин вход которого поступает сигналс нуль-органа 33, на второй - свхода 38 сигнал с выхода распределителя. Выход элемента И 28 подается 4 Она вход элемента 2 И-ИЛИ 34, на дру-,гие входы которого поступает с выходарегистра 30 потенциал вида алгоритма, который обуславливает двоично-инверсное преобразование адресов резуль тирующей последовательности элементов, а также потенциал записи благодаря которому двоично-инверсное преобразование происходит при записирезультатов быстрого преобразованияФурье вреальную. память,сного преобразования благодаря отсутствию искажающего влияния переносов при суммировании в регистре 5 сдвига постоянной (не нулевой) и переменной составляющих адресного кода. Для простоты будем полагать, что величина приращения адреса, поступающая на вход 8 арифметического блока, равна 1, т,е. ЬА = 1, при выполнемахснии быстрого преобразования Фурье максимального количества элементов.Если количество элементов, исполь- зуемых при быстром преобразовании Фурье, не является максимальным, то необходимо варьировать величину приращения адреса согласно соотношению11 максьА - 11 А максПри этом в целях экономии объемарабочей памяти целесообразно младшие биты начального значения адресазаносить в те разряды регистра 5сдвига, которые не используются принаращивании адреса с помощью приращения А. Если величина А равна 2;4; 8; 16 и т.д., то соответственно1; 2; 3; 4 и т.д. самых младших разрядов регистра 5 сдвига не используются при наращивании адреса,. Размещая в этих разрядах младшие битыначального значения адреса последовательности элементов, подвергающейся двоично-инверсному преобразованию, необходимо их разместить таким образом, чтобы самый младший битначального значения адреса бып размещен в самом старшем из неиспользованных разрядов регистра 5 сдвига,примыкающий к самому младшему битуначального значения адреса - в примыкающем к самому старшему из неиспользуемых разрядов регистра 5 сдвига и так до самого младшего разряда регистра 5 сдвига,При таком размещении младшихбитов адреса после двоично-инверсного преобразования младшие битынепосредственно примыкают к старшейгруппе регистра адреса 4, располагаясь в соответственном порядке:более младший бит занимает болееправую позицию. При двоично-инверсном преобразовании последовательности комплексных элементов возможны различные варианты взаимного размещения действительных и мнимых компонентов.20 45 Если действительные компоненты образуют компактную последовательность, в которой они расположены в соответствии с необходимым порядком размещения комплексных элементов, аналогично расположены .и мнимые компоненты, и при этом варианте устройство работает, как описано вьппе, раздельно формируя адреса 10 сначала для совокупности действи тельных, а затем мнимых компонентов.Если действйтельные и мнимые компоненты каждого элемента располо жены рядом таким образом, что между двумя соседними действительными компонентами размещен мнимый и, соответственно, между двумя мнимыми компонентами размещен действительный, то при двоично-инверсном преобразовании последовательности элементов взаимное расположение действительных и мнимых компонентов должно сохраниться. С этой целью25 как для,действительных, так и для мнимых компонентов в процессе преобразования необходимо сохранить шаг расположения соседних элементов. 30При двоично-инверсном преобразовании порядка следования действительных компонентов задается приращение адреса, равное двум, на вход 8 арифметического блока 1. Регистр 5 сдвига работает в режимах записи и сдвига вправо.В режиме записи на вход 82 регистра 5 адвига подается с выхода узла 3 управления сдвигом уровень щ единицы. С этой целью на Я - вход триггера 20 узла 3 входа 22 через элемент 17 задержки поступает последовательность синхроимпульсов с выхода распределителя 2. Благодаря наличию элемента 17 задержки обеспечивается установка триггера 20 в единичное состояние через интервал времени по окончании импульса на входе 22, Триггер 20 остается в единичном состоянии во время им-. пульса, приходящего на вход 21 узла 3 с выхода распределителя 2, Этот импульс попадает на вход элемента 2 И-ИЛИ 19, на другой вход которого 55 заведен единичный выход триггера 20.Таким образом, синхроимпульсы с входа 21 в режиме записи оказываются на выходе 25 узла 3 и, попадая на С-вход регистра 5 сдвига, обеспечивают занесение в него модифицированного значения адреса с выхода арифметического блока .1,Одновременно синхроимпульсы с входа 21 поступают на С-вход триггера 20, на Р -вход которого с выхода элемента И-НЕ 18 заведен потенциал логического нуля. В результате триггер 20 по заднему фронту синхроимпульса с входа 21 переходит в нулевое состояние. На вход элемента И-НЕ 18 при этом поступают следующие сигналы. С входа 23 .единичный потенциал с выхода узла б управления, который на выход поступаетс регистра 30 и свидетельствует о попарном размещении действительных и мнимых компонентов комплексных элементов. С входа 24 поступает единичный потенциал с выхода узла б, который задает режим двоично-инверсного преобразования. На этом режим записи заканчивается.В режиме сдвигов вправо на вход 82 - регистра 5 сдвига поступает нулевой потенциал, который устанавливается на выходе 2 б по окончании импульса на входе 21. При этом элемент 2 И-ИЛИ 19 пропускает импульс с входа 22 на выход 25 благодаря потенциалу логической единицы, приходящему на вход элемента 2 И-ИЛИ 19 с инверсного выхода триггера 20.Поступая на С - вход регистра 5 сдвига импульс с выхода 25 вызывает сдвиг вправо информации, которая была занесена в регистр по предыдущему импульсу.Двоично-инверсное преобразование последовательности адресов после преобразования осуществляется с помощью узла 7 мультиплексоров, работа которого в этом режиме специфична вследствие необходимости обеспечить адресацию мнимых компонентов. Их адреса должны быть на единицу больше адресов соответствующих им действительнык компонентов. С этой целью частота следования синхроимпульсов на входе 9 уменьшается вдвое по сравнению с предыдущими режимами.Синхроимпульсы задержанной последовательности с выхода делителя частоты делят увеличенный период следования сикхроимпульсов на входе 9 пополам по своему заднему фронту.Формула изобретения 25 Блок адресации для процессоРа быстрого преобразования Фурье, содержащий сумматор, выход которого подключен к информационному входу регистра, выход которого подключен к информационному входу регистра адреса, выход которого является пер- О вым адресным выходом блока и подключен к первому входу сумматора, второй вход которого является входом задания приращения адреса блока, а тактовые входы регистра и регистра 15 адреса подключены соответственно к первому и второму выходам распределителя импульсов, вход которого является тактовым входом блока, о тл и ч а ю щ и й с я тем, что, с 20 целью повышения быстродействия, в него введены узел мультиплексоров, узел управления сдвигом, узел управления и регистр сдвига, информационный выход которого объединен с информационным выходом регистра адреса, а выходы разрядов регистра адреса подключены к соответствующим информационным входам узла мультиплексоров, выход которого яв ляется вторым адресным выходом блока, выход регистра подключен к информационному входу регистра сдвига, первый управляющий вход узла мультиплексоров подключен к третьему входу распределителя импульсов, тактовый вход блока соединен с вторым управляющим входом узла мультиплексоров, при этом узел управления сдвигом содержит элемент 2 И ИЛИ, элемент задержки, триггер и элемент И-НЕ, выход которого подключен к Э -входу триггера, прямой и инверсный выходы которого подключены соответственно к первому 45 и второму входам элемента 2 И-ИЛИ, а установочный вход триггера подключен к выходу элемента задержки, причем узел управления включает в себя счетчик, нуль-орган, три элемента 50 И, ВЯ-триггер, элемент 2 И-ИЛИ, регистр начальных условий, выходы первого и второго, третьего и четвертого разрядов которого подключены соответственно к первому, второму, третьему и четвертому входам элемента 2 И-ИПИ, пятый и шестой входы которого подключены к выходам соответственно первого элемента И и триггера, В- вход и Я - вход которого подключены к выходам соответственно второго и третьего элементов И, информационный выход счетчика подключен к входу нуль-органа, инверсный выход которого подключен к первому входу второго элемента И, прямой выход нуль-органа подключен к первым входам первого и третьего элементов И, установочному входу счетчика, второй вход распределителя импульсов подключен к третьему входу элемента 2 И-ИЛИ и входу синхронизации триггера узла управления сдвигом, выход элемента 2 И-ИЛИ которого подключен к тактовому входу регистра сдвига, вход управления сдвигом которого подключен к прямому входу триггера узла управления сдвигом, первый и второй входы И-НЕ которого объединены соответственно с третьим и четвертым управляющими входами узла мультиплексоров и подключены соответственно к выходу элемента 2 И-ИЛИ и выходу пятого разряда регистра начальных условий узла управления, второй вход первого элемента И которого подключен к четвертому выходу распределителя импульсов, пятый выход которого подключен к входу синхронизации счетчика и вторым входам второго и третьего элементов И узла управления, информационный вход счетчика которого является входом задания числа этапов блока, а третий выход распределителя импульсов подключен к входам элемента задержки и четвертому входу элемента 2 И - ИЛИ узла управления сдвигом.223247 Фиг Х Составитель А. БарановРедактор В. Петраш ТехредЛ.Олейник КорректорИ, Демчик дписноеССР 4/5 Патент", г. Ужгород, ул ктна аз 1715/52 ВНИИПИ Государст по делам нзобр 113035, Москва, Тираж 671 П енного комитета тений и открытий -35, Раушская н