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

 

УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ ПО ОСНОВАНИЮ ДВА, содержащее logaN (N размер преобразования коммутаторов , logjN арифметических блоков и 21og2N элементов задержки, причем выход

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

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

РЕСПУБЛИК (51) 4

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

fO ДЕЛАМ ИЗОБРЕТЕИИЙ И ОТНРЬЯ ИЙ

ОПИСАНИЕ ИЭОБРЕТ

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 37 59036/24-24 (22) 26.06.84 (46) 15.12.85. Бюл. Ф 46 (71) Одесский ордена Трудового Красного Знамени политехнический институт (72) М.Б. Свердлнк, В.Л. Евсеев и А.А. Назаренко (53) 681.32(088.8) (56) Патент США У 3816729, кл. G 06 F 15/332, 1974.

Патент США 9 3588460, кл. G 06 F 15/332, 1968. (54)(57) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ

БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ ПО

ОСНОВАНИЮДВА,содержащее 1о8ф (Н размер преобразования коммутаторов, log N арифметических блоков н

21о8 Н элементов задержки, причем выход (2i-1)-го (i=1, 1оя Н) элемента задержки подключен к первому информационному входу i-го коммутатора, первый и второй выходы которого подключены соответственно к входу первого операнда i-го арифметического блока и входу i-го элемента задержки, выход которого подключен к входу второго операнда i-ro арифметического блока, второй информационный вход первого коммутатора и вход первого элемента задержки являются соответственно входами первого и второго операндов устройства, а выходы первого и второго операндов 1-го арифметического блока являются выходами соответственно первого и второго операндов устройства, входами задания i-х коэффициентов первого и второго типов которого являются соответственно входы первого и второго коэффициен„„SU„„1198534 А тов i-го арифметического блока, выходы первого и второго операндов

j-го (j=l+ log N-1) арифметического блока подключены соответственно к второму информационному входу (j+1)-го коммутатора и входу (j+1)-го элемента задержки, а управляющий вход

i-го коммутатора является i-м тактовым входом устройства, в нем к-1-й (к=2,5,8...) арифметический блок содержит первый и второй сумматоры и элемент НЕ, выход которого подключен к первому входу первого сумматора, второй вход которого является входом второго операнда блока и соединен с первым входом второго сумматора, второй вход которого соединен с вхо-. дом элемента НЕ и является входом первого операнда блока, выходами первого и второго операндов которого являются соответственно выходы второго и первого сумматоров, при этом к-й арифметический блок содержит первый и второй сумматоры, элемент . НЕ, первый и второй умножители на постоянный коэффициент, первые входы первого и второго сумматоров соединены и являются входом второго операнда блока, входом первого операнда которого является вход первого умножителя на постоянный коэффициент, выход которого подключен к второму входу первого сумматора и входу элемента НЕ, выход которого подключен к второму входу второго сумматора, выход которого подключен к входу второго умножителя на постоянный коэффициент, выход которого является выходом второго операнда блока, выходом первого операнда которого является выход первого сумматора, причем (к+1) -й арифметический блок содержит первый и второй сумматоры, элемент НЕ, первый и второй умножители комплексных чисел и умножитель на постоянный коэффициент, выход которого подключен к первому входу первого сумматора и входу элемента НЕ, выход которого подключен к первому входу .второго сумматора, выход которого подключен к первому входу первого умножителя комплексных чисел, выход которого является выходом второго операнда

198534 блока, выходом первого операнда которого является выход второго ум ожи теля комплексных чисел, первый вход которого подключен к выходу первого сумматора, второй вход которого соединен с вторым входом второго сумматора и является входом второго операнда блока, входом второго операнда которого является вход умножителя на постоянный коэффициент, а вторые входы первого и второго ум- ножителей на коэффициент являются соответственно входами первого и вто рого коэффициентов блока.

Ъ

Изобретение относится к цифровой обработке сигналов и может быть использовано в радиолокации, системах связи, при анализе речевых сигналов и двумерных иэображений. 5

Цель изобретения — упрощение ус тройства.

На фиг. приведена схема одного каскада устройства; на фиг. 2а, б схема переключения коммутатора; на фиг. 3 — схема к-1 -ro арифметического блока; на фиг. 4 — схема к-го арифметического блока; на фиг. 5 — схема (к+1)-го арифметического блока; на фиг. 6 — пример выполнения устройства для N=32.

Каскад устройства (фиг. 1) содержит взводы 1 и 2 устройства, коммутатор 3, элементы 4 и 5 задержки, арифметический блок 6, выходы 7 и 8 ариф- 2О метического блока. (k-1)-й арифметический блок 9 (фиг. 3) содержит. входы 10 и 11, сум маторы !2 и 13, элемент НЕ 14, выходы 15 и 16; к-й арифметический блок

17 (фиг. 4) содержит: входы 18 и 19, арифметический блок 9, умножитель 20 на постоянный коэффициент, выход 21 умножитель 22 на постоянный коэффициент, выход 23. (k+1)-й арифмети- 30 ческий блок 24 (фиг. 5) содержит входы 25 и 26, арифметический блок

9, умножитель 27 на постоянный коэффициент, умножители 28 и 29 комплексных чисел с входами 30 и 31, выходы 32 и 33 блока.

Устройство для N 32 (фиг. 6) содержит входы 34, 35, коммутатор 3, элементы 4 и 5 задержки, арифметические блоки 9, 17, 24, 36, умножители 20, 22, 27, 28, 29, выходы

37 и 38.

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

На входы 1 и 2 поступают по N/2 операндов. Группа операндов, поданная на вход 1, поступает на первый вход коммутатора 3, а другая группа операндов проходит через первый элемент 4 задержки, осуществляющий задержку на Nl2 <., где i — номер каскада (i 1,2,3,...), с — интервалы поступления операндов, и через

N — поступает на второй вход комму2 татора -3, который производит перераспределение операндов, поступающих на его входы между его выходами.

Й л

Первые 2 " коммутатор 3 соединяет первый и второй входы соответственно с первым и вторым выходами (фиг. 2а), N л -следующие 2г о — первый и второй входы соответственно с вторым и первым выходом (фиг. 2б) . Затем эти положения коммутатора повторяются.

На выходах коммутатора 3 появляются

N две группы по — операндов, причем группа операндов на первом выходе коммутатора 3 появляется на N/р <, 1198534

N N

ne elYI Ф1

2 2 где m=),3,5,.... С выхода умножителя

27 на постоянный коэффициент операнды подаются на второй вход блока 9.

С выхода блока 9 операнды подаются на одни входы умножителей 28 и 29 ,комплексных чисел, на другие входыкоторых (30 и 31) подаютсь коэффициенты из блока хранения весовых коэффициентов. Умножитель 28 выполняет операцию умножения на W

Ч, (и)

N операндов с. номерами и, где n=1,2, М/2;

55 раньше, чем на втором выходе и за-. держивается во втором элементе 5 заN ú де ржк и на . На входы а рифме ти2 ческого блока 6 операнды поступают парами, обрабатываются в нем и парами появляются на выходах 7 и

8 арифметического блока. На входы

10 и 11 поступает пара операндов.

На первые входы сумматоров 12 и 13 подается операнд с входа 10, на второй вход сумматора 12 подается операнд с входа 12, а на второй вход сумматора 13 подается проинвертированный в элементе НЕ 14 операнд с входа 11. На выходе 15 появляется сумма входных операндов, а на выходе

16 — их разность.

Операнд, поступающий на вход 18, подается в блок 9, аналогичный ариф- 20 метическому блоку (к-))-ro каскада.

Операнд, поступающий на вход )9, подается на вход умножителя 20, выполняющего умножения на j операндов с номерами n= 2 m+),... /2 - m 25

И где m=l 3,5,..., а затем подается в блок 9 °

С первого выхода блока 9 операнды подаются на выход 21 арифметического блока. С второго выхода операнды 30 через умножитель 22, выполняющий умножения на j операндов с номерами

) 1 и

n= 1 meal,... е, подаются на выход 23 арифметического блока.

Операнд, поступающий на вход 25, подается в блок 9, аналогичный арифметическому блоку к-1 -ro каскада.

Операнд, поступающий на вход 26, подается на вход умножителя 27 на 4р постоянный коэффициент, выполняю-.аТ я е -1 н щего умножение на )4 я, где W =e операндов с номерами а) принимает значение 0 или I и изменяется в комплексе чисел ()og N-1

log И-2,...,2,1)

Умножитель 29 выполняет операцию умножения на W ) операндов с номе-

Ч (и и рамн n,ãäå 2 а - г " р

1 с выхода умножителей 28 и 29 комплексных чисел операнды поступают на выходы 32 и 33 арифметического блока 24.

При К=32 обрабатываемая последовательность подается на первый вход 34 устройства. Первые 16-операндов через коммутатор 3 первого каскада поступают на вход элемента задержки 4, содержащий )6 элементов задержки. Ос. тальные 16 операндов через коммутатор 3 подаются на второй вход арифметического блока 9 первого каскада одновременно с первыми 16 операндами, которые подаются на первый вход арифметического блока 9. На выходе арифметического блока 9 операнды появляются парами и поступают во вто. рой каскад устройства. С первого выхода арифметического блока 9 операнды поступают непосредственно на ком. мутатор 3 второго каскада, изменяющий свое состояние через каждые 8 с.

С второго выхода арифметического блока 9 операнды поступают в элемент

4 задержки, содержащий 8 элементов задержки на ь, а затем на второй вход коммутатора 3, который произво. дит перераспределение отсчетов по двум каналам. Операнды, появляющиеся на первом выходе коммутатора 3, поступают в элемент 5 задержки, содержащий 8 элементов задержки на, а затем на вход арифметического блока

17, на второй вход которого в то же время поступают операнды с второго выхода коммутатора 3. Аналогично операнды проходят через третий, четвертый и пятый каскады. В этих каскадах элементы 4 и 5 задержки содержат соответственно по 4,2 и 1 элемента задержки на, коммутаторы 3 имеют интервалы между. переключениями 4,Яами

S 1198534 4

В последнем каскаде арифметический ческого блока второго каскада, умноблок 36 содержит умножитель 20 и блок житель 27 на постоянный коэффици9, выкоды которого 37 и 38 являются ент и два умножителя 28 и 29 компвыходами устройства для выполнения i лексных чисел из арифметического

32-точечного БПФ с основанием два.

5 блока третьего каскада, умножитель

При обработке 32-точечной последо. операндов 20 из арифметического бловательности первый и второй умножи- ка пятого каскада выполняют операции тели 20 и 22 операндов из арифмети- умножения íà 4l„

Ч; n)

gut. РиаГ, фиа,3

Рие.4.

3f фиг. 5

1198534

1-й. мвиа4

-g м.eeewou

3- д л юе е/

Ф» и жвюР

Х- е кесчеоР

Are. б

Составитель А. Баранов

Корректор М. Демчик

Редактор И. Рыбченко Техред ТАанта

Подписное

Заказ 7723/49 Тиран 709

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

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

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