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

п 650074 Союз Советских Социалистических Республикол интел вт. свид.в 2) Заявлено 30.03.76 (21) 2342197/18-2 1) М Кл6 06 Г 7/38 аявки Ю с присоединени СССР по делам изобретений и открытий(71) Заявител ОЙСТВО 54) АРИФМЕТИЧЕСКОЕ ГосУдарственный комитет (23) Приор Изобретение относится к области цифровой вычислительной техники и может быть использовано, в частности, в цифровых устройствах обработки радиолокационной информации, цифровых анализаторах спектра и в специализированных вычислителях преобразования Фурье.Известны арифметические устройства матричного типа, содержащие типовые ячейки выполнения элементарных операций и элементы памяти, расположенные в узлах матрицы связей 1,Эти устройства предназначены для выполнения сложных вычислительных операций, в частности умножения над числами, представленными в параллельном двоичном потенциальном коде. Устройства отличаются высоким быстродействием, достигаемым за счет матричной структуры устройства, наличия в них элементов памяти и конвейерного режима вычислений, Ячейки и связи в данных устройствах однотипны, что облегчает техническую реализацию устройств.Наиболее близким по технической сущности к изобретению является матричное арифметическое устройство, содержащее одноразрядные сумматоры, расположенные по строкам, по гг сумматоров в каждой, причем выход переноса каждого одноразрядного сумматора подключен ко входу переноса последующего одноразрядного сумматора той же строки, управляющие входыодноразрядных сумматоров подключены к первой управляющей шине устройства, первый и второй входы одноразрядного сумматора подключены к выходам первого и второго элементов памяти соответственно, выход суммы г-го (г = 1 - :а) одноразрядно го сумматора данной строки подключен ковходу первого элемента памяти (г+1)-го одноразрядного сумматора последующей строки, причем входы элементов памяти первой строки и входы переноса первых 15 одноразрядных сумматоров строк являютсяпервой и второй группами информационных входов устройства соответственно, выходы переноса и суммы гг-х одноразрядных сумматоров всех строк являются соответствен но первой и второй группами информационных выходов устройства 21, Кроме того, в известном устройстве выход второго элемента памяти каждой строки, соответствующего г-му одноразрядному сумматору, 25 подключен ко входу. второго элемента памяти следующей строки, соответствующего г-му одноразрядному сумматору.Устройство предназначено для использования в быстродействующих процессорах, ЗО в частности в процессорах быстрого преобразования Фурье, для вычисления в конвейерном режиме действительной и мнимой частей комплексного вектора данных при вращении его на угол, определяемый весовым коэффициентом Фурье.Устройство-прототип не может быть использовано для выполнения вычислений по алгоритму Волдера в конвейерном режиме, что ограничивает его функциональные возможности и область применения.Целью изобретения является расширение класса решаемых арифметическим устройством задач путем обеспечения реализации в нем вычислений по алгоритму Волдера в конвейерном режиме.Цель изобретения достигается тем, что устройство содержит логические ячейки по числу одноразрядных сумматоров, причем первый информационный вход каждой -й логической ячейки подключен к выходу соответствующего второго элемента памяти, выход - ко входу второго элемента памяти, соответствующего (1+1) -му одноразрядному сумматору последующей строки, вторые информационные входы логических ячеек являются третьей группой информационных входов устройства, первые управляющие входы логических ячеек подключены ко второй управляющей шине устройства, вторые управляющие входы логических ячеек строк - к третьей группе управляющих шин устройства. Кроме того, каждая логическая ячейка содержит первый и второй элементы И, элемент ИЛИ, элемент НЕ и сумматор по модулю два, выход которого подключен к первому входу первого элемента И, второй вход - к первому управляющему входу логической ячейки, выход первого элемента И подключен к первому входу элемента ИЛИ, второй вход которого подключен к выходу второго элемента И, выход элемента ИЛИ является выходом логической ячейки, первый управляющий вход логической ячейки подключен ко второму входу первого элемента И и ко входу элемента НЕ, выход которого подключен к первому входу второго элемента И, второй вход которого подключен к первому информационному входу ячейки, второй информационный вход которой подключен к первому входу сумматора по модулю два, второй вход которого подключен ко второму управляющему входу ячейки.Введение в устройство дополнительных логических ячеек, связей и информационных выходов позволяет использовать данное устройство помимо умножения для вычисления по алгоритму Волдера коэффициентов преобразования Фурье и вышеперечисленных элементарных функций.На фиг. 1 приведена электрическая схема предложенного устройства; на фиг. 2 - структура логической ячейки. 5 10 15 20 25 30 35 40 45 50 60 65 Устройство содержит одноразрядные сумматоры 1, элементы 2 памяти, логические ячейки 3, входы 4 управления устройством, информационные выходы 5 устройства, информационные входы б устройства, информационные выходы 7 устройства, второй информационный вход 8 ячейки, первый вход 9 управления ячейки, вход 10 управления устройством, элемент 11, элемент НЕ 12, элемент ИЛИ 13, сумматор по модулю два 14,Арифметическое устройство (см. фиг. 1) состоит из одноразрядных сумматоров 1, каждый из которых имеет первый, второй и третий входы, вход переноса, выход переноса и выход суммы, элементов 2 памяти и логических ячеек 3. Одноразрядные сумматоры 1 расположены по строкам, каждая из которых содержит одинаковое количество одноразрядных сумматоров 1, строки расположены по вертикали одна над другой и образуют матрицу. Первые входы всех одноразрядных сумматоров 1 в каждой строке объединены шиной управления умножением. Шины управления умножением подключены также ко входам 4 управления устройством, второй вход каждого одноразрядного сумматора 1 с номером , считая слева направо, в каждой строке, за исключением крайних левых одноразрядных сумматоров 1 и одноразрядных сумматоров 1 первой строки, подключен к выходу элемента 2 памяти, вход которого соединен с выходом суммы одноразрядного сумматора 1, расположенного строкой выше и имеющего номер ( - 1), а также с информационным выходом 5 устройства. У крайних левых одноразрядных сумматоров 1 в каждой строке и у одноразрядных сумматоров первой строки второй вход соединен с выходом элемента 2 памяти, вход которого является информационным входом б устройства. Выход переноса начатого одноразрядного сумматора в строке соединен со входом переноса следующего слева одноразрядного сумматора 1 той же строки, причем входы переноса крайних справа одноразрядных сумматоров всех строк являются информационными входами б устройства, а выходы переноса крайних слева одноразрядных сумматоров каждой строки являются информационными выходами 7 устройства.Третий вход всех одноразрядных сумматоров 1 с номером в строке У, считая слева направо, за исключением одноразрядных сумматоров первой строки, подключен к выходу элемента 2 памяти, вход которого соединен с выходом логической ячейки 3, первый информационный вход логической ячейки 3 соединен с третьим входом одноразрядного сумматора 1, расположенного строкой выше и имеющего порядковый номер в строке Л, второй информационный вход 8 ячейки 3 является информационным650074 положенного в верхней строке, подключен к выходу элемента 2 памяти, вход 6 которого является информационным входом устройства.5 Одноразрядный сумматор 1 выполняетоперации, как показано в табл. 1. Таблица 1 В х о д В ы х о д М операции У"второй Зт переноса третинЯ; первый переноса суммы 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Логическая ячейка 3 состоит из первого и второго элементов И 11, элемента НЕ 12, элемента ИЛИ 13 и сумматора по модулю два 14, первый вход которого соединен со 10 вторым информационным входом 8 ячейки, выход соединен с первым входом первого элемента И 11, второй вход которого соединен с первым информационным входом ячейки, а выход соединен со вторым входом 15 элемента ИЛИ 13, первый вход которого соединен с выходом второго элемента И 11, а выход является выходом ячейки.Работа арифметического устройства в режиме умножения осуществляется следу ющим обр азом.На входах 9 управления логических ячеек 3 устанавливаются такие значения потенциалов управления, что к выходт логических ячеек 3 оказываются подключенны ми их первые информационные входы. На входы 6 устройства, являющиеся входами элементов 2 памяти, выходы которых соединены с третьими входами одноразрядных сумматоров 1 первой строки, подключается 30 умножаемое число, представленное в параллельном двоичном коле, причем старший разряд этого числа подключен ко входч элемента 2 памяти, соответствующему крайнему левому одноразрядномх сумма тору первой строки. На входы 6, соединенные со входами элементов 2 памяти, выходы котбрых соединены со вторыми входами однбразрядных сумматоров 1 первой строки, также подается код умножаемого 40 числа, сдвинутый на один разряд вправо. На вход 4 шины управления первой стровходом устройства, первый вход 9 управления ячейки 3 является входом управления устройством. Вторые входы управления ячеек 3 в строке объединены и соединены со входом 10 управления устройством. Третий вход одноразрядного сумматора 1, раской подается управляющий потенциал, соответствующий значению старшего разряда кода множителя.Рассмотрим числовой пример. Пускай надо умножить число 0,1011 на число 0,1101, Для этого необходимо выполнить операции:+0,00000,10110,10110,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 управления,чс, =,чт.+ ,У; У,= У - ",Л; у, - 1 с, 1 У, 2- у - у, - ,Л, 2-; Таблптта 2 М операции Таким образом, введение ", т стпстйтство дополнительных логических ятеек н дополнительных информационных и т ппав,чяющих входов и выходов позволяет его использовать не только для выполи,"ния в конвейерном режиме операттий ухтножения двоичных параллельных многопазпядных кодов. но и выполнять вычисления также в онттеттепном режиме по алгоритмт Волдепа с цельто выполнения вычислительных операций, необходимых при дискретном преобразовании Фурье, при вычислении элементарных функций зтп ср, сов р Агс 1 д (У/Х); 55 б 0 б 5 1 2 3 Х,=Х+УХ =Х, - 0,5 УХз=Х, +0,25 У,У,=У,+0,5 ХУ,=У., - 0,25 Х,третьей строки поступает значение четвертого разряда множителя 1. Далее вторая строка в вычислениях не участвует, В третьей строке образуется сумма 0,1011 + -т,0110111 = 0,10001111, т, е. результат умножения.Из примера видно, что строки арифметического устройства выполняют вычислительньте операции поочередно, одна за другой. Процесс вьтчисленття как бы лвижется по тсонвейепу от строки к строке. Таким образом, хотя опепация умножения тпебчет выполнения многих опепапий сложения, но темп ввода чанных оппелеляетгя не по.чт;ьтм ввеменем умттожеттия, а вПемснем вьтгтолнения операций сммттроваттия и пепенистт в олной стпокс, Этим обусловлено вттсотсос быстполействиестпойства.Рассмотпттм паботт апттсЬметичестсого стпойстпа пптт вычисленптт в конвейепном Псжнме по алгопитму Воллепа. Алгоптттм Воллепа - это итспативная вьтчнслителтттая гтроттедупа. позволяюпан находить зттаиеттия Жутттстгттй эттт сс, он сс Лгс Ьт (У/Х), Аг"1 УГ),Хф+Уф, 1 пХ .1 . Аг 11 (УХ), 1 ГХ, Аггее)ч тУ/Х), К 1 ГЛ+У,В основе алгоритма Волдера лежат вычислеттня по формулам:, - Л; т+,У, т 2-т+т У, - У - ,Лт т 2-Коэффициенты принимают значения +1, - 1 и вырабатываются устпойством управления по правилу, зависятцему от того, какая именно элементарная функция вычисляется. Для упрощения дальнейщего описания паботы устпойства рассмотрим следующий пример. Пусть над числами х и р нужно выполнить по алгоритму Волдера следующие операции (см. табл. 2). Для. вычислений в конвейерном режиме используются лва одинаковых арифметических устройства н устройство управления. В одном арифметическом устройстве про 10 15 20 25 30 З 40 45 50 изводится вычисление хь а в другом - у; при этом х; и увычисляются в т-х строках первого и второго арифметического устройства. Числа х и у одновременно поступают на входы 6 первого и второго арифметических устройств. В первой строке первого арифметического устройства производятся вычисления согласно выражению 1 а, табл. 2, а в первой строке второго устройства - согласно выражению 1 б. При этом в первых строках арифметических устройств образуются х, и р. После этого вычисления по конвейеру переходят ко вторым строкам первого и второго арифметических устройств, причем во второй строке первого устройства производятся вычисления согласно выражению 2 а, а во второй строке второго устройства - согласно выражению 2 б. Так как при вычислении х. необходимо использовать д, а при вычислении у - хь то надо пере,чавать результат вычислений каждой прслыдущей строки одного из арифметических тстпойств на вхоч последующей строки лругого арис 1 тметичсского устройства, а такте преобразовывать Сттри вычитании) передаваемое число из прямого кода в лоно,чнительный тобпатный) и умножать на 2 -(0,5; 0,25; 0,125 и т, д).В описываемом арифметическом устройстве функпии переда ти и преобразования тсолов осуществляют логические ячейки 3, управляемые по входам 10 и 9 устройством поавления. Сдвиг кодов (умножение на 2 - ) может быть организован, в частности, за счет конфигурации связей между устройствами.Логическая ячейка 3 работает следующим образом.Рслтт на первом входе 9 упоавчения потенциал соответствует уровню логт ческого нуля, то к выходу логической ячейки 3 оказывается полключенным первый инсЬормапионный вход, если же на входе 9 потенциал соответствует логической единице, то на выход ячейки 3 передается логическая переменная второго инФопцатттоттного входа 8, просуммированная по модулю два с логическим значением управляющего сигналя входа 10, т. е. логи т"-.ая поп"хт"тптая входа 8 в прямом или инверсном виде.Агс с 1 (У/Х), /Х, К/Хф+Уй 1 п Х зт с Агй (У/Х), Агсй (У/Х), К 1 Хф - Уф, Таким образом существенно расширяется класс задач, решаемых устройством.Для оценки эффективности использования преллагаемого устройства спавним аппаратурные затраты, необходимые лля в.Т- числения функции вича г= К 1/Л+У с помощью предлагаемого устройства ц устройства-прототипа.При вычислении в конвейерно ОР 11(11 е необходимо использовать лвл апифм. Тиц - ских устройства ппедлэгаемого тиия. Гтп; этом для того, чащобы погпетпнось ления г не ппевосхо.чила 10 - , неос хочц цо. чтобы арифметическое т,стройстве мело 8 строк по т разрядов КЯТкляя (т - чцс. О Оазрялов в коде исхолных велцчии Х ц У 1. Таким образом, всего требуется щХ 8 одноразрядных сумматопов и столько жс,ТОГИЧРСКИХ ЯЧЕЕК.Ппи вычислении г с помоцсью стройства-прототипа необходимо снэчя.чя ття" тц г= х+р, а затем вычислить г:. - . 1/ф с использованием, нлпоиъсер, олного из итерационных алгортттТОВ ВЬТЧТтс,чсттттч квадратного корня с использоваиисм с"НОТ(ения.При этом потребуется ие менттис двоих оперэТтий умножения и двух опепацттй с.ожения, а всего, с учетом опепяций нахождения г, потребуется 4 т однопязряных сумматоров.Учитывая, что логическая ячейка ппимерно в два паза проде олнопазпя. ного суммэтопа. мокно записать выпажение лля коэффициента К, хапяктеризуютстего отношение эппаратурцых затрат при вьЧТ(слениц с помошью пречлягаемого устройства и устройства-прототипа.24 т 6(К4 тф т откуда следует, что ппи т) 6 выч.с,чение г с помоТцью прсчлагаемого устройства требует мень(пих затрат.Формула изобретения. Арифметическое строссс во, сочержящее одноразрядньтР сумматопьт, Оэсположеццые по стролм, по и в а.клой, ттртите выхол переноса каждого очнопазпя;тчого сумматора подключен ко вход. пепсцосл последующего одноразрялного с ммятопя туч же строки, управляющие входы одноразрядных сумматоров полклточетТт к пспвой управляющей шине устройства, пеРв.":, и втопой входы одноразрядного сумматора ИОДКЛЮЧЕНЫ К ВЫХОДЭМ ПЕПВОГО И ВТОРОГО элементов памяти соответственно, выход суммы -Го ( = 1 - :и) одноразрядного сумматора дяццоц строц прлТ( ОтРТЧ к входу первого элемента памяти (Т1) однораз рядного сумматора последующей строки,ппцчем входы элементов памяти первой строки и входы переноса первых одноразрядных суюаторов строк являются первой ц втопоГруппа.и нфоплионных вхолоВ устройства соответстветстто, выходы переноса и су,мы Гт-х очиорэзпялньх сумматоров всех стпок являются соответствеТтно первой и ч Очой ГПУТпазИ ТТТТфочЯИОННЫХ ВЬХОЛОВ устройства, Отличающееся тем, что, с ие,.ью плсищпе.сия класса решаемьх залач, тстпойсво содпжит логические ячейки по ислц о,чцопязря тных сутлаторов, причем ИСПИТ,Т" 11 Т 1 СТЮПясцТОРИТ 1 й ВХОЧ Т;ЛЖЛРй 1-и лс гичесч(Ой ячсйТ(и полклТО Тен к выходу соОТВРтствт ющего втопого элемента памяти, Г, КОЛ - КО ВХОЛ Вт РОГО ЭЛЕМРНтя ПаМЯ- ти, соог.;Ртгтвт ющего (Т11-му Олнопазрялном, сумчато послед ющей строки, втопь Р ТнсТтопТЯТтцоии 11 Р вхотсы,тогТтчсских -я яцеск являются трстс,ей ГОиной 111 тфопхтаТИОННЬХ ВХОЧОВ УСТПОЙСТВЭ ПРПВЬТР УППЯБЛЯЮТЦТР ВХОЛЬТ ЛОГИССКЦХ ЯЧРРПОЧКЛЮЧСНТ 1 КО ВТОРО МППЛВЛЯТОЦТСТ ПТИЦР СТООЙСТВл. Втопьтс уппавляютц,тс вхо 111 логических я 1 ТР. к стпок полклТотецьт к третьей группе уппв тяОтцтТх Тпцн устройства.2. Устпойство по и. 1, О тл и ч л ю щ Р ее ят. и, что кяжляя логческая ячейт(я сочер- лтТ- цепвьтТ( т втопси элементы И, эчсхтент Зд ИТГИ,:ле ТРТ(т НЕ ц смммлтоп по молмлтоЛВЯ, ВЬТХОЧ КОТОПОГО ПОЛКЛЮЧРН К ПРОВОРОТУ Иточу пепвого элемсита И. Втопои вход коТгво"О ПОЛКЛЮЧЕН К ПЕРВОЮ УППЯВЛЯЮТДЕВХРЛУ ЛОГТТЧРСТ(ой ЯТеТИП, ВХод ПСОВО -О э,чементл И по,чключен к первому вхочх".л".(Рття тЛ,ттИ, второй вход которого поллючен к выхочу второго элемента И, вьтт Олттемецтц И,ТТИ ЯВЛЯРТСЯ ВЫХОЧОМ ЛО- г ЦГСОТ( ЯтейКТТ. ПРПВЬйППаВ,ЧЯОЦцй ВХОЛ 45 лог ч"-сой ячейки подклточен ко втопомувхрч ИРПВОГО элехсентл И и Входх элемРн. л НЕ, Выход котороГО почклктчен к пРО- т.г т; Вхлтт т ТОПОго ЭЛРЧСИТЛ И ВТОПОй "ХОЛ ОТОПОго ПОЧКЧТОЧРН К ПРПВОМУ ИН (1 трОТЛТТ ОТ(Омх ВхОлт Яте 111, Втопой ин(Тт пмэ 11110 нттый вхОЧ котопой подключен кпеп--;Оч" с .,ТТТятот 1 Л цо молх лю два,втопой вход котопого подключен ко второт, уппав,чяюТцечт входу ячейки.55 Истотн 11 тт инфорхтапцц.ППТ(тТЯТЬТС ВО ВТТТ.ТЛИС ППИ ЭСИРОТя . Патент ФРГ;гэ 2084841, кл. 42 пт 7/38.1971.650074 и вОиг гСоставитель Ю. Хаскин Редактор А. Купрякова Техред А, Камышникова Корректоры: Р. Берковичо и Л. Брахннна Заказ 2713/15 Изд. Мо 167 Тираж 779 Подписное НПО Государственного комитета СССР по делам изобретений и открытий 113035, Москва, 5 К, Раушская наб., д. 4 5Типография, пр. Сапунова, 2