Процессор быстрого преобразования фурье

 

Изобретение относится к области вычислительной техники, в частности к устройствам для спектрально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

СОЮЗ СОВ ЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (И) (о(> 4 G 06 F 15/332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н ABTOPCHOVY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТ8ЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4130439!24-24 (22) 30,06,86 (46) 15,04.88. Бил. ¹ 14 (72) Г.В.Зайцев и Н.Е.Нагулин (53) 681.32 (088,8) (56) Рабинер Л., Гоулд Б, Теория и применение цифровой обработки сигналов. И.: Мир, 1978.

Авторское свидетельство СССР № 788114, кл,G 06 F 15/332, 1980, (54) ПРОЦЕССОР БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к области вычислительной техники, в частности к устройствам для спектрального анализа сигналов, представленных в цифровой форме. Цель изобретения— повышение быстродействия. Поставленная цель достигается за счет того, что в состав процессора входит блок синхронизации 1, счетчик итераций 2, счетчик отсчетов 3, счетчик адресов

4, формирователь сигналов приращений 5, формирователи адреса 6,?, мультиплексоры 8,9, регистры адреса

10 11 блок постоянной памяти 12, дешифратор 13, блок памяти 14, коммутаторы 15,16, арифметический блок

17, элемент НЕ 18, коммутатор 19.

3 з.п. ф-лы, 4 ил.

1388892

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

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

На фиг.l приведена функциональная схема процессора быстрого преоб- 10 разования Фурье (БПФ); на фиг.2— функциональная схема формирователя сигналов приращений; на фиг.3 — - функциональная схема формирователя адреса (оперативной памяти); на фиг.4— функциональная схема формирователя адреса постоянной памяти.

Процессор (фиг. 1) содержит блок

1 синхронизации, счетчик 2 итерации, счетчик 3 отсчетов, счетчик 4 адресов весовых коэффициентов, формирователь 5 сигналон приращений, формирователь 6 адреса "оперативной памяти, формирователь 7 адреса постоянной памяти, мультиплексор 8 ад-. реса оперативной памяти, мультиплексор 9 адреса постоянной памяти, регистр 10 адреса оперативной памяти, регистр 11 адреса постоянной памяти, блок 12 постоянной памяти, дешифратор 13, блок 14 оперативной памяти, коммутаторы l5 и lá арифметический блок 17, элемент НЕ 18 и коммутатор

19.

Формирователь сигналов приращений 35 (фиг.2) образуют элементы НЕ 20 — 120-К+1, дешифратор 21 коммутаторы

22-1-22-K элементы Ы 23 -1 — 23 — К, элементы И 24-1 — 24- К и элемент

ИЛИ 25.

Формирователь адреса оперативной памяти включает элементы ИЛИ 26-1

26-К-З, сумматоры 27- 1 — 27-K-2 по модулю 2 и коммутаторы 28-1 — 28-K-2.

Формирователь адреса постоянной памяти (фиг.4) содержит элементы

ИЛИ 29-1 - 29-К-4, сумматоры по модулю 30-1 — 30-К-3 и коммутаторы 31-1

31-K-3.

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

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

Запись последовательности отсчетов55 входного сигнала в блок 14 оперативной памя:ти осуществляется в нормальном порядке.При обработке комплексной последовательности в блоке 14 операК тивной памяти записывается N=2 где К вЂ” целое, комплексных отсчетов сигнала. В режиме обработки действительного сигнала в блок 14 оперативной памяти вводится 2N действительных отсчетов сигнала, причем вторая половина последовательности записывается в ячейки памяти, отведенные для мнимой части М-точечной входной последовательности, далее производятся операции над образованной таким способом М"точечной комплексной последовательностью.

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

В соответствии с графом алгоритма

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

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

Особенностью базовой операции алгоритма БПФ действительной последовательности по сравнению с базовой операцией стандартного алгоритма

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

45 сора 8 адреса оперативной IIB".(яти и мультиплексора 9 адреса постоянной памяти, для реализации базовой операции алгоритма БПФ действительной последовательности дешифратор 13 форми5 рует управлябщий сигнал, по которому на выходы коммутаторов 15 H 16 ггропускаются сигналы соответственно с второго и третьего выхода блока 14 оперативной памяти, а на выход коммутатора 19 пропускается сигнал непосредственно с выхода мнимой части второго результата арифметического блока 17„ f5

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

14 операвтивной памяти.

Порядок выборки входных операндов в арифметический блок !7 и записи результатов вычислений в блок 14 оперативной памяти на любой итерации формируется с помощью счетчика 3 отсчетов и формирователя 5 сигналов 25 приращений. На произвольной i-й итерации (i-l,Ê) базовые операции

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

35 свойство использовано в формирователе 5 сигналов приращений. Для формирования адресов операндов используются 3,4,...,К+2-1 разряды счетчика 4О

3 отсчетов, Сигнал с каждого i-ro разряда счетчика 3 отсчетов (i-3 К+2) поступает через элемент НЕ 20-i — 1 на один вход и непосредственно на другой вход коммутатора 22-1-". (фиг.2). Управление коммутатором

22i-2 осуществляется сигналом с вы хода элемента И 23-i 2, на входы которого поступают с (К+3-iI-го выхода дешифратора 21 и сигнал первого разряда счетчика 3 отсчетов, в зависимости от состояния которого на (К+3-i)-й итерации на выход коммутатора 22-i-2 пропускается прямое или инверсное значение 1-ro разряда счетчика 3 отсчетов. Ha j-й итерации, (j -1,К) по управляющему сигналу с (K+1-j)-го элемента И 23-К+l-i, на вход которого подается сигнал j-ro разряда дешифратс ра 21, находящийся на )-й итерации в единичном состоянии, на выход (К+1-j)-го коммутатора

22-К+1-) пропускается инверсное значение (К+3-j) ro разряда счетчика отсчетов с выхода (К+1-j)-ro элемента НЕ 20-К+1-j в тот момент, когда сигнал первого разряда счетчика 3 отсчетов 3 находится в единичном состоянии. На выходах коммутаторов 22 †(1=1,К) последовательно формируются адрес первого операнда при нулевом состоянии сигнала 1-го разряда счетчика отсчетов и адрес второго оперенда при единичном состоянии сигнала l"ro разряда счетчика отсчетов. Сигналы с выходов коммутаторов

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

14 оперативной памяти, а затем для записи результатов вычислений в блок оперативной памяти по тем же адресам.

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

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

Число перезаписей в счетчик 3 отсчетов определяется количеством групп базовых операций на текущей итерации.

Для формирования сигнала количества групп базовых операций в формирователе 5 сигналов приращений используются элемент ИПИ и элементы И 26-i

i=1,Ê), на входы которых подаются сигналы от дешифратора 2! 3.(К+1)-! разряды счетчика 3 отсчетов и гребенка импульсов от блока 1 синхронизации с периодом, в 2 раза большим периода следования операндов.

1388892

При выполнении базовой операции алгоритма БПФ в арифметической блок

17 по соответствуюшему входу подается значение весового коэффициента из блока 12 постоянной памяти. В блоке

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

S „ 8 „ ...S, поступающий от счетчика 4 адресов весовых коэффициентов по формуле

5 к-2-(, 1 K-2-р

k-2-1

;) S (mod2), I К-2 р, 1=о

30

g,- g.--з. " g. на выходе формирователя адреса постоянной памяти; р — номер самого старшего из ненулевых разрядов двоичного

КОдa Sk-г Sк-З oo 5ою при S,- =О (10,3-2) Р-O.

Результирующий адрес весового коэффициента g „ 9 „, ...д, через мультиплексор 9 адреса постоянной памяти поступает на регистр 11 адреса постоянной памяти.

Организация считывания по алго- 35 с-1

"ритму БНФ íà i-й итерации 2 значений весовых коэффициентов каждое из которых повторяется й/2 раз, осуществляется на основе счетчика 4 адресов весовых коэффициентов, на счетный

40 вход которого подается сигнал перезаписи счетчика 3 отсчетов. Перед началом каждой итерации по сигналу от блока 1 синхронизации счетчик 4 адресов весовых коэффициентов обну-ляется. Число состояний счетчика адреса на каждой итерации определяется числом перезаписей счетчика 3 отсчетов, что эквивалентно количеству групп базовых операций. 50

Для считывания результатов вычислений из блока 14 оперативной памяти в нормальном порядке используется формирователь 6 адреса оперативной памяти, реализующий преобразование 55 двОичнОГО кОда 9 9 юов9 у пО ступающего от формирователя 5 сигналов приращений по формуле ю -р + 9;„+ (пюд2), pi i К-2, к- э

k-<- l

Режим обработки устройством комплексной входной последовательности во многом аналогичен режиму обработки действительной последовательности, поскольку реализуемые специальный алгоритм БПФ действительной последовательности и стандартный алгоритм комплексной последовательности имеют одинаковую структуру. Отличие заключается в следующем. В случае обработки комплексной последовательности при нулевом значении показателя весового коэффициента по управляющему сигналу от дешифратора 13 осуществляется коммутация второго и третьего выходов блока 14 оперативной памяти так, что на выход коммутатора 15 пропускается сигнал с третьего выхода, на выход коммутатора 16 — с второго выхода блока оперативной памяти 14, а на выход коммутатора 19 пропускается сигнал после элемента НЕ 18. За счет этих коммутаций реализуется выполнение базовой операции стандартного алгоритма БПФ комплексной последовательности. Кроме того, на вход регистра 11 адреса постоянной памят. через мультиплексор 9 адреса постоянной памяти записываются состояния где р — номер самого младшего из ненулевых разрядов числа 91 при g=-0 считается р=К;

S„ „ S „ z ...S - двоичный код на выходе формирователя адреса

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

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

N выполняет V = ---. 1о9 N базовых опера2 ций, а общее количество базовых операций, выполняемое известным устройстN вом, составляет \! = --- (lо9 К+3)-1.

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

1S оперативной памяти. Для формирования двоично-инверсного порядка следования адресов также используется перестановка разрядов счетчика 3 отсчетов. 20

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

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

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

1388892

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

2. Процессор по п.l, о т л и— ч а ю шийся тем, что формирователь сигналов приращений содержит

K+1 (K=1og Й, N - -размер преобразователя) элементов НЕ, дешифратор, К коммутаторов, элемент ИЛИ, первую 20 и вторую группы из K элементов И, выход 1-го (i=2, К + 1) элемента НЕ подключен к первому информационному входу (i-1) -ro коммутатора, второй информационный вход которого соединен с входом 1-го эл.емента НЕ, пер- . вым входом i-ro элемента И первой группы и является входом i-ro разряда второго входа формирователя сигналов приращений, первым входом которого является вход дешифратора, 3-й (j = 1,Ê) выход которого подключен к первому входу (К-j+1)-ro элемента И второй группы, 1-й (1=1, K-l) выход дешифратора подключен к второму входу (К-1+1)-ro элемента И

35 первой группы, третий вход которого соединен с (К-1)-м входом элемента

ИЛИ и пеодключен к выходу (К-1)-го элемента И первой группы К-й выход дешифратора подключен к пер»3ому входу первого элемента И первой группы, второй вход которого является третьим входом формирователя сигналов приращений, первым выходом которого является выход элемента ИЛИ, выход первого элемента НЕ подключен к вторым входам элементов И второй

Группь3, управляющии Вход 1 ГО комму татора подключен к выходу j-ro элемента И второй группы, а выходы коммутатopoB 06ъединены и являются вторым выходом формирователя сигналов пр3»раи е3»ий, входом первого разряда второго входа которого является вход

55 первого элемента НЕ, 3. 11роцессор по п.l, о т л и— ч а ю шийся тем, что первый формьн I .OIель адреса содержит К-4 элементов ИЛИ, К-3 сумматоров IT;i и:дулю два, К-3 коммутаторов, выход I Io (i=1, К-4) элемента И .1И подключен к управляющему входу i-го коммутатора, первый информационньп» вход которого соединен с первым входом (i+1) — го сумматора по модулю два и подключен к выходу 1-ro сумматора по модулю два, первый вход i-го (j=l,К вЂ” 5) элемента ИЛИ подключен к выходу (j+I)-го элемента ИЛИ, а первый вход (К-4)-го элемента ИЛИ соединен с управляющим входом (К-3)-ro коммутатора и является входом (К-1)-Io разряда первого формирователя адреса, выход (К вЂ” 3) -ro сумматора по модулю два подключен к первому информационному входу (К-3)-го коммутатора, второй вход i-го элемента ИЛИ соединен с

Вторь3м входом (!+1) — Го сумматора по модулю два, вторым информационным входом (i+1)-го ко3»мут тора и является входом (i+2)-го разряда первого формирователя адреса, входом второго разряда которого являются соединенные между собой второй информационный вход первого коммутатора и первый вход первого сумматора по модулю два, первьп» вход которого является входом первого разряда первого формирователя адреса, выходы коммутаторов объединены с входами первого и

К-ro разрядов первого формирователя адреса и являются выходом первого формирователя адреса, 4. Процессор по п.l, о т л и— ч а ю шийся тем, что,второй формирователь адреса содержит K-3 элементов ИЛИ, К-2 сумматоров по модулю два, К-2 коммутаторов, причем внхвв i-ва ()=Г, К-33 ввемехта

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

1388892

ll чен к выходу (K-1)-го сумматора по модулю два, второй вход первого элемента ИЛИ соединен с вторым входом первого сумматора по модулю два, первым информационным входом первого коммутатора и является входом(К-1)-го разряда второго формирователя адреса, входом второго разряда которого являются соединенные между собой первый вход (К-3)-го сумматора по модулю два, первый вход (К-2)-ro сумматора по модулю два и первый информационный вход (К-2)-го коммутатора, второй информационный вход которого подключен к выходу (К-2)-го сумматора по модулю два, второй вход которого являетея входом первого раз5 ряда второго формирователя адреса, а выход первого сумматора по модулю два подключен к второму",информационному входу первого коммутатора, 1ð выходы коммутаторов, входы первого и К-го разрядов второго формирователя адреса объединены и образуют выход второго формирователя адреса.

1388892

Составитель A.Áàðàíoâ

Техред N.Õîäàíè÷

Редактор А.Огар

Корректор В.Бутяга

Заказ 158?/51 Тираж 704 Подписное

ВНИИПИ Государственного комитета, СССР по делам изобретений и открытий

113035, Иосква, Ж-35 ° Раушская наб., д. 4/5

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