Устройство для формирования адресов процессора быстрого преобразования Фурье Советский патент 1983 года по МПК G06F9/34 

(54) УСТРОЙСТВО для ФОРМИРОВАНИЯ АДРЕСОВ ПРОЦЕССОРА,БЫСТРОГО ПРЕОБРАЗОВАНИЯ Изобретение относится к области вычислительной техники и может быть использовано при построении устройств, использующих в своей работе алгоритм быстрого .преобразования Фурье ГБПФ): спектроанализаторах, ге нераторах широкополосного случайного процесса, эхо- и гидролокаторах, синтезаторах речевых сигналов и т.д Известно устройство формирования адресов, реализующее алгоритм БПФ, содержащее узел реконфигурации счетчика, выход которого соединен с уп- равляющим входом счетчика, блок выдачи адресов, первый информационный вход которого соединен с выходом счетчика, а выход - с выходом устрой ства, причем вход узла реконфигурации счетчика, первый и второй счётные входы счетчика и первый управляю щий вход блока выдачи адресов соединены соответственно с первым, вторым, третьим и четвертым выходами ФУРЬЕ блока, регистр и группу элементов ИЛИ, выход регистра-и группы элементов ИЛИ соединены соответственно с пятым, шестым, седьмым и первым входами устройства. На второй, третий, четвертый, пятый , шестой, седьмой входы устройства подаются управляющие сигналы, которые вырабатываются блоком управления устройства. На первый вход устройства поступает информация о номере слоя алгоритма БПФ, в котором в данный момент времени функционирует устройство. Для формирования этой информации устройство должно содержать второй счетчик и дешифратор, причем выход второго счетчика соединен с входом дешифратора, выход которого соединен с первым входом устройстsail. Недостатками этого блока являются сложность его построения и невозможность реализации перекрытия цик3лов обращения к памяти и циклов выполнения операций алгоритма БПФ в арифметическом устройстве, которое предполагает.в течение времени обра ботки текущей пары операндов м, запись в память обработанной пары опе рандов VI-1 и извлечение из памяти .пары операндов И+1, которая будет обработана в следующем цикле. Наиболее близким к изобретению по технической сущности является устройство для формирования адресов процессора быстрого преобразования Фурье, содержащее первый и второй счетчики, дешифратор, регистр и блок управления, первый, второй и третий выходы которого соединены соответственно с суммирующим, вычитающим и тактовым входами первого реверсивного счетчика, выход переноса и выход заема. которого соединены соответственно с суммирующим и вычитающим входами второго реверсивного счетчика , выходы которого соединены с входами дешифратора, выход старшего раз ряда которого подключен к первому входу блока управления, второй вход которого является тактовым входом устройства, а четвертый выход блока управления соединен с тактовым входом регистра, выходы которого являют ся выходами .устройства, а также N узлов блокировки, каждый из которых содержит элемент ИЛИ-НЕ, элемент ИНЕ и два сумматора по модулю два, выход элемента ИЛИ-НЕ подключен к первому входу первого сумматора по модулю два, выход которого соединен с первым входом второго сумматора по модулю два, второй вход первого сумматора по модулю два сое динен с выходом элемента И-НЕ, первый вход которого объединен с первым входом элемента ИЛИ-НЕ, при этом второй вход элемента ИЛИ-НЕ i-ro (, N) узла блокировки соединен с i-M (, N) информационным выходом первого реверсивного счетчика, второй вход элемента И-НЕ i-ro (, N) узла,блокировки соединен с пятым выходом блока управления, второй вход второгд| сумматора по мо дулю два i-ro ,.N) узла блокиро ки соединен с шестым выходом блока управления, а выход второго суммато ра по модулю два i-ro ( , N) У,зла блокировки соединен с i-ым (, N) )рмационнымвходом регистра и 1-м (, N) информационным входом 2 первого реверсивного счетчика, причем i-й выход , N-1) дешифратора подключен к первому входу элемента ИЛИ-НЕ i+1-го (, N-i) узла блокировки С23. Недостатками известного устройства являются невысокое быстродействие, сложность блока управления, а также большое количество управляющих сигналов, вырабатывающихся блоком управления, что нежелательно при применении устройства управления микропрограммного типа. / Цель изобретения - повышение быстродействия устройства. Эта цель достигается тем, что устройство для формирования адресов процессора, быстрого преобразования Фурье, содержащее первый и второй счетчики, регистр и блок управления, первый и второй выходы которого соединены соответственно с входом суммирования и входом вычитания первого счётчика, выход переноса и выход заема которого соединены соответственно с входом суммирования.и входом вычитания второго счетчика, третий . выход блока управления соединен с тактовым входом регистра, выходы которого являются выходами устройства, содержит N мультиплексоров, группу элементов И и элемент И-НЕ, причем .выходы второго сметчика соединены с соответствующими входами элемента И-НЕ и первыми входами соответствующих элементов И группы, вторые входы которых объединены и соединены с четвертым выходом блока управления, первый вход которого является тактовым входом устройства, второй вход блока управления соединен с выходом элемента И-НЕ, выходы элементов И группы соединены с управляющими входами соответствующих мультиплексоров, причем информационные входы j-ro ( , N-1) мультиплексора Х (, J-1) соединены между собой и подключены к j-му {j 1 , N-1) разряд,ному выходу первого счетчика, информационный вход j-ro (, N-1) мультиплексора X: ) соединен с выходом младшего разряда первого счетчника информационные входы .j-ro (j-j, N-2) мультиплексора Х (, N-1) соединены между собой и с j+1-м (, N-2) разрядным выходом первого счетчика,информационный вход j-ro (, N-1) мультиплексора X () соединен с инверсным разрядным выходом j , N-1) первого счетчика, п-ц nepi 0(ГГьм выход j-ro , N-1) мультиплексора соединен с информационным входом Di (, N-1) регистра. Блок управления содержит счетчик элемент 4И- И-ЗИ/ИЛИ, элемент И iM/HniH и элемент 2И-НЕ, причем первый вход блока соединен с тактовым входом счетчика, первым и вторым входами элемента 4и-4И/ИЛИ, первым, вторым и третьим входами, элемента . И- И-ЗИ/ИШ, второй вход блока соединён с четвертым входо |темвнта |И-|И-ЗИ/Ида, третьим вжййом эпемента и первый вхсч элеменТа 2И-НЕ, выход 11влеита 11-itM-3M/Mn является первым выходом блока, выход элемента И-«И/ЙЛЙ является йторым выходом блока, выход элемента 2И-НЕ является четвертым выходом блока, первый выход счетчика соединен с пятым и шестым входами элемента И И-ЗИ/ИЛИ и четвертым входом элемента «И- И/ИЛИ, второй выход счетчика соединен с седьмым и девятым входами элемента И-4И-ЗИ/ИЛЙ, пятым и шес.тцм входами элемента 4и-1 И/ИЛН и вторым входом элемента 2И-НЕ, третий выход счетчика соединен с десятым и одиннадцатым входами элемента k И-ЗИ/ИЛИ и с седьмым и восьмым вхо дами элемента И- И/ИЛИ, первый выход счетчика является третьим выходом блока.. . На фиг. 1 представлена функциональная схема устройства; на фиг. 2 функциональная схема блока управления; на фиг. 3 временные диаграммы работы блока управления. Устройство для формирования адресов алгоритма быстрого преобразова .нйя Фурье содержит блок 1 управлеI ния, первый счетчик 2, представляющий собой .N-разрядный реверсивный счбтчик, второй счетчик 3, представляющий собой М-разрядный реверсивный счетчик (где log,JLog, ( ) , rpynnny элементов И, Я мультиплексо ров N+1 канал в один канал 5, регистр 6 и М-входовой элемент И-НЕ 7 Блок управления 1 содержит счетчик 8, элемент 1 И-4И-ЗИ/ИЛИ 9, элемент it И it И/ИЛИ 10, элемент 2И-НЕ 11 Устройство для формирования .адресов алгоритма быстрого преобразования Фурье работает следующим обра- зом. В первоначальном .состоянии все счётчики обнулены. На тактовый вход 9 4 счетчика 8 поступает тактовые импульсы, по отрицательному, перепаду которых счетчик переключается в новое состояние. Управляющие сигналы вырабатываются комбинационной схемой, состоящей из элементов согласно временной диаграмме, представленной на фиг. 3, где/ТИ - тактовые импульсы; А1-А -. разрядные выходы счетчика 8; 12 - сигнал на втором входе блока 1 управления; 13 - сигнал на первом выходе блока 1 управ- . ления; - сигнал на втором выходе блока, 1 управления; 15 сигнал на третьем выходе блока 1 управления; 16 - сигнал на четвертом выходе. блока 1 управления. Рассмотрим функционирование устройства при обработке п-й пары i-ro.слоя алгоритма БПФ. Пусть в данном цикле (12 тактов ) будет обработана п-я пара i-ro слоя алгоритма БП4. Во время обработки П-й пары операндов должна быть адресована n-1-я пара операндов для записи в запоминающее устройство (эта пара была обработана в .предыдущем цикле) и n+1-я пара операндов для считывания их из запоминающего устройства (эта пара будет обработана в следую(цем цикле). Номеру слоя соответствует % состояние второго счетчика 3. В со- отвётствии с этим состоянием (на третьем выходе блока 1 управления присутствует уровень логической единицы) мультиплексоры 5 данных передают информацию с разрядных выходов niepBoro счетчика 2 на свои выходы в следующем порядке; i-й слой 21- 2 ji- . о, -1. j. t: 1t - t f- t ...2 , т.е. в порядке, соответствующем адресам i-го слоя алгоритма БПФ. На выходе элемента И-НЕ 7 присутствует уровень логической единицы. Назначение элемент И-НЕ 7 дешифрация сотояния второго счетчика 3, соответствующего специальному с. алгоритма 5ПФ. Хотя цикл работы устройства состоит из 12 тактов (цикл работы известного устройства 8 тактов) , это не означает, что устройство теряет быстродействие, так как отсутствует микрооперация параллельного занесения информации в первый счетчик 2, а это дает возможность подават-ь на суммирующий и вычитающий входы данного счетчика импульсы более высокой частоты .

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

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

Если на четвертом выходе блока 1 управления пристуствует уровень логической единицьи то-. -,-Го, ,-я. га. ;,«. ,i4-i.

, 1,.../С ,«.,

N-

в о 4

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

то 1-1

2

,1+-

2..2

lO. о1.

2

9М-1

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

Пусть в данном цикле необходимо обработать п-ую пару операндов специального слоя Садресп , -nj) Во время обработки п-п пары операндов должны быть адресованы n-1-я пара операндов (адреса | п-1 и (2 ) , обработанная в предыдуьчем цикле, и п+1-я пара (адреса j и t2 -n-l3) , которая будет обработана в следующем цикле.

В первом и втором тактах блоком 1 управления вырабатывается сигналы на втором выходе, по положительному перепаду которых из первого счетчика 2 вычитаются две единицы, чем адресуется второй операнд n-1-й пары (Е2 -П4-1. В третьем такте блоком 1 управления вырабатывается сигнал на третьем выходе, по отрица;тельному перепаду которого в регистр б заносится адрес второго операнда n-1-й пары. В четвертом, пятом и шестом тактах на четвертом выходе блока 1 управления появляется уровень логического нуля. Кроме того, в шестом такте вырабатывается сигнал на первом выходе блока 1 управления, по положительному Г7ереп,аду которого в первый счетчик 2 добавляется единица, чем адресуется первый операнд n-1-й пары п-1 J, также в шестом такте вырабатывается сигнал на третьем выходе блока 1 управления, по отрицательному перепаду которого в регистр б заносится адрес первого операнда П-1-и пары, В седьмом 99 и восьмом тактах управляющие сигналы не вырабатываптся. В девятом так те на первом выходе блока 1 управления вырабатывается сигнал, по положительному перепаду которого в пе вый счетчик 2 добавляется единица, чем адресуется второй операнд n+1-й пары 2 -п-1Д1. Кроме того, в девятом такте на третьем выходе блока 1 управления вырабатывается сигнал, .по отрицательному перепаду которого в регистр 6 заносится адрес второго операнда П4-1-Й пары. В дecяtoм, оди надцатом и двенадцатом тактах на че вертом выходе блока 1 уп авлениа появляется уровень логического нуля Кроме того, в двенадцатом такте на первом выходе блока 1 управления вырабатывается сигнал, по положител ному перепаду которого в первый сче чик 2 добавляется единица, чем адре суется первый операнд n+1-ой пары |п+1 , таюче в двенадцатом такте на третьем выходе блока 1 управлени вырабатывается сигнал, по отрицател ному перепаду которого в регистр 6 заносится адрес первого операнда n+1-й пары. Цикл повторяется снова и снова, пока не будут обработаны все пары операндов безызбыточного алгоритма БПФ. После чего устройство заканчивает работу - все адреса безызбыточного алгоритма БПФ реализованы. После обнуления первого счетчика 2, второго счетчика 3 и счетчика 8 блока 1 управления устройство для формирования адресов процессора быстрого преобразования Фурье снова готово к работе. Таким образом, изобретение пр- зволяет повысить быстродействие и yпpoqтить управление устройством. Формула изобретения 1. Устройство для формирования адресов процессора быстрого пре,образования Фурье, содержащее первый и второй счетчики, регистр и блок управления, первый и второй вы ходы которого соединены соответстве но с рходом суммирования и входом вычитания первого счетчика, выход переноса и выход заема которого сое динены соответственно с входом суммирования и входом вычитания второго счетчика, третий выход блока управления соединен с тактовым входом регистра, выходы которого являются выходами устройства, о т л и чающееся тем,что, с целъю повышения быстродействия, оно содержит N мультиплексоров, группу эле- . ментов И и элемент И-НЕ, причем выходы второго счетчика соединены с соответствующими входами элемента И-НЕ и первыми входами соответствующих элементов М группы,вторые входы которых объединены и соединены с четвертым выходом блока управления, первый вход которого является тактовым входом устройства, второй вход блока управления соединен с выходом элемента И-НЕ, выходы элементов И группы соединены с управляющими входами соответствующих мультиплексоров, при чем информационные входы , N-1) мультиплексора Х ) соединены между собой и подключены к j-му 0 1, N-1) разрядному выходу -первого счетчика, илформационный вход j-ro (, N-1) мультиплексора Х() соединен с выходом младщего разряда первого счетчика, информационные входы j-rp , N-2) мультиплексора Чд(i™ N-1) соединены между собой и с j+1-м , N-2) разрядным выходом , первого счетчика,4 лнформационный вход j-ro , N-1) мультиплексора Х() соединен с инверсным ;разродным выходом j (. N-l) первого N-1) nept , N-1) счетчика, выход j-ro (j мультиплексора соединен с информаЦИОННЫМ входом D- (, N-1) регистра.J 2. Устройство no П. Г, о T л и чающееся тем, что блок управления содержит счетчик, элемент АИ-ЦИ-ЗИ/ИЛИ, элемент M-jH/MflM и элемент 2И-НЕ, причем первый вход блока соединен с тактовым входом счетчика, первым и вторым входами элемента Й- И/ИЛИ, первым, вторым и третьим входами элемента И- И-ЗИ/ИЛИ, второй вход блока соединен с четвертым входом элемента .гЗИ/ИЛИ, третьим входом элемента И- И/ИЛИ и первым входом элемента . 2И-НЕ, выход элемента И- И-ЗИ/ИЛИ является первым выходом блока, выход элемента И- И/ИЛИ является вторым выходом блока, выход элемента 2И-Н является четвертым выходом бло.ка, первый выход счетчика соединен с пятым и шестым входами элементна ЦИ- И-ЗИ/ИЛИ и четвертым входом элемента «И-гИ/ИЛИ, второй выход счетчика соединен с седьмым, восьмым и девятым входами элемента М-АИ ЗИ/ИЛИ, пятым и шестым входами элемента |И- И/ИЛИ и вторым входом элемента 2И-НЕ, третий выход счетчика соединен с десятым и одиннадцатым входами элемента И- И-ЗИ/ИЛИ и с седьмым и воЪьмым входами элемента 9 2 И- И/ИЛИ, первый выход счетчика является третьим выходом блока. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР fP SjOefiS, кл. 606F 15/332, 1976, 2.Авторское свидетельство СССР по заявке ff 2979625/2t, кл. GOfiF 15/332, 1981 (прототип).