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

 

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

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

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

РЕСПУБЛИК

„„Я0„, 247891

Ai (5у 4 С 06 Р 15/332

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

3Р, r ч ъ 3%!

%ЖьЛЛ.

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

M АBTOPCKOMV СВИДЕТЕЛЬСТВУ (21) 3863985/24-24 (22) 22.02.85 (46) 30.07.86. Бюл. К 28 (72) Г.В. Зайцев и Н.Е. Нагулин (53) 681.32(088.8) (56) Клан и др. Специализированный процессор для быстрого решения задачгармонического анализа. — Электроника, 1968, т.41, NI 13, с. 3-9.

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

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

Ф ров, а блок формирования дополнитель- ф ного кода содержит К-1 элементов И, К элементов НЕ, К коммутаторов,К-1 одноразрядных сумматоров. 3 ил.

1I 124

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

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

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

Устройство содержит синхронизатор

1, счетчик 2 отсчетов, счетчик 3 итераций, счетчик 4 отсчетов, формирователь 5 сигналов приращений, блок 6 формирования дополнительного кода, мультиплексоры 7 и 8, регистр 9 адреса постоянной памяти, блок 10 постоянной памяти, регистры 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), К элементов

HE (26-1)-(26-К-1), К коммутаторов (27-1)-(27-К-1), К-1 одноразрядных сумматоров (28-1)-(28-К-1) .

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

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

14. В N/2 ячеек памяти комплексных чисел блока 14 оперативной памяти зак. писывается 2N=2 отсчетов действительного сигнала так, что первая половина входной последовательности записывается в ячейки памяти действительной части, а вторая половина — в ячейки памяти мнимой части комплексных чисел.

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

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

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

На второй итерации считывание операндов производится из блока 13 оперативной памяти, а запись результатов вычислений арифметического бло О ка 16 — в блок 14 оперативной памяти.

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

14 оперативной памяти на любой итерации формируется с помощью счетчиков

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

Формирование адресов для считывания операндов в арифметический блок

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

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

Причем для каждой базовой операции в

3 1247 пределах одной группы при считывании операндов в арифметический блок 16 двоичный код адреса второго операнда получается из двоичного кода адреса первого операнда путем инверсии (К+1-j)-ro разряда двоичного кода адреса первого операнда. Это свойство использовано в формирователе 5 сигналов приращений. Для формирования адресов операндов используются 2, 10

3,...,(К+1) разряды счетчика 2 отсчетов. Сигнал с каждого i-ro разряда счетчика 2 отсчетов (i=2,3,.....,К+1) поступает непосредственно на первый вход и через элемент НЕ 17-i íà вто- 15 рой вход коммутатора 19-i-1. Управ,ление коммутатором 19-i-1 осуществляется сигналом с выхода элемента И 20-1-i, на входы ко торого поступают сигналы с (К+2-i) — 20 го выхода дешифратора 18 и с первого разряда счетчика 2 отсчетов, в зависимости от состояния которого на (К+2-i)-й итерации на выход коммутатора 19-i-1 пропускается прямое или 2д инверсное значение сигнала i-ro разряда счетчика 2 отсчетов. Таким образом, на произвольной j-й итерации (j = 1, 2,...,К) по управляющему сигналу с (К+1-j)-ro элемента И

20-К+1-j на вход которого подается сигнал j-ro разряда дешифратора 18, находящийся в единичном состоянии, на выход (K+1-j)-ro коммутатора (19-К+1-j) сначала пропускается сиг35 нал (К+2-j)-го разряда счетчика 2 отсчетов, когда сигнал первого разряда счетчика 2 отсчетов находится в нулевом состоянии, а затем — инверсное. значение (К+2-j)-го разряда

40 счетчика отсчетов с выхода (К+1-j)го элемента НЕ 17-К+1-j в тот мо-. мент, когда сигнал первого разряда счетчика 2 отсчетов находится в единиЧНОМ сОстОянии IIpH этОм послеДО 45 вательно формируются адреса пввого и второго операндов на выходах коммутаторов 19-i (i = 1, 2,..., К) .

Сигналы с выходов коммутаторов

19 i (i = 1, 2, ... K) пропускаются в зависимости от режимов работы блоков 13 и 14 оперативной памяти на выход одного из мультиплексоров 7 и 8 и записываются в соответствующий регистр адреса опера. тивной памяти с тактом следования операндов.

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

891 4 осущестнляется путем параллельной перезаписи сигналов на выходах коммутаторов 19-i (i=1,2,....,К) в соответствующие разряды счетчика 2 отсчетов по выходному сигналу перезаписи формирователя сигналов приращений.

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

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

Формирование адресов для записи результатов вычисления арифметического блока 16 в один из блоков опера" тинной памяти выполняется на основе преобразования счетчика 4 отсчетов.

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

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

В двоичном коде первого результата

S S „ ...S,; где S; = 0 или 1 (i

1,2,...,К), инвертируется старший разряд S „ и выполняется вычисление дОпОлнительнОГО КОда gk g К„ж разрядов Sк-1,Sê-2 $ к,., Получаемый после преобразования двоичный код S„g, g ..eg, 8„; ...8„, где 5 — инверсное значение старшего разряда S, и является адресом второго результата. Формирование адресов записи результатов арифметического блока выполняется в блоке 6 формиро- . вания дополнительного кода. Последовательность фОрмирования адресов уп- . равляется сигналом первого разряда счетчика 4 отсчетов, от селектированного соответствующим сигналом номера итерации с выхода дешифратора.. На произвольной итерации при нулевом состоянии сигнала 1-го разряда счет1247891 чика отсчета на выход блока 6 формирования дополнительного кода пропускаются сигналы 2, 3,...,(К+ 1)-ro разрядов счетчика 4 отсчетов без изменений и используются в качестве адреса.пер. вого результата. Когда сигнал 1-го разряда счетчика 4 отсчетов принимает единичное состояние, выполняется преобразование сигналов 2, 3,..., 1p (K+1)-ro разрядов счетчика 4 отсчетов описанным выше способом. При этом на выход К-го коммутатора 27-К пропускается инверсное значение сигнала К-ro разряда счетчика 4 отсчетов, а на первые входы одноразрядных сумматоров

28-К, 28-К-1,...,28-К-i+1 пропуска-;. ются инверсные значения К-1,...,(К-i+

+1)-го разрядов счетчика 4 отсчетов для вычисления дополнительного кода. gp

В соответствии с операцией дополнительного кода на второй вход сумматора 28-К-i+1 в этот момент подается

"1", для формирования которой используется сигнал с 1-го разряда счетчика 25 отсчетов, отселектированный сигналом номера итерации с выхода дешифратора 18. Полученный после преобразования двоичный код на выходе блока 6 формирования дополнительного кода 3п представляет собой адрес записи второго результата арифметического блока

16 в один из блоков оперативной памяти. !

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

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

Н/2 раз, используются RS-триггеры

23-i (i=1 2,...,Ê-1) и коммутаторы

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

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

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

На К-й итерации все RS-триггеры 23-i (i=1,2,...,К- t) находятся в нулевом состоянии, и при выполнении базовых операций используются соответственно все N/2 значений весового коэффициента в порядке возрастания показателя степени.

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

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

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

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

1247891 ч а ю шийся тем, что, с целью повышения быстродействия, в него вве. дены второй счетчик отсчетов, три мультиплексора, второй блок памяти и .второй регистр адреса, причем выход результата арифметического блока подключен к информационным входам первого и второго блоков памяти, входы чтения записи которых подключены к !О первому выходу синхронизатора, выходь1. первого и второго блоков памяти подключены соответственно к первому и второму информационным входам первого мультиплексора, выход которого подключен к информационному входу арифметического блока, управля,ющие входы первого, второго и третьего мультиплексоров подключены к вто. рому. выходу синхронизатора, входы

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

40 регистра адреса, выход сигнала перезаписи формирователя сигналов приращений подключен к входу разрешения записи первого счетчика отсчетов, входы обнуления и счетные входы пер45 вого и второго счетчиков отсчетов и счетчика итераций подключены соответственно к первому и второму выходам синхронизатора, выходы разрядов группы счетчика итераций подключены к входам второй группы блока формирования дополнительного кода и к информационным входам третьей группы формирователя сигналов приращений, управляющий вход которого подключен к тре-: 5 тьему выходу синхронизатора, причем формирователь сигналов приращений содеры т К+1 элементов НЕ (K=log N, N — размер преобразования), 2 К элементов И, 2 К-1 коммутаторов, К-1

RS-триггеров, дешифратор и элемент

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

j ãî элемента НЕ, выходы ш-х (m=1,К) коммутаторов являются выходами второй группы формирователя сигналов приращений, управляющий вход m-го коммутатора подключен к выходу m-го элемен" та И, первые входы элементов И объе динены и подключены к выходу первого ! элемента НЕ, а второй вход ш-ro элемента И подключен к (К+д-ш)-му выхо ду дешифратора первый вход (К+1)-го элемента И является управляющим. входом формирователя сигналов прира" щений, а второй вход подключен к К-му выходу дешифратора, второй вход (К+

+S) — ro элемента И (S=2, К)подключен к (К+1-S)-му выходу дешифратора, тре- . тий вход подключен к выходу S-го элемента НЕ, выход (K+i)-го элемента

И подключен к i-му входу элемента ИЛИ и первому входу (K+i+1)-ro элемента

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

К-го коммутатора объединены, выход

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

5 одноразрядного сумматора, второй вход которого подключен к выходу (К-i)-ro коммутатора выход переноса m-го (m = 1, К-2) одноразрядного сумматора подключен к входу переноса (m+1)го одноразрядного сумматора, выход

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

1 24 7891

gnat ОтЛ дт Х Om4

Щие. 3

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

Техред N.Ходанич

Корректор М.Самборская

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

Подписное

Заказ 4128/50 Тираж 671

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

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

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