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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (st)s G 06 F 7/50

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛ ЬСТВУ (21) 4898447/24 (22) 29.12.90 (46) 15,02.93. Вюл. N 6 (71) Новосибирский государственный университет им. Ленинского комсомола (72) П. А. Ким, К, С, Алсынбаев, В, А. Забелин и Н, А. Осипов (56) Авторское свидетельство СССР

¹ 798830, кл. G 06 F 7/50, 1978.

Авторское свидетельство СССР

¹ 1569822, кл. G 06 F 7/50, 1988. (54) УСТРОЙСТВО ДЛЯ ПОДСЧЕТА КОЛИЧЕСТВА ЕДИНИЦ B ДВОИЧНОМ ЧИСЛЕ

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

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

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

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

n n функции

2 2

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

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

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

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

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

И, а входы матрицы модулей с (n/2+1)-го по и-й соединены соответственно со вторыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и со вторыми входами элементов И, выходы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединены с первыми входами модулей с первого по и/2-й первой строки матрицы, выходы элементов И соединены с первыми входами модулей с (n/2+1)-ro по (п — 1)-й и со вторым входом (и — 1)-го модуля первой строки матрицы, второй выход (n!2+1)-го модуля s-ой строки матрицы (э=Г; п74) соединен со вторым входом.n/2-го модуля (2s — 1)-й строки матрицы и со вторым входом n/2-го модуля

30 2s-ой строки матрицы.

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

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

45 8 формирования уплотненного кода, элемент НЕ 9 и модифицированную матрицу модулей 10. Устройство содержит также вход 11 признака непревышения половины количества единиц в двоичном числе. Моди50 фицированная матрица 10 содержит. модули

12, каждый из которых содержит элемент

ИЛИ 13 и элемент И 14, кроме того, модифицированная матрица 10 содержит группу элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 15 и группу элементов И 16.

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

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

1795455

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

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

Устройство для подсчета количества единиц в двоичном числе. содержащее входной регистр. выходной регистр, преобразователь двоичного кода в уплотненный код и преобразователь уплотненного кода в код количества единиц, причем входы устройства соединены с входами вход- ного регистра, выходы которого соединены с входами преобразователя двоичного кода в уплотненный код, выходы которого соединены с входами преобразователя уплотненного код;* в код количества единиц, выходы которого соединены с входами выходного регистра, выходы которого соединены с выходами устройства, при этом преобразователь двоичного кода в уплотненный код содержит узел управляемой инверсии, информационные входы которого соединены с входами преобразователя двоичного кода в уплотненный код, выходы узла управляемой инверсии соединены с входами матрицы модулей. выходы которой соединены с информационными входами узла формирования уплотненного кода, выходы которого соединены с выходами преобразователя двоичного кода в уплотненный код, а управляющий вход узла формирования уплотненного кода соединен с выходом элемента НЕ, вход которого соединен с управляющим входом узла управляемой инверсии и с входом признака непревышения половины количества единиц в двоичном числе устройства, о т л и ч а ю щ е ес я тем, что, с целью сокращения аппаратурных затрат, в матрицу модулей введены и/2 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и n/2 элементов И, где и-разрядность входного числа ус ройства, причем входы матрицы модулей с первого по n/2 соединены соответственно с первыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и с первыми входами элементов И,. а входы матрицы модулей с (n/2+1)-го по и-й соединены соответственно с вторыми вхо дами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и с вторыми входами элементов И, выходы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединены с первыми входами модулей с первого по n/2 первой строки матрицы, выходы элементов

И соединены с первыми входами модулей с (n/2+1)-го по (n-1)-й и с вторым входом (n—

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

1795455

Составитель В,Гусев

Техред M,Ìîðãåíòàë

Корректор Т.Палий

Редактор

Производственно-издательский комбинат "Патент", r, Ужгород, ул.Гагарина. 101

Заказ 431 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5