Устройство для деления чисел в системе остаточных классов Советский патент 1987 года по МПК G06F7/72 

1

12871

Изобретение относится к вычислительной технике и предназначено для использования в быстродействующих арифметических ycтpQйcтвax для выполнения операции делейия чисел, представленных в остаточной системе счисления.

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

На фиг. 1 представлена структур- ная схема предлагаемого устройства для деления в системе остаточных классовi на фиг. 2 - схема блока управления; на фиг. 3 - схема дешифратора.

Устройство содержит вход 1 запуска устройства, вход делимого 2 и делителя 3 устройства, блок 4 управления, регистр 5 делимого, регистр 6 делителя, третий регистр 7, узел 8 задержки, счетчик 9, первый преобразователь 10 прямого кода в дополнительный, блок 11 вычитания, блок 12 умножения, блок 13 масштабирования, блок 14 сложения, второй пре- образователь 15 прямого кода в дополнительный, первый коммутатор 16, первый и второй регистры 17 и 18, чет вертьй регистр 19, регистр 20 частоты, второй коммутатор 21, выход 22 окончания деления устройства, выходы остатка 23 и частного 24 устройства В состав блока 4 управления входят элемент 25 задержки, счетчик 26-, первый элемент ИЛИ 27, первый триг- гер 28, дешифратор 29, элемент НЕ 30, второй элемент ИЛИ 31, третий элемент ИЛИ 32, элемент И 33, второй триггер 34.

Дешифратор 29 (фиг. 3) может быт реализован с помощью логических элементов типа И 35.1, 35.2,...,35 .2 т-1; (2m-l) - входового элемента ИЛ 36 и (т-1) - входового элемента ИЛИ 37, . где m - модуль основания сие- темь счисления.

Блок 13 масштабирования представляет собой устройство, осуществляющее деление входного числа X , принадлежащего диапазону Б, на некото- рый положительный масштаб S D, число которых ограничено и равно L. Модульный код числа. X и номер 1е(0,1.,.L-lJ масштаба S подаются соответственно на первый и второй входы блока 13, Результатом операции масштабирования является оценка

л

ближайшее целое число дроби -- . В

3f

22

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

Набор используемых масштабов и правило их упорядочения определяются соотношением

, если f,0, , , Vf, 1,2 ° %если ,0,

где ,1..., I, {о, 1 . . ., , L-(2 -l)2.

Узел 8 задержки представляет собой цепь из Т+2 регистров, где Т,- наименьшее целое число не меньп з log,jk; k - число .оснований системы счисления, выходы Т-го и (Т+2)-го - первый и второй его выходы.

По сигналу Г (),подаваемому через вход 1 устройства на первый вход блока 4 управления, вход приема кода регистра делителя 6, установочный вход элемента 8 задержки и вход обнуления счетчика 9, кольцевой счетчик 26 (фиг. 2), ( Т+2)-й регистр узла 8 задержки и счетчик 9 обнуляются, триггер 28 блока управления устанавливается в единичное состояние элемент НЕ 30 формирует сигнал Г , который поступая с первого выхода блока 4 управления на входы синхронизации блока 13 масштабирования и первого регистра 17, блокирует поступление с их выходов, а, следовательно, и с выходов преобразователя 10 в дополнительный код по модулю М . и коммутатора 16 ненулевой информации, на выходах элементов ИЛИ 31 и 27 вырабатываются соответственно сигналы

r, G:,vr, г. .Г.

(2) (3)

(через обозначается содержимое 1-го разряда счетчика 26 (,1,.., Т+5). Так как в данный момент , то 1, благодаря чему в регистр 5 через информационный вход 2 устройства записывается модулярный код (с. , ) делимого А, а в ре- гистры 6, 7 и 19 через информационный вход 3 устройства поступает модулярный код (р,. , .j3, , . . , Э) делителя В (А, BGD, ,1АК, р. i lixi ,2 ,. . . ,k. После этого на3

чинается выполнение операции деления числа А на В,

На первом такте операции код ( Яц) делителя В с выхода регистра 7 поступает на вход блока 13 масштабирования, а номер масштаба, записанный в счетчике 9, на данном такте он равен нулю,, подается на вход узла 8 задержки и второй вход блока 13 масштабирования, который по истечении (Т+3)-го такте опредеТ1 П t O

лит оценку Bjj дроби -- , где S / (формула (О), при этим на (Т+1)-ом такте номер масштаба подается также и на третий вход блока 13 с пер- вого выхода узла 8 задержки. Параллельно с этим на каждом такте работы устройства в блоке 4 управления дешифратор 29, анализируя модулярный код некоторого числа Z D, по- ступающий с выхода регистра 19, вырабатывает сигна31ы Др Д ,...,U2. Величина Q с втор ого выхода дешифратора передается в регистр 34,а сигнал с первого выхода дешифратора 29 подается на вход сброса триггера 28 и вторые входы элементов ИЛИ 32 и И 33, на первые входы которых с иверсного и прямого выходов триггера 28 подаются соответственно величины I и б . В результате элемент ИЛИ 32 формирует сигнал

r--5vu., ,

поступающий на счетный вход счетч ка 26, а на выходе элемента И 33 сфмируется сигнал

.

(4)

который через шестой выход блока 4 управления подается на входы обнуления регистров 18 и 20 и управляющий вход приема кода счетчика 9. Предварительно на счетный вход сч-етчика 9 с пятого выхода блока 4 подается со- держимое (5 триггера 28. Так как вначале работы устройства триггер 28 был установлен в единичное состояние то, содержимое счетчика 9 от такта к такту будет увеличиваться на 1 до тех пор, пока, на первом выходе дешифратора 29 не сформируется сигнал д 1, который приведет к сбросу триггера 28. С этого же момента величина Х от такта к такту начнет принимать единичное значение. Содержимое счетчика 26 станет ненулевым лишь н конп.е (Т+2)-го такта, когда в (Т+З -й разряд с выхода эпе524

мента 25 задержки поступит величина . Поэтому начиная с (Т+3)-го такта (с момента получения оценки В )

о

И ДО первого появления на первом выходе дешифратора 29 единичной величины (& 1) с третьего выхода блока 4 управления на управляющий вход приема кода регистра 19 будет поступать единичный сигнал (6 ) ,вслед- .ствие чего выходная информация блока 13 масштабирования на каждом из тактов в указанном промежутке времени будет записываться в регистр 19.

Благодаря конвейерной структуре блока 13 на (1 + 1)-ом такте () . начинается выполнение, операции мас- сттабирования делителя на маси таб g (формула ()), результат которой В будет получен в регистре 19 по истечении (Т+1+3)-го такта. Так как последовательность оценок В, В , . . ., является абсолютно убывающей, то для любого В из диапазона D системы исчисления существует такой минимальный номер .ve{0,1,...,2-1, для которого оценка (-1п+1, -т+2, ...,т-1}. Тогда согласно изложенному на (T+V+4)-oM такте в рассматриваемой при , , на первом выходе ратора 29, а, следовательно, и на выводе элемента И 33 вырабатываются единичные сигналы, а триггер 28 обнуляется, в связи с чем наращивание содержимого счетчика 29 в дальнейшем производиться не будет. По сигналу Г 1, поступающему с шестого выхода блока 4 управления, регистры 18 и 20 обнуляются, а в группы из младших , Л и старших b разрядов счетчика 9 поступают соответственно номер V-1-1 с второго выхода элемента 8 задержки и выходная величина |3 коммутатора 21 где

p B singnBj2b lB sipnBvli ,

Формирование величины J3 ос тпествляет ся путем подачи содержимого группы Ъ младпгих разрядов k-й и.ифры модулярного кода числа В, записанного в регистре 19, на первый инсЬор- мационный вход коммутатора 21 и вход преобразователя 15, определяющего вычет (, , который поступает на второй информационный вход коммутатора 21, при этом на его вход управления с восьмого выхода блока 4 управления подается знак д , числа В, а следовательно, и делителя В, вырабатываемый на втором выходе дешифратора 29 при 7.Б. Если &,

на выходе коммутатора 21 появляе;тся нычет ,jb, если же h , то - вычет I-B 1 ь . Сформированное на (Т+

+V+A)-OM такте содержимое счетчика 9 в дальнеш1ем не изменяется, а соответствующий ему маспгтаб

- ,,.,.,,,к-

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

Второй этап реализуемой процедуры делителя носит итеративный характер. Все итерации имеют одинаковую длительность Т+6 тактов, причем пер- ,вый такт первой итерации во времени совмещен с заключительным (T+V+4) тактом первого этапа алгоритма.

На втором такте первой итерации модулярньй код делимого А с выхода регистра 5 и содержимое второго регистра 18 код нуля подаются соответственно на первый и второй входы блока 11 вычитания, в результате чего на его выходе формируется разность , которая передается в пер- регистр 1 7 .

На третьем такте первой итерации код Числа АО с выхода регистра 17 пересылается в регистр 5, а также подается на первый информационный вход коммутатора 16 и вход преоб- разователя 10 в дополнительный код по модулю М . Полученный преобразователем 10 код числа |-А)м поступает на второй информационный вход коммутатора 16, на вход управления которого с седьмого выхода блока 4 управления подается сигнал д (знак

12871526

На первом такте .й-й итерации

(,i-2,3,....) на. выходе блока 12 получится произведение 0. В, код которого передается в регистр 18, а на выходе блока 14 сформируется код

суммы Го,, который по сигналу Г 1 0

поступающему с третьего выfO

J5

G- 1,

-г+4 /

хода блока 4 управления, записывается в регистр 20 частного. Аналогично первой итерации на втором и третьем тактах j-й итерации с помо- щью блока 1 вычитания, регистра 17 преобразователь 10 в дополнительный код по модулю М и коммутатора 16 в регистрах 5 и 7 сформируются соответственно модулярные коды чисел

А; А. 1-0,- ,Б и R- А; sing(B), а по ис

J j 1 I f течении (,1 + п)-го такта итерации в

регистре 19 будет получена оценка

р. Q. дроби --

Описанная последовательность дей ствий повторяется до тех пор, пока

25 по окончании некоторой г-й итерации (г: ) в выходном регистре 19 блок масштабирования не будет получен ко нуля (о 0). В том случае на третье выходе дешифратора 29, а, следова jg тельно, и на выходе 22 устройства появится единичный сигнал. Искомое

20

Г-1

частное Q О

и остаток сни

маются с выходов 24 и 23 устройства 35 на этом процесс деления числа А и Б завершается.

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

.числа в). В результате на выходе коммутатора 16 сформируется модулярный код чиcJи Rg AgSipnB, который передается в регистр 7. Заметим,что в тeкyD eм такте содержимое 6 . нулевого разряда счетчика 26 принимает единичное значение, поэтому на вхо-. ды разрешения записи регистров 5 и 7 будет подан единичный сигнал . В течение (Т+З) последних тактов первой итерации блок 3 масштабирования находит модулярный код оцен- р

ки Q дроби г и он записывается в ±)

регистр 19, так как на последнем (Т+б)-ом такте каждой итерации б 1 и, следовательно, на вход разрешения записи регистра 19 с четвертого выхода блока 4 поступит сигнал

Устройство для деления чисел в системе остаточных классов, содер жаш. ее регистры делимого, делителя и частного, блок вычитания, блок сложения, причем первые информационные

45 входы регистров делимого и делителя являются входами делимого и делител устройства соответственно, выход ре гистра частного является выходом ча стного устройства и соединен с перв

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

суммы Го,, который по сигналу Г 1 0

поступающему с третьего вы

G- 1,

-г+4 /

хода блока 4 управления, записывается в регистр 20 частного. Аналогично первой итерации на втором и третьем тактах j-й итерации с помо- щью блока 1 вычитания, регистра 17, преобразователь 10 в дополнительный код по модулю М и коммутатора 16 в регистрах 5 и 7 сформируются соответственно модулярные коды чисел

А; А. 1-0,- ,Б и R- А; sing(B), а по исJ j 1 I f течении (,1 + п)-го такта итерации в

регистре 19 будет получена оценка

р. Q. дроби --

Описанная последовательность действий повторяется до тех пор, пока

по окончании некоторой г-й итерации (г: ) в выходном регистре 19 блока масштабирования не будет получен код нуля (о 0). В том случае на третьем выходе дешифратора 29, а, следовательно, и на выходе 22 устройства появится единичный сигнал. Искомое

Г-1

частное Q О

и остаток снимаются с выходов 24 и 23 устройства, 35 на этом процесс деления числа А и Б завершается.

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

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

входы регистров делимого и делителя являются входами делимого и делителя устройства соответственно, выход регистра частного является выходом частного устройства и соединен с первым

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

712

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

O 5 0 5 0 jQ

5

528

дом дешифратора блока управления,выход второго преобразователя прямого кода в дополнительный соединен с вторым информационным входом второго коммутатора,выход которого соединен с входом старших информационных разрядов счетчика, выход элемента :НЕ блока управления соединен с входом разрешения записи первого регистра и с входом синхронизации блока масштабирования, выход второго элемента ИЛИ блока управления соединен с входом разрешения записи регистра делимого и третьего регистра, выход (Т+4)-го разряда счетчика блока управления, где - целая часть, , k - число основания системы счисления, соединен с входом разрешения записи регистра частного, выход первого элемента ИЛИ блока управления соединен с входом разрешения записи четвертого регистра, прямой выход первого триггера блока управления соединен с первым входом элемента И блока управления и счетным входом счетчика устройства, вход разрешения записи которого соединен с входами сброса второго и четвертого регистров и выходом элемента И блока управления, выход второго триггера которого соединен с входом управления первого коммутатора, выход элемента задержки блока управления соединен с информационным входом счетчика блока управления, счетный вход которого соединен с выходом третьего элемента ИЛИ блока управления, первьй и второй ходы которого соединены соответственно с первым выходом дешифратора и инверсным выходом первого триггера блока управления,выходы нулевого и (Т+З) разрядов счетчика блока управления соединены с вторыми входами соответственно второго и первого элемента ИЛИ блока управления, первый выход дешифратора блока управления соединен с входом разрешения сброса первого триггера и вторьп входом элемента И блока управления, второй выход дешифратора блока управления соединен с инфор- мадионньм входом второго триггера блока управления и входом управления второго коммутатора, третий выход дешифратора блока управления является выходом окончания деления устройства.

22

Фш./

Q5

и

т

43

32

-Wi

Фut2

Изобретение относится к вычислительной технике и предназначено для быстрого деления целых чисел в системе остаточных классов. Цель изобретения - повышение быстродействия устройства за счет применения конвейерного принципа обработки кодов делимого и делителя. Основным элементом устройства является высокоскоростной блок масштабирования чисел конвейерного типа. Поставлен-: ная цель достигается введением четырех дополнительных регистров, двух преобразователей прямого кода в дополнительный, сч:ётчика, узла задержки и двух коммутаторов. 3 ил. S кэ 00 1 СП ГчЭ

Фаг.З

ВНИИПИ Заказ 7718/52 Тираж 694

Произв.-полигр. пр-тие, г. Ужгород, ул. Проектняя, 4

Подпис. iioe