Устройство быстрого преобразования фурье
Патент 660057
Авторы
Классы МПК
Устройство быстрого преобразования фурье
Иллюстрации
Реферат
ОП ИСАНИЕ
ИЗОБРЕТЕНИЯ
0ц666057
Союз Советских
Социалистических
Республик
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено 06.04.77 (21) 2472294/18-24 с присоединением заявки ¹ (23) Приоритет (43) Опубликовано 30.04.79. Бюллетень № 16 (45) Дата опубликования описания 30.04.79 (51) M. Кл 2
G 06F 15/34
Госуларственнь:й комитет
Совета Министров СССР по лелам изобретений и открытий (53) УДК 681.327 (088.8) (72) Авторы изобретения Н. П. Бычков, Ю. А. Грачев, Л. В. Сабаев и Т. Н. Федоровская (71) Заявитель (54) УСТРОЙСТВО БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ
Изобретение относится к области вычислительной техники и предназначено для использования в аппаратуре, осуществляющей спектральную обработку электрических сигналов в реальном масштабе времени, в частности для реализации больших фильтровых «полей».
Известно цифровое устройство быстрого преобразования Фурье, реализующее оперативный метод вычислений по алгоритму оыстрого преобразования Фурье (БПФ), позволяющий вычислять Л коэффициентов дискретного преобразования временной последовательности из Л выборок входного сигнала (1). Это устройство содержит множительный блок, блок памяти, сумматоры и работает в реальном масштабе времени.
Наиболее близким техническим решением к данному изобретению является устройство быстрого преобразования Фурье, содержащее блок управления, блок формирования весовых коэффициентов и вычислительный блок, состоящий из коммутаторов, блоков памяти и арифметического блока, причем управляющие входы коммутаторов, блоков памяти и арифметического блока подключены к соответствующим выходам блока управления, а соответствующий информационный вход арифметического блока — к выходу блока формирования весовых коэффициентов (2).
Недостатком известных устройств является низкое быстродействие, ограничивающее возможности их использования для обработки большого числа выборок N в ре5 альном масштабе времени.
Целью изобретения является повышение быстродействия устройства.
Поставленная цель достигается тем, что устройство быстрого преобразования Фурье
10 содержит дополнительно l вычислительных блоков (1+1=К вЂ” общее число вычислительных блоков), причем первые входы первого и второго коммутаторов в каждом вычислительном блоке являются соответст15 венно первым и вторым входом вычислительного блока, вторые входы первого и второго коммутаторов являются соответственно третьим и четвертым входом вычислительного блока, выходы первого и вто20 рого коммутаторов подключены ко входам соответственно первого и второго блоков памяти, выходы первого и второго блоков памяти, являющиеся соответственно первым и вторым выходом вычислительного
25 блока, подключены ко входам арифметического блока, первый и второй выходы которого подключены соответственно ко входам третьего и четвертого блоков памяти, выходы которых являются соответственно
30 третьим и четвертым выходом вычислительного блока, управляющие входы коммута660057
50 ) Э
60 с) торов, блоков памяти и арпфмстп Iccl(oão блока в каждом из дополнительно введенных вычислительных блоков подкл 0 гены к соотвстствующим выходам блока уира "лсния, а соответствующие информацпспные ные входы арифметических блоков — — к выходам блока формирования всcoBblx коэффициентов, первый вход первого вычислительного блока является информационным входом устройства, второй вход первого вычислительного б;10ка Iio+KJIIO IBII к Ilepвому выходу К-гo вычислительного блока, первый и второй входы i-го (i==2 — К) вычислительного блока подключены соответственно к первому и второму выходам (i — 1)-ro вычислительного блока, третий и четвертый выходы i-го (i = — 1 — К/2) вычислительного блока подключены к четвертому входу соответственно (2i — 1)-го и 2i ãî вычислительного блока, третий и четвертый выходы i-го (i = (1+К/2) — К) вычислительного блока подключены к третьему входу соответственно (2i — К вЂ” 1) -го и (2i — К) -ro вычислительного блока.
На фиг. 1 приведена функциональная схема устройства преобразования; на фиг. 2 — вычислительного блока, на фиг. 3 — арифметического блока.
Устройство содержит К вычислительных блоков 1, блок 2 формирования весовых коэффициентов, устройство 3 управления, блоки 4 памяти, арифметические блоки 5, блоки 6 памяти, коммутаторы 7, В состав аРИфМЕТ11с1ССКОГО ОЛОКа BXO)151 i СУ ММаТОРЬ1
8, 9, блок 10 умножения, коммутаторы 11.
Устройство осуществляет обра ботку
Л =2" дискретных значений BxoJIHoro сигнала. Каждый вычислительный блок обрабатывает одновременно Ы=2 " дискретных
М > значений(Л4= — 1, причем число вычисли1, тельных блоков К=2 "-"" должно быть выбрано исходя из требуемого быстродействия. Вся информация представляется комплексными числами. Емкость каждого блока памяти составляет 2" — комплексных чисел. Входная информация (N =-2" выборок) поступает последовательно па первый вход вычислительного блока 1. После Л тактов сдвига в первый блок 4 памяти i-го вычислительного блока 1 запишутся выборки с
Л4 номерами j с — (i — 1) по 1(М/2) i — 1), во
7 второй блок 4 памяти этого же блока-т выборки с номерами j+ — . После записи ) всей входной информации начинается собственно процесс обработки ес по алгоритму БПФ, Обработка состоит из n== logqN операций. В любой операции в каждом вычислительном блоке 1 пара комплексных чисел x(j) из первого блока памяти и х j+ †) нз второго одновременно поступа7) ет на входы сумматоров 8 и 9 арифм.етиче5
4 ского блока 5. На выходе сумматора 9 поN" ят яастся рс>таьтат > jjj + t (j+ — ) . Ре )
l зультат, полученный на сумматоре 8 и равХ, ный x(j) — xl j+ — 1 поступает на вход т блока 10 умножения, на другой Bход которого из формирователя 2 весовых коэффициентов поступает соответствующее комплексное значение коэффициента F, завиС5пцее оТ номера выборки;1 номера операции.
1эсзультаты с выхода с) мматора 9 и с выхода блока 10 ум ножения последовательно один за другим по управляющему синхроимпульсу от у стройства 3 управления (УУ) записываются в третий и четвертый блоки 6 памяти B зависимости от номера /, причем в третий блок памяти запиcbIBBI0Tc5I суммы и ьзвешенныс разности первой половины вычисленных результатов, .Н в ч с т в с p T bl I I - - - B T o p II 51 и 0 л О В и и а . П О с л с ) тактов вычислений содержимое третьих и четвертых блоков 6 памяти переписывается в первые и вторые блоки 4 памяг11 соответствующих вычислительных блоков (через коммутаторы 7 по управляющему синхроимпульсу. от УУ 3). Это позволяет проводить обработку информации во всех последующих операциях аналогично описанной выше. Окончатсльньш результат — Л коэффициентов дискретного преобр азователя
Фурье — получается после операций записанным в третьи и четвертые блоки 6 памяти всех К вычислите.li>Hbix блоков 1. Порядок записи результг та двоично-инверсный по отношению и порядку -.àïèñè входной информации.
11рсдложенная структура, устройства Iloзволяет значительно сократи гь время обработки, так как вместо п2" —: комплексных умножений и n2 " — комплексных сложений и вычитаний оно выполняет n2 — комплексных умножений II столько же комплексных сложений и вычитаний.
Формула изобретения
Устройство быстрого прсобр азова ния
Фурье, содержащее блок управления, блок формирования весовых коэффициен" îâ и вычислительный блок, сост()ящий из коммутаторов, блоков памяти и арифметического блока, причем управляющие входы ком м т TIIT01 ОВ, ОлокОВ пс1 мяти II аРиф ILTHчсскогo блока подкапочены к соответству1ощим выходам блока управления, а соотвстствуюший информационный вход арифметического блока — к выходу блока формирования весовых коэффициентов, отличающееся тем, чro, с целью повышения быстр одействп я устройства, оно содержит дополнительно l вычислительных блоков (1+1=К вЂ” общее число вычислительных блоков), причем первые входы первого и второго коммутаторов в каждом вычислител. |ом блоке являются соответственно первы:| и вторым входом вычислительного блока, вторые входы первого и второго коммутаторов являются соответственно третьим и чствертым входами вычислительного блока, выходы первого и второго коммутаторов подключены ко входам соответственно первого и второго блоков памяти, выходы первого и второго блоков памяти, являющиеся соответственно первым и вторым выходами вычислительного блока, подключены ко входам арифметического блока, первый и второй выходы которого подключены соответственно ко входам третьего и четвертого блоков памяти, выходы которых являются соответственно третьим и четвертым выходами вычислительного блока, управляющие входы коммутаторов, блоков памяти и арифметического блока в каждом из дополнительно введенных вычислительных блоков подключены к соответствующим выходам блока управления, а соответствующие информационные входы
ЫаО57
6 арифметических блоков — к выходам блока формирования весовых коэффициентов, первый вход первого вычислительного блока является информационны:а входом уст5 ройства, второй вход первого вычислительного блока подключен к первому выходу
К-ro вычислительного блока, первый и второй входы i-го (i=2 — К) вычислительного блока подключены соответственно к перво10 му и второму выходам (i — 1) -го вычислительного блока, третий и четверты i выходы
i-ro (i = 1 — К/2) вычислительного блока подключены к четвертому входу соответственно (2i — 1)-го и 2i-го вычислительного
15 блока, третий и четвертый выходы |-го (i = (1+К/2) — К) вычислительного блока подключены к третьему входу соответственно (2i — К вЂ” 1) -го и (2i — К) -го вычислительного блока.
20 Источники информации, принятые во внимание при экспертизе
1. Авторское свидетельство СССР № 480079, кл. G 06F 15/34, 1975.
2. Патент Франции ¹ 2082030, кл. G 06F
25 15/00, 1975.
КЬ1
660057 — I. 4
; L a
jm 5 фна Г
1 !
2с — 5
o"
Cmc
Составитель В. Байков
Корректоры: Л. Брахнина и Е. Осипова
Техред Н. Строганова
Редактор Б. Герцен
Типография, пр. Сапунова, 2
Заказ 568/13 Изд. № 265 Тираж 779 Подписное
НПО Государственного комитета СССР по делага изобретений и о:крыгий
113035, Москва, Ж-35, Раугпская иаб., д. 4/5