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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК А 09) (11) зло С 06 Р 15/332 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРф вПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(71) Московский ордена ТрудовогоКрасного Знамени инженерно-физический институт(56) 1. Авторское свидетельство СССР . У 913392, кл. С 06 Р 15/332, 1980.2. Казанский А.В. Анализ структур и функциональных схем процессоров быстрого преобразования фурье. В сб.: "Вопросы проектирования и эксплуатации АСУ и управляющих вычислительных комплексов". М., Знергоиздат, 1982, с. 90 (прототип).(54)(57) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯБЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее два коммутатора, два арифметических блока, блок памяти и блок управления, состоящий из тактового генератора, счетчика .циклов, счетчикаитераций и двух дейифраторов, причемвыход тактового генератора в блокеуправления подключен к входу счетчика.циклов, выход переполнения счетчикациклов подключен к входу счетчикаитераций, информационные выходы счетчика циклов и счетчика инетарцийподключены соответственно к первыми вторым входам первого и второгодешифраторов, выход первого дешифратора в блоке управления является первым выходом блока управления и подключен к адресному входу блока памяти, первый и второй выходы второгодешифратора в блоке управления явля-,ются вторым и третьим выходами блока управления и подключены к управляющим входам первого и второго коммутаторов соответственно, информационный вход и выход блока памяти являются входом и выходом устройства, выход блока памяти подключен к информационному входу первого коммутатора, выход второго коммутатора подключен к информационному входу блока памяти, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства и повышения его быстродействия, первый арифметический блок содержит четыре входных регистра, два сумматора, дваИ вычитателя, два коммутатора и четыре выходных регистра, причем информационные входы всех входных регистров первого арифметического блока образуют его информационный вход и поцключены к первому выходу первогоЪф коммутатора, выход первого входного регистра в первом арифметическом блоке соединен с первым входом первого сумматора и с суммирующим входом первого вычитателя, выход второго входного регистра в первом арифметическом блоке соединен с первым входомвторого сумматора и суммирующим входом второго вычитателя, выход третьего входного регистра в первом арифметическом блоке соединен с вторымвходом первого сумматора и с вычитающим входом первого вычитателя, выход фьчетвертого входного регистра в первом арифметическом блоке соединенс вторым входом второго сумматораи с вычитающим входом второго вычитателя, выходы первого сумматора и первого вычитателя в первом арифметическом блоке соединены с соответствую124323 1 щими информационными входами первого коммутатора в этом блоке, выходы второго сумматора и второго вычитателя в первом арифметическом блоке соединены с соответствующими информационными. входами второго коммутатора в этом блоке, первый и второй выходы первого коммутатора в первом арифметическом блоке подключены к информационным входам первого и второго выходных регистров этого блока, первый и второй выходы второго коммутатора в первом арифметическом блоке, подключены к информационным входам третьего и четвертого выходных регистров этого блока, вьиоды всех выходных регистров первого арифмети-. ческого блока образуют его выход и подключены к первому информационному входу второго коммутатора, второй арифметический блок содержит четыре входных регистра, два сумматора, два вычитателя и четыре выходных регистра, причем информационные входы всех входных регистров второго арифметического блока образуют его информационный вход и подключены к второму выходу первого коммутатора, выход первого входного регистра во втором арифметическом блоке соединен с первым входом первого сумматора и суммирующим входом первого вычитателя, выход второго входного регистра во втором арифметичесхом блоке соединенс первым входом второго сумматора и с суммирующим входом второго вычитателя, выход третьего входного регистра во втором арифметическом блоке соединен с вторым входом второгосумматора и с вычитйющнм входом вто"рого вычитателя, выход четвертоговходного регистра во втором арифмети"ческом блоке соединен с вторым входомпервого сумматора и с вычитающнм входом первого вычитателя, выходы первого и второго сумматоров, а также первого и второго вычитателей во второмарифметическом блоке соединены с информационными входами соответствующих выходных регистров этого блока,выходы которьи образуют выход второго арифметического блока и подключенык второму информационному входу второго коммутатора, блок управлениясодержит элемент ИЛИ и элемент И,причем вьиод счетчика итераций вблоке управления поразрядно подключен к входам элемента ИЛИ, выход которого, а также выход тактового генератора подключены к входам элемента И, третий выход второго дешифратора является четвертым выходом блока управления и подключен к управляющим входам первого и второго коммутаторов в первом арифметическом блоке, выход тактового генератора является пятым выходом блока управленияи подключен к тактовым входам всехвходных и выходньи регистров в первом арифметическом блоке, выход элемента И является шестым вьиодом блока управления и подключен к тактовымвходам всех входных и выходных регистров во втором арифметическом блокеИзобретение относится к автоматике и вычислительной технике, в частности к цифровой обработке сигналов, и может быть использовано при проведении спектрального экспресс-анализа. 5Известно устройство для вычисления быстрого преобразования Фурье (БПФ), содержащее блок управления, арифметический блок, коммутаторы с соответ .твующими связями между бло О ками 11Данное устройство выполняет алгоритмы БПФ упрощенным методом, однако структура арифметического блока не учитывает специфических особенностей применяемых коэффициентов, что приводитк усложнению устройства.Наиболее близким к изобретению является устройство для вычисления ВПФ, содержащее два арифметических блока, блок памяти, блок управления и два коммутатора, причем первый и второй выходы первого коммутатора соединены с информационными входами соответственно первого и второго арифметических блоков, информацнон3 1124 ные выходы которых подключены соответственно к первому и второму входам второго коммутатора, выход которого соединен с информационным входом блока памяти, информационный выход которого подключен к входу первого коммутатора, первый выход блока управления подключен к адресному входу блока памяти, второй выход блока управления соединен с. тактовыми 10 входами арифметических блоков, третий и четвертый выходы блока управления соединены с управляющими входами соответственно первого и второго , коммутаторов, информационный вход и выход блока памяти является соответственно информационным входом и выходом устройства. Данное устройство также выполняет БПФ по упрощенному алгоритму 2 .20Однако арифметические блоки, хотя и учитывают специфические особенности коэффициентов применяемого упрощения алгоритма, выполнены по универсальной схеме, позволяющей осущест влять любую базовую операцию упрощенного алгоритма БПФ и поэтому имеют сложную структуру. Устройство выполняет упрощенный алгоритм с параметром Ю. =Я/4, но в ряде случаев может бытд допущена и более низкая методическая погрешность вычислений. Более того, применение эффективного по быстродействию сглаживания в частотной области результатов упрощенных алгоритмов БПФ позволяет значитель 35 но повысить методическую точность .вычисления спектра упрощенными методами и, тем самым, определяют рацио- нальность применения упрощенных алл 40 горитмов с параметром ж =и/2 (вместо 4=1/4) с учетом затрат аппаратуры и быстродействия.Цель изобретения - упрощение устройства и повышение его быстродейст Вия еПоставленная цель достигаетсятем, что в устройстве для вычисления БПФ, содержащем два коммутатора, два арифметических блока, блок памяти 50 и блок управления, еостоящий из тактового генератора, счетчика циклов, счетчика итераций и двух дешифраторов, причем выход тактового генератора в блоке управления подключена 55 к входу счетчика циклов, выход переполнения четчика циклов подключен к входу счетчика итераций, информа 323 4ционные выходы счетчика циклов и счетчика итераций подключены соответственно к первым и вторым входам первого и второго дешифраторов, выход первого дешифратора в блоке управления является первым выходом блока управления и подключен к адресному входу блока памяти, первый и второй выходы второго дешифратора в блоке управления являются вторым и третьим выходами блока управления и подключены к управляющим входам первого и второго кс;и"гаторов соответ-. ственно, информационный вход и выход блока памяти являются входом и выходом устройства, выход блока памяти подключен к информационному входу первого коммутатора, выход второго коммутатора подключен к информационному входу блока памяти, первый арифметический блок содержит четыре входных регистра, два сумматора, два вычитателя, два коммутатора и четыре выходных регистра, причем информационные входы всех входных регистров первого арифметического блока образуют его информационный. вход и подключены к первому выходу первого коммутатора, выход первого входного регистра в первом арифметическом блоке соединен с первым входом первого сумматора и с суммирующим входом первого вычитателя, выход второго входного регистра в первом арифметическом блоке соединен с первым входом второго сумматора и с суммирующимвходом второго вычитателя, выход третьего входного регистра в первом арифметическом блоке соединен с вторым входом первого сумматора и с вычитающим входом первого вычитателя, выход четвертого входного регистра в первом арифметическом блоке соединен с вторым входом второго сумматора и с вычитающим входом второго вычитателя, выходы первого сумматора и первого вычитателя в первом арифметическом блоке соединены ссоответствующими инфсрмационными входами первого коммутатора в этомблоке, выходы второго сумматора и второго вычитателя в первом арнфметическом блоке соединены.с соответствующими информационными входами второго коммутатора в этом блоке, первый и второй выходы первого коммутатора в первом арифметическом блоке подключены к информационным входам1124323 5первого и второго выходных регист" ров. этого блока, первый и второй выходы второго коммутатора в первом арифметическом блоке подключены к информационным входам третьего и чет вертого выходных регистров этого блока, выходы всех выходных,регистров первого арифметического блока образуют его.выход и подключены к первому информационному входу второ О го коммутатора, второй арифметический блок содержит четыре . входныхрегистра, два,сумматора, два вычитателя и четыре выходных регистра, причем информационные входы всех 15 входных регистров второго арифметического блока образуют его информа-. ционный вход и подключены к .второму выходу первого коммутатора, выход первого входного регистра во втором арифметическом блоке соединен с первым входом первого сумматора и суммирующим входом первого вычитателя, выход второго входного регистра во втором арифметическом блоке соединен с первым входом второго сумматора и с суммирующим входом второго вычита-. твля, выход третьего входного регистра во втором арифметическом блоке соединен с вторым входом второго сум-ЗО матора и с вычитающим входом второго вычитателя, выход четвертого входного регистра во втором арифметическом блоке соединен с вторым входом первого сумматора и с вычитающим входом 35 первого вычитателя, выходы первого и второго сумматоров, а также первого и второго вычитателей во втором арифметическом блоке соединены с ин-. формационными входами соответствую щих выходных регистров этого блока, выходы которых образуют выход второго арифметического блока и подключены к второму информационному входу второго коммутатора, блок управления . содержит элемент ИЛИ и элемент И, причем выход счетчика итераций в блоке управления поразрядно подключен к входам элемента ИЛИ, выход которого, а также выход тактового генератора подключены к входам элемента И, третий выход второго дешифратора является четвертым выходом блока управ-. ления и подключен к управляющим входам первого и второго коммутаторов 55 в первом арифметическом блоке, выход тактового генератора является пятым выходом блока управления и подключен к тактовым входам всех входных и выходных регистров в, первом арифметическом блоке, выходэлемента И является шестым выходом блока управленияи подключен к тактовым входам всехвходных и выходных регистров .во втором арифметическом блоке.На фиг. 1 - 4 представлены функциональные схемы предлагаемого устройства для вычисления быстрого преобразования Фурьеблока управления,,первого и второго арифтиметическихблоков соответственно.Устройство содержит коммутатор 1,арифметические блоки 2 и 3, коммутатор 4, блок 5 оперативной памяти,блок 6 управления.Блок 6 управления содержит такто.вый генератор 7, счетчик 8, циклов,счетчик 9 итераций, элемент ИЛИ 10,дешифратор 11 адреса памяти, дешиф"ратор 12 адреса коммутаторов, элемент И 13.,Арифметический блок 2 содержитвходные регистры 14 - 17, сумматоры18 и 19, вычитатели 20 и.21, коммутаторы 22 и 23, выходные регистры24 - 27.Арифметический блок 3 содержитвходные регистры 28 - 31, вычитатель32, сумматоры 33 и 34, вычитатель 35,выходные регистры 36 - 39.Счетчик 8 циклов блока 6 управления имеет разрядность в=1 о 8 Х, а счетчик итераций - ш=1 о 81 о 82 И, где Я - размерность вычисляемого быстрого преобразования Фурье. Поскольку предлагаемое устройство реализует алгоритмы с замещением, то адреса первого и второго коммутаторов 1 и 4 одинаковы на каждой базовой операции, поэтому соответствующие выходы блока управления можно объединить. Если же необходимо выполнять алгоритмы без замещения, то коммутаторы 1 и 4 адресуются по разным выходам блока управления, который в этом случае содержит не один, а два параллельно соединенных дешифраторов адреса коммутаторов.Устройство работает следующим образом.Реализуется упрощенный алгоритм БПФ с параметром а 6 =П/2 с замещением т 19 ,11 руются деюифраторами 11 и 32 адреса, которые определяют соответственно адреса операндов,в блоке 5 памяти и коммутаторов 1, 4 и 22, 23, Непосредственно с выхода генератора 7 блока 6 управления тактовые сигналы поступают на .тактовые входы входных и выходных регистров арифметического блока 2, синхронизируя прием и выдачу информации для этого блока. Если код счетчика 9 итераций нулевой, то на . выходе элемента ИЛИ присутствует уро"вень логического нуля, и тактовые импульсы не проходят иа тактовые входы входных и выходных регистров арифметического блока 3. Таким образом, арифметический блок 3 на начальной итерации не функционирует.1 24323 10Базовых итераций второго типа ровно столько, сколько базовых операций первого и третьего Фнпа вместе взятых. Значит арифметические блоки работают на.кахдой итерации без ожидания е Таким образом, предлагаемое выполнение устройства для вычисления 1 О БПФ позволит существенно упроститьконструкцию устройства (практическив 2-4 раза), поскольку вместо двухуниверсальных арифметических блоковиспользуются два разнотнпных, спе . циализированных аналогичных блока,или при равных с прототипом затратахоборудования в такое зе число разповысить быстродействие.гТираж 698осударственного коиитам изобретений и открМосква, Ж, Раушска ета СССРцтийя наб д