Устройство для деления Советский патент 1992 года по МПК G06F7/52 

5

2.О

S /о

(Л

С

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

и

J

13

i7

2/

Т

23

fS

22

f

/3

3

UT

2

ю

00

ел

/S

Vu-z.f

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

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

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

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

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

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

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

в О которого соединен с установочным входом второго регистра и является установочным входом устройства, вход установки в 1 триггера соединен с входами синхронизации третьего и шестого регистров и с выходом первого элемента И, первый вход которого является первым входом синхронизации устройства, второй вход синхронизации которого соединен с первым входом

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

0 при этом блок анализа содержит п узлов формирования i-ro разряда унитарного кода Kj, где I 1,m, т - разрядность мантиссы операнда, j - номер итерации, и схему формирования сигнала окончания деления,

5 представляющую собой m-входовой элемент ИЛИ, выход которого является первым выходом блока анализа, a m входов элемента ИЛИ соединены с информационными выходами п узлов формирования унитарных

0 кодов, в каждый из которых входит первый элемент НЕ, вход которого является входом нулевого разряда мантиссы операнда, а выход элемента НЕ соединен с первыми входами первого, второго и третьего элементов

5 ИСКЛЮЧАЮЩЕЕ ИЛИ, вторые входы которых являются соответственно входами 1-го (1+1)-го и (l+2)-ro разрядов мантиссы операнда, выход первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с первым входом первого элемента И и является первым разрядом информационного выхода узла формирования унитарных кодов, выход второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с входом второго элемента НЕ, первым входом второго элементаИияв- 5 ляется вторым разрядом информационного выхода узла формирования унитарных кодов, выход третьего элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с вторым входом элемента И и является третьим разрядом информацией- 10 ного выхода узла формирования унитарных кодов, выход второго элемента НЕ соединен с вторым входом первого элемента И, выход которого соединен с первым входом элемента ИЛИ, второй вход которого соединен 15 с выходом второго элемента И, а выходы элементов ИЛИ всех п узлов формирования унитарных кодов соединены с входами т- входового элемента И, выход которого является вторым выходом блока анализа.20

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

Устройство для деления содержит первый 1, второй 2, третий 3, четвертый 4, пятый 5 и шестой 6 регистры, первый 7 и второй 8 сдвигатели, первый 9 и второй 10 мультиплексоры, первый 11 и второй 12 суммато- 30 ры, блок 13 анализа, первый 14 и второй 15 элементы, триггер 16, причем первые входы первого 11 и второго 12 сумматоров соединены с выходами первого 9 и второго 10 мультиплексоров соответственно, вторые 35 входы первого 11 и второго 12 сумматоров соединены соответственно с выходами первого 1 и четвертого 4 регистров, первые-, информационные входы первого 9 и второго 10 мультиплексоров соединены соответст- 40 венно с прямыми выходами первого 7 и второго 8 сдвигателей, третий 17 и четвертый 18 мультиплексоры, первые информационные входы которых являются соответственно входами делителя 19 и делимого 20 45 стройства, управляющие входы третьего 17 и четвертого 18 мультиплксоров соединены с выходом триггера 16, вход 21 установки которого соединен с установочным вхоом второго регистра 2 и является устано- 50 вочным входом 21 устройства, вход становки в 1 триггера 16 соединен с вхоами синхронизации третьего 3 и шестого 6 регистров и с выходом первого элемента И 14, первый вход которого является первым 55 входом 22 синхронизации устройства, второй вход 23 синхронизации которого соединен с первым входом второго элемента И 15, второй вход которого соединен с вторым входом первого элемента И 14 и с первым

выходом блока 13 анализа, второй выход которого соединен с управляющими входами первого 7 и второго 8 сдвигателей, инверсные выходы которых соединены соответственно с вторыми информационными входами первого 9 и второго 10 мультиплексоров, управляющие входы которых соединены с выходом первого регистра 1, выходы первого 11 и второго 12 сумматоров соединены соответственное информационными входами третьего 3 и шестого 6 регистров, выход шестого регистра 6 соединен с вторым информационным входом четвертого мультиплексора 18 и является выходом 24 устройства, выход третьего регистра 3 соединен с вторым информационным входом третьего мультиплексора 17, выход которого соединен с информационными входами первого 1 и второго 2 регистров, выход четвертого мультиплексора 18 соединен с информационными входами четвертого 4 и пятого 5 регистров, выход второго элемента И 15 соединен с входами синхронизации первого 1, второго 2, четвертого 4 и пятого 5 регистров, выход второго регистра 2 соединен с входом блока 13 анализа и с информационным входом первого сдвигателя 7, выход пятого регистра 5 соединен с информационным входом второго сдвигателя 8, блок 13 анализа содержит п узлов формирования 1-го разряда унитарного кода Kj (фиг.З), где I 1,m; т - разрядность мантиссы операнда, j - номер итерации, и схему формирования сигнала окончания деления, представляющую собой т-входовой элемент ИЛИ 25, выход 26 которого является первым выходом блока 13 анализа, a m входов 27 элемента ИЛИ 25 соединены с информационными выходами п узлов формирования унитарных кодов, в каждый из которых входит первый элемент НЕ 28, вход которого является входом 29 нулевого разряда мантиссы операнда, а выход элемента НЕ 28 соединен с первыми входами первого 30, второго 31 и третьего 32 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, вторые входы которых являются соответственно входами 33-35 I- го (1+1)-го и (1+2)-го разрядов мантиссы операнда, выход первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 30 соединен с первым входом первого элемента-И 36 и является первым разрядом информационного выхода 37 узла формирования унитарных кодов, выход второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 31 соединен с входом второго элемента НЕ 38, первым входом элемента И 39 и является вторым разрядом информационного выхода 37 узла формирования унитарных кодов, выход третьего элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 39 соединен с вто-рым входом второго элемента И 39 и является третьим разрядом информационного выхода 37 узла формирования унитарных кодов, выход второго элемента НЕ 38 соединен с вторым входом первого элемента И 36, выход которого соединен с первым входом элемента ИЛИ 40, второй вход которого соединен с выходом второго элемента И 39, а выходы элементов ИЛИ 40 всех п узлов формирования унитарных кодов соединены с входами 41 m-входового элемента И 42, выход которого является вторым выходом 43 блока анализа.

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

Например, X 0,71875, Y 0,5; Y/X 0,6956; п 8 m п + logtn 11.

YI

Унитарный

код К| 01000000

00100000

0.1000000000 0.001000000

,0.101000000

0.000101000

0.101101000 00000010 0.000001011 0.101100101

точность вычисления

Число итерации равно 3, т.е. п. В известY/X 0,10110010101 0,69775390625,

Д 2 0,00390625. Г 2

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

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

-fc- - где Vnp - объем оборудования известного устройства;

УИЗ - объем оборудования предлагаемого устройства.

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

Xi ,

сумма по модулю 2;

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

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

Х| - промежуточные значения 1-го разряда мантиссы делителя.

20

Zi (XiAXi -nvXi +iAx +2)n zk,

К о

где Zi - 1-й разряд унитарного KJ;

П- операция логического умножения. При этом Zi 1 в том месте унитарного

кода, которое соответствует данному Kj. Например п 8

Унитарный кодKJ

1000000Zi 1 ,1

01000000Z2 12

0000100 5 00000010 7

STOP - Ј x ,

где - операция логического сложения.

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

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

XJ-H Xj + Cj Yj-и Yj + ej

2 KJXj- 2 KJYj1;Y/X,

где X - делитель, Y - делимое.

Разрядность операндов т для обеспечения точности вычисления в п двоичных 50 разрядов должна быть

m n + log, п.

Обозначают Хо - старший разряд делителя, тогда мантисса делителя начинается с Xi разряда.

Алгоритм определения KJ в каждой итерации состоит в следующем. Если Хо 0, то в мантиссе делителя определяет порядковый

номер К старшего О и анализируется разряд, следующий за ним. Если за нулем следует О, то Kj К-1, если 1, то Kj К. Если Хо 1, то в мантиссе делителя определяется порядковый номер к старшей 1 и анализируется разряд, следующий за ней. Если за единицей следует Г, то Kj К-1, если О, то Kj К. Если Хо 0, то С) -И, если Хо 1, то е -1. После того, как делитель принимает значение, равное 1 (0.111... или 1.000...) вычисление заканчивается, а в канале Y находится результат деления Y/X. При этом максимальное количество итераций, необходимое для получения результата, не превышает j- , что в два раза меньше, чем у

известного устройства (п-1). Начальные условия Хо X, Yo Y, Исходя из данного алгоритма анализа делителя блок анализа работает в соответствии с логическими выражениями:

Xi Xo©Xi; Х2 - ХоОХа;

Хт ХаЭХт,

где Хо, Xi, X2Хт - значения выходных

разрядов второго регистра;

Xi , - промежуточные значения m-разрядной мантиссы делителя; (D - сложение по модулю 2.

Zi (Х/Л Хи-1 v Хн-1 Л Хм ) Л nzk,

К 0

где Zi - разряд унитарного кода;

П- операция логического умножения..

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

STOP 2)Xi ,

1 1

где 2 - операция логического сложения.

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

По сигналу Исходное состояние триггер 16 устанавливается в состояние О, который поступает на управляющие входы третьего 17 и четвертого 18 мультиплексоров. При этом третий 17 и четвертый 18 мультиплексоры передают информацию со своих первых входов. По сигналу Исходное состояние 21 второй регистр 2 устанавливается в состояние 0101... 01, что обеспечивает сброс сигнала STOP 1. Сигнал с первого выхода блока 13 анализа деблокирует прохождение первый 22 и второй 23 синхро- 5 серии через первый 14 и второй 15 элементы И. Интервал между тактовыми импульсами второй 23 и первой 22 синхросерий равен суммарной задержке блока 13 анализа, первого сдвигателя 7, первого мультиплексора

0 9. первого сумматора 11. По второй синхросерий происходит запись делителя в первый 1 и второй 2 регистры, делимого в четвертый 4 и пятый 5 регистры. Блок 13 анализа выдает значение Kj в каждой итерации. На выхо5 де первого сдвигателя 7 формируются прямое и инверсное значения Xj, на выходе второго сдвигателя 8 формируются прямое и инверсное значения 2 YJ. Управляющим сигналом для первого 9 и второ0 го 10 мультиплексоров является Хо, поступающий с выхода первого регистра 1. Если Хо 0, то первый 9 и второй 10 мультиплексоры пропускают прямое значение Xj, Yj ( Јj +1) соответственно,

5 если Хо 1, то инверсные значения ( е -1). Первый сумматор 11 осуществляет операцию Xj + ej Xj, второй сумматор 12 осуществляет операцию YJ + е YJ. По первой синхросерий 22 результат Xj+1, Yj+1

0 записываются в третий 3 и шестой 6 регистры соответственно. По первой синхросерий 22 триггер 16 устанавливается в 1 и третий 17 и четвертый 18 мультиплексоры переключаются на вторые информационные входы.

5 Интервал между импульсами первой 22 и второй 23 синхросерий равен времени задержки третьего 17 или четвертого 18 мультиплексора. Итерационный процесс продолжается до тех пор, пока не сформи0 руется сигнал STOP 0, который блокирует прохождение первой 22 и второй 23 синхросерий через первый 14 и второй 15элементы И. В шестом регистре 6 находится результат деления Y/X, который поступает на выход

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

Устройство может быть реализовано на базовом матричном кристалле 1548ХМЗ. При этом длительность одной итерации для п 56 равна 40 не. Время выполнения опе0 рации деления для точности в 56 двоичных разрядов мантиссы составит 1.12 мкс.

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

Таким образом предлагаемое техническое решение обеспечивает простоту и регулярность схемного решения, уменьшения оборудования в 2 раза, отсутствие коррекции и подготовительного такта внутри итерации. Обеспечивается повышение

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

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

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

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