Процессор быстрых дискретных преобразований Советский патент 1992 года по МПК G06F15/332 

(Л

С

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

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

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

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

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

Устройство состоит из двух блоков 1 и 2 памяти, двух блоков 3 и 4 постоянно памяти, сумматора-вычитателя 5, пяти регистров 6-10, регистра 11 микрокоманд, счетчика 12, тактового генератора 13, шести мультиплексоров 14-19, трех триггеров 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, выходы которых соединены с входами

VJ

ho

01

го ю VI

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

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

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 представляют собой таблицы занятости и являются эквивалентом временной диаграммы работы устройства.

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

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

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

может синхронизировать процессор, устанавливая сигнал Треб, ввода в 1.

Вывод данных осуществляется аналогично, но для синхронизации обмена служат сигналы Треб, вывода и Готов, т.е. для

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

После выполнения микропрограммы

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

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

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

на целое число тактов.

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

М ±1, М ±i;

базовая операция БПФ с произвольным вещественным или мнимым множителями

М ± w, М ± jw;

оконные функции: окно Хэннинга, модуль- нокомбинированное окно;

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

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

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

Re(a1) Re(a) + Re(b); Re(b1) (Re(a)-Re(b))-M;

Im(a1)lm(a)(b); lm(b1) (lrn(a)-lm(b))-M,

где М - мнимый либо вещественный поворачивающий множитель.

Табл.1 занятости соответствует выполнению базовой операции БПФ с М ±1. Рассмотрим выполнение этой операции по тактам.

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

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

ТактЗ. Запись Re(a) в Рег.7, запись Re(b) в Рег.6, подготовка записи Рег.7 в Рег.8, для этого мультиплексор 19 коммутируется на Вх.2 под управлением сигнала аи от БУ, сложение на сумматоре-вычитателе 5: Re(a) + Re(b). Для выполнения этой операции на входы КОП сумматора-вычитателя подается код, соответствующий операции сложения, мультиплексоры 15 и 16 выбирают операнды Рег.6 и Рег.7 под управлением сигналов аэ, поступающих от БУ через дешифратор выбора операндов на адресные входы мультиплексоров.

Такт 4. Запись Re(a) в Рег.8, запись Re(b) в Рег.7, запись lm(a) в Рег.6, считывание из ОЗУ lm(b), запись Re(a1) Re(a) + Re(b) с выхода сумматора-вычитателя 5 в Per.9, вычитание Re(a) - Re(b) (в качестве операндов выбираются Рег.8 и Рег.7), подготовка мультиплексора 17 для записи выхода Рег.9 в Per. 10 (для этого БУ выдает соответствующий управляющий сигнал на выход аэ).

Такт 5. Запись Re(a1) в Per. 10 и затем в ОЗУ через мультиплексор 18, запись Re(b1) - Re(a) - Re(b) в Рег.9., сложение lm(a) + lm(b), запись lm(a) в Рег.7, запись lm(b) в Рег.6.

Такт 6. Запись Re(b ) в Per.10 и затем в ОЗУ, запись lm(a1) в Рег.9, вычитание lm(b1) lm(a) - lm(b), запись lm(a) в Рег.8, запись im(b) в Рег.7, подготовка мультиплексора 17 для записи из Рег.9 в Рег.10.

Такт 7. Запись lm(b1) в Рег.9, запись lm(a1) в Рег.10 и в ОЗУ.

Такт 8. Запись lm(b1) в Рег.10 и в ОЗУ.

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

Рассмотрим базовую операцию БПФ с произвольным поворачивающим множителем. Так как устройство предназначено для выполнения гнездовых и простых множителей алгоритмов БПФ, то число разнотипных множителей при ограниченной длине преобразования N 120 составляет от 1 до 6. Так, для длин БПФ 8 и 12 требуется умножение на один тип множителя соответственно и . Произведения всех чисел на эти множители могут быть вычислены заранее и размещены в ПЗУ, поэтому алгоритм такого рода отличается от алгоритма для множителя равного 1 только управляющими сигналами для мультиплексора 17, формируемыми на выходах БУ (см. табл.2).

Окно Хэннинга в частотной области имеет вид

Yk (Xk J 2

(Xk-1 + Xk+i))

1/4(dk-i-dk),

I Yk I (ldk-11- I dk I).

где dk i.Xk-1 - Xk, dk Xk-1 I- IXk + 1 I,

{ I Yk I} - компенсационная последовательность для { I Yk I }k-o .

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

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

I а -МЫ а2 + Ь2 - max la I, I bl + + -y min{ laljbl} .

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

Определить знак Nab в произведении а-Ь:

Nab 0, если а b :0, Nab 1, если а-Ь 0.

Если а Ь 0, то выполнить а - b и запомнить бит переноса Са-ь, если ab 0, то выполнить а + b и запомнить бит знака суммы Na+b.

Сформировать признак того, что I a l I Ы, следующим образом:

h Nab Ca-b + Nab-(Na© Na-b).

Если h 0, то выполнить , иначе а Ь/2, где - операция, выбираемая в зависимости от знаков а и Ь,

Еслиа, b О, то соответствует операции +,

если а 0, b а - операции а/2 - b (а - - Ь/2),

если а 0, b 0, то а/2 + b (-а + Ь/2),

если а О, Ь 0, то -а/2 - b (-а - Ь/2).

Для реализации изложенного алгоритма в микрокоманде, управляющей работой устройства, заведены следующие биты CND: So, Si, Ro, RI, выбор операндов для первого и второго входов сумматора-вычи- тателя (биты ад БУ на фиг.1), (СОР0, COPi, СОР2) - код операции сумматора-вычитате- ля (биты аю БУ на фиг.1).

Дешифратор 29 выбора операндов работает в двух режимах: условного и безусловного выбора операндов в зависимости от бита CND,

В режиме условного выбора операндов бит CND 0 в качестве операнда для сумматора-вычитателя выбирается а/2 и b (если h 0) или Ь/2 и а (если h 1). В режиме безусловного выбора операндов бит CND 1 и значение не влияют на выбор операндов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5

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

Та Ь л и. ч & 1

и. ц О. з

/ О. 5л О; Ц О.

Таблица 5

fc/ 35