Устройство для преобразованияфурье

 

Iii) 794637

Союз Советских

ОПИСАНИЕ

ИЗОБР ЕТЕ Н И Я

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Социалистических

Рослублик (61) Дополнительное к авт. свид-ву —— (22) Заявлено 07.08.78 (21) 2653196/18-24 с присоединением заявки ¹â€” (23) Приоритет— (43) Опубликовано 07.01.81. Бюллетень № 1 (45) Дата опубликования описания (51) М. Кл. "

6 06 F 15/31

Государственный комитет

СССР ло делам изобретений и открытий (53) УДК 681.14 (088.8) (72) Авторы изобретения

В. Д. Гусев, А. А. Вяльшин и О. Е. Ц1веденко (71) Заявитель Специальное конструкторское бюро «Виброприбор» (54) УСТРОЙСТВО ДЛЯ БЫСТРОГО

ПРЕОБРАЗОВАНИЯ ФУРЬЕ

8 1 Г, А ., i = А + В % ;

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

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

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

Однако эти устройства сложны.

Наиболее близким по технической сущности к изобретению является устройство

3. В этом устройстве выполняется базовая операция с максимальным распараллеливанием арифметических действий с целью достижения наибольшего быстродействия устройства. Устройство 3 для быстрого преобразования Фурье, реализует основные соотношения (1, 2) B;.. = А,.— B;Wt (2) л л

Re (Вт W,) =- Re B; Re W + Im B; In W; (3) j1661fg,"; т;,: ; p-. ;-„: (2

Im(B W,1 = 1т В,.Re W,— Re В;Im W,, (4)

/ где Re u Im — вещественная и мнимая части соответственно.

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

10 подключены соответственно ко входам вещественной и мнимой части первого комплексного числа устройства, содержит сумматоры, регистры, два сумматора-вычитателя, первые входы которых подключены

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

В этом устройстве четыре одновременных действия умножения выполняются с помощью трех множительных блоков, Такая экономия достигается в рсзультате представления тригонометрических коэффициентов в виде отдельных cos О и sill О. а их суммы и разности (т. с. пе в виде

ReF и ImW, а в виде ЯеК+ImW!>

ReW — ImW).

Устройство это имеет асинхронное быстродействие.

Это устройство громоздко и имеет следующие недостатки:

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

БПФ, выполнение таких программ, как сглаживание по Хэммингу, требующее двух суммирующих блоков, разделение вещественных спектров, требующее двух сумматоров-вычитателей, перемножение двух комплексных чисел с сопряжением одного из чисел (или возведение в квадрат одного комплексного числа), требующее двух множительных блоков, одного сумматора и одного сумматора-вычитателя.

2) Требует обращения числового ряда (после перемножения комплексов) для выполнения обратного БПФ (ОБПФ) прп вычислении корреляционной функции.

Т. е. преобразуемый числовой ряд, начиная со второго члена, должен быть «раздернут», в обратном направлении, когда второе число становится последним, третье —— предпоследним, последнее — вторым. Это наиболее простое решение для рассматриваемого устройства — прототипа не требует дополнительных аппаратурных затрат, но требует дополнительных затрат времени, после чего следует стандартное прямое БПФ, дающее оценку корреляционной функции.

3) Быстродействие устройства избыточно при работе с двумя двухмодульнымп

ОЗУ по стандартной схеме: ОЗУ в режиме считывания устройства для БПФ-»-ОЗУ в режиме записи

Цель изобретения — упрощение устройства.

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

)О 6

З0

<0

4 тора знака, входы которых являются входами знака соответственно вещественной и мнимой частей устройства, Управляющие входы управляемых инверторов знака яв. ляются управляющими входами устройства. Выходы у правляемых инверторов знака соединены соотвстственно с первым и вторым входами второго сумматора-вычитателя, третий и четвертый входы которого являются соотистственно входами вещественной и мнимой частей первого числа устройства. Суммирующий и вычитаюгций выходы второго сумматора-вычитателя соединены со вторыми входами соответственно первого и второго блоков умножения, выходы которых соединены соответственно со входами сумматора, выход которого подключен к первому входу первого сумматора-вычитателя, второй вход которого является входом второго числа устройства, а управляющий вход сумматора является входом задания режима устройства. Вход третьего рсгистра объединен со ьходом первого регистра, а вход четвертого регистра — со входом второго регистра. Тактовые входы регистров являются входами синхронизации устройства.

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

Схема предлагаемого устройства на фиг. 1, где обозначены блоки 1, 2 умножения, входы 3, 4 задания коэффициентов, сумматор 5, сумматоры-вычитатели 6, 7, регистры 8 — 11, выход 12 суммы сумматоравычитателя 7, выход 13 разности сумматора-вычитателя 7, управляемые 14, 15 инверторы знака, шины 16, 17 управления инверторами 14, 15 (управляющие входы устройства), знаковая шина 18, и шины 19 вещественной части соответственно первого комплексного числа, шины 20 мнимой части и знаковая 21 шина соответственно первого комплексного числа, шина задания режима 22, шина второго комплсксного числа 23 и шины синхронизации 24 — 27.

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

Базовая операция алгоритма выполняется (как и в прототипе) за время осно„ного тактового импульса. Значение времени такта определяется временем считывания операнда из ОЗУ. Время срабатывания

ЛУ в два с лишним раза меньше времени основного такта. Поэтому для АУ такт представлен двумя полутактовыми импу, ьсами.

794637

5

При выполнении прямого БПФ в течение первого полутакта на входы сумматора-вычитателя 6 поступает первое комплексное число (Re В, + 1т В; ) с прямыми знаками своих вещественной и мнимой частей. Модуль вещественной части Re В, подается на шины 19, знак вещественной части следует по шине 18, к шинам 20 и 21 подключены соответственно модуль Im B; и знак мнимой части. На шину 3 подается тригонометрический множитель (Re Wг,+

+ Im W, ), на шину 4 — тригонометрический множитель (Re W; — Im W, ), на шину задания 22 режима подастся сигнал задания режима суммирования сумматору

5 (нулевой потенциал). По шине 23 второго комплексного числа (Re А, + Iт А, ) поступает его вещественная часть Re A,. На шины синхронизации 24 и 25 подается сигнал разрешения записи информации v, регистры 8 и 9. На шинах 26 и 27 прп этом существует сигнал запрета. В результате имеем на суммирующем выходе сумматора 6 (этот выход подкл1ачсн ко второму входу блока умножения: (Re В; + Im В, ) на вычитающем выходе блока 6 (подключен ко второму входу блока 2) - — (Re Вг— — Im В, ). На выходе блока 1 имеем (РеК,+ Im W ) Х (ReBI + 1mB ), на выходе блока 2 — (Re W,. — I m W, ) (ReB,— — Im В, ), на выходе сумматора 5 — 2 (Re W;ReBI + Iт W, 1mB, ), т. е. сумму этих произведений. Выражение в скобках есть правая часть выражения (3). Полученный результат подается на второй вход сумматора-вычнтателя 7 со сдвигом вправо на один двоичный разряд, т. е. в виде (ReW,. ReВ; + Im W, Im Вг ). Так как на его первом входе существует ReAr, то на суммирующем выходе получим

ReA;+1 на вычитающем (ReB, +1) в соответствии с выражениями (1) и (2), Эти числа запишутся в регистры 8 и 9 соответственно.

В течение второго полутакта на входы сумматора-вычитателя 6 по-прежнему подается первое комплексное число с прямым знаком мнимой части, но с инверсным знаком вещественной части. На шину задания

22 режима подается сигнал задания режима вычитания сумматору 5 (единичный потенциал), а на шину 23 поступает мнимая часть IтА, второго комплексного числа. В результате имеем на суммирующем выходе сумматора 6 (— ReB, + ImBI ), на вычитающем выходе сумматора 6 (— ReB, — IтВ, ), на выходе блока 1 (ReW, + ImW, ) (— ReB, + IтВ, ), на выходе блока 2. — (ReWI — ImW,) (— ReB,— IтВ, ), на выходе сумматора 5 — разность этих двух произведений (Лев, + ImWI ) (— КеВ, + IтВ; ) — (ReW, — ImW,.) (— ReB,.— ImB,) =

=- 2 (ReW; ImB,— ImW;ReBI).

20 п5

Выражение в скобках есть правая часть выражения (4). Полученпь1й результат подается на второй вход сумматора-вычитателя 7 со сдвигом вправо на один двоичный разряд, т. е в виде (ReWI IтВ;— — 1т%/г ReB,. ) . Так как на его первом входе существует 1тА,, то на суммирующем выходе получим IтА;, а на вычитающем — (ImB, + 1) в соответствии с выражениями (1) и (2). Эти числа запишутся в perèñòðû 10 и 11 соответственно, так как на втором полутактс на шины синхронизации 26 и 27 подастся сигнал разрсшсния записи информации, а на шиI.ax 24 и 25 в это время существует запрет, При выполнении обратного БПФ в течение первого полутакта на входы сумматора-вычитателя 6 поступает первое

КОМПЛСКСНОЕ ЧИСЛО С ПРЯМЫМ ЗиаКОМ ВЕщсственной части и инверсным знаком мнимой части, а в течение второго полутакта обс части комплексного числа проходят па входы сумматора-выштатсля 6 с прямыми знаками. Все остальное идентично прямому БПФ, В этом случае после первого полутакта иа выходс сумматора 5 имеем 2 (ReW,ReB, — IinW, IтВ, ), I после второго полутакта — 2 (ReW, 1mB,. +

—, 1mW, ReB; ). Выражения в скобках есть соответственно вещественная и мнимая части произведения первого комплексного числа В, на комплексный тригонометрический сомножитель W, с положительным показателем степени. Таким образом, для выполнения обратного БПФ не требуется обращать числовой ряд исходных чисел.

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

На фиг. 2 показана схема управляемого инвентора 15 знака (инвенторы 14 и 15 идентичны) собранного на элементах И-HF

28 — 32 (Шеффера). Знаковая шина 21 является входной, и на нее подается потенциал знака чисел. Если на шину 17 управления подан «нуль», то элемент 31 закрыт, а элемент 29 открыт через элемент

30 Потенциал знака дважды инвертируется проходя по цепи: шина 21, элемент 29, элемент 32, выход, поэтому значение его не меняется, т. е. инвертор 15 пропускает прямой знак. Если же на шину 17 управления подана «единица», то запирается элсмснт 29 и отпирается элемент 31, потенциал знака следует по цепи: шина 21, элемент 28, элемент 31, элемент 32, выход, т. с. в итоге он инвертируется.

Предложенное устройство работает как и прототип в паре с двумя ОЗУ (каждое

ОЗУ двухмодульное). Схема»x объединения в систему показана на фиг, 3. Первое

ОЗУ 33 в течение всей итерации находится в режиме считывания. Устройство 34 для

БПФ обрабатывает поступающие на его вход пары операндов А; и В, и передает результаты обработки: А;. 1 и 3 +1 на запись в ОЗУ 35, находящемся в течение всего времени итерации в режиме занессния. Режимы ОЗУ задаются по шинам управления 36 и 37. При смене итерации

БПФ цикла ОЗУ 33 и 35 работают в противоположных режимах

Сравнительные диаграммы работы прототипа и предложенного устройства показаны соответственно на фиг. 4 и фиг. 5.

Время т,„ базовой операции для прототипа, если включать сюда время т„, считывания время т,р преобразования и время т„„записи, составляет 2,5 мкс (для определенности считаем т,„= т„„

= 2т„р — — 1 мкс). Но прп этом начала базовых операций отстоят на временной оси друг от друга на 1 мкс. Например, для первых трех базовых операций (фиг. 4а, б, в) это моменты времени, tp, /,„ t>, т. е. поток пар операндов следует с частотой 1 мгц, что и определяется частотой ОЗУ (фиг. 4, г). Но при этом устройство для

БПФ вЂ” прототип участвует в работе половину всего времени цикла. На фиг. 4, д видно, что работает оно например, от t, до

4, а от tq до 1, бездействует. Затем от t3 до

t4 работает и от 14 до t5 вновь бездействует и т. д.

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

1 мкс. Например, для первых трех базовых операций (фиг. 5, а, ж, з) это моменты времени tp, t, 4, как и у прототипа. Т. е. поток пар операндов следует с той же частотой 1 мгц, определяемой частотой

ОЗУ (фиг. 5, и) и как видно по эпюре на фиг. 5r предложенное устройство работает безостановочно, что повышает коэффициент использования оборудования вдвое, т. е. в общей сложности более, чем в 6 раз.

794637

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

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

Источники информации, принятые во внимание при экспертизе

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

Ме 480079 кл. G 06 F 15/34, 1975.

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

421994, кл. G 06 F 15/34, 1974.

3. Бсндат Д. Ж., Пирсон Л. Измерение и анализ случайных процессов. М., «Мир», 1974 (прототип) .

794637 (8 /У 20 Р/

7do

Фиг 4 () / 2 4 4 4 а 7 азиг.5

Фиг /

Редактор Л. Утехина

Заказ 863

Изд. № 138 Тираж 749

11ПО «Поиск» 1 осударствсппого комитета СССР по делам изобретений и открытий

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

Подписное

Загорская типография Упрполиграфиздата Мособлисполкома

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

Техред А. Камьннникова

Корректоры A. Галахова и О. Силуянова