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

 

УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее блоки преобразования первого рода и суммирующие блоки, сгруппированные в п ярусах

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„ЯО.„.Ы 4Щ7 A (11 С 06 F 15/332

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ, " !3

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3385104/18-24 (22) 29.01.82 (46) 07.04.84. Бюл. N - 13 (72) Ю.И.Шафоростов (71) Куйбышевский институт инженеров железнодорожного транспорта (53) 681.3 (088.8) (56) 1. Патент США У 3746848, кл . Ci 06 F 7/38, 1972.

2. Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов. M. "Мир", 1978, с. 407. (54) (57) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ

ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее блоки преобразования первого рода и суммирующие блоки, сгруппированные п в п ярусах (2 -размерность преобразования Фурье), каждый из блоков преобразования первого рода и сумми-. рующих блоков Р-го (f = 0,1,...,6-1) пяруса имеет 2 входов и 2 " "выхои дов, а 2 входы блока преобразования первого рода первого яруса являются входами устройства и соединены с одноименными входами суммирующего блока первого яруса, выходы всех блоков (и-1)-го яруса являются выходами устройства, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, введены блоки преобразования второго рода, причем на 2-м ярусе содержится один блок преобразования первого рода, р-Е суммирующих блоков (1.Е =

2 мЕ-2+ ме-„- 1, Р -е = 1/2, 1kÅ = 1)

-1 е-1 и к „ блоков преобразования второго рода, каждый суммирующий блок 3-го яруса содержит две группы по 2 сумматоров причем входы i-ro (i и-Е-4

1 — 2 ) сумматора первой группы являются входами действительных составляющих по i-му и (2" "+ i)-му входам соответствующего суммирующего блока, входы i-го сумматора второй группы являются входами мнимых составляющих по i-му и (2" " + i)-му входам соответствующего суммирующего блока, выходы i-х сумматоров первой и второй групп являются выходами действительной и мнимой составляющих по д-му выходу соответствующего суммирующего блока, каждый блок преобразования первого рода 9-ro яруса содержит 2 сумматоров, три группп-е-< пы по 2 вычитателей и четыре и-Е-1 группы по 2 элементов взвешивания, причем суммирующие входы х-х

С2 вычитателей первой и второй групп являются соответственно входами действитсльной и мнимой составляющих С по i-му входу соответствующего блока преобразования первого рода, вы- р ,читающие входы i-х вычитателей первой и второй групп являются соответственI но входами действительной и мнимой осоставляющих по (2" + )-му 00 входу соответствующего блока преобразования первого рода, выход i-ro вычитателя первой группы через i-й элемент взвешивания первой группы и через 1

i-й элемент взвешивания второй грунпы подключен соответственно к первому входу i-ro сумматора и суммирующему входу i-го вычитателя третьей группы в соответствующем блоке пре- фр образования первого рода, выход i-го вычитателя второй .группы через i-й элемент взвешивания третьей группы и через i-й элемент взвешивания четвертой группы подключен соответственно к вычитающему входу 1-го вычитателя третьей группы и к второму

1084807 входу i-го сумматора в соответствующем блоке преобразования первого рода, выход i-ro сумматора и выход i-го вычитателя третьей группы являются выходами действительной и мнимой составляющих по i-My выходу соответствующего блока преобразования первого рода, каждый из блоков преобразования второго рода Х-го яруса имеи-е-1 ет две группы по 2 выходов и сои-е-1 держит две группы по 2 сумматои-l-1 ров, четыре группы по 2 вычнтаи-е-1 * телей и четыре группы по 2 элементов взвешивания, причем суммирующие входы i-x вычитателей первой и второй групп являются соответственно входами действительной и мнимой составляющих по х-му входу соответствующего блока преобразования второго рода, вычитающие входы i-x вычитателей первой и второй групп являются соответственно входами действительи-Р-1 ной и мнимой составляющих по (2 +

+ i) -му входу соответствующего блока преобразования второго рода, выход

i-го вычитателя первой группы через

i-й элемент взвешивания первой группы подключен к первому входу i-го сумматора первой группы и к суммирующему входу 1-го вычитателя третьей группы в соответствующем блоке преобразования второго рода, выход i-ro вычитателя первой группы через i-й элемент взвешивания второй группы подключен к первому входу i-ro сумматора второй группы и к суммирующему входу i-ro вычитателя четвертой группы в соответствующем блоке преобразования второго рода, выход i-го вычитателя второй группы через i-й элемент взвешивания третьей группы подключен к второму входу i-го сумматора второй группы и к вычитающему входу i-ro вычитателя четвертой

1 группы в соответствующем блоке преобразования второго рода, выход i-ro вычитателя второй группы через i-й элемент взвешивания четвертой группы подключен к второму входу i-го сумматора первой группы и вычитающему входу 1.-го вычитателя третьей группы в соответствующем блоке преобразования второго рода, выход

i-го сумматора первой группы и выход

1-го вычитателя четвертой группы являются выходами действительной и мнимой составляющих по >-му выходу первой группы, а выход i ãî вычитателя третьей группы и выход 1-го сумматора второй группы являются выходами действительной и мнимой составляющих по х-му выходу второй группы соответствующего блока преобразования второго рода, выход 1-го сумматора в блоке преобразования первого рода, выход 1-го сумматора первой группы и

i-ro вычитателя третьей группы в каждом блоке преобразования второго рода, а также выход >-ro сумматора первой группы в каждом суммирующем блоке I.-ro яруса, кроме (n-1) -r o яруса, подключены к первым входам и-е-г

i-x (i 2 ) или к вторым входам (i — 2 ) -х (i ) 2 ) сумматоров первой группы соответствующих суммирующих блоков (Р+1)-го яруса, причем выходы сумматоров p -ro суммирующего е блока Р-ro яруса соединены с входами сумматоров р -го суммирующего

0+1 блока (Р + 1) — ro яруса, выход i-ro вычитателя третьей группы в блоке преобразования первого рода, выходы

i-го вычитателя четвертой группы и

i-го сумматора второй группы в каж— дом блоке преобразования второго рода, а также выход i-го сумматора вто— рой группы в каждом суммирующем блоке Р-ro яруса, кроме (и-1)-го яруса, Ю подключены к первым входам 1-х п-е-г (i 2 ) или к вторым входам и-е-2 (i-2 ) -х (i ) 2 ) сумматоров второй группы соответствующих блоков (Р+1)-го яруса, выходы i-x сумматоров первой и второй групп каждого суммирующего блока 7-го яруса, кроме ,о.е -го суммирующего блока и кроме суммирующих блоков (n-i)-го яруса, подключены к суммирующим входам i-x (i 2" е г ) или вычитающим входам (i — 2 )-х (1 ) 2 Е ) вычитателей

° и-и-г соответственно первой и второй групп в соответствующем блоке преобразования второго рода (Р+1) -ro яруса, выходы i-x сумматоров первой и второй групп ð.е-го суммирующего блока I-ro яруса, кроме (n-1)-го яруса, подключены к суммирующим входам i-x (i 6 2и ) или вычитающим входам

-e-г (i — 2 )-х (i > 2 ) вычитате° ь-e z ° n-e-2 лей соответственно первой и второй групп блока преобразования первого ряда (2+1)-го яруса.

Изобретение относится к автоматике и вычислительной технике и может использоваться в устройствах спектрального Фурье — преобразования сигналов при параллельном спект5 ральном анализе в реальном масштабе времени.

Известно устройство для выполнения преобразования Фурье, содержащее последовательно соединенные группы блоков, в каждую из которых входят арифметические и запоминающие блоки 1).

Наиболее близким техническим решением к изобретению является устройст- 15 во для выполнения преобразования

Фурье, содержащее блоки преобразования первого рода и суммирующие блоки сгруппированные в и ярусах (2" число входных отсчетов, определяющее 2О размерность преобразования), причем выходы каждого блока преобразования первого рода и суммирующего блока предыдущего яруса соединены с входами соответствующего блока преобразова- 25 ния первого рода и суммирующего блока последующего яруса, входы блоков первого яруса являются входами устройства, а выходы блоков последнего яруса являются выходами устройства (2 3.

Недостатком известных устройств является их сложность.

Целью изобретения является упрощение устройства для выполнения пре35 образования Фурье.

Поставленная цель достигается тем, что в устройство для выполнения преобразования Фурье, содержащее блоки преобразования первого рода и суммирующие блоки, сгруппированные в п ярусах (2 -размерность преобразования Фурье), причем каждый из блоков преобразования первого рода и суммирующих блоков 2-го (I = 0,1,..., и-1) яруса имеет 2 входов и 2" е выходов,а 2 входы блока преобразования первого рода первого яруса являются входами устройства и соединены с одноименными входами суммирую50 щего блока первого яруса, выходы всех блоков (п-1) -ro яруса являются выходами устройства, введены блоки преобразования второго рода, причем на -м ярусе содержится один блок преобразования первого рода,,ц.

55 суммирующих блоков (pp = 2+p > +

+yg — 1, Р = 1/2, 9I, c= 1) и pi<„ блоков преобразования второго рода, 2 каждый суммирующий блок М-го яруса и-Р- < содержит две группы по 2 сумматоров, причем входы i-го (i = t

-е - — 2 ) сумматора первой группы являются входами действительных состави-0- ляющих по д-му и (2 + -му входам соответствующего суммирующего блока, входы i-го сумматора второй группы являются входами мнимых составляющих по i-му и (2" + i) ìó входам соответствующего суммирующего блока, выходы i-x сумматоров первой и второй групп являются выходами действительной и мнимой составляющих по i-му выходу соответствующего суммирующего блока, каждый блок преобразования первого рода 3-ro яруса содержит 2 сумматоров, три

-егруппы по 2 вычитателей и четыре

h- - группы по 2 элементов взвешивания, причем суммирующие входы i-x вычитателей первой и второй групп являются соответственно входами действительной и мнимой составляющих по

i-му входу соответствующего блока преобразования первого рода, вычитающие входы i-x вычитателей первой и второй групп являются соответствеино входами действительной и мниП-Ю-4 мой составляющих по (2 + i) ìó входу соответствующего блока преобразования первого рода, выход i-ro вычитателя первой группы через -й элемент взвешивания первой группы и через i-й элемент взвешивания второй группы подключен соответственно к первому входу i-ro сумматора и суммирующему входу i-го вычитателя третьей группы в соответствующем блоке преобразования первого рода, выход -го вычитателя второй группы через д-й элемент взвешивания третьей группы и через i-й элемент взвешивания четвертой группы подключен соответственно к вычитающему входу

i-ro вычитателя третьей группы и к второму входу i-го сумматора в соответствующем блоке преобразования первого рода, выход i-ro сумматора и выход i-ro вычитателя третьей группы являются выходами действительной и мнимой составляющих по i-му выходу соответствующего блока преобразования первого рода, каждый из блоков преобразования второго рода Х-ro яру0-1 са имеет две группы по 2" " выходов и-В- и содержит две группы по 2 суммаи-Р- 4 торов, четыре группы по 2 вычитаи-6- телей и четыре группы по 2 эле1084807 4 ментов взвешивания, причем суммирующие входы 1-х вычитателей первой и второй групп являются соответственно входами действительной и мнимой составляющих по i-му входу соответствующего блока преобразования второго рода, вычитающие входы 1 х вычитателей первой и второй групп являются соответственно входами действительной и мнимой составляющих по (2 + i)— му входу соответствующего блока преобразования второго рода, выход i-го вычитателя первой группы через 1-й, элемент взвешивания первой группы подключен к первому входу 1-го сумматора первой группы и к суммирующему входу 1-ro вычитателя третьей группы в соответствующем блоке преобразования второго рода, выход i-го вычитателя первой группы через i-й элемент взвешивания второй группы подключен к первому входу

i-ro сумматора второй группы и к суммирующему входу 1-го вычитателя четвертой группы в соответствующем блоке преобразования второго рода, выход i-го вычитателя второй группы через 1-й элемент взвешивания третьей группы подключен к второму входу

1-ro сумматора второй группы и к вычитаощему входу i-го вьтчитателя четвертой группы в соответствующем блоке преобразования второго рода, выход

i-го вычитателя второй группы через

i é элемент взвешивания четвертой группы подключен к второму входу

i-го сумматора .первой группы и к вычитающему входу 1-го вычитателя третьей группы в соответствующем блоке преобразования второго рода, выход i го сумматора первой группы и выход 1 го вычитателя четвертой группы являются выходами действительной и мнимой составляющих по 1-му выходу первой группы, а выход i — ro вычитателя третьей группы и выход

1-го сумматора, второй группы являются выходами действительной и мнимой составляющих по i-му выходу второй группы соответствующего блока преобразования второго рода, выход 1-ro сумматора в блоке преобразования первого рода, выходы i-ro сумматора первой группы и 1-го вычитателя третьей группы в каждом блоке преобразования второго рода, а также выход i-ro сумматора первой группы в каждом суммирующем блоке I — ro яруса, кроме (n-1)-го яруса, подключены к первым входам i-x (i < 2" 2) или к вто2рым входам (i — 2п-Р-2)-х и

-го суммирующего блока М-ro

Р яруса соединены с входами сумматоров ра,,„ — го суммирующего блока (2+1) -го яруса, выход i-го вычитателя третьей

1Î группы в блоке преобразования первого рода, выходы i-ro вычитателя четвертой группы и 1-го сумматора второй группы в каждом блоке преобразования второго рода, а также выход

15 i-ro сумматора второй группы в каждом суммирующем блоке 1-ro яруса, 1 кроме (n-1) -ro яруса подключены к и-Е-2 первым входам i-x (i < 2 ) или к вторым входам (1 — 2п 2 ) -х

20 (i ) 2" ) сумматоров второй группы соответствующих суммирующих блоков (2+1) -ro яруса, выходы i-х сумматоров первой и второй групп каждого сум .ирующего блока 1-го яруса, кроме

y <-ro суммирующего блока и кроме суммирующих блоков (п-1)-го яруса, подключены к суммирующим входам 1†- х (i < 2" < 2 ) или вычитающим входам и-И-2 и- -2 (i — 2 ) -х (i ) 2 ) вычитателей соответственно первой и второй групп в соответствующем блоке преобразования второго рода (7+1)-rо яруса, выходы i-x сумматоров первой и второй групп 1< -го суммирующего блока I-ro яруса, кРоме (п-1)-го яруса, подключены к суммирующим входам i-х (i < 2" 2 ) или вычитающим входам (i — 2" )-х (i > 2" 2 ) вычитателей соответственно первой

40 и второй групп блока преобразования первого рода (2+1)-ro яруса.

На фиг. 1 дана функциональная схема устройства для выполнения преоб— разования Фурье, на фиг. 2 — схема блока преобразования первого рода на фиг. 3 — схема суммирующего блока, на фиг. 4 — схема блока преобразования второго рода.

Устройство содержит блоки 1 преоб5О разования первого рода, суммирующие блоки 2, блоки 3 преобразования второго рода, группы 4 элементов взвешивания, сумматоры 5 и вычитатели 6.

Устройство работает следующим образом.

Пусть через Х(о),...,Х(1),..., Х(2 -1), (О < i < 2"-1) обозначается последовательность значений из 2

10848

S комплексных функций (сигналов), над которыми требуется произвести преобразование Фурье. И пу ;ть через Z(o), Z(k), Z(2 -1) (О < 1с 4 2"-1) обозначается последовательность значений 5 из 2" комплексных функций (сигналов), получающихся в результате преобразования Фурье данных значений функции X(i), i = 0,1,...,2 -1. Тогда соотношение, описывающее дискретное преобразование Фурье (ДПФ) сигналов X(i) (i = 0,1,...,2 -1), следующее

j, Т1%

2- 1 л 15 ()= х()е, о.<é 7, j= - ()

<=0

Вторая половина из 2" "коэффициентов Фурье легко получается в результате следующих тривиальных преобразований вида

Z(2 — 1с) = Z(k), где Z(k) - k-й комплексный коэффициент преобразования 25

Фурье, являющийся комплексно-сопряженным

k Z(k), Z(2 -k) — (2"-k)-й комплексный коэффициент преобразова- о ния Фурье.

Предлагаемое устройство предназначено для вычисления не менее 2"

07 первых коэффициентов Фурье, включающих диапазон 0-2 значений аргуменrl- 1 та 1 функции Z (k) . и

Преобразование для 2(2 -k) не отражено в схеме предлагаемого устройства в силу его тривиальности и не влияет на сложность конструкции.

Суммирование или вычитание (в зависимости от знака экспоненциального множителя) в соответствии с выражением (1) осуществляется на. сумматорах

5 и вычитателях 6. Умножение на весовые коэффициенты, представляющие значение экспоненциального множителя, обеспечивается элементами 4 взвешивания.

Для оценки положительного эффекта сравним общее число элементов взвешивания в известном устройстве.

+ 2". 2а = 2 (п+1) и предлагаемого устройства

n+ . n п-. п2

2 + 2 + 2.2 + 3-2 +

2 "++

Получаем

1.„/1. =3, что указывает на существенное упрощение конструкции.

1084807

1084807

1

Составитель В.Байков

Техред С.Мигунова

Корректор А.Гриценко

Редактор P.Öèöèêà

Заказ 3466 Тираж 699 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и октрытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент", г. Ужгород, ул, Проектная, 4