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

1

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

Известны арифметические устройства, предназначенные для умножения и деления двоичных чисел Ij, содержащие регистры, сумматор с последовательным переносом и узел вентилей, обладающие простой конструкцией. Однако эти устройства характеризуются низким быстродействием с временем выполнения операций умножения (деления), пропорциональным , где п - разрядность, t - задержка на одноразрядном сумматоре, на элементе типа И-ИЛИ.

Известны арифметические устройства, выполняющие ускоренное умножение и деление 21,13, в которых количество исполняемых итераций уменьшено до величины с временем выполнения операции умножения (деления), пропорциональным г /2-пЧ/3, и устройства, выполняющие ускоренное деление 4 и умножение 5 , использующие сумМато йл с разделением цепей суммы и переноса с количеством исполняемых итераций п. На каждой итерации операция сложения выполняется без расс пространения переносов на п разрядов . Время выполнения операций пропорционально nf.

Однако .устройства С не могут 1Q выполнять операцию деления, а устройства 4 требуют для своей реализации значительных аппаратурных затрат.

Наиболее близким по технической

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

25 ко второму входу первого сумматора, выход переноса которого подключен ко входу третьего регистра, выход которого подключен к третьему входу первого сумматора и входу первого

30 регистра, а выход младшего разряда

четвертого регистра соединен с выходом устройства.

Однако это устройство не может выполнять операции деления, поскольку в отличие от операции умножения, операция деления является рекурсивной, т.е. очередную цтерацию нель-; эя начинать до завершения предыдущей, так как знак частичного остатка, полученного на данной итерации, определяет какую операцию (сложения или вычитания) следует выполнить на очередной итерации,, а знак частного остатка может бкть получен лишь после выполнения операции сложения (вычитания) с распространение переносов на п разрядов на данной итерации,, что не позволяет осуществить сумматор с разделением цепей суммы и переноса.

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

Поставленная цель достигается тем, что в устройство, содержащее четыре регистра, первый сумматор, блок вентилей, причем выход первого регистра подключен ко входу блока вентилей, выход которого подключен к nepBO ;ty входу первого сумматора, выход суммы которого подключен к входу второго регастра, выход которого подключен ко второму входу первого сумматора, выход переноса которого подключен ко входу третьего регистра, выход которого подключен к третьему входу первого cyм taтopa и ко входу первого регистра, а выход младшего разрядачетвертого регистра соединен с выходом устройства, введены второй и третий сумматоры, причем выход суммы старших разрядов первого сумматора подключен к первому входу второго сумматора, выход переноса старших разрядов первого сумйатора подключен ко второму входу второго сумтора, выход млалших разрядов четвертого регистра подключен к первому входу третьего сумматора, выход которого подключен ко входу млаууаях разрядов четвертого регистра, второй вход третьего сумматора соедине ; с ВХОДСЛ1 устройства. ji . На чертеже показана структурнг1Я схема предлагаемого устройства.

Арифметическое устройство содержит первый регистр 1, четвертый регистр 2, второй регистр 3, третий регистр 4, первый сумматор 5, блок- вентилей 6, второй сумматор 7, третий сумматор 8, вход устройства 9, выход устройства 10.

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

сумматора 5 подключены со сдвигом влево на один разряд ко вторым входам второго сумматора 7. На вторые входы третьего сумматора 8 поступает постоянный сигнал единицы младше, го разряда регистра 2 с входа устройства.

Блок вентилей б содержит цепи передачи прямым и обратным (дополнительным) кодом, разрядность сумQ маторов 7 и 8 меньше разрядности устройства, а регистры 2, 3 и 4 содержат цепи сдвига влево и вправо.

При работе в режиме умножения не используются второй сумматор

5 7, третий сумматор 8 и-цепи сдвига влево регистра 2, регистра 3 и регистра 4. Устройство выполняет операцию умножения, начиная с младших разрядов множителя, со сдвигом

0 частичного произведения и множителя на один разряд вправо на каждой итерации точно так же. как известное устройство 4.

Регистр 1 предназначен для хранения множимого, регистр 2 для хранения множителя, сумматор 5 для формирования кода частичного произведения. На выходах цепей суммы сумматора 5 образуется код поразQ рядных сумм частичного произведения, а на выходах цепей переноса сумматора 5 - код переносов частичного произведения. Регистр 3 предназначен для хранения поразрядC ных сумм частичного произведения, а регистр 4 - для хранения кода переносов частичного произведения. Устройство работает циклически. На L-ой итерации., где , 2,..., п, с выхода младшего разряда регистра 2 снимается очередная цифра множителя. Код поразрядных суМм частичного произведения поступает из регистра 3 на вторые входы сумматора 5. Код переносов частичного

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

Q входы сумматора. 5 не происходит. Если цифра множителя равна единице, то происходит передача множимого из регистра 1 через блок вентилей 6 в прямом коде на первые входы сумматора 5, в котором происходит операция сложения без распространения переносов. Код поразрядщлх, сумм результата операции сложения с выходов цепей суммы сумматора 5 поступает на входы регистра 3. Код

0 переносов результата операции сло.жения с выходов цепей переноса сумматора 5 поступает со сдвигом влево на один разряд на входы регистра 4. В конце i-ой итерации происходит

5 сдвиг содержимого регистра 2, регистра 3 и регистра 4 на один раэряд вправо. В результате в младшем разряде регистра 2 оказывается очередная цифра множителя, в регистре 3 - код поразрядных сумм очередного частичного произведения, а в регистре 4 - код переносов очередного частичного произведения.

После п-кратного повторения итераций в регистре 3 и в регистре 4 оказывается результат - вычисленное значение произведения, представленное в двухрядном коде, при этом.в регистре 3 оказывается код поразрядных сумм произведения, а в регистре 4 оказывается код переносов произведения ,

Преобразование произведения из двухрядного кода в обыкновенный однорядный двоичный код выполняется дополнительной итерацией. Код переносов произведения из регистра

4поступает на входы регистра 1 и. не поступает на третьи входы сумматора 5. В сумматоре 5 Зс1мыкаются разделенные цепи суммы и переноса, т.е. сумматор 5 на дополнительной итерации работает по схеме сумматора с последовательным (сквозным) переносом. Код поразрядных сумм произведения из регистра 3 поступает на вторые входы сумматора. Код переносов произведения из регистра 1 через блок вентилей 6 поступает в прямом коде на первые входы сумматора 5. В сумматоре 5 происходит операция сложения с распространением переносов на п разрядов. В результате на выходах цепей суммы сумматора

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

При работе в режиме деления не используются цепи сдвига вправо регистра 2, регистра 3 и регистра 4. Устройство выполняет операцию деле- ния со сдвигом частичного значения частного влево на один разряд на каждой итерации без восстановления отрицательного частичного остатка операции деления.Регистр 1 предназначен для хранения делителя, регистр 2 для хранения частичного значения частного.. Су матор 5 предназначен для формирования кода частичного остатка. Поскольку цепи суммы и переноса сумматора 5 разделены, частичный остаток образуется на выходах сумматора 5 в двухрядном коде. При этом на выходах цепей суммы сумматора 5 образуется код поразрядных сумм частичного остатка, а на вы;содах цепей переноса сумматора 5 образуется код.

переносов частичного остатка. Регистр 3 предназначен для хранения кода поразрядных сумм частичного остатка, а регистр 4 - для хранения кода переносов частичного остатка.

Устройство работает циклически. На L-ОЙ итерации, где , 2, 3,..., п+п/(т-1), код поразрядных сумм частичного остатка поступает из регистра 3 на вторые входы суммато0ра 5 . Код переносов частичного остатка поступает из регистра 4 на третьи входы сумматора 5. Если частичный остаток отрицательный, то происходит передача делителя из

5 регистра 1 через узел вентилей б в прямом коде на первые входы сумматора 5. Если частичный остаток по- ложительный, то происходит передача делителя из регистра 1 через

0 блок вентилей б в обратном (дополнительном) коде на первые входы сумматора 5, в котором происходит операция сложения без распространения переносов. Код поразрядных сумм ,

5 результата операции сложения с выходов цепей сумматора 5 поступает на входы регистра 3. Код переносов результата операции сложения с выходов цепей переноса сумматора 5 поступает со сдвигом влево

0 на один разряд на входы регистра 4. Старшие m разрядов кода поразрядных сумм частичного остатка с вы- ходов m старших разрядов цепей суммы сумматора 5, поступающие на пер5вые входы сумматора б, и старшие m разрядов кода переносов частичного остатка с выходов m старших разрядов цепей переноса сумматора 5, поступающие со сдвигом влево на

0 один разряд на вторые входы сумматора 7, склгщываются в сумматоре 7 и на его выходах образуется обычный двоичный однорядный код старших разрядов частичного остатка.

5 Младшие m разрядов частичного зна-. чения частного с выходов млсщших m разрядов регистра 2 поступают на входы сумматора 8. На вторые входы сумматора 8 подан постоянный

0 сигнал единицы младшего разряда регистра 2. Если частичный остаток положительный, в сумматоре 8 происходит операция сложения m младших разрядов частичного значения част5ного и единицы-младшего разряда. Если частичный остаток отрицательный, в сумматоре 8 происходит операция вычитания m младших разрядов частичного значения частного и единицы младшего разряда. Результат

0 операции сложения (вычитания)- с выходов сумматора 8 поступает на входы m младших разрядов регистра 2. jB конце i-ой итерации происходит 5 содержимого регистра 2, регистра 3 и регистра 4 на один разряд влево. В результате в регистре 2 оказывается очередное частичное значение частного, в регистре 3 оказывается код поразрядных сумм очередного частичного остатка, а в регистре 4 оказывается код переносов очередного частичного остатка. К моменту определения точного значения частичного остатка на L-ой итерации может возникнуть ошибка частичного остатка, значение которой меньше 2. На (1+1)-оЛ итерации значение этой ошибки удваивается, т.е. будет меньше . Кроме того на (1+1)-ой итерации может возникнуть ошибка, значение которой меньше 2, Суммарная ошибка t-ой итерации и (1+1)-ой итерации будет меньше . После выполнения m итераций ошибочными будут все старшие m разрядов. Для компенсации данной ошибки {т-1)-ая, 2(т-1)-ая, 3(пп-1)-ая,...итерации повторяются дополнительно еще один раз, причем в конце C(m-1)-ll -ой. 2 (т-1)-П-ой, СЗ (п)-1)-l3 Ой-, . итерации сдвиг содержимого регистра 2, регистра 3 и регистра 4 на один разряд влево не происходит. При этом компенсируется искажение m старших разрядов частич ного остатка. После |п+п/(т-1)}-кратного повто рения итераций в регистре 2 оказыва ется результач; - вычисленное значение частного, представленное в обык новенном двоичном однорядном коде. Эффективность изобретения заключается в обеспечении выполнения опе рации умножения и деления двоичных чисел за счет выполнения операции сложения без распространения переносов на п разрядов. Формула изобретения Арифметическое устройство, содер щее четыре регистра, первый сумматор, блок вентилей, лричем выход первого регистра подключен ко входу блока вентилей, выход которого подключен к первому входу первого сумматора, выход суммы которого подключен ко входу второго регистра, выход которого подключен ко второму входу первого сумматора, выход переноса которого подключен ко входу третьего регистра, выход которого подключен к третьему входу первого сумматора и ко входу первого регистра, а выход младшего разряда четвертого регистра соединен с выходом устройства, о тл ичающее с я тем, что, с целью расширения функциональных возможностей за счет выполнения, кроме операции умножения, операции деления, в него введены второй и третий сумматоры, причем выход суммы старших разрядов первого сумматора подключен к первому входу второго сумматора, выход переноса старших разрядов первого сумматора подключен ко второму входу второго сумматора, выход младших разрядов четвертого регистра подключен к первому входу третьего сумматора, выход которого подключен ко входу младших разрядов четвертого регистра, второй вход третьего сумматора соединен со входом устройства. Источники информации, принятые вовнимание при экспертизе 1.Папернов А.А. Логические основы цифровой вычислительной техники. М., 1972, с. 191-201 и с. 225-240. 2.ASlOpcKoe свидетельство СССР 255648, кл. G 06 F 7/54, 1969. 3.Авт-орское свидетельство СССР 482740,. кл. G 06 F 7/52, 1975. 4.Патент Франции 2098559, кл. G 06 F 7/00, 1972. 5.Дроздов Е.А.и др. Многопрограммные цифровые вычислительные машины, М., 1974, с. 261-266 (прототип) .

Ю