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

ОЮЗ СОВЕ у С 06 Р 15/332 ЕН 1 Ю;:.щ ров ГОСУДАРСТВЕННЫЙ КОМИТЕТ ССС ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬ ПИСАНИЕ ИЗОБР АВТОРСКОМУ СВИДЕТЕЛЬСТ(71) Куйбышевский институт инженежелезнодорожного транспорта(56) 1. Патент США У 3746848,кл, С 06 Р 7/38 ф 1972.2. Рабинер Л., Гоулд Б. Теорияи применение цифровой обработкисигналов. М., иМкр", 1978, с. 407(54) (57) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее блоки преобразования первого рода и суммирующие блоки, сгруппированныеив п ярусах (2 -размерность преобразования Фурье), каждый из блоков преобразования первого рода и сумми-. рующих блоков Р-го ( = 0,1, ,6-1)ияруса имеет 2 входов и 2" "выхоидов, а 2 входы блока преобразования первого рода первого яруса являются входами устройства и соединены с одноименными входами суммирующего блока первого яруса, выходы всех блоков (и)-го яруса являются выходами устройства, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, введены блоки преобразования второго рода, причем на 2-м ярусе содержится один блок преобразования первого рода, р.Е суммирующих блоков (П.Е =2 мЕ 2+ ме 1- 1, Р-г = 1/2, А.Е = 1)-11е 1 и кблоков преобразования второго рода, каждый суммирующий блок 3-о яруса содержит две группы по 2 сумматоров причем входы 1-го (1и-Е-М1 - 2 ) сумматора первой группы являются входами действительных составляющих по 1-му и (2 и+ 1)-му входам соответствующего суммирующего блока, входы д-го сумматора второй группы являются входами мнимых составляющих по -му и (2"" + 1)-му входам соответствующего суммирующего блока, выходы -х сумматоров первой и второй групп являются выходами действительной и мнимой составляющих по д-му выходу соответствующего суммирующего блока, каждый блок преобразования первого рода 6-го яруса содержит 2 сумматоров, три групи- - 1и-епы по 2 вычитателей и четыреи-егруппы по 2 элементов взвешивания, причем суммирующие входы -хО вычитателей первой и второй групп являются соответственно входами действитсльной и мнимой составляющих (фф по 1-му входу соответствующего блока преобразования первого рода, вы- р ,читающие входы -х вычитателей первой и второй групп являются соответственно входами действительной и мнимой осоставляющих по (2" + 1)-му00 входу соответствующего блока преобразования первого рода, выход 1-го вычитателя первой группы через 1-йэлемент взвешивания первой группы и через фф 1-й элемент взвешивания второй грунпы подключен соответственно к первому входу 1-го сумматора и суммирующему входу -го вычитателя третьей группы в соответствующем блоке пре- фр образования первого рода, выход д-го вычитателя второй .группы через 1-й элемент взвешивания третьей группы и через -й элемент взвешивания четвертой группы подключен соответственно к вычитающему входу 1-го вычитателя третьей группы и к второмувходу 1-го сумматора в соответствующем блоке преобразования первого рода, выход -го сумматора и выход 1-го вычитателя третьей группы являются выходами действительной и мнимой составляющих по 1-Му выходу соответствующего блока преобразования первого рода, каждый из блоков преобразования второго рода У-го яруса имеет две группы по 2 выходов и сои-Е держит две группы по 2 сумматоИ-Е - 1ров, четыре группы по 2 вычнтаи-Е телей и четыре группы по 2 элементов взвешивания, причем суммирующие входы -х вычитателей первой и второй групп являются соответственно входами действительной и мнимой составляющих по -му входу соответствующего блока преобразования второго рода, вычитающие входы -х вычитателей первой и второй групп являются соответственно входами действительИ-Еной и мнимой составляющих по (2+ + ) -му входу соответствующего блока преобразования второго рода, выход -го вычитателя первой группы через -й элемент взвешивания первой группы подключен к первому входу -го сумматора первой группы и к суммирующему входу 1-го вычитателя третьей группы в соответствующем блоке преобразования второго рода, выход 1-го вычитателя первой группы через 1-й элемент взвешивания второй группы подключен к первому входу -го сумматора второй группы и к суммирующему входу -го вычитателя четвертой группы в соответствующем блоке преобразования второго рода, выход 1-го вычитателя второй группы через 1-й элемент взвешивания третьей группы подключен к второму входу д-го сумматора второй группы и к вычитающему входу 1-го вычитателя четвертой группы в соответствующем блоке преобразования второго рода, выход 1-го вычитателя второй группы через -й элемент взвешивания четвертой группы подключен к второму входу 1-го сумматора первой группы и вычитающему входу 1-го вычитателя третьей группы в соответствующем блоке преобразования второго рода, выход -го сумматора первой группы и выход 1-го вычитателя четвертой группы являются выходами действительной и мнимой составляющих по 1-му выходу первой группы, а выход -го вычитателя третьей группы и выход 1-го сумматора второй группы являются выходами действительной и мнимой составляющих по -му выходу второй группы соответствующего блока преобразования второго рода, выход -го сумматора в блоке преобразования первого рода, выход 1-го сумматора первой группы и х-го вычитателя третьей группы в каждом блоке преобразования второго рода, а также выход д-го сумматора первой группы в каждом суммирующем блоке Р-го яруса, кроме (и) -го яруса, подключены к первым входами-е-г1-х (х2 ) или к вторым входам (1 - 2 ) -х (12) сумматоров первой группы соответствующих суммирующих блоков (Р+1)-го яруса, причем выходы сумматоров-го суммирующего блока Р-го яруса соединены с входами сумматорови -го суммирующегое+1блока (Р + 1)-го яруса, выход 1-го вычитателя третьей группы в блоке преобразования первого рода, выходы 1-го вычитателя четвертой группы и -го сумматора второй группы в каждом блоке преобразования второго рода, а также выход 1-го сумматора второй группы в каждом суммирующем блоке Р-го яруса, кроме (и)-го яруса, подключены к первым входам -хи-е-г(1-2 )-х (1 ) 2 ) сумматоров второй группы соответствующих блоков (Р+1)-го яруса, выходы 1-х суммато-ь ров первой и второй групп каждого суммирующего блока -го яруса, кроме О.Е -го суммирующего блока и кроме суммирующих блоков (и)-го яруса, подключены к суммирующим входам 1-х (12 и Е г ) или вычитающим входам (1 - 2 )-х (12 Е ) вычитателейи-Е-г и-Есоответственно первой и второй групп в соответствующем блоке преобразования второго рода (2+1) -го яруса, выходы 1-х сумматоров первой и второй групп и.Е-го суммирующего блока 1-го яруса, кроме (и)-го яруса, подключены к суммирующим входам 1-х (12 и ) или вычитающим входами-е-г(1 - 2 ) -х (12 ) вычитате ь-е ги-е лей соответственно первой и второй групп блока преобразования первого ряда (2+1)-го яруса.108480 2каждый суммирующий блок 2-го ярусаи-Гсодержит две группы по 2 сумматоров, причем входы -го ( = 1-е-- 2 ) сумматора первой группы являются входами действительных состави-Р-ляющих по д-му и (2 + -му входам соответствующего суммирующего блока, входы -го сумматора второй группы являются входами мнимых составляющих по д-му и (2 + 3.) -му входам соответствующего суммирующего блока, выходы -х сумматоров первой и второй групп являются выходами действительной и мнимой составляющих по -му выходу соответствующего суммирующего блока, каждый блок преобразования первого рода 1-го яруса содержит 2 сумматоров, трии-Е-группы по 2 вычитателей и четыре-1-1группы по 2 элементов взвешивания, причем суммирующие входы ь-х вычитателей первой и второй групп являются соответственно входами действительной и мнимой составляющих по -му входу соответствующего блока преобразования первого рода, вычитающие входы -х вычитателей первой и второй групп являются соответствеино входами действительной и мнии-Юмой составляющих по (2 + )-му входу соответствующего блока преобразования первого рода, выход д-го вычитателя первой группы через -й элемент взвешивания первой группы и через д-й элемент взвешивания второй группы подключен соответственно к первому входу -го сумматора и суммирующему входу д-го вычитателя третьей группы в соответствующем блоке преобразования первого рода, выход -го вычитателя второй группы через д-й элемент взвешивания третьей группы и через -й элемент взвешивания четвертой группы подключен соответственно к вычитающему входу д-го вычитателя третьей группы и к второму входу д-го сумматора в соответствующем блоке преобразования первого рода, выход -го сумматора и выход -го вычитателя третьей группы являются выходами действительной и мнимой составляющих по -му выходу соответствующего блока преобразования первого рода, каждый из блоков преобразования второго рода 1-го яруса имеет две группы по 2"выходови- и содержит две группы по 2 суммаь-Р торов, четыре группы по 2 вычитателей и четыре группы по 2 эле 1Изобретение относится к автоматике и вычислительной технике и может использоваться в устройствахспектрального Фурье - преобразования сигналов при параллельном спект 5ральном анализе в реальном масштабевремени.Известно устройство для выполнения преобразования Фурье, содержащеепоследовательно соединенные группыблоков, в каждую из которых входятарифметические и запоминающие блоки Г 12,Наиболее близким техническим решением к изобретению является устройство для выполнения преобразованияФурье, содержащее блоки преобразования первого рода и суммирующие блокисгруппированные в и ярусах (2"число входных отсчетов, определяющее 2 бразмерность преобразования), причемвыходы каждого блока преобразованияпервого рода и суммирующего блокапредыдущего яруса соединены с входамисоответствующего блока преобразования первого рода и суммирующегоблока последующего яруса, входы блоков первого яруса являются входамиустройства, а выходы блоков последнего яруса являются выходами устройства 2 3.Недостатком известных устройствявляется их сложность.Целью изобретения является упрощение устройства для выполнения пре 35образования фурье.Поставленная цель достигаетсятем, что в устройство для выполненияпреобразования Фурье, содержащееблоки преобразования первого рода исуммирующие блоки, сгруппированныев п ярусах (2 -размерность преобраэо- фвания Фурье), причем каждый из блоков преобразования первого рода исуммирующих блоков 2-Го (1 = Ор 1,и) яруса имеет 2 входов и 2"евыходов,а 2" входыблока преобразования первого рода первого яруса являются входами устройства и соединены с одноименными входами суммирую 50щего блока первого яруса, выходывсех блоков (п)-го яруса являютсявыходами устройства, введены блокипреобразования второго рода, причемна 1-м ярусе содержится один блокпреобразования первого рода, р55суммирующих блоков ( = 2 ар 2 +ментов взвешивания, причем суммирующие входы 1-х вычитателей первой и второй групп являются соответственно входами действительной и мнимой составляющих по -му входу соответствующего блока преобразования второго рода, вычитающие входы 1-х вычитателей первой и второй групп являются соответственно входами действительной и мнимой составляющих по (2 + 1) - му входу соответствующего блока преобразования второго рода, выход -го вычитателя первой группы через 1-й , элемент взвешивания первой группы подключен к первому входу 1-го сумматора первой группы и к суммирующему входу -го вычитателя третьей группы в соответствующем блоке преобразования второго рода, выход -го вычитателя первой группы через 1-й элемент взвешивания второй группы подключен к первому входу д-го сумматора второй группы и к суммирующему входу 1-го вычитателя четвертой группы в соответствующем блоке преобразования второго рода, выход 1-го вычитателя второй группы через 1-й элемент взвешивания третьей группы подключен к второму входу -го сумматора второй группы и к вычитаощему входу 1-го вычитателя четвертой группы в соответствующем блоке преобразования второго рода, выход д-го вычитателя второй группы через -й элемент взвешивания четвертой группы подключен к второму входу 1-го сумматора .первой группы и к вычитающему входу 1-го вычитателя третьей группы в соответствующем блоке преобразования второго рода, выход -го сумматора первой группы и выход 1-го вычитателя четвертой группы являются выходами действительной и мнимой составляющих по 1-му выходу первой группы, а выход 1-го вычитателя третьей группы и выход -го сумматора, второй группы являются выходами действительной и мнимой составляющих по 1-му выходу второй группы соответствующего блока преобразования второго рода, выход ь-го сумматора в блоке преобразования первого рода, выходы -го сумматора первой группы и 1-го вычитателя третьей группы в каждом блоке преобразования второго рода, а также выход 1-го сумматора первой группы в каждом суммирующем блоке 1-го яруса, кроме (и)-го яруса, подключены к первым входам 1-х ( ( 2 п е г ) или к втоьмвходам (1. - 2" Е ) -х и 12" Е )сумматоров первой группы соответствующих суммирующих блоков (1+1)-гояруса, причем выходы сумматоровй -го суммирующего блока 1-гоеяруса соединены с входами сумматоровОЕ+ -го суммирующего блока (1+1)-гояруса, выход 1-го вычитателя третьей10 группы в блоке преобразования первого рода, выходы д-го вычитателя четвертой группы и -го сумматора второй группы в каждом блоке преобразования второго рода, а также выход15 д-го сумматора второй группы в каждом суммирующем блоке 1-го яруса,1кроме (и) -го яруса подключены к-е-гпервым входам 1-х (12 ) или квторым входам ( - 2")-х20 (д ) 2" е г ) сумматоров второй группысоответствующих суммирующих блоков(1 - 2 ) -х (1 ) 2 2 ) вычитате 30 лей соответственно первой и второйгрупп в соответствующем блоке преобразования второго рода (7+1)-гояруса, выходы 1-х сумматоров первойи второй групп,ь. -го суммирующегоблока Е-го яруса, кроме (и)-гояруса, подключены к суммирующим входам 1-х (12г ) или вычитающимвходам (1 - 2 )-х (1 ) 2" г )вычитателей соответственно первой40 и второй групп блока преобразованияпервого рода (2+1)-го яруса.На фиг. 1 дана функциональная схема устройства для выполнения преоб -разования фурье, на фиг. 2 - схемаблока преобразования первого родана фиг. 3 - схема суммирующего блока,на фиг. 4 - схема блока преобразования второго рода.Устройство содержит блоки 1 преоб 50 разования первого рода, суммирующиеблоки 2, блоки 3 преобразованиявторого рода, группы 4 элементоввзвешивания, сумматоры 5 и вычитатели 6.Устройство работает следующим образом.Пусть через Х(о)Х(1),Х(2 -1), (О 42" 1) обозначаетсяпоследовательность значений из 2108485комплексных функций (сигналов), над которыми требуется произвести преобразование Фурье. И пусть через 2(о), 2(1 с), Е(2 -1) (О 4 1 с 4 2"-1) обозначается последовательность значений 5 из 2" комплексных функций (сигналов), получающихся в результате преобразования Фурье данных значений функции Х(1), 1 = 0,12 -1. Тогда соотношение, описывающее дискретное преобразование Фурье (ДПФ) сигналов Х(1) ( = 0,12 - 1), следующее1. Т 1%2-1 1 л 15 2)=.С Х(1)е, 01 с 3 ", 1:К .1:ОВторая половина из 2 п "коэффициентов Фурье легко получается в результате следующих тривиальных преобразований видаЕ(2 - 1 с) = 2(1 с), где ЕЬ) - 1 с-й комплексный коэффициент преобразования 25Фурье, являющийся комплексно-сопряженным1 с 2(1 с),Е(2 -1 с) - (2"-1 с)-й комплексныйкоэффициент преобразоваОния Фурье.Предлагаемое устройство предназначено для вычисления не менее 2" 07первых коэффициентов Фурье, включающих диапазон 0-2 значений аргумени та 1 с функции ЕЬ)иПреобразование для 2(2 -1 с) не отражено в схеме предлагаемого устройства в силу его тривиальности и не влияет на сложность конструкции,Суммирование или вычитание (в зависимости от знака экспоненциального множителя) в соответствии с выражением (1) осуществляется на. сумматорах 5 и вычитателях 6, Умножение на весовые коэффициенты, представляющие значение экспоненциального множителя, обеспечивается элементами 4 взвешивания.Для оценки положительного эффекта сравним общее число элементов взвешивания в известном устройстве.2"2 а = 2 ф 1(п+1)и предлагаемого устройстваи+1, 1 п 1 п 2 2 +2 +22 +32 + 2 3 Получаем1. /1, 3,что указывает на существенное упрощение конструкции.1084807 иг Составитель В.БаиковТехред С.Мигунова ректор А.Г ко едакто аказ 346 дписное НИИ 13035, М Филиал ППП "Патент", г. Ужгород, ул, Проектная, 4 Тираж 69Государственноголам иэобретенийква, Ж, Раушс омитета СССР октрытийя наб., д, 4/