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

 

УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ, содержащее регистры делимого и делителя , преобразователь прямого кода в обратный, сумматор и блок управления , причем выход регистра делимого соединен с первым информационным входом сумматора, выход регистра делителя соединен с информационным входом преобразователя прямого кода в обратный, первый вькод блока управления соединен с входом разрешения записи регистра делимого, второй выход блока управления соединен с входом разрешения записи регистра делителя , третий выход блока управления соединен с управляющим входом сумматора, выход окончания сложения которого соединен с первым входом блока управления, отличающееся тем, что, с целью повышения быстродействия работы устройства при делении чисел в избыточной .степенной системе счисления, в него введены блок контроля регистра делимого и блок контроля регистра делителя , казкдый из которых содержит группу элементов И, количеством на единицу меньше разрядности соответствующего контролируемого регистра, и элемент ИЛИ, выход которого является выходом блока контроля, а входы соединены соответственно с выходами элементов И группы, у которых первые входы объединены и являются управляющим входом блока контроля, а второй вход каждого i-ro элемента И группы (i 1,...,п) соединен с третьим входом (i+1)-ro элемента И группы и является

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

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

РЕСПУБЛИК

4(ц G 06 F 7/49

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

К ABTOPCHOMV СВИДЕТЕЛЬСТВ,Ф

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР пО делАм изОБРетений и ОтнРытий (21) 3563467/24-24 (22) 14.03.83 (46) 23.04.85. Бюл. Ф 15 (72) В.В.Роздобара, И.А.Баранов, Г.В.Кремез, В.П.Лачугин и С.Н.Мордашов (53) 681.325 (088.8) (56) Авторское свидетельство СССР и 330451, кл. G 06 F 7/52, 1973.

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

Ф 744564, кл. G 06 F 7/52, 1980. (54) (57) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ, содержащее регистры делимого и делителя, преобразователь прямого кода в обратный, сумматор и блок управления, причем выход регистра делимого соединен с первым информационным входом сумматора, выход регистра делителя соединен с информационным входом преобразователя прямого кода в обратный, первый выход блока управления соединен с входом разрешения записи регистра делимого, второй выход блока управления соединен с входом разрешения записи регистра делителя, третий выход блока управления соединен с управляющим входом сумматора, выход окончания сложения которого соединен с первым входом блока управления, о т л и ч а ю— щ е е с я тем, что, с целью повьппения быстродействия работы устройства при делении чисел в избыточной .степенной системе счисления, в него введены блок контроля регистра делимого и блок контроля регистра делителя, каждый из которых содержит группу элементов И, количеством на единицу меньше разрядности соответст „„SU„„1151955 A вующего контролируемого регистра, и элемент ИЛИ, выход которого является выходом блока контроля, а входм соединены соответственно с выходами элементов И группы, у которых первые входы объединены и являются управляющим входом блока контроля, а второй вход каждого >-го элемента

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

1151955

Lo>. ãâåòñ-твенно с инф>>рмапис>иными

Вхс>дам!! с>>>Оков к!>нтрО>!>! делимого и делителя и с первым и вторым информационными вхслами " óììàòîðà,,второй выход которого соединен с информационным входом регистра делимого, выход преобразователя прямого кода в обратный соединен с информационным входом регистра делителя, второй вход блока

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

Цель изобретения — повышение быстродействия работы устройства при делении чисел в избыточной степенной системе счисления.

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

Устройство содержит регистр 1 делимого, регистр 2 делителя, блок

3 управления, преобразователь 4 прямого кода в обратный, блок 5 контроля регистра делимого, блок 6 контроля регистра делителя, сумматор 7.

Первый вход 8 устройства соединен с первым входом регистра 1 делимого, второй вход 9 устройства соединен с первым входом регистра 2 делителя, остальные входы 10.-12 устройства соединены с соответствующими входами блока 3 управления. Выход 13 регистра 1 делимого соединен с первым входом сумматора 7 и входом блока 5 контроля регистра делимого. Выход

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

15-20, объединенные в выходную шину блока 3 управления, соединены соответственно с входами разрешения записи регистра 1 делимого, регистра 2 делителя, управляющими входами преобразователя 4 прямого кода в обуп1>а>>>!енс>я я>!. >>>> т(>я >>х>>;I>>>I >>!>>>3>!с>ка си(те: >! c ч и< .>>е>>и н > t .т1>(>! с в а tpl тий Rxop блока у>!рая>>е>!ия являет ся пусковым входом у< трс>йства, четвертый вход блока ус!1>а>!>!ения является синхровходом устройства, а выход регистра делимого является выходом результата устройст ва. ратный, блоков 5 и 6 контроля регистров делимого и делителя, сумматора

7 и с выходом индикации готовности к работе устройства. Выход 2 t инди5 кации ошибки устройства объединяет выходы блоков 5 и 6 контроля регистров делимого и делителя и первый выход сумматора 7. Выход 13 регистра

1 соединен с первым выходом 22 уст-1О ройства.

Второй выход 23 сумматора 7 со- единен с вторым входом регистра 1 делимого. Выход 24 окончания сложения сумматора 7 соединен с первым входом блока 3 управления.

Блок 3 управления содержит узел

25 местного программного управления, дешифратор 26 и счетчик 27. Входы

10-12 и 24 блока 3 управления и выЮ ходы 28-30 дешифратора 26 соединены с соответствующими входами узла 25 местного программного управления.

Выходные шины 15-20 и вход счетчика

27 соединены с выходной шиной узла

25 25 местного программного управления.

На графе состояний из.ображены состояния узла 25 С и признаки f

1 1) переходов из состояния С в состоя1 ние С..

Блок 5 контроля регистра делимого содержит элементы И 31 и элемент

ИЛИ 32, причем, число элементов И равно разрядности делимого минус единица. Первые входы элементов И 31 соединены с управляющим входом 17.

Выход элемента ИЛИ 32 соединен с выходной шиной 2 1.

В устройстве делимое, делитель

4 и частное могут представляться в

1 -кодах. В 1 --системе счисления

3 1151 любое натуральное число представля- ется в виде многочлена

-n ! а с! +а о +- .+а о +а + " а

5 ния, являющееся положительным действительным корнем уравнения х -х-1=0:

2 !

1 + Й

Представление (1) называется нормальной формой представления при на- !5 личии не менее одного нуля после каждой единицы.

Веса в 1; кодах имеют следующие

+ свойства: с!. = y. g и о = с1 "+g" 2 как в двоичной фибоначчиевой системе счисления.

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

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

Рассмотрим случай деления модулей

2п-разрядного !» -кода делимого и и-разрядного 1 -кода делителя, при- З5

% чем их модули (1.

Перед началом деления узел 25 местного программного управления находится в состоянии СО, в котором на выходной шине 20 блока 3 управления 40 вырабатывается управляющий сигнал

УС1 "Устройство свободно" (f „ = пуск), Для выполнения деления на входы устПр име р ° а) (А) = 010100 (А),щ = 101011 (А)о р. = 101(11

<) (А) = 100000 (A)Müù = 011111 (А)обр = 011111

11

11 00110011 010001

11

11 - 00011111- 00100111 - " 001010 где а; =- (0,1); о — основание системы счисле955 4 ройства подается следующая информация: на входы 8 и 9 — соответственно модули 1 кодов делимого и делителя, на вход 10 — признак системы счисления, в которой выполняется деление, — 1 (1 -система счисления) или 1» (двоичная- классическая система счисления), на вход 11 — сигнал "Пуск", на вход 12 — серия синхроимлульсов

10, по которой тактируется переход узла 25 из одного состояния в другое.

По сигналу "Пуск" узел 25 переходит в состояние С1 (f „ = пуск) и на управляющих шинах 15 и 16 вырабатывается сигнал УС2, по которому происходит запись 2„-разрядного модуля

1 -кода делимого в регистр 1 делимого и запись инверсного значения и-разрядного модуля 1 -кода делителя в регистр 2 делителя. Регистр делителя имеет (6 +2) разряда, причем два младших раз!ояда не являются информационными и используются только для образования обратного -кода делителя, +

При з аписи делителя они у стан авлив аются в единицу.

В состоЯнии С2 („ = 1 ) на шине

16 вырабатывается сигнал УСЗ, по которому происходит образование обратного 1 -кода. По сигналу УС2 записывается прямое значение старшего разряда модуля I -кода делителя. По сигналу УСЗ выполняется нормализация инверсного значения модуля 1 -кода делителя, причем запись единицы в старший разряд регистра 2 делителя блокируется, если в старшем разряде модуля 1 — кода делителя имеется еди* ница. По окончании процесса нормализации в регистре 2 делителя формируется обратный 1 — код делителя.

После записи делимого в регистр делимого и образования обратного

1 -кода делителя в регистре делитеФ ля на управляющие выходы f7 и 18 из блока 3 управления поступают сигналы соответственно УС4 и УС5, которые включают блоки 5 и 6 контроля делимого и делителя. Эти блоки контролируют информацию, записанную 1 -кода-М ми в регистры делимого и делителя, 55 на нормальность представления и в случае ее нарушения выдают сиганл ошибки на выход 2! Устройства.

Ф 1151

Далее выполняется сложение 1"-кода делимого и обратного 1 -кода делителя в сумматоре 7. При переходе узла 25 иэ состояния С2 в состояние

СЗ (Е = 1) на управляющие входы сумматора 7 по шине 19 поступает сигнал УС6. По этому сигналу и старших разрядов 1 -кода из регистра 1 делимого записываются в и младших разрядов (и+1)-разрядного регистра 10 остатка, а и старших разрядов обратного 1+-кода делителя записываются в и-разрядный регистр переносов.

Следующим управляющим сигналом

УС7 к счетчику 27 добавляется еди- fS ница.

При переходе в состояние CS (f = 1) из блока управления на . управлякщие входы сумматора 7 по шине 19 поступает сигнал УС8. По это- 20 му сигналу промежуточная сумма с . первого выхода полусумматора записывается в регистр остатка, а промежуточный перенос с второго выхода полусумматора записывается в регистр 25 переносов..

При сложении единиц в i-х разрядах 1+-кодов слагаемых возникает единица переноса в (i+1)-й и (i-2)-й разряды суммы, По свойству нормаль- зп ной формы 1+-кодов единицу переноса можно сразу же поместить в (i+1)-й разряд промежуточной суммы, которая записывается в регистр остатка. Все образовавшиеся переносы из i-го в (i-2)-й разряд записываются в регистр переносов. При переходе узла 25 в состояние С4 нли С8 (Е = 1, e«= 1 КСл, S„= 1 КСл) на управляющий вход сумматора 7 по ур ,шине 19 поступает сигнал УС10, по которому промежуточная сумма в регистре остатка с помощью нормализации приводится к нормальной форме.

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

+» из регистра делителя.

Процесс сложения 1 -кодов в полусумматоре контролируется блок контроля сумматора, в каждом разряде ко-у торого реализуется функция ошибки

955 где d — перенос из i-го разряда, S,. — сумма в i и разряде.

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

Ф делителя.

В старший (и+1)-й разряд регистра остатка записывается перенос из и-го разряда окончательной суммы 1 -кодов слагаемых. Значение (и+1)-го разряда регистра остатка по.шине 24 поступает в блок 3 управления. Если оно равно единице, то содержимое. и старших разрядов регистра делимого больше содержимого и старших разрядов регистра 2 делителя. Если это значение получено на первом такте деления, то узел 25 местного программного управления переходит в состояние С7, в котором вырабатывается признак некорректности деления, так как модуль частного Ъ 1.

=(РИ »g=<)(C ), =1}

Сигнал об этом поетупает на вход 20 устройства, которое переходит в нулевое состояние. В противном устройство переходит в состояние С9 (f8

=(rS9Ln+13=1)С 1), в котором по сигналу УС11, поступающему по шине

15, происходит запись содержимого и разрядов регистра остатка в старшие разряды регистра делимого. По сигналу УС7 к счетчику 27 добавляется единица. Так как по свойству нормальной формы 1+-кода частного после единицы должен бить нуль, то в состоянии С10 вырабатывается управлякиций сигнал УС12 сдвига регистра делимого на два разряда влево, причем в освободившиеся после сдвига два младших разряда регистра 1 делимого записывается код 10.

Сдвиг на два разряда влево выполняется, когда нет переполнения счетчика (s„о

Если содержимое счетчика равно (н+2), то в состоянии С10 вырабатывается сигнал УС13, по которому осуществляется сдвиг регистра 1 делимого на один разряд влево, и в исходный разряд регистра 1 делимого записывается единица. Если содержимое счетчика не равно (и+1) или (n+2) то устройство переходит в состояние

СЗ, и процесс деления продолжается: оь (С+ 4 (n+1) ч (n+2))), В противном случае процесс деления завершается и в и младших разрядах регистра 1 делимого находится модуль 1+-кода частного. (f„ = (С = (n+1) ч (n+2))).

Если значение (п+1)-ro разряда регистра остатка равно нулю, то содержимое п старших разрядов регистра 1 делимого меньше содержимого и старших разрядов регистра 2 делителя. Устройство из состояния С8 переходит в состояние Сб, (f> = PS9 1.п+1) ), в котором вырабатывается сигнал

УС13 сдвйга регистра 1 делимого на

151955 8 один разряд влево, причем в младший разряд регистра 1 делимого зано. сится нуль. Далее в з ависимо сти от содержимого счетчика устройство пе5 реходит либо в состояние СЗ (f < = (С+ Ф п+1)), либо деление завершается (й„= (С+ = и+1)) .

1» 4,= 1», ь=

1 КСл P59(n+1) (С ф1), 1" КСл. P59(n+1) (С, =1), 1+ КСл, 1 P59)n+1) КСл

4 =

Деление чисел в двоичной класси10 ческой системе счисления выполняется по известному алгоритму деления с восстановлением остатка. В этом случае в устройстве отключаются преобразователь 4 прямого кода в об-!

5 ратный, блоки 5 и 6 контроля регистров делимого и делителя, нормализатор и блок контроля сумматора 7.

Кроме этого сдвиг регистра 1 делимого в каждом такте деления выполня20 ется только на один разряд. Изменение состояний узла 25 может происхо\ дить по следующим признакам:

1151955

Ю 17 18 t9 20

Фиг.2

1151915

Составитель В. Гусев

Техред С.Йовжий

Корректор В.Синицкая

Редактор Е.Папп

Филиал ППП "Патент", г. Ужгород, ул. Проектная, Заказ 23?4/37 Тираж 710 Подписное

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

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