Устройство для деления п-раздельных чисел Советский патент 1980 года по МПК G06F7/52 

37 Поставпеияая цель достигается том, что в устройство для деления введены п/к счетчик К -разрядных узлов ум ножения {K ), ( к ) - разрядны сумматор, два вычитателя п - разряд- ный коммутатор остатка, элемент НЕ, счетчик коррекции частного, при этом входы счетчика соединены с шинами (М2 старших разрядов делителя, а выход соединен со входом шифратора цифр, выход которого соединен с первыми входами узлов умножения, вторые входы которых соединены с соответствующей группой К разрядов делителя,выходы узлов умножения соединены с соответствующей группой входов сумматора, вход уменьшаемог второго вычитателя соединен с шиной делимого, а вход вычитаемого второго вычнтателя соединен с шиной делителя, вход уменьшаемого третьего вычитателя соеди нен с выходом второго вычитателя, а вхо вычитаемого первого вычитателя и вход вычитаемого третьего вычитателя соединен с выходом сумматора, входы коммута тора остатка соединены с выходами П младших разрядов первого и третьего вычитателей, а его управляющий вход соеди нен с выходом знакового разряда третьего вычитателя, выход коммутатора остат1 ка соединен с шиной п разрядов остат ка, вход счетчика коррекции цифр част кого соединен с выходом шифратора, а управляющий вход соединен через элемент НЕ с выходом знакового разряда третьего вычитателя, выход счетчика коррекции частного соединен с шиной частного. На чертеже приведена функциональная схема устройства. Устройство содержит счетчик 1 принудительного округления делителя, шифратор 2, П/К К - разрядных узлов 3 умножения, ( ) разрядный сумматор 4, три ( К ) - разрядных вычитйтеля 5, 6 и 7| U - разрядный коммутатор 8 остатка, элемент НЕ 9 и счетчик 10 кор рекции частного, вход счетчика 1 принудительного округления делителя соединен с шиной 11 ( К +2) старших разрядов j шины 12 делителя, а выход соединен с входом делителя шифратора 2, вход делимого которого соединен с шиной 13 (К+2) старших разрядов шины 14 де лимого, а его выход соединен с первыми входами узлов 3 умножения, вторые входы каждого из которых соединены с шинами 15 К разрядов делителя с учетом весовой позиции 2К- разрядного произведения, выходы узлов 3 умножения соеbцнисиы с ).-1внп1}оспвь1ми входами сумматора 4, вход у оиьц1пемого второго вычитато.чя 6 сооциири с шиной 14 п -разрядов делимого, а его вход вьгштаомого соеаииен с ииной 12 г разрядов делителя, сдвинутых на V разрядов в сторону младших ра:фядов, вход уменьшаемого третьего вычитателя 7 соединен с выходом второго вычитателя 6, а его вход вычитаемого соединен с выходом сумматора 4, вход уменьшаемого первого Bbfчитателя 5 соединен с шиной 14 П -разрадов делимого, а его вход вычитаемого соединен с выходом сумматора 4, входы коммутатора 8 остатка соединены с вььходами П младших разрядов первого и третьеговычнтателей 5 и 7, а его управ- ляющий вход соединен с выходом 17 знакового разряда третьего вычитателя 7, выход коммутатора 8 остатка соединен с шиной 16 11 разрядов остатка, вход счетчика 10 коррекции цифр частного соединен с выходом шифратора 2, а его управляющий вход соединен через элемент НЕ 9 с выходом 17 знакового раз ряда третьего вычитателя 7, выход счет чика 10 коррекции частного соединен с шиной 18 К цифр. В устройстве счетчик 1принудительного округления делителя производит прибавление к ( К +2) старшим разрядам делителя единицы к их младшему разряду. Шифратор 2 осуществляет деление ( К +2) старших разрядов делимого на принудительно округленные ( VS-(-2) старших разрядов делителя. С помощью узлов 3 умножения и сумматора 4 формируется (h-t-K ) - разрядное произведение -разрядного делителя на К -разрядное частное, полученное на выходе шифратора 2. В каждом узле 3 умножения осуществляется умножение К разркдов частного, полученных на выходе шифратора 2, на соответствующие К разря дов делителя с учетом весовой позиции 2-К -разрядного произведения. В предлагаемом устройстве предполагается, что все узлы 7 умножения, подобно шифратору 2, вьтолневы в виде логических шифраторов К -разрядных кодов сомнож55 телей в 2-К -разрядный код их произведения. Следует особо отметить, что в определенных случаях с целью сокращения оборудования и обеспечения регулярности структуры шифратора 2 и узла 3 умножения целесообразна реализация шифратора 2 в виде матрицы взаимосвязанных сумматс ов-вычитателей, а узлов 3 умножения - в виде матрицы взаимосвязанных сумматоров. Здесь также предполагается что во всех вычитлтелях и сумматоре ис пользуются пегш ускоренного формирования заема и переноса. Коммутатор 8 остатка может быть реализован на элементех И-ИЛ И. Устройство работает следующим образом. По шинам 14 и 12 поступают в прямом коде без знака П -разрядные дели мое и делитель (аля определенности пред полагается, что система счисления двоич ная), В счетчике 1 принудительного окру ления делителя производится добавление К ( К +2) старшим раэрадам делителя единицы в их младший разряд. Этим самым устраняется возможность получения в шифраторе 6, в котором производится деление (Н +2) старших разрядов делимо го на (К +2) разряда делителя, частного с избытком на выходе узла принудительного округления. Можно показать, что абсолютная погрешность (разность между значением частного, получаемого при делении П -разрядных чисел и значением частного, получаемого при делении усеченных (Kf2) - разрядных чисел) при этом будет заключена в пределах 0.2- . Действительно, пусть X -значение делимого, поступающего на вход шины 14 устройства; у -значение делителя, посту пающего на входы шины 12 устройства; Х - значение старших ( ) делимого, поступающих на вход делимого шифратора генерации К цифр псевдочастш) го; У, -значение старших ( К +2) разр дов делителя, поступающих на ёхоц счетчика принудительного округления; Покажем, что ) .Здесь предполагается,что ; и . Выполнение левого условия, очевидно, поэтому ограничимся лишь доказательством неравенства: XX. j( 5 ) , которое можно перелисать в виде X-( y( X у 2 Нетрудно заметить, ч-го максимальная абсолютная погрешность в том случае, когда -(K-tz) .„ (.);v2 -1 иV-V-V О f( С учетом этого получим )-.( Х-2 (v,()y, можно привести оследнее соотношение виду - y..lS(y,.. оторое вьтолняется при всех значениях V , заключенных в пределах то и требовалось доказать. Но тогда начение К - разрядного частного, получаемого при делении усеченных чисел, моет быть либо равно значению старших К разрядов частного, получаемых при делении К. - разрядных чисел, либо меньше его на единицу младшего разряда с весом 2 (в(дальнейшем .будем говорить соответственно о точном и неточном значениях К - разрядного частного на выходе шифратора генерации К цифр частного). С помощью узлов 3 умножения и сумматора 4 формируется ( П + К ) - разрядное произведение п -разрядного , делителя на К -разрядное частное, полученное на выходе шифратора 2 генерации К цифр псевдочастного. С помощью второго и третьего вычитателей 6 и 7 производится вычитание из п -разрядного делимого г -разрядного целителя, сдвинутого на К разрядов в сторону младших разрядов, а также ( п + К) - разрядного произведения, полученного на вьн ходе сумматора 4. Если получившаяся при этом разность положительна, то это означает, что сформированное шифратором 2 К -разрядное частное неточное и его необходимо скорректировать в счет чике 1О коррекции частного путем добавления единицы в его млацший разряд. Коммутатор 8 остатка в этом случае соединяет выхоа г млацшнх разрядов третьего вьгчитателя 7 с шиной 16 п 7,73 разрядов остатка. Если же получившаяся на выходе третьего вычитателя 7 разность отрицательна, то в ши((раторе 2 генерации К частного получено точное значение К -разрядного частного, не тре бующее дополнительной коррекции в счет чике 10 цифр частного. Коммутатор 8 остатка в, этом случае соединяет выход П младших разрядов первого вычита , теля 5, в котором сформирована разность делимого и ( )-разрядного произведе ния, полученного на выходе сумматора 4, с шиной 16 п разрядов остатка. Ниже рассматривается пример, поясняющий принцип работы и структурные особенности устройства для деления п разрядных чисел .(для определенности выбр,аны Г) 12 и 4). Пусть х lOlOOlllllll; V 101010000600. Значение К цифр частного при делении X на V равно 2 , 1111, значение получившегося при этом остатка Z 0000101001110000. Вычислительный процесс определения остатка и четырех цифр частного в этом случае организован следующим образом. В счетчик 1 п(1инудительного округле ния делителя формируется результат а ,10101О-Ю,000001 0,101011, в шифраторе 2 генерации че тырех цифр частного формируется 4 разрядное частное Z,,101001: :ОД01011 0,1И1 , с помощью узлов 3 умножения и сум матора 4 формируется 16-разрядное про изведениеЬ У%: -О.1ОО111011ООООО в вычитателе 6 формируется разность C,-X-V- O,10O1110l011100dO, в вы читателе 7 формируется разность С„-С,-Ь -0,0000000000010000, в вь читателе S формируется разность 0,0000101001110000. Так как полученная на выходе третье го вычитателя 7 разность отрицательна то сформированное в шифраторе 2 4--раз рядное частное t. точное и не требуется дополнительная коррекция, а сформированная в вычитателе 5 разность С л Является остатком Z Рассмотренное устройство используется для формирования п -разрядного част ного-аа п/к тактов, а также при пост роении матричных (однотактных) устройст деления. Оно позволяет сократить время формирования остатка и К ЦИФР частно8го .(К , в сравнении с известным устройством примерно в К раз. Формулу изобретения Устройство для деления П--разрядных чисел, содержащее шифратор, первый Ьычитатель, вход уменьшаемого которого подключен к шине делимого, соединенной со входом шифратора отлич.ающ е е С я ,, тем,- {то, с целью повышения быстродействия, в него введены п/к -разрядных ( ) узлов умножения, ( п л п ) - разрядный сумматор, второй и третий вычитатели, п -разрядный коммутатор остатка, элемент НЕ, счетчик коррекции частного, при этом входы счетчика соединены с шиной (К+2) старших разрядов делителя, а выход соединен со входом шифратора, выход котоРОГО соединен с первыми входами узлов умножения, вторые входы которых соединены соответствующей группой К- разрядов делителя, выход узлов умножения соединен с соответствующей группой входом сумматора, бход уменьшаемого второго вычитателя соединен с шиной делимого, а вход вычитаемого второго вычитателя .соединен с шиной делителя, вход уменьшаемого третьего вычитателя соединен с выходом второго вычитателя, а вход вычитаемого первого вычитателя и вход вычитаемого третьего вычитателя соединены с выходом сумматора, входы коммутатора- остатка соединены с выхоДами п -младших разрядов первого и третьего вычитателей. а его управляющий ™° соединен с выходом знакового разряда третьего вычитателя, выход коммутатора остатка соединен с шиной п -разрядов остатка, вход коррекции частного соединен с выходом шифратора, а управляющий вход соединен через элемент НЕ с выходом знакового разряда . третьего вычитателя, выход счетчика кор рекции частного соединен с шиной частного. Источники информации, принятые во внимание при экспертизе 1.Карцев Н. А. Арифметика цифровь.л машин. М. , 1969, с. 494, РИС. 5,1а. 2.Папернов А. А. Логические основы UBT. М., 1972, с. 247, РИС. 5. 3.Патент США- J 3234367, . 235-176, 1968 (прототип).

4t

fZ

Л