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

(54)УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ АДРЕСОВ ПРОЦЕССОРА БЫСТРОГО ПРЕОБРАЗОВАНИЯ t Изобретемте относится к вычислительной технике и может быть использовано при построении устройств, использующих в своей работе алгоритм быстрого преобразования Фурье: устройствах для проведения спектрального анализа, генераторах широкополосного случайного процесса, синтезаторах речевых сигналов и т..д. Известно устройство формирования адресов, реализующее алгоритм быстрого преобразования Фурье, содержащее счетчик с логической схемой, позволяющей делитель его на две части, блок выдачи информации в сумматор, сумматор, построенный из комбинационных полусумматоров, блок вьщачи кодов адреса и блок управления разделением счетчика П. Недостатки известного блока - сло ность его реализации, невысокое быстродействие и невозможность реали зации безизбыточных алгоритмов быст рого преобразования Фурье. ФУРЬЕ Наиболее близким к изобретению по технической сущности является устройство формирования адресов, реализующее алгоритм быстрого преобразования Фурье, содержащее узел реконфигурации счетчика, выход которого соединен с управляющим входом счетчика, блок выдачи адресов, первый информационный вход которого соединен с выходом счетрчика, а выход - с выходом устройства, причем вход узла реконфигурации счетчика, первый и второй счетные входы счетчика и первый управляющий вход блока выдачи адресов соединены соответственно с первым, вторым, третьим и четвертым входами блока, регистр и группу элементов Ш1И| выход регистра и группы элементов ИЛИ соединены соответственно с вторым и третьим информационными входами узла выдачи й1дресов, второй и третий управляющий входы которого, управлякя 01й вход регистра и второй вход группы элемейтов ИЛИ соединены соответственно с пятым, шестым, седь мь1м и первым входами устройства, На второй, третий, четвертый, пятый, шестой, седьмой входы устройств подаются управляющие сигналы, которые вырабатываются блоком управления данного устройства. На первый вход устройства поступает информация о но мере слоя алгоритма быстрого преобразования Фурье, в котором в данный момент времени Функционирует устройство. Для получения данной информации устройство должно содержать второй счетчик и дешифратор, причем выход счетчика соединен с входом дешифратора, выход которого соединен с первым входом устройства. Управляющий вход второго счетчика должен быть соединен с -выходом блока управления устройства 2. ГГедостатки известного блока - сложность его построения и невозможность реализации перекрытия циклов обращения к памяти и циклов выполнения операций алгоритма быстрого преобразования Фурье, которое предполагает в течение времени обработки текущей пары операндов л , запись в память обработанной пары операндов п-1, извлечение из памяти пары операндов п +1, которая будет обработана в следующем цикле. Цель изобретения - упрощение и повышение быстродействия устройства. Поставленная цель достигается тем, чтЬ устройство для формирования адресов процессора быстрого преобразования Фурье, содержащее первый и второй- счетчики, дешифратор, регистр и блок управления, первый,, второй и третий выходы которого соединены соответственно со входом суммирования, входом вычитания и тактовым входом первого реверсивного счетчика, выход переноса и выход заема которого соединены соответственно с суюадрующим и вычитающим входами второго реверсивного счетчика, выхода которого соединены со входами дешифратора, выход старшего разряда которого подключен к первому входу блока управления, второй вход которого является тактовым входом устройства, а четвертый выкод блока упргизления соединен с тактовым входом регистра, выходы которого являются выxoдa я устрой.ства, содержит N узлов блокировки, каждый из которых содвряит элемент, ИЛИ-НЕ, 92 4 элемент И-НЕ и два сумматора по модулю два, причем выход элемента ИЛИНЕ подключен к первому входу первого сумматора по модулю два, выход которого соединен с первым входом второго сумматора по модулю два, второй вход первого сумматора помодулю два соединен с выходом элемента И-НЕ, первый вход которого объединен с первьм входом элемента ИЛИ-НЕ, при этом второй вход элемента ЙЛИ-НЕ |-го (, N) узла блокировки соединен с i-ым информационным выходом первого реверсивного счетчика, второй вход элемента И-НЕ {-го узла блокировки (1, N) соединен с пятым выходом блока управления, второй вход второго сумматора по модулю два f-ro (, N) узла блокировки соединен с шестым выходом блока управления, а выход второго сумматора по модулю два t-ro (, N) узла блокировки соединен с i-ым (i 1, N) информационным входом регистра и .i-ым (, N) информационным входом первого реверсивного счетчика, причем i-ый выход (, N--T) дешифратора подключен к первому входу элемен та ИЛИ-НЕ i +1-го (i 1, N) узла блокировки. Кроме того, блок управления содержит сдвиговый регистр, пять элементов ИЛИ и девять элементов И, причем первые входы первого, второго, третьего, четвертого, пятого, щестого и седьмого элементов И объединены 6 являются первым входом блока управления, выход седьмого элемента И является первым выходом блока управления, выход первого элемента ИЛИ подключен ко вторым входам пятого и шестого элементов И, выходы восьмого и девятого элементов И являются соответственно вторым и третьим выходами блока управления, выход второго элемента ИШ является четвертым выходом блока управления, а выходы пятого и шестого элементов И являются соответственно пятым и шестым выходами блока управления, первый . выход сдвигового регистра соединен с первым входом четвертого элемента ИЛИ, второй выход сдвигового регистра подключен к первому входу первого элемента ИЛИ, первому входу второго элемента ИЛИ и второму входу первого элемента И, третий выход сдвигового регистра подключен ко второму входу второго элемента ИЖ, 5 первому входу третьего элемента ИЛ второму входу второго элемента И и первому входу пятого элемента ШМ, четвертый выход сдвигового регистра соединен со вторым входом третьего элемента ИЛИ, пятый выход сдвигово- го регистра соединен со вторым входом первого элемента ШМ; /входом второго элемента ИЛИ, третьи входом третьего, элемента ИЛИ и вторым входом четвертого элемента И, шестой йыход сдвигового регистра соединен с информационньпч входом, сдвигового регистра, четверчъм входом второго элемента ИЛИ и вторым входом третьего элемента И, выход третьего элемента ИЛИ соединен со вторым входом седьмого элемента И, выход первого элемента И соединен со вторым входом четвертого элемента ИЛИ, выход которого подключен к первому входу восьмого элемента И, выходы второго, третьего и четвертого элементов И соединены соответственно со вторым, третьим и четвертым входами пятого элемента ИЛИ, выход Которого подключен к пер вому входу девятого элемента И, вто рой вход которого объединен со вторым входом восьмого элемента И, тре тьим входом седьмого элемента И, тактовым входом сдвигового регистра и является вторым входом блока у равления.J Принцип работы устройства заключается в следующем. Адреса пары операндов алгоритма быстрого преобразования Фурье отличаются информацией в одном разряде. номер которого соответствует номеру слоя алгоритма быстрого преобразова ния Фурье, причем адрес первого опе ранда содержит логический ноль в данном разряде, а адрес второго опе ранда - логическую единицу. Если за блокировать даннь1Й разряд, т.е. не пропускать информацию данного разря да на выхрде- устройства, а вместо информации заблокированного разряда подавать на соответствующий выход устройства уровень логического нуля или единицы, то можно адресовать пару операндов (первый и второ операнды соответственно). Каждое состояние счетчика адресует пару оп рандов, поэтому счетчик обладает избыточностью, ДГш устранения избыточности вводится операция восстановления перво 3 го счетчика, позволякицая исключить узел реконфигурации счетчика и тем самым повысить быстродействие за счет применения параллельного счетчика, который не мог применяться совместно с блок&м реконфигурации счетчика. Если в следующем такте работы состояние первого счетчика будет увеличено на единицу, в заблокированном разряде восстанавливается значение логической единищ 1 при сохранении информации в остальных разрядах первого счетчика (такт параллельного занесения информации в первый счетчик при адресации второго операнда), тогда может осуществиться перенос через блокированный разряд, если в следующем такте работы состояние первого счетчика будет уменьшено на единиц, в заблокированном разряде восстанавливается значение логического нуля при сохранении 1|5нформации в остальных разрядах первого счетчика (такт параллельного занесения в первый счетчик при адресации первого операнда), тогда может осуществиться заем из разряда старшего, чем заблокированный. Таким образом, заблокированный i)aзpяд выпадает из работы, т.е. устраняется избыточность. При работе в специальном слое (безизбыточный алгоритм быстрого преобразования Фурье) ни один из ра;зрядов не блокируется, Адресуется пара операндов п, 2 -п, где ,2 -1( N - количество разрядов первого счетчика. Фop a poвaниe адресов осуществляется следуюащм образом. Инверсное значение первого счетчика адресует второй операнд, затем в первый счетчик добавляется единица и прямое значение счетчика адресует первый операнд пары операндов специального слоя безизбыточного алгоритма быстрого преобразования Фурье. На фиг, 1 представлена функциональная схема устройства, на фиг. 2 функциональная схема блока управлещ1я, на фиг. 3 - временные диаграммы работы блока управления. Устройство дпя формирования адресов алгоритма быстрого преобразования Фурье содержит блок 1 управления, первый реверсивньй счетчик 2, второй реверсивньй счетчик 3, дешифратор 4, N узлов блокировки разряда 5 и ре- . , гистр 6. Каждый узел блокировки 5 содержи элемент 2 И-НЕ, элемент 2 Ш1И-НЕ и два сумматора по модулю два М2 (не /указаны), Блок управления содержит сдвигов регистр 7, элемент ШШ 8, элемент ИЛИ 9, элемент ИЛИ 10, элемент И И элемент И 12, элемент И 13, элемент И 4, элемент И 15, элемент И 16, элемент И 17, элемент ИЛИ }8, элеме ИЛИ 19, элемент И 20, элемент И,21. Устройство для формирования адресов алгоритма быстрого преобразования Фурье функционирует следующим образом. В первоначальном состоянии все счетчики обнулены, а регистр 7 блока I управления установлен в состояние 10000000. На управдякщий вход регистра 7 поступают тактовые импульсы и логическая единица продвигается по регистру 7, который функционирует как кольцевой регистр. Управляющие сигналы вырабатываются комбинационной схемой, состоящей из элементов 8-21 (фиг. 2) Согласно приведенной вре :енной диаграмме фиг. 3 , где ТИ - тактовые импульсы, А1-А8 - разрядные выходы регистра 7, 22- сигнал на первом входе блока 1 23- сигнал на третьем вьгходе блока , 24 - сигнал на втором выходе блока 1, 25 - сигнал на первом выходе блока 1, 26 - сигнал на шестом выходе блока I, 27 - сигнал на четвертом выходе блока , 28 - сигнал на пятом выходе блока 1. Рассмотрим функционирование устройства при обработке пары 1-го слоя алгоритма быстрого преобразования Фурье. Пусть в данном цикле (8 тактов) обрабатывается п-ая пара 1-го слоя алгоритма быстрого преобразования Фурье. Во время обработки п-ой пары опёравдов должна быть адресована n-1-ая пара операндов для записи их в запоминающее устройство( эта пара обработана в предьщущем цикле), ип + 1-ая пара операндов дпя считывания их из запоминающего устройства (эта пара будет обработана в следующем цикле). Номеру слоя соответствует состояние счетчика 3. В соответствии с этим состоянием на выхо/дах дешифратора 4 -О, 1, 2 ... 1-1. 1+, появляется урозень логического нуля, а на выходе i - уровень логической единицы. Данные уровни поступают на вторые входы узлов 5, при этом информация с разрядных выходов счетчика 2-2, 2..2-; 2..2 через два инвертора и повторитель (элементы ИЛИ-НЕ, первый и второй М2) поступают на входы регистра t nU . . u у на вход D регистра 6 поступает информация с четвертого выхода блока 1 управления через инвертор и два повторителя (элементы И-НЕ, первый и второй М2) f-ro узла 5. В счетчике 2 хранится информация, адресующая п-ую пару операндов. Б первом такте на втором выходе блока 1 управления вырабатывается сигнал, по которому производится вычитание единицы из счетчика 2, чем адресуется n-1-ая пара операндов, Во втором такте вырабатывается сигнал на четвертом выходе блока 1 управления,равный логической единице. и сигнал занесения информации в регистр 6, по заднему фронту которого в регистр 6 заносится адрес первого операнда n-1-ой пары. В третьем такте управляющие сигналы не вырабатываются, В четвертом такте вырабатыва ется сигнал занесения в регистр 6 на шестом выходе блока I управления и сигнал восстановления счетчика 2 на перйом выходе блока 1 управления при сигнале на четвертом выходе блока I управления равному логическому нулю, в результате чего в л -ом разряде счетчика 2 восстанавливается значение логической единшц, а по заднему фронту сигнала на шестом выходе блока 1 управления в регистр 6 заносится адрес второго операнда n-1-ой пары, В первой половине пятого такта вырабатывается сигнал на третьем выходе блока 1 управления, по которому в счетчик 2 добавляется единица и тем самым адресуется П-ая пара операндов, а во второй половине вырабатывается сигнал на первом выходе блрка 1 управлений , при сигнале на четвертом выходе блока 1 управления, равному логическому нулю, в результате чего в i-ом разряде счетчика 2 восстанавливается значение логической единицы. В шестом такте в первой его половине вырабатывается сигнал на третьем выходе блока 1 управления, по которомуjic4ef4HK 2 добавляется единица и тем самым

адресуется .n +1-ая пара операндов, а во второй половине вырабатывается сигнал на первом выходе блока 1 управления, при сигнале на четвертом выходе блока 1 управления равном логической единице, тем самым в V-OM разряде счетчика J восстанавливается значение логического нуля. Кроме того, в шестом такте вырабатывается сигнал на шестом выходе блока 1 управле ния, по заднему фронту которого в ре гистр 6 заносится адрес первого операнда п+ 1-ой пары. В седьмом такте управлякицие сигналы не вырабатывают- ся. В восьмом такте вырабатывается сигнал на шестом выходе блока i управления, при сигнале на четвертом выходе блока I управления, равном ло гическому нулю, по заднему фронту которого в регистр 6 заносится второго операндап+1-ой пары. Цикл повторяется до .тех пор, пока не будут обработаны все пары операндов по всем слоям, после че;го уст ройство начинает вырабатывать адреса пар операндов специального слоя безизбыточного алгоритма быстрого преоб разования Фурье, При этом на выходах дешифратора 4 - О, 1, 2,..,N-1 устанавливается уровень логического ну ля, а на выходе N уровень логической единицы. Ни один из разрядов сче чика 2 не блокируется. Информация с разрядных выходов счетчика 2 через два инвертора и повторитель {сигнал на пятом выходе блока 1 управления равный логическому нулю) - элементы ИЛИ-НЕ, nepBbrii и второй М2 или же через три инвертора (сигнал на пятом выходе блока 1 управления) элементы ИЛИ-НЕ, первый и второй М2, поступае на информационные входы регистра6. Пусть в данном цикле необходимо обработать п-ую пару операндов спёДиального аюя (адреса п и 2 -п). Во время обработки п-ой пары операндов долж1й | быть адресоваш) пара операндов (адреса п-1 и 2 -n+t) обработанная в предыдущем цикле, и n+1-ая пара операндов (адреса п+1 и 2 -п-1), которая будет обработана в следующем цикле. В счетчике 2 хранится информация, адресующая первый операнд ц-ой пары. В первом такте блоком 1 управления вырабатывается сигнал на втором выходе, по которому из счетчика 2 вычитается.единица, чем адресуется первый операнд п-1 пары. Во втором

такте на втором въжоде блока 1 управления вырабатывается сигнал, по кото рому из счетчика 2 вычитается единица, кроме того, на шестом выходе блока I управления вырабатывается сигнал занесения в регистр 6 при сигнале на пятом выходе блока управления 1, равном логической единице, по заднему фронту которого в регистр 6 адре заносится адрес второго операнда п-1-ой пары 2 -n+I , В третьем такте управляющие сигналы не вырабатываются. В четвертом такте выраба1Ъ вается сигнал на третьем выходе блока 1управления, по Koi-opoMy в счетчик 2добавляется единица, кроме того, на шестом выходе блока управления вырабатывается сигнал, при сигнале на пятом выходе блока } управления, равном логическому нулю, по заднему фронту которого в регистр 6 заносится адрес первого операнда л-1-ой пары tn-il. В пятом такте вырабатывается сигнал на третьем выходе блока 1 управления, по которому в счетчик 2 добавляется единица, В шестом такте вырабатывается сигнал на шестом выходе блока 1 управления, при сигнале на пятом выходе блока ) управления, равном логической единице, по заднему фронту которого в регистр 6 заносится адрес второго опера{ода n+1-ой пары В седьмом такте управляющие сигналы не вырабатываются. В восьмом такте вырабатывается сигнал на третьем выходе блока 1управления, по которому в счетчик 2добавляется единица, кроме того вырабатывается сигнал на шестом выходе блока I управления при сигнале на пятом выходе блока 1 управления, при сигнале на пятом выходе блока I управления, равному логическому нулю, по заднему фронту которого в регистр 6 заносится адрес первого операнда n+1-ой пары операндов п+О . Затем цикл повторяется до тех пор, пока не будут обработаны все пары операндов, после чего устройство заканчивает работу - все адреса безизбыточного алгоритма быстрого . преобразования Фурье реализованы. После обнуления счетчиков 2 и 3 устройство снова готово к работе. Таким образом, изобретение позволяет упростить конструкцию блока и повысить быстродействие. Формула изобретения I. Устройство для формирования ад ресов процессора быстрого преобразования Фурье, содержащее первый и второй счетчики, дешифратор, регистр и блок управления, первый, второй и третий выходы которого соединены соответственно с входом суммирования, входом вычитания и тактовым входом первого реверсивного счетчика, выход переноса и выход заема которого соединены соответственно с суммирующим и вычитаю1чим входами второго, реверсивного счетчика, выходы которого соединены с входами дешифратора, выход старшего разряда которого подключен к первому входу блока управления, второй вход которого является тактовым входом устройства, а четвер тый выход блока управления соединен с тактовым входом регистра, выхо которого являются выходами устройства, отличаючееся тем, что, с целью упрощения устройства и повьшения быстродействия, оно соДер- ; жит N узлов блокировки, каждый из которых содержит элемент ИЛИ-НЕ, элемент И-НЕ и два сумматора по модулю два, причем выход элемента ИЛИ-НЕ подключен к первому входу первого сумматор по модулю два, выход которого соединен с первым входом второго сумматора по модулю два, второй вход первог сумматора по модулю два соединен с выходом элемента Н-НЕ-, первый вход которого объединен с первым входом элемента ИЛИ-НЕ, при этом второй взсС элемента ШШ-НН i-ro (1, N) узла блокировки соединен с i-ым информаци онным выходом первого реверсивного счетчика, вход элемента И-НЕ г-го узла блокировки -(, N) соединен с йятым выходом блока управления, второй вход второго сумматора по модулю, два i-ro (, N) узла блокировки соединен с шестым выходом блока ущ авления, а выход второго су матора по модулю два i-ro , М) узла блокировки соединен с «-ым (1 1, М) информационным входом регистра и f-ым (1, N) информационным входом первого реверсивного счетчика, причем -ый выход (, N-1) дешифратора подключен к первому входу элемента ИЛИ-НЕ (, N) узла блокировки. 2. Устройство по п, I, о т л и чающеесй тем, что блок управ 63 ления содержит сдвиговый регистр, пять элементов ИЛИ и девять элементор И, причем первые входы первого, второго, третьего, четкертого, пятого, шестого и седьмого элементов И объединены и являются первым входом блока управления, выход седьмого элемента И является первым выходом блока управления, выход первого элемента ИЛИ подключен к вторым входам пятого и шестого элементов И, выходы восьмого и девятого элементов И являются соответственно вторым и третьим выходами блока управления, выход второго элемента И)И является четвертым выходом блока управления, а выходы пятого и шестого элементов И являются соответственно пятым и шестым выходами блока управления первый выход сдвигового регистра соединен с первым входом четвертого элемента ШШ, второй выход сдвигового регистра подключен к первому входу первого элемента ИЛИ, первому входу второго элемента ИЛИ и второму входу первого элемента И, третий выход сдвигового регистра подключен к второму входу второго элемента ШМ, первому входу третьего элемента ИЛИ, второму вход второго элемента И и первому входу пятого элемента ИЛИ, четвертый выход сдвигового регистра соединен с вторым входом третьего элемента ШМ, пятый выход сдвигового регистра соединен с вторым входом первого элемента ИЛИ, третьим входом второго элемента ШШ, третьим входом третьего элемента ИЛИ и вторым входом четвертого элемента И, шестой выход сдвигового регистра соединен с информационным входом сдвигового регистра, четвертым входом второго элемента ШШ и вторым входом третьего элемента И, выход третьего элемента ИЛИ соединен с вторым входом седьмого элемента И, выход первого элемента И соединен с вторым входом четвертого элемента ИЛИ, выход которого подключён к первому входу восьмого элемента И, выходы второго, третьего и четвертого элементов И соединены соответствено с вторым, третьим и четвертым входами пятого элемента ИЛИ, выход которого подключен к первому входу девятого элемента И, второй вход которого объединен с вторым входом восьмого элемента И, третьим входом седьмого, элемента И, тактовым входом сдвигового регистра и является вторым входом блока управления .

Источники информации, ..... .ь.-,-- „„..- - принятые во внимание при экспертизе№548863,кл. G06 F15/332,1976(протртип)

922763

1.Авторское свидетельство СССР № 430381, кл. G 06 F 9/00, 1975.

2.Авторское свидетельство СССР

Фиг.1

f у j, 5 f 1 t 1 г I f f Т f

HJn n JHJLnjn П„П rTJTJTJT

;г