Процессор быстрого преобразования фурье

(46) 30.08.86,(7 1) Киевский нический инсти ликой ОктябрьсБюл. У 32 рдена Ленут имениой социал а полите -летия В тической СР983. ОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ ТОРСКОМУ СВИДЕТЕЛЬС революции(56) Авторское свидетельство СС В 1092517, кл. С 06 Г 15/332, 1Авторское свидетельство СССР Н 1095188, кл. С 06 Р 15/332, 1983. (54) ПРОЦЕССОР БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ(57) Изобретение относится к вычислительной технике, предназначено для вычисления спектров сигналов по алгоритму быстрого преобразования фурье с выполнением контрольных функций и может быть использовано в анализаторах спектра, работающих в реальном масштабе времени, в геологии, медицине, радиолокации. Цель изобретения - повышение достоверности результатов вычислений. Поставленная цель достигается тем, что в состав процессора входят генератор тактовых импуль. сов, счетчик, счетчик итераций, формирователь адреса, дешифратор, два мультиплексора, блок буферной памяти, блок памяти, регистр адреса, арифметический блок, четыре регистра, два регистра результата, умножитель, сумматор, элемент ИЛИ, триггер, группарегистров, регистр коэффициента, блок постоянной памяти микрокоманд, блок постоянной памяти коэффициентов с соответствующими связями. 2 ил,1254506 50 1Изобретение относится к вычислительной технике, предназначено длявычисления спектров сигналов по алгоритму быстрого преобразования Фурье свыполнением контрольных функций и мо 5жет быть использовано в анализаторахспектра, работающих в реальном масштабе времени, в геологии, медицине,радиолокации.Цель изобретения - повышение дос- Отоверности результатов.На фиг. и 2 представлена структурная схема процессора быстрогопреобразования Фурье,Процессор содержит блок 1 вычисления скользящего спектра, состоящийиз блока 2 буферной памяти, мультиплексора 3, арифметического блока 4,блока 5 памяти и блока 6 синхронизации, выполненного в виде генератора 207 тактовых импульсов, счетчика 8,формирователя 9 адреса, мультиплексора 10, счетчика 11 итераций, дешифратора 12 и регистра 13 адреса, бло-.ки постоянной памяти микракаманд 2514,1 и коэффициентов 14.2, регистры15,1, 15.2, 16. 1, 16.2, 17 и 18,умножитель 19, выходы 201, 20.2,21, 22.1, 22.2, 23,1, 23.2, 24, 25 и26 блоков 14.1 и 14,2, сумматор 27, З 0группа регистров 28.1-28.п, элементИЛИ 29, триггер 30, выходы 31.1-31.п,32. 1-32.п и 33 блоков 14.1 и 14.2,регистр 34 коэффициента, тактовыйвход 35 регистра и вход 36 синхронизации.В устройстве 1 из исходного вектора Гм вычисляется вектор тсаэффициентав Фурье Г, . Алгоритм работы устройства 1 предполагает хранение вектора Г в блоке 2 в течение всеговремени вычисления вектора Р . Этопозволяет использовать Г для параллельного и независимого вычисления9контРольного вектоРа Мт, 2.-и элементт кфкоторого вычисляется по алгоритму ДПФ Ю; н-т 2 Чс .ш.=а И =, а (соя -- сБк:а2 п сЯ 2 П)и ф 1 Кгде 1 - весовой коэффициент.Сравнение соответствующих результатов вычисления коэффициентов ДПФ 55 в устройстве 1 с элементами вектора М 1 дает информацию о достоверностикполученных результатов. Рассмотрим работу устройства на примере вычисления контрольного вектора Мп = 1 тп , тп , тп , тп 1, если 111024.2 п 1 с ., 2 Г 1 стп =а (соя- 3 я 2.п)КК=О2 П 21 Ттп = а(соя- 21 с - 3 я 2.п 2 с);12 Л 211тп =.) а (сая31 с - 3 я 2.пЗтс)5 . К, К ЕФком-27 . . 2 Птп =, а (соя 4 с - 3 ятп4 с).4к 1 т Бк=О В исходном состоянии счетчик 8, счетчик 11 итераций, регистры 28.1- 28.п и триггер 30 находятся в нулевом состоянии. В соответствии с алгоритмом работы устройства 1 в каждом первом и втором тактах шага иэ блока 2 выполняется считывание .саатветственна элементов а и а вектаН 2 К К ра Г , Следовательно, в данный ма". мент из блока 2 па адресу 100 выполняется считывание операнда аМ 2 действительная Еа и мнимая Зпт части которого поступают соответственнана входы регистров 15.1, 15,2, 16,1и 16.2. Из блока 14.2 считываетсязначение сая О. 11 римем исходное состояние за первый такт первого шагарабаты устройства,Ва втором такте первого шага (состояние счетчика 8 тактов 0001) изблока 2 выполняется считывание а , аоиз блока 14.2 - значения сая О, посинхраимпульсу 35 в регистр 34 записывается сая О.В третьем такге первого шага (состояние счетчика 8 тактов 00 10) пасинхраимпульсу 20.1 положительнымперепадом выполняется прием Ее а, иЪп а, соответственно в регистры 15.1и 16.1, на управляющем входе 22,присутствует единичное значение, которое разрешает поступление Ве а, навход умножителя 19, в этом такте врегистр 34 па синхраимпульсу 35 выполняется запись значения соя О, которое затем поступает на вход умнажителя 19. Результат умножения Ее асая 0 проходит через сумматор 27 безизменения на входы регистров 28,128,п (на управляющем входе 33 - "0"),так как присутствующее на управляющем входе 31.1 единичное значениеразрешает прохождение на второй входсумматора 27 нулей, записанных в ре 3 1254гистре 28.1. Из блока 14,2 выполняется считывание значения з 1 п О,В четвертом такте первого шага(состояние счетчика 8 тактов 0011) по синхроимпульсу 32.1 выполняет-ся запись Ке а, соз О в регистр 28.1,по синхроимпульсу 35 в регистр 34записывается з 1 п О. Состояние управляющего входа 22.1 не изменяется, ив умножителе 19 вычисляется Ке.а,з 1 п О, которое проходит через сумматор 27 без именения на входы регистров 28. 1-28,п; на управляющем входе31.2 единичное значение (на остальных управляющих входах 31.1, 31,231,п - "0") разрешает прохождение навторой вход сумматора 27 нулей, записанных в регистре 28.2. Из блока 14.2считывается значение з 1 п О,В первом такте второго шага (состояние счетчика 8 тактов 00100)синхроимпульсом 32.2 выполняется запись Ке а, з 1 п 0 в регистр 28.2, Состояние управляющих входов 22. 1, 23. 1,23.2, 24 и 25 - "0", управляющего 25входа 23.1 - "1", в умножитель 19поступает значение 1 ш а состояниерегистра 34 подтверждается. В умножителе 19 вычисляется Лш а, зп 0 ипоступает на вход сумматора 27, навтором входе сумматора 27 присутствует операнд Ке и, соз О, так какна управляющем входе 31.1 - "1", навходах 31.2-31 - "0". На управляющемвходе 33 значение "1" обеспечиваетвычисление Ке а, соз 0 - 0 ш а, зп 0=35= Ке А,. Из блока 2 считываетсяа иэ блока 14.2 - значениесоз О.Во втором такте второго шага (сос 40тояние счетчика 8 тактов 00 101)синхроимпульсом 32.1 выполняетсязапись Ке А, в регистр 28., по синхроимпульсу 35 в регистр 34 записывается соз О, состояние управляющихсигналов 22.1, 23.1, 22.2, 24, 2545не уменьшается и в умножителе 19вычисляется 2 ш а, соз О, которое затем поступает на вход сумматора 27,на втором входе сумматора 27 присут 50ствует операнд Ке а, з 1 п О, так какна управляющем входе 31.2 - "1", навходах 31.1, 31.3-31.п - "0". На управляющем входе 33 значение "0" обеспечивает вычисление Ке а, зп 0 ++ 2 ш а, соз 0 = 1 ш А,. Из блока 2Ысчитывается а из блока 14.2 - эна 2чение соз -- 1 с Ь = 1).И 506 4В третьем такте второго шага (сос тояние счетчика 8 тактов 000110) синхроимпульсом 32,2 выполняется запись Хш А. в регистр 28.2, по синхроимпульсу 35 в регистр 34 записывает 2 Еся соз -- Е Ь = 1) по синхроимХпульсу 20.1 выполняется прием Ке а и Еш а, соответственно в регистры 15.1 и 16. 1, на управляющем входе 22.1 присутствует единичное значение, которое разрешает прохождение Ке а на вход умножителя 19. Результат"умножения Ке а созЬ = 1)й поступает на вход сумматора 27, на второй вход сумматора 27 поступает содержимое регистра 28,1 (на управляющем входе 3 1. 1 - " 1", на входах 31.2-31.п - "0"), В сумматоре 27 вы 2 И числяется Ке А,+ Ке д,соз - Е (на управляющем входе 33 - "0"), Из блока 14.2 считывается значение21 Езп- -Ь = 1).МВ четвертом, такте второго шага (состояние счетчика 8 тактов 00111) синхроимпульсом 32.1 выполня 2 П ется запись Ке А + Ке а созе Б Ь = 1) в регистр 28. 1, по синхроимпульсу 35 в регистр 34 записывается211зжЕ Ь = 1) . Состояние управХляющего входа 22.1 не изменяется, и в умножителе 19 вычисляется Ке а,2 11з 1 п -- Е Ь = 1) которое затемИУ,поступает на вход сумматора 27, на второй вход сумматора 27 поступает содержимое регистра 28.2 (на управляющем сходе 31.2 - "1", на управляющих входах 31.1, 31.3-31.п - "О"), В сумматоре 27 вычисляется 1 ш А, +23+ Ке а зхп -- к Ь = 1) (на управ 1 Яляющем входе 33 - "0"). Из блока 14.22 ЕГ считывается значение зп в в , 1 ЙИ1).Работа устройства в остальные Я/2 - 2 шаги аналогична описанной.В первом такте первого шага навторой итерации (состояние счетчика 8 тактов 000) синхроимпульсомМ 2.2 32.2 выполняется запись Еш А +ко1254 50 б боказывает, так как на управляющем входе регистров 15.2 и 1 б.2 присутствует значение "0"),В третьем такте второго шага (состояние счетчика 8 тактов 0010) синхроимпульсом 32.2 выполняется занг-пись 1 пг А, в регистр 28.2, по синК-дхроимпульсу 35 в регистр 34 записы 2 Пвается соя1 с (1 с = 11/2), единич" 32 П+ Ке А я 1 п1 с (1 с = И/2 - )юИ-Ив регистр 28.2, Состояние управляющих входов 22.1, 22.2, 23,2, 24, 25 "0"управляющего входа 23. 1 - " 1", в умножитель 19 поступает значение 1 щ аг,г, в регистр 34 записан2 тя 1 п1 с (1 с = И/2 - 1) и поступаетБна вход сумматора 27, на втором вхо де сумматора 27 присутствует операнд%12 2 ЙКеЛ +КеА соя- - 1 с (1 с к-оК г-1 И 20 ф.г ггР вычисление , Тпг Л + Тпг А =7 1 щ Л . 50к-о211М Из блока 14.2 считывается соя -- 1 с (1 с = Б/2). В регистры 15.2 и 1 б,2 синхроимпульсом 20.2 выполняется прием соответственно Ке а и 1 щ а55м г.(на первой ицтерации прием в регистры 15.2 и 1 б.2 может выполняться, но на работу устройства оп влияния не Б151), так как на управляющемвходе 3 1. 1 - " 1", на управляющих входах 31.2-31.п - "0". На управляющемвходе 33 значение обеспечиваетггг.гвычисление Ке Лк + Ке Л . . Изг 42-1к=облока 2 считывается а, , из блока14.2 - значение соя -- 1 с (1 с11 2 251)Во втором такте второго пгага второй итерации (состояние счетчика 8тактов 0001) синхроимпульсом 32. 130выполняется запись Ке Л, в регистрк:о128. 1, по синхроимпульсу 35 в регистр2 Г И34 записывается соя = 1 с (1 сИ 21). Состояние управляющих входов3522. 1, 23. 1, 22. 2, 24, 25 не изменяется, и в умножителе 19 вычисляется2 П ИТщ а соя " - 1 с (1 с = " - 1) и пос 240тупает на вход сумматора 27, на втором входе сумматора 27 присутствуетгг 2-г 2операнд) Тщ А + Ке аяп1 с,к=отак как на управляющем входе 31.245"1", на управляющих входах 31. 1,31.3-31,п - "0". На управляющемвходе 33 значение "0" обеспечивает ное значение на управляющем входе 22,2 разрешает прохождение в этом такте Ке а 1 на вход умножителя 19.2 ГРезультат Ке а соя -- 1 с (1 с =И/2)гг Ипоступает на вход сумматора 27, на второй вход сумматора 27 поступает содержимое регистра 28,1 и в суммамг. гторе 27 вычисляется 2 Ке А + Ке а211 =очг фИх соя1 с (1 с = 11/2) . Из блока 14.22 Т 1считывается значение я 1 п -- 1 с (1 сИ- И/2) .В четвертом такте работа устройства аналогична описанной для четвертых тактов первой итерации.Отличие в работе устройства на второй итерации состоит в приеме во втором такте каждого шага в регистры, 15 2 и 1 б.2 соответственг о операндовКе а и 1 щсгц и выдаче из них информ гк г+"мации на вход умножителя в третьемтакте.Таким образом, к концу выполнениявторой итерации в регистрах 28.1 и28,2 вычисляются значения действигггг т ель и ой 2 Ке Ли мнимой Е 1 п 1 А ч аск:о к:отей коэффициента Фурье щ , На третьей и четвертой итерациях аналоничным образом вычисляются действительная и мнимая части коэффициентаФурье пг, которые будут храниться врегистрах 28.3 и 28.4. На пятый ишестой - щ в регистрах 28.5 и 28.б,на седьмой и восьмой - щ в регистрах 28.7 и 28.8,Значения весовых коэффициентовдля вычисления и., щ , щ обеспечивает блок 14.2,На девятой итерации управляющиесигналы с шины 21 синхронизации непоступают.7На десятой и 1 ргерации работы устройства 1 выполняется сравнение коэффициентов т , т , т , т с анапогичными коэффициентами Г , Г , Г1 ф 2 ф Г , вычисленными по алгоритму БПФ в устройстве 1. Из .алгоритма работы устройства 1 следует, что Г, Г Г , Г получаются в третьих тактахФсоответственно шагов И/4, Ы/8, ЗИ/4, Б/6, т.е. Г получаем на 1024/16 - 64 шаге; Г - на 128 шаге; Г, - на 256 шаге; Г - на 384 шаге.Рассмотрим работу устройства на десятой итерации на 64, 128, 256 и 384 шагах. 1На 64 шаге в третьем такте на выходе арифметического блока 4 присутствует операнд Г , действительная и мнимая части которого по синхроимпульсу 26 записываются соответствен но в регистры 17 и 18, на управляющем входе 24 - " 1", в регистр 34 по синхроимпульсу 35 выполнена запись кода 111, поэтому значениеЕе Г проходит через умножитель 19 без из менений и поступает на вход сумматора 27. На второй вход сумматора 27 в этом такте поступает содержимое регистра 28.7 (на управляющем входе 32,7 - "1"), на управляющем входе ЗО 33 сумматора 27 присутствует код "1", выполняется операция вычитания, значение разрядов сумматора 27 поступает на схему ИЛИ 29, результат логического преобразования присутствует на входе триггера 30 ошибки. 40 45 50 В четвертом такте синхроимпульсом36 выполняется запись результатасравнения в триггер 30 ошибки. Еслитриггер не изменяет своего состояния, результат верен, если изменяет,в вычислениях произошла ошибка. Аналогичным образом;: четвертом тактевыполняется сравнение мнимых частейкоэффициентов Г и ш , записанных4соответственно в регйстры 18 и 28.8.В первом такте 65 шага результатсравнения может быть записан в триггер 30,Работа схемы на 128, 256 и 384шагах аналогична и отличается от описанной для 64 шага значениями управляющих сигналов, обеспечивающих выдачу соответственно из регистров28,3, 28.4, 28,1, 28.2, 28.5, 28.6.Таким образом за время двух итераций устройства можно вычислять одинэлемент контрольного вектора,1254506 Формула изобретения Процессор быстрого преобразованияФурье, содержащий генератор тактовыхимпульсов, выход которого подключен квходу формирователя адреса и счетному входу счетчика, выход переносакоторого подключен к счетному входусчетчика итераций, информационныйвыход которого подключен к входу де- Ошифратора и управляющему входу первого мультиплексора, выход которогоподключен к адресному входу блокапамяти, выход которого подключен кпервбму информационному входу второго 5мультиплексора, выход которого подключен к информационному входу арифметического блока, информационныйвыход арифметического, блока подключен к информационному входу блока Опамяти, второй информационный входвторого мультиплексора подключен квыходу блока буферной памяти, адресный вход которого подключен к выходу регистра адреса, информационныйвход которого подключен к выходуФормирователя адреса, а выход дешифратора подключен к управляющему входу второго мультиплексора, выходпервого разряда счетчика подключенк управляющим входам блока буфернойпамяти и блока памяти, выходы разрядов счетчика подключены к соответствующим информационным входам первого мультиплексора, информационныйвход блока буферной, памяти являетсяинформационным входом процессора,отличающийся тем, что,с целью повышения достоверности, внего введены четыре регистра, дварегистра результата, умножитель, сумматор, элемент ИЛИ, триггер, группарегистров, регистр коэффициента,блок постоянной памяти микрокоманд,блок постоянной памяти коэффициентов, выход блока буферной памятиподключен к информационным входампервого, второго, третьего и четвертого регистров, выходы которых подключены кпервому входу умножителя,выход которого подключен к первому входу сумматора, выход которого подключен к информационным входам регистров группы, выходы которых подключены к второму входу сумматора, выходы разрядов которого подключены к соответствующим входам элемента ИЛИ, выход которого подключен к уста новочному входу триггера, выход ко9второго является контрольным выходом процессора, информационные выходы счетчика и счетчика итераций подключены к адресным входам блока постоянной памяти микрокоманд и блока постоянной памяти коэффициентов, выход последнего подключен к информационному входу регистра коэффициента, выход которого подключен к второму входу умножителя, выход -го (х = 1,и) разряда блока постоянной памяти микрокоманд подключен к управ ляющему входу -го регистра группы, тактовый вход которого подключен к выходу ( + и) -го разряда блока постоянной памяти микрокоманд, выходы (2 п ь 1)-го, (2 п+2) - го, (2 п+3) -го,(2 п+ +4) -го, (2 п+5) -го и (2 п+6) -го разрядов блока постоянной памяти микро- команд подключены к управляющим входам соответственно первого, второго,125450 бтретьего,и четвертого регистров, первого и второго регистров результата,выходы (2 п + 7)- го, (2 п + 8) - го и(2 п + 9)-го разрядов блока постоянной памяти микрокоманд подключенык тактовым входам соответственно первого и второго регистров, третьего ичетвертого регистров, первого и второго регистров результата, выходы(2 п + 10)-го и (2 п + 11) -го разрядовблока постоянной памяти подключены квходам синхронизации соответственносумматора и триггера, информационныйвыход арифметического блока подключен к информационным входам первогои второго регистров результата, выходы которых подключены к первомувходу умножителя, а выход генераторатактовых импульсов подключен к тактовому входу регистра коэффициента1254 50 бСоставитель А,БарановРедактор А.Огар Техред И,Попович Корректор М.Максимишинец Заказ 4723/54 Тираж 671 Подписное ВНИИПИ Гасударственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб д. 4/5 Производственно-полиграфическое предприятие, г.ужгород, ул.Проектная, 4