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

(61) Дополнительное к авт. св (22) Заявлено 02.09.80 (21) 25 18-2 29 б Г 15/332 с присоелииеиием заявки ле(23) Приоритет Гоеудеретекницй мемнт СССР по делам нзебретеин(088.8) еткрцтн Дата опубликования описания 23.04.8 2) Авторы изобретеии(71) Заявител УСТРОИСТВО ДЛЯ ФОРИИРОВАНИЯ АЦРЕСО ПРОЦЕССОРА БЫСТРОГО ПРЕОБРАЗОВАНИЯФУРЬЕ Изобретение относится к вычислительной технике и может быть использовано при построении устройств, использующих в своей работе алгоритмбыстрого преобразования Фурье: устройствах для проведения спектрального анализа, генераторах широкополосного случайного процесса, синтезаторах речевых сигналов и .т,.д,Известно устройство формированияадресов, реализующее алгоритм быстрого преобразования Фурье, содержащее счетчик с логической схемой, позволяющей делитель его на две части,блок выдачи информации в сумматор,сумматор построенный из комбинационных полусумматоров, блок выдачикодов адреса и блок управления разделением счетчика 11,Недостатки известного блока - сложность его реализации, невысокоебыстродействие и невозможность реализации безизбыточных алгоритмов быстрого преобразования Фурье. Наиболее близким к изобретениюпо технической сущности является устройство формирования адресов, реали.зующее алгоритм быстрого преобразования Фурье, содержащее узел реконфигурации счетчика, выход которого соединен с управляющим входом счетчика,блок выдачи адресов, первый ннформационный вход которого соединен с выходом счетчика, а выход - с выходам 6устройства, причем вход узла реконфигурации счетчика, первый н второйсчетные входы счетчика и первый управляющий вход блока выдачи адресов сое"динены соответственно с первым, вто- Ирым, третьим и четвертым входами блока, регистр и группу элементов ИЛИ,выход регистра и группы элементовИЛИ соединены соответственно с вторым и третьим информационными входами узла выдачи адресов, второй итретий управляющий входы которого,управляющий вход регистра и второйвход группы элемейтов ИЛИ соединены5 0 15 20 25 ЭО 35 40 45 50 соответственно с пятым, шестым, седьмым и первым входами устройства.На второй, третий, четвертый, пятый, шестой, седьмой входы устройстваподаются управляющие сигналы, которые вырабатываются блоком управленияданного устройства. На первый входустройства поступает информация о номере слоя алгоритма быстрого преобразования Фурье, в котором в данныймомент времени функционирует устройство. Для получения данной информации устройство должно содержать второй счетчик и дешифратор, причем выход счетчика соединен с входом дешифратора, выход которого соединенс первым входом устройства. Управляющий вход второго счетчика долженбыть соединен с .выходом блока управления устройства 21,Йедостатки известного блока - сложность его построения и невозможностьреализации перекрытия циклов обращения к памяти н циклов выполненияопераций алгоритма быстрого преобразования Фурье, которое предполагает в течение времени обработки текущей пары операндов , запись впамять обработанной пары операндовизвлечение из памяти пары операндов и +1, которая будет обработанав следующем цикле.Цель изобретения - упрощение иповышение быстродействия устройства.11 оставленная цель достигаетсятем, что устройство для формирования адресов процессора быстрого преобразования Фурье, содержащее первыйи второй счетчики, дешифратор, регистр и блок управления, первый,второй и третий, выходы которого соединены соответственно со входом суммирования, входом вычитания и тактовым входом первого реверсивногосчетчика, выход переноса и выходзаема которого соединены соответственно с суммирующим и вычитающимвходами второго реверсивного счетчика, выходы которого соединены совходами дешифратора, выход старшего разряда которого подключен кпервому входу блока управления, второй вход которого является тактовымвходом устройства, а четвертый выход блока управления соединен с тактовым входом регистра, выходы которого являются выходами устройства,содержит Х узлов блокировки, каждыйиэ которых содержит элемент, ИЛИ-НЕ,элемент И-НЕ и два сумматора по модулю два, причем выход элемента ИЛИНЕ подключен к первому входу первого сумматора по модулю два, выход которого соединен с первым входом второго сумматора по модулю два, второй вход первого сумматора по- модулю два соединен с выходом элемента И-НЕ, первый вход которого объединен с первым входом элемента ИЛИ-НЕ, при этом второй вход элемента ИЛИ-НЕ 1-го (1=1, Й) узла блокировки соединен с 1"ым информационным выходом первого реверсивного счетчика, второй вход элемента И-НЕ 1-го узла блокировки (1=1, Й) соединен с пятым выходом блока управления, второй вход второго сумматора по модулю два 1"го (1=1, Й) узла блокировки соединен с шестым выходом блока управления, а выход второго сумматора по модулю два 1-го (1=1, Й) узла блокировки соединен с 1-ым (1 =1, Й) информационным входом регистра и л-ым (1=1, Й) информационным входом первого реверсивного счетчика, причем 1-ый выход (1=0, Й"Т) дешифратора подключен к первому входу элемента ИЛИ-НЕ +1-го (=1, Й) узла блокировки.Кроме того, блок управления содержит сдвиговый регистр, пять элементов ИЛИ и девять элементов И, причем первые входы первого, второго, третьего, четвертого, пятого, шестогои седьмого элементов И объединеныЙ являются первым входом блока управления, выход седьмого элемента И является первым выходом блока управления, выход первого элемента ИЛИ подключен ко вторым входам пятого и шестого элементов И, выходы восьмого и девятого элементов И являются соответственно вторым и третьим выходамн блока управления, выход второго элемента ИЛИ является четвертым выходом блока управления, а выходы пятого и шестого элементов И являются соответственно пятым и шестым выходами блока управления, первый выход сдвигового регистра соединен с первым входом четвертого элементаИЛИ, второй выход сдвигового регист.ра подключен к первому входу первого элемента. В 1 И, первому входу второго элемента ИЛИ и второму входупервого элемента И, третий выходсдвигового регистра подключен ковторому входу второго элемента ИЛИ,22763 55Устройство для формирования адресов алгоритма быстрого преобразования Фурье содержит блок 1 управления, первый реверсивный счетчик 2, второй реверсивный счетчик 3, дешифратор 4,5 9первому входу третьего элемента ИЛ,второму входу второго элемента И ипервому входу пятого элемента ИЛИ,четвертый выход сдвигового регистрасоединен со вторым входом третьегоэлемента ИЛИ, пятый выход сдвигово"го регистра соединен со вторым вхо"сдом первого элемента ЮЩ третьимвходом второго элемента ИЛИ, третьимвходом третьего элемента ИЛИ и вторым входом четвертого элемента И,шестой выход сдвнгового регистра)соединен с информационным входом,сдвигового регистра, четвертым входом второго элемента ИЛИ и вторымвходом третьего элемента И, выходтретьего элемента ИЛИ соединен совторым входом седьмого элемента И,выход первого элемента И соединенсо вторым входом четвертого элемента ИЛИ, выход которого подключенк первому входу восьмого элементаИ, выходы второго, третьего и четвертого элементов И соединены соот"ветственно со вторым, третьим ичетвертым входами пятого элементаИЛИ, выход которого подключен к пер"вому входу девятого элемента И, вто"рой вход которого объединен со вто-рым входом восьмого элемента И, третьим входом седьмого элемента И,тактовым входом сдвигового регистра н является вторым входом блока управления,Принцип работы устройства заключается в следующем, .Адреса пары операндов алгоритмабыстрого преобразования Фурье отлиэчаются информацией в одном разряде,номер которого соответствует номеруслоя алгоритма быстрого преобразования Фурье, причем адрес первого операнда содержит логический ноль вданном разряде, а адрес второго операнда - логическую единицу. Если заблокировать данный разряд, т,е. непропускать информацию данного разряда на выходе. устройства, а вместоинформации заблокированного разря да подавать на соответствующий вы- "ход устройства уровень логическогонуля или единицы, то можно адресовать пару операндов (первый и второйоперанды соответственно), Каждоесостояние счетчика адресует пару операндов, поэтому счетчик обладаетизбыточностью.ДЛя устранения избыточности вводится операция восстановления перво 5 10 15 20 25 30 35 40 го счетчика, позволяющая исключить узел реконфигурации счетчика и тем самым повысить быстродействие засчет применения параллельного счетчика, который не мог применяться совместно с блокЬм реконфигурации1счетчика.Если в следующем такте работы сос тояние первого счетчика будет увеличено на единицу, в заблокированном разряде восстанавливается значе" ние логической единицы при сохранении информации в остальных разрядах первого счетчика (такт параллельного занесения информации в первый счетчик при адресации второго операнда), тогда может осуществиться перенос через блокированный разряд, если в следующем такте работы состояние первого счетчика будет уменьшено на единиц, в заблокирован" ном разряде восстанавливается значение логического нуля при сохранении информации в остальных разрядах первого счетчика (такт параллельного занесения в первый счетчик при адресации первого операнда), тогда может осуществиться заем из разряда старшего, чем заблокированный. Таким образом, заблокированный разряд выпадает из работы, т.е, устраняется избыточность. При работе в специальном слое (безизбыточный алгоритм быстрого преобразования Фурье) ни один из разрядов не блокируется.Адресуетс пара операндов и, 2 -и,й где и=1,2 "-11 й - количество раз-. рядов первого счетчика.Формирование адресов осуществляется следующим образом. Инверсное значение первого счетчика адресует второй операнд, затемв первый счетчик добавляется единица и прямое значение счетчика адресует первый операнд пары операндовспециального слоя безизбыточногоалгоритма быстрого преобразованияФурье. На фиг,представлена функциональная схема устройства, на фиг. 2 - функциональная схема блока управления,на фиг.-3 - временные диаграммы работы блока управления,763 8нуля, а на выходе 1 в уровень логи"ческой единицы, Данные уровни поступают на вторые входы узлов 5, приэтом информация с разрядных выходовсчетчика 2-2 , 2"2" ", 2 " .2через два инвертара и повторитель(элементы ИЛИ-НЕ, первый и второйМ 2) поступают на вхофа регистра6 О ОО " О О" Оф 1на вход О регистра 6 поступаетинформация с четвертого выхода блока1 управления через инвертор и дваповторителя (элементы И-НЕ, первыйи второй М 2) 1-го узда 5. В счетчике2 хранится информапия, адресующаяи-ую пару операндов,В первом такте на втором выходеблока 1 управления вырабатываетсясигнал, по которому производитсявычитание единицы из счетчика 2, чемадресуется -1-ая пара операндов.Во втором такте вырабатывается сигнал на четвертом выходе блока 1 управления,равный логической единице,и сигнал занесения информации в регистр 6, по заднему Фронту которогов регистр 6 заносится адрес первогооперанда и -1-ой пары. В третьем так .те управляющие сигналы не вырабатываются, В четвертом такте вырабатывается сигнал занесения в регистр 6на шестом выходе блока 1 управленияи сигнал восстановления счетчика2 на первом выходе блока 1 управления при сигнале на четвертом выходеблока 1 управления равному логическому нулю. в результате чего в 1 -омразряде счетчика 2 восстанавливаетсязначение логической единицы, а позаднему Фронту сигнала на шестом выходе блока 1 управления в регистр 6заносится адрес второго операндаи-ой пары, В первой половине пятого такта вырабатывается сигнал натретьем выходе блока 1 управления,по которому в счетчик 2 добавляется.единица и тем самым адресуется11-ая пара операндов, а во второй половине вырабатывается сигнал на первом выходе блока 1 управлений, присигнале на четвертом выходе блока 1управления, равному логическому нулю, в результате чего в 1 -ом разряде счетчика 2 восстанавливается значение логической единицы. В шестомтакте в первой его половине вырабатывается сигнал на третьем выходе блока 1 управления, по которому в счетчик2 добавляется единица и тем самым 7 9228 узлов блокировки разряда 5 и ре-. , гистр 6.Каждый узел блокировки 5 содержитэлемент 2 И-НЕ, элемент 2 ИЛИ-НЕ идва сумматора по модулю два М 2 неуказаны).Блок управления содержит сдвиговыйрегистр 7, элемент ИЛИ 8, элемент ИЛИ 9, элемент ИЛИ 10, элемент И 11,элемент И 12, элемент И 13, элемент 16 И 14, элемент И 15, элемент И 16,элемент И 17, элемент ИЛИ 18, элемент ИЛИ 19, элемент И 20, элемент И.21,Устройство для Формирования адресов алгоритма быстрого преобразования фурье Функционирует следующим образом.В первоначальном состоянии всесчетчики обнулены, а регистр 7 блока 1 управления установлен в состоя- щние "10000000". На управляющий вход регистра 7 поступают тактовые импуль" сы и логическая единица продвига- ется по регистру 7, который Функцио-,нирует как кольцевой регистр. Уп равляющие сигналы вырабатываются комбинационной схемой, состоящей изэлементов 8-21 (Фиг. 2). Согласно приведенной вре енной диаграммеФиг. 3 , где ТИ " тактовые импульсы, Зб А 1-АЯ - разрядные выходы регистра 7, 22 - сигнал на первом входе блока 1, 23 - сигнал на третьем выходе блока 1, 24 - сигнал на втором выходе блока25 - сигнал на .первом выходе бло 35 ка 1, 26 - сигнал на шестом выходе блока 1, 27 - сигнал на четвертом выходе блока 1, 28 - сигнал на пятом выходе блока 1.40Рассмотрим Функционирование устройства при обработке и-ой пары 1-го слоя алгоритма быстрого преобразования Фурье.Пусть в данном цикле 18 тактов) обрабатывается и-ая пара 1-го слоя45 алгоритма быстрого преобразования Фурье. Во время обработки -ой пары операндов должна быть адресована п-ая пара операндов ддя записи их в запоминающее устройство( эта. пара обработана в предыдущем цикле),50 и и+1-ая пара операндов дпя считывания их из запоминающего устройства эта пара будет обработана в следующем цикле). Номеру слоя соответствует состояние счетчика 3. В соот 55 ветствии с этим состоянием иа выхо,дах дешифратора 4 - О, 1, 21-1.1+ 1появляется уровень логическогоа 1 адресуется и+1-ая пара операндов, а во второй половине вырабатывается сигнал на первом выходе блока 1 управления, при сигнале на четвертом выходе блока 1 управления равном ло гической единице, тем самым в-ом разряде счетчика 1 восстанавливается значение логического нуля. Кроме того, в шестом такте вырабатывается сиг.нал на шестом выходе блока 1 управлЕния, по заднему фронту которого в регистр 6 заносится адрес первого операнда и +1-ой пары. В седьмом такте управляющие сигналы не вырабатываются. В восьмом такте вырабатывается 13 сигнал на шестом выходе блока 1 управления, при сигнале на четвертом выходе блока 1 управления, равном логическому нулю, по заднему фронту которого в регистр 6 заносится адрес 20 второго операнда а +1-ой пары.Цикл повторяется до .тех пор, пока не будут обработаны все пары опЕ- рандов по всем слоям, после чего устройство начинает вырабатывать адреса И пар операндов специального слоя безизбыточного алгоритма быстрого преобразования Фурье. При этом на выходах дешифратора 4 - О, 1, 2,.й"1 устанавливается уровень логического ну ля, а на выходе 1 ч уровень логической единицы. Ни один из разрядов счетчика 2 не блокируется. Информация с разрядных выходов счетчика 2 через два инвертора и повторитель (сигнал на пятом выходе блока 1 управления равный логическому нулю) - элементы ИЛИ-НЕ, первый и второй М 2 или же через три инвертора (сигнал на пятомвыходе блока 1 управления) элементы ИЛИ-НЕ, первый и второй М 2, поступает на.информационные входы регистра 6,Пусть в данном цикле необходимо обработать и-ую пару операндов спе- ,циального слоя (адреса и и 2 -и).М Во время обработки и-ой пары операндов должны быть адресованы и-ая пара операндов (адреса ии 2 -и+1),Ю обработанная в предыдущем цикле, и и+1-ая пара операндов (адреса и+1 ий Ю 2 -и), которая будет обработана в следующем цикле. В счетчике 2 хранится информация, адресующая первый операнд и-ой пары.В первом такте блоком 1 управле 33 ния вырабатывается сигнал на втором выходе, по которому из счетчика 2 вычитается единица, чем адресуется первый операнд ипары. Во втором такте на втором выходе блока 1 управления вырабатывается сигнал, по которому из счетчика 2 вычитается единица, кроме того, на шестом выходе бло" ка 1 управления вырабатывается сигнал занесения в регистр 6 при сигнале на пятом выходе блока управления 1, равном логической единице, по заднему Фронту которого в регистр 6 заносится адрес второго операнда и-ой пары 12 -и+1, В третьем такте управляющие сигналы не вырабатываются. В четвертом такте вырабатывается сигнал на третьем выходе блока 1 управления, по которому в счетчик 2 добавляется единица, кроме того, на шестом выходе блока 1 управления вырабатывается сигнал, при сигнале на пятом выходе блока 1 управления, равном логическому нулю, по заднему Фронту которого в регистр 6 заносится адрес первого операнда и-ой пары и. В пятом такте вырабатывается сигнал на третьем выходе блока 1 управления, по которому в счет" чик 2 добавляется единица, В шестом такте вырабатывается сигнал на шестом выходе блока 1 управления, при сигнале нз пятом выходе блокауп" равления, равном логической единице, по заднему фронту которого в регистр 6 заносится адрес второго операнда и+1-ой пары Г 2 ф"-и"1) . В седьмом такте управляющие сигналы не вырабатываются. В восьмом такте вырабатывается сигнал на третьем выходе блокауправления, по которому в счетчик 2 добавляется единица, кроме того вырабатывается сигнал на шестом выходе блока 1 управления при сигнале на пятом выходе блока 1 управления, при сигнале иа пятом выходе блока 1 управления, равному .логическому нулю, по заднему фронту которого в ре" гистр 6 заносится адрес первого опе" ранда и+1-ой пары операндов и+1 .Затем цикл повторяется до тех пор, пока не будут обработаны все пары операндов, после чего устройство заканчивает работу - все адреса безизбыточного алгоритма быстрого преобразования фурье реализованы. После обнулЕния счетчиков 2 и 3 устройство снова готово.к работе,Таким образом, изобретение позволяет упростить конструкцию блока и повысить быстродействие.922763 12 юФормула изобретения Устройство для формирования адресовпроцессора быстрого преобразования Фурье, содержащее первый ивторой счетчики, дешифратор, регистри блок управления, первый, второй итретий выходы которого соединены соответственно с входом суммирования,входом вычитания и тактовым входом 10первого реверсивного счетчика, выходпереноса и выход заема которого соединены соответственно с суммирующими вычитающим входами второго реверсивного счетчика, выходы которого1 фсоединены с входами дешифратора, вы"ход старшего разряда которого подключен к первому входу блока управления, второй вход которого являетсятактовым входом устройства, а четвер- щтый выход блока управления соединен с тактовым входом регистра, выходыкоторого являются выходами устройства, о т л и ч а ю щ е е с я тем,что, с целью упрощения устройства иповышения быстродействия, оно содержит М узлов блокировки, каждый из которых содержит элемент ИЛИ-НЕ, элемент 1И-НЕ и два сумматора по модулю два,причем выход элемента ИЛИ-НЕ подключен к первому входу первого сумматорапо модулю два, выход которого соединен с первым входом второго сумматора по модулю два, второй вход первогосумматора по модулю два соединен свыходом элемента И-НБ, первый вход3которого объединен с первым входомэлемента ИЛИ-НЕ, при этом второй вхбдэлемента ИЛИ-НЕ -го (=1, К) узлаблокировки соединен с 1-ым информаци 40онным выходом первого реверсивногосчетчика, второй вход элемента И-НЕ-го узла блокировки (1=Г, Й) соединен с пятым выходом блока управления, второй вход второго сумматорапо модулю. два 1-го (=1, М) узла45блокировки соединен с шестым выходомблока управления, а выход второго сумматора по модулю два -го (=Г, Й)узла блокировки соединен с 1-ым (1==1, Й) информационным входом регистра и 1-ым ( 1, Й) инФормационнымвходом первого реверсивного счетчика, причем 1-ый выход (1=0, Й"1)дешифратора подключен к первому входу элемента ИЛИ-НЕ 1+-го (3=1, М)узла блокировки,2. Устройство по п, 1, о т л и "ч а ю щ е е с я тем, что блок управления содержит сдвиговый регистр,пять элементов ИЛИ и девять элементогИ, причем первые входы первого,второго, третьего, четвертого, пятого, шестого и седьмого элементов Иобъединены и являются первым входомблока управления, выход седьмогоэлемента И является первым выходомблока управления, выход первого элемента ИЛИ подключен к вторым входампятого и шестого элементов И, выходывосьмого и девятого элементов И являются соответственно вторым и третьим выходами блока управления, выход второго элемента ИЛИ являетсячетвертым выходом блока управления,а выходы пятого и шестого элементовИ являются соответственно пятым ишестым выходами блока управлениямипервый выход сдвигового регистра соединен с первым входом четвертогоэлемента ИЛИ, второй выход сдвигового регистра подключен к первому входу первого элемента ИЛИ, первомувходу второго элемента ИЛИ и второмувходу первого элемента И, третийвыход сдвигового регистра подключенк второму входу второго элемента ИЛИ,первому входу третьего элемента ИЛИ,второму входу второго элемента И ипервому входу пятого элемента ИЛИ,четвертый выход сдвигового регистра соединен с вторым входом третьегоэлемента ИЛИ, пятый выход сдвиговогорегистра соединен с вторым входом первого элемента ИЛИ, третьим входом второго элемента ИЛИ, третьим входомтретьего элемента ИЛИ и вторым входом четвертого элемента И, вестойвыход сдвигового регистра соединенс информационным входом сдвиговогорегистра, четвертым входом второгоэлемента ИЛИ и вторым входом третьего элемента И, выход третьего элемента ИЛИ соединен с вторым входом седьмого элемента И, выход первого элемента И соединен с вторым входом четвертого элемента ИЛИ, выход которогоподключен к первому входу восьмогоэлемента И, выходы второго, третьего и четвертого элементов И соединены. соответствено с вторым, третьим и четвертым входами пятого элемента ИЛИ, выход которого подключен к первому входу девятого элемента И, второй вход которого объединен с вторым входом восьмого элемента И, третьим входом седьмого, элемента И, тактовымФвходом сдвигового регистра и.являет.13 ся вторым входом блока управленияИсточники инФормации,принятые во внимание при экспертизе922763 141. Авторское свидетельство СССРУ 430381, кл. С 06 Г 9/00, 1975 е2. Авторское свидетельство СССР9548863,кл. 6 06 Г 157332,1976(прототип)5922763 Р Ф Х Ф 7 8У 3 Ф Ф У Т У ЛК Л 7 Составитель А.Баранов Техред И. Гайду Корректор И,Макаренко Редактор Н.Пушненкова Филиал 111 П 111 атент, г,. Ужгород, ул. Проектная, 4 Заказ 2583/65 Тираж 732 ПодписноеВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д. 4/5