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

) С 06 Р 15/332 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР Е ИЗОБРЕТЕНИЯ А ВТОРСНОМУ СВИДЕТЕЛЬСТВ 4 Р 22УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БЫСТПРЕОБРАЗОВАШЬЧ ФУРЬЕИзобретение относится к вычисьной цифровой технике и можетиспользовано в системах цифро(54 РОГ (57 лителбыть вычислиИзобретение относится ктельной цифровой технике, предназначено для вычисления быстрого преобразования Фурье и может быть испольвано в системах цифровой обработксигналов.Целью изобретения является упрощение устройства за ижения аппаратурных затрат,На фиг, 1 - 8 изображена структурная схема устройства для вычислениябыстрого преобразования Фурье.Устройство (Фиг. 1 - 8) содержитинформационный вход 1, блок 2 буферной памяти, генератор 3 тактовых импульсов, счетчик (по модулю И) 4,блок 5 постоянной памяти, вторую общую инФормационную шину б, шину 7синхронизации, блок 8 постоянной памяти, первую группу вычислительных1 зои счет сн(56) АвторскоВ 1196894, клАвторскоеВ 1348815, кл вой обработки сигналов. Цель изобретения - упрощение устройства. Это достигается эа счет того, что в составустройства входят генератор тактовыхимпульсов, счетчик, четыре блока постоянной памяти, блок умножения, дваблока буферной памяти, две группыиз А (А - простое число) вычислительных блоков первого типа, каждый изкоторых содержит буферный регистр,регистр результата, сумматор и триггер, две группы из В (В - простоечисло, АхВ=М - размер преобразования)вычислительных блоков второго типа.Каждый из них содержит коммутатор,триггер, сумматор, две группы иэ Абуферных регистров. 8 ил. Ю блоков первого типа 9.р (р=,А), каж- Е дый из которых состоит из сумматора 10.р, регистра (результата) 11,р, р 1 буферного регистра 12.р, триггера 13.р, первую общую информационную шину 14, группу вычислительных блоков 15.р (р=1,В), каждый Оф 1 иэ которых состоит из триггера 1 б.р, коммутатора 17.р, группы буферных ре- ффффф гистров 18,р, 1 с %=1,А), сумматора 19,р, группь буферных регистров 20.р.1. 9=1,А), блок 21 постоянной памяти, блок 22 умножения, третью общую информационную шину 23, третью группу вычислительный блоков второго а типа 24.р (р=1,В),.каждый иэ которых состоит иэ триггера 25.р, коммутатора 26,р, группы буферных регистров 27.р.1 с В=1,А), сумматора 28,р, группы буферных регистров 29.р.1 (1;=1,А),1571611 Составитель А. БарановРедактор О.Спесивых Техред М,Дндык Корректор Э,Лончакова роиэводственно-иэдательский комбинат Патент , г. Ужг11 1 ул. Гагарина, 1 Заказ 1514 Тираж 572ЯИИПИ Государственного комитета по113035, Москва ЖПодписноебретениям и открытиям при ГКНТ ССаушская наб., д, 4/5четвертую общую информационную шину30, группу вычитательных блоков первого типа 31,р (р= 1,А), каждый из которых состоит из сумматора 32,р, реги стра (результата) 33,р, буферного регистра 34,р, триггера 35р, выходы36,р (рд 1,4) блока 5 постоянной памяти, двухразрядные выходы 37,р (р 1,2 х(А+В блока 8 постоянной памяти,блок 38 буферной памяти, информационный выход 39 всего устройства, блок 40постоянной памяти, выходы 40 - 41.р(р 12 В) блока постоянной памяти.Устройство вычисляет быстрое преоб разование Фурье по алгоритму Винограда с периодом в С отсчетов, где СдАххВ (А и В - простые числа).Рассмотрим работу устройства потактно. При описании работы устройст рва применены следующие сокращения:См - сумматор, Тр - триггер, Рг - регистр, ББП - блок буферной памяти,ПЗУ (пронумерованный выход) - блокпостоянной памяти, Ум - умножитель. 25Для конкретизации примем Ад 3, Вд 5, апериод преобразования будет равен 15,число Мд 18. С генератора поступаютпрямоугодьнЬе импульсы типа меандр,Будем полагать, что триггеры, регист- ЗОры во всех вычислительных элементахсрабатывают по переднему фронту синхросигнала (положительный перепад).Первые 15 тактов работы мы опускаемдля счета, поскольку за это времявходные отсчеты Х(р) (рд 1,15) в прямой последовательности поступают свхода 1 в ББП 2,. После этого следуюттри такта паузы, поскольку счетчик 4работает по модулю Мд 18. Со следующего такта входные отсчеты Х(р) в нужной нам последовательности поступаютв первую общую информационную шину.1 такт. ББП 25 Х(0),2 такт. ББП 2 дХ(5); Рг 12,1 дХ(0); 45ПЗУ 5 (36.1)="1"; См 10.1 ддХ(0),3 такт. ББП 2 дХ(10); ПЗУ 5 (36,)д"Ф";Рг 12. 1 дХ(0); См 10, 1 до;Тр 13.1 д"1"р Рг. 12,2=Х(5);См 10.2=Х(0)+Х(5); Рг 11.1 ддХ(0),4 такт. ББП 2 дХ(3); См 10, 1 дОрРг 12. 1 дХ(0) Рг 11. 1 до;Тр 13.1 д"0"; Рг 12.2 дХ(5)См 0.2 дх(5)р Рг 11.2 дХ(0)+(т(1 дХ(0)+Х(5)+Х(10. 6 такт, ББП 2 дХ(13); Рг 12. 1 дХ(3); Рг 11.1=Х(3); ПЗУ 5 (361)= д ОТр 131 д 1 е См 1 О1 дОУ рг 12.2 дХ(8); См 10,2=Х(3)+ +Х(8); Рг 11,2 дх(5) Рг 12.3=Х(10); См 10.3 дХ(5)-Х(10);Рг 11Зд(У(2)дх(5)+Х(10. 7 такт, ББП 2 дХ(6); Рг 12,1 дХ(3); Рг 11.1=0; См 10.дои Рг 12.2 д дХ(8)р См 10,2 дХ(8); Рг 1.2 д дХ(3)+Х(8); Тр 13.1 д"О"; Тр 132 д"1"1 Рг 12,3 дХ(13); См 1 О.З=Х(3)+Х(8)+Х(13)1 Рг 11.3 д(У(3)дХ(5)-Х(10). Дальше работа группы вычислительных блоков 9 продолжается по описанному алгоритму. Управляющие сигналы поступают на сумматоры вычислительных блоков 9 таким образом что на выходе первой группы получаем результат, равносильный умножению двух матриц (суммирование в скобках во второй матрице происходит по модулю 15); 1 1 1 Х(р) О1 х Х(р+5) 0 1 1 Х(р+10) где Х(р) - входные отсчеты сигнала, рд 0,3,6,9,12,Работу группы вычислительньгх блоков 15.р рассмотрим, начиная с 5-го такта. 5 такт. Рг 11.ЗдУ(1) (это значение и все последующие поступают на вторую общую информационную шину 6 для группы вычислительных блоков 15, поэтому в дальнейшем вместо знака Рг 11.3 будет 111 6, что означает "шина 6"); ПЗУ 5 (36.2)д"1"; (при "1" на управляющем входе коммутаторы 17.р группы 151571611 18 такт. У(р)У (р+1)У(р+2)У (р+3)Ъ (р+4)У(р+5) 0 0 0 0 1 1 0 1 -1 1 0 - 1 х 0 -1 1 1 О 1 - 1 - 1 1 0 1 1 1 1 1 1 1 1 19 такт,40 Дальше Йых блоко санному налы на ким обр получае ноже нию У(р)(р+гг(р+3У(р+4о 1 оо о о о о 1 о о о о о ычисления быстроурье, содержащее Устроиство длго преобразовани 19, 5 У(1)+У (4)+У (7)+У (10)++У(9)+У(12)+У(15).работа группы вычислительв 15,р продолжается по опиалгоритму. Управляющие сигсумматоры 19,р поступают таазом, что на выходе группы 15м результат, равносильный умматриц: где У(р) - значения, поступающие наобщую информационную шину6 (р=1,6,11).С информационного выхода вычислительного блока 15,5 значения поступают на вход блока 22 умножения, надругой вход которого приходят с 113 У21 значения весовых коэффициентов ипризнаков. После умножения в блоке 22умножения значения поступают в третьюобщую информационную шину 23,Группа вычислительных элементов24.р работает аналогично группе вычислительных блоков 15.р (р=1,5),Управляющие сигналы на сумматоры 28,рпоступают таким образом, что на выходе получаем значения, которые были быполучены при умножении двух матриц: где У(р) - значения, поступающие на третью общую информационную шину 23 (р=1,7,13). С информационного выхода вычислительного блока 24,5 значения поступают на четвертую общую информационную шину 30,Группа вычислительных блоков 31р (р=1 р 3) работает аналогично группе вычислительных блоков 9.р, для которой алгоритм описан вышеУправляющие сигналы поступают на сумматоры 32,р таким образом, что на выходе вычислительных блоков получаем значения, которые были бы получены при умножении двух матриц: 1 0 0 Х(1 с)1 1 х Х (1 с+1)1 1 -1 Х %+2) где ХЬ) - значения, поступающие на четвертую общую информационную шину 30 Й=1,4,7, 10,13), С информационного выхода 31 третьего вычислительного блока значения поступают на вход блока 38 буферной памяти, который на выход выдает значения в порядке поступления их на вход первого блока 2 буферной памяти,Формула изобретениягенератор тактовых импульсов и первую группу из А (А - простое число) вычислительных блоков первого типа, причем информационный выход -го (=1, А) вычислительного блока5 первого типа группы подключен к первому информационному входу (+1)-го вычислительного блока первого типа группы, первый вход синхронизации которого подключен к выходу синхронизации -го вычислительного бЛока первого типа группы, при этом вычислительный блок первого типа группы содержит сумматор, триггер, Регистр результата и буферный регистр, выход которого подключен к первому информационному входу сумматора, второй информационный вход которого является первым информационным входом вычисли тельного блока первого типа, вторым информационным входом которого является инФормационный вход буферного регистра, тактовый вход которого соединен с тактовым входом триггера и 25 является первым входом синхронизации вычислительога блока первого типа, вторым входом синхронизации которого является вход синхронизатора сумматора, выход которого подключен к инфар мационному входу регистра результата, выход которого является информационным выходом вычислительного блока первого типа, а т л и ч а ю щ е е с я тем, что, с целью упрацения, она са 35 держит счетчик, два блока буферной памяти, четыре блока постоянной памяти, блок умножения, вторую группу из Л вычислительных блоков первого типа, первую и вторую группы из В (Б - прасБ тое число; И=АхБ - размер преобразования) вычислительных блоков второго типа, причем информационный выход 3-го (3 =1, Б) вы шслительного блока второго типа группы подключен к первому информационному входу (3+ +1)-го вычислительного блока второго типа, первый вход синхронизации которого подключен к выходу синхронизации 3-го вычислительного блока второго типа группы, при этом выход генератора тактовых импульсов подключен к счетному входу счетчика, информационный выход которого подключен к адресным входам первого, второго, третьего и четвертого блоков постоянной памяти и первого и второго блоков буферной памяти, выходы с первой по четвертый первого блока постояннай памяти подключены к первым входамсинхронизации соответственно первоговычислительного блока первого типапервой группы, первых вычислительныхблоков второго типа первой и второйгрупп и первого вычислительного блока первого типа второй группы, К-й(К=1,Л) выход второго блока постоянной памяти подключен к второму входусинхронизации 1(-го вычислительногоблока первого типа первой группы,(1(+Л)"й н (К+А+А)-й выходы второгоблока постоянной памяти подключенык вторым входам синхронизации К-х вычислительных блоков второго типа соответственно первой и второй групп,а (К+А+2 В)-й выход второго блока постоянной памяти подключен к второмувходу сийхронизации 1(-го вычислительного блока первого типа второйгруппы, 1-й и (1+Б)-й (1=,Б)выходы третьего блока настоянай пагмяти подключены к третьим входам синхронизации 1-х вычислительных блоковвторого типа соответственно первойи второй групп, выход четвертого. блока постоянной памяти подключен к первому входу блока умножения, выход которого подключен к второму информационному входу (К-го вычислительногоблока второго типа второй группы, выход Б-го вычислительного блока второго типа которой подключен к: второмуинформационному входу 1-га вычислительного блока первого типа второйгруппы, выход Л-га вычислительногоблока первого типа которой подключен к информационному входу первогоблока буферной памяти, выход которого является информационным выходомустройства, информационным входомкоторого является информационный входвторого блока буферной памяти, выходкатарога подключен к второму информационному входу 1-го вычислительнагаблока первого типа первой группы,информационный выход Л-го вычислительного блока первого типа которойподключен к второму информационномувходу К-го вычислительного блока второго типа первой группы, информационный выход Б-го вычислительного блокавторого типа которой подключен к второму входу блока умножения, причемвычислительный блок второго типа группы содержит триггер, коммутатор,сумматор, первую, вторую группы из Лпоследовательно соединенных буферных571 брегистров, при этом выход коммутатора подключен к первому информационному. входу сумматора и информационному входу первого буферного регистра ,первой группы, выход А-го буферного регистра которой подключен к первому информационному входу коммутатора, управляющий вход которого соединен с тактовым входом триггера и является перзым входом синхронйзации вычислительного блока второй группы, первым информационным входом которого является второй информационный вход сумматора, выход которого подключен к информационному .входу первого буферного регистра второй группы, выход А-го 11 12буферного регистра которой является информационным выходом вйчислительного блока второго типа, вторым информационным входом, вторым и третьим входами синхронизации которого являются соответственно второй информационный вход коммутатора, вход синхронизации сумматора и установочный вход. триггера, при этом выход генератора тактовых импульсов подключен к входам синхронизации первого и второго блоков буферной памяти и тактовым входам буферных регистров вычислительных блоков первого и второго типов первой и второй групп.