Арифметическое устройство для процессора быстрого преобразования Фурье Советский патент 1984 года по МПК G06F17/14 

1 11

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

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

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

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

Однако в известном устройстве

большой объем требуемой памяти ограничивает размерность, выполняемого БПФ-процессором преобразования, и как следствие этого разрешающую способность спектрального анализа, выполняемого процессором. Действительно известное устройство вычисляет комплексное произведение 7 СW в базовой операции (бабочке) алгоритма быстрого преобразования Фурье с основанием . Здесь С обрабатываемое в данной элементарной операции комплексное число, если обраба03472

тываемые числа представлены в формате с фиксированной запятой, или комплексная мантисса числа, если обрабатываются числа, представленные в фор5 мате с плавающей запя.той, W - поворачивающий мнояштель; k- целое число; , зависящее от выполняемой итерации и номер элементарной операции в ней, N - размерность БПФ преоб0 разования. Это арифметическое устройство вычисляет действительную и мнимую часть Z Zp-f-jZ- (j y-T - мнимая единица) по формулам -f

5 Z fc сМ-Ф (с° R tr/ 1 К3/ 44R or

8

С

/г сЧ-V (с с°1

. ) vl Rbl

Cj, или 1,

где

(fJ.VbUcos-2.

(2) Ч, (U,V).-Usm-gl Vcos 2я1.

NN

и,V 0 или 1,

,е С - значение

Cj, - значение Е-го разряда действительной и мнимой частей операнда С, представленного в дополнительном коде;

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

Требуемые для вычисления преобразования Фурье наборы значений функций Ф(.и) и (U,V) хранятся в первом и втором блоках памяти. Для каждого значения V функции ф и V. могут принимать каждая только по четыре значения, зависящих от двоичных аргументов U,V . Известное арифметическое устройство может применяться в поточной и последовательной, схеме вычисления БПФ. В поточной схеме число значений k и, следовательно, объе памяти зависят от порядкового номера итерации, в которой используется арифметическое устройство, но максимальное число значений, которое принимает k в одном из используемь}х АУ, как и в последовательной схеме вычисления БПФ, равно N/2. Число подается на старишх разрядов адресных входов первого и второго блоков памяти, на два младших разряда которых подаются входные переменные и, V, т.е. адрес требуемой ячейки блоков памяти представляется (р+1)-разрядным числом, которое можно записать следующим образом ,u,v, где , р-2) - значение i-ro разряда в двоичном представлении чисел К. Из сказанного следует, что необходимая емкость памяти арифметического устройства определяется размерностью выполняемого БПФ и для двух блоков памяти равна В (бит) , где В - разрядность функций ф и V. Цель изобретения - сокращение аппаратурных затрат. Поставленная цель достигается тем что арифметическое устройство для процессора БПФ, содержащее первый и второй блоки памяти, информационные выходы которых подключеньТ к информационным входам соответственно первого и второго регистров, первый и второй сумматоры-вычитатепи, выходы которых соединены с информационны ми входами соответственно третьего и четвертого регистров, информационные выходы которых подключены к первым входам соответственно первого и второго сумматоров-вычитателей и являюТся соответственно первым и вторы информационными выходами устройства, а входы старших разрядов адреса первого и второго блоков памяти поразрядно объединены и являются адресным входом устройства, содержит первый и второй мультиплексоры, первый и второй элементы НЕ и первый, второй и третий элементы И, причем первьй вход первого элемента И объединень с первым входом второго элемента И, входом первого.элемента НЕ и является первым информационным входом устройства, второй вход первого элемента И объединен с входом второго элемента НЕ и является вторым информационным входом устройства, выход вто рого элемента НЕ подключен к первому входу третьего элемента И и второму входу второго элемента И, выход кото рого соединен с управляющим входом второго сумматора-вычитателя и управ ляющими входами первого и.второго мультиплексоров, выходы которых подключены к вторым входам соответствен но первого и второго сумматоров-вычитателей, выход первого элемента НЕ соединен с вторым входом третьего элемента И, выход которого соединен с входами бсэнуления первого и второго регистров и управляющими входами первого и второго блоков памяти, входы младших разрядов адреса которых объединены и подключены к выходу первого элемента И, информационный выход первого регистра подключен к первым информационным входам первого и второго мультиплексоров, вторые информационные входы которых объединены и подключешл к информационному входу второго регистра. На фиг. 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 блока. Устройство работает следующим образом. Перед началом вычислений в первый блок памяти вводятся коды функции ,; Vaein(fk.«), Ф 51ПВО второй блок - коды функции -sf 1с; V;-r2co5(-M-K.45°l, Причем адреса ячеек для функции Ф и 4, определяются выражением A--kp- t pа адреса ячеек для функций Ф и 1V выражением ...,. Отметим,что для любого значения в первый и второй блоки памяти записываются только по два числа ф|,фМ и ftf I + Мсоответств,енно, поэтому в памяти прежней емкости число возможным значений адресов 1 может быть вдвое большим, чем в известном варианте арифметического устройтсва. Число значений 1 связано с размерностью максимального выполнимого БПФ преобразования, которое теперь -2N, На информационные входы 12 и 13 в последовательном коде подаются мни мая и действительная части операнда C Cp+jCj. В блоке 1 анализа операндов производится анализ поступающих разрядов операндов и на его выходахвырабатываются сигналы в соответствии с таблицей истинности, где О пассивный уровень, 1 - активный уровень и X - значение сигнала безразлично. Сигнал с первого выхода 22 блока 1 анализа операндов подается на младшие адресные разряды блоков 2 и 3 памяти и выбирает из них функхщи ф. If, если он нулевой, или ф, М если он единичный. При нулевом значении сигнала на втором выходе 23 блока 1 анализа операндов мультиплексоры 6 и 7 находятся в первом положении (к выходу мультиплексора подключен первый его вход), а- второй сумматор-вычитатель 9 в режиме, опре деляемом алгоритмом (1). При единичном сигнале на втором выходе 23 блока 1 анализа операндов мультиплексоры 6 и 7 переключается во второе положение (к выходу мультиплексора подключен его второй вход), а второй сумматор-вычитатель 9 изменяет релсим требуемый по алгоритму (1), на проти воположный, т.е. суммирование на вычитания, вычитание на суммирование. Сигнал с третьего выхода 24 блока 1 анализа операндов подается на обнуляюпщй вход первого 4 и второго 5 регистровой на вход разрешения выбора блоков 2 и 3 памяти. Нулевой сиг176 нал разрешает работу блсУков 2 и 3 памяти и регистров 4 и 5, единичный сигнал запрещает выбор блоков 2 и 3 памяти и обнуляет регистры 4 и 5. В предлагаемом арифметическом устройстве сохраняется принцип формирования комплексного произведения по формуле (1), но из блоков 2 и 3 п мяти выбираются не функции ф (U|YJ, (U|V) , каждая из которых приниV, мает по четыре возможных значения-, для любого, 1, а коды Ф,Ф,| У (их всего 4 для каждого К). Из этих кодов в арифметическом устройстве под управлением сигналов, вырабатываемых блоком анализа операндов, формируются требуемые функции .у)и (ЧV. Ситуация 1. Если на информационных входах 12 и 13 устройства, двоичные переменные (U|V) принимают значения Vr (J 0, то блок 1 анализа операндов вырабатывает активный (единичный) сигнал на третьем выходе 24, который запрещает выбор кодов из блоков 2 и 3 памяти и обнуляет первый 4 и второй 5 регистры, формируя тем тсамым на вторых информационнь х входах первого 8 и второго 9 сумматороввычитателей требуемые (нулевые) значения функции ф, и Vi , т.е. и V, 0. Ситуация 2. Если поступающие на информационные входы двоичные переменные принимают значения (, , то с первого выхода 22 блока 1 анализа операндов на младший разряд адресов блоков 2 и 3 памяти поступает нулевое значение U , из блоков 2 и 3 выбираются коды Ф| и Ц, Мультиплек,- -, , к к соры 6 и 7 находятся в первом положении, позтому на вторые информационные входы.первого 8 и второго 9 сумматоров-вычитателей поступают соответственноф .. (0,11 , k N к ф;-..Ф(0,.}. . Так как в этой ситуации на третьем выходе 24 блока 1 анализа операндов имее место,нулевой сигнал, то оба сумматора-вычитателя работают в режимах определяемых формулами (1), т.е. и в этой ситуации вычисление комплексного произведения 2 осуществляется в соответствии с алгоритмом (1), - (2).

71

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

Следовательно на первый суммат орвычитатель поступает код Ф /ф(1,0), а, с учетом изменения знака на второй сумматор-вычитатель код -y -3in- k V (1,0), что и требуется при вычислении по формулам (1) - (2).

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

ти поступают коды А ,К

K.l, а из блоков памяти выбираются числа k . Мультиплексоры 6 и 7 находятся в первом положении, поэтому 5 на вторые информационные входы первого 8 и второго 9 сумматоров-вычитателей поступают соответственно

ф; (

Ф (l,f)

1)7cos(ljLl.45°) V (1,„.

Оба сумматора-вычитателя работают в режиме, соответствующем операции

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

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

устройство за счет указанных блоков

и связей Позволяет сократить емкость

блоков памяти в два раза.

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

Фиг.1

Фиг. 2