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

Изобретение относится к области вычислительной техники и может быть использовано при разработке быстродействующих устройств деления чисел с контролер по четности. :- :;: . CV ...-.- ., .

Известно устройство для деления, содержащее п n-разрядн.ых сумматоров (п - четное число), образующих однотактный:- матричный делитель без восстановления остатков. ,

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

Наиболее близким по технической сущ-1 ности к предлагаемому изобретению является устройство для деления, содержащее п n-разрядных сумматоров (п - четное число), четыре блока свертки по модулю два и двй элемента сравнения, причем первый вход первого сумматора соединен с входом старших разрядов делимого устройства, первый вход j-ro сумматора 0 2,3, 4,..., п) соединен с выходом (п-1) младших разрядов Ьуммы (Н)то сумматора и с входом 0-1)-го Младшего разряда делимого устройства, вторые ёход ы всех сумматоров соединены С входом делителя устройства, вход пере- носа.}-го сумматора соединен с выходом суммы старшего разряда (Н)-го сумматора и б выходом соответствующего разряда частного устройства, вход переноса первого сумматора соединен с входом логической единицы устройства, выход пёрёйбс а из старшего разряда h-ro сумматора соединен с выходом п-го разряда частного устройства, выход суммы п-го сумматора соединен гс выходом остатка устройства, вход четно-. сти делимого устройства; соединен сТтёр&ым входом первого блока свёртки по модулю два, второй вход которого соединен с выходом переносов из (п-1) младших разрядов всех сумматоров, выхоД первого блока свёртки по модулю Два соединен с первым входом первого элемента сравнения, вто- рОй которого соединен с выходом вто; блока Свертки по модулю два и выходом чётности остатка устройства, вход второго блока свертки по модулю две среди 1 нё н с выходом остатка устройства, вход дё лйтёля устройства соединен & входом третьего.блока свертки по модулю два, выход Которого соединен с первым входом второго элемента сравнений, второй вход которого соединен с входом четности Делителя устройства, выходы двух элементов сравнения соединены с выходом признака

ошибки устройства, выход частного устройства соединен с входом четвертого блока свёртки по модулю два, выход которого соединен с выходом четности частногоустрой ства. .;. / л..:. Ч:,::---... л-.--.;:.--:.-л. л . ,. Зтб устройство обеспечивает высокую достоверность формируемых в нем результатов благодаря наличию в нем встроенных средств контроля по четности.

0 Недостатком известного устройства является недостаточно высокое быстродействие, обусловленное тем, что формирование цифр частного производится по знаковым разрядам остатков,

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

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

5 элемента сравнения, причем первый вход первого сумматора соединён с входом старших разрядов делимого устройства, первый вход J-ro сумматора 0 - 2,3.4,.... п) соединён с выходом (п-1) младших разрядов суммы

0 Н)т° сумматора и с входом Ш-. |)-го шего разряда делимого устройства, вторые входы всех сумматоров соединены с . входом делителя устройства, вход переноса первого суммётора соединен с входом

5. логической единицы устройства, выход переноса йэi старшего разряда п-го суммато- ; ра соединен с выходом ri-rq разряда частного устройства, выход суммы п-го сумматора соёдиМён с вЙхрдОм остатка устрой- J

0 ства, вход четности делимого устройства

соединен с первым входом первого блока

свертки по модулю два, второй, вход которого

соединен с выходом переносов из (п-1)

младших разрядов всех :сумматррое, выход

5 первого блока Свертки по модули два соединен с первым входом первого элемента сравнения, вход второго блока свертки по модулк) два соединен с выходом-остатка устройства, выход.второго блока свертки по

0 модулю два соединен с выходом четности остатка устройства, вход делителя устройстv BS сЬёдинен с входом третьего блока свертs ки по модулю два, выход которого соединен

ё первым входом второго элемента сравне5 ния, второй вход кото|з6го соединен с входом четности делителя устройства, выходы двух элементов сравнения соединены с выходом признака ошибки устройства, первый вход четвертого блока свертки по ЛиоДулю два соединен с выходом переноса

из старшего разряда n-го сумматора, выход четвертого блока свертки по модулю два соединен с выходом четности частного устройства, введены пятый и шестой блоки свертки по модулю два, причем вход пятого блока свертки по модулю два соединен с выходом переноса из старших разрядов сумматоров с первого по (п-1)-й и с выходом частного устройства, вход переноса j-ro сумматора соединен с выходом переноса из старшего разряда 0-1)го сумматора, третий вход первого блока свертки по модулю два соединен с входом логической единицы устройства, а четвертый вход - с вторым входом четвертого бока свертки по модулю два и с выходом пятого блока свертки по модулю два, второй вход первого элемента сравнения соединен с выходом шестого блока свертки по модулю два, первый вход которого соединен с выходом второго блока свертки по модулю два, а второй вход - с выходом сумм старших разрядов сумматоров с первого по (п-1)-й.

Совокупность перечисленных ниже признаков позволяет значительно увеличить быстродействие устройства с сохранением высокой достоверности получаемых в нем результатов:

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

2.Вход переноса j-ro сумматора соединен с выходом переноса из старшего разряда Q-1)-ro сумматора.

3.Пятый блок свертки по модулю два. вход-которого соединен с выходом переносов из старших разрядов сумматоров с первого по (п-1)-й.

А. Шестой блок свертки по модулю два, первый вход которого соединен с выходом второго блока свертки по модулю два, а второй вход - с выходом сумм старших разрядов сумматоров с первого по (п-1)-й.

На фиг. 1 приведена структурная схема предлагаемого устройства для деления; на фиг. 2 для п 4 показана реализация устройства в виде итеративной сети без аппаратуры контроля; на фиг. 3 - функциональная схема ячейки итеративной сети; на фиг. 4 - два примера, поясняющие деление чисел в исправном и неисправном устройстве на фиг. 2.

Устройство для деления (фиг. 1) содержит п n-разрядных сумматоров (п - четное число) 1i-1n блоки 2-7 свертки по модулю два с первого по шестой соответственно, первый 8 и второй 9 элементы сравнения.

вход 10i старших разрядов делимого устройства, вход 10а младших разрядов делимого устройства, вход 11 делителя устройства, вход 12 логической единицы ус- 5 тройства, вход 13 четности делимого устройства, вход 14 четности делителя устройства, оыход 15 частного устройства, выход 1 б четности частного устройства, выход Постатка устройства, выход 18 четности остатка уст- 10 ройства, выход 19 признака ошибки устройства, выходы 20i-20n (n-1) младших разрядов суммы сумматоров 1i-1n соответственно, выходы 21-|-21п старшего разряда Суммы сумматоров 1i-1n соответственно, 15 выходы переносов из (п-1) младших разрядов сумматоров 11-1 п соответственно, выходы переноса из старшего разряда сумматоров ti-1n соответственно.

Первый вход сумматора 1i соединен с 0 входом Ют старших разрядов делимого устройства, первый вход сумматора 1j (j 2, 3, 4,.... п) соединен с выходом 20j-i (n-1) младших разрядов суммы сумматора 1j-i и с входом (Н) го разряда входа 102 младших 5 разрядов делимого устройства, вторые входы сумматоров 11-1 п соединены с входом 11 делитбля устройства, вход переноса сумматора 1i соединен с входом 12 логической единицы устройства, вход переноса сумма- 0 тора 1j соединен с выходом 23j-i переноса из старшего разряда сумматора 1j-i, с выходом (И)-го разряда выхода 15 частного устройства и с входом пятого блока 6 свертки по модулю два, выход 23п переноса из стар- 5 шего разряда сумматора 1п соединен с выходом n-го разряда выхода 15 частного устройства и с первым входом четвертого блока 5 свертки по модулю два, второй вход которого соединен с выходом пятого 0 блока 6 свертки по модулю два, выход четвертого блока 5 свертки по модулю два соединен с выходом 16 четности частного устройства, первый вход первого блока 2 свертки по модулю два соединен с входом 5 13 четности делимого устройства, второй вход - с выходами 22i-22n переносов из (п-1) младших разрядов сумматоров 1i-1n, третий вход - с входом 12 логической единицы устройства, четвертый вход - с выхо- 0 дом пятого блока б свертки по модулю два, выход первого блока 2 свертки по модулю два соединен с первым входом первого элемента 8 сравнения, второй вход которого соединен с выходом шестого блока 7 сверт- 5 ки по модулю два. первый вход которого соединен с выходом второго блока 3 свертки по модулю два и выходом 18 четности остатка устройства, второй вход шестого блока 7 свертки по модулю два соединен с выходами 21i-21n-i сумм старших разрядов

сумматоров 1i-1n-t. вход второго блока 3 свертки по модулю два соединен с выходом суммы сумматора 1п и выходом 17 остатка устройства, вход третьего блока 4 свертки по модулю два соединен с входом 11 делителя устройства, выход которого соединен с первым входом второго элемента 9 сравнения, второй вход которого соединен с входом 14 четности делителя устройства, выход элементов 8 и 9 соединены с выходом 19 признака ошибки устройства.

Рассмотрим назначение и реализацию узлов и блоков устройства.

Сумматоры 1i-1n n-разрядные двоичные сумматоры комбинационного типа. Соединены они между собой, с входами и выходами устройства таким образом, что образуют однотактный матричный делитель/реализующий способ деления без восстановления остатков. В зависимости от значения управляющего сигнала на входе переноса сумматора информация, подаваемая на его второй вход с входа 11 делителя устройства, либо инвертируется (если значение предыдущего остатка положительное), либо проходит без изменения (если значение предыдущего остатка отрицательное). Одновременно с инвертированием информации на вход переноса сумматора подается сигнал логической единицы. Этим обеспечивается подача делителя в дополнительном коде. Таким образом, каждый сумматор 1i-1n является сумматором с управляемым инвертором на втором входе. Перенос в нем может быть организован любым способом.

На фиг. 2 для п 4 показана реализация однотактного матричного делителя без восстановления остатков (на фг. 1 он образован сумматорами 1i-1n с соответствующими связями) в виде итеративной сети, В ней осуществляется деление делимого X - 0,Х 1X2X3X4X5X5 на делитель Y 0,YiY2Y3, в результате которого получается частное Z Zo.ZiZ2Z3 и сдвинутый на три разряда влево остаток R Ro,RiR2R3 (истинный остаток равен R/8).

В сети используются ячейки 24 одного типа. Ячейки 24 (фиг. 3) содержит элемент 25 сложения по модулю два и одноразрядный двоичный сумматор26. Если в качестве сумматора 26 использовать одноразрядный двоичный сумматор с функциональной зависимостью суммы от переноса, то в предлагаемом устройстве для деления аппаратурой контроля по четности будут обнаруживаться все ошибки результата, вызываемые одиночной неисправностью устройства или одиночной ошибкой во входных данных. Следует отметить, что крайние

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

Функционирование одноразрядного сумматора 26 описывается следую щи ми-логическими выражениями:

Ci GI + TiCi-и;

Sif - fi©Ci AiBiCi+iCTi + dn) ©Ci, где Ci и Sif - перенос и сумма сумматора соответственно;

GI AiBi, Ti Ai + Bi - функции генерации и транзита переноса соответственно;

AI, BI, Сн-1 - разрядные слагаемые сумматора.

Первый блок 2 свертки по модулю два предназначен для формирования значения в соответствии с выражением:

Р2 - Рх© § Prtt ©1© g Скст,

l-мдKt i

где Рх - четность делимого;

четность переносов из (п-1) младших разрядов k-ro сумматора;

§ - знак суммирования по модулю

два;

Скст - перенос из старшего разряда k-ro сумматора.

Второй блок 3 свертки по модулю два формирует значение фактической четности остатка устройства PR. .

Третий блок 4 свертки по модулю два

вместе со вторым элементом 9 сравнения

осуществляет проверку правильности поступления делителя на вход 11 устройства и

на вторые входы всех сумматоров ,

Четвертый блок 5 свертки по модулю два формирует значение PZ - четности част- х ного устройства.

Пятый блок 6 свертки по модулю два формирует значение Ре четности переносов из старших разрядов сумматоров 1i-1n-i Pe lVcr..

к 1

Шестой блок 7 свертки по модулю два формирует значение

Р7,

55

)nsVCT,

к - 1

где 5кст - сумма старшего разряда k-ro сумматора.

На первом элементе 8-сравнения осуществляется проверка равенства

РхФ Л Р

к 1

n-1 v

PR© I SKCT. к 1

В случае нарушения этого равенства на выходе 19 устройства вырабатывается сигнал ошибки.

Устройство работает следующим образом. После подачи делимого на входы 10i и 102 и делителя на вход 11 устройства в нем начинается вычислительный процесс определении частного и остатка по способу без восстановления остатков. После завершения в устройстве переходного процесса на его выходах 15 и 17 формируются соответственно частное и остаток. Одновременно с выполнением в устройстве деления чисел, возникающие на выходах 22i-22n сумматоров 11-1 n переносы поступают на вход первого блока 2 свертки по модулю два, на который подаются также четность делимого со входа 13 устройства, логическая единица со входа 12 устройства и с выхода пятого блока 6 свертки по модулю два значение четности переносов из старших разрядов сумматоров . Таким образом, на выходе первого блока 2 свертки по модулю два будет сформировано значение

Р2-Рх©1Рс&„

к 1

nsVc,

к - 1

Второй блок 3 свертки по модулю два формирует значение четности остатка PR, которое поступает на выход 18 четности остатка устройства и на первый вход шестого блока 7 свертки по модулю два, на второй вход которого поступают значения сумм старших разрядов сумматоров 1i-1n-i. Таким образом, на выходе шестого блока 7 свертки по модулю два получим значение

Рт

На втором элементе 8 сравнения осуществляется сравнение значений, сформированных первым и шестым блоками свертки по модулю два:

Рх© Е РС&Л €М©П1 Скст- к 1к 1

PR® Ё1 Зкст.

к 1

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

Таким образом, блоки 2, 3, 6 и 7 свертки по модулю два и первый элемент 8 сравне- 5 ния осуществляют контроль по четности правильности выполнения операции деления.

Четвертый блок 5 свертки по модулю два формирует значение четности частно0 го.

Третий блок 4 свертки по модулю два и второй элемент 9 сравнения осуществляет контроль по четности поступления делителя на вход 11 устройства и на вторые входы

5 сумматоров 1i-1n.

Если сумматоры построены на основе одноразрядных двоичных сумматоров с функциональной зависимостью суммы от переноса, то при появлении одиночной не0 исправности в устройстве, приводящей к искажению результата на выходах 15 и 17 устройства, приведенное выше равенство будет нарушено и, таким образом, будут обнаружены все возникшие ошибки на выхо 5 дах 15 и 17 частного и остатка устройства. Схемы контроля обнаруживают также все ошибки результата, вызываемые одиночной ошибкой в делимом на входах 10i и 102 устройства. Для обнаружения одиночных

0 ошибок в делителе, которые могут привести к необнарум иваемому классу ошибок в работе устройства, предусмотрен контроль по четности поступления делителя на вход 11 устройства и на вторые входы сумматоров

5 1i-1n с помощью третьего блока 4 свертки по модулю два и второго элемента 9 сравнения.

На фиг. 4 приведены два числовых примера, подтверждающие правильность функ0 ционирования предлагаемого устройства для деления с контролем. Примеры ра смот- рены применительно к итеративной сети, изображенной на фиг. 2 в предположении, что делимое X 0,100101, делитель Y

5 0,101. В случае правильного деления на выходе 15 устройства формируется частное Z 0,111, на выходе 17 устройства - сдвинутый на три разряда влево остаток R 0,010 (истинный остаток равен 0,000010).

0 На фиг. 4, а поясняетсяделение чисел в исправном устройстве, а на фиг. 4, б - в неисправном, Предполагается, что неисправность устройства обусловлена наличием контактного нуля на выходе суммы сумма5 тора 26 (фиг. 3) ячейки 24, заштрихованной на фиг. 2, Точка на фиг. 4 указывает на образование переноса в сумматоре, значение которого равно единице и которое учитывается при проверке контрольного соотношения.

Произведем сравнение времен выполнения операции деления в предлагаемом устройстве и в устройстве-прототипе.

В устройстве-прототипе цифры частного формируются по инверсным значениям сумм старших разрядов сумматоров и управление инвертированием делителя в J- м сумматоре осуществляется инверсным значением суммы старшего разряда (И)г° сумматора. Поэтому (применительно к итеративной сети прототипа) время деления чисел

То 4(3г + 3т+22тч 6г)64г

В предлагаемом устройстве цифры частного формируются по переносам из старших разрядов сумматоров 1i-1n и управление инвертированием делителя в j-м сумматоре тоже осуществляется переносом из старшего разряда (ННо сумматора. Поэтому (применительно к итеративной сети время деления чисел

То 4 (3 г + 3 г+ 2 2 г + 2 т) 48 г.

Сравнивая времена выполнения операции, получим, что s предлагаемом устройстве быстродействие увеличилось примерно на 25%.

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

Формула изобретения Устройство для деления, содержащее п n-разрядных сумматоров (п - четное число), четыре блока свертки по модулю два и два элемента сравнения, причем первый вход первого сумматора соединен с входом старших разрядов делимого устройства, первый вход j-ro сумматора ( 2, 3, 4 п)

соединен с выходом (п-1)-х младших разрядов суммы (Н)-го сумматора и с входом (J-1)-ro младшего разряда делимого устройства, вторые входы всех сумматоров соединены с входом делителя устройства, вход переноса первого сумматора соединен

с входом логической единицы устройства, выход переноса из старшего разряда п-го сумматора соединен с выходом n-го разряда частного устройства, выход суммы n-го сумматора соединен с выходом остатка устройства, вход четности делимого устройства соединен с первым входом первого блока свертки по модулю два, второй вход которого соединен с выходом переносов из (п-1)-х

младших разрядов всех сумматоров, выход первого блока свертки по модулю два соединен с первым входом первого элемента сравнения, вход второго блока свертки по модулю два соединен с выходом остатка

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

с первым входом второго элемента сравнения, второй вход которого соединен с входом четности делителя устройства, выходы двух элементов сравнения соединены с выходом признака ошибки устройства, первый вход четвертого блока свертки по модулю двёгсоединен с выходом переноса из старшего разряда n-го сумматора, выход четвертого блока свертки по модулю два соединен с выходом четности частного

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

выходом переноса из старших разрядов сумматоров с первого по (п-1)-й и с выходом частного устройства, вход переноса j-ro сумматора соединен с выходом переноса из Старшего разряда (НКо сумматора, третий

вход первого блока свертки по модулю два соединен с входом логической единицы устройства, а четвертый вход - с вторым входом четвертого блока свертки по модулю два и выходом пятого блока свертки по модулю два, второй вход первого элемента сравнения соединен с выходом шестого блока свертки по модулю два, первый вход которого соединен с выходом второго блока свертки по модулю два, а второй вход - с

выходом сумм старших разрядов сумматоров с первого по (п-1)-й.

Фиг. 2

2.5

Изобретение относится к вычислительной технике и может быть использовано при разработке быстродействующих устройств для деления чисел с контролем по четности. Целью изобретения является повышение быстродействия устройства. Устройство содержит п n-разрядных сумматоров 1 i-1n(n - четное число), четыре блока 2-5 свертки по модулю два, два элемента 8. 9 сравнения и нововведенные пятый и шестой блоки 6, 7 свертки по модулю два. 4 ил. 11(702 -ч 00 N о Ч /3

&.::

а)

&е|Јв Ф5Ј Р,Ф| 5

W « . « Г

я

. о 1 о о { о

ULLJ 1

ОТО О

yw

/ Р„ Ф Jp,, Хй, 4 СД к m 9

16

ч

Фиг.

а /