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

(И) А 4 С 06 Р 15/3 ПИСАНИЕ ИЗОБРЕТВТОРСКОМУ СВИДЕТЕЛЬСТВУ отсчетов вх ную последо Цель изо ройства. На фиг. схема устрофров т бы диого си ательнос нала в часто о етени упрощение устпоказан ства; на н структурная иг. 2 - гра ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР(71) Институт теАН БССР(54)(57) УСТРОЙСТВО ДЛЯ БЫСТРОГО ДЕЙ СТВИТЕЛЬНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее синхронизатор, первый и второй выходы которого подключены к счетным входам соответственно первого и второго счетчиков адреса, информационные выходы которых подключены к адресным входам соответственно блока постоянной памяти и блока памяти, третий и четвертый выходы синхронизатора подключены соответственно к входу чтения блока постоянной памяти и входу чтения записи блока памяти, выход которого подключен к информационным входам первого и второго входных регистров и является информационным выходом устройства, выход блока пос-: тоянной памяти подключен к информационному входу регистра, тактовый вход которого подключен к пятому выходу синхронизатора, шестой и седьмой входы которого подключены к тактовым Бюл, У 8хнической кибернетики Изобретение относится к ци вычислительной технике и може использовано в системах и устр вах цифровой обработки информации в качестве преобразователей вр ной последовательности действи входам соответственно первого и второго входных регистров, умножитель и два сумматора, о т л и ч а ю щ е ес я тем, что, с целью .упрощения устройства, оно содержит первый, второй и третий мультиплексары, выходы которых подключены соответственно к первым входам первого и второго,сумматоров и информационному входу блока памяти; выход первргп.входного регистра подключен к вторым входам первого и второго сумматоров, выходы которых подключены соответственно к первому и второму информационным входам третьего мультиплексора, третий информационный вход которого является информационным входом устройства, вход Е второго входного регистра подклю к первым информационным входам первого и второго мультиплексоров и пе вому .входу умножителя, выход которого подключен к вторым информационным входам первого и второго мультиплексоров, управляющие входы которых рподключены соответственно к восьмомуи девятому выходам синхронизаторадесятыи выход которого подключен куправляющему входу третьего мульти-С 4плексора, а выход регистра подключенк второму входу умножителя.з 14 алгоритма быстрого преобразования Фурье.(БПФ), реализованный в устройстве; на фиг. 3 - временные диаграммы работы устройства.Устройство содержит синхронизатор1, счетчик 2 адреса, блок 3 постоянной памяти, счетчик 4 адреса, входной регистр 5, регистр 6, вхоцной регистр 7, блок 8 памяти, умножитель 9, первый 10 и второй 11 мультиплексоры, первый 12 и второй 13 сумматоры,тре-тий мультиплексор 14, информационные , вход 15 и выход 16.Граф алгоритма БПФ (фиг. 2) приве-. ден для исходного. массива длиной в16 значений. На фиг. 2 обозначены входная последовательность 17, выходная последовательность 18 коэффици" . ентов Фурье, операции 19, применяе:мые в алгоритме.Рассмотрим работу устройства.Вы; полнение БПФ в нем включает три эта: па: вход исходной информации, нычис" , ление коэффициентов Фурье и вывод результатов преобразования.На этапе ввода используются только синхронизатор 1, счетчик 4, блок 8 памяти и мультиплексор 14, По сигналам синхронизатора 1 счетчик 4 адреса формирует и передает на блок 8 памяти последовательность адресов, по которым в него записывается исходная информация, поступающая через мультиплексор 14 с входа 15.Этап вычисления коэффициентов Фурье включает несколько шагов. На первом шаге в соответствии с алгоритмом выполняются операции сложения и вычитания отсчетов. Синхронизатор 1 передает в счетчик 4 сигнал, по которому в последнем формируется и передается на блок 8 памяти код адреса первого операнда, представляющего собой некоторый -й входной отсчет (з. = О, 1 М/2 -1). Считанный из блока 8 памяти операнд фиксируется в первом входном регистре 5. С выхода последнего цифровой код поступает на входы первого 12 и второго 13 сумматоров. На счетчике 4 по сигналу синхронизатора 1 формируется код адреса второго операнда, являющегося (х + М/2)-м входным отсчетом. С выхода блока 8 оперативной памяти , значение операнда поступает на входной регистр 7 и фиксируется в нем, Отсюда цифровой код попадает на входы мультиплексоров 10 и 11. На управляющие входы последних с синхронизатора623544 51 О 15 40 45 50 55 20 25 ЗО 35 1 поступает сигнал, вызывающий передачу этой информации на входы первого 12 и второго 13 сумматоров. Сумматор 12 осуществляет сложение операндов, поступающих на его входы, а сумматор 13 - вычитание. второго операнда изпервого. С выходов сумматоров 12 и 13 результаты поступают соответственно на входы мультиплексора 14,По сигналам с синхронизатора 1 этиданные последовательно передаются в блок 8 памяти и фиксируются по адресам операндов, считанных из него в начале выполнения шага. Аналогичнымпутем происходит обработка остальных пар отсчетов на первом шаге алгоритма. Выполнение второго шага включаеттолько операции сложения-вычитанияи происходит в целом подобно первомушагу. Однако в данном случае инымиявляются коды адресов, задаваемые по командам синхронизатора 1 из счетчика 4 в блок 8 памяти (в данном случае из блока 8 памяти в соответствии с алгоритмом, так же, как и на преды" дущем шаге, выбираются такие парыоперандов, над которыми надо производить операции сложения и вычитания).Кроме того, на данном шаге присутствуют операнды, над которыми не требуется производить какие-либо преобразования (с номерами Н/2 и ЗИ/4).Эти отсчеты не считываются из блока8 и не подвергаются обработке. Третий и последующий шаги алгоритма содержат операции не только сложения-вычитания, но и умножения на тригонометрические весовые коэффициенты. Третий шаг включают два подшага. Выполнение первого из них, содержащего только операции сложениявычитания, в целом подобно отработке первого и второго шага преобразования. Функционирование устройства навтором подшаге происходит следующимобразом. По сигналам с синхронизатора 1 счетчик 4 последовательноформирует коды адресов, по которымиз блока 8 памяти считывается очередная пара операндов, которая записывается во входные регистры 5 и 7(считываемые операнды А и В выбираются такими, над которыми должна бытьвыполнена пара операций вида А+СВ иА-СВ, где С - весовой коэффициент;для представленного на фиг. 2 алгоритма при Б16 это отсчеты с но1462354 5мерами 8 и 10, 9 и 11, 12 и 14, 13 и 15). Одновременно по сигналу из . синхронизатора счетчик 2 адреса формирует и передает на блок 3 постоянной памяти код адреса, по которому из него считывается и фиксируется в регистре 6 значение соответствующего весового коэффициента (в том случае, когда по алгоритму требуется умножение на удвоенный весовой коэффициент, такое удвоенное значение и хранится в блоке 3 постоянной памяти). С выхода регистра 6 код коэффициента передается на вход первого сомножителя умножителя 9, на вход второго сомножителя которого с выхода регистра 7 поступает значение второго операнда. Результаты умножения через мультиплексоры 10 и 11, управляемые синхронизатором 1, поступают на вторые входы сумматоров 12 и 13, на первые входы которых подается код операнда с выхода первого входного регистра 5. В сумматоре 12 .происходит сложение, а в сумматоре 13 - вычитание операндов. Результаты из сумматоров 12 и 13 через мультиплексор 14 передаются в блок 8 оперативной памяти и фиксируются в нем. Аналогично выполняется обработка и остапьных пар операндов. На этом заканчивается отработка устройства третьего шага алгоритма. 6Последующие шаги вплотьдо (и)-гоподобны третьему шагу алгоритма ивыполняются в целом аналогично описанному (но с другими значениями весовых коэффициентов и операндов). Последний, и-й шаг алгоритма содержит операции сложения-вычитания и сложения-вычитания с умножением. Первые выполняются аналогично отработке таких операций на первом шаге, а вторые - на третьем шаге. После окончания и-го шага преобразования, являющегося последним на этапе вычисления коэффициентов фурье в блоке 8 оперативной памяти получают набор искомых значений, порядок следования которых отличается от нормального вследствие специфики алгоритма. Выдача результатов и восстановление требуемого порядка следования 2 б выходных отсчетов осуществляются наэтапе вывода. Здесь счетчик по сигналам с синхронизатора 1 формируеткоды адресов в порядке, обеспечивающем считывание из блока 8 и выдачу ЗО на выход коэффициентов действительного преобразования фурье в нормаль"ной последовательности, т.е. а,аф ф йр Ь,е Ьм(Й-1462354 Пр 2 ранов Составитель А.Редактор А. Огар Техред Л. Олийнык С. Чер рре Тирах 667внного комитета но изобретениям и 13035, Москва, Ж"35, Раушская наб Заказ 715/49НИИПИ Государ ГКНТ СССР нт", г. Ужгород, ул. Гагарина,101 ъский нат Производственно-и Р ЭЮ+ь -.Эс а, а Оу фэ Ьу дписноеткрытиям д 4/5