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

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

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

Изобретение относится к цифров вычислительной технике и может бы использовано в вычислительных и информационно-гизмерительных .устро ствах и системах для выполнения о рации деления чисел. Известны устройства для. делени чисел, реализующие подбор текущег значения частного; использующие различного вида пересчетные схемы использующие различного вида итерационные алгоритмы. Текущие приближения частного в последних образуются с помощью решения на кс1Ж дой итерации определенных рекуррентных соотношений Cl3Однако из-за большой сложности ин терационных алгоритмов они реализую преимущественно программным путем Известны специализированные делительные устройства С2 1 и ЗЗ. Однако для них необходим многотактный режим работы, требующий сложной лоХики управления и больши аппаратурных затрат. Вариантом построения итерационной процедуры вычислений является так называемая гарвардская итерация, когда делитель и делимое умножаются на одинаковые последова тельности чисел пока делитель с требуемой точностью не станет равным единице. Данный алгоритм универсален и может применяться при любых соотношениях делимого и дели теля, Частным случаем построения гарвардской итерации при Y« 1 является использование в качестве мн жителя для числителя и знаменателя некоторой конечной суммы чисел натурального ряда, а именно: X Ci . , 1 1,2,3 (1) Операции умножения чисел замеменяются при этом, накапливающим суммированием, а вычисление прекра щается при таком kj ,.. когда выполняются соотношения N .. . Здесь М- ближайшее меньшее или равно.е, а j-f ближайшее большее или равное целое число. Если у 1 или лишь немногим меньше единицы, то числитель и знаменатель предварительно умножаются на некоторый множитель М (h 3,2,3,...) зависящий от требуемой точности вычислений. Наиболее близким к предлагаемому является устройство для деления чисел, которое содержи.т два накапливающих сумматора, имеющих (h+1) и (h+n) разрядов соответственно, два счетчика делителя и делимого, имеющих тип разрядов соответственно, три элемента И, генератор импульсов и блок формирования сигналов управления, этом выходы разрядов первого и второго . ков подсоединены к соответствукяцим информационным входам первого и вто Iporo накапливающих сумматоров соответственно, входы уста:новки в исходное состояние счетчиков и накапливающих сумматоров подсоединены к первому выходу блока формирования сигналов управления, счет- . ные входы первого и второго сче: чиков подсоединены к выходам второго и первого элементов И соответственно, первые входы которых подсоединены ко второму выходу -блока формирования сигналов управления, второй вход первого элемента И соединен со входом подачи импульсного кода делимого, втгорой вход .второго элемента,И соединен со входом подачи числоимпульсного кода делителя, тактирующие входы сумми-., рования накапливающих сумматоров соединены с выходом третьего элемента И, первый вход которого соединен с выходом генератора импульсов , второй вход .- с третьим выходом блока формирования сигналов управления, а третий вход с инверсным выходом старшего разряда первого накапливающего сумматора, выходы второго накапливающего сумматора подсоединены к выходам устройства С ЗДанное устройство выполняет операцию деления - двух целых чи,сел, которые могут изменяться в диапазоне ,1; В начале работы устройство сигнгСлов Сброс устанавливается в исходное состояние. Затем-сигналом Запись открываются первый и второй элемент ,И и числоимпульсные коды делимого и делителя записываются во второй и первый счетчики соответственно. По окончании счета сигналом Разрешени деления открывается третий элемент И. Импульсы генератора начинайт поступать в качестве тактовых импульсов суммирования на накапливающие сумматоры. Значения делимого и делителя суммируются во втором и первом сумматорах до тех пор, пока в (h+1) разряде первого сумматора, соответствующем младшему разряду целой части, непоявится единица. Третий элемент И закрывается. Общее число импульсов 1с, прошедагих на сумматоры, будет равно , а код, сформированный во вто ром сумматоре, с учетом положения запятой, будет равен .Ьг --h V V Ic - К ii - Как видно, алгоритм работы этого (1 )c предварительным умножением де лимого и делителя на 2 и их накап .ливающим суммированием до тех пор, ,пока делитель не достигнет значения ; единицы.. . Недостатком устройства является сравнительно невысокое быстродействие, определяемое в первую очередь числом тактов сумз шрования k, которое зависит от диапазона значений делимого у и требуемой погрешности вычислений. В наихудшем случае пру у 1 ; k k Период следования импульсов генератора дол жен превышать максимально возможное время переходных процессов в накапливающих сумматорах tj-, т.е. Максимальное время вычисления соста ляет таким образом: max Л t Т ВЫЧ tridX Целью изобретения является повышение быстродействия устройства. Поставленная цель .достигается тем, что в устройство для деления чисел, содержащее два накапливающих сумматора, элемент И, генератор импульсов и блок формирования сигнало управления, причем входа установки в исходное состояние нака.пливающих сумматоров подключены к первому выходу блока формирования сигналов уп равления, тактирующие входы накапли вающих сумматоров подключены к выхо элемента И, первый вход которого со единен с выходом генератора импульсов, второй вход - со вторым выходом блока формирования сигнала управления, а третий вход - с выходом старшего разряда первого накапливающего сумматора, выходы второго накапливающего сумматора подключены к выходам устройства, введены три регистра сдвига, группа элементов И, группа формирователей импульсов и элемент ИЛИ, при этом входы старших разрядов первого регистра соединены со входами двоичного кода делителя устройства, входы старших разрядов второго рогистра соединены со входами двоичного кода делимого устройства, входы младших разрядов первого и второго регистров соединены с шиной логического нуля устройства, вход старшего разряда третьего регистра соединен с шиной логической единицы устройства, а входы остальных разрядов третьего регистра соединены с шиной логического нуля устройства, выходы разрядов первого и второго регистров соединены с соответствующими группами информационных входов .первого и второго накапливающих сумматоров соответственно, выходы разрядов третьего регистра подключены к первым входам элементов И группы, вторые входы которых соединены соответственно с выходами старших разрядов первого накапливающего сумматора, выходы элементов И группы соединены со входами соответствующих формирователей импульсов группы, выходы которых подключены ко входам элемента ИЛИ, выход которого-соединен с входами сдвига первого, второго и третьего регистров, входы записи которых соединены с третьим выходом блока формирования сигналов управления, вход которого соединён с входом пуска устройства. Блок формирования сигналов управления содержит регистр сдвига, четыре элемента И, генератор импульсов и триггер, при этом выходы регистра сдвига подключены к первым входам первого, второго и третьего элементов И соответственно, вторые входы которых соединены с тактирующим входом регистра сдвига и выходом четвертого элемента И, первый вход которого соединен с выходом генератора импульсов, а второй вход - с выходом триггера, счетный вход которого соединен с выходом старшего разряда регистра сдвига и с входом записи первого разряда регистра сдвига, вход установки в единичное состояние триггера соединен со входом пуска устройства, выходы первого, второго и третьего элементов И являются первым, третьим и вторым выходами блока соответственно. 1а фиг. 1 изображена функциональ-, ная схема устройства для деления чисел; на фиг. 2 - функциональная

схема блока формирования сигналов управления.

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

первый входкоторого соединен с выходом генератора 10 импульсов, второй .вход - со вторым выходом 18 сигнала Разрешение деления блок.а 11 формирования сигналов управления, а третий вход - с инверсным выходом старшего разряда сумматора 1.

Группы информационных входов сум-i матора 1 соединены с соответствующими выходами регистра 3, входы записи m старших разрядов которого подсоединены ко входам 12 подачи кода делителя. Группы информационных входов сумматора 2 соединены с соответствующими выходами регистра 4, входы записи п старших разрядов которого подсоединены ко входам 13 подачи кода делимого. Входы записи младших (h-m-1) разрядов регистров 3 и 4 подсоединены к шине 14 логического нуля. Вход записи старшего разряда регистра 5 соединен с шиной 15 логической единицы, а входы записи остальных разрядов - с шиной 14 логического нуля. Выходы регистра 5 подсоединейы к первым входам элементов И группы б, вторые входы которых подсоединены соответственно к выходам, разрядов сумматора 1, имеющим номера с (т+1) по h. Выходы элементов И группы 6 соединены со входами ждущих формирователей импульсов группы 7, выходы которых подсоединены ко входам эле.мента ИЛИ 8, Тактирующие

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

управления подсоединен вход 20 пуска устройства.

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

рядный регистр 21 сдвига, элементы И 22-25, генератор 26 импульсов, триггер 27, вход 20 пуска, первый выход 17 сигнала Сброс, второй выход сигнала Запись, третий выход 5 18 сигнала Разрешение деления.

При этом выходы регистра сдвига подсоединены соответственно к первым входам элементов И 22-24. Вторые входы данных элементов И соединены

Q С Тактирующим входом сдвига регистра и выходом элемента И 25, первый . вход которого соединен с выходом генератора 26 импульсов, а второй -с выходом триггера 27. Вход установки

f В единичное состояние триггера 27 соединен со входом 20 пуска, а счетный вход - с выходом старшего разряда и входом записи первого разряда регистра 21 сдвига.

Выходы элементов И 22, 23, 24

0 являются выходами 17, 19, 18 устройства 11 формирования импульсов управления соответственно.

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

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

0 и п разрядов регистров 3 и 4 соответственно заносятся коды делителя и делимого, а в старший разряд регистра 5 заносится логическая единица. В остальные разряды регистров 3-5 заносятся логические нули. По сигналу Разрешение деления элемент И 9 открывается и импульсы генератора, 10.начинают поступать на тактирующие входы суммирования накапливающих сумматоров 1 и 2. Как только в старшем разряде дробной части сумматора 1, имеющем номер, равный ft, сформируется единица, откроется первый элемент И группы 6. Сформированный по этому перепаду первым

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

е группы 6, а содержимое регистров

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

Таким образом, на сумматор 1 всегда подаются коды, лиши на один разряд сдвинутые в сторону младших j относительно ближайшего по старшинству разряда, имеющего нулевое значение. Как только дробная часть сумматора 1 полностью заполнится, т,е, появится единица в (h+1) разряде, элемент И 9 закроется и поступление тактирующих импульсов суммирования прекратится. В сумматоре. 2 будет сформирован код результата деления -. Абсолютная погрешность вычислений - 4 4 -г относительная -сГ, а 2 приведенная - . В блоке 11 формирования сигналов управления в исходном положении второй и третий разряды регистра 21 сдвига установлены в нулевое, а первый - в единичное состояние, триггер 27 установлен в нулевое состояние. При поступлении на вход 20 сигнала пуска триггер 27 устанавливается в единичное состояние и открыва ется элемент И 25. Импульсы генератора 26 начинают поступать на тактирующий вход сдвига регистра 21 и вторые входы элементов И 22-24. По заднему фронту каждого очередного импульса Единица в регистре сдвига перемещается в сторону старших разрядов, поочередно открывая элементы И 24, на выходах 17, 19, 18 которых формиру{отся три задержанных относительно друг друга импульса Сброс, Запись и. Разрешение деления. Задним фронтом третьего импульса генератора 26 Единица вновь заноситс в первый разряд регистра 21, а 27 возвращается в нулевое состояние. Большинство применяемых в настоя,щее время устройств деления устанавливаемых в универсальных ЦВМ, исподь зуют представление текущего значения частного в виде последовательно формируемых убывающих двоичнокодированных приращений. В данном устройстве используются единичные приращения частного, что упрощает его аппаратур ную реализацию. От других устройств с аналогичной формой промежуточного представления частного данное устрой ство отличается очень широким диапазоном возможных значений операндов, получением результата деления с любой заданной точностью, простотой структуры и логики работы, благодаря чему при практической реализации оно может быть построено с использованием небольшого набора функциональных узлой.. Так как накапливающее суммировани в сумматорах 1 и 2 осуществляется с переменным двоичным весом, число так тов суммирования в данном устройстве существенно меньше, чем в известном Максимальное число тактов, имеющее место при у у. 1, для данного устройства равно lmcix 2 Ch-m+1),(4) а сокращение максимального числа тактов в сравнении с известным устройством составляет Z th-m+l) h-m+T глал В частности при m 16, h 32, Р 3855, при m 16, h 64, Р 1,3-10 . Правда, следует учитывать, что период вспомогательной импульсной последовательности генератора 10 для данного устройства необходимо брать несколько большим, чем для известного. Это объясняется тем, что данный период должеи превышать максимально возможное время переходных процессов, которое имеет место при у У,,з,,, т.е. когда все разряды делителя имеют единичное значение и необходим сдвиг сразу на m разрядов. Если обозначить через -t j- - максимальное время переходных процессов в сумматорах 1 и 2; to - минимальная длительность выходных импульсов формирователей, обеспечивающая надежное срабатывание регистров сдвига; :ti,. максимальная продолжительность Tat та сдвига, то период .следования импульсной последовательности генератора 10 должен удовлетворять соотношениюf Члв В частности, при реализации сравниваемых устройств на микросхемах серии К155 можно принять t 50 НС, НС. В этом случае Inin (Utj; 3 максимальное время вычисления данного устройства будет .равно , . . 4b.,l„д (in)tj.v2() Результирующий выигрыш в быстродействии предлагаемого устройства в сравнении с известным может быть оценен соотношением ЫЧ гпдк tj-(m+1) 2(h-m+1) выч mcijt ti-rtt (h-m-t-1)(m+n Как следует из соотношения, применение предлагаемого устройства тем предпочтительнее, чем выше требования к точности и динамическим диапазонам операндов. Например, для рассматриваемого примера при , выигрыш Q составляет 227 раз, а при m 16, h 64 дй7,.

чн

т

&

t-t И NX

Ч

.о о о.

«At

±

(Ь

DC

а

ос

Jd

,

о о. ii

toJ

о

с

Фиг.1