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

со тветствеино информ пшотшыми входами блоков контроля делимого и делителя и с первым и вторым информационными входами сумматора, второй выход которого соединен с информацион ным входом регистра делимого, выход преобразователя прямого кода в обратньй с информационным входом регистра делителя, второй вход блока упранления ян.пястс.я I.X.O;IOM щяшнака систрм(.1 счнс.лепия ус.трсми тиа, третий вход блока управления янляется пусковым входом устройства, четвертой вход блока управления является синхрОБХОдом устройства, а выход регистра делимого является выходом результата устройст ва.

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

1

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

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

На фиг.. 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 прямого кода в обратный, блоков 5 и 6 контроля регистров делимого и делителя, сумматора 7 и с выходом индикации готовности к работе устройства. Выход 21 индикации ошибки устройства объединяет выходы блоков 5 и 6 контроля регистров делимого и делителя и первый выход сумматора 7. Выход 13 регистра 1 соединен с первым выходом 22 уст-ройства.

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

входом блока 3 управления.

Блок 3 управления содержит узел 25 местного программного управления, дешифратор 26 и счетчик 27. Входы 10-12 и 24 блока 3 управления и выходы 28-30 дешифратора 26 соединены с соответствующими входами узла 25 местного программного управления. Выходные шины 15-20 и вход счетчика 27 соединены с выходной шиной узла

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

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

Блок 5 контроля регистра делимого содержит элементы И 31 и элемент ИЛИ 32, причем, число элементов И равно разрядности делимого минус единица. Первью входы элементов И 31 соединены с управляюпум входом 17. Выход элемента ИЛИ 32 соединен с выходной шиной 21.

В устройстве делимое, делитель ... и частное мохут представляться в

4ъ

1 -кодах. В 1 -системе счисления 31 любое натуральное число представляется в виде многочлена N.....«,V..,-...t«./,( где а,- {0,1 у, (L - основание, системы счисления, являющееся положитель ным действительным корнем уравнения х 1 + V5 Представление (1) называется нормальной формой представления при на личин не менее одного нуля после каждой единицы. Веса в 1;«скодах имеют следующие |йства: flt oi. и + как свойства: в двоичной фибоначчиевой системе счисления. Операции нормализации, сложения, вьиитания, кодирования отрицательных чисел и основные контрольные соотношения для 1 -кодов аналогичны таким же операциям для 1 -кодов Фибоначчи, Операции умножения и деления чисел в 1 -кодах аналогичны этим операциям в двоичной классической системе счисления. Устройство работает следующим образом. Рассмотрим случай деления модулей 2п-разрядного 1 -кода делимого и П-разрядного 1 -кода делителя, причем их модули 1. Перед началом деления узел 25 мест ного программного управления находится в состоянии СО, в котором на выходной шине 20 блока 3 управления вырабатывается управляющий сигнал УС1 Устройство свободно ( пуск) Для выполнения деления на входы устП р и м е р. а) (А) 010100 (А)и„в 1010 (А) lOlp к) (А) 100000 (A)v,Ke 0111 (А)о5р 0111

После записи делимого в регистр делимого и образования обратного 1 -кода делителя в регистре делителя на управляющие выходы Т7 и 18 из блока 3 управления поступают сигналы соответственно УС4 и УС5, которые включают блоки 5 и 6 контроля делимого и делителя. Эти блоки контролируют информацию, записанную 1 -кодами в регистры делимого и делителя, на нормальность представления и в случае ее нарушения выдают сиганл ошибки на выход 21 устройства. 554 ройства подается следующая информация: на входы 8 и 9 - соответственно модули 1 кодов делимого и делителя, на вход 10 - признак системы счисления, в которой выполняется деление, -И (1 -система счисления) или 1 (двоичная- классическая система счисления) , на вход 11 - сигнал Пуск, на вход 12 - серия синхроимпульсов 10, по которой тактируется переход узла 25 из одного состояния в другое. По сигналу Пуск узел 25 переходит в состояние С1 (fo пуск) и на управляющих шинах 15 и 16 вырабатывается сигнал УС2, по которому происходит запись 2 -разрядного модуля 1 -кода делимого в регистр 1 делимого и запись инверсного значения л-разрядного модуля 1 -кода делителя в регистр 2 делителя. Регистр делителя (п+2) разряда, причем два младших не являются информационными и используются только для образования обратного 1 -кода делителя. При записи делителя они устанавливаются в единицу. В состоянии С2 (fii 1) на шине 16 вырабатывается сигнал УСЗ, по ко торому происходит образование обратного 1 -кода. По сигналу УС2 записывается прямое значение старшего разряда модуля 1 -кода делителя. По сигналу УСЗ выполняется нормализация инверсного значения модуля 1 -кода делителя, причем запись единицы в старший разряд регистра 2 делителя блокируется, если в старшем разряде модуля 1 -кода делителя имеется единица. По окончании процесса нормализации в регистре 2 делителя формируется обратный код дели,те.пя. - 00110011- 010001. - 00011111- 00100111- 001010

5

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

Следующим управляющим сигнешом УС к счетчику 27 добавляется единица.

При переходе в состояние С5 ( блока управления на , управляющие входы сумматора 7 по шине 19 поступает сигнал УС8. По этому сигналу промежуточная С5гмма с первого выхода полусумматора записывается в регистр остатка, а промежуточный перенос с второго выхода полусумматора записьшается в регистр переносов. .

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

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

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

,--.,.

9556

где dj - перенос из i-ro разряда , S. - сумма в i-M разряде.

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

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

(,, (), ,;-.1).

Сигнал об этом поступает на вход 20 устройства, которое переходит в нулевое состояние. В противном устройство переходит в состояние С9 (fgj (P59tn+l3 1)C4.) , в котором по сигналу УС11, поступакяцему по шине 15, происходит запись содержимого п разрядов регистра остатка в старшие разряды регистра делимого. По сигналу УС7 к счетчику 27 добавляется единица. Так как по свойству

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

1).

(f.

510 Если содержимое счетчика равно (п+2), то в состоянии СЮ вырабатывается сигнал УС13, по которому осу ществляется сдвиг регистра 1 делимо го на один раз.ряд влево, и в исходный разряд регистра 1 делимого запи сывается единица. Если содержимое счетчика не равно (п-ь1) или (п+2)/ то устройство переходит в состояние СЗ, и процесс деления продолжается: (f,« (С4 (n+1)v(n+2))). В противном случае процесс деления завершается и в п младших разрядах регистра 1 делимого находится модуль 1 -кода частного. (С (n-t-l)v (п+2))). Если значение (п+1)-го разряда регистра остатка равно нулю, то со держимое п старших разрядов регист ра 1 делимого меньше содержимого п старших разрядов регистра 2 дели теля. Устройство из состояния С8 переходит в состояние С6, (f PS9 U+O), в котором вырабатывается сигнал УС13 сдвига регистра 1 делимого на

в 9

2

Фиг, один разряд влево, причем в младший разряд регистра 1 делимого заносится нуль. Далее в зависимости от содержимого счетчика устройство перекодит либо в состояние СЗ (ft3 (С. п+1)), либо деление завершается (f,o (С, п+О). Деление чисел в двоичной классической системе счисления выполняется по известному алгоритму деления с восстановлением остатка. В этом случае в устройстве отключаются преобразователь 4 прямого кода в обратный, блоки 5 и 6 контроля регистров делимого и делителя, нормализатор и блок контроля сумматора 7. Кроме этого сдвиг регистра 1 делимого в каждом такте деления выполняется только на один разряд. Изменение состояний узла 25 может происходить по следующим признакам: Ц- j5 . f5i . (), 1 КСл-Р59 п+11.(). „ 1 КСл, f JJ 1 КСл

25

U

т Y Ф Ф Ф ф

/5 J6 17 n /5 20

, T,

rtn T Фиг.2.

I г I

z/