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

 

О П И С А Н И Е (1875387

ИЗОБРЕТЕН ИЯ

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

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

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (6 l ) Дополнительное к авт. свнд-ву (22) Заявлено 04.02.80 (2 I ) 2884810/18-24 (51)М. Кл. с присоединением заявки №вЂ” (28) Приоритет—

G 06 F 15/332

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

СССР ио дедам изобретений и открытий. Опубликовано 23.10.81. Бюллетень № 39 (53) УДК 681.3 (088.8) Дата опубликования описания 23.10,81 (72) Автор изобретения

В. Ф. Коваль

Ордена Ленина институт кибернетики (7I ) Заявитель

ok ..ССР (54) АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО

ДЛЯ БАЗОВОЙ ОПЕРАЦИИ

БЫСТРОГО ПРЕОБРАЗОВАНИЯ (ФУРЬЕ

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

Pi = А + (+BC 2 DS)

= А — (+BC + OS)

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

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

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

Недостатком известного устройства является низкое быстродействие, поскольку базовая операция БПФ вида (1) выполняется в нем в доа этапа через операцию вида (2): (+ 8С + DS)

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

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

875387

1О

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

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

Схема содержит регистр 1 сдвига (первого множителя), регистр 2 (первого множимого), блок 3 преобразования прямого кода в инверсный, сумматоры 4 и 5 (комбинационного типа), накапливающий сумматор 6, регистр 7 сдвига (второго множителя), регистр 8 (второго множимого), блок «1 преобразования прямого кода в инверсный, управляющие входы 10 и 11, выходы 12 и 13.

Функция каждого из блоков 3 и 9 определяется следующим образом.

При нулевом сигнале на соответствующем управляющем входе 10 или 11 выходной код регистра 2 или 8 передается на выход блока 3 или 9 без изменения . При единичном управляющем сигнале осуществляется поразрядная инверсия кода. Передача кода через блок 3 или

9 разрешена, если в выходном разряде регистра сдвига 1 или 7 записана едищща, в противном случае на выходе блока 3 или 9 формируетсн нулевой код.

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

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

В и О, а также число А представлены в модифицированном дополнительном коде, т.е. знак числа записан в двух старших разрядах. Множители С и S представлены в дополнительном коде и в каждом из них имеется еще один служебный разряд, расположенный левее знакового бита.

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

15 го

4

Перед началом вычислений производится одновременная загрузка операндов в регистры 1, 2, 7 и 8, и на управляющие входы устройства

10 и 11 поступают логические нули.

Разряды множимых В и D иэ регистров 2 и 8, логически умноженные на значения битов множителей из регистров 1 и 7, передаются на входы сумматоров без инвертирования (здесь рассматривается работа, когда вычисляется выражение с верхними знаками). На входы переносов сумматоров 4 и 5 поступают логические нули. Одновременно с загрузкой операндов накапливающий сумматор 6 сбрасывается в нуль. На выходе сумматора 5 установится сумма содержимого накапливающего суммато-. ра 6, частного произведения первого множимого и частного произведения второго множимого. Полученная сумма записывается в накапливающий сумматор и сдвигается на один разряд вправо (в сторону младших разрядов). Одновременно с этим производятся сдвиги на один разряд множителей вправо. Эти операции повторяются (М вЂ” 1) раз, где М вЂ” число разрядов множителя.

На М-м такте множимые В и D умножаются на значения знаковых битов множителей

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

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

4 и 5 — знаки соответствующих множителей.

В момент записи скорректированного результата в накапливающий сумматор в регистр 2 первого множимого загружается число А, а в регистр 8 второго множимого числа 2А. Одновременно сдвигается содержимое регистров 1 и 7.

При этом на входы управления выдачей информации блоков 9 поступают служебные биты, равные логическим единицам. На управляющий вход блока 3 подается логический нуль, а второго 9 — логическая единица. Одновременно на вход переноса первого сумматора 4 подается логический нуль, а второго 5 — логическая единица.

На выходе первого сумматора 4 получается алгебраическая сумма числа А с содержанием накапливающего сумматора 6, т.е.

Р1 А + (BC + DS) а на выходе второго сумматора 5 разность числа Р1 у числа 2А, Р = А + (ВС + 08) +

+ 2А + 2 - А (BC + DS), представляющая собой поразрядную инверсию числа Р 2. тя -т1

Тя

5 8

Время выполнения операции (1) в предлага. емом устройстве (Т1) и в известном устройстве (Тэ ) onределяется выражением

Т1 =(М+4) (и+1) г

Тр = (M+3) (й+1) где Ч, N — разрядность множителей и множимых; т — время получения. суммы на один разряд.

Относительный выигрыш в быстродействни— . выражением

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

Арифметическое устройство для базовой операции быстрого преобразования Фурье, содержащее два регистра, два регистра сдвига, два бло ка преобразования прямого кода в инверсный первый сумматор, накапливающий сумматор, причем выход первого.и выход второго регистров подключены соответственно к информационным входам первого и второго блоков преобразования прямого кода в инверсный, управляющие входы которых являются управляннци75387 6 ми входами устройства,. а входы управления выдачей информации первого и второго блоков преобразования прямого кода в инверсный подключены к выходам первого и второго регистров сдвига соответственно, выход накапливающего сумматора подключен к первому входу первого сумматора, выход которого является первым выходом устройства, о т л и ч а ющ е е с я тем, что, с целью повышения быстродействия, оно содержит второй сумматор, выход которого является вторым выходом устройства и подключен ко входу накапливающего сумматора, второй вход первого сумматора подключен к выходу первого блока преобразования прямого коде в инверсный, выход первого сумматора подключен к первому, а выход второго блока преобразования прямого кода в инверсный — ко второму входу второго сумматора.

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

I. Рабинер Л. и Гаулд Б. Теория и применение цифровой обработки сигналов. М., "Мир", 1978, с. 707, фнг. 11.5.

2. Авторское свидетельство СССР N 553613, 2S кл. 6 06 F 7/38, 1976 (прототип).

875387

Составитель В. Байков

Редактор Н. Кончицкая Техред Л.Пекарь

КОРректор С.llloMSK

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4

Закаэ 9335/74 Тираж 748 йод всвое

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

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