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

 

АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО ДЛЯ ПРОЦЕССОРА БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее первый и второй блоки памяти, информационные выходы которых подключены к информационным входам соответственно первого и второго регистров, первый и второй сумматоры-вьмитатели, выходы которых соединены с информационными входами соответственно третьего и четвертого регистров, информационные выходы которых подключены к первым входам соответственно первого и второго сумматоров-вычитателей и являются соответственно первым и вторым информационными выходами устройства, а входы старших разрядов адреса первого и второго блоков памяти поразрядно объединены и являются адресным входом устройства, отличающееся тем, что, с целью сокращения аппаратурньпс затрат, оно содержит первый и второй мультиплексоры, первый и второй элементы НЕ и первый, второй и третий элементы И, причем первый вход первого элемента И объединен с первым входом второго элемента И, входом первого элемента НЕ и является первым информационным входом устройства, второй вход первого элемента И объединен с входом второго элемента НЕ и является вторым информационным входом устройства, выход второго элемента НЕ подключен к первому входу третьего элемента И и второму входу второго элемента И, выход которого соединен с управляющим входом второго сумматора-вычиО ) тателя и управляющими входами первого и второго мультиплексоров, выходы которых подключены к вторым входам соответственно первого и второго сумматоров-вычитателей, выход первого элемента НЕ соединен с вторым входом .третьего элемента И, выход которого соединен с входами обнуления первого и второго регистров и управляющими входами первого и второго блоков памяти, входы младших разрядов адреса которых объединены и подключены к выходу первого элемента И, информационный выход первого регистра подключен к первым информационным входам первого и второго мульти- . плексоров, вторые информационные входы которых объединены и подключены к информационному выходу второго регистра .

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

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

РЕСПУБЛИН

09) (11) ЗОБО G 06 F 15/332

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

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

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

Н ABT0PCKOMV СВИДЕТЕЛЬСТВУ (21) 3604350/ 18-24 (22) 10.06.83 (46) 23. 10.84.Бюл . Ф 39 (72) В.А.Колюскин (71) Московский институт электронной техники (53) 681.32(088.8) (56) 1. Авторское свидетельство СССР

У 480079, кл. G 06 F 15/332, 1973.

2. Liv В., Polet А. А new hardware realization of high-speedi fast

Fourier transfarmers.- IEEE Trans.

Acoustic, Speech and Signal Processing, 1975, 23, Р 6, рр. 543-547 (прототип). (54) (57) АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО

ДЛЯ ПРОЦЕССОРА БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее первый и второй блоки памяти, информационные выходы которых подключены к информационным входам соответственно первого и второго регистров, первый и второй сумматоры-вычитатели, выходы которых соединены с информационными входами соответственно третьего и четвертого регистров, информационные выходы которых подключены к первым входам соответственно первого и второго сумматоров †вычитател и являются соответственно первым и вторым информационными выходами устройства, а входы старших разрядов адреса первого и второго блоков памяти поразрядно объединены и являются адресным входом устройства, о т л и ч а ю— щ е е с я тем, что, с целью сокращения аппаратурных затрат, оно содержит первый и вТорой мультиплексоры первый и второй элементы НЕ и первый, второй и третий элементы И, причем первый вход первого элемента И объединен с первым входом второго элемента И, входом первого элемента НЕ и является первым информационным входом устройства, второй вход первого элемента И объединен с входом второго элемента HE и является вторым информационным входом устройства, выход второго элемента НЕ подключен к первому входу третьего элемента И и второму входу второго элемента И, выход которого соединен с управляющим входом второго сумматора-вычитателя и управляющими входами первого и второго мультиплексоров, выходы которых подключены к вторым входам соответственно первого и второго сумматоров †вычитател, выход перво— го элемента НЕ соединен с вторым входом .третьего элемента И, выход которого соединен с входами обнуления первого и второго регистров и управляющими входами первого и второ.го блоков памяти, входы младших разрядов адреса которых объединены и подключены к выходу первого элемента

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

1 120347

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

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

Однако это устройство. требует большого количества оборудования. 20

Наиболее близким к предлагаемому по технической сущности является арифметическое устройство, содержащее первый и второй блоки памяти, четыре регистра и два сумматора-вы- 25 читателя, причем адресные входы первого и второго блоков памяти соединены с входами устройства, выход первого блока памяти подключен к входу первого регистра, выход которого под-щ0 ключен к второму входу первого сумма— тора-вычитателя, выход последнего соединен с входом третьего регистра, выход которого подключен к первому входу первого сумматора-вычитателя и первому выходу устройства, выход второго блока памяти подключен к входу второго регистра, выход которого подключен к второму входу второго сумматора-вычитателя, выход последнего 40 соединен с входом четвертого регист— ра, выход которого подключен к первому входу второго сумматора-вычита— теля и второму выходу устройства 2 J. !

Однако в известном устройстве 45 большой объем требуемой памяти ограничивает размерность, выполняемого

БПФ-процессором преобразования, и как следствие этого разрешающую способность спектрального анализа, 50 выполняемого процессором. Действительно известное устройство вычис.ляет комплексное произведение Z=С«

М в базовой операции (" бабочке" ) алгоритма быстрого преобразования Фурье 55 с основанием < =2. Здесь С обрабатываемое в данной элементарной операции комплексное число, если обрабатываемые числа представлены в формате с фиксированной запятой, или комплексная мантисса числа, если обрабатываются числа, представленные в фор- . мате с плавающей запятой, W — поворачивающий множитель; к — целое число;

0(k N/2, зависящее от выполняемой итерации и номер элементарной операции в ней, N — размерность БПФ преобразования. Это арифметическое устройство вычисляет действительную и мнимую часть 2= 2+> 2 (1= — 1 — мнимая

R еди н ица) по ф ор мул ам к2 2 Ф IC,<; } — <Р I<:,< ), С, С =Оили 1, где

Ф„(ufV}=ucos " "+Ч„„, (2)

4 (<-<< / } = - << з« вЂ” + V c os

2Й1с 2д 1с

М. N

0,V=O или 1, С, С вЂ” значение 3 --ro разряда

0 действительной и мнимой частей операнда С, представленного в дополнительном коде;

U, V — двоичные переменные.

Требуемые для вычисления преобразования Фурье наборы значений функций Ф (1.1} и Ф(О<Ч} хранятся в первом и втором блоках памяти. Для каждого значения 1< функции фК и 1 могут принимать каждая только по четыре значения, зависящих от двоичных аргументов U,V . Известное арифметическое устройство может применяться в поточной и последовательной схеме вычисления БПФ. В поточной схеме число значений % и, следовательно, объем памяти зависят от порядкового номера итерации, в которой используется арифметическое устройство, но максимальное число значений, которое принимает к в одном из используемых ЛУ, как и в последовательной схеме вычисления БПФ, равно <

2 адресных входов первого и второго блоков памяти, на два младших разряда которых подаются входные переменные u V т. е. адрес требуемой ячейки блоков памяти представляется

3 1120 (p+1)-разрядным числом, которое можно записать следующим образом

t р-2 р-3 о где К (1=0, р-2) — значение 1-ro разряда в двоичном представлении чисел К.

Из сказанного следует, что необходимая емкость памяти арифметичесl0 кого устройства определяется размер— ностью выполняемого БПФ и для двух блоков памяти равна

М =2 2Р B=4N В(бит), где  — разрядность функций Ф и

1с 15

Цель изобретения — сокращение аппаратурных затрат.

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

25 ды которых соединены с информационными входами соответственно третьего и четвертого регистров, информационные выходы которых подключены к первым входам соответственно первого и второго сумматоров-вычитателей и являюГся соответственно первым и вторым информационными выходами устройства, а входы старших разрядов адреса первого и второго блоков памяти поразрядно ооъединены и являются адресным 35 входом устройства, содержит первый и второй мультиплексоры, первый и второй элементы НЕ и первый, второй и третий элементы И, причем первый вход первого элемента И объединены с 40 первым входом второго элемента И, входом первого. элемента НЕ и являет— ся первым информационным входом устройства, второй вход первого элемента И объединен с входом второго эле- 45 мента НЕ и является вторым информа— ционным входом устройства, выход второго элемента НЕ подключен к первому входу третьего элемента И и второму входу второго элемента И, выход кото-5 рого соединен с управляющим входом второго сумматора-вычитателя и управляющими входами первого и второго мультиплексоров, выходы которых подключены к вторым входам соответствен-55 но первого и второго сумматоров-вычитателей, выход первого элемента НЕ соединен с вторым входом третьего

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

На фиг. 1 представлена функциональная схема арифметического устрой ства; на фиг. 2 — блок анализа операндов.

Арифметическое устройство для процессора БПФ (фиг. 1) содержит блок 1 анализа операндов, первый 2 и второй 3 блоки памяти, первый 4 и второй 5 регистры, первый 6 и второй

7 мультиплексоры, первый 8 и второй

9 сумматоры-вычитатели, третий 10 и четвертый 11 регистры, информационные входы 12 и 13 устройства, адресный вход 14 устройства, информационные выходы 15 и 16 устройства.

Блок 1 анализа операндов (фиг.2) состоит из первого 17 и второго 18 элементов НЕ, первого 19, второго 20 и третьего 21 элементов И, выходов

22 — 24 блока.

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

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

Ф = sin; Ф = 2 sin — 1<+ Ф5 а во второй блок — коды функции

v ==ссс k y = сс сас k 44< 1.

k t4 k М

Причем адреса ячеек для функции ф1, и Ч „ определяются выражением

Р 2 а адреса ячеек для функций1 Ф1 и 9

И .Ц1 выражением

Д" 1,Р-",1.Р 2, Отметим, что для любого значения в первый и второй блоки памяти записываются только по два числа(ф1,ф и (, 4 " соответственно, поэтому в памяти прежней емкости число возможным значений адресов k может быть вдвое большим, чем в известном варианте арифметического устройтсва. ЧисФ 1120341 б ло значений 1 связано с размерностью максимального выполнимого БПФ преобразования, которое теперь N =2"2 =26.

На информационные входы 12 и 13 в последовательном коде подаются мни- 5 мая и действительная части операнда

СС +!С . В блоке анализа операндов производится анализ поступающих разрядов операндов и на его выходах. вырабатываются сигналы в соответствии с таблицей истинности, где 0— пассивный уровень, 1 — активный уровень и Х вЂ” значение сигнала безразлично, Выход

Вход

Ситуа ция

22 23 24

12 13

0 1

0 0

1 0

0 0

0 0 Х

0 1 0

0 0

Сигнал с первого выхода 22 блока

1 анализа операндов подается на младшие адресные разряды блоков 2 и 3 памяти и выбирает иэ них функции 35 ф, Ц", если он нулевой, или ф, ф", если он единичный. При нулевом значении сигнала на втором выходе 23 блока 1 анализа операндов мультиплексоры б и 7 находятся в первом положении {к выходу мультиплексора подключен первый его вход), а.второй сумматор-вычитатель 9 в режиме, определяемом алгоритмом {1). При единичном сигнале на втором выходе 23 бло45 ка 1 анализа операндов мультиплексоры 6 и 7 переключается во второе положение (к выходу мультиплексора подключен его второй вход), а второй сумматор-вычитатель 9 изменяет режим, " требуемый по алгоритму (1), на противоположный, т.е. суммирование íà BbI читания, вычитание на суммирование.

Оигнал с третьего выхода 24 блока 1 анализа операндов подается на обнуляющий вход первого 4 и второго 5 ( регистров и на вход разрешения выбора блоков 2 и 3 памяти. Нулевой сиг-, нал разрешает работу блоков 2 и 3 памяти и регистров 4 и.5, единичный сигнал запрещает выбор блоков 2 и 3 памяти и обнуляет регистры 4 и 5.

В предлагаемом арифметическом уст- ройстве сохраняется принцип формирования комплексного произведения по формуле (1), но из блоков 2 и 3 памяти выбираются не функции ф (O,V) * (U, V), каждая из которых прини— мает по четыре воэможньгх значениг. для любого,1с, а коды Ф1„Ф1, Ч 4 .1, (их всего 4 для каждого К). Из этйх кодов в арифметическом устройстве под управлением сигналов, вырабатываемых блоком анализа операнцов, формируются требуемые функции Ф1,(0 V) и

y (o,v) .

Ситуация 1. Если на информационных входах 12 и 13 устройства, двоичные переменные (ЦЧ) принимают значения Ч= Ц =О, то блок 1 анализа операндов вырабатывает активный (единичный) сигнал на третьем выходе 24, который запрещает выбор кодов из блоков 2 и 3 памяти и обнуляет первый

4 и второй 5 регистры, формируя тем

;самым на вторых информационных входах первого 8 и второго 9 сумматороввычитателей требуемые (нулевые) значения функции ф и, т.е. Ф1, =0 и У1, =О.

Ситуация 2. Если поступающие на информационные входы двоичные переменные принимают значения 0 =О, V =1, то с первого выхода 22 блока 1 анализа операндов на младший разряд адресов блоков 2 и 3 памяти поступает нулевое значение U из блоков 2 и 3 выбираются коды Ф и 1 . Мультиплексоры б и 7 находятся в первом положении, поэтому на вторые информационные входы первого 8 и второго 9 сумматоров-вычитателей поступают соответственно ф з,„ =ф (о,

1с ф = 005 — k= 4 (О ), 1 4

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

7 11

Ситуация 3. Если на входы 12 и 13 блока анализа операндов- переменные

U,V принимают значения О =1, V =0 то младший разряд адресных входов блоков 2 и 3 памяти остается тем же (нулевым), что и в ситуации 2, но мультиплексоры 6 и 7 переключаются во второе положение, а второй сумматор-вычитатель 9 изменяет режим работы так, что поступающая на второй его вход информация берется с противоположным знаком.

Следовательно на первый сумматорl вычитатель поступает код ф =сОз k = ф1,(1,0), а, с учетом изменения знака,. на второй сумматор-вычитатель код (Я

-М„,=-з н — „k= 91 (1,0), что и требуется прй вычислении по формулам (1) — (2) .

Ситуация 4. На входах 12 и 13 блока 1 анализа операндов U =1, V =1.

На адресные входы блоков 2 и 3 памя20347 8 ти поступают коды А =К,KР, К,1, а из блоков памяти выбираются числа ф и 4 " . Мультиплексоры 6 и 7 находятся в первом положении, поэтому

5 на вторые информационные входы первого 8 и второго 9 сумматоров-вычитателей поступают соответственно

Ф =12 sin("»+45)=ф (»

e „ = -.I+ » )=»„, .

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

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

Итак, предлагаемое арифметическое

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

1120347

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

Редактор Н. Бобкова Техр ед И. Асталош Корректор С.Черни

Заказ 7744/37 Тираж 698 Подписное

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

113035, Москва, Ж- 35, Раушская наб., д. 4/5 филиал ППП "Патент", г.ужгород, ул.Проектная, 4