Результат интеллектуальной деятельности: Параллельный сумматор

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

Известен сумматор с последовательным переносом, содержащий объединенные в цепь N полные одноразрядные сумматоры (рис. 5.5, стр. 604. Дэвид М. Хэррис и Сара Л. Хэррис. Цифровая схемотехника и архитектура компьютера. Второе издание. Издательство Morgan Kaufman. English Edition, 2013). Сумматор позволяет выполнять параллельное суммирование двух n-разрядных чисел.

Недостатком данного сумматора является то, что скорость его суммирования падает при увеличении числа N.

Наиболее близким по технической сущности к заявляемому изобретению является сумматор с условным переносом (рис. 2.32, стр. 88-89. Угрюмов Е.П. Цифровая схемотехника. - СПб.: БХВ - Петербург, 2004. - 528 с.), содержащий три параллельных n/2-разрядных сумматора, один n/2-разрядный двухвходовый мультиплексор и один одноразрядный двухвходовый мультиплексор. Сумматор позволяет выполнять параллельное суммирование двух n - разрядных чисел.

Недостатком данного сумматора является большой объем оборудования.

Техническим результатом данного изобретения является сокращение объема оборудования и, как следствие, уменьшение энергопотребления за счет исключения одного n/2-разрядного двухвходового мультиплексора, одного одноразрядного двухвходового мультиплексора, одного n/2-разрядного сумматора и введения одного (n/2+1)-разрядного полусумматора.

Для достижения технического результата в параллельный сумматор, содержащий два n/2-разрядных сумматора, причем первые информационные входы первого n/2-разрядного сумматора являются входами младших разрядов первого слагаемого, вторые информационные входы являются входами младших разрядов второго слагаемого, вход переноса является входом переноса параллельного сумматора, а информационные выходы являются выходами младших разрядов суммы параллельного сумматора, первые информационные входы второго n/2-разрядного сумматора являются входами старших разрядов первого слагаемого, вторые информационные входы являются входами старших разрядов второго слагаемого, а на вход переноса подается логический «0», введен (n/2+1)-разрядный полусумматор, второй информационный вход которого соединен с выходом переноса первого n/2-разрядного сумматора, младшие n/2 первые информационные входы соединены с информационными выходами второго n/2-разрядного сумматора, (n/2+1)-й первый информационный вход соединен с выходом переноса второго n/2-разрядного сумматора, младшие n/2 информационные выходы являются выходами старших разрядов суммы параллельного сумматора, а (n/2+1)-й информационный выход является выходом переноса параллельного сумматора.

Сущность изобретения заключается в реализации следующего способа суммирования n - разрядных чисел А и В.

Имея n-разрядный сумматор, делят его на 2 равные n/2-разрядные группы. На первом n/2-разрядном сумматоре суммируют младшие с 1 по n/2 разряды слагаемых А_мл и В_мл, на втором n/2-разрядном сумматоре суммируют старшие поля операндов А_ст и B_ст при условии, что перенос на C_in2 на втором n/2-разрядном сумматоре равен «0». После получения результата в первом n/2-разрядном сумматоре становится известным фактическое значение переноса во второй n/2-разрядный сумматор. К этому моменту времени становится также известен результат во втором n/2-разрядном сумматоре. Используя (n/2+1)-разрядный полусумматор, суммируют значение переноса с результатом второго n/2-разрядного сумматора. В итоге получают окончательное значение старших разрядов суммы.

На фиг. 1 представлена схема параллельного сумматора.

Параллельный сумматор содержит два n/2-разрядных сумматора 1 и 2, (n/2+1)-разрядный полусумматор 3, информационные входы 4 первого слагаемого А, разделенные на младшие разряды А_мл с А₁ по А_n/2 и старшие разряды A_ст с А_n/2+1 по А_n, информационные входы 5 второго слагаемого В, также разделенные на младшие разряды В_мл с В₁ по В_n/2 и старшие разряды В_ст с В_n/2+1 по В_n, первый вход 6 переноса C_in1, второй вход переноса 7 C_in2, выход 8 суммы S, выход 9 переноса С_out. Первые информационные входы первого n/2-разрядного сумматора 1 являются информационными входами 4 младших разрядов первого слагаемого А_мл, вторые информационные входы являются информационными входами 5 младших разрядов второго слагаемого В_мл, вход переноса является первым входом 6 переноса С_in1 параллельного сумматора, а информационные выходы являются выходами 8 младших разрядов суммы S_мл параллельного сумматора, первые информационные входы второго n/2-разрядного сумматора 2 являются информационными входами 4 старших разрядов А_ст первого слагаемого, вторые информационные входы являются информационными входами 5 старших разрядов В_ст второго слагаемого, а на второй вход 7 переноса C_in2 подается логический «0», второй информационный вход (n/2+1)-разрядного полусумматора 3 соединен с выходом переноса первого n/2-разрядного сумматора 1, младшие n/2 первые информационные входы соединены с информационными выходами второго n/2-разрядного сумматора 2, (n/2+1)-й первый информационный вход соединен с выходом переноса второго n/2-разрядного сумматора 2, младшие n/2 информационные выходы являются выходами 8 старших разрядов суммы S_ст параллельного сумматора, а (n/2+1)-й информационный выход является выходом 9 переноса С_out параллельного сумматора.

Параллельный сумматор работает следующим образом.

Первое А и второе В n-разрядные слагаемые разделяют на n/2 младшие (A₁ … A_n/2) (В₁ … В_n/2) и n/2 старшие (А_n/2+1 … А_n), (В_n/2+1 … В_n) разряды. Первое слагаемое поступает на информационный вход 4, а второе слагаемое поступает на информационный вход 5 параллельного сумматора. На первый вход 6 переноса C_in1 параллельного сумматора при увеличении разрядности суммируемых чисел может подаваться сигнал переноса. Младшие разряды первого (А₁ … А_n/2) и второго (В₁ … В_n/2) слагаемых суммируются в первом n/2-разрядном сумматоре 1. Одновременно старшие разряды первого (А_n/2+1 … А_n) и второго (В_n/2+1 … В_n) слагаемых суммируются во втором n/2-разрядном сумматоре 2, на второй вход 7 переноса которого подается сигнал логического «0». На выходах 8 суммы (S₁ … S_n/2) первого n/2-разрядного сумматора 1 образуются младшие разряды суммы S. Сигнал переноса с выхода переноса Р_o первого n/2-разрядного сумматора 1 суммируется с промежуточными результатами суммы старших разрядов, образующихся на выходе второго n/2-разрядного сумматора 2 в n/2+1-разрядном полусумматоре 3. В результате на (S₁ … S_n/2) информационных выходах n/2+1-разрядного полусумматора 3 образуется окончательная сумма старших разрядов, которая поступает на (S_n/2+1 … S_n) выходы 8 суммы S параллельного сумматора, а на S_n/2+1 информационном выходе n/2+1-разрядного полусумматора 3 образуется сигнал переноса C_out, который поступает на выход 9 переноса устройства.

Рассмотрим работу параллельного сумматора на конкретном примере.

Пусть разрядность слагаемых А и В n составляет 4 бита, пусть А=13₁₀=1101₂, В=7₁₀=0111₂. Тогда младшие разряды А_мл=01, B_мл=11, а старшие разряды А_ст=11, B_ст=01. На информационных выходах первого n/2-разрядного сумматора 1 образуются младшие разряды суммы S_мл=00, а на выходе переноса Р_о первого n/2-разрядного сумматора 1 образуется сигнал логической «1». На выходах второго n/2-разрядного сумматора 2 образуется сумма чисел А_ст и В_ст=11+01=00, а на его выходе переноса образуется сигнал логической «1». В результате в n/2+1-разрядном полусумматоре 3 осуществляется суммирование чисел 100+1=101. В итоге на выходе устройства образуется число S=10100₂=20₁₀. Суммирование выполнено корректно, поскольку 13+7=20.

Оценим эффективность предлагаемого устройства по сравнению с прототипом.

Одноразрядный полусумматор содержит 4 элементарных логических элемента, одноразрядный полный сумматор состоит из двух полусумматоров и дополнительного логического элемента, т.е. содержит 9 элементарных логических элементов (рис. 3.52, с. 274 и рис. 3.53, с. 276, Безуглов Д.А. Цифровые устройства и микропроцессоры / Д.А. Безуглов, И.В. Калиенко. - Изд. 2-е. - Ростов н/Д: Феникс, 2008. - 468 с.). Один мультиплексор содержит 3 элементарных логических элемента на один разряд и один логический элемент на всю схему (рис. 3.8 б, с. 104, Пухальский Г.И., Новосельцева Т.Я. Проектирование дискретных устройств на интегральных микросхемах: Справочник. - М.: Радио и связь. 1990. - 334 с.).

При построении сумматора n-разрядных чисел прототип будет содержать три n/2-разрядных сумматора по 9 элементарных логических элементов на разряд и два мультиплексора, один n/2-разрядный, а второй одноразрядный, соответственно, с 3n/2+1 и 4 элементарными логическими элементами на разряд. Итого прототип будет содержать 3⋅9n/2+3n/2+1+4=15n+5 элементарных логических элементов.

Предлагаемое техническое решение при построении сумматора n-разрядных чисел будет содержать два n/2-разрядных сумматора по 9 элементарных логических элементов на разряд и один (n/2+1)-разрядный полусумматор с 4 элементарными логическими элементами на разряд. Итого предлагаемое техническое решение будет содержать 2⋅9n/2+4(n/2+1)=9n+2n+4=11n+4 элементарных логических элементов.

Таким образом, предлагаемое техническое решение будет содержать на (15n+5)-(11n+4)=4n+1 элементарных логических элементов на один разряд меньше, чем прототип.