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

СО 03 СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК А 1 332 5 )5 х.р ТЕТРЫТИ ГОСУДАРСТВЕННЫИ КОПО ИЗОБРЕТЕНИЯМ И ОПРИ ГКНТ СССР Н ОБР САНИ ДЕТЕЛ ЬСТВ ОРСКОМУны 4(71) Житомирский филиал Киевского политехнического института(56) Авторское свидетельство СССР М 1196894, кл. 6 06 Е 15/332, 1985,Авторское свидетельство СССР М 1474673, кл. 6 06 Г 15/332, 18.05.87.(54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к цифровой вычисли"ельной технике, предназначено для вычис ления быстрого преобразования Фурье и может быть использовано в системах цифровой обработки сигналов. Цель Изобретение относится к цифровой вычислительной технике, предназначено для вычисления быстрого преобразования Фурье, может быть использовано в системах цифровой обработки сигналов,Цель изобретения - упрощение устройства за счет снижения ап паратурных затрат.На фиг. 1-4 изображена структурная схема устройства для вычисления быстрого преобразования Фурье; на фиг, 5 - структурная схема умножителя,Устройство (фиг. 1 - 4) содержит информационный вход 1, генератор 2 тактовых импульсов, счетчик (по модулю М) 3, дешифратор 4, первый блок 5 постоянный памяти имЕЮщий двухрвврвдныв выходы 5.р (р=1, А+М 2) первый демультиплексор б, второй демультиплексор 7. вспомогательные вычислительные модули 8 и 9. первую группу 5 Ц 1644158 изобретения - упрощение устройства, Поавленная. цель достигается за счет того, что устройство имеет генератор тактовых импульсов, счетчик, дешифратор, блок постоянной памяти, два демультиплексора, два вспомогательных вычислительных модуля, две группы вычисли 1 ельных модулей. Каждый вычислительный модуль первой группы содержит два регистра, триггер, два буфферных регистра, сумматор. Первый вспомогательный вычислительный модуль содержит триггер, буферный регистр, сумматор и регистр, Каждый вычислительный модуль второй группы содержитдва регистра, триггер, два буферных регистра, два сумматора. Второй вспомогательный вычислительный модуль содержит сумматор, регистр, буферный регистр, триггер, блок постоянной памяти и умножитель, 5 ил,вычислительных модулей 10.р (р=1, А/2), каждый из которых состоит из(проходного) регистра 11.р, триггера 12.р, буферных регистров 13.2 р - 1 и 13.2 р, (промежуточного) сумматора 14,р, сумматора (результата) 15,р, регистра (результата) 16.р, вспомогательный вычислительный модуль 8 состоит из триггера 17, буферного регистра 18, сумматора 19. регистра (результата) 20; вторую гоуопу вычислительных модулей 21.р (р=1 М/2), каждый из которых состоит из (проходного) регистра 22.р, триггера 23,р. буферного регистра 24.р, буферного регистра 25,р. (промежуточного) сумматора 2 б,р. сумматора (результата) 27.р. регистра (результата) 28,р; входы задания режима 29 и 30. информационный выход 31, вспомогательный вычислительный модуль 9 состоит из сумматора 32, регистра (результата) 33, бу1644158 Ъферного регистра 34, триггера 35; шину 36 синхронизации; второй блок 37 постоянной памяти, умножитель 38.Умножитель 38 (фиг, 5) состоит из блока 39 умножения, входа для признака "7 40, 5 выхода 41 для действительной части комплексного числа, выхода 42 для мнимой части комплексного числа, первого коммутатора 43, второго коммутатора 44, входа 45 для значения весового коэффициента, входа 46 10 для мнимой части комплексного числа, входа 47 для действительной. части комплексного числа, блока 48 умножения.Все сумматоры и умножитель выполняют операции над комплексными числами, 15Устройство производит вычисление БПФ по алгоритму Винограда, который можно записать в следующем виде:у=Сх ВхАхХ,(1). где У - выходной вектор; 20А - матрица, элементы которой принадлежат множеству ( 1; 0; -1)В - диагональная матрица, элементы которой либо чисто действительные, либо чисто мнимые; 25С - матрица, элементы которой принадлежат подмножеству ( 1; 0: - 1Работа устройства на примере А=4, В этом случае выражение (1) примет следующую форму: ЗО. 001-1 Х(0 Х(1). Х(2) Х(3) 0010 10-1 иУ (О) У (1) У(2) У(3) группы модулей 10.р. Управляющие сигналы на сумматоры 26,1 и 27.М (=1, 2) поступают в соответствии с матрицей С.Если при другом значении числа А число35 М окажется больше числа А (это определяется алгоритмом Винограда), то в работепервой группы модулей делается пауза наопределенное количество тактов, определяемое разницей чисел М и А.40 Если число А (М) - нечетное, то на демультиплексор 6 (7) поступает управяющийлогический сигнал, который логическую и 1 ис дешифратора 4 подает на вход триггера 17(35) и запись первого значения происходит45 в буферный регистр 18 (34). Дальше работагрупп модулей происходит по описанномувыше алгоритму,Умножитель 38 работает следующим об 50 разом.С регистра 16.1 на вход 47 поступаетдействительная часть комплексного числа, ана вход 46 - мнимая часть комплексногочисла, на вход 45 приходит с ПЗУ 37 значе 55 ние весового коэффициента, Блоки умножения 48 и 39 производят операциюумножения и через коммутатор 43 действительная часть комплексного числа попадаетна выход 41, а мнимая часть через коммутатор 44 - на выход 42. Если необходимо значение, содержащееся в регистра 16,1,где)= 1/ - Т.Подобные разложения можно найти для различных А.Пусть триггеры 12,р, (23,1), проходные регистры 11,р (22,К), регистоы 16.р (28,1 29 и 33, результата, где (р=1, А/2; 1=1, М/2), срабатывают по переднему фронту синхросигнала (положительный перепад), а буфер ные Еегист ы 13,р (24.К 25;к), 18 и 34, где (р=1, А; 1 с=1, М 2) срабатывают по заднему фронту синхросигнала (отрицательный перепад). Входные отсчеты поступают на информационный вход 1.Рассмотрим работу первой группы моАупеи 10,р 1 р=Т, А)2) потактио. при описании работы применяются следующие сокращения: Рг - регистр, См - сумматор, Ум - умножитель, ПЗУ - блок постоянной памяти, Дш - дешифратор, Дм - демультиплексор, Тр - триггер, Вх - вход, Вых - выход,Первый такт, Вх 1=Х(0)Втерой такт. Вх 1=Х(1): Рг 11.1=Х(0):Дш 4=иОи Третий такт. Вх 1=Х(2):Рг 11.1=Х(1):Рг 11,2=Х(0):Дш 4=и 1";Рг 13,4=Х(0);Рг 13,3=Х(1):Дм 6=и 1 и (на втором выходе):См 14,2=Х(0)+Х(1); См 15,2=Х(0)+Х(1).Четвертый такт. Вх 1=Х(3):Дш 4=иО":Дм 6=иО";Тр 12,2=и 1";Рг 11,1=Х(2):Рг 13.4=Х(0);Рг 13.3=Х(1):См 14.2=Х(0)-Х(1):См 15,2=Х(0) - Х(1):Рг 13,2=Х(2):Рг 13.1=Х(3):См 14.1=Х(2)+Х(3): Рг 16,2=Х(0)+Х(1); См 15.1=Х(0)+Х(1)+Х(2)+Х(3),Пятый такт, Вх 1=Х 1(0) (индекс 1 значит отсчет следующего периода); регистры 13.1-13.4 сохраняют значения предыдущего такта, Дш 4=иО": Дм 6=иО";Тр=12,2=иО";См 14,2=Х(0): См 15,2=Х(0): См 14.1=Х(2)-Х(3);Рг 16.2=Х(0) - Х(1): См 15.1=Х(0) - ,Х(1)+Х(2) - Х(3): Р г 16,1=Х(0)+Х(1)+Х(2)+Х(3),Начиная с шестого такта, работа первой группы модулей происходит по описанному выше алгоритму. Управляющие сигналы на сумматоры 14.1, 14,2,15,1 и 15,2 поступают в соответствии с матрицей А.С выхода регистра 16,1 значения поступают на первый вход умножителя 38. на второй вход которого приходят значения с ПЗУ 37. С выхода умножителя 38 умноженные значения поступают на первый информационный вход модуля 21.1,Работа второй группы модулей 21,М(1=1, М/2) происходит аналогично работе первойумножить на), то с ИЗу 37 на вход 40 приходит соответствующий управляющий сигнал, и коммутаторы 43 и 44 меняют местами дей ствительную и мнимую части комплексного числа. Формула изобретения устройство для вычисления быстрого преобразования Фурье, содержащее первую группу из А/2 (А - целое число) вычислительных модулей, первый блок постоянной памяти, дешифратор, счетчик и генератор тактовых импульсов, выход которого подключен к первым тактовым входам всех вычислительных модулей первой группы и счетному входу счетчика, информационный выход которого подключен к адресному входу первого блока пос гоянной памяти и входу дешифратора, первый ин 10 15 формационный выход -го (=1, А/2 - 1) вы 20 числительного модуля первой группы подключен к первому информационному входу (+1)-го вычислительного модуля первой группы, второй информационный и тактовый выходы которого подключены соответственно к второму информационному и второму тактовому входам -го вычислительного модуля первой группы, при этом каждый вычислительный модуль содержит два регистра, триггер, два буферных регистра и два сумматора, выход первого регистра подключен к информационному входу первого буферного регистра и является первым информационным выходом вычислительного модуля, первым информационным входом ко торого являются соединенные между собой информационные входы второго буферного регистра и первого регистра, тактовый вход которого соединен с тактовым 30 35 40 входом второго регистра и подключен к первому тактовому входу вычислительного модуля, тактовым выходом которого является выход триггера, тактовый вход которого является вторым тактовым входом вычисли 45 тельного модуля, вторым информационным выходом которого является выход второго регистра, информационный вход которого подключен к выходу первого сумматора, первый и второй информационные входы 50 55 которого подключены соответственно к выходу второго сумматора и второму информационному входу вычислительного модуля, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, оно содержит два демультиплексора, умножитель, второй блок постоянной памяти, два вспомогательных вычислительных модуля и вторую группу из М/2 (М) - целое число) вычислительных модулей, причем выход генератора тактовых импульсов подключен к первым тактовым входам всех вычислительных модулей второй группы и первого и второго вспомогательных вычислительных модулей, первый и второй выходы дешифратора подключены к информацио ным входам соответственно первого и второго демультиплексоров, первьге выходы кото. рых подключены к вторым тактовым входам соответственно первого и второго вспомогательных вычислительных модулей, тактовые выходы которых соединены с вторыми входами соответсгвенно первого и второго демультиплексоров и подключены к вторым тактовым входам соответственно А/2-го вычислительного модуля первой гоуппы и М/2- го вычислительного модуля второй группы, первые информационные выходы которых подключены к информационным входам соответственно первого и вгорого вспомогагельных вычислительных модулей, информационные выходы ко 1 орых подключены к вторым информационным входам соответственно А/2-го вычислительного модуля первой группы и М/2-го вычислительного модуля второй группы, первый ингвормвцггонныг выход ггго (=Т, М 72 - 1) вычислительного модуля второй группы подключен к первому информационному входу Д 1)-го вычислительного модуля второй группы. второй информационный и тактовый выходы которого подключены соответственно к второму информационному и тактовому входам -го вычислительного модуля второй группы, выход первого вычислительного модуля первой группы подключен к первому входу умножителя, выход которого подключен к первому информационному входу первого вычислительного модуля второй группы, второй информационныи выход которого является информационньм выходом устройства, информационным входом котооого является первый информационныи вход первого вычислительного модуля первой группы, второй вход умножителя подключен к выходу первого блока постояннои памяти, информационный выход счетчика подключен к адресному входу второго блока постоянной памяти, 1-й (1=1, А/2) и (+А/2)-й.выходы которых подключены соответственно к третьему и четвертому тактовым входам-го вычислительного модуля первой группы, гпй (гп=А -1, А- М/2) и (гп+М/2)-й выходы второго блока постоянной памяти подключены соответственно к третьему и четвертому тактовым входам (гп - А)-го вычислительного модуля второй группы, (Ач М+1)-й и (А+М+2)-й выходы второгО блока постоянной памяти подключены к третьим тактовым входам соответственно первого и второго вспомога 1644158тельных вычислительных модулей, управляющие входы первого и второго демультиплексоров являются входом задания режима устройства, причем в каждом вычислительном модуле первый и второй информационные входы второго сумматора подключены к выходам соответственно первого и второго буферных регистров, тактовые входы которых подключены к второму тактовому входу вычислительного модуля, третьим и четвертым тактовыми входами которого являются входы синхронизации соответственно первого и второго сумматоров, при этом каждый вспомогательный вычислительный модуль содержит триггер, регистр, сумматор и буферный регистр, выход которого подключен к первому информационному входу сумматора, выход которого подключен к информационному входу регистра, выход и тактовый вход которого являются соответственно информационным выходом 5 и первым тактовым входом вспомогательного вычислительного модуля, информационным входом и тактовым выходом которого являются соответственно информационный вход буферного регистра и выход триггера, 10 тактовый вход которого соединен с тактовымвходом буферного регистра и подключен к второму тактовому входу вспомогательного вычислительного модуля, третьим тактовым . входом которого является вход синхрониза ции сумматора, второй информационныйвход которого является входом задания логического нуля устройства.1644158 Фиг,ь А.БаранМоргентал Редактор Е.Папп орректор Т, Колб Тираж 416твенного комитета 113035, Москва, Ж изводственно-издательский комбинат "Патент", г. Ужгород. ул,Гагарина, 10 аказ 1242 ВНИИПИ Государс Составит Техред М Подписноеизобретениям и открытиям при ГКН