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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

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

Республик

t tt>955039 (61) Дополнительное к авт. свид-ву— (22) Заявлено 27.06.80 (21) 2950449/18-24

И)М Кп з

0 06 F 7/52 с присоединением заявки Мо

Государственный комитет

СССР по делам изобретений и открытий (23) Приоритет

Опубликовано 300882. Бюллетень ¹ 32 (53)УДК 681.325 (088 ° 8) Дата опубликования описания 30.08.82

A.Ï. Заморин и А.A. Маханов

1„ (72) Авторы изобретения

Кировский политехнический институт. (11) Заявитель

{,54) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ ДВОИЧНЫХ ЧИСЕЛ

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

Известны устройства деления, содержащие регистры, сумматоры и элементы И-ИЛИ {1).

Однако данные устройства характеризуются низким быстродЕйствием.

Известно устройство деЛения, которое на каждом шаге производит сложение tl -разрядных чисел C распространением переноса через все tl-разряды Ю.

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

Цель изобретения - увеличение быстродействия устройства за счет исключения распространения переноса через все разряды.

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

25 разрядных выходов первого блока вычи тателей, первая группа входов которого соединена с группой выходов первого блока сумматоров, а вторая группа входов — с группой выходов блока

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

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

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

З5 входами йятого и десятого элементов И, седьмыми входами седьмого и тринадцатого элементов И, шестым входинена с первой группой выходов треть

40 формирования единиц соединена с.групБлок анализа содержит с первого по

50 55

И

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

;четвертого и одиннадцатого элемендом двенадцатого элемента И и одиннадцатым входом группы блока анализа, пятый вход четвертого элемента И соединен с пятым входом одиннадцатого элемента И и двенадцатым входом группы блока анализа, первый вход пятого элемента И соединен с четвертым входом десятого элемента И и тринадцатым входом группы блока анализа, выход первого элемента И соединен с первыми нходами первого и третьего элементов ИЛИ, выход четвертого элемента И вЂ” с четвертыми входами первого и третьего элементов

ИЛИ, выход пятоro элемента И вЂ” с пятыми входами первого и третьего элементов ИЛИ,выход шестого элемента Ис шестым входом первого элемента ИЛИ и первым входом второго элемента ИЛИ, выход седьмого элемента И вЂ” с седьмым входом первого элемента ИЛИ и вторым входом второго элемента ИЛИ, выход восьмого элемента И вЂ” с третьим входом второго элемента HJIH u первым входом четвертого элемента ИЛИ, выход девятого элемента И вЂ” с четвертым входом второго элемента ИЛИ и вторым sxo oM четвертого элемента ИЛИ, выход десятого элемента И вЂ” с шестым

955039 входом третьего элемента ИЛИ и третьим входом четвертого элемента ИЛИ, выход одиннадцатого элемента И вЂ” с седьмым входом третьего элемента ИЛИ и четвертым входом четвертого элемента ИЛИ, выход двенадцатого Элемента И вЂ” с восьмым входом третьего элемента ИЛИ и пятым входом четвертого элемента ИЛИ, выход тринадцатого элемента И вЂ” с девятым входом. третьего элемента ИЛИ и шестым входом четвертого элемента ИЛИ, вйход четырнадцатого элемента И вЂ” с десятым входом третьего элемента ИЛИ и седьмым входом четвертого элемента

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

Блок формирования сдвига содержит

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

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

r-ых разрядов соединены со вторыми входами элементов ИЛИ (r-1)-ых разрядов, а выходы схем ИЛИ соединены с выходной шиной блока формирования сдвига.

На фиг. 1 изображена блок-схема предлагаемого устройства деления; на фиг. 2 — функциональная схема блока анализа; на фиг. 3 — функциональная схема блока формирования сдвига на три разряда; на фиг. 4 — функциональная схема блоков формирования еди 0 ниц на один разряд; на фиг. 5. — функ- циональная схема блоков счетчиков положительных и отрицательных единиц (три счетчика), вариант; на фиг. 6 функциональная схема блоков вычита65 телей.

Блок формирования единиц содержит.

r разрядов, каждый из которых содержит первый, второй, третий, четвертый, пятый, шестой, седьмой и восьмой элементы И, первый, второй, третий и четвертый элементы ИЛИ, причем первый вход первого элемента И соединен с первым входом пятого элемента И и информационной шиной блока формирования единиц, первый вход второго элемента И соединен с первым входом шестого элемента И и информаЦ ионной шиной блока формирования едит И ниц, второй вход первого элемента соединен со вторыми входами второго, пятого и шестого элементов И и информационной шиной блока формирования единиц, первый вход третьего элемента И соединен с первым входом седь мого элемента И и информационной шиной блока формирования единиц, первый вход четвертого элемента И соединен с первым входом восьмого элемента И и информационной шиной бгока формирования единиц, второй вход третьего элемента И соединен со вторыми входами четвертого, седьмого и восьмого элементов И и информационной шиной блока формирования единиц, третьи входы первого, третьего, шестого и восьмого элементов И сое10 динены между собой и с управляющей шиной блока формирования единиц, третьи входы второго, четвертого, пятого и седьмого элементов И соединены между собой и с управляющей ши)5 ной блока формирования единиц, первый вход первого элемента ИЛИ соединен с выходом первого элемента И, а вто. рой вход первого элемента ИЛИ вЂ” с выходом элемента И, первый вход второго элемента ИЛИ соединен с выходом третьего элемента И, а второй

> вход второго элемента ИЛИ вЂ” с выходом четвертого элемента И, первый вход третьего элемента ИЛИ соединен

25 с выходом пятого элемента И, а вто5 рой вход третьего элемента ИЛИ вЂ” с выходом шестого элемента И, первый вход четвертого элемента ИЛИ соединен с выходом седьмого элемента И, 30 а второй вход четвертого элемента

ИЛИ вЂ” с выходом восьмого элемента И, . выходы первого и второго элементов

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

ИЛИ вЂ” со второй группой выходов блока формирования единиц.

Введенные в предлагаемое устройство блоки вычитателей, блоки счетчи40 ков положительных и отрицательных единиц, блоки формирования единиц, блок формирования сдвига и блок анализа позволяют производить вычисления в избыточной знакоразрядной сис45 теме счисления с основанием 2 и разрядными цифрами, принимающими значение(-3, -2, -1, О, 1, 2, 3 . Это позволяет во всех случаях при выполнении суммирования устранять распростране5р ние перенбсов ер з все и разряды, что обеспечивает сокращение времени деления в предлагаемом устройстве.

955039

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

13 блоки счетчиков отрицательных единиц, первый 14,второй 15, третий

16 и четвертый 17 блоки формирования единиц, блок 18 анализа и блок 19 формирования сдвига.

Блок 18 анализа (фиг. 2) содержит элементы И 20 и с.первого по четвертый элементы ИЛИ 21-24.

Блок 19 формирования сдвига (фиг. 3) содержит и разрядов, каждый разряд содержит первый и второй элементы схемы И 22 и 23 и элемент

ИЛИ 24.

Блоки 14-17 формирования единиц содержат и разрядов, каждый из которых содержит элементы И 25 и ИЛИ 26.

Блоки 10 и 11 счетчиков положительных единиц и блоки 12 и 13 счетчиков отрицательных единиц (фиг. 5) содержит и счетчиков 27, каждый из которых содержит первые 28 и вторые

29 одноразрядные сумматоры на три входа (на фиг. 5 изображено три счетчика 28) .

Блоки 8 и 9 вычитателей (фиг. 6) содержат и вычитателей двухразрядных чисел 30 (на фиг. 6 изображены три разряда вычитателей).

Деление в прецлагаемом устройстве выполняется в знакоразрядной системе счисления, В этой системе счисления любое и-разрядное число х () х(<1) представляется в виде х« )(< (g«< < с ). 2-г где с< .1 6 (0 1) — мЛадшая цифра r-го разряда, р 6 (0,1 — старшая цифра r-ro разряда, (6 (0,13 — знак r-го разряда (g"«0 соответствует знаку + ; g = 1 соответствует знаку †).

Процесс деления Z = x/ó (х и у нормализованные двоичные числа) описывается уравнениями (1) „,.„.2(l)» E 2 " " . . (2) где 1 = 1,2,3,...,п.

Начальные, условия: х„= 2х, у„=2у.

Результат Z = х >.

Переменные Е„и m „.в (1) и (2) на каждой i-ой итерации определяются по значениям старших разрядов у„ таким образом, чтобы первый разряд переменной у„в . результате выполнения сложения в (2)

Ч;E;2

5 принимал нулевые значения. При этом переменная у; стремится к значению уя = 2, а переменная х — к значе- .

П

4 нйю х„= х/у. В результате модели10 рования работьг предлагаемого устройства на ЭЦВМ Наири 2 для всех возможных значений аргументов х и у выявлена зависимость Е„и m îò значений старших разрядов у;, обеспечи15 вающая сходимость итерационного про-. цесса (1) и (2) .

В табл. 1 приведена зависимость значений E„è m„ от значений старших разрядов переменной у„.

20 В предлагаемом устройстве регистры делимого 1 и делителя 2 предназначены для хранения переменных х, и у„, представленных в знакоразрядной системе счисления. Каждый регистр содержит и разрядов дробной части и один разряд целой части переменных, каждый разряд содержит три триггера для хранения знака )) „. старшей цифры „ и младшей цифры a„"

Сдвигатели 3 и 4 осуществляют параллельный сдвиг регистров 1 и 2 на (i — m;) разрядов вправо и выполнены на матрицах элементов И и ИЛИ.

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

Блок 18 анализа (фиг. 2) выполнен на логических элементах И и ИЛИ и реализует следующие логические функ45 ции в соответствии с табл. 2 истиннос ти;

).R, уЯРФ I1",.Ж „3„р„М; К»»(3ЭЧ

»» 2 Я Я Ъ » » Ч

50 "II g.),g„g„P " " Р " Р 2- l » < 1 2 < ° 2- Ъ ч . ",p у,„чу,o„т; р„чу.<х,„у„g„ы; у„„P„; =,ж„ ; „; „ „ ;;,ЧУ„П."„ „й, Ч

$ „06» g,. „ (, „g,. (3 < u 0<, 65 < =>»«, 1:л" g„о, < р Ф „ g, р< Ч

955039

2- l -ъ g q-т-g т з з " 3 „ 4„У „p a У л р „v 3 „x; 3 о 3

1 л °

Приведенные булевые функции реализуются в блоке анализа на схемах

И 20 и ИЛИ 21. Значения переменных

4 «2 2 — 2 2. — Я (1 г g4 ко » к $1F f1I I 1 t Рл f+g ю ;

, P Р; на вход блока анализа поступают с выходов старших разрядов регистра 2.

Счетчик 6 тактов предназначен для счета номера итерации, дешифратор 7 для дешифрирования кода номера итерации.

Блок 19 формирования сдвига(фиг.3) предназначен для формирования величи.ны сдвига j = (1-щ;). Значение i по." ступает на информационный вход блока

19 с выхода дешифратора 7, значение щ4 поступает на управляющий вход блока 19 с выхода блока 18 анализа. .Переменная m„ представляется двоич- . ными переменными L u L. Если L=0(L=1), то j=i, если L=l(L=O), то j=i-l, Указанные преобразования,для каждого ,значения i выполняются в блоке 19 формирования сдвига схемами И 22 и 23 и ИЛИ 24. Значение j с выхода блока

19 поступает на управляющие входы блоков 3 и 4 сдвига для управления величиной сдвига. Первый 14, второй

15, третий 16 и четвертый 17 блоки формирования единиц (фиг. 4) предназначены для формирования положиог тельных + E" и отрицательных — f единиц с весом 2 (r=1,2,...,n) разрядных цифр ос и "„ регистров 1 и 2 с учетом их знаков », „""" и значения переменной Я„. Блоки 14 и 16 формируют положительные и отрицательные единицы, соответствующие слагаемым уравнения (1 ): х „и E „2 " ° х; блоки 15 и 17 формируют единицы, соответствующие слагаемым уравнения (2) у, и Е; 2 g< . На. информационные входы блоков 14 и 15 поступают разряды х„и у„с выходов регистров 1 и 2. На информационные входы блоков 16 и 17 поступают сдвинутые íà j =(i m <) вправо разряды регистров 1 и 2 с выходов блоков 3 и 4 сдвига. Значения Е< (двоичные переменные S и В) поступают на управляющие входы 6JIQKQB 16 и 17 формирования единиц с первого выхода блока

18 анализа. На управляющие входы блоков 14 и 15 поданы постоянные значения S = 1 и В = О, что соответствует значению Е, = +1 (управляющие входы блоков 14 и 15 на фиг. 1 не указаны).

На фиг. 4 приведена функциональная схема одного разряда блоков 14-17, осуществляющая формирование двух положительных) +Ги двух отрицательных — (, " единиц с одинаковым весом 2

На выходе блоков формируется положительная единица, если соответствующие цифры разряда oc„" и Р совпадают, и отрицательная единица, если знаки разные. Булевые функции для формирования положительных и отрицательных единиц представляются:

4.1г=5бг Сгч В г г .

-3=Bg g, v 5 f g, - =8 ч 5у" р" .

Приведенные булевые функции реализуются в блоках формирования 14-17 на схемах И 25 и ИЛИ 26. Каждый разряд блоков содержит восемь схем И 25 и четыре схемы ИЛИ 26. Положительные единицы поступают на входы счетчиков положительных единиц, отрицательные единицы — на входы счетчиков отрицательных единиц. Блоки счетчиков положительных единиц 10 и 11 и отрицательных единиц 12 и 13 (фиг. 5). сос- . тоят из счетчиков 27. Каждый счетчик содержит первый 28 и второй 29 одноразрядные сумматоры на три входа комбинационного типа. (Ha фиг. 5 введеЗ5 ны следующие обозначения: «+ P — знаг чение.положительных и отрицательных единиц, поступающих с соответствующих выходов блоков 14 или 15 формирования единиц с весом 2 " р + 0г40 значение положительных. и отрицательных единиц, поступающих с соответствующих выходов блоков 16 и 17 формйрования единиц с весом 2 ; + сагзначение положительной или отрицатель

-г

g5 ной промежуточной суммы с весом 2

+t" — значение полбжительного или от,рицательного переноса в r-ый разряд).

Функционирование каждого счетчика положительных единиц 27 описывается

50 следующими уравнениями: I этап выполняется на первом одноразрядном сумматоре 28

++2(," +я" =+ В "+ " (г

II этап выполняется на втором одноразрядном сумматоре 29

42рг ГФяг (г(3г

60 где ыг,g" е {0,<) .

Функционирование счетчиков отрицательных единиц описывается аналогичными уравнениями с заменой знака

65 + на знак - . Ha выходах счет955039 ° чиков положительных единиц формируются положительные суммы +S" = +2 p".+

+ g" на выходах счетчиков отрицательных единиц - отрицательные суммы -S = -2 - Ы . Значения положительных сумм поступают на первые входы блоков 10 и 11 сумматоров, значения отрицательных сумм — на вторые входы.

На фиг. 6 приведена функциональная схема трех разрядов 30 блоков 8 и 9 вычитателей. Функционирование каждого разряда описывается уравнением

10!

re g„„(2)„«w ob„,„.) — значение г-го разряда переменных х„ или у„.. co знаком, получающееся в результате выпол- .О нения 1-ой итерации.

Результаты вычисления переменных х„, у„ с выходов блоков 8 и 9 вычитателей поступают на входы регистров

1 и 2, где они хранятся íà (i+1) ой итерации.

Предлагаемое устройство деления работает следующим образом. Деление производится над положительными числами, знак результата определяется по сочетанию знаков делимого и делителя. Перед началом вычисления в регистры 1 и 2 заносятся сдвинутые влево на один разряд делимое и делитель 2х и 2у. Далее производится выполнение и итераций в со- З5 ответствии с уравнениями (1) и (2) .

На каждой итерации производятся следующие действия.

В счетчике тактов 6 производится прибавление единицы, в дешифраторе 40 производится дешифрирование номера итерации 1, значение которого поступает на информационный вход блока 19 формирования сдвига.,В блоке 18.анализа по,значениям старших разрядов регистра 2 формируются значения переменных щ„ и Е;, значение m, поступает на управляющий вход блока 19 формирования сдвига, значение E < на управляющие входы третьего и четвертого блоков формирования единиц

l6,17. В блоке 19.формирования сдвига формируется величина. сдвига j=(1,), которая поступает на управляющие входы блоков 3 и 4 сдвига. В блоках

3 и 4 производится сдвиг вправо на разрядов переменных х; и у„, поступающих соответственно с регистров 1 и 2;

В первом 14 и втором 15 блоках формирования единиц производится формирование положительных + " и отри- о цательных — (единиц разрядных цифр " и (" поступающих с регистров 1 !

Г Р <-4. и 2, с учетом их знаков g и g

В третьем 16 и четвертом 17 блоках формирования единиц производится фор- 6$ мирование положительных и отрицательных единиц, сдвинутых в блоках 3 и 4 разрядных цифр М" и P ""+" регистров

1 и 2. Формирование единиц происходит с учетом знаков разрядных цифр

g" и g " " и значения Ц . Таким об . разом, на входах блока 14 формируются единицы, соответствующие первому слагаемому уравнения (1) х на выходах блока 16 — второму слагаемому Е; 2 " х„ . На выходах блока 15 формируются единицы, соответствующие первому слагаемому уравне нияя (2) у„, на выходах блока 17 второму слагаемому Е; 2

Далее в блоке 10 производится сум- мирование положительных единиц, поступающих с выходов блоков 14 и 16, 1 в блоке 12 — суммирование отрицательных единиц, поступающих с блоков 14 и 16, в блоке 11 — производится суммирование положительных единиц, поступающих с выходов блоков 15 и 17, в блоке 13 — суммирование отрицатель ных единиц, поступающих с блоков 15 и 17.

В блоке 8 вычитателей производится вычитание из суммы, поступающей с выхода блока 10, суммы, поступающей с выхода блока 12, .результат вычитания записывается в регистр 1. В блоке 9 производится вычитание из суммы, по- . ступающей с выхода блока 11, суммы, поступающей с выхода блока 13, результат вычитания записывается в регистр 2 со сдвигом на один разряд влево. Прн этом в регистрах значения переменных х;, у; заменяются на их новые значенйя х„„, у„,, вычисленные в данной итерации.

При сдвигах влево в регистре 2 старшие разряды переменной теряются.

Однако оставшиеся разряды дробной части обеспечивают правильное выполнение алгоритма деления °

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

B табл. 3 приведен пример деления двоичных чисел х = 0,100110, у =

О, 101110.

Регистр 2 делителя не содержит разрядов целой части, поэтому значение целой части у; равно нулю.

Преобразование результата иэ энакоразрядной системы счисления в двоичную систему путем алгебраического

14 13 .955039 суммирования двух положительных и двух отрицательных чисел:

+1,000000

+0,00100 0

-0,010000

-0 000000

Х

+О, 110101

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

В этом случае на его входы,одновре= менно подаются четыре числа с регистра 1.

Выполнение итераций в предлагаемом устройстве может быть прек-(> (5 ращено на 1-ой итерации, если все разряды у> окажутся нулевыми. Это

4 позволяет дополнительно повысить среднее быстродействие устройства.

В прототипе на каждой итерации; )() производится суммирование двух иразрядных чисел на п-разрядном сум.маторе с распространением переносов через все и разрядов. Таким образом, общее время деления, выраженное в единицах задержки на элементе, пропорционально п . В предлагаемом устройстве суммирование на каждой итерации производится в знакораэрядной системе счисления, при этом распространение переноса происходит иэ каждого разряда только в один соседний слева разряд (функциональная схема блока счетчиков на фиг. 5). Таким образом: суммарное время деления в 1

35 предлагаемом устройстве, выраженное в единицах задержки не элементе, пропорционально и.

Проведен сравнительный анализ времени деления в известном и предлага- 4Q емом устройстве.

В прототипе в процессе вычисления производится п суммирований с распространением переноса. Общее время деления Т составляет

Т1 и Е> где t - время выполнения суммироваЕ ния с распространением переноса двух п-разрядных чисел для различных ва- 50 риантов построения сумматора: последовательный сумматор, параллельный сумматор с последовательным переносом. сквозным переносом и т.д.

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

И-ИЛИ), в блоках счетчиков (2 элемента И-ИЛИ) и в блоках вычитателей (элемент И-ИЛИ). Таким образом, время выполнения одной итерации в предлагаемом устройстве, выраженное в единицах времени tåó составляет

° t

7 н rl X."

Время выполнения и итераций

Т,„= 7 ° t

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

Т2 = (1+ — ) ° t

tl п Е

Общее время деления в предлагаемом устройстве

Т2 = Т2У + Т2 =(7 4 -) ° Е

В табл. 4 приведены расчетные значения времени деления в прототипе Т и в предлагаемом устройстве Т для различных значений разрядности и .и соответс гвующие им значения коэффициента увеличения быстродействия К.

Значение коэффициента К определяется выражением

К = л

Т

Т2

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

955039

+ (Ъ„f, rn;

+1

40

0 и р и м е ч а н и е, м<, ;. — значения со знаком

Р младшей и старшей цифры г-го разряда на < --ой итерации переменной у„; знак означает, что данная переменная не влияет на значения 1; и н ;.

Я В L ?.

Таблица 2

1 О

О 1 О

Ф О

О О О

О 1 О О

1 О

1 О

О 1 О

О 1 1

1 l О

П р и м е ч а н и е. S — двоичная переменная, принимающая эначе ние l,если Б =+1;  — двоичная переменная, принимающая значение l,åñëè „.=-1;при „ =О

S = О и В = О, L — двоичная переменная, принимающая значение 1, если m „ = 1, L — инверсная L; знак " — неопределенное значение. Ъ /Ъ Л /\ф 1

О 1 1 l 1

О .1 0 1 1

О 1 - О 1

О О 1

1 1

О 1 1 1 1

О 1

О 1

О 1

О 1

О 1

1 О

1 О

1 . О

955039

Таблица 3

Значение разряда

m(УГ

1 О

2 -1 2

3 -1 3

4 0

+1, +0 +1 +1 +1 +0 +О

+О, +1 +1 +1 +О +О +О

+О, +1 +0 +1 -1 +О +О

+О, Ю -1 -2 +О +1 +О

+О „-1 -2 +О +1 +О +О

+О, +О +О +1 -2 +О +О

+О, +О +l -2 +О +О +О

+1, +О +О +1 +1 +0 +0

+1, +О +О +1 +1 +О +О

+1, +О -l +1 +1 -1 -1

+1, +О -1 +О +1 +О -2

+1, +О -1 +О +1 +О -2

+1, +О -1 +О +2 -1 -1

1, +О. -1 +О +2 — 1 -1

5 +1 4

6 О

Таблиц а4 и 10 20 30 40 50

10 20 t 7,30СЕ 7 15tE

30t

401

60t

7,05

8,51

501

7,06 t

Т2

4,23

2,80

1,37

7,08

5,65

Формула изобретения

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

40 торого соединена со второй группой ,выходов первого блока формирования единиц, информационная шина которого ,соединена с группой разрядных выходов регистра делимого и информацион45 ной шиной первого сдвигателя, информационная шина второго блока формирования единиц соединена с группой разрядных выходов первого сдвигателя,. группа разрядных входов регистра де о лителя соединена с группой разрядных выходов второго блока вычитателей, первая группа входов которого соединена с группой выходов третьего блока сумматоров, а вторая группа входов второго блока вычитателей - с выходом четвертого блока сумматоров, первая группа входов которого соединена с первой группой выходов третьего блока формирования единиц, а вторая группа входов четвертого блока О сумматоров соединена с первой группой выходов четвертого блока формирования единиц, вторая группа выходов которого соединена с первой группой входов третьего блока сумматоров, 65 вторая группа входов которого соеди

955039

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

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

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

1О вход пятого элемента И соединен с четвертым входом десятого элемента И и тринадцатым входом группы блока анализа, выход первого элемента И соединен с первыми входами первого 5,к третьего элементов ИЛИ, выход вто.рого элемента И вЂ” со вторыми входами первого и третьего элементов ИЛИ, выход третьего элемента И вЂ” с третьими входами первого и третьего элеjg ментов ИЛИ, выход четвертого элемента И вЂ” c четвертыми входами первого и третьего элементов ИЛИ, выход пятого элемента И вЂ” с пятыми входами первого и третьегО элементов ИЛИ, выход шестого элемента И вЂ” с шестым входом первого элемента ИЛИ и первым входом второго элемента ИЛИ, выход седьмого элемента И вЂ” с седьмым входом первого элемента ИЛИ и вторым входом второго элемента ИЛИ, выход восьмого элемента И вЂ” с третьим вхо. дом второго элемента ИЛИ и первым входом четвертого элемента ИЛИ, выход девятого элемента И вЂ” с четвертым входом второго элемента ИЛИ и вторым входом четвертого элемента ИЛИ, выход десятого элемента И вЂ” с шестым входом третьего элемента ИЛИ и третьим входом четвертого элемента ИЛИ, выход одиннадцатого элемен4О та И вЂ” с седьмым входом третьего элемента ИЛИ и четвертым входом четвертого элемента ИЛИ, выход двенадцатого элемента И вЂ” с восьмым входом третьего элемента ИЛИ и пятым входом

4$ четвертого элемента ИЛИ, выход тринадцатого элемента И вЂ” с девятым входом третьего элемента ИЛИ и шестым входом четвертого элемента ИЛИ, а ,выход четырнадцатого элемента И вЂ” с десятым входом третьего элемента ИЛИ и седьмым входом четвертого элемента ИЛИ, выходы первого и четвертого элементов ИЛИ соединены соответственно с первым и вторым выходами первой группы выходов блока анализа, выходы второго и третьего элементов

ИЛИ соединены соответственно с первым и вторым выходами второй группы выходов блока анализа.

3. Устройство по п. 1, о т л и ч а ю ш е е с я тем, что блок формирования сдвига содержит Г разрядов (г-1,2,...,n, где п.-разрядность уст ройства), каждый из которых содержит первый и второй элементы И и элемент

22

955039

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

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

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

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

15 первого элемента И, а второй вход первого элемента ИЛИ вЂ” с выходом второго элемента И, первый вход второго, элемента ИЛИ соединен с выходом третьего элемента И, а второй вход второ20 го элемента ИЛИ вЂ” с выходом четвертого элемента И, первый вход третьего элемента ИЛИ соединен с выходом пятого элемента И, а второй вход третьего элемента ИЛИ вЂ” с выходом

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

Источники информации, принятые во внимание при экспертизе

1. Папернов А.А. Логические основы цифровой вычислительной техники.

40 N., Советское радио, 1972, с. 235.

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

9 570054, кл. G 06 F 7/52, 1977 (прототип).

955039 г-1

Ь i j г

r,„

pl"

+o(Фф "

Заказ б437/52 /

+ f

М

tf (+ ьг (+ ГЛ

r-1 к М г с

-ГУ," с

Составитель В. Венцель

Редактор Л. Пчелинская. Техред A.Ач Корректор М. Коста

Тираж 731 Подписное

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

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

Филиал ППП Патент, r. Ужгород, ул. Проектная, 4