Устройство для реализации быстрого преобразования фурье Советский патент 1978 года по МПК G06F17/14 

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

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

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

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

Блок хранения и преобразования информации в известном устройстве выполнен в виде узлов сложения и умножения на регистрах сдвига. В связи с тем, что в основе работы такого устройства лежит принцип последовательной обработки информации, недостаток его состоит в том, что оно обладает относительно низкой скоростью вычисления, а также достаточно слабой УСТОЙЧИВОСТЬЮ

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

Цель 113обретения - повышение быстродействия.

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

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

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

Устройство для реализации быстрого иреобразования Фурье содержит блок 1 хранения и иреобразования информации со входами 2-5, входом 6, являющимся входом устройства, выходом 7, являюшнмся выходо.м устройства, выходом 8, а также блок 9 управления со входом 10 и выходами , иричем блок хранения и преобразования иифор мации содержит узел 15 входной памяти со входами , узел 20 выходной памяти со входами 21-23 и выходами 24-26, первый узел 27 аналогового преобразователя Фурье со входами 28, 29 и выходами 30, 3:1, второй узел 32 аналогового преобразователя Фурье со входами 33, 34 и выходами 35, 36, а блок управления содержит арифметико-логический узел 37 со входами 38, 39 и выходами 40, 41, коммутатор 42, цифро-аналоговый иреобразователь 43, счетчик 44 циклов со входом 45 и выходами , счетчик 49 шагов со входом 50 и выходом , элемент И 54 со входами 55, 56 и выходом 57.

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

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

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

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

24, 25 узл.а 20 подается на первый вход 28 узла 27 и на вход 33 узла 32, на входы 29, 34 соответственно узлов 27 и 32, через цифроаналоговый нреобразователь 43 поступают аргументы тригонометрических фуикций. С

выходов 30, 35 узлов 27, 32 информации, иреобразованная в соответствии с алгоритмом быстрого преобразования Фурье, записывается по входам 16, 17 Е первые ячейки регистров узла 15 входной памяти.

С выходов 31, 36 узлов 27, 32 с выхода 8 блока / на вход 10 блока 9 подается сигнал обратной связи, который со входа 55 элемента И 54 подается на,счетчик 49, увеличивая его содержимое на единицу. С выхода 51

счетчика 7 через выход 14 блока 9 и вход 5 блока / в узел 15 поступает сигнал, в результате чего ко входам 16, 17 узла 15 подключаются уже вторые ячейки его регистров (то есть осуществляется сдвиг регистров па.мяти).

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

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

счетчика 49, а сигнал иереполнения с выхода 52 этого .счетчика идет на вход 45 счетчика 44, увеличивая его содержимое на едииицу. При этом с его вы.хода 46 через выход 12 блока 9 на вход 4 блока 1 и на вход 18 узла

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

При переполнении счетчика 44, означающего конец быстрого преобразования Фурье, происходит сброс счетчика 44, а сигнал переполнения с его .выхода 48 поступает иа вход 5S элемента И 54, в результате чего

разрывается цепь обратной связи. Информация выводится из устройства.

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

уменьшается в среднем в несколько раз по сравнению с исиользованием ЦВМ. Так как решающие элементы устройства - аналогового действия, то вычислительный процесс будет всегда устойчивым относительно малых

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

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

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

соединен со вторыми выходами первого и второго аналоговых узлов преобразования Фурье.

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

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

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

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