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

О П И 1 А Н И Е ИЗОБРЕТЕН И Я 590750 Союз Советских Социалистических Республик(51) Ч Кт6 06 Г 15 явлено 03.10.75 (21) 2178656,2единением заявки М -с пр Государственныи комитет Савета Министров СССР по делам изобретенийи открытийл етень,хе 01,78 та опубликования описания 20.0.78 2) Авторы изобретен Серовайский А. Т. Лукьянов и(71) Заявитель азахский ордена Трудового Красного Знамени сударственный университет им. С. М, Кирова(54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ БЪСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ 2 Изооретение относится к области вычислительной техники и может быть использовано для решения задач гармонического анализа, а также при численном решении дифференциальных уравнений в частных производных на сеточных моделирующих устройствах,Известно устройство для реализации быстрого преобразования Фурье (БПФ) 1" 1, построенное с использованием регистров сдвига различной длины.Конструкция этого устройства сложна.Наиболее близким к изобретению по технической сущности и достигаемому положительному результату является устройство для реализации быстрого преобразования Фурье 21, содержащее блок хранения и преобразования информации и блок управления, причем первый, второй входы и выход блока хранения и преобразования информации соединены соответственно с первым, вторым выходами и входом блока управления.Блок хранения и преобразования информации в известном устройстве выполнен в виде узлов сложения и умножения на регистрах сдвига. В связи с тем, что в основе работы такого устройства лежит принцип последовательной обработки информации, недостаток его состоит в том, что оно обладает относительно низкой скоростью вычисления, а также достаточно слабой устойчивостью относительно малых начальных возмущений.Увеличение быстродействия в известном устройстве может быть достигнуто за счет использования параллельных секций, что ведет 5 к значительным конструктивным усложнениям и повышению стоимости устройства.Кроме того, цифровой способ обработки информации не позволяет использовать известное устройство непосредственно в качестве 10 процессоров для сеточных моделирующихустройств прп решении уравнений в частных производных, сужая тем самым функциональные возможности устройства,Цель изобретения - повышение быстро действия.Поставленная цель достигается тем, чтотретий и четвертый вьходы блока управления соединены с третьим и четвертым входами блока хранения и преобразования ин формации, а блок хранения и преобразования информации содержит узел входной памяти, узел выходной памяти, первый и второй аналоговые узлы преобразования Фурье, причем первый и второй выходы узла выходной памяти соединены с первыми входами соответственно первого и второго аналоговых узлов преобразования Фурье, вторые входы которых соединены со вторым входом блока, первый и второй входы зла выходной па О мяти соединены соответственно с первым входом блока и входом устройства, выход которого соединен с выходом узла выходной памяти, первые выходы первого п второго анало. говых узлов преобразования Фурье соединены соответственно с первым п вторым входа. мп узла входной памяти, третий и четвертый входы которого соединены соответственно с третьим и четвертым входами блока, а выход блока соединен со вторыми выходами первого и второго аналоговых узлов преобразоваппя Фурье,Поставленная цель достигается тем, что блок управления содержит арифметпко-логический узел, счетчик циклов, счетчик шагов, элемент Л, коммутатор и цифро-аналоговый преобразователь, причем первый и второп выходы арифметико-логического узла соединены соответственно со входом коммутатора и входом цифро-аналогового преобразователя, выходы которых соединены соответственно с первым и вторым выходами блока, первый, второй, третий выходы счетчика циклов соединены соответственно с третьим выходом блока, с первым входом арифметикологического узла и с первым входом элемен. та И, первый, второй, третий выходы счетчика шагов соединены соответственно с четвертым выходом блока, со вторым входом арифметико-логического узла п со входом счетчика циклов, второй вход и выход элемента И соединены соответственно со входом блока и входом счетчика шагов.На чертеже представлена блок-схема устройства.Устройство для реализации быстрого преобразования Фурье содержит блок 1 хранения и преобразования информации со входами 2 - 5, входом б, являющимся входом устройства. выходом 7, являющимся выходом устройства, выходом 8, а также блок 9 управления со входом 10 и выходами 11 - 14, причем блок хранения и преобразования информации содержит узел 15 входной памяти со входами 1 б - 19, узел 20 выходной памяти со входами 21 - 23 и выходами 24 - 2 б, первый узел 27 аналогового преобразователя Фурье со входами 28, 29 и выходами 30, 31, второй узел 32 аналогового преобразова.еля Фурье со входами 33, 34 и выходамп 35, Зб, а блок управления содержит арифметико-логический узел 37 со входами 38, 39 и выходами 40, 41, коммутатор 42, цифро-аналоговый прсобразователь 43, счетчик 44 циклов со входом 45 и выходами 4 б - ;48, счетчик 49 шагов со входом 50 и выходом 51 - ;53, элемент И 54 со входами 55, 5 б и выходом 57.Устройство работает следующим образом.Перед началом преобразования в блоке 9 управления задается размер преобразуемой информации (степень числа 2), через вход 6 устройства на вход 22 узла 20 выходной памяти записывается исходная информация.ПО спгналч начало работь информация о текущем шаге и цикле оыстрого ппеобразования Фурье из счетчиков 44 и 49 подается 5 о 15 20 25 зо 35 40 45 50 60 65 в узел 37, где формируются номера двух ячеек узла 20 выходной памяти, необходимых на данном шаге преобразования, а также аргументы тригонометрических функций в соответствии с алгоритмом быстрого преобразования Фурье. Информация о номерах ячеек с выхода 40 узла 37 через коммутатор 42 подается на вход 21 узла 20, в результате чего содержимое вызванных ячеек через выходы 24, 25 узла 20 подается на первый вход 28 узла 27 и на вход 33 узла 32, на входы 29, 34 соответственно узлов 27 и 32, через цифроаналоговый преобразователь 43 поступают аргументы тригонометрических функций. С выходов 30, 35 узлов 27, 32 информации, преобразованная в соответствии с алгоритмом быстрого преобразования Фурье, записывается по входам 1 б, 17 в первые ячейки регпсгров узла 15 входной памяти.С выходов 31, Зб узлов 27, 32 с выхода 8 блока 1 на вход 10 блока 9 подается сигнал обратной связи, который со входа 55 элемента И 54 подается на счетчик 49, увеличивая его содержимое на единицу. С выхода 51 счетчика 7 через выход 14 блока 9 и вход 5 блока 1 в узел 15 поступает сигнал, в результате чего ко входам 1 б, 17 узла 15 подключаются уже вторые ячейки его регистров (то есть осуществляется сдвиг регистров памяти), Начинается новый шаг быстрого поеобразования Фурье.В случае переполнения счетчика 49, означающего конец очередного цикла быстрого преобразования Фурье, происходит сброс счетчика 49, а сигнал переполнения с выхода 52 этого счетчика идет на вход 45 счетчика 44, увеличивая его содержимое на единицу, При этом с его выхода 4 б через выход 12. блока 9 на вход 4 блока 1 и на вход 18 узла 15,подается сигнал перезаписи, в результате чего информация из регистров узла 15 входной памяти переписывается по входу 23 узла 20 в выходную память. Начинается новый цикл быстрого преобразования Фурье.При переполнении счетчика 44, означающего конец быстрого преобразования Фурье, происходит сорос счетчика 44, а сигнал переполнения с его выхода 48 поступает нг вход Бб элемента И 54, в результате чего разрывается цепь обратной связи. Информация выводится из устройства.В связи с тем, что в данном устройстве проводится параллельная обработка информации, серьезно возрастает скорость вычисления. При этом существенное повышение быстродействия будет происходить на стадии вычисления трпгопометрических функций. Общее время вычисления в каждом конкретном случае определяется спецификой задачи и уменьшается в среднем в есколько раз по сравнению с использованием ЦВМ, Так как решающие элементы устройства - аналого- гого действия, то вычислительный процесс будет всегда устойчивым относительно малых возмущений. Кроме того, предлагаемое устройство можно использовать непосредственно (без вспомогательных элементов) в качестве приставки к счетным моделирующим устройствам при численном решении дифференциальных чравнений в частных производных.чФормула изобретенияУстройство для реализации быстрого преобразования Фурье, содержащее блок хранения и преобразования информации и блок управления, причем первый, второй входы и выход блока хранения и преобразования информации соединены соответственно с первым, вторым выходами и входом блока управления, отличающееся тем, что, с целью повышения быстродействия, третий и четвертый выходы блока управления соедиг иены с третьим и четвертым входами олока хранения и преобразования информации, а блок хранения и преобразования информации содержит узел входной памяти, узел выходной памяти, первый и второй аналоговые узлы преобразования Фурье, причем первый, второй выходы узла выходной памяти соединены с первыми входами соответственно первого и второго аналоговых узлов преобразования Фурье, вторые входы которых соединены со вторым входом блока, первый и второй ход узла выходной памяти соединены соответственно с первьц входом блока н входом устройства, выход которого соединен выходом узла выходной памяти, первые выходы первого и второго аналоговых узлов преобразования Фурье соединены соответственно с первым и вторым входами узла входной памяти, третий и четвертый входы кото- Р ого соединены соответственно с третьим игчетвертым входами блока, а выход олока 5 соединен со вторыми выходами первого ивторого аналоговых узлов, преобразования Фурье.2. Устройство по п. 1, от ли ч а ю ще ес ятем, что блок управления содержит арифмс тико-логический узел, счетчик циклов, счетчикшагов, элемент И, коммутатор и цифро-аналоговый преобразователь, причем первый и второй выходы арифметико-логического узла соединены соответственно со входом .коммунтатора и входом цифро-аналогового преооразователя, выходы которых соединены соответственно с первым и вторым выходами блока, первый, второй, третий выходы счетчика циклов соединены соответственно с третьим вы ходом блока, с первым входом арифметико.логического узла и с первым входом элемента И, первый, второй, третий выходы счетчика шагов соединены соответственно с четвертым выходом блока, со вторым входом ариф метико-логического узла и со входом счетчикациклов, второй вход и выход элемента И соединены соответственно со входом блока и входом счетчика шагов. З 0 Источники информации, принятые во внимание при экспертизе:1. Патент США М 37883258, кл. 340 в 1,5, 1974.2, Авторское свидетельство СССР 35382091, кл, 6 Об Г 15/34, 1971.590750 Составитель ф. ШагиахметовТехред А. Камышникова Корректов В. Гутман Редактор Р. Киселева 1 одписное Тип. Харьк. фил. пред. Патент Заказ 1011/2062 Изд.209 Тираж 818 НПО Государственного комитета Совета Министров СССР по делам изобретений и открытий Москва, Ж.35, Раушская наб., д. 4/5