УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ Российский патент 1994 года по МПК G06F7/52 

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

Известно устройство для деления, построенное по однотактному принципу и содержащее mn-разрядных сумматоров m - нечетное число, n - четное число) [1] . В устройстве реализован способ деления чисел без восстановления остатков.

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

Наиболее близким по технической сущности к предлагаемому изобретению является устройство для деления, содержащее mn-разрядных сумматоров (m+n-1 - разрядность делимого, m - нечетное число, n - четное число), два элемента сравнения и четыре узла свертки по модулю два, причем первый вход первого сумматора соединен со старшими разрядами (с первого по n-й) входа делимого устройства, разряды выхода результата, кроме старшего, каждого j-го сумматора (1≅ j ≅ m-1) и (n+j)-й разряд входа делимого устройства соединены с соответствующими разрядами первого входа (j+1)-го сумматора, вторые входы всех сумматоров подключены к входу делителя устройства, старшие разряды выходов результата j-х сумматоров группы и выход переноса из старшего разряда m-го сумматора образуют группу выходов частного устройства, выход результата m-го сумматора является выходом остатка устройства, вход инвертирования первого сумматора подключен к входу логической единицы устройства, старший разряд выхода результата каждого j-го сумматора соединен с входом инвертирования (j+1)-го сумматора, входы контрольных разрядов делимого и делителя устройства, выходы внутренних межразрядных переносов всех сумматоров и вход логической единицы устройства соединены с соответствующими входами первого узла свертки по модулю два, выход результата m-го сумматора соединен с входом второго узла свертки по модулю два, вход третьего узла свертки по модулю два подключен к входу делителя устройства, группа выходов частного устройства соединена с группой входов четвертого узла свертки по модулю два, выходы второго и четвертого узлов свертки по модулю два являются соответственно выходами контрольных разрядов остатка и частного устройства, выходы первого и второго узлов свертки по модулю два соединены соответственно с первым и вторым входами первого элемента сравнения, первый и второй входы второго элемента сравнения соединены соответственно с входом контрольного разряда делителя устройства и выходом третьего узла свертки по модулю два, выходы первого и второго элементов сравнения образуют выход признака ошибки устройства [2].

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

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

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

Цель достигается тем, что в устройство для деления, содержащее mn-разрядных сумматоров (m+n-1-разрядность делимого, m - нечетное число, n - четное число), четыре узла свертки по модулю два и два элемента сравнения, причем первый вход первого сумматора соединен со старшими разрядами (с первого по n-й) входа делимого устройства, разряды выхода результата, кроме старшего, каждого j-го сумматора (1≅ j ≅ m -1) и (n+j)-й разряд входа делимого устройства соединены с соответствующими разрядами первого входа (j+1)-го сумматора, вторые входы всех сумматоров подключены к входу делителя устройства, выход результата m-го сумматора является выходом остатка устройства, входы контрольных разрядов делимого и делителя устройства, вход логической единицы устройства, выходы внутренних межразрядных переносов всех сумматоров соединены с соответствующими входами первого узла свертки по модулю два, выход которого соединен с первым входом первого элемента сравнения, вход второго узла свертки по модулю два соединен с выходом результата m-го сумматора, а выход подключен к выходу контрольного разряда остатка устройства, вход третьего узла свертки по модулю два соединен со входом делителя устройства, а выход - с первым входом второго элемента сравнения, второй вход которого соединен с входом контрольного разряда делителя устройства, выходы первого и второго элементов сравнения соединены с выходом признака ошибки устройства, вход инвертирования первого сумматора подключен к входу логической единицы устройства, введены два узла свертки по модулю два, причем выход переноса из старшего разряда j-го сумматора соединен с входом инвертирования (j+1)-го сумматора, выходы переносов из старших разрядов всех сумматоров образуют группу выходов частного устройства, выходы переносов из старших разрядов сумматоров с первого по (m-1)-й соединены с входом четвертого узла свертки по модулю два, выход которого соединен с пятым входом первого узла свертки по модулю два и с первым входом пятого узла свертки по модулю два, второй вход которого соединен с выходом переноса из старшего разряда m-го сумматора, а выход - с выходом контрольного разряда частного устройства, выходы старших разрядов результата сумматоров с первого по (m-1)-й соединены с первым входом шестого узла свертки по модулю два, второй вход которого соединен с выходом второго узла свертки по модулю два, а выход - со вторым входом первого элемента сравнения.

Заявляемое устройство содержит следующие отличительные признаки, не обнаруженные ни в одном другом из известных устройств:
1) пятый и шестой узлы свертки по модулю два;
2) выход переноса из старшего разряда каждого сумматора соединен с соответствующим разрядом выхода частного устройства, т.е. в устройстве формирование цифр частного осуществляется по переносам из старших разрядов сумматоров;
3) выход переноса из старшего разряда j-го сумматора соединен с входом инвертирования (j+1)-го сумматора;
4) выходы старших разрядов результатов сумматоров с первого по (m-1)-й соединены с первым входом шестого узла свертки по модулю два;
5) выход четвертого узла свертки по модулю два соединен с пятым входом первого узла свертки по модулю два.

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

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

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

Устройство для деления чисел (фиг.1) содержит mn-разрядных сумматоров (n+m-1 разрядность делимого, m - нечетное число, n - четное число) 1₁-1_m, узлы 2-7 свертки по модулю два с первого по шестой соответственно, первый 8 и второй 9 элементы сравнения, вход 10₁ n старших разрядов делимого устройства, вход 10₂ (m-1) младших разрядов делимого устройства, вход 11 - делителя устройства, вход 12 логической единицы устройства, вход 13 контрольного разряда делимого устройства, вход 14 контрольного разряда делителя устройства, выход 15 частного устройства, выход 16 контрольного разряда частного устройства, выход 17 остатка устройства, выход 18 контрольного разряда остатка устройства, выход 19 признака ошибки устройства, выходы 20₁-20_m (n-1) младших разрядов результата сумматоров 1₁-1_m соответственно, выходы 21₁-21_m старших разрядов результатов сумматоров 1₁-1_m соответственно, выходы 22₁-22_m внутренних межразрядных переносов сумматоров 1₁-1_m соответственно, выходы 23₁-23_m переносов из старших разрядов сумматоров 1₁-1_m соответственно.

Первый вход сумматора 1₁ соединен с входом 10₁ n старших разрядов делимого устройства, разряды выхода результата, кроме старшего, сумматора 1j (1≅j≅m-1) и (n+j)-й разряда входа делимого устройства (он подается на вход 10₂ устройства) соединены с соответствующими разрядами первого входа сумматора 1_j+1, вторые входы сумматоров 1₁-1_m подключены к входу 11 делителя устройства, выход результата (выходы 20_m и 21_m) сумматора 1_m является выходом 17 остатка устройства, входы 13, 14 контрольных разрядов соответственно делимого и делителя, вход 12 логической единицы устройства и выходы 22₁-22_m внутренних межразрядных переносов сумматоров 1₁-1_m соединены с соответствующими входами первого узла 2 свертки по модулю два, выход которого соединен с первым входом первого элемента сравнения, вход второго узла 3 свертки по модулю два соединен с выходом результата (выходы 20_m и 21_m) сумматора 1_m, а выход подключен к выходу 18 контрольного разряда остатка устройства, вход третьего узла 4 свертки по модулю два соединен с входом 11 делителя устройства, а выход - с первым входом второго элемента 9 сравнения, второй вход которого соединен с входом 14 контрольного разряда делителя устройства, выходы элементов 8, 9 сравнения соединены с выходом 19 признака ошибки устройства, вход инвертирования сумматора 11 соединен с входом 12 логической единицы устройства, выход 23_j переноса из старшего разряда сумматора 1_j соединен с входом инвертирования сумматора 1_j+1, выходы 23₁-23_m переносов из старших разрядов сумматоров 1₁-1_m образуют группу выходов 15 частного устройства, выходы 23₁-23_m-1 переносов из старших разрядов сумматоров 1₁-1_m-1 соединены с входом четвертого узла 5 свертки по модулю два, выход которого соединен с пятым входом первого узла 2 свертки по модулю два и с первым входом пятого узла 6 свертки по модулю два, второй вход которого соединен с выходом 23_m переноса из старшего разряда сумматора 1_m, а выход - с выходом 16 контрольного разряда частного устройства, выходы 21₁-21_m-1 старших разрядов результатов сумматоров 1₁-1_m-1 соединены с первым входом шестого узла 7 свертки по модулю два, второй вход которого соединен с выходом второго узла 3 свертки по модулю два, а выход - со вторым входом первого элемента 8 сравнения.

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

На фиг.2 для m=3 и n=4 показана реализация однотактного матричного делителя без восстановления остатков (на фиг.1 он образован сумматорами 1₁-1_m с соответствующими связями) в виде итеративной сети. В нем осуществляется деление делимого Х=Х_о,Х₁Х₂Х₃Х₄Х₅ на делитель Y=0,Y₁Y₂Y₃, в результате получается частное Z= Z₀; Z₁Z₂ и сдвинутый на два разряда влево остаток R= R_0,R₁R₂R₃ (истинный остаток равен Р/4). Предполагается, что делимое и делитель положительные числа, причем делитель 1/2≅Y≅1, делимое Х≅2Y.

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

Как и в устройстве-прототипе сумматор может быть реализован на трех элементах 2И, одном элементе 3И, трех элементах 2 ИЛИ, одном элементе НЕ и одном двухвходовом элементе сложения по модулю два.

Первый узел 2 свертки по модулю два формирует значение
P₂=P_x⊕ P_y⊕ 1⊕ P C^k, где Р_х,Р_y - контрольные разряды (четности)делимого и делителя соответственно;
Р_Сk - четность внутренних межразрядных переносов (переносов из (n-1) младших разрядов) К-ого сумматора;
- знак суммирования по модулю два;
С^k - значение переноса из старшего разряда (внешнего переноса) k-ого сумматора.

Второй узел 3 свертки по модулю два формирует значение контрольного разряда остатка устройства. Третий узел 4 свертки по модулю два формирует значение контрольного разряда делителя, поступившего на входы сумматоров 1₁-1_m и на вход 11 устройства. Четвертый узел 5 свертки по модулю два формирует значение четности переносов из старших разрядов сумматоров с первого по (m-1)-й. Пятый узел 6 свертки по модулю два формирует контрольный разряд частичного устройства.

Шестой узел 7 свертки по модулю два формирует значение
P₇ = S^k⊕ P_R, где S^k - значение суммы старшего разряда k-го сумматора;
Р_R - значение контрольного разряда остатка устройства.

Первый элемент 8 сравнения осуществляет проверку равенства
Р₂=Р₇, которое должно выполняться при правильном выполнении операции.

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

Устройство работает следующим образом. После подачи на входы 10₁ и 10₂ устройства делимого, а на вход 11 - делителя, в устройстве начинается вычислительный процесс определения частного и остатка по способу без восстановления остатков. После завершения в устройстве вычислительного процесса на его выходах 15 и 17 образуются частное и остаток соответственно, а на выходах 16 и 18 формируются значения контрольных разрядов частного и остатка соответственно. Одновременно с выполнением в устройстве операции деления чисел на выходах 22₁-22_m сумматоров 1₁-1_m образуются внутренние межразрядные переносы, которые поступают на вход первого узла 2 свертки по модулю два, на который подаются значения контрольных разрядов делимого, делителя и сигнал логической единицы с входов 13, 14 и 12 устройства соответственно. С выхода четвертого узла 5 свертки по модулю два на пятый вход узла 2 подается значение четности переносов из старших разрядов сумматоров с первого по (m-1)-й. Сформированное на втором узле 3 свертки по модулю два значение четности остатка Р₃ суммируется по модулю два на шестом узле 7 свертки по модулю два со значениями сумм старших разрядов сумматоров с первого по (m-1)-й. Значения, полученные на выходах узлов 2 и 7 свертки по модулю два, сравниваются между собой на первом элементе 8 сравнения. При несовпадении этих значений на выходе 19 устройства вырабатывается сигнал ошибки.

Если сумматоры 1₁-1_m построены на одноразрядных двоичных сумматорах с функциональной зависимостью суммы от переноса, то в предлагаемым устройстве аппаратурой контроля по четности будут обнаруживаться все ошибки результата, вызываемые одиночной неисправностью устройства. Обеспечивается также обнаружение всех ошибок, вызываемых одиночной ошибкой в делимом на входах 10₁ и 10₂ устройства. Для обнаружения одиночных ошибок в делителе, которые могут привести к необнаруживаемому классу ошибок в работе устройства, предусмотрен контроль по четности поступления делителя на вход 11 устройства и на входы сумматоров 1₁-1_m с помощью третьего узла 4 свертки по модулю два и второго элемента 9 сравнения.

На фиг. 4 приведены два числовых примера, подтверждающие правильность функционирования предлагаемого устройства для деления. Примеры рассмотрены применительно к итеративной сети, изображенной на фиг.2 в предположении, что делимое Х=1,00101, делитель Y=0,111. В случае правильного деления частное Z=1,01, сдвинутый на два разряда влево остаток R=0,010 (истинное значение остатка равно R=0,00010). На фиг.4,а поясняется деление чисел в исправном устройстве, на фиг.4,б - в неисправном. Предполагается, что неисправность устройства обусловлена наличием константной единицы на выходе переноса сумматора 26 ячейки 24, заштрихованной на фиг.2. Точка на фиг.4 указывает образование внутреннего межразрядного переноса, значение которого равно единице и который учитывается при предсказании четности остатка.

Знаком * обозначено образование единичного переноса из старшего разряда сумматора (внешнего переноса сумматора), который формирует единицу в соответствующем разряде частного.

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

В устройстве-прототипе [2] цифры частного формируются по инверсным значениям сумм старших разрядов сумматоров 1₁-1_m и управление инвертированием делителя в сумматорах осуществляется инверсным значением сумм старших разрядов соответствующих сумматоров. Поэтому применительно к итеративной сети на фиг.2 прототипа время деления чисел равно
Т_Д=3(3 τ +3 τ +2^.2 τ +6 τ)=48 τ .

В предлагаемом устройстве цифры частного формируются по переносам из старших разрядов сумматоров 1₁-1_m и управление инвертированием делителя в сумматорах осуществляется переносами из старших разрядов соответствующих сумматоров. Поэтому применительно к итеративной сети на фиг.2 время деления чисел равно
Т_Д=3(3 τ +3 τ +2^.2 τ +2 τ )=36 τ .

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

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

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

УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ, содержащее m n-разрядных сумматоров (n + m - 1 - разрядность делимого, m-нечетное число, n-четное число), четыре узла свертки по модулю два и два элемента сравнения, причем первый вход первого сумматора соединен с входом старших разрядов (с первого по n-й) делимого устройства, выход разрядов результата, кроме старшего, каждого j-го сумматора (1 ≅ j ≅ m - 1) и вход (n + j)-го разряда делимого устройства соединены с первым входом соответствующих разрядов (j + 1)-го сумматора, вторые входы всех сумматоров подключены к входу делителя устройства, выход результата m-го сумматора является выходом остатка устройства, входы контрольных разрядов делимого и делителя устройства, вход логической единицы устройства, выходы внутренних межразрядных переносов всех сумматоров соединены с соответствующими входами первого узла свертки по модулю два, выход которого соединен с первым входом первого элемента сравнения, вход второго узла свертки по модулю два соединен с выходом результата m-го сумматора, а выход второго узла свертки по модулю два подключен к выходу контрольного разряда остатка устройства, вход делителя которого соединен с входом третьего узла свертки по модулю два, выход которого соединен с первым входом второго элемента сравнения, второй вход которого соединен с входом контрольного разряда делителя устройства, выходы первого и второго элементов сравнения соединены с выходом признака ошибки устройства, вход инвертирования первого сумматора соединен с входом логической единицы устройства, отличающееся тем, что в устройство введены два узла свертки по модулю два, причем выход переноса из старшего разряда j-го сумматора соединен с входом инвертирования (j + 1)-го сумматора, выходы переносов из старших разрядов всех сумматоров образуют группу выходов частного устройства, выходы переносов из старших разрядов сумматоров с первого по (m - 1)-й соединены с входом четвертого узла свертки по модулю два, выход которого соединен с пятым входом первого узла свертки по модулю два и с первым входом пятого узла свертки по модулю два, второй вход которого соединен с выходом переноса из старшего разряда m-го сумматора, а выход пятого узла свертки по модулю два соединен с выходом контрольного разряда частного устройства, выходы старших разрядов результатов сумматоров с первого по (m - 1)й соединены с первым входом шестого узла свертки по модулю два, второй вход которого соединен с выходом второго узла свертки по модулю два, а выход шестого узла свертки по модулю два соединен с вторым входом первого элемента сравнения.