Арифметическое устройство

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено 30.03.76 (21) 2342197/18-24 с присоединением заявки № и 1 650074 союз Оаветских

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

Республик

84 ут .--/ фД// а)т

"::Й;8,".::;ле / (51) М. Кл 2

G 06F 7/38 (43) Опубликовано 28.02.79. Бюллетень № 8

l(45) jI,ата опубликования описания 28.02.79 (53) УДК 681.325 (088.8) по делам изобретений и открытий (72) Авторы изобретения

Ю. А. Хаскин и Е. М. Репетюк (71) Заявитель (54) АРИФМЕТИЧЕСКОЕ УСТРОИСТВО

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

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

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

Наиболее близким по технической сущности к изобретению является матричное арифметическое устройство, содержащее одноразрядные сумматоры, расположенные по строкам, по и сумматоров в каждой, причем выход переноса каждого одноразГосударственный комитет (23) П рядного сумматора подключен ко входу переноса последующего одноразрядного сумматора той же строки, управляющие входы в одноразрядных сумматоров подключены к первой управляющей шине устройства, первый и второй входы одноразрядного сумматора подключены к выходам первого и второго элементов памяти соответственно, выход суммы 1-го (i = 1 —:n) одноразрядно1п го сумматора данной строки подключен ко входу первого элемента памяти (i+ 1) -го одноразрядного сумматора последующей строки, причем входы элементов памяти первой строки и входы переноса первых

1; одноразрядных сумматоров строк являются первой и второй группами информационных входов устройства соответственно, выходы переноса и суммы lт-х одноразрядных суMматоров всех строк являются соответствен20 но первой и второй группами информационных выходов устройства (2). Кроме того, в известном устройстве выход второго элемента памяти каждой строки, соответствующего i-му одноразрядному сумматору, 2ч подключен ко входу второго элемента памяти следующей строки, соответствующего

1-му одноразрядному сумматору.

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

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

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

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

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

И подключен к первому входу элемента

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

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

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

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

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

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

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

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

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

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

650074 положенного в верхней строке, подключен к выходу элемента 2 памяти, вход 6 которого является информационным входом устройства.

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

Таблица 1

В х о д

В ы х о д

М операции У " второй фТ- -. -) переноса третий

Б; первый переноса суммы

2

4

6

8

11

12

13

14

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

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

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

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

Рассмотрим числовой пример. Пускай надо умножить число 0,1011 на число

0,1101, Для этого необходимо выполнить операции:

+О, 1011

+0,0000

0,1011

0,1011

0,10001111

На первый и второй информационный входы 6 первой строки поданы числа 0,1011 и 0,01011, на вход управления 4 первой строки — значение второго разряда множителя О. На информационных выходах 5 первой строки образуется сумма 0,0000+

+ 0,01011 = 0,01011, которая со сдвигом на один разряд вправо подается на элементы

2 памяти, подключенные к вторым входам одноразрядных сумматоров 1 второй строки. На элементы 2 памяти, соединенные с третьими входамп одноразрядных сумматоров второй строки, поступает с выходов соответствующих элементов 2 памяти первой строки код множителя 0,1011. После этого первая строка в дальнейших вычислениях не участвует. На вход 4 управления второй строки поступает значение третьего разряда множителя 1, во второй строке образуется сумма 0,1011 + 0.001011 =

= 0,110111. Со сдвигом на бдин разряд она поступает на вход третьей строки; на другой вход третьей строки поступает код множимого 0,1011, а на вход 4 управления

650074

Л,— Ë.+r:,у;

У,= Y — :,Л ;

X, = Ë, + l Yr 2-

Y, = Y, — ",Y,.2- ; таблиц", 2

M операции

60 б5

2

Х,=Х+1

Х,=Х,— 0,5Y„

Х,=Х +0,251, 1,=Y — Х

Y =Y+0,5Х 1 з= Yÿ — 0,25Х третьей строки поступает значение четвертого разряда множителя 1. Далее вторая строка в вычислениях не участвует. В третьей строке образуется сумма 0,1011 + вЂ, - 0,0110111 = 0,10001111, т. е. результат умножения.

Из примера видно, что строки арифметического устройства выполняют вычислительные операции поочередно, одна за другой. Процесс вычисления как бы движется по конвейеру от строки к строке. Таким образом, хотя операция умножения требует выполнения многих опеоаций с.чожения, но темп ввода данных оппеделяется не по.чНЫМ ВП МеНЕМ ЧМнО>«ЕНИЯ, а ВРЕМЕНЕМ Bbrполнения операций суммирования и пепеписи в одной стпокс. Этим об ссловлено высо«ос быстродействие устпойства.

Рассмотрим работ ависЬметического . стпойстпа пои вычислении R конвейепном режиме по алгоритму Волдера. Ллгопитм

Волдера — )TA итспативная вычнслител«ная пропел па. позволяющая находить зпа."fear Ж; н«пцй яп сс, поз rr . 1гс Ьу (У/Х}, ."«гс cto (Y!Х}, К ) Х +У, 1п Х. Bh rr. Лгй (У!Х},1 Х, Arctb (У(Х}, К.1бЛ +У .В основе алгоритма Волдера лежат вычисления по формулам:

Л; = Л < «+ =, Y« 12- +

Y, = Yrr — l, Ë rr2- -

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

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

В одном арифметическом устройстве про10

З

50 изводится вычисление хь а в другом — у«; при этом х; и у«вычисляются в «-х строках первого и второго арифметического устройства. Числа х и у одновременно поступают на входы б первого и второго арифметических устройств. В первой строке первого арифметического устройства производятся вычисления согласно выражению 1 а, табл. 2, а в первой строке второго устройства — согласно выражению 1 б. При этом в первых строках арифметических устройств образуются х| и ur. После этого вычисления по конвейеру переходят ко вторым строкам первого и второго арифметических устройств, причем во второй строке первого устройства производятся вычисления согласно выражению 2 а, а во второй строке второго устройства — согласно выражению

2 б. Так как при вычислении х. необходимо использовать д., а при вычислении у — xr, то надо пере,чавать результат вычислений каждой предыдущей строки одного из арифметических:стройств на вход последующей строки другого арифметического устройства, а также преобразовывать (при вычитании) передаваемое число из прямого кода в,чопо,чнительный (обпатный) и умножать на 2 — (0,5; 0,25; 0,125 и т. д.) ..

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

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

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

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

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

:онпейпрном режиме по алгоритм Волдера с целью выполнения вычислительных операций, необходимых при дискретном преобразовании Фурье, при вычислении эл-ментарных функций sin р, cos «р Arc tg (Y/Õ);

650074

Arcctg (Yt Õ),рА, К Л +У 1ПХ, Агth (Y/Õ), Arcth (Y/Õ), К1/X — У . Таким образом существенно расширяется класс задач, решаемых устройством.

Для оценки эффективности использования преллагаемого устройства свавним аппаратурные затраты, необходимые лля в?.тчисления функции вила z = К1/Л +У с помощью предлагаемого устройс ва и устройства-прототипа.

При вычислении в когтвейтерно.т DPF«1?i;n.. необходимо использовать лвя авиф?.?Ртиче— ских устройства пведлягаемого т тпя. Гт > этОМ TIJIH rorо, чтобы ления z не Hpегоcxoлчла 10-, нР01 хо . n. чтобы арифметическое;стпойствР ??мел 8 строк по т разрядов тля>кляя Fm — чис. п

Разрялов в коде исхолных вел?тчи?1 Х и У1.

Таким образом, всего требуется пт, к 8 от.норазрядных сумматовов и столько жс,?0ГИ ТРСКИХ ЯЧЕЕК.

При вычислении z с помощью стройства-прототипа необходимо сначала Fla "ти г = х + tP а затем вычислить z — g/Z с использованием, напри? тер. олного из итерационных алгоритм?ОН вычислен?лч квадратного корня с использованием с".1110>тления.

При этом потребуется пе мен?.тпс лв х операций у.лножения ", двух опеоацттй c..lnжения, а всего, с учетом опеРяпий нахожления Р, потребуется 4m олнорязря".ных сумматоров.

Учитывая, что логическая ячейка примерно в двя раза про?де олновязпялного

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

24m 6

ГК

4т т откуда следх T, что пDè т ) 6 вы и c,÷PíHе с помощью предлагаемого уствойствя требует меньтпих затрат.

Формула иaîбретения !. Арифметическо". i.стро?" Сво, cолер кащее одноразрядны сумматопьк расположенныее по стро«ям, по и в «а.клой, р;«Tp.. выхол переноса каждого олноразпя;тчого сумматора подключен ко вход. пепснося

ПОСЛЕДУЮЩЕГО ОДНОРаЗРЯЛНОГО СХ ММЯтОР3

Т0Н же строки, управляющие входы одноразрядных схмматоров подклточен?-т «ПРРвой управляющей шине устройства, пепв. ":, и втоРой входы одпоразрялного схммятРра подключены к выходам TTPDBorn и второ?.п элементов памяти соответственно, выход суммы I.-lo (t. = 1 —:и) одноразрядного сумматора данной стро«п подключен к входу первого элемента памяти (i 1) одноразрядного сумматора последующей строки, причем входы элементов памяти первой строки и входы переноса первых одноразрядных сумматоров строк являются первой

;1 RTnDn;, Грт Ппямп и .:??DODS!3 f10}IT!bf I ВХО IOB устройства соответствеFIEIo, выходы переноСа И СУ лМЫ П,-Х Î I!IОРаЗРЯЛНЬТХ СУММатОРОВ всех стг?Р« являются соответственно первой

ТТ "- npn 1 ГТТУТтпа 11!1 1?нфоп таттf?n××ÛÕ ВЫХО IOB

YcòD0écòRa, Отлпчающp.еся тем, что, с пе .ю Ряспщг>ет?ия к.тасся РР?паемь!х задач, т СтРОЙС во Солс Ржчт ЛОГПЧ СКИЕ ЯЧЕЙКИ ПО

"f .?cë " однооязря тных c Ala!a TopoB. прттче т

HРвВ111? 1 !1?Т1Г101Тя "1 101 111!11 RXO;I Tiaж Той t- — и л? гпческой ячсй«п полкл?О IPH к выход - cooxR xc R ющего втoporo элемента памяти, r..fX0 — КР ВХОЛ ВтОРОТО ЭЛЕМЕНтя ПаМЯти, cnn f--;Р-тствт ют?тс Го (1- -1l -м олновазРялном, л ммятот» пос.тел ющсй cTpo«ff.

ВТРР? > ТтнфРР ?3111?Р! ITl.т" Вхо lhl, тоГ?тчРскпх я еск являются трет?,ей грмппой пнфовмаIfT?oHF;b? F ВхОПОВ Уст?тоттства пеРВые х.ппав

ЛЯЮТТ ТТЕ Г1ХО:ТЬТ ЛОГ?? ТСРТ<ТТХ ЯЧЕЕК ПОЛКЛЮЧСíf.т Тсп RToD0!f ттоявлятоптс!1 ?111111 4 стРОЙстR3. з-0?1ь?Р упоавляющ??с вхРлт.т логических я1?РР« ствок полк.лточеньт к третьей группе упт> Тля?от???тх тпт;н устройства.

2. УстРОйетт.О пп П. 1, ОтЛ И Ч я ТО T!I p ЕС я

ГР т. что кяжляя логттчест яя ячетт«а Родер>i 1- T PDВЫй IT ВтРРОТТ ЭЛЕМЕНтЬТ И, Э.ЛСХТЕНт

ИГГИ, "-.лемснт HF и смммятов по молхлто лв . выход котопого подключен к пепво тт

RòРлс псового элехлснтя И. Втопой вход ко—,пТ "О ПОЛКЛЮЧЕН К ПЕРВОМХ УПРаВЛЯЮТЦЕВХР.IA TOT TITIPC«ОЙ Sf ?PHTCTI, ВТ-,ТХОЛ ПСDRÎ40 - ."-,лементя И I!o÷«aþ÷eH к первохт вхочх

"-л"- ентя ИЛИ, второй Rroл которого пол«лючен к вь?холу второго элемента И. RhTХn "-. Емячтя H,TTÖ яВЛНЕтся ВЫХОЛОМ ЛО.. Тсc«РТ? я? йктт. Певвьтй vlfpaR,лятотцттй вход

45,-.0гТ :т"-с.

В;рчх ттепвого э,"ехтентя И и вхоЛх эf!eFIpH. Я HF., Выход КОТОРОГО полк flovPH к IIPPчР.,т - в п т. R nrnãn R."òã т тття И втоРОЙ

-Хо Т 1?ОТРРОГО ПО I«Л?ОЧЕН К ПЕОВОМХ ИН50 ?1тР?тмя?ТТ 0T!TTмл Входl ячсйктт, ВТОРОЙ интттnphтяппРнньтй R. Ioл кОтОРОЙ полклк IcH II

ПРD"n» - -,,:Ол c" ..,л>.тяго?13 и; модулю два, втР?тРЙ вход котопого подключен ко второмт ппавляющеч входу ячейки.

Исто ?ники пнфорхтации.

TTDT1FTFTTbIe R0 ВТТТ. ТЯНТТР ПРИ ЭКСПРПт?ТЗ . Патент ФРГ М 2084841, кл. 42m 7/38.

1971.

2. The Рadio and Е1ес1гоп?с Еп ineer

60 Л",Гтаг;., 1974, N. 1, Р. 21, ф?;г. 1 (прототттп).

650074 и в

Риа 2

Составитель Ю. Хаскин

Редактор А. Купрякова

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

Корректоры: P. Беркович а. и Л. Брахннна

Заказ 2713/15 Изд. М 167 Тираж 779 Подписное

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

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

Типография, пр. Сапунова, 2