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

Изобретение относится к автомати ке и вычислительной технике и предназначено для использования в аппарате при спектрально-корреляционном анализе сигналов. Известно устройство для быстрого преобразования Фурье, содержащее четыре сумматора., три множительных блока, два с мматора-вычитателя и четыре регистра результата , Недостатком такого устройства яв ляется большой объем оборудования, связанный о тем., что во время выпол нения операции умножения четыре оум матора и два cьnvuv aтopa вычитaтeля бездействуют, кроме того, устройотво ориентировано на выполнение только одного алгоритма прямого быстрого преобразозания Фурье, Наиболее близкИЛ техническим решением к изобретению является устройство для быстрого преобразова ния Фурье,, содержащее четыре входны регистра, два регистра вектора пово рота, коммутатор, четыре регистра , произведений, бло1с управления, коммутатор сомножителей, блок умножения и регистры слагаемых 2j „ Недостатком известного устройства является малое быстродействие. Цель изобретения - поньшение быстродействия устройства Поставленная цель достигается тем, что в устройство для быстрого преобразования Фурье, содержащее четыре входных регистра, парный сум матор, четыре регистра произведений два регистра вектора повороте;, icoM мутатор и блок управления,- причем входы регистров зактора псзорота являются входами действительной и г.шимой частей вектора поворота устройства, выходы регистров произведений подключены к первой группе информационных входов коммутатора, первый выход блока управления подклю чен к входам управления сдвигом регистров вектора поворота, второй выход блсха управления подключен к вхо дам уггравлэкия сдвигом входньтх per гистров, третий выход блока управления подключен к управляющек- у входу коммутаторе, введены второй, третий и четвертнй су Ф1аторы, причем первы виход KOMuViy та тора подключен к информационным входам первого и второго входных регистров, второй выход коммутатора подключен к информационным входам третьего и четвертого входных регкотров, выходы входньж регистров подключены к первым информационным входам соответс -у-с1л -тк сумматоров, выходы с1.ч 1Мс1торОй пс.пключены к инфор ;Мационныт.5 входам соответствующих ре1ИС7рОБ произведи;:-:;:/.; выходы регистров п.роивве,цй -:н1л го.дключень к вторым кнформационнга в:лс,пам соотретствуюш,их .1маторов , nocneaoBsiTenbrbTe вы ходы регистров вектора поворота подключены к соответствующим управляющим входам блока управления, четвертый выход блока управления подключен к входам задания режима сумматоров, пятый выход блока управления подключен к входам управления записью первого и третьего регистров произведений, шестой выход блока управления , подключен к входам управления записью второго и четвертого регистров произведений, вторая и третья группы информационных входов являются входами первого и второго комплексных оперондов устройства, третий и четвертый выходы коммутатора являются выходами комплексного результата устройства. Блок управления состоит из четырехразрядного регистра сдвига, трехразрядкого счетчика, двух элементов И и блока постоянной памяти, причем перв.ые входы элементов И подключены к тактовому входу устройства, выход первого элемента И подключен к управляющему входу регистра, сдвига, выход четвертого разряда регистра сдвига подключен к входу его первого разряда, выход третьего разряда регистра сдвига подключен к второму входу второго элемента И, выход второго элемента И подключен к входу счетчика, выход Переполнение счетчика подключен к второму входу первого элемента И, управляющие входы блока управления подключены к первой группе адресных входов блока постоянной памяти, разрядные выходы регистра сдвига подключены к второй группе адресных входов блока постоянной памяти, выходы блока постоянной ПЕСМЯТИ являются выходами блока управления. На фиг, 1 приведена функциональная схема устройства; на фиг. 2 схема блока управления. Устройство состоит из четырех входньхх. регистров 1-4, четырех сумматоров 5-8, четырех регистров 9-12 произведений, коммутатора 13, блока 14 управления, двух регистров 15 и 16 вектора поворота, причем два информаДИОННЫ5С входа 17 и 18 регистров вектора поворота и четыре информационных входа 19-22 коммутатора являются входами устройства, а два выхода 23 и 24 коммутатора являются выходами устройства. Блок управления состоит из элементов И 25 и 26, четырехразрядного регистра 27 сдвига, трехразрядного четчика 28 и блока 29 постоянной паяти , Устройство выполняет следующие операции (прореживание по частоте): ReA,M , + Ree, , , 1mA,, , ReB,, ,(ReД,-ReB,l-:),(rv,A,-:), 1, 3m6-,,OmW,(ReA,-Ree,VPeW, (lm,,) где A - первое входное комплексное ЧИСЛО; в; - второе входное комплексное число; W - вектор поворота. Устройство работает следующим образом, В исходном состоянии регистры 9 12 произведений обнулены. Коммутатор 13 направляет в регистры 1 и 2 величину Re А , а в регистры 3 и 4 величину 3т AJ. Суммируясь с нулевы содержимым регистров 9 - 12 на сумматорах 5-8, эти величины без изменения записываются в регистры 9 - 12. На этом первы{1 такт рабо ты устройства закончен. Коммутатор 13 направляет в регистры 1 и 2 входную величину RgB , а в- ре|гистры 3 и 4 входную величину IrnB, и на сумматорах 5-8 образуются следующие величины: на сумматоре 5 - (ReA +ReB;), на суммато ре б - (ReA,- ReB, ) , на сумматоре 7 - (mA, + ln,Bi ) , на сумматоре 8 - (IrrtAj-tlruB; ) , Величины с выходов сумматоров записываются в регистры 9 - 12. С выхода регистров 9 и 11 величины Re А,., и ТгиВ,, , равные соответственно ( ReA; + ReBj) и QmA;+TmB), через коммутатор 13 подаются на выходы 23 и 24 устройства соответственно. На этом второй такт работы устройства закончен Коммутатор слагаемых направляет величину с выхода регистра 10 в регистры 1 и 2, а. с. выхода регистра 12 в регистры 3 и 4, Регистры 9-12 обнуляются. На этом третий такт работы устройства закончен Затем блок управления начинает операцию умножения, одновременно фО1ЯИируя на регистрах 9-12 четыре величины: ReW; (ReA;-ReB;) , ( Re А;- ReB; ) ,tRe W, , ) ,tDm W; (3mA;-3t,B; ) . /множение длится на столько тактов , ,сколько разрядов регистров векторов (в наиболее распространен ном случае восемь разрядов). Частич ные произведения формируются путем сдвигов в регистрах 1 - 4 и записываются в регистры 9-12, если соот ветствующий разряд регистра вектора поворота равен единице. Коммутатор 13 направляет величины с выхода регистра 10 в регистр 3 а с выхода регистра 12 в регистр 1 Величины RP В, и ТтВ, с выходов сумматоров 5 и 7 записывается в регистры 9 .и 11, С выхода, регистров 9 и 11 величины Re В,, и через коммутатор 13 подаются на выходы 23 и 24 устройства соответственно. На этом последний такт работы устройства закончен. Блок 14 управления работает следующим образом. В исходном состоянии на вход регистра 27 сдвига подается логическая единица, счетчик 28 тактов умножения сброшен в нуль, на всех выходах блока 29 постоянной памяти логические нули и, следовательно, не иницируется ни одна микрооперация. Через элемент И 25 первый тактовый импульс поступает на вход сдвигов регистра 27, логическая единица появляется на выходе регистра Qj и из блока постоянной памяти вызывает код микроопераций, необходимых на первом такте работы устройства. Единица на входе регистра сбрасывается. Второй тактовый импульс сдвигает единицу из первого разряда регистра во второй, а в первый разряд принимается логический нуль с входа регистра и, таким образом, на всех выходах регистра за исключением выхода а2 присутствуют нули. Наличие логической единицы на выходе Q . вызывает выполнение микроопераций, необходимых на втором такте работы устройства. Третий тактовый импульс сдвигает единицу из второго разряда регистра 27 в третий разряд. Начинается выполнение умножения. В зави Симости от состояния ( или О) выходов блоков 15 и 16 на регистры 9-12 произведений либо подается сигнал записи, либо нет. Тактовые импульсы с 4-го по 10-й не изменяют состояние регистра 27, так как счетчик, начиная с третьего тактового импульса, блокирует прохождение тактовых импульсов на регистр 27. По этим тактовым импульсам происходит увеличение содержимого счетчика и сдвиги вправо во входных регистрах 1 - 4. На каждом из тактовых импульсов 4-10 в зависимости от состояния выходов регистров 15 и 16 происходит либо нет запись частичных Произведений в регистры 9-12, При достижении счетчиком 28 двоичного кода 000 (переполнение счетчика) вновь разрешается прохождение тактовых импульсов на регистр 27 и единичное состояние переходит из третьего разряда регистра в четвертый разряд. Наличие единицы на выходе Д регистра 27 вызывает выполнение микроопераций, необходимых на 11-м такте работы устройства. Последующие тактовые импульсы запускают сначала описанный процесс. Длительность всего цикла преобразования в предлагаемом устройстве

при наличии 8-разрядного умножения составляет 11 тактов вместо 34 тактов в известном устройстве, В случае применения в прототипе умножителя

на сдвигах и сложениях предлагаемое устройство обеспечивает примерно в три раза более высокое быстродействие при меньшем количестве оборудования.

1,. УСТРОЙСТВО ДЛЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее четыре входных регистра, первый сумматор. Четыре регистра произведений, два регистра вектора поворота, коммутатор и блок управления, причем входы регистров вектора поворота являются входами действительной и мнимой частей вектора поворота устройства, выходы регистров произведений подключены к первой группе информационных вхрдов коммутатора, первый выход блока управления подключен к входам управления сдвигом регистров вектора поворота, второй выход блока управления подключен к входам управления сдвигом входных регистров, третий выход блока управления подключен к управляющему входу коммутатора, отличающееся тем, что, с целью повышения быстродействия устройства, в него введены второй, третий и четвертый сумматоры, причем первый выход когимутатора подключен к информационным входам первого и второго входных регистров, второй выход коммутатора подключен к информационным входам третьего и четвертого входньк регистров, выходы входных регистров подключены к первым информационным входам соответствующих сумматоров, выходы сумматоров подключены к информационным входам соответствующих регистров произведений, выходы регистров произведений подключены к вторым информационным входам соответствующих сумматоров, последовательные выходы регистров вектора поворота подключены к соответствующим управляющим входам блока правления, четвертый выход блока управления подключен к входам задания режима сумматоров, пятый выход блока управления подключен к входам управления записью первого и третьего регистров произведений, шестой выход блока управления подключен к входам управления записью второго и четвертого регистров Произведений, вторая и третья группы информационных входов являются входами первого и вто(g рого комплексных опероидов устройст(Л ва, третий и четвертый выходы коммутатора являются выходами комплексного результата устройства. 2, Устройство по п. 1, отличающееся тем, что блок управления состоит из четырехразрядного регистра сдвига, трехразрядного счнтчика, двух элементов И и блока постоянной памяти, причем первые входы элементов И подключены к тактовому входу устррйства, выход первого эле мента И подключен к управляющему 00 входу регистра сдвига, выход четвертого разряда регистра сдвига подклю4; чен к входу его первого разряда, выоо ход третьего разряда регистра сдвига подключен к второму входу второго со элемента И, выход второго элемента И подключен к входу счетчика, выход Переполнение счетчика подключен к второму входу первого элемента И, управляющие входы блока управления подключены к первой группе адресных входов блока постоянной памяти, разрядные выходы регистра сдвига подключены к второй группе адресных входов блока постоянной памяти, выходы блока постоянной памяти являются выходами блока управления.