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

делаи изебре и открытиЯ ия описания 30. 10.81 ат ов и М,) Авторыизобретения(54) УСТРОЙСТВО ДЛЯ ВЬ ПРЕОБРАЗОВАНИзобретение относится к вычислительной технике и может быть использовано для цифровой обработки сигнапов, спектрального анализа различных процессов.. Известно устройство, которое содер жит в блоке управления помимо.коммута 5 тора, счетчика циклов и счетчика шагов адифметико-логическое устройство 13.Недостатком устройства для выполнения БПФ является сложность узлов, формирующих адреса, и применение.нетипоте вых блоков памяти, что ограничивает функциональные возможности и обусловливает высокую стоимость.Наиболее близким по технической сушности к предлагаемому является устройство, которое содержит блок оперативной памяти, отдельный арифметический блок, блок формирования адресов, называемый индексным устройством и предназначенный для получения последовательности ад ресов отсчетов и адресов весовых коэффициентов на каждой итерации. Формиро. вание адресов осуществляется с помошью логических схем и двоичных счетчиков с входной логикой, управляемой кодом из сдвигового регистра номера итерации 2Недостатками известного устройства является низкое быстродействие и большой объем оборудования.Цель изобретения - сокращение состава оборудования и уменьшение времени выполнения преобразования.Поставленная цель достигается тем, что в устройство, содержащее блок оперативной памяти, арифметический блок, формирователь адресов весовых коэффициентов и счетчик номера итерации, причем первый вход блока оперативной памяти явля ется входом устройства, а первый выход блока оперативной памяти соединен с первым входом арифметического блока, пер вый выход которого соединен с вторым входом блока оперативной памяти, введены блок хранения весовых коэффициентов, .счетчик адресов операндов и дешифратор номера итерации, первый вход счетчика адресов операндов соединен со вторым вы8775ходом блока оперативной памяти, первыйвыход счетчика адресов операндов соединен с третьим входом блока оперативнойпамяти и первым входом формирователяадресов весовых коэффициентов, второйвход которого соединен с выходом дешифратора номера итерации и вторым входомсчетчика адресов операндов, второй выходкоторого соединен с входом счетчика номефа итерации, выход которого соединен 10с входом дешифратора номера итерации,выход формирователя адресов весовых ко.эффициентов соединен с первым входомбпока хранения весовых коэффициентов, выход которого соединен с вторым входомарифметическоо бпока, второй выход которого соединен с вторым входом блокахранения весовых коэффициентов,, На чертеже представпена структурнаясхема устройства дпя выполнения быстрого преобразования Фурье.Устройство содержит бпок 1 оперативной памяти (ОП), .арифметический блок 2,счетчик 3 адресов операндов, счетчик 4номера итерации, дешифратор Б номераитерации, формирователь 6 айреса весовыхкоэффициентов и бпок 7 хранения весовыхкоэффициентов.Работа устройства при вьшопнении преобразования поспейоватепьности размераИ осуществпяется в соответствии с алгоритмом Кц.В исходном состоянии счетчика 4 номера итерации на выходе Эо дешифратора 5сигнал равен "1", а на остальных равен"Оф, Сигнап с выхода 30, подключенного35к входным погическим схемам счетчика3 адресов операндов, запрещает нрохождение прямого переноса (в сторону старшихразрядов), подключает шину ф+1 ф к п 1 -муразряду счетчика, делая его младшим раэ 40рядом; и для всех остальных разрядов разрешает прохождение обратного 1переноса (в сторону мпадших разрядов).Для перевода счетчика адресов в очередное состояние испопьзуется синхроимпупьс43считывания боо кода йз бпока 1. В резупьтате на вйходе счетчика адресов формируется двоично-инверсная поспедовательмность адресов для записи в ОП исходныхотсчетов, поступающих в естественном порядке через арифметический блок 2, гдепри необходимости может производитьсявзвешивание отсчетов входной последоватепьности,Йо окончании последовательности предварительной итерации до счетчик адресовустанавливается в состояние Оф. Сигнал0 с выхода Эо,поступая на входные по 55 4гические схемы всех разрядов счетчика,запрещает прохождение обратного переноса и разрешает прохождение прямого переноса (в сторону старших разрядов), вкпючая циклический перенос из ь -го разрядав 1 й,При передаче в блок ОП кода адресадня чтения операнда поступает сигнал опв.бъ)"й разряд счетчика адресов. Сигнал Спри передаче второго адреса серии вычитает единицу из адреса.Йоспедовательность адресов на другихитерациях преобразования д- Р, анапогична поспедоватепьности из итерации Э, но01все коды адресов и соответствии с правипом сдвига циклически сдвигаются (например, дпя Э- на разряд вправо, дпя Эиа два разряда вправо, дпя Э, -наразрядвцево). По окончании посдедоватепьностиадресов очередной итерации и переходесчетчика адресов через нупевое состояние происходит переключение на следующую итерацию, а переход через нуль врежиме вычитания приводит к переключе-нию на предыдущую итерацию, Таким образом, обеспечивается правильная адреса.ция операндов на границах итераций безнаруШения чередования серий,Поспе передачи в ОП адресов последней серии записи на т -й итерации счетчик адреса устанавпивается в нулевое состояние. При этом счетчик итераций сигналомпереводится в состояние Э ,1При необходимости изменения размера преобразования на шину ЙЙ. подается сигнал ф 1 ф. Кроме. того, сигнал й(2в счетчике 4 итерации искпючает появление сигнала 1. Работа устройства неотличается от описанной ранее, но все поспедоватепьности вдвое укороены .и исключается итерация Э п . При необходимостиболее широкого изменения размера преобразования, например до М 4 аналогичныйкоммутатор цикпа пересчета необходимовводить и в (в -1)-й разряд.Структура предлагаемого устройствапозвопяет сократить время выполненияпреобразования путем совмещения итерации. При этом необходима перестройкаузпа формирования серий, а именно; при- .менение счетчика с циклом пересчета дпиной (5 -2), где и дпина серии, равная2, где р - число совмещаемых итераций;изменение соответствующим образом схемдешифратора реверса и дешифратора запрета; суммирование по сигнапу г к счетчику итераций единиц.В этом случае формируется последовательность адресов, позволяющая над каж5 8775 дой серией иэ 1 операндов,выполнять , преобразования 9 соседних итераций беэ записи промежуточных результатов в ОП.Таким образом, предлагаемое устройство при одинаковых с известным требэ ваниях к быстродействию основных блоков эа счет рационапьной органиэации процесса позволяет вдвое сократить время пре образования.Удвоение числа арифметических блоков 1 О и совмещение соседних итераций еше вдвое сокрашает время преобразования, Удвоение производительности арифметического блока у известного устройства дает сокрашение обШего времени преобразования лишь в 15 1,5 раза.Предлагаемое устройство позволяет легко уменьшать размер в число раз краьное двум. Улучшение характеристик устройства достигнуто одновременно с сокраше 20 нием состава оборудования. ф орму ла и з обретения25Устройство дпя выполнения быстрого преобразования фурье, содержащее блок оперативной памяти, арифметический блок, формирователь адресов весовых коэффициентов и счетчик номера итерации, причем ЗО первый вход блока оперативной памяти яв ляется входом устройства, а первый выход блока оперативной памяти соединен с первым входом арифметического блока,55 бпервый выход которого соединен с вторымвходом блока оперативной памяти, о тличаюшееся тем,что,сцепьюсокрашения оборудования и повышениябыстродействия, оно содержит блок хранения весовых коэффициентов, счетчик адресов операндов и дешифратор номера итерации, первый вход счетчика адресов операндов соединен с вторым выходом бпокаоперативной памяти, первый выход счетчика адресов операндов .соединен с третьимвходом блока оперативной памяти и первым входом формироватепя адресов весовых коэффициентов, второй вход которогосоединен с выходом дешифратора номераитерации и вторым входом счетчика адресов операндов, второй выхОд которого совдинен с входом счетчика номера итерации,выход которого соединен с входом дешифратора номера итераш 1 и, выход формирователя адресов весовьць коэффициентов соединен с первым входом бпока хранениявесовых коэффициентов, выход которогосоединен с вторым входом арифметическэго блока, второй выход которого соединенс вторым входом блока хранения весовыхкоэффициентов,Источники информации,принятые во внимание при экспертизе .1. Авторское свидетельство СССРМ:590750 кп, ( 06 Р 15/34, 1978.2, Вьюгина Н, Н. Индексное устройство процессора дпя выполнения БПф."Автоматизация", 1973, И, 3 (прототип).