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

СОЮЗ СОВЕТСКСОЦИАЛИСТИЧЕРЕСПУБЛИН 09) (11) 1) 4 С 06 Р 15/33 4-24шюл. Ф 46икова и В.А. Шаньг уль тер бл ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ПИСАНИЕ ИЗОБР ВТОРСКОМУ СВИДЕТЕЛЬСТВ(56) Авторское свидетельство СССР У 999062, кл. С 06 Р 15/332, 1979.Авторское свидетельство СССР 9 1056207, кл. С 06 Р 15/332, 1981. (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ АДРЕСОВ ОПЕРАНДОВ ПРОЦЕССОРА БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЪЕ(57) Изобретение относится к вычислительной технике, к устройствам для выполнения быстрого преобразования Фурье, которые могут быть применены всистемах цифровой обработки сигналов.Цель изобретения - повьппенпе быстродействия, Поставленная цель достигается за счет того, что в состав устройства входит счетчик 1, мультиплексоры 2,3, регистр 4, счетчик 5, мультиплексор 6, регистр 7, преобразователь кодов 8, состоящий из сдвиговогорегистра и блока элементов И-ИЛИ,м типлексор 9, счетчик 10, счетчики аций 11, дешифратор 12, счетчик 13и ок управления 14. 5 ил.Изобретение относится к вычислительной технике, а именно к устройствам для выполнения быстрого преобразования Фурье (БПФ), которые могутбыть применены в системах цифровойобработки сигналов.Цель изобретения - повышение быстродействия,На фиг. 1 приведена схема устрой- Оства, на Фиг. 2 - схема преобразователя кодов; на фиг. 3 - схема блокауправления; на фиг. 4 - граф-схемаалгоритма; на фиг. 5 - временные диаграммы работы. 15Устройство содержит счетчик 1,мультиплексоры 2 и 3, регистр 4,счетчик 5, мультиплексор 6, регистр7, преобразователь 8 кодов, мультиплексор 9, счетчик 10, счетчик итераций 11, дешифратор 12, счетчик 13и блок управления 14.Преобразователь кодов (фиг. 2)содержит блок элементов И-ИЛИ 15,состоящий из и элементов, где и - 25число разрядов адресного устройства, и сдвиговый регистр 16,Блок управления 14 (фиг. 3) содержит генератор 17 тактовых имЗО пульсов, элемент И 18, триггер 1 9, триггер 20, триггер 21, элемент И 22, регистр 23, элементы И 24-26, регистр 27, элемент И 28, счетчик 29, дешифраторы 30 и 31, мультиплексоры 32 и 33, элементы И 34 и 35, триггер Зб и элемент ИЛИ 37. Устройство Формирует адреса алгоритма БПФ для граф-схемы (фиг, 4). 40 Отличительной особенностью его является то, что закон Формирования адресов считывания не зависит от номера итерации, причем адрес первого операнда отличается от второго опе - 45 ранда для одной и той же базовой операции на Я/2, где М - размер обрабатываемого массива. Закон Формирования адресов записи зависит от номера итерации, причем адрес первого операнда отличается от адреса второ го операнда.на 2 , где 1 " номер итерации. Как видно из граФ-схемы алгоритма, входной и выходной массивы располагаются в памяти в естественном порядке. Счетчик 1 предназначен для формирования первого адреса считывания, а на счетчике 5 формируется второй адрес считывания. Рассмотрим работу устройства приформировании адресов для операцииБПФ.В исходном состоянии все счетчикии регистры установлены в нулевоесостояние, триггер 20 установлен в0ФВнешнее устройство выставляет навходах устройства соответственно кодоперации БПФ (О) и код размера обрабатываемого массива Н. С получением по входу сигнала "Пуск" триггер20 устанавливается в состояние "1"и разрешает прохождение синхросигналов ТЗ на вход счетчика 29.На соответствующих выходах дешифратора ЗО начинают появляться сигналы ДШ 0 - ДШ 14, стробированныесерией Т 2, Сигналом ДШ 7 происходитзанесение в регистр 27 кода Ю, определяющего размер обрабатываемогомассива. Примем, что коду "001" соответствует М = 32Сигналом ДШ 8 через элемент И 35устанавливаются в состояние 0" триггер 21, счетчики 5, 11 и 13 и ре -гистр 16.Сигналом ДШ 9 в регистре 23 фиксируется код "01", соответствующийвыполнению операции БПФ,По сигналу ДШ 1 О устанавливаетсяв состояние "1" триггер 19 и начинает работать счетчик 1. Этим же сигналом в счетчике 5 устанавливается код"010000", соответствующий значению И/2 = 6.Состояние счетчика 5, равное 6,через вход мультиплексора 2 (открытый при значении синхросигнала Т 1,равном "1"), вход мультиплексора 3(открытый при состоянии триггера 21,равном "О, что соответствует нечетной итерации) фиксируется в регистре4 по.синхросигналу ТЗ. При значении синхросигнала Т 1, равном "0", на вход регистра 4 подключается выход счетчика 1 и положительным фронтом синхросигнала ТЗ фиксируется в регистре 4, Далее состояние счетчикови 5 по положительному фронту синхросигнала Т 1 увеличивается на единицу и описанным вьпде способом передается в регистр 4 и далее на выход устройства. Работа счетчика 10, формирующего лреса записи, в это время блокирова нулевым состоянием триггера 36.При появлении сигнала ДШ 4 через элемент И 34 триггер 36 устанавливается в состояние "1" и разрешает ра- г;боту счетчика 10, одновременно через элемент И 26 в счетчике устанавлива - ется код "0010" и работа его блокируется.Адреса записи формируются следующим образом. Счетчик итераций 11 на 10 первой итерации находится в состоянии001 , чта соответствует состоянию "1" на выходе дешифратара 12,При этом на выходе элемента И-ИЛИ 15 передается синхросигнал Т 1, который со ответствует значению первого разряда адресов записи.Сдвиговый регистр 16 имеет и разрядов. Значения разрядов счетчика 10, подключенных к входу блока элементов И-ИЛИ 15, на выход преобразователя кодов не проходят . На всех инверсных выходах сдвигового регистра 16 (кроме первого разряда) установлен еди 25 ничный уровень. При этом значения разрядов счетчика 10,.подключенных к входам блока элементов И-ИЛИ 15, проходят на выход преобразователя кодов. Таким образом, на первой итерации значения адресов записи опреде 30 ляются фазой синхросигнала Т 1 (первый разряд) и значением разрядов счетчика 10. С выхода преобразователя 8 кодов код адреса через вход мультиплексора 9 (на входе 7 мульти- З 5 плексора 9 при операции БПФ постоянно высокий уровень)и вход мультиплексора 6 переписывается в регистр 7, а затем на выход устройства, При появлении на.выходе счетчика 1 кода "О010000", что соответствует значению Ю/2 = 16, на выходе мультиплексора 32 устанавливается высокий уровень, что соответствует сигналу окончания итерации, Этим сигналом через элемент И 19 триггер 19 устанавливается в состояние "0" и блокирует работу счетчика 1, устанавливая его в состояние "0". Одновременно через элемент И 26 снимается блокировка счетчика 29 и он начинает счет, начиная с состояния "0010. На выходе дешифратора начинается снова формирование сигналов ДШ 2 - ДШ 14.55 Припоявлении сигнала ДШ 6 триггер36 устанавливается в состояние "0" иблокирует работу счетчика 10. На этом заканчивается фаомиравание адресов записи операндов для первой итерации.Далее начинается подготовка устройства к формированию адресов для второй итерации. Сигналом ДШ 8 триггер 21 перебрасывается в противоположное состояние и производит перекоммутацию выходов мультиплексоров 2 и 9. Теперь, на второй итерации, адреса для считывания операндов появляются на втором выходе устройства (на регистре 7), а адреса для записи - на первом выходе устройства (на регистре 4).Сигналом ДШ 10 в счетчик 11 добачляется единица, и в нем устанавливается код 00 О", соответствующий второй итерации, одновременно этим же сигналом в счетчике устанавливается код, соответствующий значению И/2 = 16, а в регистре сдвига 16 устанавливается код "0001". Кроме того, сигналом ДШ О триггер 19 устанавливается в состояние "1", и разрешает работу счетчика 1 по входу "+1". Начинается формирование адресов считывание, которое происходит так же, как и на первой итерации. С задержкой, определяемой сдвигом между сигналами ДШ 10 и ДШ 14, сигналом ДШ 14 устанавливается в состояниетриггер 36 и начинает работать счетчик 1 О, формирующий вместе с преобразователем 8 кодов адреса записи. При этом на второй итерации на выходе дешифратора 12 состояние "1" устанавливается только на втором выходе. При этом на выход толька второго элемента блока элементов И-ИЛИ 15 передается синхросигнал Т 1, который определяет значение второго разряда адреса записи. Регистр 16 находится в состоянии "00011", поэтому на входе шестого элемента блока элементов И-ИЛИ 5 устанавливается значение "1" и первый разряд счетчика 10 поступает на выход первого элемента 15 и определяет значение первого разряда адреса записи.На входах остальных элементов бло- ка элементов И-ИЛИ 15 устанавливается уровень "0", и значения разрядов счетчика 10, подключенных к входу блока элементов И-ИЛИ 15, на выход не проходят. На инверсном выходе сдвигового регистра 16 устанавливается код "11100", поэтому разряды счетчика 10, подключенные к входамвсех элементов блока элементов И-ИЛИ15, начиная с третьего, проходят навыход преобразователя кодов. При этомвторой разряд счетчика поступает навыход третьего элемента, третий разряд - на выход четвертого элементаи т.д. Таким образом, на второй итерации первый разряд адреса записи определяется значением первого разряда 10счетчика 10. Второй разряд определяется значением синхросигнала Т 1. Третий и последующие разряды адреса записи определяются значением разрядовсчетчика 10, начиная с второго. На 15первом выходе формируется последовательность адресов для записи операндов. Далее процесс продолжаетсяаналогично описанному выше и формируются адреса считывания адресов последней итерации, что соответствуетзначению единицы на пятом выходе дешифратора 12 (при И = 32), на выходе мультиплексора 33 устанавливается высокий уровень. При появлении 25сигнала ДШ 7 через элемент 22 сбрасываются регистр 23 и триггер 20.Работа счетчика 29 по входу "+1" блокируется. Устройство находится в состоянии готовности к исполнению следующей команды,Рассмотрим работу устройства приформировании адресов для операциибезызбыточного алгоритма БПФ.Как известно, для выполнения операции безызбыточного алгоритма необходимо сформировать следующую последовательность адресов ,0 и Ии И, "2" и Ии т.д. Порядок адресов считывания и записи одинаков,Для выполнения этой операции внешнее устройство выставляет на второми третьем входе устройства код операции 10 и код размера обрабатываемого массива И (пусть И = 32 и емусоответствует код 001). При получении по первому входу сигнала "Пуск"триггер 20 устанавливается в состояние "1" и разрешает прохождение синхросигналов 13 на вход счетчика 29.50Дешифратор начинает вырабатывать сиг.налы, начиная с ДШ 7. Этим сигналом в регистре 27 фик - сируется код размера массива. Сигналом ДШ 8 через элемент И 35 устанавливаются в состояние "0" триггер 21, счетчики 5, 11 и 13 и регистр 16, По сигналу ДШ 9 в регистр 23 записывается код команды "10", соответствующий операции безызбыточного алгоритма БПФ. Сигналом ДШ О устанавливается в состояние "1" триггер 19 и начинает работать счетчик 17.Этим же сигналом в счетчиках 5 и 13 устанавливается код "0100000", соответствующий значению И = 32, что обеспечивается дешифратором 31 при коде команд "10". Начинается,формирование адресов считывания, причем первый адрес формируется на счетчике 1 в последовательности "0", , "2" и т.д, до И/2. Второй адрес считывания образуется на счетчике 5, который при этой операции работает по входу "1",.что определяется элементом 28, причем адреса формируются в последовательности И, И, Ии т.д. до И-И/2-1.Коммутация адресов на выходе устройства осуществляется аналогично операции БПФ.Адреса записи образуются на счетчиках 1 О и 13, причем преобразователь 8 коцов работает как на первой итерации алгоритма ВПФ, т.е, первый разряд совпадает со значением синхросигнала Т 1, а остальные разряды определяются значением разрядов счетчиков 10.Адреса записи начинают формироваться по сигналу ДШ 6, т,е. с такой же задержкой, как и при операции БПФ, Второй адрес записи формируется на счетчике 13, который работает аналогично счетчику 5, с учетом задержки. Сформированные адреса записи через мультиплексоры 9 и 6 поступают на вход регистра 7, а затем на второй выход устройства, При появлении на выходе счетчика 1 кода "010000", что соответствует значению И/2, на выходе мультиплексора 32 вырабатывается сигнал "Конец итерации", который через элемент 18 устанавливает триггер 19 в состояние "0", и работа счетчика 1 блокируется. Одновременно начинает работать счетчик 29, и с появлением сигнала ДШ 6 устанавливается в состояние "0" триггер 36 и блокируется работа счетчика 10. Далее сигналом ДШ 7 через элемент 22 устанавливается в состояние "0" регистр 23 и сбрасывается триггер 20, Выполнение операции заканчивается, и устройство будет находиться в состоянии ожидания следующей команды.Формула и з о б р е т е н и я Устройство для формирования адресов операндов процессора быстрогопреобразования Фурье, содержащее блок5управления, первый счетчик, счетчикитераций, информационный выход которого подключен к входу дешифратора,первый и второй регистры, выходы которых являются выходами соответственно адреса считывания и адреса записи устройства, о т л и ч а ю щ ее с я тем, что, с целью повышениябыстродействия, в него введен реверсивный счетчик, второй и третий счетчики, первый, второй, третий и четвертый мультиплексоры, сдвиговый регистр,блок элементов И-ИЛИ, первыйвыход блока управления подключен к 20управляющим входам первого и второгомультиплексоров, выходы которых подключены к информационным входам соответственно первого и второго регистров, второй выход блока управления подключен к входу обнуления первого счетчика, информационный выходкоторого подключен к первому информационному входу третьего мультиплексора и входу номера последнего элемента блока управления, третий выходкоторого подключен к счетным входампервого и второго счетчиков, первомувходу блока элементов И-ИЛИ и управляющему входу третьго мультиплексора,выход которого подключен к первым ин 35формационным входам первого и второгомультиплексоров, вторые информационные входы которых подключены к выходу четвертого мультиплексора, первый 40информационный вход которого подключен к выходу блока элементов И-ИЛИ,второй и третий входы которого подключены соответственно к прямому иинверсному выходам сдвигового регистра, четвертый выход блока управленияподключен к суммирующему входу реверсивного счетчика, вычитающий вход которого соединен со счетным входомтретьего счетчика, управляющим входом четвертого мультиплексора и под 50ключен к пятому выходу блока управления, шестой выход которого подключен к тактовому входу сдвигового регистра, счетному входу второго счетчика, входам синхронизации приемапервого и третьего счетчиков, информационные входы которых подключены кседьмому выходу блока управления,восьмой выход которого подключен к входам обнуления третьего счетчика, счетчика итераций, сдвигового регистра и реверсивного счетчика, информационный выход которого подключен к второму информационному входу третьего мультиплексора, девятый выход блока управления подключен к входу обнуления второго счетчика, информационный выход которого подключен к четвертому входу блока элементов И-ИЛИ, пятый вход которого соединен с входом номера последней итерации и подключен к выходу дещифратора, десятый выход блока управления подключен к тактовым входам первого и второго регистров, информационный выход третьего счетчика подключен к второму информационному входу четвертого мультиплексора, вход запуска, вход задания режима и вход задания размера преобразования блока управления являются соответственно входом запуска, входом задания режима и входом задания размера преобразования 1 устройства, причем блок управления содержит два регистра, два дешифратора, счетчик, два мультиплексора, четыре триггера, восемь элементов И, элемент ИЛИ и генератор тактовых импульсов, первый выход которого подключен к первым входам первого и второго элементов И, второй выход генератора тактовых импульсов подключен к первому входу первого дешифратора, первый вход которого подключен к К-входу первого триггера, Б- вход которого подключен к выходу третьего элемента И, первый вход которого подключен к выходу второго триггера, К-вход которого подключен к выходу четвертого элемента И, первыи вход которого подключен к третьему выходу генератора тактовых импульсов, второй выход первого дешифратора подключен к первому входу пятого элемента И, выход которого подключен к входу обнуления первого регистра и К-входу третьего триггера, выход которого подключен к первому входу шестого элемента И, выход которого подключен к счетному входу счетчика, информационный выход которого подключен к второму входу первого дешифратора, третий выход которого подключен к первому входу седьмого элемента И и тактовому входу четвертого триггера, К-вход которогоподключен к выходу седьмого элемента И, второй вход которого подключен к выходу младшего разряда первого регистра, выход второго разряда ко то рого подключ ен к в то рому входу в то,рого элемента И,первому входу второго дешифратора и первому входу элемента ИЛИ, второй вход которого подключен к выходу первого мультиплек сора, управляющий вход которого соединен с вторым входом второго дешиф - ратора, управляющим входом второго мультиплексора и подключен к выходу второго регистра, тактовый вход ко торого соединен с тактовым входом первого регистра и подключен к четвертому выходу первого дешифратора, пятый выход которого подключен к Я-входу второго триггера, шестой выход пер вого дешифратора подключен к второму входу третьего элемента И, выход второго мультиплексора подключен к второму входу четвертого элемента И, выход первого триггера подключен к первому входу восьмого элемента И, выход которого подключен к входу синхронизации приема счетчика, информа - ционный вход которого является. входом задания константы устройства, выход 30 элемента ИЛИ подключен к второму входу пятого элемента И, вторые входы шестого и восьмого элементов И подключены соответственно к третьему выходу генератора тактовых импульсов и выходу второго триггера, выход старшего разряда первого регистра подключен к второму входу первого элемента И, информационные входы первого и второго мультиплексоров, Я-вход третьего триггера, информационные входы первого и второго регистров являются соответственно входом номера последнего элемента, входом номера последней итерации, входом запуска, входом задания режима, входом задания размера преобразования блока управления, выходами с первого , по десятый которого являются соответственно выход четвертого триггера, первый выход генератора тактовых импульсов, выход второго триггера, выходы первых и второго элементов И, пятый выход первого дешифратора, выход второго дешифратора, выход седьмого элемента И, выход первого триггера и третий выход генератора тактовых импульсов.1444814 оставитель А. Баранов Техред А.Кравчук Корректор Г. Рещетни едактор М. Циткин аказ 6508/5 ираж 704 исное 13 жгород, уп ктная,ое предприятие,оизводственно-по ИИПИ Государственногоделам изобретений и Москва, Ж, Раушс митета СССРткрытийя наб д, 4/