Устройство для деления

 

Изобретение относится к области вычислительной техники и может быть использовано в устройствах обработки информации, представленной в двоичной системе счисления с фиксированной запятой . Цель изобретения - повышение быстродействия . Устройство для деления содержит шесть регистров 1-6, два сдвигателя 7 и 8, два мультиплексора 9 и 10, два сумматора и 12, блок 13 анализа, два элемента И 14 и 15 и триггер 16, соединенные между собой функционально. 1 з.п. ф-лы, 3 ил., 1 табл.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

1742815 А1 (si)s 6 06 F 7/52

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4870221/24 (22) 25.06.90 (46) 23.06.92, Бюл. М 23 (71) Научно-производственное обьединение

"Орион" (72) М.В.Козырькова и А.Д.Марковский (53) 681.325 (088.8) (56) Авторское свидетельство СССР

М 1541598, кл. G 06 F 7/52, 1988.

Авторское свидетельство СССР

М 1541597, кл. G 06 F 7/52, 1987. (54) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ (57) Изобретение относится к области вычислительной техники и может быть использовано в устройствах обработки информации, представленной в двоичной системе счисления с фиксированной запятой. Цель изобретения- повышение быстродействия, Устройство для деления содержит шесть регистров 1-6,два сдвигателя 7 и 8, двй мультиплексора 9 и 10, два сумматора 11"и

12, блок 13 анализа, два элемента И 14 и 15 и триггер 16, соединенные между собой функционально. 1 з.п. ф-лы, 3 ил., 1 табл.

1742815

15

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

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

Недостатки устройства — большой объем оборудования, сложность и невысокое быстродействие.

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

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

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

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

Kj, где i = 1,m, m — разрядность мантиссы операнда, J — номер итерации, и схему формирования сигнала окончания деления, представляющую собой m-входовой элемент ИЛИ, выход которого является первым выходом блока анализа, а m входов элемента ИЛИ соединены с информационными выходами и узлов формирования унитарных кодов, в каждый из которых входит первый элемент НЕ, вход которого является входом нулевого разряда мантиссы операнда, а выход элемента НЕ соединен с первыми входами первого, второго и третьего элементов

ИСКЛЮЧАЮЩЕЕ ИЛИ, вторые входы которых являются соответственно входами i-го (I+1)-ro и (1+2)-го разрядов мантиссы операнда, выход первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с первым входом первого элемента И и является первым раз1742815 рядом информационного выхода узла формирования унитарных кодов, выход второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с входом второго элемента НЕ, первым входом второго элемента И и является вторым разрядом информационного выхода узла формирования унитарных кодов, выход третьего элемента ИСКЛЮЧАЮЩЕЕ

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

На фиг.1 представлена блок-схема устройства для деления; на фиг.2 — схема-формирования сигнала окончания деления; на фиг.3- узел формирования i-ro разряда унитарного кода.

Устройство для деления содержит первый 1, второй 2,третий 3, четвертый4, пятый

5 и шестой 6 регистры, первый 7 и второй 8 сдвигатели, первый 9 и второй 10 мульти. плексоры, первый 11 и второй 12 суммато ры, блок 13 анализа, первый 14 и второй 15 элементы, триггер 16, причем первые входы первого 11 и второго 12 сумматоров соединены с выходами первого 9 и второго 10 мультиплексоров соответственно, вторые входы первого 11 и второго 12 сумматоров соединены соответственно с выходами первого 1 и четвертого 4 регистров, первые. информационные входы первого 9 и второго

10 мультиплексоров соединены соответственно с прямыми выходами первого 7 и второго 8 сдвигателей, третий 17 и четвертый

18 мультиплексоры, первые информационные входы которых являются соответствен но входами делителя 19 и делимого 20 устройства, управляющие входы третьего

17 и четвертого 18 мультиплксоров соединены с выходом триггера 16, вход 21 установки в" 0" которого соединен с установочным входом второго регистра 2 и является установочным входом 21 устройства, вход установки в "1" триггера 16 соединен с входами синхронизации третьего 3 и шестого 6 регистров и с выходом первого элемента И

14, первый вход которого является первым входом 22 синхронизации устройства, второй вход 23 синхронизации которого соединен с первым входом второго элемента И 15, второй вход которого соединен с вторым входом первого элемента И t4 и с первым элемент ИЛИ 25, выход 26 которого является первым выходом блока 13 анализа, à m входов 27 элемента ИЛИ 25 соединены с информационными выходами и узлов фор40 мирования унитарных кодов, в каждый из которых входит первый элемент ВЕ 28, вход которого является входом 29 нулевого разряда мантиссы операнда, а выход элемента

Н Е 28 соединен с первыми входами первого

45 30, второго 31 и третьего 32 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, вторые входы которых являются соответственно входами 33 — 35 iro (!+1 -ro и (1+2 -ro разрядов мантиссы oneранда, выход первого элемента

50 ИСКЛЮЧАЮЩЕЕ ИЛИ 30 соединен с первым входом первого элемента-И 36 и является первым разрядом информационного выхода 37 узла формирования унитарных кодов, выход второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 31 соединен с входом второго

55 элемента НЕ 38, первым входом элемента И

39 и является вторым разрядом информационного выхода 37 узла формирования унитарных кодов, выход третьего элемента

ИСКЛЮЧАЮЩЕЕ ИЛИ 39 соединен с втовыходом блока 13 анализа, второй выход которого соединен с управляющими входами первого 7 и второго 8 сдвигателей, инверсные выходы которых соединены

5 соответственно с вторыми информационными входами первого 9 и второго 10 мультиплексоров, управляющие входы которых соединены с выходом первого регистра 1, выходы первого 11 и второго 12 сумматоров

10 соединены соответственно,с информационными входами третьего 3 и шестого 6 регистров, выход шестого регистра 6 соединен с вторым информационным входом четвертого мультиплексора 18 и явЪяется выходом 24 .

15 устройства, выход третьего регистра 3 соединен с вторым информационным входом третьего мультиплексора 17, выход которого соединен с информационными входами первого 1 и второго 2 регистров, выход чет20 вертого мультиплексора 18 соединен с информационными входами четвертого 4 и пятого 5 регистров, выход второго элемента

И 15 соединен с входами синхронизации первого 1, второго 2, четвертого 4 и пятого

25 5 регистров, выход второго регистра 2 соединен с входом блока 13 анализа и с информационным входом первого сдвигателя 7, выход пятого регистра 5 соединен с информационным входом второго сдвигателя 8, 30 блок 13 анализа содержит и узлов формирования i-ro разряда унитарного кода Kj (фиг.3), где i = 1,m; m — разрядность мантиссы операнда, j — номер итерации, и схему формирования сигнала окончания деле35 ния, представляющую собой m-входовой

1742815

Унитарный код К1

01000000

0.1011100000 0.1000000000

0.0010111000 0.001000000

0.1110011000 0.101000000

0.0001110011 0.000101000

1.0000001011 0.101101000

0.000001000 0.000001011 тлоооооои о.1о11оо1о1

00000010

Y/Х = 0,10110010101 = 0,69775390625, точность вычисления Л = 2 = 0,00390625.

Число итерации равно 3, т.е. < g. В известA ном устройстве для обеспечения точности в

2 " требуется и-1 итераций и удвоенная разрядность регистров, сдвигающего регистра, сумматор. Сравнивают аппаратные затраты известного и предлагаемого устройств (см. таблицу).

Как видно иэ таблицы, аппаратные затраты уменьшаются примерно в 2 раза. Таким образом экономический эффект

Э вЂ” — -=4, Vp n — 1

Vpg пУ2 рым входом второго элемента И 39 и является третьим разрядом информационного выхода 37 узла формирования унитарных кодов, выход второго элемента НЕ 38 соединен с вторым входом первого элемента И 36, выход которого соединен с первым входом элемента ИЛИ 40, второй вход которого соединен с выходом второго элемента И 39, а выходы элементов ИЛИ 40 всех и узлов формирования унитарных кодов соединенц с входами 41 m-входового элемента И 42, выход которого является вторым выходом 43 блока анализа.

Увеличение быстродействия достигается путем применения мультиплекативного алгоритма деления. Если в известном число итераций составляет п-1, где n — двоичная точность вычислений, то в предлагаемом усп тройстве количество итераций . Это достигается путем введения блока анализа, формулирующего Kl в соответствии с мультиплекативными алгоритмами. За счет анализа двух разрядов мантиссы делителя скорость приближения Х-1 не превыи шает — .

Например, Х = 0,71875, Y = 0,5; Y/Х =

0,6956; n = 8 m = n + log и = 11. где V>p — обьем оборудования известного устройства;

V — объем оборудования предлагаемого устройства.

5 Блок 13 анализа функционирует в соответствии с логическими выражениями:

Х = Хо® Хь

10 где@ — сумма по модулю 2;

Xi — значение I-ro разряда второго регистра 2;

Хо — значение О-го разряда второго регистра 2;

15 Х вЂ” промежуточные значения I-го разряда мантиссы делителя. — I — 1.

Zi =(Х1 Х +1чХ +1" Хн- )лП ZK, 20

K =a где 21 — I-й разряд унитарного KI, П вЂ” операция логического умножения.

При этом Ъ = 1 в том месте унитарного

25 кода, которое соответствует данному К;.

Например n = 8

Унитарный код К1

1000000 21=1 - 1

01000000 22 = 1 2

00001 00 25-1 . 5

00000010 27=1 7

STOP = XI, 1=1 где — операция логического сложения.

Конструктивно блок 13 анализа состоит из и блоков получения i-го разряда унитарного кода К1 (фиг.3), где n — точность вычисления операции деления, и формирователя сигнала STOP (фиг.2).

40 Устройство для деления.(фиг.1) работает в соответствии с мультипликативными алгоритмами:

Х)+1=XI+ q 2 1XI 1;

-к1

Yl+1 = Yl+ eI 2 KI YI Y/X, где Х вЂ” делитель, Y — делимое, Разрядность операндов m для обеспечения точности вычисления в и двоичных

50 разрядов должна быть

m >и+ log n, Обозначают Хо — старший разряд дели55 теля, тогда мантисса делителя начинается с

Х1 разряда.

Алгоритм определения KI в каждой итерации состоит в следующем. Если Xo - О, то в мантиссе делителя определяет порядковый

1742815 к

X1 = ХО®Х1;

Хг =ХоЮХк

Xm m= АХАХ., 25

ГдЕ ХО, Х1, Х2, ..., Xm — ЗНаЧЕНИя ВЫХОДНЫХ разрядов второго регистра;

Х1, Х, ..., Xm — промежуточные значения m-разрядной мантиссы делителя; 30

Q+ — сложение по модулю 2. с! l — 1

Z1 = (X1 л X)+1 v Xi+1 1 X1+z ) д П2к, К =о

35 где 21 — разряд унитарного кода;

П- операция логического умножения, Таким образом на втором выходе блока

13 анализа формируется унитарный код ве- 40 личины К, поступающий на управляющие входы сдвигателей 7 и 8. На втором выходе блока 13 анализа формируется сигнал окончания вычислений STOP:

STOP =, Я Х, I=1 где — операция логического сложения.

Устройство работает следующим обра- 50 зом.

По сигналу "Исходное состояние" триггер 16 устанавливается в состояние "О", который поступает на управляющие входы третьего 17 и четвертого 18 мультиплексо- 55 ров. При этом третий 17 и четвертый 18 мультиплексоры передают информацию со своих первых входов. По сигналу "Исходное состояние" 21 второй регистр 2 устанавлиномер К старшего "О" и анализируется разряд, следующий за ним. Если за нулем следует "О", то К - К-1, если 1, то К1 К, Если

Хо = 1, то в мантиссе делителя определяется порядковый номер к старшей "1" и анализи- 5 руется разряд, следующий за ней. Если за единицей следует "1". то К1 = К-1, если "О", то К1 = К. Если Хо = О, то е = +1, если Хо - 1, то ej - -1. После того, как делитель принимает значение, равное 1(0.111... или 1.000...) 10 вычисление заканчивается, а в канале Y на.ходится результат деления Y/Х. При этом максимальное количество итераций, необходимое для получения результата, не преп 15 вышает —, что в два раза меньше, чем у известного устройства (и — 1). Начальные условия Хо = Х, Уо = Y. Исходя из данного алгоритма анализа делителя блок 13 анализа работает в соответствии с логическими 20 выражениями: вается в состояние 0101 ... 01, что обеспечивает сброс сигнала STOP - 1. Сигнал с первого выхода блока. 13 анализа деблокирует прохождение первый 22 и второй 23 синхросерии через первый 14 и второй 15 элементы

И. Интервал между тактовыми импульсами второй 23 и первой 22 синхросерий равен суммарной задержке блока 13 анализа, первого сдвигателя 7, первого мультиплексора

9, первого сумматора 11. По второй синхросерии происходит запись делителя в первый

1 и второй 2 регистры, делимого в четвертый

4 и пятый 5 регистры. Блок 13 анализа выдает значение К1 в каждой итерации. На выходе первого сдвигателя 7 формируются прямое и инверсное значения 2 1 - Х1, на выходе второго сдвигателя 8 формируются прямое и инверсное значения.2 " Yj. Управляющим сигналом для первого 9 и второго 10 мультиплексоров является Хо, поступающий с выхода первого регистра 1.

Если Xo = О, то первый 9 и второй 10 мультиплексоры пропускают прямое значение

2 Х1, 2 . Yj (q =+1) соответственно, если X0=1, то инверсные значения(e1 =-1).

Первый сумматор 11 осуществляет операцию X + q 2 Х1, второй сумматор 12 осуществляет операцию Yj + 812 Yj, По первой синхросерии 22 результат Х +1, У1+1 записываются в третий 3 и шестой 6 регистры соответственно, По первой синхросерии

22 триггер 16 устанавливается в "1" и третий

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

Интервал между импульсами первой 22 и второй 23 синхросерий равен времени задержки третьего 17 или четвертого 18 мультиплексора. Итерационный процесс продолжается до тех пор, пока не сформируется сигнал STOP = О. который блокирует прохождение первой 22 и второй 23 синхросерий через первый 14 и второй 15 элементы

И. В шестом регистре 6 находится результат деления Y/Х, который поступает на выход

24 устройства.

Устройство может быть реализовано на базовом матричном кристалле 1548ХМЗ.

При этом длительность одной итерации для

n = 56 равна 40 нс. Время выполнения операции деления для точности в 56 двоичных разрядов мантиссы составит 1,12 мкс.

Все устройство также может быть выполнено на микросхемах 533 серии, регистры—

555 ТМ8, мультиплексоры — 533ЛР1, сдвигатели 533ЛИ2, 533ЛЛ1, элементы И -533ЛИ2, триггер — 533TP2, сумматоры 533ИМ6, блок анал иза 533ЛА2, 533ЛАЗ, 533ЛЛ17.

Таким образом предлагаемое техническое решение обеспечивает простоту и ре1742815 гулярность схемного решения, уменьшения соединен с вторым информационным вхооборудования в 2 раза, отсутствие коррек- дом третьего мультиплексора, выход котоции и подготовительного такта внутри ите- рого соединен с информационными рации. Обеспечивается повышение входами первого и второго регистров, выи „5 ход четвертого мультиплексора соединен быстРодействиЯ итеРации до 2 по сРавне с информационными входамичетвертогои нию п-1 в известном устройстве, где n — пятого регистров, выход второго элемента количество точных разрядов мантиссы. И соединен с входами синхронизации перФормула изобретения ваго, второго, четвертого и пятого регист1.Устройство для деления, содержащее 10 ров, выход второго регистра соединен с первый, второй, третий, четвертый, пятый и входом блока анализа и с информационным шестой регистры, первый и второй сдвига- входом первого сдвигателя, выход пятого тели, первый и второй мультиплексоры, пер- регистра соединен с информационным вховый и второй сумматоры, блок анализа, дом второго сдвигателя. первый и второй элементы И и триггер, при- 15 2. Устройство по п.1, о т л и ч а ю щ e ечем первые входы первого и второго сумма- с я .тем, что блок анализа содержит и узлов торов соединены соответственно с формирования 1-ro разряда унитарного кода выходами первого и второго мультиплексо- К), где i = 1,m, m — разрядность мантиссы ров, вторые входы первого и второго сумма- операнда, J — номер итерации, и схему форторов соединены соответственно с 20 мирования сигнала окончания деления, выходами первого и четвертого регистров, представляющую собой m-входовой элепервые информационные входы первого и мент ИЛИ, выход которого являе-ся первым второго мультиплексоров соединены соот- . выходом блока анализа, а m входов элеменветственно с прямыми выходами первого и та ИЛИ соединены с информационными вывторого сдвигателей, о т л и ч а ю щ е е с я 25 ходами и узлов формирования унитарных тем, что, с целью повышения быстродейст- кодов, в каждый из которых входит первый вия, в него введены третий и четвертый элемент НЕ, вход которого является входом мультиплексоры, первые информационные нулевого разряда мантиссы операнда, а вывходы которых являются соответственно ход элемента НЕ соединен с первыми вховходами делителя и делимого устройства, 30 дами первого, второго и третьего элементов управляющие входы третьего и четвертого .ИСКЛЮЧАЮЩЕЕ ИЛИ, вторые входы котомультиплексоров соединены с выходом рых являются соответственно входами !-ro, триггера, вход установки в "0" которого со- (1+1)-го и (1+2)-го разрядов мантиссы операнединен с установочным входом второго ре- да, выход первого элемента ИСКЛЮЧАЮгистра и является установочным входом 35 ЩЕЕ ИЛИ соединен с первым входом устройства, вход установки в "1" триггера первого элемента И и является первым разсоединен с входами синхронизации третье- рядом информационного выхода узла форго и шестого регистров и с выходом первого мирования унитарных кодов, выход второго элемента ¹ первый вход которого является элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединен первым входом синхронизации устройства, 40 с входом второго элемента НЕ, первым вховторой входсинхронизации которого соеди- дом второго элемента И и является вторым нен с первым входом второго элемента И, разрядом информационного выхода узла второй вход которого соединен с вторым формирования унитарных кодов, выход входом первого элемента И и с первым вы- третьего элемента ИСКЛЮЧАЮЩЕЕ ИЛИ ходом блока анализа, второй выход которо- 45 соединен с вторым входом второго элего соединен с управляющими входами мента И и является третьим разрядом инпервого и второго сдвигателей, инверсные формационного выхода узла формирования выходы которых соединены соответственно унитарных кодов, выход второго элемента с вторыми информационными входами пер- НЕ соединен с вторым входом первого элевого и второго мультиплексоров, управляю- 50 мента И, выход которого соединен с перщие входы которых соединены с выходом вым входом элемента ИЛИ, второй вход первого регистра, выходы первого и второго которого соединен с выходом второго элесумматоров соединены соответственно с мента И, а выходы элементов ИЛИ всех и информационными входами третьего и ше-, узлов формирования унитарных кодов соестого регистров, выхор ".::; . ого регистра со- 55 динены с входами m-входового элемента И, единен с вторым инф.,".пацирнным входом выход которого является вторым выходом четвертого мультиплексора и является вы- блока анализа. ходом устройства, выход третьего регистра

1742815

13

Риг.k

У и г.5

Составитель М.Козырькова

Техред М,Моргентал Корректор Н.Король

Редактор Н.Бобкова

Заказ 2286 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101