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

 

вт «Т@еТт Г:-, ":;,., "АЯ библииетта МБА

O ll M A H M E

ИЗОБРЕТЕН И Я

IiiI590750

Союз Советских

Социалистических

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву— (22) Заявлено 03.10.75 (21) 2178656, 24 с присоединением заявки М— (23) Приоритет— (43) Опубликовано 30.01.78. Бюллетень «е 4 (45) Дата оп:бликования описания 23.0!.78 (51) Ч.Кл G 06 F 15. 34

Государственный комитет

Совета Министров СССР па делам изобретений и открытий (53) УДК 681.325 (088.8) (72) Авторы изобретения

А. Т. Лукьянов и С. Я. Серовайский (71) Заявитель

Казахский ордена Трудового Красного Знамени государственный университет им. С. М. Кирова (54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ

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

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

Известно устройство для реализации быстрого преобразования Фурье (БПФ) (1), построенное с использованием регистров сдвига различной длины.

Конструкция этого устройства сложна.

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

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

Увеличение быстродействия в известном устройстве может быть достигнуто за счет использования параллельных секций, что ведет к значительным конструктивным усложнениям и повышению стоимости устройств».

Кроме того, цифровой способ обработки информации не позволяет использовать известное устройство непосредственно в качестве

10 процессоров для сеточных моделирующих устройств прп решении уравнений в частных производных, сужая тем самым функцпопаlbные возможности устройства.

Цель изобретения — повышение быстро15 действия.

Поставленная цель достигается тем, что третий и четвертый IIII«oды блока управления соединены с третьим и четвертым в«одами блока хранения и преобразования информацтш, а блок хранения и преобразования информации содержит узел входной II»мяти, узел выходной памяти, первый и второй аналоговые узлы преобразования Фурье, причем первый и второй выходы узла вы«одной памяти соединены с первыми входами соответственно первого и второго аналоговых узлов преобразования Фурье, вторые в«оды которых соединены со вторым входом блок», первый и второй в«оды узла выходной 1»зо мяти соединены соответственно с первым вхо590750 дом блока и входом устройства, выход которого соединен с выходом узла выходной памяти, первые выходы первого п второго аналоговых узлов преобразования Фурье соединены соответственно с первым п вторым входамп узла входной памяти, третий и четвертый входы которого соединены соответственно с третьим и четвертым входами блока, а выход блока соединен со вторыми выходами первого и второго аналоговых узлов преобразова11пя Фурье.

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

На чертеже представлена блок-схема устройства.

Устройство для реализации быстрого преобразования Фурье содержит блок 1 хранения и преобразования информации со входами 2 — 5, входом б, являющимся входом уст poHcTB3. BbIxotIo 1 7, являющимся выходо I устройства, выходом 8, а также блок 9 управления со входом 10 и выходами 11 — 14, причем блок хранения и преобразования информации содержит узел 15 вхо„í.îé памяти со входами lб — 19, узел 20 выходной памяти со входами 21 — 28 и выходами 24 — 2б, первый узел 27 аналогового преобразователя Фурье со входами 28, 29 и выходами 80, 81, второй узел 82 аналогового преобразователя Фурье со входами 88, 84 и выходамп 85, Зб, а блок управления содержит арифметико-логический узел 87 со входами 88, 89 и выходами 40, 41, коммутатор 42, цифро-аналоговый прсобразователь 48, счетчик 44 циклов со входом 45 и выходами 4б —;48, счетчик 49 шагов со входом

50 и выходом 51 —;58, элемент И 54 со входами 55, 5б и выходом 57.

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

Перед началом преобразования в блоке 9 управления задается размер преобразуемой информации (степень числа 2), через вход

6 устройства на вход 22 х зла 20 B6Ixo I. oÉ памяти записывается исходная информация.

По спгна Iv «нача70 работы» и 1формация о текущем шаге и цикле оыстрого . реоорязования Фурье из счет и;ков 44 и 49 подается

lO

3О

65 в узел 87, где формируются номера двух ячеек узла 20 выходной памяти, необходимых на данном шаге преобразования, а также аргументы тригонометрических функций в соответствии с алгоритмом быстрого преобразования Фурье. Информация о номерах ячеек с выхода 40 узла 87 через коммутатор 42 подается на вход 21 узла 20, в результате чего содержимое вызванных ячеек через выходы

24, 25 узла 20 подается на первый вход 28 узла 27 и на вход 88 узла 82, на вхо IBI 29, 84 соответственно узлов 27 и 82, через цифроаналоговый преобразователь 48 поступают аргументы тригонометрических функций. С выходов 80, 85 узлов 27, 82 информации, преобразованная в соответствии с алгоритмом быстрого преобразования Фурье, записывается по входам lб, 17 в первые ячейки регпсгров узла 15 входной памяти.

С выходов 81, Зб узлов 27, 82 с выхода 8 блока 1 на вход 10 блока 9 подается сигнал обратной связи, который со входа 55 элемента И 54 подается на счетчик 49, увеличивая его содержимое на единицу. С выхода 51 счетчика 7 через выход 14 блока 9 и вход 5 блока 1 в узел 15 поступает сигнал, в результате чего ко входам lб, 17 узла 15 подключаются уже вторые ячейки его регистров (то есть осуществляется сдвиг регистров памяти).

Начинается новый шаг быстрого преобразования Фурье.

В случае переполнения счетчика 49, означающего конец очередного цикла быстрого преобразования Фурье, происходит сброс счетчика 49, а сигнал переполнения с выходя

52 этого счетчика идет на вход 45 счетчика

44, увеличивая его содержимое на единицу.

При этом с его выхода 4б через выход 12 блока 9 на вход 4 блока 1 и на вход 18 узла

15,подается сигнал перезаписи, в результате чего информация из регистров узла 15 входной памяти переписывается по входу 28 узла

20 в выходную память. Начинается новый цикл быстрого преобразования Фурье.

При переполнении счетчика 44, означающего конец быстрого преобразования Фурье, происходит сорос счетчика 44, а сигнал псреполнеш1я с его выхода 48 поступает нг вход

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

В связи тем, что в данном устройстве проводится параллельная обработка информации, серьезно возрастает скорость вычисления. При этом существенное повышение быстродействия будет происходить на стадии вычисления трпгопометрических функций. Общее время вычисления в каждом конкретном случае определяется спецификой задачи и уменьшается в среднем в 1 есколько раз по сравнению с использованием ЦВМ. Так как решающие элементы устройства — аналогового действия, то вычислительный процесс будет всегда устойчивым относительно малых возмущений. Кроме того, предлагаемое устройство можно использовать непосредственно (без вспомогательных элементов) в качестве приставки к счетным моделирующим устройствам при численном решении дифференциальных уравнений в частных производных.

Формула изобретения

Устройство для реализации быстрого преобразования Фурье, содержащее блок хранения и преобразования информации и блок управления, причем первый, второй входы и выход блока хранения и преобразования информации соединены соответственно с первым, вторым выходами и входом блока yitравления, отличающееся тем, что, с целью повышения быстродействия, третий и четвертый выходы блока управления соедиг иены с третьим и четвертым входами олока хранения и преобразования информации, а блок хранения и преобразования информации содержит узел входной памяти, узел выходной памяти, первый и второй аналоговые узлы преобразования Фурье, причем первый, второй выходы узла выходной памяти соединены с первыми входами соответственно первого и второго аналоговых узлов преобразования Фурье, вторые входы которых соединены со вторым входом блока, первый и второй входы узла выходной памяти соединены соответственно с первьц входом блока н входом устройства, выход которого соединен выходом узла выходной памяти, первые выходы первого и второго аналоговых узлов преобразования Фурье соединены соответственно с первым и вторым входами узла входной памяти, третий и четвертый входы которого соединены соответственно с третьим и четвертым входами блока, а выход олока соединен со вторыми выходами первого и второго аналоговых узлов, преобразования

Фурье.

2. Устройство по п. 1, от ли ч а ю ще ес я тем, что блок управления содержит арифмстико-логический узел, счетчик циклов, счетчик шагов, элемент И, коммутатор и цифро-аналоговый преобразователь, причем первый и второй выходы арифметико-логического узла соединены соответственно со входом .коммун татора и входом цифро-аналогового преооразователя, выходы которых соединены соответственно с первым и вторым выходами блока, первый, второй, третий выходы счетчика циклов соединены соответственно с третьим вы20 ходом блока, с первым входом арифметикологического узла и с первым входом элемента И, первый, второй, третий выходы счетчика шагов соединены соответственно с четвертым выходом блока, со вторым входом арифметико-логического узла и со входом счетчика циклов, второй вход и выход элемента (Л соединены соответственно со входом блока и входом счетчика шагов.

З0 Источники информации, принятые во внимание при экспертизе:

1. Патент США ¹ 37883258, кл. 340 — 172, 5, 1974.

2. Авторское свидетельство СССР № 382091, кл. G Об F 15/34, 1971.

590750

Составитель Ф. Шагиахметов

Техред А. Камышникова Корректор В. Гутман

Редактор P. Киселева

1 одписное

Тип. Харьк. фил. пред. «Патент»

Заказ 1011/2062 Изд. № 209 Тираж 818

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

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