Устройство для деления п-раздельных чисел

Устройство для деления п-раздельных чисел

Иллюстрации

Показать все

Реферат

 

ОП ИСАНИ Е

ИЗОБРЕТЕН ИЯ

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

Союз Советскнк

Соцнелнстнческнк

Республнк

Опубликовано.05.05.80. Бюллетень 1}е 17 (5! )М. Кл.

Ск 06 г 7/52

Государственный комитет

СССР (53) УДК 681.

° 325(088.8) 60 делам изобретений и открытий

Дата опубликования описания. 06.05.80 (72) Авторы изобретения

Б. Г. Лысиков, Е, B. Песин и A. А, Шостак (71) Заявитель

Минский радиотехнический институт (54) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ 1} РАЗРЯДНЫХ

ЧИС ЕЛ

Изобретение относится к вычислительной технике н может быть применено при разработке быстродействующих устройств деления, Известно устройство для деления, со5 держащее комбинационный сумматор, входы которого соединены с шинами.значений 11 разрядов делимого и делители, а выход соединен с шиной значений +. разрядов остатка, выход его знакового разряда соединен с шиной значении цифр частного (1) Основным недостатком такого устройства является большое время попучениа цифры частного (оно примерно равно вре15 мени сложения двух A- разрядных чисел), а также невозможность одновременного получения нескольких цифр частного.

Известно устройство для деления, содержащее формирователь устроенного делителя, комбинационный сумматор, узлы сравнения, узел формирования цифр част ного и узел коррекции остатка Я .

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

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

ro также c.в хоoд о м M ш ифра тTоoрpа, выход ко торого подключен к первому входу блока коррекции, а второй вход блока коррекции соединен с выходом вычитателя 13)

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

732868

Ноставленная цель достйг ается тем, что в устройство для деления введены

П /К счетчик Q -разрядных узлов умножения (К = й-п/й), (h 4 К ) — разрядный сумматор, два вычитателя Tl — разряд- 5

Р ный коммутатор остатка, элемент НЕ, счетчик коррекции частного, при атом входы счетчика соединены с шинами (К 2.} старших разрядов целителя, а выход соединен со входом шифратора цифр, выход которого соединен с первыми входами узлов умножения, вторые входы которых соединены с соответствующей группой

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

HE с выходом знакового разряда третьего вычитателя, выход счетчика коррекции частного соединен с шиной частного.

На чертеже приведена функциональная схема устройства.

Устройство содержит счетчик 1 при40 нудительного округления делителя, шифратор 2, П/K К - разрядных узлов 3 умножения, (n+8, ) разрядный сумматор 4, три (O+ К ) — разрядных вычит4теля

5, 6 и 7 A — разрядный коммутатор 8

t 45 остатка, элемент НЕ 9 и счетчик 10 коррекции частного, вход счетчика 1 принудительного округления делителя соединен с шиной 11 (К +2) старших разрядов 1 шины 12 делителя, а выход соединен с входом делителя шифратора 2, вход дели50 мого которого соединен с шиной 13

f /+2) старших разрядов шины 14 делимого, а его выход соединен с первыми входами узлов 3 умножения, вторые вхо55 ды каждого из которых соединены с шинами 15 \(разрядов делителя с учетом весовой позиции 2 3(— разрядного произведения, выходы узлов 3 умножения соеди1 п311 ь1 с р:11311О (3есовы ми входами су м мате ра 4, 13ХОд v О11ьц1аемого второго вычитателя 6 соедппрн с шиной 14 и -разрядов делимого, и er О вход вьгштаемого соединен с шиной 12 13 разрядов делителя, сдвинутых на 1(разрядов в сторону младших ра.3р ядов, вход уменьшаемого третьего вычитателя 7 соединен с выходом второго вычитателя 6, а его вход вычитаемого соединен с выходом сумматора 4, вход уменьшаемого первого вычитателя 5 соединен с шиной 14 и -разрядов делимого, а его вход вычитаемого соединен с выходом сумматора 4, входы коммутатора 8 остатка соединены с выходами П младших разрядов первого и третьего вычитателей 5 и 7, а его управ- ° ляющий вход соединен с выходом 17 знакового разряда третьего вычитателя 7, выход коммутатора 8 остатка соединен с шиной 16 >1 разрядов остатка, вход счетчика 10 коррекции цифр частного соединен с выходом шифратора 2, а его управляющий вход соединен через элемент HE 9 с выходом 17 знакового разряда третьего вычитателя 7, выход счет чика 10 коррекции частного соединен с шиной 18 К цифр. В устройстве счетчик

1 принудительного округления делителя производит прибавление к (К +2) старшим разрядам делителя единицы к их младшему разряду. Шифратор 2 осуществляет деление (3(+2) старших разрядов делимого на принудительно округленные (\(+2,1 старших разрядов делителя. С помощью узлов 3 умножения и сумматора 4 формируется (h+ К ) — разрядное произведение г3 -разрядного делителя íà g -разрядное частное, полученное на выходе шифратора 2. В каждом узле 3 умножения осуществляется умножение К разрядов частного, полученных на выходе шифратора 2, на соответствующие К разрядов делителя с учетом весовой позиции

2 К -разрядного произведения. В предлагаемом устройстве предполагается, что все узлы 7 умножения, подобно шифратору 2, выполнены в виде логических шифраторов k -разрядных кодов сомножителей в 2 К -разрядный код их произведения. Следует .особо. отметить, что в определенных случаях с целью сокращения оборудования и обеспечения регулярности структуры шифратора 2 и узла 3 умножения целесообразна реализация шифратора 2 и виде матрицы взаимосвязанных сумматоров-вычитателей, а узлов 3 умно-: жения - в виде матрицы взаимосвязанн-:..

7З28

Х=Х =У -2

Исакс Л

Последнее соотношение можно привести к виду

0

Действительно, пусть х -значение делимого, поступаюшего на вход шины 14 устройства; у -значение делителя, посту лающего на входы шины 12 устройства;

Х вЂ” значение старших (К +2) разрядов делимого, поступающих на вход делимого шифратора генерации К цифр псевдочастиого; У -значение старших (К +2) разрядов делителя, поступающих на Ьход счет

40 чика принудительного округления; л =Х-Х„и у=Ч-у„

Покажем, -«то х о — « I2-K у,» 2++т)

Здесь предполагается, что

0 Xi) {/2<ус v y(p

55 сумматоров. Здесь также предполагается

I что во всех вычитателях и сумматоре используются пели ускоренного формирования заема и переноса. Коммутатор 8 остатка может быть реализован на элемен- 5 тах И-ИЛИ.

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

По шинам 14 и 12 поступают в прямом коде без знака A -разрядные дели- 0 мое и делитель (для определенности предполагается, что система счисления двоичная), В счетчике 1 принудительного округления делителя производится добавление

К (К +2) старшим разрядам делителя единицы в их младший разряд. Этим самым устраняется возможность получения в шифраторе 6, в котором производится деление (К +2) старших разрядов делимого на (К +2) разряда делителя, частного с избытком на выходе узла принудительного округления. Можно показать, что абсолютная погрешность (разность между значением частного, получаемого при делении и -разрядных чисел и значением частного, получаемого при делении усеченных (К+2) — разряднык чисел) при этом будет заключена в пределах

Выполнение левого условия, очевидно, поэтому ограничимся лишь доказательством неравенства: х х„

-K у + 2 т1

c L которое можно лерелирать в виде

К (у+2 " ")-x„ < 2 у(у1 (" 4) 68 6

Нетрудно заметить, » о максимальная абсолютная погрешность б дет в том случае, когда (+<) -и

У =У =0(У-Ъ ) Х =X, *2

2 Ф,Мин 4 Д айзакс

С учетом этого получим

Х.2 + Х У,<2 J (У„ g. илр, -(к+ 2) -ь -{к ) {»-2 "12 " <("- т"jv„<2»{к ) У.2 (" ") " < -{g+g)

4 которое выполняется при всех значениях

Ъ, закшоченных в пределах "/24 >«i что и требовалось доказать. Но тогда значение 6. — разрядного частного, получаемого при делении усеченных чисел, может быть либо равно значению старших К разрядов частного, получаемых при делении К вЂ” разрядных чисел, либо меньше его на единицу младшего разряда с весом 2 (в дальнейшем.будем говорить соответственно о точном и неточном значениях К вЂ” разрядного частного на выходе шифратора генерации К цифр частного).

С помощью узлов 3 умножения и сумматора 4 формируется (h + К ) - разрядное произведение и -разрядного, делителя на К -разрядное частное, полученное на выходе шифратора 2 генерации

К цифр псевдочастного. С помощью второго и третьего вычитателей 6 и 7 производится вычитание из и -разрядного делимого A -разрядного делителя сдвинутого на К разрядов в сторону младших разрядов, а также (о + К) — разрядного произведения, полученного на вь ходе сумматорв 4. Если получившаяся при этом разность положительна, то это означает, что сформированное шифратором 2 К -разрядное частное неточное и его необходимо скорректировать в счет чике 10 коррекции частного путем добавления единицы в его младший разряд.

Коммутатор 8 остатка в этом случае

coeQHBQeT выход tl млацших разря дов третьего вычитателя 7 с шиной Д6

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

O младших разрядов первого вычитателя 5, в котором сформирована разность 10 делимого и. (A+K )-разрядного произведения, полученного на выходе сумматора 4, с шиной 16 и разрядов остатка.

Ниже рассматривается; пример, поясняющий принцип работы и структурные особенности устройства для деления и разрядных чисел (для определенности выбраны A =12 и К=4), Пусть х= 101001111111;

У =101010000000. Значение К цифР 20 частного при делении X на равно

1111, значение получившегося при этом остатка Х

0000101001110000.

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

О = > + a =0,101010+0,000001=

=0,101011, в шифраторе 2 генерации четырех цифр частного формируется 4-разряд ное частное Z 4= X : О =О, 10 100 1:

:0,101011--0, 1111, с помощью узлов 3 умножения и сум- 5 матора 4 формируется 16-Разрядное про,и=.ведение b=> g =О,ЮО111011000ОООО в вычитателе 6 формируется разность

С, Х-У.2. 0,1001110101110000, в вычитателе 7 формируется разность

0 = С4-b =-0,0000000000010000, в вычитателе 5 формируется. разность

5 =Х-Ь =0,00001010011 0000.

Ъ

Так как полученная на выходе третьего вычитателя 7 разность отрицательна 4> то сформированное в шифраторе 2 4-ðàçрядное частное Z точное и не требчется дополнительная коррекция, а сфрмированная в вычитателе 5 Разность С является остатком

Рассмотренное устройство используется для формирования и -разрядного част ного.за n(g тактов, а также при постРоении матричных (однотактных) устро йств деления, Оно позволяет сократить время формирования остатка и К, цифр частного (, в сравнении с известным устройством примерно в К раз

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

Устройство для деления л Разрядных чисел, содержащее шифратор, первый

Нычитатель, вход умень шаемого которого подключен к шине делимого, соединенной со входом шифратора о т л и ч,а ю— щ е е с я тем,. что, с целью повышения быстродействия, в него введены счетчик n/Ê К-разрядных (К= 2 2 ) узлов умножения, (и к ) — Разрядный сумматор, второй и тРетий вычитатели, fl -разРядный коммутатор остатка, элемент НЕ, счетчик коРРекции частного, при этом входы счетчика соединены с шиной (К+2) старших Разрядов делителя, а выход соединен со входом шифратора, выход которого соединен с первыми входами узлов умножения, вторые входы которых соединены соответствующей группой К- разрядов делителя, выход узлов умножения соединен с соответствующей гРуппо и входом сумматора, вход уменьшаемого втоРого вычитателя соединен с шиной делимого, а вход вычитаемого второго вычитателя. соединен с шиной целителя, вход уменьшаемого тРетьего вычитателя соединен с вЫходом второго вычитателя, а вход вычитаемого первого вычитателя и вход вычитаемого третьего вычитателя соединены с выходом сумматора, входы коммутатоРа остатка соединены с выходами tl -младших Разрядов первого и третьего вычитателей, а егоуправляющий вход соединен с выходом знакового разряда третьего вычитателя, выход коммутатора остатка соединен с шиной и -разрядов остатка, вход счетчика коррекции частного соединен с выходом шифратора, а упРавляющий вход соединен через элемент НЕ с выходом знакового Разряда третьего вычитателя, выход счетчика коррекции частного соединен с шиной частного.

Источники информации, пРинятые во внимание при экспертизе

1. Карцев H. A. Арифметика цифровьх машин, М., 1868, с, 494, рис. 5,1а, 2. Папернов А, А. Логические основы

ЫВТ. М., 1972, с. 247, рис, 5.

3. Патент США N 3234367, кл. 235-176, 1968 (нрототип).

732868

Составитель Г. Плешев

Редактор Л. Курасова ТехрелЖ.Кастелевич Корректор М. немчик

Закаэ 1737/38 Тираж 751 Подписное

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

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

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