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

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

Цель изобретения - повышение быстродействия процессора быстрого преобразования Фурье.

На Фчг, 1 приведена функциональная схема -процессора быстрого преобразования Фурье (БПФ)J на фиг, 2 - функциональная схема формирователя сигналов приращенийJ на фиг. 3 . функциональная схема блока формирования дополнителыЛго кода.

Устройство содержит синхронизатор 1, счетчик 2 отсчетов, счетчик 3 итераций, счетчик 4 отсчетов, формирователь 5 сигналов приращений, блок 6 формирования дополнительного кода, мультиплексоры 7 и 8, регистр 9 адреса постоянной памяти, блок JO постоянной памяти, регистры 11 и 12 адреса (оперативной памяти), блоки 13 и 14 (оперативной) памяти, мультиплексор 15, арифметический блок 16.

Формирователь 5 сигналов приращений (фиг, 2) содержит элементы НЕ (17-1) - (17-К+1), дешифратор 18, коммутаторы (19-1)-(19-К), элементы И (20-1)-(20-К), элементы И (2-1-1) (21-К), элемент ИЛИ 22, RS-триггеры (23-1)-(23-К-1), коммутаторы (24-1)- (24-К-1).

Блок 6 формирования дополнительного кода (фиг. 3) содержит К-1 элементов И (25-1)-(25-К-1), К элементов НЕ (26-1)-(26-К-1), К коммутаторов (27-1)-(27-К-1), К-1 одноразрядных сумматоров (28-1)-(28-К-1).

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

На вход синхронизатора 1 поступает внешний сигнал запуска. Запись последовательности отсчетов входного сигнала производится в один из блоко оперативной памяти, например в блок 14. Б N/2 ячеек памяти комплексных чисел блока 14 оперативной памяти записывается отсчетов действительного сигнала так, что первая половина входной последовательности записывается в ячейки памяти действительной части, а вторая половина - в ячейки памяти мнимой части комплексных чисел.

После записи входной информации начинается процесс ее обработки. При

вычислении на первой итерации алгоритма БПФ из блока 14 оперативной памяти считываются два операнда, представляющие собой комплексные чис- ла, и записываются в арифметический блок 16 через мультиплексор 15, пропускающий на первой итерации сигналы от блока 14 оперативной памяти. Арифметический блок 16 реализует вычисле- ние базовой операции алгоритма БПФ действительной последовательности, особенностью которой по сравнению с базовой операцией стандартного алгоритма БПФ является перестановка мни- 5 ной части-первого операнда и действительной части второго операнда при показателе весового множителя, равном нулю, и комплексное сопряжение числа на выходе вычитателя арифмети- 0 ческого блока 16.

После выполнения базовой операции результирующие значения операндов с выходов арифметического блока 16 поступают на входы приема информации 5 блока 13 оперативной памяти.

На второй итерации считывание операндов производится из блока 13 оперативной памяти, а запись результатов вычислений арифметического бло- 0 ка 16 - в блок 14 оперативной памяти. Чередование режимов з.аписи-считы- вания блоков 13 и 14 оперативной памяти выполняется и на последующих итерациях. При этом коммутация адресов операндов для записи или считыва- ния блоков 13 и 14-оперативной памяти выполняется мультиплексорами 7 и 8.

Порядок выборки входных операндов на арифметический блок 16 и записи результатов вычислений в блоки 13 и 14 оперативной памяти на любой итерации формируется с помощью счетчиков 2 и 4 отсчетов, счет,чика 3 итераций, формирователя 5 сигналов приращений и блока 6 формирования дополнительного кода, управление которыми производится по сигналам от синхронизатора 1 .

Формирование адресов для считывания операндов в арифметический блок 50 16 осуществляется следующим образом.

Из алгоритма БПФ действительной последовательности следует, что на произвольной i-й итерации (, 2,....,К) базовые операции можно раз- 55 бить на группы так, что в каждой из групп базовые операции имеют одно и ,то же значение весового множителя. Причем для каждой базовой операции в

45

пределах одной группы при считывании операндов в арифметический блок 16 ДВОИЧНЫЙ код адреса второго операнда получается из двоичного кода адреса первого операнда путем инверсии (K+1-j)-ro разряда двоичного кода адреса первого операнда. Это свойство использовано в формирователе 5 сигйалов приращений. Для формирования адресов операндов используются 2, 3,...,(К+1) разряды счетчика 2 отсчетов. Сигнал с каждого i-ro разряда счетчика 2 отсчетов (,3,.....,К+1) поступает непосредственно на первый

осуществляется путем параллельной перезаписи сигналов на выходах коммутаторов 19-1 (,2,К) в соответствующие разряды счетчика 2 отсчетов по выходному сигналу перезаписи формирователя сигналов приращений, С приходом после перезаписи счетного импульса счетчик 2 отсчетов начинает вырабатывать сигналы для формирования адресов операндов новой группы. Число перезаписей в счетчик 2 отсчетов определяется количеством групп операций на текущей итерации. Для формирования сигнала перезаписи в

ход и через элемент НЕ 17-1-на вто- 15 формирователе 5 .сигналов приращений

рой вход коммутатора 19-1-1. Управ- .ление коммутатором 19-1-1 осуществляется сигналом с выхода (Элемента И 20-1-1, на входы коиспользуется элемент ИЛИ 22 и элементы И 21-1 (,2,...,К), на входы которых подаются сигналы от дешифратора 18, (2-К)-е разряды счетчика отсче25

30

торого поступают сигналы с (К+2-i)- 20 тов 2 и гребенка импульсов от синхро- го выхода дешифратора 18 и с первого разряда счетчика 2 отсчетов, в зависимости от состояния которого на (К+2-1)-й итерации на выход коммутатора 19-1-1 пропускается прямое или инверсное значение сигнала 1-го разряда счетчика 2 отсчетов. Таким образом, на произвольной j-й итерации (J 1 2,...,К) по управляющему сигналу с (K+1-j)-ro элемента И 20-K+1-J, на вход которого подается сигнал j-ro разряда депшфратора 18, находящийся в единичном состоянии, на выход- (K+1-j)-ro коммутатора (19-K+1-J) сначала пропускается сигнал (K+2-j)-ro разряда счетчика 2 отсчетов, когда сигнал первого разряда счетчика 2 отсчетов находится в нулевом состоянии, а затем - инверсное значение (K+2-j)-ro разряда счетчика отсчетов с выхода (К+1-j)- го элемента НЕ 17-K+1-J в тот мо-. мент, когда сигнал первого разряда счетчика 2 отсчетов находится в единичном состоянии. При.этом последовательно формируются адреса ПЕРВОГО и второго операндов на выходах коммутаторов 19-1 (1 1, 2,..., К) . Сигналы с выходов коммутаторов 19-1 (,2,..., К) пропускаются в зависимости от режимов работы блоков 13 и 14 оперативной памяти на выход одного из мультиплексоров 7 и 8 и .записываются в соответствующий регистр адреса оперативной памяти с тактом следования операндов.

Переход к формированию адресов следующей группы базовых операций

низатора 1.

Формирование адресов для записи результатов вычисления арифметического блока 16 в один из блоков оперативной памяти выполняется на основе преобразования счетчика 4 отсчетов. В соответствии с графом алгоритма БПФ в качестве адреса первого результата можно использовать непосредственно сигналы разрядов счетчика отсчетов. Адрес второго результата на первых двух итерациях получается путем инверсии старшего разряда .двоичного кода первого операнда. На 1-й 35 итерации (,4,...,К), адрес второго результата формируется из адреса первого результата следующим образом. В двоичном коде первого результата ...S, , где S I О или 1 (1 1,2,...,К), инвертируется старший

40

разряд S и выполняется вычисление

45

дополнительного кода g., g к-гёк- +т разрядов S,S ...8ц. . Получаемый после преобразования двоичный

код S g,

&н-а

S.C-i41...S

1

SO

55

где S - инверсное значение старшего разряда S, и является адресом второго результата. Формирование адресов записи результатов арифметического блока выполняется в блоке 6 формиро- . вания дополнительного кода. Последовательность формирования адресов уп- равляется сигналом первого разряда .счетчика 4 отсчетов, от селектированного соответствующим сигналом номера итерации с выхода дешифратора. На произвольной итерации при нулевом состоянии сигнала 1-го разряда счет;г.

осуществляется путем параллельной перезаписи сигналов на выходах коммутаторов 19-1 (,2,К) в соответствующие разряды счетчика 2 отсчетов по выходному сигналу перезаписи формирователя сигналов приращений, С приходом после перезаписи счетного импульса счетчик 2 отсчетов начинает вырабатывать сигналы для формирования адресов операндов новой группы. Число перезаписей в счетчик 2 отсчетов определяется количеством групп операций на текущей итерации. Для формирования сигнала перезаписи в

формирователе 5 .сигналов приращений

используется элемент ИЛИ 22 и элементы И 21-1 (,2,...,К), на входы которых подаются сигналы от дешифратора 18, (2-К)-е разряды счетчика отсче

тов 2 и гребенка импульсов от синхро-

низатора 1.

Формирование адресов для записи результатов вычисления арифметического блока 16 в один из блоков оперативной памяти выполняется на основе преобразования счетчика 4 отсчетов. В соответствии с графом алгоритма БПФ в качестве адреса первого результата можно использовать непосредственно сигналы разрядов счетчика отсчетов. Адрес второго результата на первых двух итерациях получается путем инверсии старшего разряда .двоичного кода первого операнда. На 1-й итерации (,4,...,К), адрес второго результата формируется из адреса первого результата следующим образом. В двоичном коде первого результата ...S, , где S I О или 1 (1 1,2,...,К), инвертируется старший

тов 2 и гребенка импульсов от синх

разряд S и выполняется вычисление

0 тов 2 и гребенка импульсов от синхро-

5

дополнительного кода g., g к-гёк- +т разрядов S,S ...8ц. . Получаемый после преобразования двоичный

код S g,

&н-а

S.C-i41...S

1

O

5

где S - инверсное значение старшего разряда S, и является адресом второго результата. Формирование адресов записи результатов арифметического блока выполняется в блоке 6 формиро- . вания дополнительного кода. Последовательность формирования адресов уп- равляется сигналом первого разряда .счетчика 4 отсчетов, от селектированного соответствующим сигналом номера итерации с выхода дешифратора. На произвольной итерации при нулевом состоянии сигнала 1-го разряда счет;г.

ика отсчета на выход блока 6 формиования дополнительного кода пропускатся сигналы 2, 3,...,(К+1)-го разряов счетчика 4 отсчетов без изменений используются в качестве адреса.пер- вого результата. Когда сигнал 1-го разряда счетчика 4 отсчетов принимает единичное состояние, выполняется преобразование сигналов 2, 3,..., ю (К+1)-го разрядов счетчика 4 отсчетов описанным вьше способом. При этом на выход К-го коммутатора 27-К пропускается инверсное значение сигнала К-го разряда счетчика 4 отсчетов, а на 15 первые входы одноразрядных сумматоров 28-1с, 28-K-1,...,28-K-i+1 пропуска-;- ются инверсные значения К-1,...,(K-i+ +1)-го разрядов счетчика 4 отсчетов для вычисления дополнительного кода. 20 В соответствии с операцией дополнительного кода на второй вход сумматора 28-K-i+1 в этот момент подается 1, для формирования которой используется сигнал с 1-го разряда счетчика 25 отсчетов, отселектированный сигналом номера итерации с выхода дешифратора 18. Полученный после преобразования двоичный код на выходе блока 6 формирования дополнительного кода зо представляет собой адрес записи второго результата арифметического блока 16 в один из блоков оперативной памяти. 1

Для выполнения базовой операции алгоритма БПФ в арифметический блок 16 по соответствующему входу подает.ся значение весового коэффициента из блока 10 постоянной памяти, в котором| затЛгсаны значения комплексной экспоненты в порядке возрастания показателя степени. Для организации считывания в соответствии с графом алгоритма БПФ на произвольной i-й итерации 2 значений весовых коэффициен- тов, каждое из.которых повторяется N/2 раз, используются RS-триггеры

23-i (,2,...,К-1) и коммутаторы 24-1 (.,2,.. . ,К-1) формирователя 8 сигналов приращений. По началу первой итерации от управляющего сигнала с 1-го выхода дешифратора 18 все RS-триггеры устанавливаются в единичное состояние. При этом все коммутаторы 24-i (,2,...К-1), на уп- равляющие входы которых подаются сиг налы с выходов соответствующих RS- триггеров 23-i (,2,...,К-1), про40

50

пускают на выход О и из блока 10 постоянной памяти считывается для выполнения базовых операций только одно значение весового множителя с. нулевым показателем степени. На вто рой итерации переводится в нулевое состояние RS-триггер 23-1 по сигналу второй итерации с 2-го выхода дешифратора 18 и на выход коммутатора 24-К-1 пропускается сигнал К-го разряда счетчика 4 отсчетов, который используется в качестве старшего разряда кода адреса весового коэффи- щента.При этом из блока постоянной памяти считываются два значения весового коэффициента с показателями степени О и N/2. На третьей итерации по сигналу с 3-го выхода, дешифратора в нулевое состояние переводится RS- триггер 23-2 и считываются значения весового коэффициента с показателями степени О, N/4, N/2, 3N/4 и т.д. На К-й итерации все RS-триггеры 23-i (,2,...,К-1) находятся в нулевом состоянии, и при вьшолнении базовых операций используются соответственно все N/2 значений весового коэффициента в порядке возрастания пока- . зателя степени.

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

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

Процессор быстрого преобразования Фурье, содержащий синхронизатор, первый счетчик отсчетов, счетчик итераций формирователь сигналов приращений, первый регистр адреса, регистр адреса постоянной памяти, блок постоянной памяти, первый блок памяти, арифметический блок, блок формирования дополнительного кода, причем ВХОД задания коэффициента арифметического блока подключен к выходу блока постоянной памяти, вход которого подключен к выходу регистра адреса постоянной памяти, информационные входы первой и второй групп формирователя сигналов приращений подключены к выходам разрядов группы соответственно первого счетчика отсчетов и счетчика итераций, адресный вход первого блока памяти подключен к выходу первого регистра адреса, о т л и чающийся тем, что, с целью повьшения быстродействия, в него введены второй счетчик отсчетов, три мультиплексора, второй блок памяти и .второй регистр адреса, причем выход результата арифметического блока подключен к информационным входам первого и второго блоков памяти, входы чтения записи которых подключены к первому вьпсоду синхронизатора, выход первого и второго блоков памяти подключены соответственно к пер- , вому и второму информационным входам первого мультиплексора, выход , 1 которого подключен к информационному входу арифметического блока, управля ,ющие входы первого, второго и третьего Гультиплексоров подключены к вто рому,выходу синхронизатора, входы 1 разрядов группы регистра адреса пос- тоянной памяти соединены с выходами первой группы формирователя сигналов приращений, выходы второй группы которого подключены к информационным входам первого счетчика отсчетов, к информационным входам первых групп второго и третьего мультиплексоров, выход третьего мультиплексора подключен к информационному входу второго регистра адреса, выход которого подключен к адресному входу второго блока памяти, выходы третьей группы формирователя сигналов приращений подключены к входам первой группы блока формирования дополнительного кода, выходы группы которого подключены к информационным входам вторых групп третьего и второго мультиплексоров, выход второго мультиплексора подключен к информационному входу первого регистра-адреса, выход сигнала перезаписи формирователя сигналов приращений подключен к входу разрешения записи первого счетчика отсчетов, входы обнуления и счетные входы первого и второго счетчиков отсчетов и счетчика итераций подключены соответственно к первому и второму выходам синхронизатора, выходы разрядов группы счетчика итераций подключены к входам второй группы блока формирования дополнительного кода и к информационным входам третьей группы формирователя сигналов приращений, управляющий вход которого подключен к третьему выходу синхронизатора, причем формирователь сигналов приращений содержит К+1 элементов НЕ (К 1о§2Ы,

5 10 15

0 5

5

0

N - размер преобразования), 2 К элементов И, 2 К-1 коммутаторов, К-1 RS-триггеров, дешифратор и элемент ИЛИ, причем входы элементов НЕ группы являются информационными входами- первой группы формирователя сигналов приращений, информационными входами второй группы которого являются входы группы дешифратора, первые инфор- мационные входы (K+i)-x (, К-1) ком- 1 утаторов являются информационными входами третьей группы формирователя сиг, приращений, выход j-ro (, К+1) элемента НЕ подключен к первому информационному входу (j-1)- го коммутатора, второй информационный вход которого объединен с входом j-ro элемента НЕ, выходы га-х (,к) коммутаторов являются, выходами второй группы формирователя сигналов приращений, управляющий вход т-го коммутатора подключен к выходу т-го элемен- 1та И, первые входы элементов И объединены и подключены к выходу первого элемента НЕ, а второй вход т-го элемента И подключен к (К+1-т)-му выхо- ду дешифратора, первый вход (К+1)-го элемента И является управляющим- входом формирователя сигналов приращений, а второй вход подключен к К-му выходу дешифратора, второй вход (К+ )-ro алемента И (, К)подключен к (К+1-3)-му выходу дешифратора, тре- тий вход подключен к выходу S-ro элемента НЕ, выход (K+i)-ro элемента И подключен к i-му входу элемента ИЛИ и первому входу (K+i+1)-ro элемента И, выход 2 К-го элемента И подключен к К-му входу элемента ИЛИ, выход которого является выходом сигнала перезаписи формирователя сигналов приращений, R-входы RS-триггеров объединены и подключены к первому выходу, дешифратора, S-вход i-ro RS-триг- гера подключен к (1-ь1)-му выходу дешифратора, а выход - к управляющим входам ( 2 K-i)-ro коммутатора, инфор,- мационные входы первой группы (K+i)-x коммутаторов объединены и являются входом задания логического О процессора, выходы (K+i)-x коммутаторов являются выходами первой группы формирователей сигналов приращений, а :вь1ходы RS-триггеров являются выходами третьей группы формирователя сигналов приращений, причем блок формирования дополнительного кода содержит К-1 элементов И, К элементов НЕ, К ком9

мутаторрв и К-1 одноразрядных сумма- .торов, при этом первые входы i-x (1 ГГк-Г) элементов И являются входами первой группы блока формировани дополнительного кода, входы j-x (, К) элементов НЕ и управляющий вход К-го коммутатора являются выходами второй группы блока формирования дополнительного кода, вторые входы элементов И и управляющий вход Кто коммутатора объединены, выход j-ro элемента НЕ подключен к первому информационному входу j-ro коммутатора, второй- информационный вход ко

фиг./

91

10

торого объединен с входом j-ro элемента НЕ, выход i-j O элемента И подключен к управляющему входу (K-i)-ro коммутатора и первому входу (K-i)-ro одноразрядного сумматора, второй вхо которого подключен к выходу (K-i)-ro комму атрра выход переноса т-го (га 1, К-2) одноразрядного сумматора подключен к входу переноса (т+1)- го одноразрядного сумматора, выход Кго коммутатора и выходы одноразрядных сумматоров являются выходами группы блока формирования допо- тельного кода.

Ki

Редактор И. Рыбченко

Составитель А. Бдранов

Техред М.Ходанич Корректор М.Самборская

Заказ 4128/50 . Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

Iput.S

От 5 Om t

Изобретение относится к вычислительной технике и, в частности, к устройствам для спектрального анализа сигналов, представленных в цифровой форме. Цель изобретения-- повышение быстродействия. Поставленная цель достигается тем, что в состав устройства входит синхронизатор, два счетчика отсчетов, счетчик итераций, формирователь сигналов приращений,- блок формирования дополнительного кода, три мультиплексора, регистр адреса постоянной памяти, блок Постоянной памяти,два регистра адреса,два блока памяти,арифметический блок. Кроме этого, формирователь сигналов приращений содержит К+1 элементов НЕ (, N - размер преобразования), дешифратор, 2К-1 коммутаторов, 2К элементов И, элемент ИЛИ и К-1 RS-тригге- ров, а блок формирования дополнительного кода содержит К-1 элементов И, К элементов НЕ, К коммутаторов,К-1 одноразрядных сумматоров. 3 ил., . i СЛ