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

Союз Советскик Социалистическик РеспубликГосударственный комитет СССР по делам изобретений н открытийДата опубликования описания 260181(54) УСТРОИСТВО ДЛЯ ПОДСЧЕТА КОЛИЧЕСТВА ЕДИНИЦИзвестен асинхронный импульсный счетчик на асинхронных симметричных Т-триггерах, реализующий Функцию подсчета количества единиц в двоичном числе, представленном последовательнымимпульсным кодом. Двоичное 15 число поступает на вход Т-триггера первого разряда. Код; являющийся результатом подсчета количества единиц входного двоичного числа, образуется на выходах А,В,С,Т-триггеров, 20 СЦНедостатком асинхронного импульсного счетчика, в случае использования его для определения количества единиц в двоичном числе, является ограниченная область применения и малое быстродействие, что обусловлено необходимостью представления входного двоичного числа в последовательном импульсном коде. 30 Изобретение относится к автоматике и вычислительной технике, и, в частности, к устройствам, предназначенным для подсчета количества еди"4ницфв двоичных числах и может быть использовано при реализации технических средств дискретной автоматики и вычислительной техники. Наиболее близким по технической .сущности к предлагаемому являетсяустройство для параллельного счетаколичества единиц (нулей) в двоичномчисле, содержащее и-разрядныйвходной регистр, выходной регистр и1 оцп групп сумматоров по тт/2 сум-кматоров в каждой группе 1КоЯ п),В устройстве двоичное число заносится на и-разрядный входной регистр,а результат подсчета количества единиц (нулей) входного двоичного числа. - на выходной регистр, Соединениесумматоров внутри каждой группы, атакже соединение групп сумматоровдруг с другом и с выходным п- разрядным регистром и выходным регистром выполнены таким образом, что осуществляется подсчет количества единиц(нулей) входного двоичного числа 12(.Недостатком устройства являетсяего сложность, обусловленная необходимостью применения конструктивноотносительно сложных сумматоров исвязанное с этим сравнительно низкое быстродействие. Вследствие этого при реализации устройства методами микроэлектроники уменьшается технологичность его изготовления,Цель изобретения - упрощение устройства и повышение его быстродействия.Для достижения поставленной целиустройство для подсчета количестваединиц в двоичном числе, содержащееи-разрядный входной регистр и выходной регистр, причем входы и-разрядного входного регистра соединены совходами устройства, выходы выходногорегистра соединены с выходами устройства, содержит преобразовательдвоичного кода в уплотненный коди преобразователь уплотненного кодав код .количества единиц, причем выходЫ.входного регистра соединены со входами преобразователя двоичного кода вуплотненный код, выходы которого сое-.динены со входами преобразователяуплотненного. кода в код количестваединиц, выходы которого соединены совходами выходного регистра,Преобразователь двоичного кода в .уплотненный код при этом может бытьвыполнен так, что он содержит 1 од истрок модулей, причем входы модулейпервой строки соединены со входамипреобразователя двоичного кода вуплотненный код, выходы модулей последней строки соединены с выходамипреобразователя двоичного кода вуплотненный код, каждый модуль к-ойстроки (М=11 одп) содержитэлементы И и ИЛИи две группы входовпо 2"- входов в каждой, входы первой и второй групп каждогоэлемента М-ой строки (1=1 пй" )соединены с выходами (21-1)-го и21 -го модулей (-1)-ой строки,элементы И каждого модуля образуютматрицу, причем входы элементов Икаждой строки матрицы подключены ксоответствующему входу первой группы входов модуля, входы элементов Икаждого столбца матрицы подключенык соответствующему входу второй группы входов модуля, входы каждого аэлемента ИЛИ (а=1,2 -1) соединены с выходами элементов И соответствующей диагонали матрицы, входыкаждого р элемента ИЛИ (р=2"- + 12" ) соединены с (-2" ф )-ми, входамипервой и второй групп входов модуля,выходы элементов ИЛИ подключены квыходам модуля.Преобразователь двоичного кода вуплотненный код выполнен так, чтоон содержит (и) строк модулей,каждый из модулей содержит элементыИ и ИЛИ, причем первый вход каждогомодуля соединен с первыми входамиэлементов.И и ИЛИ, второй вход модулясоединен со вторыми входами элементов И и ИЛИ,. выход элемента И соединен. с первым выходом модуля, выходэлемента ИЛИ соединен со вторым выходом модуля, входы модулей первойстроки соединены со входами преобра.зователя двоичного кода в уплотненный код, выходы модулей последней строки, а также первый выход первого модуля и второй выход последнего модуля предпоследней строки присоединены к выходам преобразователя двоичного кода в уплотненный код, первый выход последнего модуля первой строки соединен с первым входомпервого модуля второй строки, второйвыход последнего модуля первой строки соединен со вторым входом последнего модуля второй строки, первый выход первого модуля каждой четнойстроки подключен к первому входу первого модуля следующей четной строки, которой выход последнего модуля каж- О дой четной строки присоединен ко второму входу последнего модуля следующей четной строки, остальные выходымодулей каждой строки присоединеныко входам модулей следующей строки, причем первый выход любого 1-гр модуля каждой нечетной строки присоединен ко второму входу 1-го модуля следующей строки, второй выход любого 1-го модуля каждой нечетной строки присоединен к первому входу 1+1-го модуля следующей строки, первый выход любого 1-го модуля каждой четной строки присоединен ко второму входу 1-1-го модуля следующей строки, а второй выход любого 1-го модуля каждой четной строки.присоединен к первому входу 1-го модуля следующей строки.Преобразователь двоичного кода вщ уплотненный код может быть выполнентак, что он содержит истрок модулей, причем каждая 1-ая строка(1 1п) преобразователя двоичного кода в уплотненный код содержит имодулей, а каждый из модулей содержит элемент И и элементИЛИ, причем первый вход модуля соединен с первыми входами. элементов И иИЛИ, второй вход модуля соединен совторыми входами элементов,И и ИЛИ,4 выход элемента И соединен с первымвыходом модуля, выход элемента ИЛИсоединен со вторым выходом модуля,первые входы модулей первой строкии второй вход последнего модуля перяр вой строки соединены со входами преобразователя двоичного кода в уплотненный код, второй выходпервого модуля каждой строки и первый выход мо-,дуля последней строки соединены свыходами преобразователя двоичногокода в уплотненный код, первый выходпоследнего модуля каждой строки,кроме последней, соединен со вторымвходом последнего модуля следующейстроки, в каждой строке второй выход60 )-го модуля=2 и"1) присоединен ко второму входу -1)-гомодуля, первый выходмодуля (=1,,и-1) каждой стрЬки присоедине.ны к первому входу (, модуля слеИ дующей строки,На фиг. 1 изображена схема устройства для подсчета количества единиц в двоичном числе на 8 разрядов,на фиг. 2,3 и 4 - варианты выполненияпреобразователя двоичного кода вуплотненный код на фиг, 5 - схемавыполнения модуля преобразователядвоичного кода в уплотненный код,выполненного в соответствии с фиг.2.Устройство для подсчета количества единиц в дво:.ом числе содержитвходной регистр 1, выходной регистр2, входы устройства 3, выходы устройства 4, преобразователь 5.двоичного кода в уплотненный код и преобразователь б уплотненного кода вкод количества единицпричем входыгреобразователя 5 соединены с выходами входного регистра 1, выходыпреобразователя 5 соединены со входами преобразователя б, выходы которого соединены со входами выходного регистра 2,Устройство для подсчета единицработает следующим образом.На входной регистр 1 через входыустройства 3 заносится двоичный кодчисла, С выходов входного регистра1 код числа передается в преобразователь 5 двоичного кода в уплотненный код, количество единиц на выходе которого равно количеству единицво входном числе,Работа преобразователя б уплотненного кода в код количества единицописывается формуламио о)а,=Ь,Ь 401 Ь Ь У Ь Ь 40где,ао, а,;а ,а - сигналы на выходахпреобразователя бкода,Ь; Ь,;,-;Ь 7 - сигналы на входах.преобразователя б. ЯВ результате такого двойного преобразования на выходах устройстваобразуется код количества единиц вовходном числе,Преобразователь 5 состоит из 1 одп Щстрок модулей 7 (фиг.5), причем входымодулей 7 первой строки соединены совходами преобразователя 5, выходымодуля последней строки соединены свыходами, преобразователя 5, выходыкаждой из двух групп входов любогомодуля 7,кроме модулей первой строки,подключены к соответствующим выходамодного модуля 7 предыдущей строки,каждый модуль 7 содержит элементы8 И, образующие матрицу, элементы МО9 ИЛИ, и две группы входов, причемвходы каждой группы входов модуля 7(-ой строки (1=11 о 9 и) пронумерованы от 0 до 2" - 1 и соедииены со входами элементов 8 И такимб 5 образом, что образуется совпадениекаждого входа первой группы входовмодуля 7 с каждым входом второй группы входов модуля 7, выход каждогоэлемента 8 И подключен к входу тогоэлемента 9 ИЛИ, номер которого равенсумме номеров входов модуля 7, подключенных к данному элементу 8 И,кроме того, каждый -ый вход любойгруппы входов модуля 7 1-ой строки.соединен со входом элемента 9 ИЛИ сномером 2"+ , выходы элементов9 ИЛИ соединены с соответствующимивыходами модуля 7.Работа преобразователя 5 двоичного кода в уплотненный код заключаетсяв следующем,Каждый модуль 1-ой строки устройства преобразует коды, поступающиена входы первой ивторой групп еговходов таким образом, что в коде навыходе модуля 7 все единицы сдвинутывправо, а количество единиц в выходном коде равно суммарному количеству единиц во входных кодах. Модули7 соединены между собой так, что йавходы каждой группы входов любого модуля 7 поступает код, в котором всеединицы сдвинуты вправо. В результате преобразования двоичного входного .числа модулями 7 преобразователя 5 на выходе модуля 7 последнейстроки образуется код, в котором всеединицы сдвинуты вправо, а их количество равно количеству единиц вовходном регистре 1.Другой вариант построения преобразователя 5 двоичного кода в уплотненный код показан на фиг. 3.Преобразователь 5 содержит и-строк модулей 10, каждый из которыхсодержит элементы 11 И и 12 ИЛИ, Входы модулей 10 первой строки соединены со входами преобразователя 5, Выходы модулей 10 последней строки, атакже первый выход первого модуля10 (модули в строках нумеруютсяслева направо) и второй выходпоследнего модуля 10 предпоследнейстроки присоединены к выходам преобразователя 5. Первый выход последнего модуля 10 первой строки соединен с первым входом первого модуля10 второй строки, второй выход пос-леднего модуля 10 первой строки сое-.динен со вторым входом последнегомодуля 10 второй строки. Первыйвыход первого модуля каждой четнойстроки подключен к первому входупервого модуля 10 следующей четнойстроки. Второй выход последнего модуля 10 каждой четной строки присоединен ко второму входу последнегомодуля 10 следующей четной строки.Оставшиеся выходы модулей 10 каждойстроки присоединены ко входам модулей 10 следующей строки, причемпервый выход любого 1-го модуля10 каждой нечетной строки присоеди1 О где нен ко второму входу -го модуля10 следующей строки, второй выходлюбого -го модуля 10 каждой нечетной строки присоединен к первому входу +1-го модуля 10 следующей строки, первый выход любого-го модуля 10 каждой четной строкиприсоединен ко второму входу 1-1-гомодуля 10 следующей строки, а второйвыход любого -го модуля .10 каждой четной строки присоединен к первому входу 1-го модуля 10 следующейстроки. Входы элементов 11 И и 12 ИЛИкаждого модуля 10 соединены со входами модуля 10, а выходы подключенысоответственно к первому и второмувыходам модуля 10. Каждый из модулей 10 осуществляет сдвиг единиц,поступивших на его входы, вправо, тоесть, если на первый и второй входы модуля 10 поступают коды 00,01,10,11,то на первом и втором выходе модуляпоявляются соответственно коды 00,01, 01,11. Модули 10 соединены между собой таким образом, что на выходе преобразователя 5 образуетсякод, в котором все единицы сдвинутывправо, а их количество равно количеству единиц входного двоичного числа. Третий вариант построения преобраэователя 5 двоичного кода в уплотненный код представлен на фиг.4.Преобразователь 5 содержит модули 13, каждый из модулей 13 содержит элемент 14 И и элемент 15 ИЛИ причем первый вход модуля 13 соединен с первыми входами элементов 14 Ии 15 ИЛИ, второй вход модуля 13 соединен. со вторыми входами элементов14 И и 15 ИЛИ, выход элемента 14 Исоединен с первым выходом модуля13, выход элемента 15 ИЛИ соединенсо вторым выходом модуля 13, Первыевходы модулей 13 первой строки ивторой вход последнего модуля 13первой строки соединены со входамипреобразователя 5. Второй выход первого модуля 13 каждой строки (модули в строках пронумерованы слева направб) и первый выход первого модуля 13 последней строки присоединен к соответствующим выходам преобразователя 5. Первый выход последнего модуля 13 каждой строки, кроме последней, соединен со вторым входом последнего .модуля 13 следующей строки. В каждой. строке второй выход любого 1-го модуля 13, кроме первого, присоединен ко второму входу 1-1-гс модуля 13, В каждой строке первый выход любого 1-го модуля 13, кроме последнего, присоединен к первому входу -.го же модуля 13 следующей строкиСтруктура связи между элементами предлагаемого устройства проще, чем в известном устройстве, эа счет исключения таких конструктивно слож ных элементов, как сумматоры. Большая степень регулярности связей между элементами и простота самих элементов устройства повышает технологичность его изготовления методами микроэлектроники, что приводит, в конечном счете, к увеличению процента выхода годных изделий в производстве и повышение надежности устройства в процессе эксплуатации.В известном устройстве время задержки сигналов при прохождении их через сумматоры определяется по фор- муле Т= ь(п 2-1)+ ь Яоф(1) где Т, - время пробега сигнала суммы через сумматор;овремя пробега сигнала переноса через сумматор;и - разрядность входного регистра.В данном устройстве время задержки Т 1 сигналов с выходов и-разрядного входного регистра 1 при прохождении их через модули преобразователя 5 и через преобразователь б складывается из суммарного времени задержки сигнала модулем каждой строки первого преобразователя кода и вторым преобразователем кода и определяется по формуле задержка сигнала модулем-ой строки преобразователя 5,задержка сигнала преобразователем б;разрядность входного регистра Формула изобретения 1.устройство для подсчета количества единиц в двоичном числе, содержащее и-разрядный входной регистр и выходной регистр, причем входы и- разрядного входного регистра соединены со входами устройства, выходы выходного регистра соединены с выходами устройства, о т л и ч а ю щ е е с я тем, что, с целью упрощения и повышения быстродействия устройства, оно содержит преобразователь двоичного кода вуплотненный код и преобразователь уплотненного кода в код количества ед иц, причем выходы входного региетра соединены со входами преобразователя двоичного кода в уплотненный .код, выходы которого соединены со входами преобразователя уплотненного кода в код количества единиц, выходы которого соединены со входами выходного регистра.45 2.Устройство по п,1, о т л и ч а ю щ е е с я тем, что преобразователь двоичного кода в уплотненный код содержит 1 од и строк модулей, причем входы модулей первой строки соединены со входами преобразователя двоичного кода в уппотненный код, выходы модулей последней строки соединены с выодами преобразователя двоичного кодав уплотненный код, каждый модуль М-ой строки (к=1, ,)одоп) содержит элементы И и ИЛИ и две группы входов по 2 входов в каждой, входы первой и второй группы каждого 1 элемента 1-ой строки (1=1.Щ 2 ) соединены1с выходами (21 -1)-го и 21 -го модулей (1-1)-ой строки, элементы И каждого модуля образуют матрицу, причем входы элементов И каждой строки матрицы подключены к соответствующему входу первой группы входов моду-,Я .ля,входы элементов И каждого столбца матрицы подключены к соответствующему входу второй группы входов модуля, .входы каждого,в элемента ИЛИ (в=1,К,2 -1) соединены с выходами эле- д ментов И соответствующей диагонали матрицы,.входы каждого р элемента ИЛИ (р=2 + 1,;2 К ) соединены с (р-.2 )-ми входами первой и второй групп входов модуля, выходы элементов ИЛИ подключены к выходам модуля.3. Устройство по п,1, о т л ич а ю щ е е с я тем, что преобразователь двоичного кода в уплотненный код содержит (и) строк модулей, каждый из модулей содержит элементы И и ИЛИ, причем первый вход каждого модуля соединен с первыми входами элементов И и ИЛИ, второй вход модуля соединен со вторыми входами элементов И и ИЛИ, выход элемента 40 И соединен с первым выходом модуля, выход элемента ИЛИ соединен со вторым выходом модуля, входы модулей первой строки соединены со входами. преобразователя двоичного кода в уплотненный код, выходы модулей последней строки, а также первый выход первого модуля и второй выход последнего модуля предпоследней строки присоединены к выходам преобразователя двоичного кода в уплотненный код, первый выход последнего модуля первой строки соединен с первым входом первого модуля второй строки, второй выход последнего модуля:первой строки соединен.со вторым входом пос- О леднего модуля второй строки, первый выход первого модуля каждой четной строки подключен к первому входу пер. вого модуля следующей четной стро" ки, второй выход последнего модулякаждой четной строки присоединен ковторому входу последнего моцуля следующей четной строки, остальные выходы модулей каждой строки присоединены ко входам модулей следующейстроки, причем первый выход любого-го модуля каждой нечетной строкиприсоединен ко второму входу (-гомодуля следующей строки, второйвыход любого -го модуля каждойнечетной строки присоединен к первому входу +1-го модуля следующей строки, первый выход любого -гсмодуля каждой четной строки присоединен ко второму входу (-1-го модуляследующей строки, а второй выход любого -го модуля каждой четной строки присоединен к первому входу -гомодуля следующей ютроки.4.устройство по п.1; о т л ич а ю щ е е с я тем, что преобразователь двоичного кода в уплотненныйкод содержит истрок модулей,причем каждая -ая строка ( =1и) преобразователя двоичного Йодав уплотненный код содержит и- модулей, а каждый из модулей содержитэлемент И и элемент ИЛИ, причем первый вход модуля соединен с первымивходами элементов И и ИЛИ, второйвход модуля соединен со вторыми входами элементов И и ИЛИ, выход элемента И соединен с первым выходом модуля,выход элемента ИЛИ соединен со вторым выходом модуля, первые входы модулей первой строки и второй входпоследнего модуля первой строки соединены со входами преобразователядвоичного кода в уплотненный код,второй выход первого модуля каждойстроки и первый выход первого модуля последней строки соединены с выходами преобразователя двоичного кодав уплотненный код, первый выход последнего модуля каждой строки, кромепоследней, соединен со вторым входомпоследнего модуля следующей строки,в каждой строке второй выход -гомодуля =2 иприсоединенко второму входу )-1 -го модуля,первый выход с(, -го модуля ( =1и1) каждой строки присоединен кпервому входу-го модуля следующей строки.Источники информации,принятые во внимание при экспертизе1.Будинский Я. Логические цепи вцифровой технике. М., "Связь", 1977,с, 266, рис. 6.111 а.798830писноекаэ 1005667 ТиРаж 75 НИИП филиал НПП "Патент", г. Ужгород, ул. Проектная,