Устройство для суммирования м-чисел

(7 ) Одесский политехнический институт(56) Авторское свидетельство СССР У 1068932, кл. О 06 Г 7/50, 1981,Авторское свидетельство СССР1159013, кл. 0 06 Р 7/50, 1983.(57) Изобретение относится к в лительной технике и может быть пользовано в высокопроизводите ных вычислительных устройствах лью изобретения является повыш быстродействия, Цель достигает за счет введения в устройство, жащее в каждом разряде преобразо тель 1 двоичного кода в код колства единиц и сумматор 3 по модулюдва, дополнительно (И+К) элементов И-ИЛИ 2, где И - разрядностьслагаемых, К - количество входныхпереносов, а также новых связей.Данное устройство реализует парал 1545216лельный способ суммирования и по числам, и по разрядам, вырабатывая одновременно переносы во все разряды,5которые складываются на сумматорах по модулю два с поразрядными суммами. 5 ил.,5 табл.Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных вы 15числительных устройствах.Цельюизобретения является повышение быстродействия устройства длясуммирования М чисел.На фиг, 1 приведена структурнаясхема устройстваф на фиг. 2-5 - четырехразрядное устройство суммирования четырех чисел.Устройство для суммирования М чисел содержит преобразователи 1 двооичного кода в код количества единиц,элементы И-ИЛИ 2, сумматор 3 по модулк 1 два, входы 4 одноименных разрядов всех слагаемых, входы 5 переноса,выходы 6 суммы и выходы 7 переноса.Элементы И-ИЛИ образуют блок 8 формирования параллельных переносов Р-Ргде Б - разрядность слагаемых,На фиг2 показано, что с цельюоптимизации элементов И-ИЛИ выходыпреобразователей 1 могут быть объеди- З 5нены внутри преобразователя. Каждыйпреобразователь 1 имеет также выходнечетности кода, соединенный с вхо-,дом Б. соответствующего сумМатора по1 40модулю два.Устройство работает следующим образом.На входы преобразователей ходов(ПК) 1, х-го разряда (х = 1,И) поступают сигналы М слагаемых А, кроме того, на ПК 1 первых К разрядов поступают сигналы входных одноразрядныхпереносов Е . ПК 1 вырабатывает Ь .1сигналов симметрических Функций, об 50разующих совокупность С , в том числесигнал частичной суммы Б СигналыС,выходов ПК 1; поступают на соот"ветствующие входы элементов И-ИЛИ 2,причем на элемент 1-го разряда (1552, М) поступают определенные сигналы из совокупностей сигналов С,С, На выходах элементов И-ИЛИ 2образуются сигналы переносов Р во2-й. И-й разряды, а также выходных переносов Р в (И+1)-й (И+К)-й разряды, Сигналы Р,и 81 складываются по модулю два на сумматоре 3 по модулю два, так что на его выходе образуется сигнал результирующей суммы 8,. данного разряда.Преобразователь 1, представляет собой комбинационную схему с М+1 (сли х 4 К) либо (если х ) К) входами и Ь выходами, К определяется Фор- мулой к+1Ммнк 2 К 1/ где М скс- максимальное количество слагаемых, при котором количество выходных переносов еще равно К.При построении ПК используют свойства симметрических функций (СФ), основным из которых является следующее: СФ щ аргументов принимает значеИИ 11ние 1 тогда и только тогда , когда в каждом иэ е е ( а ) наборов аргументовтимеется ровно а единиц (символ ( )ш означает числа сочетаний из ш по а), иначе говоря, значение СФ определяется только количеством а 1 ф в наборах ее аргументов, Число а будем называть индексом СФ.На вход ПК 1, поступают сигналы М слагаемых А = х ..х, и входного переноса Е; = х (дляс К).М+1,Из этих переменных ПК 1; формирует СФ вида Р 1(а а .), аргументами которых являются индексы а а обозначим В,. = Рдля М+1 переменных 1-го разряда и 0; = Р, для М переменных.Объединение индексов в Р; основано на следующем свойстве СФ: Р(а , а ,) =. - Р(а 1)Р(а )+, те,на вазможности разложения СФ на простейшие.Простейшая СФ выражается через исходные переменные, как и обычная Функция алгебры логики, приведением к совер-45 55 5 154521щенной дизъюнктивной нормальной форме,так при М=4, И=4 СФ В(4) равна В(4)=Х,Х Х Х Х + Х 1 хгХЗХ Х + Х,ХХХРХ 1 ХХ 5 Х 4 Х + Х 1 Х тХ 5 Х 4 Х 5Особым случаем функции В либо Рявляется СФ Я; = Р (1,2 В), т.е.частичная сумма- го разряда. ЕслиМ - четно, то М+1 для 1,2 К-го разряда 10 В Мдля К+1,К+2,. ;,М-го разряда если М нечетно, то В = М для всех разрядов, Отметим, что функции Я явля ются функциями нечетности.Сигналы СФ, сформированные ПК 1. ( = 2, Б) образуют совокупность С1 а также сигнал 8 На выходе элементов И-ИЛИ 2 с первого по (Б)-й фор мируются сигналы функций переноса Р 2 Рц 1 которые поступают на Вхо ды сумматоров 3 по модулю два с 2-го до И-го разрядов соответственно, на выходах которых формируются сигналы результирующих сумм 8 . = Я, (+3 Р Сигнал 8= Ч, формируется непосредственно в ПК 1 , что упрощает схему для первого разряда. На выходах элементов И-ИЛИ 2 с Б-го по (И+К)-й ЗО формируются сигналы выходных переносов Ов О аПринцип формирования функций переносов Р и С 1 покажем на частном, но практически важном примере построения четырехраэрядного(Б=4) сумматора четырех слагаемых (М=4), у которого число К внешних переносов равно 2 (Е , Р; 0 = Р О = Р )В табл.1-5 приведены значения раз рядных индексов для функций переносаР 2-Р соответственно. В приведенных ниже табл.3-5 в столбцах помещены индексы СФ Э (для третьего и четвертого разрядов) и В (для первых двух разрядов), сумма которых для Р. по некоторой строке1с учетом веса разряда дает перенос в 2.-й разряд. Например, для переноса в четвертый разряд по первой строке табл.З) имеем 2 2 + 4. 2 О = 8 либо 2 2" + 5 2 = 9, Аналогично. составлены и остальные строки данной и всех других таблиц, так что множе,ство строк данной таблицы является результатом Перебора всех возможных вариантов получения .1 переноса всоответствующий разряд. 6 6В общем случае таблица значенийразрядных индексов для Р.(2 й ( И+К)составляется следующим образом. Последовательно перебираются значенияиндексов от О до М+1 (до М для) К)в столбце первого разряда при фиксированных значениях индексов в старших разрядах, затем увеличивается наединиц 1 значение индекса во второмразряде при фиксированных значенияхиндексов старших разрядов и сновапроизводится перебор всех возможныхзначений индексов в первом разряде,и т,.д. до тех пор, пока во второмразряде не будут перебраны все возможные значения индексов, затем увеличивается на единицу значение индекса в третьем разряде и производитсяперебор значений индексов в первом ивтором разрядах в последовательности,описанной ранее. Описанная процедуравыполняется вплоть до заполнения впоследнем столбце таблицы для Р,(количество столбцов равно х, если1Б, и равно И в остальных случаях)последнего значения индекса, равного М,В каждой строке должны быть такиезначения разрядных индексов, что ихдвоично-взвешенная сумма дает число,в двоичном эквиваленте которого появляется 1 в -м (иногда, крометого, в (ь.+1)-м) разряде.Полученные таким образом таблицыобладают некоторой избыточностью идопускают минимизацию описания схемысумматора за счет объединения строк,в которых индексы Отличаются тольков одном столбце при этом для СФ ссоседними значениями индексов по данному столбцу возможно склеивание исходных переменных, Для функции В (45)при М=4 получаем В (4,5) = х 1 Х 2 хзх ++ ххх 4 Х. Совокупность индексов0-5 для первых двух разрядов и 0-4для третьего и четвертого разрядовв таблицах соответствует тождественной единице, независимо от значенийдругих переменных. Информация, представленная в такого рода таблицах, является исчерпывающей для построения принципиальной схемы сумматора с заданными значениями М и Р.В приведенном на фиг.2 примере элементы И-ИЛИ заменены элементами154521И-НЕ в результате эквивалентного преобразования логических функций.Строкаф о Р и У л а и з о б р е т е н и Я 5 Т а б л и ц аРазряд2,3Таблица 2 Разряд Строка 4,5 2-5 0-3 0-3 0,1 4,5 2-5 0 1 2 3 3 4 5 1 2 3 4 4 5 6 Таблица 3 Разряд Строка- 1 4,5 2-5 0-5 4,5 2-5 0-5 0-3 0,1 0-5 0-3 О, 0-3 О, 4,5 2-5 4,5 2-5 0-5 Таблица 4 Разряд Строка 4,5 2-5 4,5 2-5 0-5 4,5 4 5 2 3 4,5 0 1 1 2.2 2 3 0 0 0 0 0 0 2 3 4 5 6 Устройство для суммирования М чисел, содержащее в каждом разряде преобразователь двоичного кода в код1 О количества единиц и в каждом разряде. кроме младшего, сумматор по,модулю два, выход которого является выходом суммы данного разряда устройства, входы каждого преобразователя двоичНого кода в код количества единиц соединены с входами соответствующего разряда слагаемых устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, устрой ство содержит (И+К) элементов И-ИЛИ, где М - разрядность слагаемых, МК+12 -К, образующих блок формирования параллельных переносов, причем каждый преобразователь двоичного коода в код количества единиц содержит выходы по числу значений кода количества единиц, а также выход нечетности кОда, который в каждом разряде устройства, кроме младшего разряда, соединен с первым входом сумматора по модулю два того же разряда, выходы элементов И-ИЛИ с первого по (11-)-й ссединены с вторыми входами соотвЕтствующих сумматоров по модулю два, а выходы элементов И-ИЛИ с И-го по 1 (И+К)-й соединены с выходами переносов устройства, в каждом 1-м разряде (=2.1+К) входы каждой группы И элемента И-ИЛИ соединены с выходами преобразователей двоичного кода в код количества единиц разрядов с первого по (1.-1)-й для1 и с первого по м-й для х1 У, так что1( Х В .) Л 2 Ф О, где Л - поразрядК ная операция И; 1 - номер выхода преобразователя двоичного кода в код количества единиц, 1 = О 1 Ь число входов преобразователя; В - вес 50 3-го выхода К - го преобразователя В:= О Ь, дополнительные входы преобразователей двоичного кода в код количества единиц с первого по К-й соедйнены с входами переноса устройства, выходом суммы младшего разряда устройства является выход нечетности преобразователя двоичного кода в код количества еднниц этого разряда. 0 22 0 33 0 4,54 1 . 05 1 16 2,37 1 48 1 59 2 О,1 О 2 211 2 312 3 013 3 114 3 415 3 516 4 217 4 318 4 4,51545216 Составитель А. Степановактор Н. Лаза енкор Техред М,Ходаиич Корректор В,Гирняк НИИПИ при ГКНТ СССР тенням ская н изводственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 10 49.1 ТиражГосударственного комитета113035, Москва, Ж по изо -35, Р дписное открытид, 4/