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

ОП ИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Сею СоветсиикСоциалистмчасииараст 1 ублии щ 940168(22) Заявлено 02,01.80(21) 2863056/18-24 с присоединением. заявки И Ьвударстеае 6 кемтет СССР ае делам эобрете открытй(54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕИзобретение относится к вычислительной технике и предназначено длн цифровой обработки сигналов на основе алгораттма быстрого преобразования фурье (БПФ).Известны специализированные вычис 5лители для реализации БПФ, которые выполняются как однопроцессорные цифровые машины1,Указанные вычислители характеризуются наличием одного арифметического уст-ройства и последовательной пропедуройвыполнения вычислений, Быстродействиеэтш устройств низкое н ограничено ихпропускной способностью и временем выполнения одной базовой операции.15Наиболее близким по техническойсущности к предлагаемому является итеративный процессор, содержащий счетчикитераций, М/2 решающих блоков, каждый из которых содержит четыре регист ора, причем выходы действительной и мнимой частей первого результата 2 1 гои (2 1 + 1)-го решакацнх блоков ( 1ф 0 - М/4) подключены к входам дей 2:ствнтельной и мнимой частей соответственно первого и второго операндов 1 -го решающего блока, выходы действительной и мнимой частей второго результата 2 1- го и (2 1+ 1)-го решающих блоков подкшочены к входам действительной и мнимой частей соответственно первого и второго операндов ( 1 + М /4)-го решающего блока, входы действительной и мнимой частей первого и второго отсчетов ,О-го (,ст 0 - И/2 - 1) решающего блока являются 2 р-м и (2,О+ 1)-м информационными входами устройства2.В итеративном процессоре осуществляется параллельная обработка данных для реализации одной итерации алгоритма БПФ, количество которых равно 1 щ Й, где й - число входных отсчетов, что повышает быстродействие пропессора. В каждом решающем блоке выполняются арифметические операции над комплексными числами, Однако блоки являются сложными устройствами и содержат наборы регистров, сумматоров, логических3 94 схем, обеспечивающих выполнение арифметических операций.Цель изобретения - упрощение устрой- стваПоставленная цель достигается тем, что устройство для выполнения БПФ со-дерхат реккурентный регистр сдвига, два блока элементов И, блок элементов ИЛИ, два сумматора по модулю два, три элемента И, а в каждом решающем блоке - два селектора, четыре блока равно значности, четыре элемента И-ИЛИ, четыре счетчика, четыре элемента ИЛИ, четыре коммутатора, причем выходы разряДов реккурентного регистра сдвига подключены к входам первого и второ 1 о сумматоров по модулю два и к входам первого и второго блоков элементов И, выход первого блока элементов И подключен .к входу счетчика итераций и к входу блока элементов ИЛИ, прямой вы ход первого сумматора по модулю два подключен к первым входам первого и второго элементов И, инверсный выход первого сумматора по модулю два - к первому входу третьего элемента И, пря мой выход второго сумматора по модулю два подключен к вторым входам первого и третьего элементов И, а инверсный вы ход второго сумматора по модулю двак второму входу второго элемент И, выход счетчика Итераций подключен к уп" равляющим входам селекторов каждого решающего блока, а выход блока элементов ИЛИ - к информационным входам селекторов, первые входы первого и второго блоков равнозначности в каждом решающем блоке подцпочены к входу действительной части первого операнда решающего блока, первые входы третьего и четвертого блоков равнозначности подключены к входу мнимой части первого операнда решающего блока, вторые входы первого и четверто о блоков равнозначности подключены к выходу первого селектора, а вторые входы второго и третьего блоков равнозначности - к выходу второго селектора соответствующего решающего блока, выходы первого, второго и третьего элементов И подключены к первым входам первой, второй и третьей групп элементов И-ИЛИ всех решающих блоков, вход действительной части второго операнда в каждом решающем блоке подипочен к вторым входам первой группы первого и второго элементов И-ИЛИ, вход мнимой части второго операнда - к вторым входам первой группы третьего и четвертого элементов И-ИЛИ, прямой и 0168финверсный выходы первого блока равнозначности в каждом решающем блоке подключены к вторым входам второй группысоответственно первого и второго элемен тов И-ИЛИ, прямой и инверсный выходывторого блока равнозначности подключены к вторым входам второй группы соответственно третьего и четвертого элеме.,- тов И-ИЛИ, прямой и инверсный выход 1 о третьего блока равнозначности подключены к вторым входам третьей группы соответственно первого и второго элементовИ-ИЛИ, прямой и инверсный выходы четвертого блока равножачности подключены 1 з к вторым входам третьей группы соответственно третьего и четвертого элементовИ-ИЛИ, выходы элементов И-ИЛИ в каждом решающем блоке подключены к входам соответствующих счетчиков, выходы, го которых подключены к первым входамсоответствуюших элементов ИЛИ, вторыевходы первого и третьего элементов ИЛИявляются соответственно входом действительной и мнимой частей первого от счета, а вторые входы второго и четвертого элементов ИЛИ - соответственновходом действительной и мнимой частейвторого отсчета решающего блока, выходы элементов ИЛИ подключены к входам зо соответствующих регистров, выходы которых являются информационными выходами решающего блока и подключены кинформационным входам соответствующих коммутаторов, управляющие входы 35коммутаторов всех решающих блоковподключены к выходу второго блока элементов И, выходы первого и третьегокоммутаторов являются выходами действительной и мнимой частей первого ре зультата, а выходы второго и четвертого коммутаторов - выходами действительной и мнимой частей второго результата соответствукяцего решающего блока. На чертеже представлена блок-схема45, устройствае Устройство содержит реккурентный регистр 1 сдвига; два блока 2 и 3 элементов И, блок 4 элементов ИЛИ, два сумматора 5 и 6 по модулю два, три элемента И 7 - 9, счетчик 10 итераций, М/2 решающих блоков 11, каждый из которых содержит два селектора 12 и 13, четыре блока 14 - 17 равнозначности, четыре элемента И-ИЛИ 18-21, четыре счетчика 22-25, четыре элемента ИЛИ 26 - 29, четыре регистра 30- ЗЗ, четыре коммутатора 34 - 37,Р (таас М) р Выходы 40 и 41 действительной и мнимой частей первого и второго отсчетов,о -го (,0 0 -,П/2 - 1 решающего блока являются 2,О -м и 2 О+ 1-м 5 94.016Решающий блок 11 имеет две пары входов 38 и 39 и двс пары выходов 40 и 41 для связи с другими решающими блоками, две пары входов 42 и 43 для подключения источников комплексных от счетов, две пары выходов 44 и 45 для комплексных выходных отсчетов.Выходы 40 действительной и мнимой частей первого результата 2 1-го и (2 1 + 1)-го решающих блоков ( 4 - о = 0 - М/4) подключены к входам 38 и 39 действительной и мнимой частей соответственно первого и второго операндов -го решающего блока, выходы 41 действительной и мнимой частей второго 15 результата 2 1 -го и (2 1 + 1)-го решающих блоков подключены.к входам 38 и 39 действительной и мнимой частей соответственно первого и второго операндов ( 4 + Й/4)-го решающего блока, 2 оВыходы разрядов реккурентного регистра 1 сдвига подключены к входам блоков 2 и 3 элементов И, выход блока 2 элементов И .2 подключен к входу счетчика 10 итераций и к входу блока 4 элемен тов ИЛИ. Прямой выход сумматора 5 по модулю два подключен к первым входам элементов И 7 и 9, инверсный выход сумматора 5 по модулю два - к первому входу элемента И 8. Прямой выход зо сумматора 6 по модулю два подключен к вторым входам элементов И 7 и 8, а инверсный выход сумматора 6 по модуп два - к второму входу элемента И 9. Выход счетчика 10 итераций подклю-З 5 чен к управляюшим входам селекторов 12 и 13 каждого решающего блока, а выход блока 4 элементов ИЛИ - к информационным входам селекторов 12 и 13, Первые входы блоков 14 и. 17 равно-що значности в каждом решающем бпокеподключены к входу действительной части первого операнда Решающего блока, первые входы блоков 15 и 16 равнозначности подключены к входу мнимой части 45 ,первого операнда решающего блока, Вторые входы блоков 14 и 16 равнозначности подключены к вьцсоду селектора 12, а ,вторые входы блоков 15 и 17 равнозначности - к выходу селектора 13 соответствующего решающего блока. Выходы элементов И 7 - 9 подключены к первым входам первой, второй и третьей групп элементов И-ИЛИ 18 - 21 всех решаю- . ших блоков, вход действительной части второго операнда в каждом решающем блоке подключен к вторым входам первой группы элементов И-ИЛИ 18 и 20, вход мнимой части второго операнда - к вто 8 6рым входам первой группы элементовИ-ИЛИ 19 и 21. Прямой и инверсный .выходы первого блока 14 равнозначностиподключены к вторым входам второйгруппы соответственно элементов ИИЛИ 18 и 20, прямой и инверсный выходывторого блока 17 равнозначности йодключены к вторым входам второй группысоответственно элементов И-ИЛИ 19 н21, Прямой и инверсный выходы блока15 равнозначности подключены к вторымвходам третьей группы соответственноэлементов И-ИЛИ 18 и 20, прямой иинверсный выходы блока 16 равнозначности подключены к вторым входам третьей группы соответственно элементовИ-.ИЛИ 19 и 21. Выходы элементов ИИЛИ 18 - 21 в каждом решающем блокеподключены к входам соответствуюпихсчетчиков 22 - 25, выходы которыхподключены к первым входам соответствующих элементов ИЛИ 26 - 29,Вгорые входы элементов ИЛИ 26 и27 являются соответственно входом действительноФ и мнимой частей первого отсчета, а вторые входы элементов ИЛИ 28и 29 - соответственно входом действительной.и мнимой частей второго отсчета решающего блока. Выходы элементов ЕЛИ 26 - 29 пошцпочены к входамсоответствующих регистров 30 - 33,выходы которых являются информационными выходами решающего блока и подключены к информационным входам соответствующих коммутаторов 34 - 37.Управляющие входы коммутаторов 3437 всех решающих блоков подключены квыходу блока 3 элементов И, Выходыкоммутаторов 34 и 35 являются выходами действительной и мнимой частейпервого результата, а выходы коммутатор.ров 36 и 37 - выходами действительнойи мнимой частей второго результатасоответствующего решающего блока.В решающем блоке 11 реализуютсябазовые операции БПФ(4+4) (з) , р( )САфн(К ге Аг,оицгде й - число отсчетов;ДО 1 -й комплексный отсчет в ф-ойф итерапиьц, 7 9401информационными входами 38 и 39 ус;тройства,Б качестве реккурентного регистра 1сдвига в процессоре используется и -раз;рядный регистр сдвпга с линейной обратной связью, реализованной на сумматорах по модулю два.Регистр 1 сдвига, блок 3 элементовИ, коммутаторы 34 - 37, регистры 3033 образуют преобразователь двоичныхчисел Д"регистров в псевдослучайныеОпоследовательности,Регистр 1 сдипа, блок 2 элементовИ, селекторы 12 и 13, бпок 4 элементов ИЛИ образуют формирователь экспоненциальных коэффициентов БПФ Ф Р" .Регистр 1 сдвига, сумматоры 5 и 6по модулю два, элементы И 7 - 9 составляют формирователь несовпадаюшихпсевдослучайных последовательностей 20для представления весовых коэффщиентовпри реализации операции сложения с помошью элементов И-ИЛИ 18 - 21.Для обеспечения модуля коэффициентакорреляции порядка 2 на входах эломентов И-ИЛИ 18 - 21 входы сумматора 5 по модулю два подключены к выходам всех разрядов регистра 1 сдвига,а входы сумматора 6 по модулю дваподключены к нечетным выходам разря- ЗОдов регистра 1 сдвига. 0Блоки 14 - 17 равнозначности составляют умножит ели.Для обеспечения модуля коэффициентакорреляции порядка 2 -И последовательностей на входах блоков 14 - 17 равнозначности входы к-го элемента И 2( К + 1)-у и ( К -+ 1)-м инверснымвыходам разрядов регистра 1 сдвига 401, 2 К), авходы К-гоэлемента И 3 присоединены к ( и - К )-мпрямому и( Ю - К + 0 )-м инверснымвыходам разрядов регистра 1 сдвига,Счетчики . 22 - 25, число разрядов 45которых равно И, образуют преобразоватоли последовательностей в двоичныекоды. 3 и -разрядньцс регистрах 30 - 33хранятся двоичные коды. входных отсчетов или результаты вычислений в итерациях. По коду счетчика итераций 000решаюшие блоки 11 через входы 42 и43 подключаются к двум источникам входных комплексных цифровых отсчетов, номера которых определяются двоично-ин 55версной перестановкой кода порядковогономера М (М = О, 1 , 1 ч - 1) этихисточников без инверсии младшего разряда кода номера. Указанная схема соеди 68 8нений решающих блоков позволяет использовать регистры 30 - 33 для хранения,входных отсчетов и результатов вычис-лений в итерациях,Устройство работаег следующим образом.На выходах каждого разряда реккурентного регистра 1 генерируются псевдослучайные последовательности (М-последовательности), которые имеют периодй(2 - 1) тактов и математические ожидания, пропорциональные 1/2. Эти последовательности поступают на входы элементов И 2 и 3, на выходах которых образуются последовательности с периодоми2 - 1 тактов и математическим ожиданием, пропорциональным 2 (р = 2,и 1Последовательности с выходов элементов И 3 поступают на первые входы .коммутаторов 34 - 37, к вторым входам которых подключены выходы разрядов регистров 30 - 3;5. На выходе коммутаторов 34 - 37 формируются псевдослучайные последовательности, математическое ожидание которых пропорционально содержимому соответствующих регистров,Последовательности с выходов элементов И 2 поступают на входы элементов1 ИЛИ 4, на выходах которых формируютсяпоследовательности, математическое ожидание которых пропорционально значениМ-последовательности с выходов разрядов регистра 1 сдвига поступают навходы сумматоров 5 и 6 по модулю два,на выходах которых образуются М-последовательности, сдвинутые относительноразрядных последовательностей регистра1 сдвига. Эти последовательности поступают на входы элементов И 7 - 9.С помошью блоков 14 - 17 равнозначности выполнякгся операция умножения переменных, представленных псевдослучайными последовательностями, коэ ффициент взаимной корреляции которыхравен 2 и, Эти последовательности поступают на входы блоков 14 - 17 равнозначности с выходов селекторов 12 и13 и входов 38 решающего блока. Напервые входы И элементов И-ИЛИ 1821 поступают последовательности с выходов блоков 14 - 17 равнозначностии с входов 39 решающего блока, на вторые входы И - несовместные последователыости с выходов элементов И 7-9,Последовательности с выходов элементов И-ИЛИ 18 - 21 поступают в9 9401 М 10счетчики 22 - 25, в которых воспроиз- полнения БПФ сокращаются примерно в водится в двоичном коде результат ба- три раза по сравнению с известным.зовых вычислений в соответствии с (1).В устройстве за 6)д Й итерацийосуществляется параллельная обработка 5 Ф о р м у л а и з о б р е т е н и я М отсчетов по алгоритму (1. С помощью селекторов 12 и 13 и соответ- Устройство дпя выполнения быстрого ствии с кодом счетчика 10 итераций преобразования Фурье, содержащее счет выбираются требуемые дпя данной ите- чик нгервций, К/2 рещакапих блоков рации коэффщиенты Ф" 1 О ( й - порядок преобразованИя), каждЬйВ первой итерации производятся обра- из которых содержит четыре регистра, ботка входных отсчетов, которые зано- причем выходы действительной и мними мнимой сятся в регистры 30 - 33. В. последую- частей первого результата 2 4 -го и ших итерациях производится обработка (2 1 + 1)-го решаюших блоков ( ф результатов предыдуших итераций, 15 0 - Й/4) подключены к входам дейЗа время одной итерации, равное 2 -1 ствительной и мнимой частей соогветсттактов, комплексные отсчетыхраняшие- венно первого и второго операндов 1 -го , ся в регистрах 30-33, преобразуются решающего бпока, выходы действительв псевдослучайные последовательности, ной и мнимой частей второго результата которые через выходы 40 и 41 и входы 2 о 2 4 -го и (2 1 +1)-го решаюпшх блоков 38 и 39 решающих блоков поступают подключены к входам действительной и на входы блоков 14 - 17 равнозначнос- мнимой частей соответственно первого и ти и входы элементов И-ИЛИ 18 - 21. Второго операндов ( 1 + М /4(-го РешаюЕПЬНОЙ И МНИРезультат арифметических операций, шеГО блока р Входы действительной и выполняемых с помошью этих элементов, 25 мой частей первого и второго Отсчетов декодируется счетчиками 22 - 25 за,О -го ( ц = 0 - М/2 - 1) решаюш.его время итерацют, блока являются 2 р-м и (2,О + 1)-мВ момент окончания итерации двоич- информационными входами устройства, ный код счетчиков 22 - 25 через эле- о т л и ч а ю ш е е с я тем, что, с менты ИЛИ 26 - 29 переписывается в 50 целью упрощения устройства, Оно содержитегистры 30 - 33 и счетчики 22 - 25 реккурентный регистр сдвига, два блока Ре иустанавливаются в исходное состояние, элементов И, блок элементов, дв Сигналы переписи в регистры и установ- сумматора по модулю два, три элемента ки в исходные состояния счетчиков могут И, а в каждом решающем блоке - два себыть организованы, например, как коньюк- лектора, четыре блока равнозначности, цци импульса с выхода ( И)-ГО эле- четыре элемента И-ИЛИ, четыре счетчика, мента И 2 и прямого и инверсного им- четыре элемента ИЛИ, четыре коммутапульсов тактов. В последней итерации тора, причем выходы разрядов реккурентв регистрах формируются комплексные ного регистра сдвига подключены к вхоВыходны отсчеты Время Выполнения ал 4( дам, первого и второго сумматоров Горнтма БПФ модулю два и к входам первого и второго=Го блоков элементов И, выход первого 6 о=ГР Р -1)(2)ка элементов И подключен к входу счетгде Г - длительность тактовых импульсов. чика итераций и к дуй и к вхо элементов ИЛИ,Введение реккурентного регистра сди прямойервямой выход и ого суМматора по мога, групп элементов, суъыаторовпе вого и вто го элементов И., инверсный выход первого сумматора по модулю ных чисел в псевдослучайные последовательности, реализация решаюших блоков два - Р мУ Рва - к пе вому входу третьего элемента И, прямой выход второго сумматора устройства и схемы их соединений в соотпрПО МОглпПО ДВа ПОДКЛЮЧЕН К ВТОРЫМ ВХОДаМ ветствюи с изобретением позволяет исключить из решающих блоков сложные и Рв ГР Рпе о и третьего элементов И, а иннабоеги, сумматоров, логичес- версный выход второго сумматора по модупо два - к второму входу второго ких схем и, тем самым, существенноэлемента И, выход счетчика итераций упро у рростить ст й ство.подключен к управляюпшм входам селекторП инни одинаковой элемент- ров каждого решающего блока, а выходным входам сепекгоров, первые входы ение предлагаемого устройства для вы 11 9401 пс ртюго и второго блоков равнозначности в каждом решающем блоке подключены к входу действительной части первого операнда решающего блока, первые входы треть(чО и четвертого блоков раВно 5 значности подкл 10 чены к Входу мнимОЙ 1 асж первого операнда решсоошего блока, вторые входы первого и четвертого блоков равнозначнос 1% подключены к выходу первого селектора, а вторые входы 1 О второго и третьего блоков равнозначности - к выходу второго селектора соответствуюшего решаюшего блока, выходы первого, второго и третьего элементов И подключены к первым входам первой, второй и третьей групп элементов И-ИЛИ всех решаю 1 цих блоков, вход действительной части второго операнда в каждом решающем блоке подключен к вторым Входам и е 1 эВОЙ групшы перВого и ВтОрого д элементов И-ИЛИ, Вход мнимой части второго операнда - к вторым входам первой грутпы третьего и четвертого элементов И-ИЛИ, прямой и инверсный выходы первого блока равнозначности в . каждом решвюшем блоке подключены к вторым входам второй группы соответственно первого и второго элементов И-ИЛИ, прямой и инверсный выходы второго блока равнозначности подключены к вторым входам второй грутпы соответственно третьего и четвертого элементов И-ИЛИ, прямой и инверсный выходы треть его блока равнозначности подключены к вторым входам третьей грутпы соответ 35 ственно второго и первого элементов 68 12И-ИЛИ, прямой и инверсный выходь 1 четвертого блока равнозначности подключенык вторым входам третьей группы соответственно третьего и четвертого элементов И-ИЛИ, выходы элементов И-ИЛИв каждом решаюшем блоке подключенык входам соответствующих счетчиков,вьходь 1 которых подключены к первымвходам соответствующих элементов ИЛИ,вторые входы первого и третьего элементов ИЛИ являются соответственновходом действительной и мнимой частейпервого отсчета, а вторые входы второгои четвертого элементов ИЛИ - соответственно входом действительной и мнимойчастей второго отсчета решаюшего блжа,выходы элементов ИЛИ подключены квходам соответствуюцжх регистров, выходы которых являются информационнымивыходами решающего блока и подключенык информапионным входам соответствующих коммутаторов, управляюшие входыкоммутаторов всех решаюших блоковподключены к выходу второго блокаэлементов И, выходы первого и третьегокоммутаторов являются выходами действительной. и мнимой частей первого результата, а выходы второго и.четвертогокоммутаторов - выходами действительнойи мнимой часте 11 второго результатасоответствующего решаюшего блока.. Источники информации,принятые во внимание при экспертизе1. фЭлектроника", 1968, % 13, с. 3.2. "Зарубежная радиоэлектроника",1975, Мо 9, с. 87 (прототип),040 Ы 8 ектарМ. Кост Тираж 731 Подписное ПИ Государственного комитета СССР по делам юабретений и открытий 035, Москва, Ж 35, Раушская наб.) д.