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

Союз Советскик Социалистических Республик(22) Заявлено 300678 (2 ) 2637956/18-24 с присоединением заявки М 6 06 Р 15/31 Государственный комитет СССР по делам изобретений н открытий(54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЬ.СТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ годключены к первым входам соответственно первого и второго сумматоров, выходы третьего и четвертого регистров - соответственно кпервому и второму входам третьегосумматора, выходы первого и второгоблоков сдвига - ко вторым входамсоответственно второго и первогосумматоров, выходы первого ,второго и третьего сумматоров подключены ко вхопам соответственно первого, второго и третьего регистров,выходы разрядов первого и второгорегистров подключены ко входамразрядов соответственно первого ивторого блоков сдвига, выходы блокапамяти подключены ко входам разрядов четвертого регистра, выходблока управления подключен к управляющим входам всех регистров иблоков сдвига, а также к адресномувходу блока памяти, содержит ариф"метико-логический блок, состоящийиз регистра сдвига, двух группсумматоров по модулю два, группыэлементов И и выходного элемента И,причем выход импульсов отсчетачисла итераций блока управления под;ключен,к управляющему входу регистра сдвига, выходы разрядов коИзобретение относится к области автоматики и вычислительной техники и может быть использовано в устройствах, реализующих дискретное преобразование Фурье.. 5Известно устройство для выполнения быстрого преобразования Фурье, содержащее регистры, сдвигатели и сумматоры 1).Наиболее близким техническим решением к предлагаемому изобретению является устройство для выполнениябыстрого преобразования Фурье (БПЬ), содержащее четыре регистра, два блока сдвига, три сумматора, блок 15постоянной памяти (ПЗУ), блок управления 2).Недостатком известных устройствявляется малое быстродействиеЦель изобретения - повышение 26 быстродействия устройства для выполнения быстрого преобразования Фурье.Поставленная цель достигается тем. что устройство для выполнения 25 быстрого преобразования Фурье, содержащее четыре регистра, два блока сдвига, блок памяти, три сумматора и блок управления, причем выходы первого и второго регистров 39 Ленинградский ордена Ленина электротехнический институт им. В.И.Ульянова (Ленина)где Н - число дискрет входного сигнала,А и В - комплексные числа, которые определяются на предыдущем шаге вычислений;В +ч .Вычисление значений Х, У осуществляется в соответствии со следующими рекуррентными соотношениями;а 1,.-Ф,"Ъ, 2;нМ,ь;.агс 1 ф )1=(,й П1 - номер итерации,и - разрядность входного слова. где торого подключены к первым входамсоответствующих элементов И группы,вторые и третьи входы которыхподключены к выходам соответствующих сумматоров .,по модулю два первой и второй групп, а выходы - ксоответствующим входам выходного:элемента И, выход которого подключенк управляющему входу блока управления, первые входы сумматоров по модулю два первой группы подключены квыходу знакового, а вторые входы - квыходам соответствующих информационных разрядов первого регистра, пер"вые входы сумматоров по модулю двавторой группы подключены к выходузнакового, а вторые входы - к выходам соответствующих информационныхразрядов второго регистра,На Фиг. 1 представлена функциональная схема устройства; на фиг,2функциональная схема арифметико-логического блока.Устройство содержит регистры 1-4,блоки 5,б сдвига, сумматоры 7-9,блок 10 памяти (ПЗУ), блок 11 управления, арифметико-логический блок 12,состоящий из сумматоров по модулю двапервойи второйгрупп, эле 4%ментов 3 И, выходного элемента 4И, регистра 5(1 сдвига.Блок 11 управления представляетиз себя счетчик, имеющий разрядность, соответствующую разрядностивходного слова устройства для выполнения БПф,и состоящий из двух.частей, в дальнейшем именуемыхсчетчиками итераций и шагов итераций.Вычисления в предлагаемом устройстве осуществляются в соответствиис выражениямиЮА = А+ Х В;(1)В =А - ХВ,х: еаза (-ЗютСн; Значения Х, у, 9 фиксируются врегистрах 1, 2 и 3, В блоке 10памяти хранятся константы Ь . Блоки5, б сдвига служат для умноженияна 2При обработке реального массивавхОдных данных может иметь местоследующее соотношение(4)О 3, Я ГНУ15гдеУ(0), Х(0) - знаковые РазРяды регистров .1п - вспомогательная функция;С - 4 о-;К (О о-ЯПоследняя Реализована при помощирегистра сдвига с начальной установкой Н= 2 и текущим содержимым Нфа,1 где 4 - номер итерации. З 0Устройство работает следующимобразом.По команде из блока управленияосуществляется занесение в регистр1 вещественной, в .Регистр 2 мни мой части числа В и в регистр 3числа 0=2 Л 01 М . При этом счетчик.блока 11 управления находится всостоянии 0. На вход счетчикав блоке 11 управления и управляющиевходы регистров 1 - 4 поступает однаи та же последовательность тактовыхимпульсов, формируемая в блоке 11управления. На управляющий входрегистра 5 1 сдвига АЛУ поступаютимпульсы со старшего разряда 45 счетчика шагов итераций. код снимаемый со счетчика итераций являетсякодом управления для блоков 5, бсдвига и адресом констант для ПЗУ.Далее устройство начинает работать 50 в соответствии с выражениями (2).Его работа заканчивается через иитераций. Если после итерации щ Сивыполняется условие (3), то выходнойсигнал АЛУ прерывает итерационный 55 процесс, разрешая обнуление счетчика блока 11 управления, Послеокончания итерационного процесса врегистры 1 и 2 производится записьновых входных данных и процедураповторяется.0 Необходимо отметить, что выражение(4) может быть положено в основуреализации АЛУ как для последовательного, так и для параллельногоустройства для выполнения БПФ, 65 реализующего алгоритм (2).Использование АЛУ позволяет повысить быстродействие устройства для выполнения БПФ приблизительно В два раза.Формула изобретенияУстройство для выполнения быстрого преобразования Фурье, содержащее четыре регистра, два блока сдвига, блок памяти, три сумматора и блок управления, причем выходы первого и второго регистров подключены к первым входам соответственно первого и второго сумматоров, выходы -гретьего и четвертого регистров соответственно к первому и второму входам третьего сумматора, выходы первого и второго блоков сдвига - ко вторым входам соответственно второго и первого сумматоров, выходы первого, второго и третьего сумматоров подключены ко входам соответственно первого, второго и третьего регистров, выходы разрядов первого и второго регистров подключены ко входам разрядов соответственно первого и второго блоков сдвига, выходы блока памяти подключены ко входам разрядов четвертого регистра, выход блока управления подключен к управляющим входам всех регистров и блоков сдвига, а также к адресному входу блока памяти, о т л и ч а ющ е е с я тем, что, с целью повышения быстродействия устройства, оносодержит арифметико-логическийблок, состоящий из регистра сдвига,двух групп сумматоров по модулю два,группы элементов И и выходного элемента И, причем выход импульсов отсчета числа итераций блока управленияподключен к управляющему входу регистра сдвига, выходы разрядовкоторого подключены к первым входамсоответствующих элементов И группы,вторые и третьи входы которых подключены к выходам соответствующихсумматоров по модулю два первой ивторой групп, а выходы - к соответ 15с тв ующим в ходам выходно го элементаИ, выход которого подключен к управляющему входу блока управления,первые входы сумматоров по модулюдва первой группы подключены квыходу знакового, а вторые входы - к20 выходам соответствующих инФорма"ционных разрядов первого регистра,первые входы сумматоров по модулюдва второй группы подключены к выходу знакового, а вторые входы - к25 выходам соответствуюших информационных разрядов второго регистра.Источники инФормации,принятые во внимание при экспертизе1. Патент ВеликобританииЗО Р 1350904, кл. С 06 Г 15/34 с 19692, РеяраЫ А,М. Гоцг 1 ег ТгапяйонпСощрцегя Ря 1 пд СОКР,7 С 7 г.ега 11 опя,ЮЕЕЕ Тгапя оп Сощрцегя, ч,с,И 10, 1974.752348 Рад Корректор Н. Григо одписное Заказ 4 а зС "ф; а Составитель В. БайкоЛ. Веселовская Техреду,Бабурка 747/8 Тираж ЦНИИПИ Государственного по делам изобретени 113035, Москва, Ж, Раф