Устройство для подсчета количества единиц в -разрядном двоичном коде

(5 ИСАНИЕ ИЗОБРЕТЕНИ РСКОМУ СВИ ЬСТВУ: К СЧЕТА КОЛИ- РЯДНОМ ДВОий инО 64786 ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕВЕДОМСТВО СССР(54) УСТРОЙСТВО ДЛЯ ПОД ЧЕСТВА ЕДИНИЦ В и-РАЗИЧНОМ КОДЕ (57) Изобретение относится к вычислительной технике. Его использование в системах Обработки Цифровой информаЦии позволя" ет повысить быстродействие устройства, которое содержит несколько ярусов из трехвходовых сумматоров 2. Цель достигается благодаря введению блоков суммирования 1 со специфической структурой, что минимизйрует число последовательныхний. 1 з.п. ф-лы, 2 ил.Изобретение относится к области вычислительной техники и предназначено дляподсчета количества единиц в двоичномчисле.Известно устройство для определения 5количества единиц в двоичном числе, содержащее последовательно включенные группы сумматоров.Недостатками известного устройства,обусловленными низкой степенью регулярности связей, являются большое количествопересечений связей между собой, значительная длина линий связи между сумматорами логической схемы. Вследствие этого:при реализации устройства методами Микроэлектроники уменьшается технологичность его изготовления и увеличиваетсязанимаемая площадь.Наиболее близким из известных по технической сущности и принятым за прототип 20является устройство для параллельного счета,количества единиц (нулей) в двоичномчисле, содержащее входной и выходной регистры и группы сумматоров: выход суммыпоследнего сумматора каждой группы и выход переноса сумматора последней группысоединен с входами соответствующих разрядов выходного регистра,Недостатком прототипа является низкое быстродействие, обусловленное последовательным распространением сигналасуммы через-- 1 сумматор первогои2яруса, где и - разрядность входного кода.Целью изобретения является повышение быстродействия устройства. Поставленйая цель достигается тем, что в устройстводля подсчета количества единиц в и-разрядном двоичном коде, содержащее первыйярус из первого -- - го трехвходовыхи 4012сумматоров (, - ближайшее большее целое)ю второй - (1 оя 2 и - 1) ярусы из первого -и- -+1- го трехвходовых сумматоров (к =2"2,3, .од 2 и - 1), в каждом ярусе, кроме последнего, вьход суммы каждого трехвходового сумматора, кроме последнего,соединен с первым входом последующеготрехвходового сумматора этого же яруса,выход переноса (21-1)-го и (21)-го трехвходовых сумматоров( = 1,2,. - +) каждо 2го яруса, кроме первого и последнего,соединен с вторым и третьим входами 1-готрехвходового сумматора последующегояруса, выход суммы последних трехвходовых сумматоров каждого яруса и выход переноса трехвходового сумматора последнего яруса являются соответственно первым -1 оо 2 п- м разрядами выходов устройства, введены первый в .в - й блои6ки суммирования, первый - шестой информационные входы каждого из которых являются соответствующими информационными входами устройства, третий выход каждого блока суммирования, кроме последнего, соединен с входом переноса последующего блока суммирования, третийивыход-- го блока суммирования является нулевым разрядом выходов устройства, второй выход первого блока суммирования подключен к первому входу первого трехвходового сумматора первого яруса, вторые выходы (2)-го и (2+1)-го блоков суммирования соединен с вторым и третьим входами 1-го трехвходового сумматора первого яруса, первый выход каждого блока суммирования и выход переноса каждого трехвходового сумматора первого яруса подключены к вторым и третьим входам соответствующих трехвходовых сумматоров второго яруса.Кооме того, эта цель достигается тем, что блок суммирования содержит первый-, третий трехвходовые сумматоры, первый и второй полусумматоры, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент НЕ и первый-третий мультиплексоры, управляющие входы которых обьединены и являются входом переноса блока, входы первого и второго трехвходовых сумматоров являются соответственно первым-шестым информационными входами блока, выходы суммы первого и второго трехвходовых сумматоров соединены с входами первого полусумматора, выход переноса которого и выходы. переноса первого.и второго трехвходовых сумматоров подключены к входам третьего и трехвходового сумматора, выход переноса которого соединен с первым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и первым информационным входом.первого мультиплексора, выход которого является первым выходом блока, выход суммы третьего трехвходового сумматора подключен к первому входу второго полусумматора и первому информационному входу первого мультиплексора, выход которого является вторым выходом блока, выход переноса второго полусумматора подключен к второму входу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого соединен с вторым информационным входом первого мультиплексора; выход суммы первого полусумматора соединен с входом элемента НЕ, первым информационным входом третьего мультиплексора и51015 20 25 30 35 40 55 вторым входом второго полусумматора, выход суммы которого подключен к второму информационному входу второго мультиплексора, выход элемента НЕ соединен с вторым информационным входом третьего мультиплексора, выход которого является третьим выходом блока.На фиг.1 показана схема устройства для подсчета количества единиц в двоичном коде; на фиг.2 - реализация блока суммирования.Устройство для подсчета количества единиц содержит и-разрядную входную шину А,-блоков суммирования 1 1.1 и6и1. 6, образующих первый ярус, и-+-- 1 трехвходовых сумматорови и12 42 2.1-1 о 92 и1, Первый-шестой входы каждого блока суммирования 1 1.1-1.и-являются соответствующими инфор 6мационными входами устройства, третий выход 1-го блока суммирования 1 1.1, кроме последнего блока 1,- , соединен с вхоидом переноса (1+1)-го блока суммирования 1 1,(1+1), третий выход- - го блока суммии6рования 1 1.-является нулевым разряи6дом выходов устройства, второй выход первого блока суммирования 1 1,1 подключен к первому входу первого трехвходового сумматора 2 второго яруса 2,1, вторые выходы (2)-го 1,(2) и (23+1)-го 1.(21+1) блоков суммирования 1 соединены с вторым и третьим входами 1-го трехвходового сумматора 2 второго яруса 2 Л, первые выходы блоков суммирования 1 1,1 - 1-и выходы пере 6носа трехвходовых сумматоров 2 второго яруса 2.1-2.-поступают на соответсти12вующие входы трехвходовых сумматоров 2 третьего яруса 3.1 - 3.- ; в третьем -п(1 оцгп)-м ярусах выход суммы каждого 1-го трехвходового сумматора 2 Ь 1, кроме последнего М.- , где К - номер яруса,и2соединен с входом переноса (+1)-го сумматора 2 того же яруса М (1+1), выходы переноса (21-1)-го к.(21-1) и (2)-го к.(2) трехвходовых сумматоров 2 каждого М-того яруса кроме оцуп-го соединены с вторым и третьим входами 1-го трехвходового сумматора 2 (к+1)-гО яруса (к+1). выход суммы последних трехвходовых сумматоров 2 второго -о 92 п-го ярусов и выход переноса сумматора 2 1 о 92 п-го яруса 1 о 92 п 1 являются соответственно первым - (1 оя 2 п - 1)-м разрядами выходов устройства.Блок суммирования (фиг.2) содержит первый-третий трехвходовце сумматоры 1- 3, первый и второй полусумматоры 4 - 5, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 6, элемент НЕ 7 и первый - третий мультиплексоры 8 - 10, управляющие входы которых объединены и являются входом переноса блока, входы сумматоров 1 и 2 являются информационными входами блока, выходы суммы треквходовых сумматоров 1 и 2 соединены с входами первого полусумматора 4, выход переноса которого и выходы переноса сумматоров 1 и 2 подключены к входам третьего трехвходового сумматора 3, выход переноса которого соединен с первым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 6 и первым информационным входом мультиплексора 8, выход которого является первым выходом блока, выход суммы трехвходового сумматора 3 подключен к первому входу второго полусумматора 5 и первому информационному входу второго мультиплексора 9, выход которого является вторым выходом блока, выход переноса второго полусумматора 5 подключен к второму входу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 6, выход которого соединен с вторым информационным входом мультиплексора 8; выход суммы первого полусумматора 4 соединен с входом элемента НЕ 7, первым информационным входом третьего мультиплексора 10 и вторым входом полусумматора 5, выход суммы которого подключен к второму информационному входу второго мультиплексора 9, выход элемента НЕ 7 соединен с вторым информационным входом мультиплексора 10, выход которого является третьим выходом блока.Устройство "работает следующим образом.45 Блоки суммирования первого яруса 1.11.-формируют и группы по три6 6 сигнала. Сигнал младшего разряда суммы, имеющий вес 2, последовательно распространяется через- -1 блоков суммирои6вания первого яруса 1.2 - ,Ц -. Сигнал6 младшего разряда суммы, формируемый последним блоком суммирования первого яруса 1.-имеет вес 2 и являетсяиР6 значением младшего разряда двоичного кода количества единиц в и-разрядном коде,1783617 дт сои 1 - 1 + ствиюдт=для ивый су и и12 1 +4 1 1 трехвходовых сумматоров, 5 По аппаратурным затратам блок суммирования (фиг.2) превышает трехвходовый сум-.матор приблизительно в 4,5 раэ.Таким образом, аппаратурные затратыпри реализации предлагаемого устройства О 13могут быть оценены как - и - 1 то есть12проигрыш по аппаратурным затратам составляет менее 8%.Фо р мул а и зоб рете н ия 5 1, Устроиство для подсчета количестватединиц в и-разрядном двоичном коде, содержащее первый ярус из первого -- 1 трехвходовых сумматоров (.1 - ближайшее большее целое), второй -(од 2 п 1-1)- -й ярусы иэ первогои- + Ътрехвходовых сумматоров (1,=22,3,од 2 п 3, в каждом ярусе, кроме последнего, выход переноса соединен с первым входом последующего трехвходового сумматора этого же яруса, выходы суммы (2 - 1)- го и (2)-го трехвходовых сумматоров ( =и1 2- ,:-т 1 ) каждого яруса, кроме пертвого и последнего, соединены с вторым и третьим входами -го трехвходового сумматора последующего я руса, выходы переноса последних трехвходовых сумматоров каждого яруса и выход суммы трехвходового сумматора последнего яруса являются соответственно первым - од 2 п 1-м разрядами выходов устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства, в него введены первый -и- 1- й блоки суммирования, первый-шестой информационные входы каждого из ко- торых являются соответствующими информационными входамй устройства, первый выход каждого блока суммирования, кроме последнего, соединен с входом переноса последующего блока суммирова+Гсм "(од 2 и - 1),где тсм- задержка формирования40 младшего разряда суммы при подаче сигнала на входы блока суммирования;тсм, тсм- задержки формиладшего и среднего разрядов сумке суммирования при подачеа вход переноса блока суммироварованиям мы в бло сигнала н ния.Для б"од 2 п Сигналы среднего разряда суммы блоков суммирования первого яруса 1.1 - 1.и 1- 1 имеют вес 2 и поступают на входы сумматоров второго яруса 2,.1 - 2,- ),12 Сигналы переноса с сумматоров второгоияруса 2 1 - 2- 1 и сигналы старших разрядов сумм блоков суммирования первого яруса 1.1 - 1,- 1, имеющие вес 2, поступпают на входы сумматоров третьего яруса 3.1 - 3.- 1, Далее на входы сумматоров (с+1)-го яруса (с+1).1-(+1).1 посту 2пают сигналы переноса только из с-то ярусаимеющие вес 2 . Сигнал суммы, формируе-мый последним сумматором с-го яруса 1,2- 1, имеет вес 2 и является 1-м разря 2 е дом двоичного числа количества единиц во входном и-разрядном коде.Использование в первом ярусе блоков суммирования позволяет повысить быст 2 родействие без увеличения аппаратурных затрат. Действительно максимальная задержка Тмас отработки сигналов прототипом равна Тмасс П имас тсм с( -- 1)+см Од 2 П, ГДЕс птсм и тсм - задержки сигналов суммы и переноса в одном сумматоре (2), В то же время для рассматриваемого устройства 3 Т =г ( 2). (2)(3)+ Таким образом,Т макс =тсм ( - + 1 ) +гсс П6 Выигрыш по быстродействиюставляет к, при и = 32 выигрыш по быстродейд т составляет 1,6 раза, при и = 64 . При этом аппаратурные затраты рототипа составляют и - 1 трехвходомматор, для предлагаемого устройсти- блоков суммирования и1783617 10 Составитель В,Федо Техред М.Моргентал ектор С,Юск дакто 521 Тираж . ПодписноеИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС113035, Москва, Ж, Раушская наб 4/5д Заказ Внно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина Произв ния, первый выход . - - го блока суммиибрования является нулевым разрядом выходов устройства, второй выход первого блока суммирования подключен к первому входу 5 первого трехвходового сумматора первого яруса, вторые выходы (2 О-го и (21+1-го блоков суммирования соединены с вторым и третьим входами 1-го трехвходового сумматора первого яруса, третий выход каждого 10 блока суммирования и выход суммы каждого трехвходового сумматора первого яруса подключены к вторым и третьим входам соответствующих трехвходовых сумматоров второго яруса. 152. Устройство по п.1, о т л и ч. а ю щ е е с я тем, что блок суммирования содержит первый-третий трехвходовые сумматоры, первый и второй полусумматоры, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент НЕ и пер вый - третий мультиплексоры, управляющие входы которых объединены и являются входом переноса блока, входы первого и второго трехвходовцх сумматоров являются соответственно первым-шестым информа ционными входами блока, выходы суммы первого и второго трехвходовых сумматоров соединены с входами первого полусумматора, выход переноса которого и выходы переноса первого и второго трехвходовых сумматоров подключены к входам третьего трехвходового сумматора, выход переноса которого соединен с первым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и первым информационным входом первого мультиплексора, выход которого является первым выходом блока, выход суммы третьего трехвходового сумматора подключен к первому входу второго полусумматора и первому информационному входу второго мультиплексора, выход которого является вторым выходом блока, выход переноса второго полусумматора подключен к второму входу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого соединен с вторым информационным входом первого мультиплексора, выход суммы первого полусумматора соединен с входом элемента НЕ, первым информационным входом третьего мультиплексора и вторым входом второго полусумматора, выход переноса которого подключен к второму информационному входу второго мультиплексора, выход элемента Н Е соединен с вторым информационным входом третьего мультиплексора, выход которого является третьим выходом блока.