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

(51)5 6 06 Р 7 БРЕТЕН рственныи унимсомола в, В, А,Забелин ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕВЕДОМСТВО СССР(54) УСТРОЙСТВО ДЛЯ ПОЧЕСТВА ЕДИНИЦ В ДВОИ(57) Изобретение относитсявычислительной технике. Це о СССР 978.о СССР 1988.ДСЧЕТА КОЛИЧНОМ ЧИСЛЕ к автоматике и ль изобретения 795455 А 1- сокращение аппаратурных затрат, Устройство для подсчета количества единиц в двоичном числе содержит и-разрядный входной регистр 1, выходной регистр 2, преобразователь 3 двоичного кода в уплотненный код, преобразователь 4 уплотненного кода в код количества единиц, Преобразователь 3 содержит узел 7 управляемой инверсии, узел 8 формирования уплотненного кода, элемент НЕ 9 и модифицированную матрицу 10 модулей, Узлы 7 и 8 управляются с входа 11, Цель изобретения достигается введением в матрицу 10 и/2 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и и/2 элементов И, 2 ил,Изобретение относится к автоматике и вычислительной технике,Известно устройство для подсчета количества единиц в двоичном числе, содержащее и-разрядные входной и выходной регистры, преобразователь двоичного кода в уплотненный код и преобразователь уплотненного кода в код количества единиц.Недостатком устройства является большое количество элементов, растущее пои ифункции2 2Известно устройство для подсчета количества единиц в двоичном числе, содержащее и-разрядные входной и выходной регистры, преобразователь уплотненного кода в код количества единиц и преобразователь двоичного кода в уплотненный код, содержащий узел управляемой инверсии, связанный с управляющим входом, с которым через инвертор связан узел формирования уплотненного кода, а также матрицу модулей, состоящую из и+1)/2) строк модулей, причем каждая -я строка содержит (и - ) модулей,Недостатком устройства является большое число элементов, растущее по функции,(и - 1),Цель изобретения - сокращение аппаратурных затрат,Поставленная цель достигается тем, что в устройстве для подсчета количества единиц в двоичном числе, содержащем входной регистр, выходной регистр, преобразователь двоичного кода в уплотненный код и преобразователь уплотненного кода в код количества единиц, причем входы устройства соединены с входами входного регистра, выходы которого соединены с входами преобразователя двоичного кода в уплотненный код, выходы которого соединены с входами преобразователя уплотненного кода в код количества единиц, выходы которого соединены с входами выходного регистра, выходы которого соединены с выходами устройства, при этом преобразователь двоичного кода в уплотненный код содержит узел управляемой инверсии, информационные входы которого соединены с входами преобразователя двоичного кода в уплотненный код, выходы узла управляемой инверсии соединены с входами матрицы модулей, выходы которой соединены с информационными входами узла формирования уплотненного кода, выходы которого соединены с выходами преобразователя двоичного кода в уплотненный код, а управляющий вход узла формирования уплотненного кода соединен с выходом элемента НЕ, вход которого соединен с управляющим входом узла управляемой инверсии и с входомпризнака непревышения половины количества единиц в двоичном числе устройства, вматрицу модулей введены и/2 элементов"0 ИСКЛЮЧАЮЩЕЕ ИЛИ и и/2 элементов И,где и - разрядность входного числа устройства, причем входы матрицы модулей с первого по и/2-й соединены соответственно спервыми входами элементов ИСКЛЮЧАЮ 15 ЩЕЕ ИЛИ и с первыми входами элементовИ, а входы матрицы модулей с (и/2+1)-го пои-й соединены соответственно со вторымивходами элементов ИСКЛЮЧАЮЩЕЕ ИЛИи со вторыми входами элементов И, выходы20 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединены с первыми входами модулей с первого пои/2-й первой строки матрицы, выходы элементов И соединены с первыми входамимодулей с (и/2+1)-го по (и - 1)-й и со вторымвходом (и - 1)-го модуля первой строки матрицы, второй выход (и/2+1)-го модуля з-ойстроки матрицы (з=Г; и 74) соединен со вторым входом. и/2-го модуля (2 з - 1)-й строкиматрицы и со вторым входом и/2-го модуля30 2 з-ой строки матрицы,На фиг. 1 представлена функциональная схема устройства для подсчета количества единиц в двоичном числе; на фиг. 2 -схема выполнения модифицированной мат 35 рицы модулей со входным преобразователем - модификатором кода.Устройство для подсчета количестваединиц в двоичном числе содержит и-разрядный входной регистр 1, выходной ре 40 гистр 2, преобразователь 3 двоичного кодав уплотненный код, преобразователь 4 уплотненного кода в код количества единиц,входы 5, выходы б. Преобразователь 3 содержит узел 7 управляемой инверсии, узел45 8 формирования уплотненного кода, элемент НЕ 9 и модифицированную матрицумодулей 10. Устройство содержит такжевход 11 признака непревышения половиныколичества единиц в двоичном числе. Моди 50 фицированная матрица 10 содержит. модули12, каждый из которых содержит элементИЛИ 13 и элемент И 14, кроме того, модифи- .цированная матрица 10 содержит группуэлементов ИСКЛЮЧАЮЩЕЕ ИЛИ 15 и груп 55 пу элементов И 16.Устройство работает следующим образом.На входной регистр 1 через входы устройства 5 заносится код числа. С выходоввходного регистра 1 код числа передается50 на узел 7, управляемый по входу 11, Пусть сигнал "1" на входе 11 информирует устройство о том, что число единиц в обрабатываемом коде не больше числа нулей, тогда узел 7 пропускает через себя информацию без изменения. Если на входе 11 сигнал "0", то узел 7 инвертирует каждый разряд кода, обеспечивая тем самым подсчет числа нулей с помощью той же аппаратуры, подсчитывающей число единиц в коде, Первая половина выходов узла 7 передается на первые входы группы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 15 и первые входы группы элементов И 16, на вторые входы обеих этих групп передаются сигналы со второй половины выходов узла 7, При этом на выходах группы элементов И 16 выявляются единички, отстоящие друг от друга в точности на расстоянии и/2, или другими словами, идентифицируется число таких пар. На выходах элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 15 накапливаются все остальные единички, не попавшие в число пар, и только они. Поскольку число единичек, поступающих с выхода узла 7, не превышает половины общего числа выходов, то число единичек, идентифицирующих число пар на выходах группы элементов И 16, не будет превышать четверти разрядности обрабатываемого кода, и, следовательно, число элементов 12 матрицы 10 может быть сокращено,В итоге на выходе модифицированной матрицы из модулей 12 образуется уплотненная последовательность единиц, длина которой равна количеству единиц во входном числе при общем количестве единиц, не превышающем число нулей, либо числу нулей во входном числе при сигнале "0" на входе 11,Информация из матрицы 10 поступает на входы узла 8, с помощью которого приводится к уплотненному коду, равному количеству единиц во входном числе. Если с входа 11 поступает сигнал "1", то работа второй половины узла 8 блокируется, уплотненный код, равный количеству единиц во входном числе, поступает на входы преобразователя 4, Если на вход 11 поступает сигнал "0", то . на первую половину входов преобразователя 4 засыпаются "1", а на вторую половину входов преобразователя 4 посылаются инверсные значения выходов матрицы 10.Сигнал через выходной регистр 2 поступают на выходы 6. В результате на выходах 6 устройства образуется код количества единиц во входном числе. Информация о соотношении нулей и единиц на входе 11 может быть обеспечена аналоговыми пороговыми элементами,5 10 15 20 25 ЗО 35 40 45 Формула изобретения Устройство для подсчета количества единиц в двоичном числе содержащее входной регистр. выходной регистр, преобразователь двоичного кода в уплотненный код и преобразователь уплотненного кода в код количества единиц, причем входы устройства соединены с входами вход- ного регистра, выходы которого соединены с входами преобразователя двоичного кода в уплотненный код, выходы которого соединены с входами преобразователя уплотненного кода в код количества единиц, выходы которого соединены с входами выходного регистра, выходы которого соединены с выходами устройства, при этом преобразователь двоичного кода в уплотненный код содержит узел управляемой инверсии, информационные входы которого соединены с входами преобразователя двоичного кода в уплотненный код, выходы узла управляемой инверсии соединены с входами матрицы модулей, выходы которой соединены с информационными входами узла формирования уплотненного кода, выходы которого соединены с выходами преобразователя двоичного кода в уплотненный код, а управляющий вход узла формирования уплотненного кода соединен с выходом элемента НЕ, вход которого соединен с управляющим входом узла управляемой инверсии и с входом признака непревышения половины количества единиц в двоичном числе устройства, о т л и ч а ю щ е ес я тем, что, с целью сокращения аппаратурных затрат, в матрицу модулей введены и/2 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и и/2 элементов И, где и-разрядность входного числа усройства, причем входы матрицы модулей с первого по и/2 соединены соответственно с первыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и с первыми входами элементов И,. а входы матрицы модулей с (и/2+1)-го по и-й соединены соответственно с вторыми вхо- дами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и свторыми входами элементов И, выходы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединены с первыми входами модулей с первого по и/2 первой строки матрицы, выходы элементов И соединены с первыми входами модулей с(и/2+1)-го по (и)-й и с вторым входом (и - -1)-го модуля первой строки матрицы, второй выход п/2+1)-го модуля Я-й строки матрицы1795455 Палий Редакто СССР оизводственно-издательский комбинат "Патент", г, Ужгород, ул,Гагарина,СоставитТехред М аказ 431 ТиражВНИИПИ Государственногокоми113035, Москв ь В,Гусеворгентал а по изобре Ж, Раушс Подписноеиям и открытиям прия наб., 45