Устройство для выполнения быстрого преобразования Фурье Советский патент 1981 года по МПК G06F15/332 

(54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

Изобретение относится к вычиспитецьной технике и может быть использовано для цифровой обработки сигнапов, спектрального анализа различных процессов. Известно устройство, которое содержит вблоке управления помимо коммутатора, счетчика циклов и счетчика шагов арифметико-логическое устройство tl. Недостатком устройства для вьшолнения БПФ является сложность узлов, формирующих адреса, и применение нетипо вых блоков памяти, что ограничивает функциональные возможности и обусловли вает высокую стоимость. Наиболее близким по технической суш нооти к предлагаемому является устройство, которое содержит блок оперативной памяти, отдельный арифметический блок, блок формирования адресов, называемый индексным устройством и предназначенньтй для получения последовательности ад ресов отсчетов и адресов весовых коэффициентов на каждой итерации. Формирование адресов осуществляется с помощью логических схем и двоичных счетчиков с входной логикой, управляемой кодом из сдвигового регистра номера итерации Г21 Недост атками известного устройства является низкое быстродействие и большой объем оборудования. Цель изобретения - сокращение состава оборудования и уменыиение времени вьшолнения преобразования. Поставленная цель достигается тем, что в устройство, содержащее блок оперативной памяти, арифметический бпак, формирователь адресов весовых коэффициентов и счетчик номера итерации, причем первый вход блбка оперативной памяти является входом устройства, а первый выход блока оперативной памяти соединен с первым входом арифметического блока, первый выход которого: соединен с вторым входом блока оперативной памяти, введены блок хранения весовых коэффициентов, .счетчик адресов операндов и дешифратор номера итерации, первый вход счетчика адресов операндов соединен со вторым вы38ходом блока операгивной памяти, первый выход счетчика адресов операндов соеди. нен с третьим входом блока оперативной памяти и первым входом формирователя адресов весовых коэффициентов, второй вход которого соединен с выходом дешиф ратора номера итерации и вторым входом счетчика ад|эесов операндов, второй выход которого соединен с входом счетчика номера итерации, выход которого соединен с входом дешифратора номера итерации, выход формирователя адресов весовых коэффициеятой соединен с первым входом блока хранения весовых коэффициентов, вы ход которого соедийен с вторым входом арифметического блока, второй выход которого соединен с вторым входом бпока хранения весовых коэффициентов. На чертеже представлена структ рнай Схема устройства- дпя выполнения быстро го преббразобания Фурье. Устройство содержит блок 1 оперативной памяти (ОП), арифметический блок 2, счетчик 3 адресов операндов, счетчик 4 номера итерации, дешифратор 5 номера итерации, формирователь 6 адреса весовы коэффициентов и блок 7 хранения весовых козффидаентов. Работа устройства при выполнении пре образования последоватепьности размера {4 осуществляется в соответствии с алгоритмом Кудц. В исходном состоянии счетчика 4 номе ра итерации на выходе Зо дешифратора 5 сигнал равен 1, а на остальных равен О. Сигнал с выхода JQ | подключенного к входным логическим схемам счетчика 3 адресов операндов, запрещает прохожде ние прямого переноса (в сторону старших разрядов), подключает шину -И к m м разряду счетчика, делая еГо младшим раз рядом, и для всех остальных разрядов разрешает прохождение обратного переноси (в сторону младших разрядов). Для перевода счетчика адресов в очередное состояние используется синхроимпульс считывания Con кода йэ блока 1. В результате на вьЬсоде счетчика адресов мируется двойчно-йнйерсная последователь ность адресов для записи в ОП исходных отсчетов, постулаюших в естественном по рядке через арифметический блок 2, где при необходимости может производиться взвешивание отсчетов входной воследовательности. По окончании последовательности пред варительной итерации Зо счетчик адресов в состояние О. Сигнал устанавливается /О с выхода О о, поступая на входные ло5гические схемы всех разрядов счетчика, запрещает прохождение обратного переноса и разрешает прохождение прямого переноса (в сторону старших разрядов), включая Циклический перенос из m -го разряда в 1--Й-. При передаче в блок ОП кода адреса для чтения операнда поступает сигнал Cot, в. (т-1)-й разряд счетчика адресов. Сигнал С 5 при передаче второго адреса серии вычитает единицу из адреса. Последовательность адресов на других итерациях преобразования 3 аналогична последовательности из итерации 0., но все Коды адресов и соответствии с пршвидом сдвига циклически сдвигаются (например, дпз Лц - на разрад вправо, для 3 на два разряда вправо, для п. разряд влево). По окончании последовательности адресов очередной итераций и переходе счетчика адресов через нулевое состояние происходит перейлючение на следующую итерацию, а переход через нуль в режиме вычитания приводит к переключению на предыдущую Итерацию. Таким образом, обеспечивается правильная адресация операндов на границах итераций без нарушения чередования серий. После передачи в ОП адресов последней серии записи на m -и итерации счетчик адреса устанавливается в нулевое состояние. При этом счетчик итерапий сигналом Y переводится в состояние 0 При необходимости изменения размера преобразования на iirajt подается сигнал 1. Кроме того, сигнал N/2 в счетчике 4 итерации исключает появление сигнала Э п Работа устройства не отличается от описанной ранее, но все последовательности .вдвое укороены и исключается итерация Э , Прк необходимости более широкого изменения размера преоб-; разования, например до М/4 аналогичный коммутатор цикла пересчета необходимо вводить и в ((п-1)-й разряд. Структура предлагаемого устройства позволяет сократить время выполнения преобразования путем совмещения итерации. При этом необходима перестройка узла формирования серий, а именно: при- . менение счетчика с циклом пересчета длиной (5 -2), где Y1 дгтна серии, равная 2 , где р - число совмещаемых итераций; изменение соответствующим образом схем дешифратора реверса и дешифратора запрета; суммирование по сигналу г к счетчику итераций единиц. В этом случае формируется последовательность адресов, позволяющая над каж-