Арифметическое устройство Советский патент 1979 года по МПК G06F7/38 

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

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

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

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

Кроме того, каждая логическая ячейка содержит первый и второй элементы И, элемент ИЛИ, элемент НЕ и сумматор по модулю два, выход которого подключен к первому входу первого элемента И, второй вход - к первому управляющетму входу логической ячейки, выход первого элемента И подключен к первому входу элемента ИЛИ, второй вход которого подключен к выходу второго элемента И, выход элемента ИЛИ является выходом логической ячейки, первый управляющий вход логической ячейки подключен ко второму входу первого элемента И и ко входу элемента НЕ, выход которого подключен к первому входу второго элемента И, второй вход которого подключен к первому информационному входу ячейки, второй информационный вход которой подключен к первому входу сумматора по модулю два, второй вход которого подключен ко второму управляющему входу ячейки.

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

На фиг. 1 приведена электрическая схема предложенного устройства; на фиг. 2- структура логической ячейки.

Устройство содержит одноразрядные сумматоры 1, элементы 2 памяти, логические ячейки 3, входы 4 управления устройством, информационные выходы 5 устройства, информационные входы 6 устройства, информационные выходы 7 устройства, второй информационный вход 8 ячейки, первый вход 9 управления ячейки, вход 10 управления устройством, элемент 11, элемент

НЕ 12, элемент ИЛИ 13, сумматор по модулю два 14.

Арифметическое устройство (см. фиг. 1) состоит из одноразрядных сумматоров 1, каждый из которых имеет первый, второй

и третий входы, вход переноса, выход переноса и выход суммы, элементов 2 памяти и логических ячеек 3. Одноразрядные сумматоры 1 расположены по строкам, каждая из которых содержит одинаковое количество одноразрядных сумматоров 1, строки расположены по вертикали одна над другой и образуют матрицу. Цервые входы всех одноразрядных сумматоров 1 в каждой строке объединены шиной управления

умножением. Шины управления умножением подключены также ко входам 4 управления устройством, второй вход каждого одноразрядного сумматора 1 с номером i, считая слева направо, в каждой строке,

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

сумматора 1, расположенного строкой выше и имеющего номер (i-1), а также с информационным выходом 5 устройства. У крайних левых одноразрядных сумматоров 1 в каждой строке и у одноразрядных сумматоров цервой строки второй вход соединен с выходом элемента 2 памяти, вход которого является информационным входом 6 устройства. Выход переноса начатого одноразрядного сумматора в строке соединен

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

а выходы переноса крайних слева одноразрядных сумматоров каждой строки являются информационными выходами 7 устройства. Третий вход всех одноразрядных сумматоров 1 с номером в строке Л, считая слева направо, за исключением одноразрядных сумматоров первой строки, подключен к выходу элемента 2 памяти, вход которого соединен с выходом логической ячейки 3,

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

вход 8 ячейки 3 является информационным

входом устройства, первый вход 9 управления ячейки 3 является входом управления устройством. Вторые входы управления ячеек 3 в строке объединены и соединены со входом 10 управления устройством. Третий вход одноразрядного сумматора 1, расположенного в верхней строке, подключен к выходу элемента 2 памяти, вход б которого является информационным входом устройства.

Одноразрядный сумматор 1 выполняет операции, как показано в табл. 1.

Таблица 1

Логическая ячейка 3 состоит из первого и второго элементов И 11, элемента НЕ 12, элемента ИЛИ 13 и сумматора по модулю два 14, первый вход которого соединен со вторым информационным входом 8 ячейки, выход соединен с первым входом первого элемента И 11, второй вход которого соединен с первым информационным входом ячейки, а выход соединен со вторым входом элемента ИЛИ 13, первый вход которого соединен с выходом второго элемента ИИ, а выход является выходом ячейки.

Работа арифметического устройства в режиме умножения осуществляется следующим образом.

На входах 9 управления логических ячеек 3 устанавливаются такие значения потенциалов управления, что к выходу логических ячеек 3 оказываются подключенными их первые информационные входы. На входы 6 устройства, являющиеся входами элементов 2 памяти, выходы которых соединены с третьими входами одноразрядных сумматоров 1 первой строки, подключается умножаемое число, представленное в параллельном двоичном коле, причем старший разряд этого числа подключен ко входу элемента 2 памяти, соответствующему крайнему левому одноразрядному сумматору первой строки. На входы 6, соединенные со входами элементов 2 памяти, выходы которых соединены со вторыми входами одноразрядных сумматоров 1 первой строки, также подается код умножаемого числа, сдвинутый на один разряд вправо. На вход 4 щины управления первой строкой подается зправляющий потенциал, соответствующий значению старшего разряда кода множителя.

Рассмотрим числовой пример. Пускай надо умножить число 0,1011 на число 0,1101. Для этого необходимо выполнить операции:

-fO,1011 +0,0000

, 0,1011(1)

+0,1011

0,10001111

На первый и второй информационный входы 6 первой строки поданы числа 0,1011 и 0,01011, на вход управления 4 первой строки - значение второго разряда множителя 0. На информационных выходах 5 первой строки образуется сумма 0,0000 + -f 0,01011 0,01011, которая со сдвигом на один разряд вправо подается на элементы 2 памяти, подключенные к вторым входам одноразрядных сумматоров 1 второй строки. На элементы 2 памяти, соединенные с третьими входами одноразрядных сумматоров второй строки, поступает с выходов соответствуюших элементов 2 памяти первой строки код множителя 0,1011. После этого первая строка в дальнейших вычислениях не участвует. На вход 4 управления второй строки поступает значение третьего разряда множителя 1, во второй строке образуетсясумма 0,1011+0,001011 0,110111. Со сдвигом на один разряд она поступает на вход третьей строки; на другой вход третьей строки поступает код множимого 0,1011, а на вход 4 управления

третьей строки поступает значение четвертого разряда множителя I. Далее вторая строка в вычислениях не участвует. В третьей строке образуется сумма 0,1011 + + 0,0110111 0,10001111, т.е. результат умножения.

Из примера видно, что строки арифметического устройства выполняют вычислительные операции поочередно, одна за другой. Процесс вычисления как бы движется по конвейеру от строки к строке. Таким образом, хотя операция умножения требует выполнения многих операций сложения, но темп ввода данных определяется не полны1 т впрмрнел.г y rнoжeния, а временем выполнения операций суммтфования и переписи в одной строке. Этим обусловлено высокое быстродействие устройства.

Рассмотрим работу арифметического УГТройстпа при вычислении в конвейерном режиме по алгоритму Волдера. Алгоритм Волдера - -это итеоативняя вычислительная процедура, позволяющая находить cfiyHKinn sin fp, os fp .Arc tf (У/Х}, ATc. cis(Y/X, K- 1/Д +, n X. sh rn. Arth

Г7/Л.1/Ж ЛгсШГУШ, . основе алгоритма Волдера лежат вычисления по формулам:

x,x+.j:

Y, X X,,.lУ - У - X -2-

2 - г -z )

Л , + г;У;-12-+ ,,Д,,2--1

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

Т а б .п и 1г а 2

Для; вычислений в конвейерном режиме используются два одинаковых арифметических устройства и устройство управления. В одном арифметическом устройстве производится вычисление Ki, а в другом - г/,-; при этом Хг и г/г ВЫЧИСЛЯЮТСЯ В 1-х строках первого н второго арифметического устройства. Числа хну одновременно поступают на входы 6 первого и второго арифметических устройств. В первой строке первого арифметического устройства производятся вычисления согласно выражению 1 а, табл. 2, а в первой строке второго устройства - согласно выражению 1 б. При этом в первых строках арифметических устройств образзются ДГ и г/i. После этого вычисления по конвейеру переходят ко вторым строкам первого и второго арифметических

устройств, причем во второй строке первого з стройства производятся вычисления согласно вырал ению 2 а, а во второй строке второго устройства - согласно выражению 2 б. Так как при вычислении .tf. необходиМО использовать г/;, а при вычислении УЗ - Xi, то надо передавать результат вычислений каждой предыдущей строки одного из арифметических устройств на вход последующей строки другого ариАметического устройства, а также преобразовывать (при вычитании) передаваемое число из прямого кода в дополнительный (обратный) и умножать на 2- (0,5; 0,25; 0,125 и т. д.).

В описываемом арифметическом устройстве функции передачи и преобразования кодов осуществляют логические ячейки 3, управляемые по входам 10 и 9 устройством л-правления. Сдвиг кодов (умножение на

2-) может быть организован, в частности, за счет конфигурации связей между устройствами.

Логическая ячейка 3 работает следующим образом.

Если на первом входе 9 управ.тения потенциал соответствует уровню логического нуля, то к выходу логической ячейки 3 оказывается подключенным первый информационный вход, если ж& на входе 9 потенциал соответствует логической единице, то на выход ячейки 3 передается логическая переменная второго инфорлганяонного входа 8, просуммированная по модулю два с логическим значением управляющего сигнала входа 10, т. е. логи т-:ля входа 8 в прямом или инверсном виде.

Таким образом, введение т устройство дополпите.яьных логических ячеек F дополнительных информационных и управляющих входов и выходов позволяет его использовать не только для РЬШОЛНОНИЯ в конвейерном режиме операций умножения двоичных параллельных М1 огоразрядных

кодов, но и выполнять вычисления также в конпейерном режиме по алгоритму Волдера с целью выполнения вычислительных операций, необходимых при дискретном преобразовании Фурье, при вычислении элрментарных функций 51Пф, созф Arctg(F/J),

9

ATccig{Y/X),YX, ,X, shcp, Arth (Y/X), Arcth (Y/X), Таким образом существенно расштряется класс задач, решаемых устройством.

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

При вычислении в конвейерное режш.гр необходимо использовать два аоигЬмрттгтеских устройства поедлагаемого типа. Пп;

этом для того, чтобы ПОГПРТПНОСТЬ ВЫЧГТСления Z не ппевосхолчла 10, нpoбxoп: ; тo. чтобы арифметическое УСТРОЙСТВО име.п 8 строк по т разрядов каждая (т - число разрядов в коде исходных величи . и У). Таким образом, всего требуется тУВ одноразрядных сдшматоров и столько же логических ячеек.

При вычислении т. с помощью лттройства-прототипа необходимо сначала найти 2 л;2 -(- г/2 а затем вычислить .г 1/Z с использованием, например, одного из итерационных алгоритАТОв вычисления квадратного корня с использованием умножения.

При этом потребуется не меньнге ДВУХ операций умножения и ДВУХ операшй сложения, а всего, с учетом операций нахождения г, потребуется 4 т одноразрядных сумматоров.

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

г/ Н1 -- Л 47к m

откуда следлет, что ПРИ яг 6 вычисление Z с помощью предлагаемого устройства требует меньщих затрат.

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

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

10

элементов памяти соответственно, выход суммы t-ro (i ) одноразрядного сумматора данной строки подключен к входу первого элемента памяти (i-J-1) одноразрядного сумматора последующей строки, причем входы элементов памяти первой строки и входы переноса первых одноразрядных сумматоров строк являются первой и ВТОЛО- гтмформлпюнных входов устройства соответствентю, выходы иереноса и СУММЫ п,-х одноразрядных сумматоров всех СТРОК являются соответственно первой и группами инфпp aтптoннь x выходов Устройства, отличающееся тем, что, с целью растиирения класса реитаемых задач, стройс во содержит логич сктте ячейки по ЧИСЛУ одноразрядных сумматоров, причем первый 1Пг1лп тят1тгонны1 | вход кажлой г-й логич ской ячейки подключен к ВЫХОДУ соответств ютцего ВТОРОГО элемента памяти, выход - ко входу второго элемента памяти, соотчртствуюитего (i- -П-му одноразрядному сумматорл- последующей строки. вторые инсЬормя.гттгоуньте входы логпческпх ячеек являются третт ей гp ппoй информационных входов устройства, первые управляющие вхояы логических ячеек попключенн ко второй управляюп1ей тине лттройстра.. вторьте лправляющие входы логических строк подключены к третьей группе упрпрляюпитх тин устройства.

принятые во внимание ПРИ экспертизе - 1. Патент ФРГ Хг 2034841. кл. 42шЗ 7/38. 1971.

2. The Radio and Electronic Ensfineer Janyary, 1974, Л 1, p. 21, ф1г. 1 (прототип).