Устройство для подсчета количества единиц в двоичном числе Советский патент 1993 года по МПК G06F7/50 

Фиг.1

Изобретение относится к автоматике и вычислительной технике.

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

Недостатком устройства является большое количество элементов, растущее по

п2 п функции -у -

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

Недостатком устройства является большое число элементов, растущее по функции

(п+1)/21

I (п-0,

i 1

Цель изобретения - сокращение аппаратурных затрат.

Поставленная цель достигается тем, что в устройстве для подсчета количества единиц в двоичном числе, содержащем входной регистр, выходной регистр, преобразователь двоичного кода в уплотненный код и преобразователь уплотненного кода в код количества единиц, причем входы устройства соединены с входами входного регистра, выходы которого соединены с входами преобразователя двоичного кода в уплотненный код, выходы которого соединены с входами преобразователя уплотненного кода в код количества единиц, выходы которого соединены с входами выходного регистра, выходы которого соединены с выходами устройства, при этом преобразователь двоичного кода в уплотненный код содержит узел управляемой инверсии, информационные входы которого соединены с входами преобразователя двоичного кода в уплотненный код, выходы узла управляемой инверсии соединены с входами матрицы модулей, выходы которой соединены с информационными входами узла формирования уплотненного кода, выходы которого соединены с выходами преобразователя двоичного кода в уплотненный код, а управляющий вход узла формирования уплотненного кода соединен с выходом элемента НЕ, вход которого соединен с управляющим входом узла управляемой инверсии и с входом признака непревышения половины количества единиц в двоичном числе устройства, в матрицу модулей введены п/2 элементов

ИСКЛЮЧАЮЩЕЕ ИЛИ и п/2 элементов И, где п - разрядность входного числа устройства, причем входы матрицы модулей с первого по n/2-й соединены соответственно с первыми входами элементов ИСКЛЮЧАЮ5 ЩЕЕ ИЛИ и с первыми входами элементов И, а входы матрицы модулей с (n/2+1)-rq по n-й соединены соответственно со вторыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и со вторыми входами элементов И, выходы

0 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединены с первыми входами модулей с первого по n/2-й первой строки матрицы, выходы элементов И соединены с первыми входами модулей с (п/2+1)-го по (п-1)-й и со вторым

5 входом (п-1)-го модуля первой строки матрицы, второй выход (п/2+1)-го модуля s-ой строки матрицы (, n/4) соединен со вторым входом п/2-го модуля (2з-1)-й строки матрицы и со вторым входом п/2-го модуля

0 2з-ой строки матрицы.

На фиг. 1 представлена функциональная схема устройства для подсчета количества единиц в двоичном числе; на фиг. 2 - схема выполнения модифицированной мат5 рицы модулей со входным преобразователем - модификатором кода.

Устройство для подсчета количества единиц в двоичном числе содержит п-раз- рядный входной регистр 1, выходной ре0 гистр 2, преобразователь 3 двоичного кода в уплотненный код, преобразователь 4 уплотненного кода в код количества единиц, входы 5, выходы 6. Преобразователь 3 содержит узел 7 управляемой инверсии, узел

5 8 формирования уплотненного кода, эле-, мент НЕ 9 и модифицированную матрицу модулей 10. Устройство содержит также вход 11 признака непревышения половины количества единиц в двоичном числе. Моди0 фицированная матрица 10 содержит модули 12, каждый из которых содержит элемент ИЛИ 13 и элемент И 14, кроме того, модифицированная матрица 10 содержит группу элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 15 и груп5 пуэлементов И 16.

Устройство работает следующим образом.

На входной регистр 1 через входы устройства 5 заносится код числа. С выходов входного регистра 1 код числа передается

на узел 7, управляемый по входу 11. Пусть сигнал 1 на входе 11 информирует устройство о том. что число единиц в обрабатываемом коде не больше числа нулей, тогда узел 7 пропускает через себя информацию без изменения. Если на входе 11 сигнал О, то узел 7 инвертирует каждый разряд кода, обеспечивая тем самым подсчет числа нулей с помощью той же аппаратуры, подсчитывающей число единиц в коде. Первая половина выходов узла 7 передается на первые входы группы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 15 и первые входы группы элементов И 16, на вторые входы обеих этих групп передаются сигналы со второй половины выходов узла 7. При этом на выходах группы элементов И 16 выявляются единички, отстоящие друг от друга в точности на рассто- янии п/2, или другими словами, идентифицируется число таких пар. На выходах элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 15 накапливаются все остальные единички, не попавшие в число пар, и только они. Поскольку число единичек, поступающих с выхода узла 7, не превышает половины общего числа выходов, то число единичек, идентифицирующих число пар на выходах группы элементов И 16, не будет превышать четверти разрядности обрабатываемого кода, и, следовательно, число элементов 12 матрицы 10 может быть сокращено.

В итоге на выходе модифицированной матрицы из модулой 12 образуется уплотненная последовательность единиц, длина которой равна количеству единиц во входном числе при общем количестве единиц, не превышающем число нулей, либо числу нулей во входном числе при сигнале О на входе 11.

Информация из матрицы 10 поступает на входы узла 8, с помощью которого приводится к уплотненному коду, равному количеству единиц во входном числе. Если с входа 11 поступает сигнал 1, то работа второй половины узла 8 блокируется, уплотненный код, равный количеству единиц во входном числе, поступает на входы преобразователя 4. Если на вход 11 поступает сигнал О, то на первую половину входов преобразователя 4 засыпаются 1, а на вторую половину входов преобразователя 4 посылаются инверсные значения выходов матрицы 10.

Сигнал через выходной регистр 2 поступают на выходы 6. В результате на выходах 6 устройства образуется код количества единиц во входном числе. Информация о соотношении нулей и единиц на входе 11 может быть обеспечена аналоговыми пороговыми элементами.

Формула изобретения

Устройство для подсчета количества единиц в двоичном числе содержащее 5 входной регистр, выходной регистр, преобразователь двоичного кода в уплотненный код и преобразователь уплотненного кода в код количества единиц, причем входы устройства соединены с входами вход0 ного регистра, выходы которого соединены с входами преобразователя двоичного кода в уплотненный код, выходы которо го соединены с входами преобразователя уплотненного кода в код

5 количества единиц, выходы которого соединены с входами выходного регистра, выходы которого соединены с выходами устройства, при этом преобразователь двоичного кода в уплотненный код содер0 жит узел управляемой инверсии, информационные входы которого соединены с входами преобразователя ДЕЮИЧНОГО кода в уплотненный код, выходы узла управляемой инверсии соединены с входами матрицы мо5 дулей, выходы которой соединены с информа- ционными входами узла формирования уплотненного кода, выходы которого соединены с выходами преобразователя двоичного кода в уплотненный код, а управляющий вход

0 узла формирования уплотненного кода соединен с выходом элемента НЕ, вход которого соединен с управляющим входом узла управляемой инверсии и с входом признака непревышения половины количества единиц в

5 двоичном числе устройства, отличающее- с я тем, что, с целью сокращения аппаратурных затрат, в матрицу модулей введены п/2 эле ментов ИСКЛЮЧАЮЩЕЕ ИЛИ и п/2 элементов И, где n-разрядность входного числа

0 устройства, причем входы матрицы модулей с первого по п/2 соединены соответственно с первыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и с первыми входами элементов И,, а входы матрицы модулей с (п/2+1)-го по п-й

5 соединены соответственно с вторыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и с вторыми входами элементов И. выходы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединены с первыми входами модулей с первого по п/2

0 первой строки матрицы, выходы элементов

И соединены с первыми входами модулей с

(п/2+1)-го по (п-1)-й и с вторым входом (п-1)-го модуля первой строки матрицы, второй

выход (п/2+1)-го модуля S-й строки матрицы

5 (, п/4) соединен с вторым входом n/2-ro модуля ()-й строки матрицы и с вторым входом п/2 модуля 25-й строки матрицы.

Фиг. I

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - сокращение аппаратурных затрат. Устройство для подсчета количества единиц в дво- ичном числе содержит п-разрядный входной регистр 1, выходной регистр 2, преобразователь 3 двоичного кода в уплотненный кодопреобразователь 4 уплотненного кода в код количества единиц. Преобразователь 3 содержит узел 7 управляемой инверсии, узел 8 формирования уплотненного кода, элемент НЕ 9 и модифицированную матрицу 10 модулей. Узлы 7 и 8 управляются с входа 11, Цель изобретения достигается введением в матрицу 10 п/2 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и п/2 элементов И. 2 ил.