Процессор быстрых дискретных преобразований

 

Изобретение относится к вычислительной технике, в частности к цифровой обработке сигналов. Изобретение позволяет реализовать гнездовые алгоритмы быстрых преобразований Фурье и Хартли со спектральными весовыми функциями и модулями комплексных коэффициентов ДПФ с введением программируемого блока формирования адресов и сигналов управления. Цель изобретения - повышение быстродействия. Для этого процессор содержит два блока памяти, блок управления, арифметический блок, содержащий шесть мультиплексоров, пять регистров, сумматор-вычитатель, узел постоянной памяти, три триггера, два дешифратора и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ. 3 ил.,5табл.

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

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

РЕСПУБЛИК (я)ю G 06 F 15/332

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4773584/24 (22) 25.12.89 (46) 07.04,92, Бюл, М 13 (71) Ленинградский механический институт (72) Ю.И.Гагарин и В.В.Шифрин (53) 681.32 (088.8) (56) Авторское свидетельство СССР

М 1278884, кл. 6 06 F 15/332, 1984.

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

hL 1313351, кл. G 06 F 15/332, 1986, (54) ПРОЦЕССОР БЫСТРЫХ ДИСКРЕТНЫХ

ПРЕОБРАЗОВАНИЙ (57) Изобретение относится к вычислительной технике, в частности к цифровой обработке сигналов. Изобретение позволяет

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

Целью изобретения является повышение быстродействия и расширение функциональных возможностей за счет вычисления преобразования Хартли, весовых функций и модуля преобразований.

На фиг.1 — 3 представлены структурная схема и алгоритмы процессора БПФ.

В табл.1 — 4 представлены временные диаграммы различных режимов работы устройства, Устройство состоит из двух блоков 1 и

2 памяти, двух блоков 3 и 4 постоянной памяти, сумматора-вычитателя 5, пяти регистров 6 — 10, регистра 11 микрокоманд, счетчика 12, тактового генератора 13, шести мультиплексоров 14-19, трех тригге,, Ж,„, 1725227 А1 реализовать гнездовые алгоритмы быстрых преобразований Фурье и Хартли со спектральными весовыми функциями и модулями комплексных коэффициентов ДПФ с введением программируемого блока формирования адресов и сигналов управления. Цель изобретения — повйшение быстродействия.

Для этого процессор содержит два блока памяти, блок управления, арифметический блок, содержащий шесть мультиплексоров, пять регистров, сумматор-вычитатель, узел постоянной памяти, три триггера, два дешифратора и элемент ИСКЛЮЧАЮЩЕЕ

ИЛИ. 3 ил„5 табл. ров 20-22, дешифратора 23 кода операции, схем ИСКЛ ЮЧАЮЩЕЕ ИЛИ 24 и 25, ИЛ И

26, И 27 и 28, дешифратора 29 выбора операндов, внешних выходов 30-32 и внешних входов 33 — 36.

При этом выход тактового генератора

13 соединен со счетным входом счетчика

12, выход которого соединен с входом блока 3 постоянной памяти, соединенного выходом с входом регистра 11 микрокоманд.

Выходы блоков 1 и 2 памяти объединены и соединены с внешним выходом 30 и с одним из информационных входов мультиплексора 14, выход которого последовательно через регистры 6 и 7 соединен с одним из информационных входов мультиплексора 19, соединенного выходом через регистр 8 с первыми информационными входами мультиплексоров 15 .и 16, выходы которых соединены с входами

1725227

30

40

50

М=- +1,Ì= +i;

+м, M = +.ум; данных сумматора-вычитателя 5, соединенного выходом данных через регистр 9 с одним из информационных входов мультиплексора 17, второй информационный вход которого соединен через блок по- 5 стоянной памяти также с выходом регистра

9. Выход мультиплексора 17 через регистр

10 соединен с вторым информационным входом мультиплексора 14 и с одним из информационных входов мультиплексора 18, 10 выход которого соединен с объединенными входами данных блоков 1 и 2 памяти. Вход

35 данных соединен с вторым информационным входом мультиплексора 18. Адресные и управляющие чт,зп-входы блоков 15 памяти, управляющие входы мультиплексоров 14, 19, 17 и 18, часть входов дешифратора 23 кода операции и дешифратора 29 выбора операнда, выходы 31 и 32 соединены с соответствующими выходами регистра 20

11 микрокоманды. Старшие (знаковые) разряды регистров 6 и 7 объединены на входах схемы ИСКЛЮЧАЮЩЕЕ ИЛИ 24, выход которой соединен с входом первого. триггера

22, и с одним из входов дешифратора 23 кода операции, соединенного выходом с управляющим входом сумматора-вычитателя

5. Выход дешифратора выбора операндов соединен с управляющими входами мультиплексоров 15 и 16, информационные входы которых соединены с соответствующими выходами регистров 6 — 10. Внешние входы

33, 34 и 36 соединены с входами соответствующих схем И 27 и 28 и схем ИЛИ 25 и 26, соединенных выходами с управляющими входами счетчика 12. Входы триггеров 20 и

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

Заметим, что табл.1 — 4 представляют собой таблицы занятости и являются эквивалентом временной диаграммы работы устройства.

При включении питания схема начальной установки блока управления формирует импульс "Начальная установка", который сбрасывает счетчик микрокоманд (МК). Начиная с нулевого адреса в ПЗУ МК, расположена микропрограмма ввода данных в ОЗУ процессора. Во время ввода данных бит Готовность ввода" устанавливается в "0", что сигнализирует внешнему источнику данных о том, что процессор готов принять данные, Если данные сформированы, то источник данных устанавливает сигнал

"Требование ввода" в "0". Если процессор установил сигнал "Готовность ввода" при

"1" на входе "Треб, ввода", то на выходе вентиля И-ИЛИ устанавливается "1" и счетчик МК не будет. принимать тактовые импульсы, пока сигнал "Треб. ввода" не станет равным "0". После этого с каждым тактом источникданных выставляетданные на входе процессора, который, формируя сигналы записи и адреса, записывает данные в свое

ОЗУ. Если скорость поступления данных ниже тактовой частоты, то источник данных может синхронизировать процессор, устанавливая сигнал "Треб. ввода" в "1".

Вывод данных осуществляется аналогично, но для синхронизации обмена служат сигналы "Треб. вывода" и "Готов", т.е. для выполнения микропрограммы ввода (вывода) данных необходимо как минимум 2N+ 1 тактов (N тактов для действительной и N— для мнимой частей).

После выполнения микропрограммы ввода выполняется микропрограмма БПФ, вычислений "окна" и модулей комплексных взвешенных коэффициентов, а затем — микропрограмма вывода данных. По окончании вывода формируется сигнал сброса счетчика ИК и вводится новый входной вектор.

Микропрограммы, выполняемые предлагаемым устройством, не содержат циклов и условных переходов, поэтому на выходе регистра МК устанавливается индивидуальное для каждого такта управляющее слово, что позволяет оперативно менять временную диаграмму от одной базовой операции к другой, не имея для этого специальных аппаратных средств, Блок памяти процессора представляет собой дуальный буфер, каждый банк которого имеет свои сигналы управления 4т, Зп, ВК и адрес, такжеформируемые микропрограммно. Два банка блока памяти работают в противофазе: когда в один из них производится запись данных, с второго производится считывание. В любом такте имеется возможность считать, записать данные по любому адресу памяти или не обращаться к нему, формируя задержку на целое число тактов.

Рассмотрим работу устройства по следующим базовым операциям: базовая операция БПФ с тривиальными множителями, равным базовая операция БПФ с произвольным вещественным или мнимым множителями оконные функции: окно Хэннинга, модульнокомбинированное окно;

1725227 вычисление модуля комплексного числа.

Будем полагать, что все операции записи в регистры осуществляются по переднему фрону ТИ.

Базовая операция БПФ представляет собой операцию вида

Re(a ) = Re(a) + Re(b);

Re(b ) = (Re(a) — Re(b)) М;

Im(a ) = Im(a) + Im(b);

Im(b1) = (Im(a) — Im(b)) M, где М вЂ” мнимый либо вещественный поворачивающий множитель.

Табл.1 занятости соответствует выполнению базовой операции БПФ с М =+1.

Рассмотрим выполнение этой операции по тактам.

Такт 1, Считывание Re(a) из ОЗУ.

Такт 2. Запись Re(a) с Рег.6, считывание из ОЗУ Re(b).

Такт 3. Запись Re(a) в Рег.7, запись Re(b) в Per.6, подготовка записи Рег.7 в Рег.8, для этого мультиплексор 19 коммутируется на

Вх.2 под управлением сигнала aii от БУ, сложение на сумматоре-вычитателе 5: Re(a)

+ Ке(Ь). Для выполнения этой операции на входы КОП сумматора-вычитателя подается код, соответствующий операции сложения, мультиплексоры 15 и 16 выбирают операнды Per.6 и Рег.7 под управлением сигналов

ag, поступающих от БУ через дешифратор выбора операндов на адресные входы мультиплексоров.

Такт 4. Запись Re(a) в Рег.8, запись Re(b) в Рег.7, запись Im(a) в Per.6, считывание из

ОЗУ Im(b), запись Re(a ) = Re(a) + Re(b) с выхода сумматора-вычитэтеля 5 в Рег.9, вычитание Re(a) — Re(b) (в качестве операндов выбираются Рег.8 и Рег.7), подготовка мультиплексора 17 для записи выхода Рег.9 в

Рег.10 (для этого БУ выдает соответствующий управляющий сигнал на выход ад).

Такт 5. Запись Re(a ) в Per.10 и затем в ОЗУ через мультиплексор 18, запись

Re(b ) = Re(a) — Re(b) в Рег.9., сложение

Im(a) + Im(b), запись Im(a) в Рег.7, запись

1п (Ь) в Рег,6.

Такт 6. Запись Re(b ) в Per.10 и затем в ОЗУ, запись Im(a ) в Рег.9, вычитание

Im(b ) = Im(a) — Im(b), запись Im(a) в Рег.8, запись im(b) в Рег.7, подготовка мультиплексора 17 для записи из Рег.9 в Рег.10.

Такт 7. Запись Im(b ) в Рег,9, запись

Im(a ) в Per.10 и в ОЗУ.

Такт 8. Запись Im(b ) в Рег.10 и в

О 3 У.

Эта операция занимает восемь ТИ, но с учетом конвейерной обработки следующая

5 операция может быть начата после четырех

ТИ от начала выполнения.

Рассмотрим базовую операцию БПФ с произвольным поворачивающим множителем. Так как устройство предназначено для

10 выполнения гнездовых и простых множителей алгоритмов БПФ, то число разнотипных множителей при ограниченной длине преобразования N <120 составляет от 1 до 6.

Так, для длин БПФ 8 и 12 требуется умноже15 ние на один тип множителя соответственно

V2 /2и КЗ /2. Произведения всехчисел на эти множители могут быть вычислены заранее и размещены в ПЗУ, поэтому алгоритм такого родэ отличается от алгоритма для

20 множителя равного 1 только управляющими сигналами для мультиплексора 17, формируемыми на выходах БУ (см. табл.2), Окно Хэннинга в частотной области имеет вид

Yk = — (Xk — — (Xk-1 + Xk+1)) =

1 1

2 2

=1/4 (dk-1 — dk), 30 ! Yk = — (Idk-1 1-1 dk1), 4 где dk = Xk-1 — Хк, 1dk!= I Xk-1 1 — Ixk+11, 35 { I Yk I } — компенсационная последовательность для {1Ук1}k-о

B табл,4 представлена диаграмма занятости в приведенных обозначениях, причем для вычисления каждого нового Ук исполь40 зуется dk->, уже вычисленное для Yk->, что позволило сократить время для вычисления каждого нового Ур до двух тактов.

Вычисление модуля комплексного числа производится по приближенной форму45 ле, например

1 a +ial = ax+ax =max Ital, I a l)+

+ 21 min f I a I, I Ь 1 .

Алгоритм вычисления модуля имеет следующий вид (в соответствии с табл.3).

Определить знак Nat в произведении

55аЬ:

Nab = О, если à . b 0, Nab= 1, если а.b< О.

Если а b> О, то выполнить а — Ь и запомнить бит переноса Ce-b, если ab< О, то вы1725227

10 полнить а + Ь и запомнить бит знака суммы

Na+b.

Сформировать признак того, что

I à I> I Ы, следующим образом:

h = Nab Са-Ь + Nab (Na® Na-b) Если h = О, то выполнить а/2 Ь, иначе а т b/2, где м. — операция, выбираемая в зависимости от знаков а и Ь, Если а, Ь > О, то * соответствует операции "+", если а О, b < а — операции а/2 — b (а—

- Ь/2), если а< О, Ь > О, то а/2 + b (— а + Ь/2), если а< О, Ь< О, то-а/2 — Ь(-а — b/2).

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

CND . So, S1, Rp, R1, выбор операндов для первого и второго входов сумматора-вычитателя (биты ag БУ на фиг.1), (COPo, СОР1, COPz) — код операции сумматора-вычитателя (биты акр БУ на фиг.1).

Дешифратор 29 выбора операндов работает в двух режимах: условного и безусловного выбора операндов в зависимости от бита CND, В режиме условного выбора операндов бит CND = О в качестве операнда для сумматора-вычитателя выбирается а/2 и Ь (если h= О) или Ь/2 и а (если h= 1). В режиме безусловного выбора операндов бит CND = 1 и значение не влияют на выбор операндов.

Условный выбор операндов осуществляется, если СОР(а1о) = 111. В этом случае

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

Знаки индицируются двумя битами: знак аЬ и знак а.

Логика выбора КОП приведена в табл.5.

В режиме безусловного выбора КОП знаки ab и а не влияют на выбор КОП для сумматора-вычитателя, который определяется только битами а1р, принимающими значения от 0002 до 1102.

Условный выбор КОП сумматора-вычитателя реализован в дешифраторе выбора операндов 23.

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

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

55 информационному выходу процессора и к первому информационному входу арифметического блока, второй информационный вход которого является информационным входом устройства, первый и второй адресные выходы блока управления подключены к адресным входам соответственно первого и второго блоков памяти, входы управления записью-считыванием которого подключены соответственно к первому и второму тактовым выходам блока управления, третий тактовый выход которого подключен к первому тактовому входу арифметического блока, отличающийся тем, что, с целью повышения быстродействия и расширения функциональных возможностей за счет вычисления преобразования Хартли, весовых функций и модуля преобразований, тактовые выходы с четвертого по девятый блока управления подключены к тактовым входам соответственно с второго по седьмой арифметического блока, причем арифметический блок содержит шесть мультиплексоров, пять регистров, сумматор-вычитатель, узел постоянной памяти, три триггера, два дешифратора и элемент ИСКЛЮЧАЮЩЕЕ

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

1725227!

О,KAи.(- CL У

50 шестого мультиплексора, выходы знаковых разрядов первого и второго регистров подключены соответственно к первому и второму входам элемента ИСКЛЮЧАЮЩЕЕ

ИЛИ, выход которого подключен к первым входам первого и второго дешифраторов и тактовому входу триггера, выход которого подключен к втормы входам первого и BTG рого дешифраторов, третьи входы которых подключены к знаковому выходу третьего регистра, выход первого дешифратора подключен к управляющему входу сумматоравычитателя, выходы переноса и знака которого подключены к тактовым входам соответственно второго и третьего триггеров, выходы которых подключены соответственно к -четвертому и пятому входам второго дешифратора, выход которого подключен к

5 управляющим входам второго и третьего мультиплекссров, тактовые входы всех регистров подключены к первому тактовому входу арифметического блока, к тактовым входам с второго по седьмой которого под10 ключены соответственно управляющие входы первого, четвертого, пятого, шестого мультиплексоров. четвертый вход первого дешифратора, шестой вход второго дешифраторэ, 15

1725227 (;z

1725227

16

1725227

Таблица 5

pubs/

1725227 х(о) 10

Редактор С.Пекарь

Заказ 1177 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

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

Фиг.5

Техред М.Моргентал Корректор Э.Лончакова

Х() и