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

 

1. УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ ЧИСЕЛ, содержащее два накапливающих сумматора, элемент И, генератор импульсов и блок фор шрования ; сигналов управления, приче 4 входы установки в исходное состояние накапливгиощих сумматоров подключены к первому выходу блока формирования сигналов управления, тактирующие входы накапливаюсцих сумматоров подключены к выходу элемента И, первый вход которого соединен с выходом генератора импульсов, второй вход - с вторым выходсм блока формирования сигналов управлё1ния, .а третий вход - с выходом старшего . . pJlЗpяДa первого накапливакксаёго cyw-1 мотора, выходы второго накапЗШйайще :го сумматора подключены к выходам устройств 1, отличающееся тем, что, с пойьпиения быстрот действия, в него введены три регистра сдвига, группа элементов и, группа формирователей импульсов и эле .мент ИЛИ при этом входы старших разрядов первого регистра соединены с входами двоичнаго кода делителя устройства,входы старших разрядов двоичного кода делителя устройства входы старши разрядов второго регистра соединены с входами двоичного кода делимого устройства, младших разрядов первого и второго pei CTpoB .соединешл с шириной логического нуля ус тройства,вход старшего разряда третьего регистра соединен с шиной логической единицы устройства, а выходы остальных разрядов третьего регистра соединены с шиной логического нуля устройства, выходы разрядов Первого и второго регистров соедин&ка с соответствующими группами информационных входов первого и второго накапливающих сумматоров со-, ответственно, выходы разрядов третьего регистра подключены к первым входам элементов И группы, входа которах соединены соответственно с выходами старших разрядов первого накапливающего сумматора, . выходы элементов И группы соедийены со входами соответствующих формирователей импульсов группы, выходы которых подкдтченБ ко входгм элемента ИЛИ, выход которого соединен с. входами срвига первого, вто00 со . рого и третьего регистров, входы записи KOTOptxx соединены с третьим выходом блока формирования сигна4ib лов управления, вход которого со00 единен с входом пуска устройства. 2. Устройство по п. 1, 6 т л и.чаю щ с я тем, что блок формирования сигналов управления содержит регистр сдвига, четыре элемента И, генератор импульсов и триТгер, при этом выходы регистра сдвига подключены к первым входам первого, второго и третьего элементов и.соответственно, вторые входы которых соединены с тактирующим входом регистра сдвига и выходом четвертого элемента И, первый вход которого соединен с вы

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

СС И4ИПИ:

РЕСПУБЛИК (5В С 06 Р 7, 52

ПО,ЦЕЛАМ ИЗОБРЕТЕНИЙ И (ЛНРЫТИЙ

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

К ASTOPCHohAf СВЩфЕТЕЛЬСТВУ

k .1"> -.".- яв -;.

1 ОСУДАРСТВЕННЫЙ КОМИТЕТ СССР (2i) 3366547/18-24 (22) 16.12.81 (46) 23.04.83. Вюл. В 15 (72) Е.И. филатов (71) Новосибирский электротехнический институт (531 681.325(088.8) .(56) 1. Влаговещенский Ю.В., Теслер Г.С. Вычисление элементарных функций на ЭВМ. Киев, "Техника", 1977. 2. Авторское свидетельство СССР

В 331386, кл. G 06 F 7/52, 1972.

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

В 602994, кл. G 06 F 7/52, 1978.

4. Измерительные информационные системы. Под ред. М.П. Цапенко, .НовОсибирск, НГУ-НЭТИ, 1977, с.133150 (прототип). (54)(57) 1. устРойстВО для дЕЛЕНИя

ЧИСЕЛ, содержащее два накапливающих сумматора, элемент И, генератор импульсов и блок формирования сигналов управления, причем входы установки в исходное состояние накапливающих сумматоров подключены к первому выходу блока формирования сигналов управления, тактирующие входы накапливающих сумматоров подключены к выходу элемента

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

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

gl ,SU„„948 А.устрбйства,входы старших разрядов двоичного кода делителя устройства, входы старших разрядов второго регистра соединейы с входами двоичного кода делимого устройства, входы младшйх разрядов первого и второго регистров, соединены с шириной логического нуля устройства, вход старшего разряда третьего регистра соединен с шиной логичес.кой единицы устройства, а выходы остальных разрядов третьего регистра соединены с шиной логического нуля устройства, выходы разрядов первого и второго регистров соединены с соответствующими группами информационных входов первого и вто-. рого накапливающих сумматоров со-. ответственно, выходы разрядов Tðåчьего регистра подключены к первым входам элементов И группы, вторые входы которых соединены соответственно с выходами старших разрядов первого накапливающего сумматора, . Я выходы элементов И группы соедийе.ны со входами соответствующих формирователей импульсов группы, выходы которых подключены ко входам элемента ИЛИ, выход которого соединен с. входами сдвига первого, второго и третьего регистров, входы записи которых соединены с третьим выходом блока формирования сигна-. лов управления,. вход которого соединен .с входом пуска устройства.

2. Устройство по п. 1, о т л и.— ч а ю щ е е с я тем, что блок формирования сигналов управления содержит регистр сдвига, четыре элемента И,.генератор импульсов и . триггер, при этом выходы регистра сдвига подключены к первым входам первого, второго и третьего элементов Й соответственно, вторые входы которых соединены с тактирующим входом регистра сдвига и выходом четвертого элемента И, первый вход которого соединен с вы1013948

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

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

Известны устройства для.деления чисел, реализующие подбор текущего значения частного; использующие различного вида пересчетные схемы; использующие различного вида итерационные алгоритмы. Текущие приближения частного в последних образуются с помощью решения на каждой итерации определенных рекур15 рентных соотношений (1 J.

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

Известны специализированные делительные устройства 2 g u t 3j. 20

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

Вариантом построения итерацион- 5 ной процедуры вычислений является так называемая "гарвардская" итерация, когда делитель и делимое умножаются на одинаковые последовательности чисел пока делитель с 30 требуемой точностью не станет .равным единице. Данный алгоритм универсален и может применяться при любых соотношениях делимого и делителя. Частным случаем построения

"гарвардской" итерации при У<< 1 яв- . ляется использование в качестве множителя для числителя и знаменателя некоторой конечной сумМы чисел натурального ряда, а именно:

4с

1: — =1,э,э (1 Е::

Операции умножения чисел замеменяются при этом накапливающим суммированием, а вычисление прекра- щается при таком Е;, когда выпол+3 50 няются соотношения y j =1 = 1

i=1 тановки в едийичное состояние триггера соединен с входом пуска устройства, выходы первого, второго и .третьего элементов И являются первым, третьим и вторым выхо дами блока соответственнО.

3 или ) ; . Здесь Г.3- ближайЬ1 шее меньшее или равное, а ближайшее большее или равное целое число. Если у ) 1 или лишь немногим меньше единицы, то числитель и знаменатель предварительно умйожаются на некоторый множитель

М = à (h = ),2,3,...), зависящий от требуемой точности вычислений.

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

1 информационным входам первого и втоIporo накапливающих сумматоров со ответственно, входы установки в исходное состояние счетчиков и накапливающих сумматоров подсоединены к первому выходу блока формирования сигналов управления, счет- . ные входы первого и второго счетчиков подсоединены к выходам второго и первого элементов И соответственно, первые входы которых подсоединены ко второму выходу блока формирбвания сигналов управления, второй вход первого элемента И соединен qo входом подачи импульс) ного кода делимого, второй вход .второго элемента,И соединен со входом подачи, числоимйульсного кода делителя, тактирующие входы сумми-. рования накапливающих сумматоров соединены с выходом третьего элемента И, первый вход которого соединен с выходом генератора импульсов, второй вход . — с третьим выходом блока формирования сигналов управления, а третий вход— с инверсным выходом старшего разряда первого накапливающего сумматора, выходы второго накапливающего сумматора подсоединены к выходам устройства (4 ).

1013948

10

Данное устройство выполняет операцию деления — двух целых чиX

М

I .сел, которые могут изменяться в диапазоне 1 < х < Z —.1; 1< у < 2 — 1.

В начале работы устройство сигналов

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

,делителя записываются во второй и первый счетчики соответственно. По окончании счета сигналом "Разрешение деления" открывается третий элемент И. Импульсы генератора начинают поступать в качестве тактовых импульсов суммирования на накапливающие сумматоры. Значения делимого и делителя суммируются во втором и первом сумматорах до тех пор, пока в (h+1) разряде первого сумматора, соответствующем младшему разряду целой части, не появится единица. Третий элемент И закрывается. Общее число импульсов Ф, прошедших на сумматоры, будет равно

) (, а код, сформированный во втором сумматоре, с учетом положения запятой, будет равен 21Г - х

xk-2 = x) — (2 (2)

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

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

В наихудшем случае при у у,.„= 1; k = k

Максимальное время вычисления составляет таким образом: выч mdx Фп п fhax Е

<Т ° 1< = t 2

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

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

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

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

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

Блок формирования сигналов управления содержит регистр сдвига, четыре элемента И, генератор импульсов

45 и триггер,при этом выходы регистра сдвига подключены к первым входам первого, второго и третьего элементов И соответственно, вторые входы которых соединены с тактирующим входом регистра сдвиra и выходом четвертого элемента И, первый вход которого соединен с выходом генератора импульсов, а второй вход — с выходом триггера, счетный вход которого со55 единен с выходом старшего разряда регистра сдвига и с входом записи первого разряда регистра сдвига, вход ;" ""ановки в единичное состояние триггера соединен со входом пуска устройства, выходы первого, вто60 . рого и третьего элементов И являются первым, третьим и вторым выходами блока соответственно.

На фиг. 1 изображена функциональ-, ная схема устройства для деления чисел; на фиг. 2 — функциональная

1013948

Устройство содержит накапливающие сумматоры 1 и 2, имеющие соответственно (h+1) и (Л+ ) разрядов, 5 регистры 3-5 сдвига, имеющие (h-1), (h+n-m- 1) и (h-m-1) разрядов соответственно, группу 6 элементов И, группу 7 ждущих формирователей импульсов, элемент ИЛИ 8, элемент И 9, 10 генератор 10 импульсов, блок 11 формирования сигналов управления, входы 12 подачи кода делителя, входы

13 подачи кода делимого, шину 14 логического нуля, шину 15 логической единицы, выход 16. При этом входы установки в исходное состояние сумматоров 1 и 2 подсоединены к первому выходу 17 сигнала "Сброс" блока 11 формирования сигналов управления, а тактирующие входы суммирования — к выходу элемента И 9, первый вход которого соединен с выходом генератора 10 импульсов, второй вход — со вторым выходом 18 сигнала "Разрешение деления" блока 11 25 формирования сигналов управления, а третий вход — с инверсным выходом старшего разряда сумматора 1.

Группы информационных входов сумматора 1 соединены с соответствую- З0 .шими выходами регистра 3, входы записи m старших разрядов которого подсоединены ко входам 12 подачи кода делителя. Группы информационных входов сумматора 2 соединены с соответствующими выходами регистра 4, входы записи и старших разрядов которого подсоединены ко входам 13 подачи кода делимого. Входы записи мпадших (h-m-1) разрядов регистров 3 и 4 подсоединены к шине 14 логического 40 нуля. Вход записи старшего разряда регистра 5 соединен с шиной 15 логической единицы, а входы записи остальных разрядов — с шиной 14 логического йуля. Выходы регистра 5 под- 45 соединены к первым входам элементов

И группы б, вторые входы которых подсоединены соответственно к выходам. разрядов сумматора 1, имеющим номера с (m+1) по h. Выходы элементов И группы б соединены со входами ждущих формирователей импульсов группы

7, выходы которых подсоединены ко входам элемента ИЛИ 8. Тактирующие входы регистров 3-5 соединены с выходом элемента ИЛИ 8, а тактирующие входы записи — с третьим выходом 19 сигнала "Запись" блока 11 формирования сигналов управления. Выходы накапливающего сумматора 2 подсоединены к выходам 16 устройства. Ко вхо- . 60 ду блока 11 формирования сигналов управления подсоединен вход 20 пуска устройства.

Блок формирования сигналов управления содержит кольцевой трехраз 6у

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

И 22-25, генератор 26 импульсов, триггер 27, вход 20 пуска, первый выход 17 сигнала "Сброс", второй выход сигнала "Запись", третий выход

18 сигнала "Разрешение деления".

При этом выходы регистра сдвига подсоединены соответственно к первым входам элементов И 22-24. Вторые входы данных элементов И соединены с тактирующим входом сдвига регистра и выходом элемента И 25, первый вход которого соединен с выходом генератора 26 импульсов, а второй -с выходом триггера 27. Вход установки в единичное состояние триггера 27 соединен со входом 20 пуска, а счетный вход — с выходом старшего разряда и входом записи первого разряда регистра 21 сдвига.

Выходы элементов И 22, 23, 24 являются выходами 17, 19, 18 устройства 11 формирования импульсов управления соответственно.

Устройство для деления чисел ра с ботает следующИМ образом.

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

Затем сигналом "Запись" в старшие rn и и разрядов регистров 3 и 4 соответственно заносятся коды делителя и делимого, а в старший разряд регистра

5 заносится логическая единица. В остальные разряды регистров 3-5 заносятся логические нули. По сигналу

"Разрешение деления" элемент И 9 открывается и импульсы генератора.

10 начинают поступать на тактирующие входы суммирования накапливающих сумматоров 1 и 2. Как только в старшем разряде дробной части сумматора 1, имеющем номер, равный Ь,,сформируется единица, откроется первый элемент И группы б. Сформированный по этому перепаду первым из группы 7 ждущим формирователем короткий импульс, пройдя через элемент ИЛИ 8, своим задним фрбнтом сдвинет содержимое регистров 3-5 на один разряд в сторону младших разрядов. Если.и в последующих в порядке убывания разрядах сумматора 1 имеются в данный момент единичные значения, то поочередно будут открываться второй, третий и т.д. элементы И группы 6, а содержимое регистров

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

1013948 ству разряда, имеющего нулевое значение. Как только дробная часть сум-, матора 1 полностью заполнится, т.е. появится единица в (h+1) разряде, элемент И 9 закроется и поступление тактирующих импульсов суммирования прекратится. В сумматоре, 2 будет сформирован код результата деления х — Абсолютная погрешность вычислений

У х — д < —; относительная -д"< —, а

-ъ приведенная — д" р < 2

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

27 установлен н нулевое состояние.

При поступлении на вход 20 сигнала пуска триггер 27 устанавливается в единичное состояние и открывается элемент И 25. Импульсы генератора 26 начинают поступать на тактирующий нход сдвига регистра 21 и вторые входы элементов H .22-24. Но заднему фронту каждого очередного импульса

"Единица" в регистре сдвига переме-. щается н сторону старших разрядов, поочередно открывая элементы И 22;23, 24, на выходах 17, 19, 18 которых формируЫтся три задержанных относительно друг друга импульса "Сброс", "Запись" и "Разрешение деления".

Задним фронтом третьего импульса генератора 26 "Единица" вновь заносится в первый разряд региетра 21, а триггер 27 возвращается н нулевое состояние.

Ю

Большинство применяемых в настоя.щее время устройств деления устанавливаемых в универсальных ЦВМ, используют представление текущего значения частного в виде последовательно формируемых убывающих двоичнокодированных приращений. B данном устройстве 45 используются единичнЫе приращения частного, что упрощает его аппаратур-. ную реализацию. От других устройств с аналогичной формой промежуточного представления частного данное устрой- 50 ство отличается очень широким диапазоном возможных значений операндов, получением результата деления с любой заданной точностью, простотой структуры и логики работы, благодаря чему при практической реализации оно может быть построено с использованием небольшого набора функциональных узлов.

Так как накапливающее суммирование в сумматорах 1 и 2 осуществляется с переменным двоичным весом, число тактов суммирования в данном устройстве существенно меньше, чем в известном.

Максимальное число тактов, имеющее место при у = у . = 1, для данного устройства равно тиса Х (4) а сокращение максимального числа тактов в сравнении с известным устройством составляет р wax

k 2 2

1 „„= 2 (Ь в+Т) = Ь.-и+Т-.

В частности при m = 16, h = 32,,Р = 3855, при m -=-16,,h = 64, Э

P = 1,3 10 . Правда, следует учитывать, что период вспомогательной импульсной последовательности генератора 10 для данного устройства необходимо брать несколько большим, чем для известного. Это объясняется тем, что данный период должен превышать максимально возможное время переходных процессов, которое имеет место при у = у „, т.е. когда все разряды делителя имеют единичное значение и необходим сдвиг сразу на m разрядов.

Если обозначить через .1 - — максимальное время переходных процессон в сумматорах 1 и 2; t0 — минимальная длительность выходнйх импульсов формирователей, обеспечивающая надежное срабатывание регистров сдвига; -й„„ максимальная продолжительность тЖ.та сдвига, то период следования импульсной последовательности генератора 10 должен удовлетворять соотношению

mi (9 сдв) )

В частности, при реализации сравниваемых устройств на микросхемах серии К155 можно принять to = и

-50 нс, t 100 нс. В этом случае

Т„„,.„ (m+T)t, а максимальное время вйчйсления данного устройства будет равно ваныч 6 Твi п 1тах (m+1) + 2 (h-и+1)

Результирующий выигрыш н быстродействии предлагаемого устройства в сравнении с известным может быть оценен соотношением выч тм" 1 ныч тпс к

Ъ-ю

-й+ й+

Как следует из соотношения, применение предлагаемого устройства тем предпочтительнее, чем выше требования к точности и динамическим диапазонам операндов. Например, для рассматриваемого примера при m = 16, h = 32 выигрыш Я составляет 227 паз, а при

m = 16, h = 64 g 7 6 10 раэ. хохае а

1013948

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

Редактор Н. Егорова ТехредИ.Коштура, Корректор E. Рошко

Заказ 3018/57 Тираж 704 Подписное

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

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

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