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

 

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

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

Республик

К АВТОР СХОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (5I)M. Кл. (22)Заявлено 11.05.79 (21) 2765191/18-24 с присоединением заявки М5 06 F 15/33 с

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

СССР ао делаи нзебретеннй и открытий (23) Приоритет

Опубликовано 30.10.81. Бюллетень J4 40 (53) УДК 681 323 (088.8) Дата опубликования описания 30. 10.81

Н. Н. Немшилов и М. А. Титов (72) Авторы изобретения (7! ) Заявитель (54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО

ПРЕОБРАЗОВАНИЯ ФУРЬЕ

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

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

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

Недостатками известного устройства является низкое быстродействие и большой объем оборудования.

Цель изобретения - сокрашение состава оборудования и уменьшение времени выполнения преобразования.

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

Устройство содержит бпок 1 оперативной памяти (ОП), арифметический блок 2, счетчик 3 адресов операндов, счетчик 4 номера итерации, дешифратор 5 номера итерации, формирователь 6 адреса весовых коэффициентов и бпок 7 хранения весовых коэффициентов.

Работа устройства при вьшопнении преобразовани я поспедоватепьности размера

t4 осуществпяется в соответствии с алгоритмом К ц.

В исходном состоянии счетчика 4 номера итерации на выходе до дешифратора 5 сигнал равен "1", а на остальных равен

"0", Сигнал с выхода 3о, подключенного

35 к входным логическим схемам счетчика

3 адресов операндов, запрещает прохождение прямого переноса (в сторону старших разрядов), подкпючает шину "+1" к п -му разряду счетчика, делая его мпадшим раэ40 рядом; и для всех остальных разрядов разрешает прохождение обратного I переноса (в сторону мпадших разрядов).

Для перевода счетчика адресов в очередное состояние испопьзуется синхроимпупьс

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

llo окончании последовательности пред- 55 варитепьной итерации до счетчик адресов устанавливается в состояние О». Сигнал

0 с выхода Эо,поступая BG BKoltHbIe no

55 4 гические схемы всех разрядов счетчика, запрещает прохождение обратного переноса и разрешает прохождение прямого переноса (в сторону старших разрядов), вкпючая циклический перенос из м -го разряда в 1 й.

При передаче в блок ОП кода адреса дня чтения операнда поступает сигнал Соп в.(-1) и разряд счетчика адресов. Сиг« нал Со„при передаче второго адреса серии вычитает единицу из адреса.

Йоспедоватепьность адресов на других итерациях преобразования 4,,- 3> анапогична поспедоватепьности из итерации Э, но ! о все коды адресов II соответствии с правипом сдвига циклически сдвигаются (например, дпя 3 — на разряд вправо, дпя Э,, иа два разряда вправо, дпя Э, -Ha paapIIII вцево). По окончании посдедоватепьности адресов очередной итерации и переходе счетчика адресов через нупевое состояние происходит переключение на следующую итерацию, а переход через нуль в режиме вычитания приводит II переключе- нию на предыдущую итерацию. Таким образом, обеспечивается правильная адреса.ция операндов на границах итераций без нарушения чередования серий.

Поспе передачи в ОП адресов последней : серии записи на m -й итерации счетчик адреса устанавпивается в нулевое состояние. При этом счетчик итераций сигналом переводится в состояние Э,+1

При необходимости изменения размера преобразования на шину Njf. подается сигнал "1". Кроме. того, сигнал й/g, в счетчике 4 итерации исключает появление сигнала g „„. Работа устройства не отличается от описанной ранее, но все поспедоватепьности вдвое укороены .и исключается итерация п1 . При необходимости более широкого изменения размера преобразования, например до М/4 аналогичный коммутатор цикла пересчета необходимо вводить и в (м-1)-й разряд.

Структура предлагаемого устройства позвопяет сократить время выполнения преобразования путем совмещения итерации. При этом необходима перестройка узпа формирования серий, а именно: при- . менение счетчика с циклом пересчета дпиной (5 -2), где и дпина серии, равная

2, где p - число совмещаемых итераций; изменение соответствующим образом схем дешифратора реверса и дешифратора запрета; суммирование по сигнапу г к счетчику итераций единиц.

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

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

Удвоение числа арифметических блоков 10 и совмешение соседних итераций еше вдвое сокрашает время преобразования. Удвоение производительности арифметического блока у известного устройства дает сокрашение обшего времени преобразования лишь в ts

1,5 раза.

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

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

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

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

1. Авторское свидетельство СССР

М .:590750 кп. Q 06 F 15/34, 1978.

2. Вьюгина Н. Н. Индексное устройст во процессора дпя выполнения БПФ. Авизо матиэация", 1973, И. 3 (прототип).

ВНИИПИ Заказ 9617/74

Тираж 74S Подписное

Филиал ППП Патент, г. Ужгород,ул. Проектная,4