Устройство для деления чисел в системе остаточных классов

Устройство для деления чисел в системе остаточных классов

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИН (50 4 0 06 F 7/7? " Г.

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

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

:В»

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3919291/24-24 (22) 01.07,85 (46) 30.01.87. Бюл, к- 4 (71 ) Научно-исследовательский институт прикладных физических проблем им, А.Н.Севченко (72) А.А.Коляда (53) 681,325(088 ° 8) (56) Авторское свидетеЛьство СССР

Р 398949, кл, G 06 F 7/72, 1971.

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

9 579614, кл, G 06 F 7/72, 1972, (54) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ ЧИСЕЛ В

СИСТЕИЕ ОСТАТОЧНЫХ КЛАССОВ

„„SU„„1287152 А 1 (57) Изобретение относится к вычислительной технике и предназначено для быстрого деления целых чисел в системе остаточных классов. Цель изобретения — повышение быстродействия устройства за счет применения конвейерного принципа обработки кодов делимого и делителя, Основным элементом устройства является высокоскоростной блок масштабирования чисел конвейерного типа. Поставлен-. ная цель достигается введением четырех дополнительных регистров, двух преобразователей прямого кода в дополнительный, счетчика, узлà задержки и двух коммутаторов, 3 ил.

) 2871

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

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

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

Устройство содержит вход 1 запуска устройства, вход делимого 2 и делителя 3 устройства, блок 4 управления, регистр 5 делимого, регистр

6 делителя, третий регистр 7, узел 20

8 задержки, счетчик 9, первый преобразователь 10 прямого кода в дополнительный, блок 11 вычитания, блок

12 умножения, блок 13 масштабирования, блок 14 сложения, второй пре- 25 образователь 15 прямого кода в дополнительный, первый коммутатор 16, первый и второй регистры 17 и 18, четвертый регистр 19, регистр 20 частоты, второй коммутатор 21, выход 22 30 окончания деления устройства, выходы остатка 23 и частного 24 устройства, В состав блока 4 управления входят элемент 25 задержки, счетчик 26, первыи элемент ИЛИ 27, первый триггер 28, дешифратор 29, элемент HE

30, второй элемент ИЛИ 31, третий элемент ИЛИ 32, элемент И 33, второй триггер 34, Дешифратор 29 (фиг. 3) может быть 40 реализован с помощью логических элементов типа И 35.1, 35,2,...,35.2

m-1; (2m-1) — входового элемента ИЛИ

36 и (m-1) — входового элемента ИЛИ

37,, где m — модуль основания сис- 45 темы счисления.

Блок 13 масштабирования представляет собой устройство, осуществляющее деление входного числа X принадлежащего диапазону D, на некоторый положительный масштаб F ED, В число которых ограничено и равно L.

Модульный код числа, Х и номер

1 0, 1...L-1I масштаба Б подаются соответственно"на первый и второй входы блока 13. Результатом операции масштабирования является оценка

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

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

Ь,(, 1)

S, ° = ь,с, Х, 2,если <, 0, где 2е {0 1...2"-2), 1 ={0 1...,2 — 1), Ь=(2" -1 ) 2b

Узел 8 задержки представляет собой цепь из Т+2 регистров, где Т наименьшее целое число не меньп1е

log k; k — число оснований системы счисления, выходы Т-ro и (Т+2)-го первый и второй его выходы.

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

Г =Г=О, который поступая с первого выхода блока 4 управления на входы синхронизации блока 13 масштабирования и первого регистра 17, блокирует поступление с их выходов, а, следовательно, и с выходов преобразователя 10 в дополнительный код по модулю М и коммутатора 16 ненулевой к информации, на выходах элементов ИЛИ

31 и 27 вырабатываются соответственно сигналы (2) Г2 = Gvró (3) r, =G,fr, (через 6 обозначается содержимое

i-ro разряда счетчика 26 (i=O 1, ° ., Т+5). Так как в данный момент Г=l, то Г =Г =1, благодаря чему в регистр

5 через информационный вход 2 устройства записывается модулярный код (<, с,...,".) делимого А, а в ре— гистры 6, 7 и 19 через информационный вход 3 устройства поступает модулярный код (P,, I),..., {3„) делите. ля В (А, ВЕВ, НСС; Ы,=)АI {3 =

= ) B),„ i-=i,2,...,k. После этого на52 2 блоке 13 масштабирования стандартным образом реализована функция бло d=GV h,, поступающий на счетный вход счетчи-35 ка 26, а на выходе элемента И 33 сформируется сигнал (4) Г 04, который через шестой выход блока 4 40 управления подается на входы обнуления регистров 18 и 20 и управляющий вход приема кода счетчика 9. Предварительно на счетный вход счетчика 9 с пятого выхода блока 4 подается содержимое ь триггера 28. Так как вначале работы устройства триггер 28 был установлен в единичное состояние то, содержимое счетчика 9 от такта к такту будет увеличиваться на 1 до тех пор, пока на первом выходе дешифратора 29 не сформируется сигнал д =l, который приведет к сбросу

1 триггера 28. С этого же момента величина 1 от такта к такту начнет 55 принимать единичное значение. Содержимое счетчика 26 станет ненулевым лишь в конце (Т+2)-го такта, когда в i.I о,Т+3, -й разряд с выхода эле3 1287 чинается выполнение операции деления числа А на В.

На первом такте операции код (P, 1 ,..., P,) делителя В с выхода регистра 7 поступает на вход блока 13

5 масштабирования, а номер масштаба, записанный в счетчике 9, на данном такте он равен нулю, подается на вход узла 8 задержки и второй вход блока 13 масштабирования, который по истечении (Т+3)-го такте опредеВ Ьо лит оценку В, дроби --, где F. =2 (формула (1 ) ), при этом на (Т+1 )-ом такте номер масштаба подается также и на третий вход блока 13 с первого выхода узла 8 задержки. Параллельно с этим на каждом такте работы устройства в блоке 4 управления дешифратор 29, анализируя модулярный код некоторого числа Е E.D, по- 20 ступающий с выхода регистра 19, вырабатывает сигнаПн

Величина с второго выхода дегпифратора передается в регистр 34,а сигнал с первого выхода дешифратора

29 подается на вход сброса триггера

28 и вторые входы элементов ИЛИ 32 и И 33, на первые входы которнх с инверсного и прямого выходов триггера

28 подаются соответственно величины 30

0 и Б . В результате элемент ИЛИ 32 формирует сигнал

152 4 мента 25 задержки поступит величина

1 =1 . Г оэтому начиная с (Т+3)-ro такта (с момента получения оценки В ) о и до первого появления на первом выходе дешифратора 29 единичной величины (А =1) с третьего выхода блока т

4 управления на управляющий вход приема кода регистра 19 будет поступать единичный сигнал (б„ =1),вследствие чего выходная информация блока

13 масп табирования на каждом из тактов в указанном промежутке времени будет записываться в регистр 19.

Благодаря конвейерной структуре блока 13 на (1+1)-ом такте (1 > О) начинается выполнение операции масп табирования делителя на масп таб

8 =2 (формула (1 ) ), результат котоГ „ рой В будет получен в регистре 19

1 по истечении (Т+Х+3) -го такта . Так как последовательность оценок В,, В,..., является абсолютно убываю— щей, то для любого В из диапазона D системы исчисления существует такой л минимальный номер г Е-10, l .. 2 -, для которого оценка В j-и;+1, -m+2 ..., m†- 1). Тогда согласно изложенному на (Т+ Ч+4) — ом такте в рассматриваемой при Z=B на первом выходе депифV ратора 29, а, следовательно, и на вы оде элемента И 33 вырабатываются единичные сигналы, а триггер 28 обнуляется, в связи с чем наращивание содержимого счетчика 29 в дальнейшем производиться не будет. Го сигналу

Г =1, поступающему с шестого выхода блока 4 управления, регистры 18 и 20 обнуляются, а в группы из младпIHx д и cTBpIIIHx Ь разрядов счетчика 9 поступают соответственно номер 7 л! с второго выхода элемента 8 задержки и выходная величина (коммутатора 21 где =1 В э пРпВ, ь — 1Р з:гРпВ„ а

Формирование величины Р осуществляетсяя путем подачи содержимого ) В„1 6 группы b младпгих разрядов k-й гифры модулярного кода числа В „, записанного в регистре 19, на первый информационный вход коммутатора 21 и вход преобразователя 15, определяющего вычет (-B„l ь, который поступает на второй информационный вход коммутатора 21, при этом на его вход управления с восьмого выхода блока 4 управления подается знак 4 числа В„, 2 а следовательно, и делителя В, вырабатываемый HB втором выходе дешифратора 29 при 2,=В „. Если a, =0, то

87152 6

На первом так Ге,4-й итерации (,1=2,3,.... ) на выходе блока 12 лучится произведение A. В, код

j-1 торого передается в регистр 18, на выходе блока 14 сформируется

J суммы Е и которь>й по сигналу

:4

>-<> пококод

Г з

35 завершается.

5 12 на ныходе коммутатора 21 появпяется вычет ) В ) ь если же h =1 то — вь! чет )-Б,) ь . Сформированное на (Т+

+V+4)-о» такте содержимое счетчика

9 в дальнейшем не изме14яется, а соответствующий ему масштаб л b (vi>) (формула (1)) используется в качестве приближения абсолютной величины делителя В на следующем этапе алгоритма, Второй этап реализуемой процедуры делителя носит итеративный характер. Все итерации имеют одинаковую длительность Т+6 тактов, причем первый такт первой итерации во времени совмещен с заключительным (7+V+4)-ым тактом первого этапа алгоритма, На втором такте первой итерации модулярный код делимого А с выхода регистра 5 и содержимое второго регистра 18 код нуля подаются соответственно на первый и второй входы блока 11 вычитания, в результате чего на его выходе формируется разность

А,=А †О, которая передается в первый регистр 17.

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

2 .числа В) . В результате на выходе коммутатора 16 сформируется модулярный код числа Р,=А,з1р,пВ, который передается в регистр 7. Заметим,что в текущем такте содержимое G нулео вого разряда счетчика 26 принимает единичное значение, поэтому на входы разрешения записи регистров 5 и

7 будет подан единичный сигнал

Г =1. В течение (Т+3) последних така тов первой итерации блок 13 масштабирования находит модулярный код опен

R, ки Q дроби — и он записывается в В регистр 19, так как на последнем (Т+6)-ом такте каждой итерации П. т+3

=1 и, следовательно, на вход разрешения записи регистра 19 с четвертого выхода блока 4 поступит сигнал

1 „=1 .

=б =1, поступающему с третьего вы +4 хода блока 4 управления, записыва10 ется в регистр 20 частного, Ана Io гично первой итерации на втором и третьем тактах,)-й итерации с помо-щью блока 11 вычитания, регистра 17, преобразователь 10 в дополнительный код по модулю 14 и коммутатора 16 в

К регистрах 5 и 7 сформируются соответственно модулярные коды чисел

А =А„. 1-Р„,В и Р. =A„sing(B), а по исJ течении (Т+б) "го такта итерации в регистре 19 будет получена опенка

Г

Н, дроби

J В

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

< частное q= P n и остаток R=P сни>=О маются с выходов 24 и 23 устройства, на этом процесс деления числа А и В

<1> о р м у л а и з о б р е т е н и я

Устройство для деления чисел в системе остаточных классов, содержащее регистры делимого, делителя и частного, блок вычитания, блок сложения, причем первые информационные входы регистров делимого и делителя являются входами делимого и делителя устройства соответственно, выход регистра частного является выходом частного устройства и соединен с первым информационным входом блока сложения, выход которого соединен с информационным входом регистра частного, о тл и ч а ю щ е е с я те», что, с IIeлью повьш>ения быстродействия, в него введены четыре регистра, два преобразователя прямого кода в дополнительный, счетчик, узел задержки, блок масштабирования, два ко»»утатор» и блок управ >ения, ь < ос га з ><с <>р I,>

) 287)52 входят счетчик, два триггера, дешифратор, три элемента ИЛИ, элемент задержки, элемент НЕ и элемент И, причем вход запуска устройства является входом элемента задержки блока управления и соединен с входом элемента НЕ, с первыми входами первого и второго элементов ИЛИ, с входом разреп!ения сброса счетчика и с входом установки в единипу триггера f0 блока управления, с входом разрешения записи регистра делителя, с тактовым входом узла задержки и входом сброса счетчика устройства, выход регистра делимого соединен с входом 15 уменьшаемого блока вычитания, выход которого соединен с информационным входом первого регистра, выход которого соединен с входом первого преобразователя прямого кода в дополни- д) тельный, с первой группой информационных входов первого коммутатора и с вторым информационным входом регистра делимого, выход регистра делителя соединен с первым информационным вхо-25 дом блока умножения, выход которого соединен с информационным входом второго регистра, выход которого соединен с .входом вычитаемого блока вычитания, вход делителя устройства ц соединен с первыми информационными входами третьего и четвертого регистров, выход третьего регистра является выходом остатка устройства и соединен с входом-остаточного кода блока масштабирования, первый и второй входы номера масштаба которого соединены с первым выходом узла задержки и информационным выходом счетчика, второй выход узла задержки сое-4п динен с входом младших информационных разрядов счетчика, выход которого соединен с входом узла задержки, выход первого преобразователя прямого кода в дополнительный соединен с 45 вторым информационным входом первого коммутатора, выход которого соединен с вторым информационным входом второго регистра, выход блока масштабиро- вания соединен с вторым информационным входом четвертого регистра,выход которого соединен с вторыми информационными входами блоков умножения и сложения, с первой группой информационных входов второго коммутатора, входом второго преобразователя

55 прямого кода в дополнительный и входом деп|ифратора блока управления, выход второго преобразователя прямого кода в дополнительный соединен с вторым информационным входом второго коммутатора, выход которого соединен с входом старших информационных разрядов счетчика, выход элемента . НЕ блока управления соединен с входом разрешения записи первого регистра и с входом синхронизации блока масштабирования, выход второго элемента

ИЛИ блока управления соединен с входом разрешения записи регистра делимого и третьего регистра, выход (Т+4)-ro разряда счетчика блока управления, где ) (— целая часть, T=)log k (, k — число основания системы счисления, соединен с входом разрешения записи регистра частного, выход первого элемента ИЛИ блока управления соединен с входом разреп ения записи четвертого регистра, прямой выход первого триггера блока управления соединен с первым входом элемента И блока управления и счетным входом счетчика устройства, вход разрешения записи которого соединен с входами сброса второго и четвертого регистров и выходом элемента И блока управления, выход второго триггера которого соединен с входом управления первого коммутатора, выход элемента задержки блока управления соединен с информационным входом счетчика блока управления, счетный вход которого соединен с выходом третьего элемента ИЛИ блока управления, первый и второй входы которого соединены соответственно с первым выходом дешифратора и инверсным выходом первого триггера блока управления,выходы нулевого и (Т+3) разрядов счетчика блока управления соединены с вторыми входами соответственно второго и первого элемента ИЛИ блока управления, первый выход дешифратора блока управления соединен с входом разрешения сброса первого триггера . и вторым входом элемента И блока управления, второй выход дешиАратора блока управления соединен c информационным входом второго триггера блока управления и входом управления второго коммутатора, третий выход дешифратора блока управления является выходом окончания деления устройства, 1287152

Фиа f

ВНИИПИ Заказ 7718/52 Тирак 694 Подписное

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