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

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

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

На фиг„1 приведена функциональная схема процессора быстрого преоб- разования Фурье (ВПФ) на фиг„2 - функциональная схема формирователя сигналов приращений; на фигоЗ - функциональная схема формирователя адреса (оперативной памяти); на фиг„4 - Фзткциональная схема формирователя адреса постоянной памятис

Процессор (фиГоО содержит блок i синхронизации , счетчик 2 итерации, счетчик 3 отсчетов, счетчик 4 адресов весовых коэффициентов, формирователь 5 сигналов приращений, формирователь 6 адреса -оперативной памяти, формирователь 7 адреса постоянной памяти, мультиплексор 8 ад- раса оперативной памяти, мультиплексор 9 адреса постоянной памяти, регистр 10 адреса оперативной памяти, регистр 11 адреса постоянной памяти, блок 12 постоянной памяя и, дешифра- тор 13, блок 14 оперативной памяти, коммутаторы 15 и 16, арифметический блок 17 J элемент НЕ 18 и коммутатор 19.

Формирователь сигналов приращений (фиго2) образуют элементы НЕ 20 - 1- 20-К+1, дешифратор 21, коммутаторы 22-1-22-К, элементы И 23 -1 - 23 - К элементы И 24-1 - 24-К и элемент ИЛИ 25 о

Формирователь ад,реса оперативной памяти включает элементы ИЛИ 26- - 26-К-З, сумматоры 27-1 27-К-2 по модулю 2 и коммутаторы 28-1 - 28-К-2

Формирователь а;,реса постоянной памяти (фиго4) содержит элементы ИЛИ 29-1 - 29-К-4,, С1; мматоры по модулю 30-1 - 30-К-З и коммутаторы 31-1 31-К-З.

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

На вход блока 1 синхронизации поступает внешний управляющий сигнал запуска

Запись последовательности отсчето входного сигнала в блок 14 оперативной памяти осуществляется в нормальном порядке.При обработке комплексно

Q i-

0 5 n

5 0

0

5

5

последовательности в блоке 14 опера1C

тивной памяти записывается , где К - целое, комплексных отсчетов сигнала. В режиме обработки действительного сигнала в блок 14 оперативной памяти вводится 2N действительных отсчетов сигнала, причем вторая половина последовательности записывается в ячейки памяти, отведенные для мнимой части .N-точечной входной последовательности, далее производятся операции над образованной таким способом N-точечной комплексной последовательностью

Вычисление спектра действительной последовательности выполняется по специальному алгоритму БПФ„

В соответствии с графом алгоритма БПФ действительной последовательности с замещением для записи промежуточных результатов вычислений требуется N ячеек памяти комплексных чисел. Такой объем памяти требуется и в режиме обработки устройством N-точечной последовательности по стандартному алгоритму БПФ с замещением.

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

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

В режиме обработки действительного сигнала, который задается внешним управляющим сигналом типа обрабатываемой последовательности (комплексной или действительной), поступающим через блок 1 синхронизации (фиГоО на вход дешифратора 13 и на управляющие входы коммутатора 19, мультиплексорп

8

i:ipecH , памяти и

мультиплексор; 9 ;1дреса постоянной

памят 1, для рсализяп,ии базовой операции алгорт1тма БПФ действительной последовательности дешифратор 13 формирует управлябщий сигнал, по которому на выходы коммутаторов 15 и 16 пропускаются сигналы соответственно с второго и третьего выхода блока 14 оперативной памяти, а на выход коммутатора 19 пропускается сигнал непосредственно с выхода мнимой части второго результата арифметического блока 17 о

Новые значения операндов с выходов арифметического блока 17 и коммутатора 19 поступают на входы блока 14 операвтивной памяти.

Порядок выборки входных; операндов в арифметический блок 17 и записи результатов вычислений в блок 14 оперативной памяти на любой итерации формируется с помощью счетчика 3 отсчетов и формирователя 5 сигналов приращений о На произвольной i-и итерации (i-1,К) базовые операции можно разбить на групп так, что в каждой из групп базовые операции имеют одно и то же значение весового множителя, причем в пределах одной группы для каждой базовой операции двоичный код адреса второго . операнда получается из двоичного код адреса первого оперенда путем инверсии его (Ktl-i)-ro разряда Это свойство использовано в формирователе 5 сигналов приращений Для формирования адресов операндов используются 3,4,о„„,К+2-1 разряды счетчика 3 отсчетов. Сигнал с каждого i-ro разряда счетчика 3 отсчетов (,K+2 поступает через элемент ИЕ 20-i-l на один вход и непосредственно на другой вход коммутатора . (фиго2)„ Управление коммутатором 221-2 осуществляется сигналом с выхода элемента И 23-i-2, на входы которого поступают с (К+3-)-го выхода дешифратора 21 и сигнал первого разряда счетчика 3 отсчетов, Б зависимости от состояния которого на (К+3-i)-й итерации на выход коммутатора 22-1-2 пропускается прямое или инверсное значение i-ro разряда счетчика 3 отсчетов На j-й итерации (J-I,K) по управляющему сигналу с (K+l-j)-ro элемента И 23-K+l-i, на вход которого подается сигнал j-ro

10

15

20

25

30

88892

разряда дешифратора 21, находящийся на j-и итерации в единичном состоянии, на выкол (K-t-l-j)-ro коммутатора 22-K+1-J пропускается .инверсное значение (K+3-j)-ro разряда счетчика отсчетов с выхода (K-fi-j)-ro элемента НЕ 20-K+1-J в тот момент, когда сигнал первого разряда счетчика 3 отсчетов 3 находится в единичном состоянии о На выходах коммутаторов 22-i ,К) последовательно формируются адрес первого операнда при нулевом состоянии сигнала 1-го разряда счетчика отсчетов и адрес второго оперенда при единичном состоянии сигнала i-ro разряда счетчика отсчетов о Сигналы с выходов коммутаторов 22-i (,K) переписываются в блок оперативной памяти с тактом следования операндов

Поскольку для образования адреса операнда используются 3 (К+2)-1 разряды счетчика 3 отсчетов, а на управляющие входы коммутаторов 22-i (,K) подается 1-й разряд счетчика отсчетов, то каждая пара адресов операндов формируется дважды: для считывания исходных операндов из блока 14 оперативной памяти, а затем для записи результатов вычислений в блок 14 оперативной памяти по тем же адресам

5

0

5

0

Переход к формированию адресов следующей группы базовых операций осуществляется путем параллельной перезаписи содержимого регистра 10 адреса оперативной памяти в счетчик 3 отсчетов по выходному сигналу количества групп базовых операций формирователя 5 сигналов приращений, С приходом после перезаписи счетного импульса счетчик 3 отсчетов начинает вырабатывать сигналы для формирования адресов операндов новой группы Число перезаписей в счетчик 3 отсчетов определяется количеством групп базовых операций на итерации. Для формирования сигнала количества групп базовых операций в формирователе 5 сигналов приращений используются элемент ИЛИ и элементы И 26-i ,K), на входы которых подаются сигналы от дешифратора 21, 3- г(к+1)-1 разряды счетчика 3 отсчетов и гребенка импульсов от блока 1 синхронизации с периодом, в 2 раза большим периода следования операндов о

51

При выполнении базовой операции алгоритма БПФ в арифметической блок 17 по соответствующему входу подается значение весового коэффициента из блока 2 постоянной памятио В блоке 12 постоянной памяти значения весово экспоненцальной функции записаны g нормальном порядке. Для считывания весовых коэффициентов в соответствии с алгоритмом БПФ действительной по- следоват ельности используется формирователь 7 адреса постоянной памяти, являющийся комбинагщонной схемой и преобразующий двоичный код Sk-4 S К-, ,„,3д, поступающий от счетчика 4 адресов весовых коэффициентов по формуле

Г5к-эи , i K-2-p

g I к-2-i

21S; (mod2), .p, r-°

яе Зк-гд ,gg двоичный код на

При вычислении спектра 2N-точечной действительной последовательности по специальному алгоритму БПФ устройство N Г

ций, а общее количество базовых операций, выполняемое известным устройстN

на выходе формирователя ад,ре- - выполняет V, --т базовых опера- са постоянной памяти; р - Номер самого старшего из ненулевых разрядов двоичного

вом, составляет / --- (ogjN+3)-lo

кода SK-; S oooSo, при (,3-2) ,

Результирующий адрес весового коэффициента дч-г. О к-э ° «go через мультиплексор 9 адреса постоянной памяти поступает на регистр 11 адреса постоянной памятио

Организация считывания по алго- ритму БПФ на 1 -и итерации 2 значений весовых коэффициентов каждое из которых повторяется N/2 раз, осуществляется на основе счетчика 4 адресов весовЬпс коэффициентов, на счетный вход которого подается сигнал перезаписи счетчика 3 отсчетов о Перед началом каждой итерации по сигналу от блока 1 синхронизации счетчик 4 адресов весовых коэф({)ициентов обнуляется Число состояний счетчика адреса на каждой итерации определяется числом перезаписей счетчика 3 отсчетов, что эквивалентно количеству групп базовых операций.

Для считывания результатов вычислений из блока 14 оперативной памяти в нормальном порядке используется формирователь 6 оперативной памяти, реализующий преобразование двоичного кода g, g, поступающего от формирователя 5 сигналов приращений по формуле

k-(- 1

fg; ,Up

g ;- д;.,+ (mod2), ,

g.-,.

j

где р - номер самого младшего из ненулевых разрядов числа д, при считается SK-I S «.г о о.So двоичный код на выходе формирователя адреса I оперативной памяти

На этапе считывания результатов вычисления спектра сигнала на выход мультиплексора 8 адреса оперативной памяти пропускаются двоичные коды адресов спектральных отсчетов 5,, S . „ о ocoSjjOT формирователя 6 адреса оперативной памяти, которые записываются в регистр 10 адреса оперативной памяти.

При вычислении спектра 2N-точечной действительной последовательности по специальному алгоритму БПФ устройство N Г

ций, а общее количество базовых операций, выполняемое известным устройстN

выполняет V, --т базовых опера-

вом, составляет / --- (ogjN+3)-lo

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

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

блока 14 оперативной памяти так, что на выход коммутатора 15 пропускается сигнал с третьего выхода, на выход коммутатора 16 - с второго выхода блока оперативной памяти 14, а на выход коммутатора 19 пропускается сигнал после элемента НЕ 18, За счет этих коммутаций реализуется выполнение базовой операции стандартного алгоритма БПФ комплексной последовательности. Кроме того, на вход регистра 1 1 адреса постоянной пгмят.-: через мультиплексор 9 адреса постоянной памяти записываются состояния

счетчика 4 адресов весовых коэффициентов. При этом для организации счи- тьюания весовых: коэффициентов в двоично-инверсном порядке в старшие разряды регистра 11 адреса постоянной памяти записываются значения млаших разрядов счетчика 4 адресов весо вых коэффициентов„ Дпя считывания результатов вычислений спектра сигнала из блока 14 оперативной памяти исползуются разряды счетчика отсчетов, знчения которых поступают через мультиплексор 8 адреса оперативной памяти на вход регистра 10 адреса оперативной памяти Для формирования двоично-инверсного порядка следования адресов также используется перестановка разрядов счетчика 3 отсчетов .

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

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

Q г 0

5 о д г

5

0

5

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

и подключен к выходу блока ПОСТОЯ НО

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

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

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

3„ Процессор по пЛ, о т л и - ч ,ч И1 ц и и с я тем, что первый фор ми1- пп:п-ель адреса содержит К-4 :элеЙ

ох

15

38889.210

г.ентов ИЛИ, К-3 сумматоров по модулю два, К-3 коммутаторов, в(,гход i-ro ( К-4) элемента ИЛИ подключен к управляющему входу I-го кот-тмутатора, первый инфop faциoнньri вход которого соединен с первым входом (i+l)-ro сумматора по модулю два и подключен к выходу I-го сумматора по модулю

Q два, первый вход I-го (,K-3) элемента ИЛИ подключен к выходу (j+l)-ro элемента ИЛИ, а первый вход (К-4)-го элемента ИЛИ соединен с управляющим входом (к-З)-го коммутатора и является входом (к-1)-го разряда первого формирователя адреса, выход (К-З) -го сумматора по модулю два подключен к первому информационному входу (К-З)-го коммутатора, второй

20 вход i-ro эл.емента ИЛИ соединен с вторым входом (i+)-ro сумматора по модулю два, вторым информационным входом (i+l)-ro коммутатора.и является входом (i+2)-ro разряда первого

25 формирователя адреса, входом второго разряда которого являются соединенные между собой второй ипформацион- ный вход первого коммутатора и первый вход первого сумт атора по модулю

:jQ два, первьш вход которого является входом первого разряда первого формирователя адреса, выходы коммутаторов объединены с входами первого и К-го разрядов первого формирователя адреса и являются выходом первого формирователя адреса,

4;, Процессор по По , о т л и - чающийся тем, что,второй формирователь адреса содержит К-3 элементов ИЛИ, К-2 сумматоров по модулю два, К-2 коммутаторов, причем выход i-ro (i r К-3) элемента ШТИ подключен к управляющему входу (i + l)-ro кo rмyтaтopa, выход j-ro (, К-4) элемента ИЛИ подключен к первому входу {j+l)-ro элемента ИЛИ, а первьш вход первого элемента ИЛИ соединен с управляющим входом первого коммутатора и являет35

40

45

ся входом К-го разряда второго мирователя адреса, входом 1-го (, К-2) разряда которого являются соединенные между собой второй вход (к-1 )-го элемента ИЖ, первый вход (К-1-1 )-.го сумматора по модулю два, яторой вход (К-1)-го сумматора по модулю два и первый информационный вход (К-1)-го коммутатора, второй информационный вход которого подключен к выходу (к-1)-го сумматора по модулю два, второй вход первого элемента ИЛИ соединен с вторым входом первого сумматора по модулю два, первым информационным входом первого коммутатора и является входом(К-1)-г разряда второго формирователя адреса, входом второго разряда которого являются соединенные между собой первый вход (К-З/то сумматора по модулю два, первый вход (К-2)-го сумматора по модулю два и первый информационный вход (К-2)-го коммута

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

Изобретение относится к области вычислительной техники, в частности к устройствам для спектральноasos ; UHCpafff OtfUU го анализа сигналов, представленных в цифровой форме. Цель изобретения - повышение быстродействия. Поставленная цель достигается за счет того, что в состав процессора входит блок синхронизации 1, счетчик итераций 2, счетчик отсчетов 3, счетчик адресов 4 5 формирователь сигналов приращений 5, формирователи адреса 6,7, мультиплексоры 8,9, регистры адреса 10,11, блок постоянной памяти 12, дешифратор 13, блок памяти 14, коммутаторы 15,16, арифметический ,блок 17, элемент НЕ 18, коммутатор 19 3 ЗоП. ф-лы, 4 ило (/ с tf3u8.t

Фиг.2

А. Г

28 J

/ч /V

/ /

.i

Jt

ZB-

26-2

±L:

±

ffw J

К 8

/tv

Г ч

g-X-j ЭД

«

34L.

Фиг. 5